From: "John Kelsey" <kelsey@plnet.net>
Date: Mon, 2 Feb 1998 06:47:30 +0800
To: "cypherpunks" <cypherpunks@Algebra.COM>
Subject: Re: Chaining ciphers
Message-ID: <199802012242.QAA31781@email.plnet.net>
MIME-Version: 1.0
Content-Type: text/plain



-----BEGIN PGP SIGNED MESSAGE-----

[ To: Cypherpunks ## Date: 02/01/98 ##
  Subject: Re: Chaining ciphers ]

>Subject:      Re: Chaining ciphers
>From:         ghio@temp0201.myriad.ml.org (Matthew Ghio)
>Date:         1998/01/30

>One other possibility is to encrypt with plaintext block
>chaining, then superencrypt it PBC in reverse order,
>starting with the last block first. An attacker would thus
>have to decrypt the entire message before knowing whether
>the key was correct or not.

I've seen proposals along these lines before (I think there
was one by Ron Rivest).  If you have a hash function and any
symmetric cipher, you can do this.  BEAR and LION, the two
arbitrary-size block cipher constructions by Ross Anderson
and Eli Biham, have this property; you have to process every
bit of the message to check a key guess.  Using normal
chaining modes for this kind of thing, at least with 64-bit
block ciphers, usually exposes you to internal-collision
kinds of attacks.

>> One word of caution (which should be obvious, but can't
>> hurt to repeat it): if you chain ciphers (e.g. DES | IDEA |
>> 3DES | CAST | Blowfish), be sure to use separate keys for
>> each of them; otherwise breaking the last one will give the
>> key to the whole lot.

>Only if the cryptanalyst knows that the decryption of the
>last one was correct, which shouldn't be possible without
>also decrypting all the other layers.

Actually, this isn't necessarily true.  The problem is that
you can't guarantee that there won't be some interaction
between those encryption operations unless you can assume
independent keys.  The classic example is this:  Suppose the
first cipher is double-DES encryption with DES keys (K0,K1),
and the second and third encryptions are single-DES
decryptions with keys K1 and K0, respectively.  You now have

e_0(e_1(e_2(x)))

leaking all your plaintext directly.

The proof for why something like

E(X) = IDEA_{K_0}(3DES_{K_1}(X))

is at least as secure as 3DES is as follows:  Suppose those
keys are random and independent, and suppose you have a way
to break E(X).  Now, anytime you see a 3DES-encrypted block
of data, you can break it, as well, by simply choosing a
random IDEA key, encrypting it under that key, and then
applying your attack on E(X).  In other words, the attack on
E(X) implies the attack on 3DES(X), but only if the keys are
independent.  If there is some dependency between K_0 and
K_1 that's required for your attack on E(X), then you can't
generalize that out to an attack on 3DES, since you don't
know the 3DES key when you start attacking it.

To take this a little further, note that an attack on E(X)
also implies a chosen-plaintext attack on IDEA.  If I have
an attack that allows me to break E(X), then I can choose a
random 3DES key, pre-encrypt all my chosen plaintexts with
it, and then request the encryption of all those plaintexts
under the secret IDEA key.  The result is E(X), so I can now
apply my attack to E(X).

For more elaborate constructions, like

E3(X) = 3DES_{K_1}(IDEA_{K_2}(Blowfish_{K_3}(X))),

we can make the same kind of proof.  Suppose I can break
E3(X).  Now, I can mount a chosen-plaintext attack on IDEA.
I select a random encryption key and use it to encrypt all
my chosen plaintexts under with Blowfish, and then I request
their encryptions.  When I get the ciphertexts from that, I
select a random 3DES key and encrypt them again.  I then
apply my attack on E3(X) to break the system.  Thus, an
attack on E3(X) implies an attack on 3DES, IDEA, *and*
Blowfish.  But only if the keys are independent and random.

Note:  I read CP-LITE instead of the whole list.  Please CC
       me on replies.

- --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print =  5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBNNRSUiZv+/Ry/LrBAQGTgAP9EhO0wyPT0HKSXqZD61YPwId8E5C4GJK2
c/+27LBZy8WLhiD92NBc42Rzjbxbir8oWlPkSkZa565mYoaILM0CcP7S15ECyfBY
yV2yCOlJdoUo2ea70uIucowxpc2zx2G2KPKBLmGS5P5cwNsx8h3i7KDiRfcWSIGN
Omqf38rAy6E=
=+f39
-----END PGP SIGNATURE-----