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