Paranoid Encryption Standard (was Re: Rijndael & Hitachi)

[Arnold G. Reinhold]

At 8:13 PM -0400 10/11/2000, John Kelsey wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>At 01:44 PM 10/10/00 -0400, Arnold G. Reinhold wrote:
>
>...
>>I was thinking it might be useful to define a "Paranoid
>>Encryption Standard (PES)" that is a concatenation of all
>>five AES finalists, applied in alphabetical order, all with
>>the same key (128-bit or 256-bit).  If in fact RC6 is the
>>only finalist still subject to licensing by its developer,
>>it could be replaced by DEAL (alphabetized under "D"). Since
>>DEAL is based on DES, it brings the decades of testing and
>>analysis DES has received to the party.
>
>This basic idea is discussed in Massey and Maurer's ``The
>Importance of Being First'' paper.  There are a couple
>issues:

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.

As I understand it, their argument goes like this: Let the 
concatenated cipher C1*C2 applied to plaintext P be C2(C1(P)). If C2 
is subject to attack when the plaintext it gets has certain 
statistical properties, then it is possible for C1's ciphertext to 
have those properties and the concatenated cipher to be less 
resistant to statistical attack than either component.

Massey and Maurer give a very simple example to show this can occur. 
Here is a bit more realistic example: Suppose C1 simply permutes the 
input bits and that in doing so it takes the high-order bit of each 
plaintext byte and moves it to the first two bytes of the cipher 
text. Suppose further plaintext blocks that have the first two bytes 
zeroed are weak for C2. Then if C1 is fed ordinary printable ascii 
text with no parity, the first two bytes of C1-ciphertext will be 
zero, exposing the weakness of C2.  On the other hand, if C2 were 
used alone on the same ascii plaintext it would never see zeros as 
input bytes and thus would not be subject to attack.

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.

Here is an outline of the proof. Note, as they do, that the worst 
case is when you can easily determine the key to every cipher except 
one.  In their case it is the first cipher, in ours say it is Ci, 
1<=i<=n.  Then any set of chosen plaintext, ciphertext pairs (PTj, 
CTj) that results in a break of the concatenated cipher C1*...*Cn 
can be converted in to a set of chosen plaintext, ciphertext pairs 
(PT'j,  CT'j) that results in a break of Ci as follows (I'll use CCk 
to denote the inverse cipher of Ck):

PT'j = (C1*...*Ci-1)(PTj)

CT'j = (CCi+1*...*CCn)(CTj)

One might ask why this proof works in the chosen-plaintext attack but 
not the statistical attack. The reason is that in the later,  while 
you can still compute each PT'j, there is no reason to expect that 
they will have the same statistical properties as the original PTj. 
However PT'1 is always equal to PT1, so the proof does work for the 
first cipher in the statistical attack case. That is where "the 
importance of being first" comes from.

My main question is how much weight should we give to this result in 
designing a crypto system by combining AES candidates? Remember that 
the AES candidates were designed to resist chosen-plaintext attack. 
Resistance to chosen-plaintext attack is a far more stringent demand 
on a cipher than resistance to statistical attack. And I have just 
shown that a concatenated cipher is at least as strong as any of its 
components against chosen-plaintext attack. So why should we even 
consider Massey and Maurer's result? The one argument I can think of 
goes like this:  Suppose we are wrong and all the component ciphers 
are subject to chosen-plaintext attack and, even worse, so is the 
concatenated cipher. The component ciphers might still be resistant 
to statistical attack and often this is the best attackers can do, so 
we would like the extra insurance.

But in the real world of AES candidates I claim even that argument 
should be discarded.  Massey and Maurer worry about the possibility 
that the output of one cipher may have statistical properties that 
cause weakness when that output is fed into the subsequent ciphers. 
The AES candidates were designed to have outputs that appear 
uniformly random and have all undergone extensive statistical testing 
http://csrc.nist.gov/encryption/aes/round1/r1-rand.pdf. The have also 
been studied for weak inputs. Thus the first cipher in the 
concatenation can be expected to destroy patterns in the plaintext, 
not create them. While not a mathematical proof, the results of the 
AES candidate analysis and testing to date make it overwhelmingly 
more likely that the concatenation of AES-candidate ciphers will in 
fact be more resistant to statistical attack than any of the 
individual ciphers.


>
>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.


>
>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?

>
>A smarter way to do this is to do OFB-mode or counter-mode
>with all N ciphers.  That way, you can prove that breaking
>the resulting cipher is equivalent to breaking OFB mode
>encryption under all N of the ciphers.

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. I have 
spent a lot of effort in my CipherSaber project teaching people how 
to do that, and the risk of implementors getting it wrong is high. 
I've even seen commercial products that claim to use RC4 but don't do 
IVs. Note that IV reuse is far more catastrophic in a stream cipher 
than it would be in a block cipher used in a feedback mode.

Also OFB means that ciphertext is always bigger than plaintext (if 
you include the IV). That prevents encryption in place, for example. 
I'd rather have a block cipher if at all possible.

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")

The character string constants are 8-bit ascii with zero parity bit.

The order of each cipher is determined alphabetically, except that I 
obviously could have chosen to put Rijndael under "R"  instead of 
"A."  By putting it first we can take advantage of Massey and 
Maurer's result and state the PES is at least as strong against 
statistical attack as AES.  The second cipher, DEAL, is based on DES, 
which has received the most public scrutiny of any cipher. I am not 
aware of any  statistical attack on DES inputs or any statistical 
weaknesses in DES output that might compromise MARS.  And, as we have 
shown above, PES is at least as resistant to chosen plaintext attack 
as any of its components.

PES is intended to address concerns that AES might have a design flaw 
or deliberate, hidden weakness. Confidence that neither exist can 
only come from additional years of testing and analysis.  PES, 
because it is at least as strong as AES and incorporates the 
strengths of  four other AES design teams and the decades of work on 
DES, might be a better choice for very high value messages, where 
encryption time is not an issue.

Some other comments I have received urged the use of salt.  Salt is 
very important is overall system design, but it is not part of the 
cipher per se.  As I mentioned in my earlier post, RC6 is not being 
used because it still requires licensing. No criticism of RC6 or its 
owner's decision to retain commercial licensing rights is intended.

FWIW

Arnold Reinhold