[2126] in cryptography@c2.net mail archive
Interesting dual-cipher CFB mode
daemon@ATHENA.MIT.EDU (Colin Plumb)
Sun Feb 8 22:19:58 1998
Date: Sun, 8 Feb 1998 19:59:50 -0700 (MST)
From: Colin Plumb <colin@nyx.net>
To: cryptography@c2.net
There was an idea I had a while ago for letting two people communicate
who disagree as to a suitably secure conventional cipher in such a way
to satisfy them both. It's never been used, but I thought I'd toss it
out in case it of interest to anyone.
It's based on a paper I read a while ago, by Massey I think, about the
strength of double-encryption. (Encryption using two ciphers with
independent keys. The independence of the keys is crucial, as without
it the double-encryption can be weaker than either input cipher.) It
proves that such encryption is only provably as strong as the first
layer. So if you want something provavly as strong as either of two
ciphers, you have to combine them in a way that is commutative, so each
one comes first.
One obvious way to do this is to use two stream ciphers, since XOR is
commutative. Or a block cipher in OFB or counter mode.
However, is some cases a self-synchronous stream cipher such as CFB mode
is more useful. For example, there's a neat trick that can be used
to get almost the efficiency of CFB-64 while having almost the
error-tolerance of CFB-1 or CFB-8.
A "resync point" is a point between two transmitted bits where
you use the previous 64 bits to generate the next portion of the
key stream. In CFB-n, these points arise every n bits.
For additional sync recovery, define a flag sequence. Since the
stream is effectively random, the pattern is irrelevant except
for its length, so I'll assume it's k consecutive zeros. Operate
in CFB-64 mode, except that every time the flag sequence occurs,
force a resync point.
A shorter flag sequence results in more resyncing, with faster
sync recovery and more encryption. The ultimate, a zero-length
flag sequence, results in CFB-1 (or CFB-b if the underlying transport
provides b-bit sync, e.g. b=8 for RS-232).
The important thing is that, since the ciphertext stream can be
assumed to be totally random, sync is guaranteed to be eventually
reestablished.
I kind of liked this because it avoids transmitting any framing
information whatsoever in the clear. An eavesdropper can't even
tell what the flag sequence is, unless timing reveals it.
Anyway, back to the story. It's possible to combine two ciphers
in CFB mode, using C[i] = P[i] XOR E1(k1,C[i-1]) XOR E2(k2,C[i-1).
Basically, you're defining an encryption E3(x) = E1(x) XOR E2(x).
Now, what I observed and proposed using was that there is no need for
the sync points of the two ciphers to be in the same places. You
can combine 64-bit blocks, 96-bit blocks (e.g. 3-way), 128-bit blocks
or 160-bit blocks (MDC/SHA), and have a wierd sort of dual-cipher
unsynchronized CFB mode.
To give an example, suppose you have a 3-word and a 4-word block cipher,
whose encryption operations I'll call E3() and E4().
then stating from a 4-word IV C[-4..-1], the ciphertext is formed
from the plaintext as C[i] = P[i] ^ K[i], and the keystream K[i]
is formed as K[i] = K3[i] ^ K4[i], where K3[i] and K4[i] are the key
streams produced by the individual ciphers. Finally, K3[i] is
generated as:
K3[0..2] = E3(k3,C[-3..-1]
K3[3..5] = E3(k3,C[0..2]
K3[6..8] = E3(k3,C[3..5]
K3[9..11] = E3(k3,C[6..8]
K4[0..3] = E4(k4,C[-4..-1])
K4[4..7] = E4(k4,C[0..3])
K4[8..11] = E4(k4,C[4..7])
This is provably as strong as either E3 or E4 (again, assuming that k3 and
k4 are independently chosen keys), and kind of interesting.
For more fun, you can use the same flag-sequence-resync trick, but have
different flag sequences for the two ciphers. I don't know if that is
worth anything, though.
Anyway, I just thought I'd throw it out in case it is helpful in some
wierd way.
--
-Colin
