Re: Jail Cell Cipher (modified RC4)
Paul Crowley has shown that Schneier's Solitaire cipher is insecure. See http://www.ciphergoth.org/crypto/solitaire/. Repetitions occur with frequence 1/22.5 rather than 1/26 as they should. Also, the state machine is not reversible, contrary to the design intent.
Re: Re: Jail Cell Cipher (modified RC4)
- Original Message - From: Jeremy Lennert [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, February 23, 2002 8:15 AM Subject: CDR: Re: Jail Cell Cipher (modified RC4) Unfortunately it has a rather damning effect on the cipher. First in the key scheduling there is a distinct possibility of keys that are impossible. It assumes that all K[i] are generators mod 37, so using a key where the offset is 0 will result in an infinite loop in the key scheduling, this is obviously a bad design decision. Second the distinguisher from random for such a small RC4 state would require a relatively small known plaintext. In fact at that size I think there are better attacks against it than the distinguishers known for full sized RC4. I believe it would be achievable to actually determine that complete state, although it would take more significant amounts of work than would be applied to most inmate mail (an encrypted message would probably be simply discarded and never delivered). The specification for the key requires all key values to be nonzero. From the web site: an array of key values K, where each value is a nonzero alphabetical character or its numerical equivalent However, there was an error in the source code that allowed zeroes in the key. This has been corrected. Any zeroes in the key definition now cause the program to abort with an invalid character error message. Regarding the distinguisher, I don't think I understand how distinguishing the keystream from random amounts to an attack that will recover the internal state. Could you offer further clarification on that? In this case they are two different attacks. The first attack being the distinguisher which will let the attacker read the plaintext, but not necessarily find the internal state. The second an attack on the internal state where the known small variations in the state between outputs could be used to compute a state that is at least a full collision on the outputs. Incidentally, for paper-and-pencil applications, I'm assuming that the message length will not exceed about 100 characters. I think that will be small enough to save the security of the system, but I'm not sure. The problem with using full RC4 is not in the actual keystream generation, but in running the key-scheduling algorithm. Even if we only ran the KSA for one round through the permutation table, estimated time is about 50 minutes (not necessarily impractical, but making many rounds to improve security or repeated trials to improve accuracy very difficult) and the chances of performing that entire round without error for my current best estimations of accuracy are about 1 in 150,000. Why not just memorize the permutation table? It's only 37 characters. Also I don't see where a difference of an hour or two will necessarily make a difference, the point of incarceration is that you can't go out and do anything you want, you have to sit in your cell for 23 hours a day. So anything that you can encrypt in 23 hours is good enough. By your estimates that gives time for 27 KSAs (which wouldn't increase security in the slightest, a permutation is a permutation) which I think should be more than enough KSAs for any reasonable demands. For the modified RC4, accuracy still isn't great, but it is good enough that careful error-checking may leave the algorithm feasible in terms of both time and accuracy. It's the security of the scheme, not the usability, that I am questioning. I think the artifacts of RC4 will be enhanced to the point where the security is, for all practical purposes, useless. The only question remaining in my mind is how long before those artifacts can be detected and/or made use of? Joe
Re: Jail Cell Cipher (modified RC4)
On Fri, 22 Feb 2002, Neil Johnson wrote: I believe that Ron Rivest (the R in RC4) has already created a version for jail-cell use. Pick up a copy of Cryptonomicon by Neal Stephenson. It's used in the book and there is an appendix in the back that explains the algorithm in good detail. (Stephenson calls it Pontifex in the book). Huh? Pontifex is Bruce Schneier's Solitare. (Neal changed the name as not to give away the fact that it relied on a deck of cards.) What's this have to do with Rivest? It works with playing cards, that would probably be less conspicuous in Jail than pencil and paper. -Neil -MW-
Re: Jail Cell Cipher (modified RC4)
Unfortunately it has a rather damning effect on the cipher. First in the key scheduling there is a distinct possibility of keys that are impossible. It assumes that all K[i] are generators mod 37, so using a key where the offset is 0 will result in an infinite loop in the key scheduling, this is obviously a bad design decision. Second the distinguisher from random for such a small RC4 state would require a relatively small known plaintext. In fact at that size I think there are better attacks against it than the distinguishers known for full sized RC4. I believe it would be achievable to actually determine that complete state, although it would take more significant amounts of work than would be applied to most inmate mail (an encrypted message would probably be simply discarded and never delivered). The specification for the key requires all key values to be nonzero. From the web site: an array of key values K, where each value is a nonzero alphabetical character or its numerical equivalent However, there was an error in the source code that allowed zeroes in the key. This has been corrected. Any zeroes in the key definition now cause the program to abort with an invalid character error message. Regarding the distinguisher, I don't think I understand how distinguishing the keystream from random amounts to an attack that will recover the internal state. Could you offer further clarification on that? Incidentally, for paper-and-pencil applications, I'm assuming that the message length will not exceed about 100 characters. I don't think this reduced version of RC4 would be very suitable even assuming a perfect delivery mechanism. I've actually considered a similar question before (http://groups.google.com/groups?hl=enth=f0d53f0eb5d7c011see km=9s2akd%24qk 4%241%40nntp9.atl.mindspring.netframe=off), I never managed to come up with anything really suitable. I did find a solution where the inmate is given a computer and a compiler, use RC5 to key itself (very similar to Blowfish), a 128-bit block, and 20 rounds. Should withstand pretty much any analysis work (except throw it in the trash cryptanalysis). This suffers from being difficult to calculate with a pencil and paper, and so doesn't really fit the requirement for a jail cell cipher. Using full RC4 is actually doable. Take a sheet (or multiple sheets) of paper, create 3 sets of 0,...,255 numbers. on a large table in front of you (or in a controlled grid) place the first 0...255 set in order, that's your state array, the other two sets are for your i and j values. If a guard is approaching and the data must be destroyed simply blow very hard and all the numbers are scrambled. Of course you will probably be adding and subtracting instead of performing XOR. This is obviously pain-staking, and slow, but it will offer the same security as a computer running the RC4 algorithm. Joe The problem with using full RC4 is not in the actual keystream generation, but in running the key-scheduling algorithm. Even if we only ran the KSA for one round through the permutation table, estimated time is about 50 minutes (not necessarily impractical, but making many rounds to improve security or repeated trials to improve accuracy very difficult) and the chances of performing that entire round without error for my current best estimations of accuracy are about 1 in 150,000. For the modified RC4, accuracy still isn't great, but it is good enough that careful error-checking may leave the algorithm feasible in terms of both time and accuracy. Grace Peace, Jeremy
Re: Jail Cell Cipher (modified RC4)
At 10:28 PM -0600 on 2/22/02, Neil Johnson wrote: I believe that Ron Rivest (the R in RC4) has already created a version for jail-cell use. Schneier did Solitaire. Cheers, RAH -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
Re: Jail Cell Cipher (modified RC4)
Yep, I stand corrected. Another place to check is Cyber (or is it Cypher Saber ?). You can get it by going to http://www.diceware.com and hunting around. It has a disscusion on learning how to implement RC4. -neil - Original Message - From: R. A. Hettinga [EMAIL PROTECTED] To: Neil Johnson [EMAIL PROTECTED]; Jeremy Lennert [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Friday, February 22, 2002 10:51 PM Subject: Re: Jail Cell Cipher (modified RC4) At 10:28 PM -0600 on 2/22/02, Neil Johnson wrote: I believe that Ron Rivest (the R in RC4) has already created a version for jail-cell use. Schneier did Solitaire. Cheers, RAH -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
RE: Jail Cell Cipher (modified RC4)
I'm not having difficulty with the implementation (the C++ code included in my first message, also available at http://www.mindflare.com/cipher/jcrc4.cpp , already implements the cipher correctly). I'm inquiring regarding the impact of the changes on the security of the cipher. Grace Peace, Jeremy -Original Message- From: Neil Johnson [mailto:[EMAIL PROTECTED]] Sent: Friday, February 22, 2002 9:29 PM To: Jeremy Lennert; [EMAIL PROTECTED]; R. A. Hettinga Subject: Re: Jail Cell Cipher (modified RC4) Yep, I stand corrected. Another place to check is Cyber (or is it Cypher Saber ?). You can get it by going to http://www.diceware.com and hunting around. It has a disscusion on learning how to implement RC4. -neil
Re: Jail Cell Cipher (modified RC4)
Actually it was Bruce Schneier who created Solitaire (Pontifex) for Cryptonomicon, The basic algorithm is in the back of the book, plus there are several code implementations on the counterpane labs site. -steve -Original Message- From: Neil Johnson [EMAIL PROTECTED] To: Jeremy Lennert [EMAIL PROTECTED]; [EMAIL PROTECTED] [EMAIL PROTECTED] Date: Friday, February 22, 2002 11:30 PM Subject: Re: Jail Cell Cipher (modified RC4) I believe that Ron Rivest (the R in RC4) has already created a version for jail-cell use. Pick up a copy of Cryptonomicon by Neal Stephenson. It's used in the book and there is an appendix in the back that explains the algorithm in good detail. (Stephenson calls it Pontifex in the book). It works with playing cards, that would probably be less conspicuous in Jail than pencil and paper. -Neil - Original Message - From: Jeremy Lennert [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, February 22, 2002 7:06 PM Subject: Jail Cell Cipher (modified RC4) I am attempting to modify the RC4 cipher to be paper-and-pencil computable. I realize that others have tried to construct secure paper-and-pencil ciphers, but I would be very appreciative of any input you may have. In particular, if you are aware of (or can invent) any cryptanalytical attacks of practical use against this cipher, I would appreciate it if you would send me a description of those attacks. The keystream generator is the same as standard RC4, but the permutation table is smaller (37 entries instead of 256) and the key-scheduling algorithm has been completely changed. A more detailed description and a partial analysis can be found here: http://www.mindflare.com/cipher The source code for a C++ program implementing the cipher can be found here (and is also attached): http://www.mindflare.com/jcrc4.cpp although the goal is for the cipher to be paper-and-pencil-computable If there is anything I can do to help you understand the cipher, or if you have any input, please do not hesitate to contact me. My email address is [EMAIL PROTECTED] Thanks for your time, Jeremy [demime 0.97c removed an attachment of type application/octet-stream which had a name of jcrc4.cpp]
