267 lines
10 KiB
Plaintext
267 lines
10 KiB
Plaintext
Ritter Software Engineering
|
|
2609 Choctaw Trail
|
|
Austin, Texas 78745
|
|
(512) 892-0494, ritter@cactus.org
|
|
|
|
|
|
|
|
2x Isolated Double-DES: Another Weak Two-Level DES Structure
|
|
|
|
Terry Ritter
|
|
February 16, 1994
|
|
|
|
|
|
Introduction
|
|
|
|
The time has come to replace DES, the US Data Encryption Standard,
|
|
but there is no clear alternative. While there are many ciphers
|
|
which are demonstrably faster and also arguably stronger than DES,
|
|
the fact that cipher strength cannot be _tested_ but must instead
|
|
be_argued_ makes many users nervous. The US government offers some
|
|
alternative ciphers, but those are secret designs whose strength
|
|
_cannot_ be argued, again making users nervous.
|
|
|
|
The current leading candidate for a replacement to DES is "triple-
|
|
DES," a three-level construct using DES at each level. This is a
|
|
comforting design, because users are already convinced that DES
|
|
can be relied upon for a certain level of strength. Unfortunately,
|
|
a software implementation of triple-DES takes three times the
|
|
processing of normal DES. While this is a mere detail on systems
|
|
which process the occasional enciphered email message, operational
|
|
speed is fundamental to widespread industrial use. Ciphering speed
|
|
is essential in LAN servers and other fully-enciphered communications
|
|
nodes. Speed is also important when ciphering is an integral part
|
|
of laptop software which communicates to a central facility. Fast
|
|
software ciphering is important.
|
|
|
|
Because the ciphering speed for triple-DES is not acceptable, no
|
|
three-or-more-level construct could possibly be satisfactory in
|
|
this respect. This limits our design alternatives to one-or two-
|
|
level constructs based on DES.
|
|
|
|
The goal, then, is to find--if possible--a construct which is based
|
|
on DES, has strength substantially beyond normal DES, but requires
|
|
less processing than triple-DES. This time we start from the base
|
|
of double-DES, and directly confront the known weakness of that
|
|
approach:
|
|
|
|
|
|
Double-DES
|
|
|
|
The classical double-DES construct is something like this:
|
|
|
|
A
|
|
v
|
|
k1 -> DES1
|
|
v
|
|
B
|
|
v
|
|
C
|
|
v
|
|
k2 -> DES2
|
|
v
|
|
D
|
|
|
|
where each single capital letter represents an 8-byte DES block.
|
|
Double-DES is normally not used, because of the meet-in-the-middle
|
|
attack:
|
|
|
|
|
|
Meet-In-The-Middle Attack on Double DES
|
|
|
|
Assume we have known-plaintext A for ciphertext D: Encipher A
|
|
under every possible key k1, and decipher D under every possible
|
|
key k2. (The cost for this is only two full DES key searches.)
|
|
Then check for matches between B and C. If there are multiple
|
|
matches, the correct k1 and k2 will be there somewhere, and we
|
|
can isolate the correct pair with one or two more known-plaintext
|
|
blocks (this is a loose interpretation of [2]).
|
|
|
|
This works for the normal double-DES construction because it is
|
|
possible to check for matches between B and C; the weakness seems
|
|
to be the ability to check for a match. Assuming that we have
|
|
properly identified the principal weakness of double-DES, let's
|
|
fix it: We can isolate the two values, making a match check
|
|
impossible, so that not even one bit can be checked.
|
|
|
|
|
|
Isolated Double-DES
|
|
|
|
Consider a two-level DES construct like this:
|
|
|
|
A
|
|
v
|
|
k1 -> DES1
|
|
v
|
|
B
|
|
v
|
|
km -> XOR
|
|
v
|
|
C
|
|
v
|
|
k2 -> DES2
|
|
v
|
|
D
|
|
|
|
where k1 and k2 are 56-bit keys, but km is a 64-bit key.
|
|
Technically, this construct could be considered to be either
|
|
double-DES with an intermediate ("isolating") XOR operation, or
|
|
triple-DES with XOR replacing the middle DES operation. But since
|
|
the processing cost for this system is similar to double-DES, it
|
|
is reasonable to call it a form of double-DES.
|
|
|
|
While it is true that we now have three keys for a two-level DES
|
|
structure, this is no worse than triple-DES with separate keys.
|
|
But is it stronger than double-DES?
|
|
|
|
|
|
Isolated Double-DES Meet-In-The-Middle Attack
|
|
|
|
Again, encipher A under every possible key k1, and decipher D under
|
|
every possible key k2 and check for matches between B and C.
|
|
|
|
But in the isolated construction, every possible pair of values
|
|
(B,C) has some key km which would make that pair match. Thus, the
|
|
weakness of match identification in the original construction is
|
|
not possible in the alternate construction.
|
|
|
|
The keyspace seems to be 56 + 64 = 120 bits, which would probably
|
|
be satisfactory for another couple of decades, or until an open
|
|
science of cryptographic machine design has matured. It still
|
|
has a small block size, however.
|
|
|
|
|
|
Larger Blocks
|
|
|
|
DES uses a relatively-small 8-byte block, so if DES were used
|
|
in Electronic Code Book (ECB) mode and large amounts of plaintext
|
|
were known, a dictionary attack would be possible. Fortunately, DES
|
|
is normally used in Cipher Block Chain (CBC) mode, making dictionary
|
|
attacks difficult. But a dictionary attack on ECB mode could be
|
|
viewed as a "certificational attack" which is "indicative of
|
|
weakness" in the cipher itself. [1:466]
|
|
|
|
If we make the modest assumption that ordinary text has an
|
|
information content of under 40 percent of the binary size, then
|
|
a 64-bit block of text generally contains less than 26 bits of
|
|
uniqueness. Worse, short words occur far more often than an even
|
|
distribution would indicate. Although it would certainly be ill-
|
|
advised to send 2^26 blocks (2^29 bytes) of data under a single set
|
|
of keys, it is interesting to note the relatively small size of this
|
|
figure when compared to other cryptographic quantities.
|
|
|
|
For this reason, it seems appropriate that any new standard specify
|
|
an expanded block width. Here is a double-width approach, 2x2 DES
|
|
described in an earlier article:
|
|
|
|
A B
|
|
v v
|
|
k1 -> DES1 k2 -> DES2
|
|
v v
|
|
C D
|
|
Exchange Right 4 Bytes
|
|
E F
|
|
v v
|
|
k3 -> DES3 k4 -> DES4
|
|
v v
|
|
G H
|
|
|
|
Note that the 64-bit quantity G (for example) is a complex nonlinear
|
|
function of A, B, k1, k2, and k3; a total of 296 bits. Nevertheless
|
|
the system is still solvable with meet-in-the-middle:
|
|
|
|
|
|
2x2 DES Meet-In-The-Middle Attack
|
|
|
|
With one known-plaintext block, we can search one top key and one
|
|
bottom key (say, k1 and k3) and find pairs (E,C) which match at the
|
|
appropriate 32 bit-positions. Then we can identify the correct
|
|
pair with additional known-plaintext blocks, resolving the keys at
|
|
32-bits per known-plaintext pair.
|
|
|
|
We can guarantee that the two keys will be found by searching all
|
|
possible k1 and k3. This is only twice the normal DES keyspace,
|
|
but may well require a huge amount of storage to identify all the
|
|
values and associated keys (say, E and k3) which match a particular
|
|
result (say, C). We do not want to run through every k3 every
|
|
time we change k1.
|
|
|
|
|
|
2x2 DES Differential Attack
|
|
|
|
Eli Biham [1] points out that a differential attack can eliminate
|
|
the need to store the result from every possible key. In this case
|
|
we need two different large blocks of known-plaintext with plaintext
|
|
or ciphertext half the same (say, A:B -> G:H and A:X -> Y:Z). With
|
|
A the same in both large blocks, we know that the left-half of E
|
|
must also be the same. Then, since we have two different blocks, we
|
|
can step through all possible values for k3, deciphering G into E
|
|
and Y into E' each time, looking for any results with the left-half
|
|
the same. This should occur about every 2^32 trials, producing 2^24
|
|
trials which match, which should be resolved in only one or two more
|
|
set of known-plaintext blocks. No huge storage is needed.
|
|
|
|
|
|
2x Isolated Double-DES
|
|
|
|
Consider a pair of isolated double-DES structures, combined as
|
|
described for 2x2 DES:
|
|
|
|
A B
|
|
v v
|
|
k1 -> DES1 k2 -> DES2
|
|
v v
|
|
km -> XOR1 kn -> XOR2
|
|
v v
|
|
Exchange Right 4 Bytes
|
|
v v
|
|
k3 -> DES3 k4 -> DES4
|
|
v v
|
|
C D
|
|
|
|
The result is a double-width structure, in which every ciphertext
|
|
bit in C depends on each and every bit in A, B, k1, k2, and k3, as
|
|
well as half the bits in km and kn. Ciphering occurs at the rate
|
|
of double-DES. While it is certainly true that six keys are needed,
|
|
keys need be transmitted far less often than data, and by having
|
|
separate keys we avoid attacks which depend upon having the same
|
|
key at multiple parts of the operation. If we say that enciphering
|
|
occurs "from the top down," (XOR before exchange) then we would say
|
|
that deciphering occurs "from the bottom up" (exchange before XOR).
|
|
|
|
|
|
2x Isolated Double-DES Meet-In-The-Middle Attack
|
|
|
|
The double-DES meet-in-the-middle attack depended upon having a
|
|
structure in which the enciphered plaintext was identical to the
|
|
deciphered ciphertext. This allowed both keys to be manipulated
|
|
and the resulting data space searched for matches.
|
|
|
|
In isolated double-DES any enciphered plaintext value can be
|
|
related to any deciphered ciphertext value by varying the middle
|
|
or "isolating" key. Thus, meet-in-the-middle seems not very useful.
|
|
|
|
|
|
2x Isolated Double-DES Differential Attack
|
|
|
|
The 2x2 differential attack depended not upon identical top and
|
|
bottom values, but upon producing an identical value (in particular
|
|
known bit positions) from a bottom deciphering (for example). This
|
|
situation is not affected by the XOR and so the differential attack
|
|
will still work.
|
|
|
|
|
|
Conclusion
|
|
|
|
2x Isolated double-DES falls to a differential attack.
|
|
|
|
|
|
References
|
|
|
|
[1] Biham, E. Mon, 7 Feb 1994 16:59:28 GMT. Comments on Nx2 DES.
|
|
<CKv5v5.EnF@chinet.chinet.com>
|
|
|
|
[2] Merkle, R. and M. Hellman. 1981. On the Security of Multiple
|
|
Encryption. Communications of the ACM. 24(7): 465-467.
|
|
|