Prev: A simple scheme of combining PRNGs
Next: Criticism of a proposed floating point (cs)prng requested.
From: Cryptoengineer on 2 Jun 2010 09:48
Those who have been in this group for a long time may recognize my
name. I'm still around.

In another group, an acquaintance recently described his homegrown
stream cipher (yes, I know, I know....). I'd like to provide some
informed criticism to him. He's a pretty decent mathematician, but
knows very little about crypto.

It's a keyed stream cipher.

1. Select a 100 bit random key (too short, in my opinion).
Each bit is mapped to one of the first 100 primes.

2. There are algorithms to compute successive digits or bits of square
roots. For each '1' bit in the key calculate the square root of the
corresponding prime, out to the length of the message to be encrypted.

3. Xor the fractional parts of the calculated square roots together,
and xor with the message. This creates the encrypted message.

Aside from the short key, my main critique is that this is going to
be slow. You can speed it up by precalculating the square roots out to
a length greater than most messages, but that will require a good deal
of storage.

Of course, it has the key distribution drawbacks of any symmetric
cipher.

So, what other drawbacks can I present to him?

Peter Trei
From: Scott Fluhrer on 2 Jun 2010 10:02

"Cryptoengineer" <petertrei(a)gmail.com> wrote in message
news:b242a635-b84c-4455-94fa-5e8ed512fd55(a)o4g2000vbo.googlegroups.com...
> Those who have been in this group for a long time may recognize my
> name. I'm still around.
>
> In another group, an acquaintance recently described his homegrown
> stream cipher (yes, I know, I know....). I'd like to provide some
> informed criticism to him. He's a pretty decent mathematician, but
> knows very little about crypto.
>
> It's a keyed stream cipher.
>
> 1. Select a 100 bit random key (too short, in my opinion).
> Each bit is mapped to one of the first 100 primes.
>
> 2. There are algorithms to compute successive digits or bits of square
> roots. For each '1' bit in the key calculate the square root of the
> corresponding prime, out to the length of the message to be encrypted.
>
> 3. Xor the fractional parts of the calculated square roots together,
> and xor with the message. This creates the encrypted message.
>
> Aside from the short key, my main critique is that this is going to
> be slow. You can speed it up by precalculating the square roots out to
> a length greater than most messages, but that will require a good deal
> of storage.

Even with precomputing, it'll still be slow.

>
> Of course, it has the key distribution drawbacks of any symmetric
> cipher.
>
> So, what other drawbacks can I present to him?

It can be broken in O(2**50) time (and a large amount of memory) using a
standard meet-in-the-middle attack (
http://en.wikipedia.org/wiki/Meet-in-the-middle_attack ). This attack works
because the attacker can model the cipher as one where you encrypt using the
first 50 bits of key (and the first 50 primes), and then encrypt using the
second 50 bits of key (and the next 50 primes).

On the other hand, it can be a fool's errand to point out flaws to a novice
cryptography; he's likely to make a trivial change that voids the attack
exactly as specified and then claim it's perfect. It's rather better if you
can get him to find the attacks; it's easier on you, and he'll learn more.

--
poncho


From: Francois Grieu on 2 Jun 2010 12:24
[basically the only technical contribution in my previous message was
dead wrong, and I removed it.

On 02/06/2010 15:48, Peter Trey wrote:
> (..) an acquaintance recently described his homegrown
> stream cipher (yes, I know, I know....). I'd like to provide some
> informed criticism to him. He's a pretty decent mathematician, but
> knows very little about crypto.
>
> It's a keyed stream cipher.
>
> 1. Select a 100 bit random key (too short, in my opinion).
> Each bit is mapped to one of the first 100 primes.
>
> 2. There are algorithms to compute successive digits or bits of square
> roots. For each '1' bit in the key calculate the square root of the
> corresponding prime, out to the length of the message to be encrypted.
>
> 3. Xor the fractional parts of the calculated square roots together,
> and xor with the message. This creates the encrypted message.
>
> Aside from the short key, my main critique is that this is going to
> be slow. You can speed it up by precalculating the square roots out to
> a length greater than most messages, but that will require a good deal
> of storage.
>
> Of course, it has the key distribution drawbacks of any symmetric
> cipher.
>
> So, what other drawbacks can I present to him?

As for any keyed stream cipher, a unique shared random key must be used
for each message.

The system is awfully inefficient for long messages. By contrast, we
know simple stream ciphers with conjectured n-bit security requiring
only 3*n bits of storage and a small constant number of XOR per output bit:
<http://en.wikipedia.org/wiki/Alternating_step_generator>

As pointed by Scott Fluhrer, there is a meet-in-the-middle attack
reducing the cost to O(2^50) time and memory. If the amount of memory is
a problem (2^57 bits is a lot), there are well-known trade-offs between
time and memory.

I suspect that there might be ways to trade abundance of known
plaintext against less time and/or memory; or perhaps a much more
devastating attack. But I fail to pinpoint that right now.


Fran�ois Grieu
From: Paul Rubin on 2 Jun 2010 12:46
Francois Grieu <fgrieu(a)gmail.com> writes:
> I suspect that there might be ways to trade abundance of known
> plaintext against less time and/or memory; or perhaps a much more
> devastating attack. But I fail to pinpoint that right now.

Isn't this a trivial linear algebra problem? Let K1...K100 be the
unknown key bits. Let P1...P100 be the known plaintext. Let C1,C2....
be the ciphertext. Let Si,j be the j'th bit of the square root of i.
So

Cn = K1*S1,n + K2*S2,n + ... + K100*S100,n + Pn

where the multiplication is in GF(2). Solve simultaneous equations to
get K. Am I misunderstanding the question and/or overlooking something
silly?
From: Francois Grieu on 2 Jun 2010 13:00
On 02/06/2010 18:46, Paul Rubin wrote:
> Francois Grieu <fgrieu(a)gmail.com> writes:
>> I suspect that there might be ways to trade abundance of known
>> plaintext against less time and/or memory; or perhaps a much more
>> devastating attack. But I fail to pinpoint that right now.
>
> Isn't this a trivial linear algebra problem? Let K1...K100 be the
> unknown key bits. Let P1...P100 be the known plaintext. Let C1,C2....
> be the ciphertext. Let Si,j be the j'th bit of the square root of i.
> So
>
> Cn = K1*S1,n + K2*S2,n + ... + K100*S100,n + Pn
>
> where the multiplication is in GF(2). Solve simultaneous equations to
> get K. Am I misunderstanding the question and/or overlooking something
> silly?

I (now) second that.

n bits of known plaintext reveal n equations of the form

(K1 & S1,n) ^ (K2 & S2,n) ^ ... ^ (K100 & S1,n) = Cn^Pn

and this is a linear system since a&(b^c) = (a&b)^(a&c)

100 bits of known plaintext (or slightly more in degenerate cases),
Gaussian elimination, and the key is recovered.


Fran�ois Grieu
 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: A simple scheme of combining PRNGs
Next: Criticism of a proposed floating point (cs)prng requested.