At 2:14 PM -0700 10/20/2000, Bram Cohen wrote:
This is just silly. There's nothing wrong with Rijndael.
Maybe so. I do agree that Rijndael is an excellent design and a good choice for AES. But it hasn't been tested enough for complete confidence, in my opinion. Supposedly NSA takes 7 years to vet a new cipher. If anything, the public cryptographic community should take even longer, given we lack the budgets and accumulated methodologies that NSA can bring to bear. Testing is the most expensive part of any new cipher effort. So I think there is a practical basis for at least asking if there is a simple way to combine the AES finalists and take advantage of all the testing that each has already undergone. And, IMHO, it is an interesting theoretical question as well. Even if the answer is "yes," I am not advocating that it be used in most common applications, e.g network security, because there are so many greater risks to be dealt with. But it might make sense in some narrow, high value, applications. At 2:31 PM -0400 10/23/2000, John Kelsey wrote:
[long, clear exposition deleted]
The reason the keys have to be independent is because otherwise, the proof doesn't work. If the keys are chosen so that K1 == K2, then I can't build these attacks for my proof, because I can't choose F_{K2} without knowing K1.
I agree that Massey and Maurer's proof requires independent keys for each cipher, and have tried meet that requirement in my design. But the fact that Massey and Maurer's proof fails does not mean that the keys must, in fact, be independent for the combined cipher to be secure. See below.
Now, we can also come up with examples of places where choosing K1 and K2 to be related is a bad idea. For example, imagine the following ``game:'' You define some structure for putting N block ciphers together, and then I get to choose the N ciphers, with the constraint that at least one of the N must be strong against all attacks. Now, in this model, it's clear that if the keys are all equal, I can choose the ciphers so that a structure like E1(E2(E2(X))) is easily broken. (Let E1 = 3DES encryption, E2 = 3DES decryption, and E3 = the identity cipher.)
In this model, it's also clear that when the keys are independent, I can't choose the ciphers to include one strong cipher and N-1 ones specially designed to me to make the composition weak. If I could, I could always convert the algorithm into a chosen-plaintext attack on the strong cipher.
I have long felt that there should be some way to exclude using the inverse cipher in these counter examples just as we exclude the possibility that the attacker can simply guess the key. I think I have a different approach to formulating the problem which does that: Let's define a modified version of your game: game2. We'll stick with the two cipher case E(F()) for the moment. Here are the rules: 1. Just as in your game, you get to choose two ciphers, one of which has to be strong. 2. You pick which is E and which is F. 3. The ciphers have to be bijections (one-to-one, onto functions) on {1,...,2**N} where N is the block size in bits. In particular, this means each cipher has no internal state. The same input always produces the same output. 4. If K is the key for the combined cipher, then the key for E is also K, but the key for F is K xor M, where M is a bit string the same length as K that will be selected randomly AFTER you have specified your two ciphers. You will then be informed of its value (which will never change) and may use it in attempting to break E(F()), but you cannot input it into either cipher. If a strong cipher is assumed to have the property that you cannot derive any information about the content of an input block from examining the output block unless you know the complete key, then I claim E(F()) cannot be broken without guessing M. I am making a very broad assumption about what a strong cipher is, but even without it, I believe my version of the game breaks up all counterexamples that use the inverse ciphers to break E(F()). Now you might say "this construction proves my point, you are not using the same keys." That is true, but the keys are far from independent. I can go even further. Most block ciphers have some internal constants that can be varied. There may be constraints on how these constants are selected, but there is still some underlying variability. You can think of these constants as playing the same role as M in game2. If we were allowed to select final values for these constants in the strong cipher after the probe cipher was finalized, one could make a similar argument without a separate M.
...
The problem with OFB is that what you get is a stream cipher and that, in turn, means a unique IV for each message is required.
Hmm. It seems like you're going to need an IV for any chaining mode. Using a superstrong block cipher, but then not bothering to use a chaining mode, is just silly.
The IV reuse problem *is* a lot worse for OFB and counter modes than for any other mode. Though once you decide you're going to use CFB- or CBC-mode, and choose a random IV, nearly all attacks end up being chosen-plaintext attacks, so maybe that's another reason not to worry too much about which cipher is first.
Block ciphers are easy to test and audit and are hard to subvert (you have to alter the cipher at each node and at the same time.) On the other hand, IV generation schemes are hard to test, nearly impossible to audit, and relatively easy to subvert (you just have to sabotage the RNG at one node). It would be really foolhardy of me to introduce a stream cipher with those known risks, just to counter what I admit is a very small chance of an undetected flaw in Rijndael.
So here is my draft proposal for the Paranoid Encryption Standard, PES: (P is a plaintext block and K is the user key.)
PES(P) =Twofish(Serpent(MARS(DEAL(AES(P))))), where:
the key for AES is SHA2(K||"Rijndael") the key for DEAL is SHA2(K||"DEAL") the key for MARS is SHA2(K||"MARS") the key for Serpent is SHA2(K||"Serpent") the key for Twofish is SHA2(K||"Twofish")
Just an aside: What properties are you assuming for SHA2? Because you're going to all this trouble to build a paranoid encryption standard, but then you're doing this weird construction to derive keys for everything, and it's not clear that you can prove anything about the structure when SHA2 is just a collision-resistant hash function. ...
I am assuming SHA2 is a one-way hash as well. So breaking one of the component ciphers will not allow an attacker to derive the key for any of the other ciphers. It was an ad hoc response to your comment about the need for key independence. Better suggestions are welcome. My game2 construction, above, suggests that key independence doesn't have to be super strong. I suppose based on that argument I should use constants that were clearly derived after the individual cipher designs had been completed. One possibility might be to use voting results from the upcoming Nov. 7 U.S. presidential election: say, Alabama's for AES. Delaware's for DEAL, Maryland's for MARS and South Carolina's for Serpent, Tennessee's for Twofish. (Final voting results as decimal numbers in ascii, with no punctuation or leading zeros, in alphabetical order by candidate: Buchanan, Bush, Gore, Nader). Arnold Reinhold