-----BEGIN PGP SIGNED MESSAGE----- At 02:26 PM 10/20/00 -0400, Arnold G. Reinhold wrote:
At 8:13 PM -0400 10/11/2000, John Kelsey wrote:
...
I read the Massey and Maurer paper (One can find it at http://www.isi.ee.ethz.ch/publications/isipap/umaure-mass-inspec-1993 1.pdf ) and I have a couple of comments on it.
Okay. I think it's a lot easier to understand their result and all its implications like this: Suppose we have two ciphers, E_{K}(X),F_{K}(X), and we encrypt by computing C[i] = E_{K1}( F_{K2}( P[i] ) ) Now, suppose I can break this composed cipher, when you choose E and F's keys independently, in a known plaintext attack. I have some algorithm, A(), into which I feed my known plaintexts and the corresponding ciphertexts, and it churns on them for awhile, and returns the keys K1,K2. This algorithm can be used to break E in a known plaintext attack as follows: You encrypt a bunch of messages under E_{K1}(X). I know nothing of K1, but I know the plaintexts and their corresponding ciphertexts. I randomly choose a key K2, encrypt all those ciphertexts with F_{K2}, and then feed the original plaintexts and my ciphertexts into my algorithm for breaking the composed cipher E_{K1}(F_{K2}(X)). That means that a known plaintext attack on E(F()) leads to a known plaintext attack on E(). I can also mount a chosen plaintext attack on F, when you choose a random key K2. I randomly select a key K1, randomly select a bunch of plaintexts, and encrypt them all under E_{K1}. I then send you the ciphertexts and ask you to encrypt them under F_{K2}. You do so, and send me back the results. I now send my original plaintexts and the ciphertexts you sent me into my algorithm for breaking the composed cipher E_{K1}(F_{K2}(X)). That means that a known-plaintext attack on E(F()) leads to a chosen-plaintext attack on F(). All the result is saying is that you can always convert breaking both ciphers to breaking either cipher individually. The cool part of this isn't the worry about which cipher comes first, it's the fact that, with independent keys, you can show that composing the ciphers gives you a cipher no weaker than the stronger of the two ciphers. 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. 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. But these are different arguments. The Massey and Maurer argument, at least as I've understood it, is that the keys have to be independent because otherwise the proof doesn't work, and so we can't say anything about their security. The game example I just gave argues that it's clearly possible to choose strong ciphers that fit into this multiple-encryption structure, and combine them in a way that's weak, when the keys are not independent. (But it's been five years or so since I read their paper, so I may be forgetting some of what they said.) ...
However in the case of a chosen-plaintext attack, Massey and Maurer's argument does not work. In fact the proof they give of their "Proposition" can easily be adapted to prove that a concatenated cipher C1*...*Cn is always at least as difficult to break by chosen-plaintext as *any* cipher in the concatenation.
Right. This falls out of the basic argument really nicely. If you want to use an algorithm to break E1(E2(X)) to break E1(X), it has to use a chosen-plaintext attack on E1.
My main question is how much weight should we give to this result in designing a crypto system by combining AES candidates?
Probably not too much, in terms of worrying about known-plaintext vs. chosen-plaintext attacks. Though honestly, I think designing your PES is like providing really effective padlocks for screen doors. (But you could say the same thing about AES with 256-bit keys.) ...
a. The keys need to be independent. (Otherwise, imagine if cipher #1 is DES encryption, and cipher #2 is DES decryption.)
I don't think it is quite that clear. It might well be easier to prove, say, that Twofish is not the inverse of MARS for the same key than it is to prove the same result for separately hashed keys. But again, the likelihood of two different ciphers being accidental inverses is even lower than the likelihood of guessing the key correctly (there are (2**n)! bijections on n-bit blocks). And NIST has just released SHA-2 which provides 256 bit hashes, so I suppose we might as well use it here.
See above. The important part of the Maurer and Massey proof, IMO, is that it shows that you do get at least the strength of the strongest component cipher against chosen-plaintext attacks. But that proof falls apart when you don't have independent keys, which means you can't really say anything about the strength of the composed cipher. And the game argument shows that it's possible to choose those ciphers with non-independent keys badly enough to make the composed cipher weaker than any of its components.
b. There order of the ciphers matters for the kind of security proof you can do. If you do Twofish, then Rijndael, you can prove that a known-plaintext attack on this system = a known plaintext attack on Twofish and a chosen-plaintext attack on Rijndael. (That is, the combined system can be no easier to break than the easier of a known-plaintext attack on Twofish or a chosen-plaintext attack on Rijndael.)
Is this the Massey and Maurer result or is there something specific about these two ciphers?
It's the Massey and Maurer result. ...
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.
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. ...
Arnold Reinhold --John Kelsey, Counterpane Internet Security, kelsey@counterpane.com PGP Fingerprint: 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE----- Version: PGPfreeware 6.5.1 Int. for non-commercial use <http://www.pgpinternational.com> Comment: foo iQCVAwUBOfSD3iZv+/Ry/LrBAQFBoAP+Jeq0bc9cA36WxnxOl+rz3O8bOYPkB0cG GLmCSm0gyxTPtfrDiqWW/fGFxOl0/E+Ec6IzG+WPrg7lwy5gjeOEHfzIkfB5dC0E rctkTSTum0lXGD3WKAOc4E+SKPaaU6pQRDZ4YcYkOZXGN9WVO88v7zZSGJvMCay9 ig11jvhdgGc= =Xa+c -----END PGP SIGNATURE-----