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