Criticism of a proposed stream cipher requested.
in [Cryptography]
|
Prev: A simple scheme of combining PRNGs
Next: Criticism of a proposed floating point (cs)prng requested.
From: Peter Fairbrother on 3 Jun 2010 09:21 Cryptoengineer wrote: > 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? Well, for a start, it's trivially breakable with a single known plaintext of something less than 101 bits length ... (and the "stirring" doesn't help any). We have 100 known bit strings, some number of which are xored with each other and the plaintext. With 101 bits of ciphertext and corresponding known plaintext we now have 101 equations in 100 variables - that's trivial. Ciphertext-only attacks are not that much harder. -- Peter Fairbrother
From: Mok-Kong Shen on 3 Jun 2010 09:43 Peter Fairbrother wrote: [snip] > Ciphertext-only attacks are not that much harder. For stream ciphers, it's desirable (IMHO more desirable than in the case of block ciphers) to use message specific (i.e. unique) keys. This would render many of the known attacks valueless. Deriving such message keys from a master-key shouldn't as a rule amount to a huge problem. See also the thread "On the general benefits of introducing dynamics into encryption processing" of 01.05.2010. M. K. Shen
From: Francois Grieu on 3 Jun 2010 09:50 On 03/06/2010 15:21, Peter Fairbrother wrote: > Cryptoengineer wrote: >> 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? > > Well, for a start, it's trivially breakable with a single known > plaintext of something less than 101 bits length... Yes. Paul Rubin's post was the first to state that the cryptosystem, as originally described by Peter Trey, is linear and thus solvable with little more known plaintext than the key size. > (and the "stirring" doesn't help any). Agreed, "stirring" of the plaintext would not help a lot, and "stirring" of the ciphertext would not help at all. But Keith F. Lynch, in his post dated Thu, 3 Jun 2010 03:09:12 +0000 (UTC), after describing "stirring" on plaintext, says: >> My complete system consists of: >> * Generate S, the hashed together key-defined subset of the square >> roots of the first hundred primes, as many binary digits of each >> as there are bits in the plaintext file. >> * Hash the plaintext with S. >> * "Stir" the result. >> * Hash this new result with a "stirred" copy of S. >> * Reverse-stir the latest result (i.e. start at the end of the >> 256-character "alphabet" and work backwards). >> * Hash the latest result with S. [I guess "hash" means "XOR"] So there are 3 "stirring" / shuffling involved; 2 are data-dependant, and all 3 are keystream-dependant; it is no longer a stream cipher. All this largely breaks the straight linearity-based attack, at least for known but arbitrary plaintext. Fran�ois Grieu
From: Cryptoengineer on 3 Jun 2010 10:42 On Jun 3, 9:50 am, Francois Grieu <fgr...(a)gmail.com> wrote: > On 03/06/2010 15:21, Peter Fairbrother wrote: > > > > > Cryptoengineer wrote: > >> 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? > > > Well, for a start, it's trivially breakable with a single known > > plaintext of something less than 101 bits length... > > Yes. Paul Rubin's post was the first to state that the cryptosystem, as > originally described by Peter Trey, is linear and thus solvable with > little more known plaintext than the key size. > > > (and the "stirring" doesn't help any). > > Agreed, "stirring" of the plaintext would not help a lot, and "stirring" > of the ciphertext would not help at all. > > But Keith F. Lynch, in his post dated Thu, 3 Jun 2010 03:09:12 +0000 > (UTC), after describing "stirring" on plaintext, says: > > >> My complete system consists of: > >> * Generate S, the hashed together key-defined subset of the square > >> roots of the first hundred primes, as many binary digits of each > >> as there are bits in the plaintext file. > >> * Hash the plaintext with S. > >> * "Stir" the result. > >> * Hash this new result with a "stirred" copy of S. > >> * Reverse-stir the latest result (i.e. start at the end of the > >> 256-character "alphabet" and work backwards). > >> * Hash the latest result with S. > > [I guess "hash" means "XOR"] > > So there are 3 "stirring" / shuffling involved; 2 are data-dependant, > and all 3 are keystream-dependant; it is no longer a stream cipher. > All this largely breaks the straight linearity-based attack, at least > for known but arbitrary plaintext. > > François Grieu [I'm the OP. I asked for criticism of Keith's algorithm]. Keith is cryptographically naive, his use of 'hash' for 'xor' is simply a demonstration of that. Back in the original thread, I did agree that re-xoring after 'stirring' the cryptotext or keystream from the first stage did appear to significantly improve the system. However, it remains very slow. Finally, what he describes above is a bit different than what he originally proposed; first he talked about the stream cipher as I described at the top of the thread; later he added in the 'stirring' function, which he believed turned the algorithm into a 'block cypher'[sic]. Here's his original description of the use of 'stirring': - start quote - So I start by generating a not-an-otp by hashing together some set of square roots. Call the plaintext S1 and the not-an-otp S2. I can hash S1 and S2 together to make S3, the cyphertext. That's what I described in previous messages. But suppose I then stir S3 in the way I described above, then hash it with S2 a second time to create S4? I can then stir S4, or perhaps S2, or both, then hash one of both of them with a stirred S1. The possible permutations are limitless. I actually forget what combination of these I use for my offsite backups, as I wrote the program some years ago. - end quote - This is far from the worst amateur system presented in this newsgroup. We'll see more in the future. Keith trusts his system. Fortunately, the rest of us don't have to. pt
From: Mike Amling on 4 Jun 2010 11:41
Cryptoengineer wrote: > The possible permutations are limitless. I actually forget what > combination of these I use for my offsite backups, as I wrote the > program some years ago. Good luck doing a restore. --Mike Amling |