CDR: Re: Paranoid Encryption Standard (was Re: Rijndael & Hitachi)

[Arnold G. Reinhold]

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