From dawagner@flagstaff.princeton.edu Mon Oct 10 17:31:18 EDT 1994 Article: 29 of sci.crypt.research Path: princeton!udel!MathWorks.Com!europa.eng.gtefsd.com!howland.reston.ans.net!wupost!waikato!auckland.ac.nz!news From: dawagner@flagstaff.princeton.edu (David A. Wagner) Newsgroups: sci.crypt.research Subject: Combining ciphers Date: 10 Oct 1994 13:42:02 GMT Organization: Princeton University Lines: 138 Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator) Approved: crypt-submission@cs.aukuni.ac.nz Message-ID: <37bgba$s53@ccu2.auckland.ac.nz> Reply-To: dawagner@flagstaff.princeton.edu (David A. Wagner) NNTP-Posting-Host: cs13.cs.aukuni.ac.nz X-Newsreader: NN version 6.5.0 #7 (NOV) Consider the following situation: Alice and Bob want to communicate securely. Alice believes that the cipher A is strong, but doesn't trust B. Bob would prefer to encrypt using the algorithm B, and suspects that A is weak. How can they agree on some cryptosystem which they will both trust? What is needed is some general way to combine ciphers A and B into a new cipher C which is at least as strong as both A and B. I'm hoping someone will point me to a nice way to solve this, or comment on the ideas below... One natural idea is to try composing A and B; thus for two independent keys K_A, K_B, we let Encrypt_C(K_A, K_B, P) = Encrypt_B(K_B, Encrypt_A(K_A, P)). [Clearly independent subkeys are necessary in this problem, if we plan to make no restrictions on A and B: in a degenerate case, A could be "encrypting with DES" and B could be "decrypting with DES."] The problem with composition is that if A is weak, then the whole combination can be insecure. As a thought experiment, suppose B is very resistant to known plaintext attacks, but succumbs easily to a chosen plaintext attack. Let S be a set of plaintexts which are useful in a chosen plaintext attack. If A transforms most inputs (or the most common inputs, like maybe those with the 8-th bit clear) into elements of S, then C will fall easily to a known plaintext attack. Thus, if A is untrusted, the composed cipher C could be very weak. [It seems like I remember a discussion about this topic from a year or two ago on sci.crypt: I think someone produced a reference that mentioned this problem with composition. I hope I'm not mentioning a result without giving due attribution; if anyone knows of related papers, I'd love to hear from them!] This may seem like an overly contrived example -- but there might be a more natural example out there, anyways. [Tell me if you find one!] Also, remember, Bob isn't willing to assume that Alice's cipher A is any good. [It's almost an adversarial situation.] If there were some method for combining A and B into a new cipher C that is provably as secure as both A and B, that'd be quite nice... John Krueger (krueger@cs.hope.edu) has kindly sent me some interesting comments on this. He mentioned that the composition must be at least as secure as the first cipher: if there were some easy way to break C, then you could also break A by picking a random key K_B and encrypting the output of A with cipher B. He also pointed out a way to combine A and B into a new stronger cipher. Prof. Lipton (from the CS dept here) also independently came up with the same idea, so maybe it's fairly natural... Anyhow, to encrypt P under C, we first generate a block of random bits R, and then let Encrypt_C(K_A, K_B, P) = Encrypt_A(K_A, R) || Encrypt_B(K_B, R+P) where || denotes concatenation and + denotes bitwise xor. This can also be viewed as creating a random one-time pad, encrypting the plaintext with it to get X, sending the pad encrypted with cipher A, and then sending X encrypted with cipher B. It's possible to prove that this technique gives you a new cipher C which is at least as strong as both A and B: suppose there is some easy way to break C [i.e. some algorithm which outputs X given Y = Encrypt_C(K_A, K_B, X) and possibly access to chosen plaintexts]. To break the cipher A [i.e. produce P given C = Encrypt_A(K_A, P) and possibly some chosen plaintexts], generate a random key K_B, compute a random block R, set Y = C || Encrypt_B(K_B, R), and use the method for breaking C to obtain X. [If that method needed chosen plaintexts, we can simulate them easily using chosen plaintexts from A.] Finally, since X = P + R, P is easily found. [If the algorithm for breaking C only works for a fraction of the inputs, then we can randomize P by xoring in another random block, and mutter something about uniformity -- the proof will still work.] This proof shows that C is as secure as A (and of course by symmetry C is just as secure as B, too). The disadvantage is that this method expands the length of the plaintext by a factor of two. This would be unacceptable for an encrypting filesystem, but is probably not too much to pay for provable security in (for example) email applications. In addition to just proving a lower bound on the security of the cipher C, I think I can also exhibit an upper bound. It seems like a meet-in-the-middle attack would work if you have known plaintext: suppose you're given (P, C_A, C_B) with C_A = Encrypt_A(K_A, R) C_B = Encrypt_B(K_B, R+P) for some R. Store Decrypt_A(x, C_A) for all values of x, and store Decrypt_B(y, C_B)+P for all values of y. Sort or whatever to find collisions; when you find one, you'll have z = Decrypt_A(x, C_A) = Decrypt_B(y, C_B) + P so that with high probability R=z, K_A=x, K_B=y. If A and B use n bit keys, this attack takes O(2^n) space and O(2^n) time. Anyone see any better attacks? Thus this scheme seems like analogous to double encryption, in some sense. Is it possible to make it as secure as (say) triple encryption? There's also the question of how to use this method with messages longer than the block length -- sure, you can use chaining, but is it better to apply the chaining before or after you apply this technique? Or doesn't it matter? Also, there's a related problem of how to combine two hash functions into something which is at least as strong as the stronger of the two. This problem seems harder... Comments, anyone? ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu