From the time DES was introduced, the 56-bit length of its key was a subject of concern and controversy.
A common way to increase the security of DES is to apply DES to a block three times. The reason that it isn't simply applied twice is because of the existence of an attack which reduces the security of double-DES almost to the level of single-DES. This attack, called the meet-in-the-middle attack, requires a very large quantity of memory. The basic principle of this attack is that if one has two or more blocks of ciphertext with known plaintext, instead of having to do a brute-force search over all possible pairs of DES keys, one can simply do a brute-force search over all possible values of the first key, as applied to the plaintext, and over all possible values of the second key, as used to decrypt the ciphertext, and then find which result of the first search is also a result of the second search.
While a random-access memory large enough to hold 2^56 data items, each at least 128 bits in length, seems preposterous, it is not beyond imagination to put that much information on a medium such as magnetic tape; and, if the values were sorted, they would be useful in that form. Techniques for efficiently sorting files too large to read in to a random-access storage device were intensively studied in the early years of computing, and so they are available.
Usually, Triple-DES is done by encrypting with one key, decrypting with another, and then encrypting again with either the first key or a third one. This way, if all three phases are done with the same key, interoperability with regular single DES is possible. This is called EDE mode, for Encrypt-Decrypt-Encrypt.
If one is going to use DES three times, one can be more elaborate.
If one is going to use Triple-DES, one can also increase the effective block size of DES through something called an Outerbridge construction. The image below illustrates a generalization of that construction to quadruple, rather than merely double, the block size, and to increase the effective key size as well. The 64-bit blocks are considered to be divided into four 16-bit parts, which are distributed between DES operations.
And here is the same diagram in ASCII graphics format:
------------ ------------ ------------ ------------ | K1 | | K2 | | K3 | | K4 | ------------ ------------ ------------ ------------ | | | | | | | | | | | | | | | | | | | | | | | \ | / | | | | | | | | | | | | \ ----- |/ | \ | / | | | \ \ \ | | \ \| | --- -|- / | | \ \ ----------------------------------- \/ | / | | \ ---------------------- / |\ | \ /\ | / | | -------- | | \ \ | ----|---- \ / / | | \/ | \/ \/ | \/ \/ \/ | | /\ | /\ /\ | /\ /\ /\ | | -------- | | / / | ----|---- / \ \ | | / ---------------------- \ |/ | / \/ | \ | | / / ----------------------------------- /\ | \ | | / / / | | / /| | --- -|- \ | | | | | | | / ----- |\ | / | \ | | | | | | | | | / | \ | | | | | | | | | | | | | | | | | | | | | | ------------ ------------ ------------ ------------ | K5 | | K5 | | K5 | | K5 | ------------ ------------ ------------ ------------ | | | | | | | | | | | | | | | | | | | | | | | \ | / | | | | | | | | | | | | \ ----- |/ | \ | / | | | \ \ \ | | \ \| | --- -|- / | | \ \ ----------------------------------- \/ | / | | \ ---------------------- / |\ | \ /\ | / | | -------- | | \ \ | ----|---- \ / / | | \/ | \/ \/ | \/ \/ \/ | | /\ | /\ /\ | /\ /\ /\ | | -------- | | / / | ----|---- / \ \ | | / ---------------------- \ |/ | / \/ | \ | | / / ----------------------------------- /\ | \ | | / / / | | / /| | --- -|- \ | | | | | | | / ----- |\ | / | \ | | | | | | | | | / | \ | | | | | | | | | | | | | | | | | | | | | | ------------ ------------ ------------ ------------ | K1 | | K2 | | K3 | | K4 | ------------ ------------ ------------ ------------
If only the keys for the four middle operations were different, a meet-in-the-middle attack could reduce the security of this to that of ordinary Triple-DES, but varying the keys on the outside genuinely lengthens the key. (However, varying them on the inside may be a good idea too, as there may be other types of attack possible.)
Another suggestion for modifying Triple-DES to encipher a large block of text was made by Carl Ellison. What was suggested was the following: in addition to enciphering an input text by means of ECB mode three times, twice, between each pair of DES encryptions, the bytes of the entire message would be transposed. The transposition would not depend on any secret key, but instead the number of times each possible byte value from 0 to 255 occured in the text being transposed (which, of course, is not changed by transposition) would provide the "key" for the transposition.
But a chosen-plaintext attack on this scheme was found by Paul Crowley.
The attack works like this: encipher a message consisting of the same block repeated over and over.
After the first DES encryption, the result will also consist of a single block repeated over and over. So, after the first unkeyed transposition, the result will be a message consisting of at most eight different byte values in scrambled order.
If the message is long enough, it will be very likely that the result of the first unkeyed transposition will include two identical blocks, while this would still be very unlikely in any other case. This will result in two identical blocks being found in the output of the second DES encryption.
Now, it becomes possible, using the actual ciphertext produced by encrypting the chosen plaintext, to perform a brute-force search on the key of the third DES encryption stage only. After decrypting the ciphertext by a trial key, one can then reverse the second unkeyed transposition stage. This obtains a possible intermediate text which will, or will not, include a repeated block in it.
By using more than one chosen plaintext of repeated identical blocks, one can check if such a possible key is correct.
Then, a brute-force search on the key for the first DES stage is possible, because different keys would, by producing different inputs to the first unkeyed transposition stage, result in repeated blocks at different locations in the message. Finally, with both the first and third DES keys known, the inputs and outputs to the second DES stage are known, and so that key can be searched for independently.
Clearly, it is easy to frustrate this specific attack. The second DES stage could use a chaining mode of encryption, which would completely conceal any repeated blocks which it recieved as input.
As well, if a system using such a cipher were vulnerable to a chosen-plaintext attack, it could be constructed so as to use a separate session key for each message, with only the random session key being enciphered by a permanent key that could be used to read other messages.
If the transposition stages used a large secret key, in addition to being varied by the byte frequencies, then the search for the key for the third DES stage would become much more difficult, although it is possible that transposed bytes of a message with repeated blocks would still be distinguishable, particularly if a sufficiently large number of chosen plaintexts is used.
However, this result is still relevant, because it illustrates how easily a measure which one might think would make triple-DES more secure, by mixing the bytes of a message together in an unknown way, would actually reduce security by allowing the keys of the three DES layers to be searched for independently of one another.
Also, another way in which to get more mileage out of a block cipher would be to use it as the heart of a sort of nonlinear shift-register. Instead of using a shift register whose cells contain bits, however, the cells of the shift register would contain entire 64-bit (or larger) blocks.
An example of what such a mode might be like is shown in the diagram below:
Plaintext
|
-------
| DES |
-------
|
XOR<---------ADD<----ADD<---
| | | |
------- | | |
| DES | | | |
------- -------------------
| | | | | | | | | | |
|-------->| | | | | | | | | |
| | | | | | | | | | |
------- -------------------
| DES |
-------
|
Ciphertext
Three layers of DES are shown; the first and the last are in ECB mode, and serve to keep the contents of the shift register hidden.
The middle layer of DES is the one operating in an unusual mode. Its output is saved in a shift register. The output blocks produced 2, 4, and 7 blocks previously are added together (with normal arithmetic addition, including carries, so that the shift register actually contains 64-bit quantities, instead of merely being effectively 64 single-bit wide shift registers in parallel), and the result is XORed with the input to the middle DES operation. This is essentially a variation on cipher feedback (CFB) mode.
A mode like this:
Plaintext
| |
--->XOR -------->XOR
| | |
----------- | -----------
| DES 1 | | | DES 1 |
----------- | -----------
| | |
--->XOR |---| |-------->XOR
| | D | | |
| | E | | |
|-----| S |---- |-----
| | | |
| | 2 | |
| |---| |
Ciphertext
based on a different mode devised by Matt Blaze of AT&T, illustrates how additional security may be achieved by using DES twice for each block encrypted. (Unlike Matt Blaze, though, I got things at least slightly wrong: with 2^32 known plaintexts, which may be hard to obtain under many circumstances, a birthday attack can provide the necessary information for permitting a meet-in-the-middle attack on the mode shown here.)
Just encrypting each block twice in a row is usually not done; instead, if that type of mode is desired, encryption is performed three times in a row.
This is because, with a stretch of both plaintext and ciphertext known, it is possible to try each possible key on the plaintext and ciphertext separately, and then look for matches. This approach, called the meet-in-the-middle attack, does require a large amount of memory. However, even if that attack is more theoretical than real, the fact that one theoretical weakness exists indicates the possibility of other, more exploitable, weaknesses that may also exist even if they are not known at present.
Ron Rivest, one of the inventors of the RSA public-key algorithm, noted that because of the desirable properties of DES, it is possible to obtain a genuine increase in its key size simply by XORing the input to DES, and the output from DES, each by an additional 64 bits of key material. This form of enhanced DES is called DESX.
Other enciphering modes that provide a genuine improvement in the security of DES are possible. For example, here is a single-DES mode with variable whitening:
Plaintext
| | |
---SS1-->XOR ---SS1-->XOR ---SS1-->XOR
| | | | | |
| --------------- | --------------- | ---------------
|->| | | | | | | | | |->| | | | | | | | | |->| | | | | | | | |
| --------------- | --------------- | ---------------
| | --| | --| |
|---SS2-->XOR | |---SS2-->XOR | |---SS2-->XOR
| | | | | | | |
---------->XOR --------------->XOR --------------->XOR
| | | | | | | | | |
| |---------->XOR | |---------->XOR | |-----
| --------- | | | --------- | | | ---------
| | DES | | | | | DES | | | | | DES |
| --------- | | | --------- | | | ---------
| --------------------- | --------------------- | --------------
| | | | | | | | | | |
--- |----------------- |----------------- |-----
| | | | | |
|---SS3-->XOR |---SS3-->XOR |---SS3-->XOR
| | | | | |
| --------------- | --------------- | ---------------
|->| | | | | | | | | |->| | | | | | | | | |->| | | | | | | | |
| --------------- | --------------- | ---------------
| | | | | |
|---SS4-->XOR |---SS4-->XOR |---SS4-->XOR
| | |
Ciphertext
The DES layer in the middle uses CBC mode, so as to provide an additional source of random variation.
Before and after DES encryption, a 64-bit value is used to choose one of four whitening quantities to XOR with the message, four times, and is used twice to choose one of eight invertible substitutions for each byte of the block. Thus, this consumes 4+24+4+4+24+4 bits. Since each side is "guarded" by only a 32 bit unknown quantity, the XOR of the input to DES for the previous block and the output from DES for the block before is used.
This 64 bit quantity could also be the output of another DES encryption, perhaps one operating in OFB or counter mode, or the DES encryption of the previous ciphertext block as in CFB.
But this kind of mode has the problem, specifically because it uses a value that isn't openly visible in the ciphertext, that a single garble of the ciphertext will render the rest of the message unintelligible. This is not normally a problem for encrypting discrete messages, but it means the mode is not applicable to communications links.
Similar concepts are explored in the section on the Large-Key Brainstorm.
Another way to make double-DES encryption genuinely useful is suggested by constructions that will be discussed in the next section when looking at Dual Counter Mode.
Use one DES encryption as the heart of a nonlinear shift register, somewhat along the lines of Panama, for example, and XOR its output to the plaintext and ciphertext going through the second DES encryption.
The diagram above illustrates a mode using this principle. The shift register's feedback loop is independent of the text being encrypted, but the previous ciphertext block is used to modify the outputs from the shift register applied to the incoming plaintext and outgoing ciphertext. Thus, it has error recovery properties similar to those of CBC mode, and it combines dependence on a complicated counter (including another DES encryption) with dependence on the previous ciphertext block.
When error recovery is not a concern, one can allow the previous ciphertext block to affect the shift register contents, for even more complexity, as shown below:
On the other hand, one can use a simpler stream cipher mode for the second block cipher as well, such as:
---------
| |
| ---------
Counter ---> XOR | DES 2 |
| ---------
| |
---------|
Plaintext |
| --------------
| |
XOR <----|
| |
--------- |
| DES 1 | |
--------- |
| |
XOR <----
|
|
Ciphertext
where the combined counter/OFB mode I mentioned earlier is used to supply a value XORed with both the input and output of the block cipher.
The ANSI x9.17 standard uses the following arrangement of triple-DES encipherments (of the standard Encrypt-Decrypt-Encrypt type), all three of which use the same key, to produce successive output values from a changing seed value, with the input of values having some degree of entropy derived from physical randomness, such as the date and time of keypresses:
which can also be illustrated as an ASCII diagram:
input seed
| |
| |
------- |
|3-DES| |
------- |
| |
|-----> XOR
| |
| -------
| |3-DES|
| -------
| |
| |-------- output
| |
-----> XOR
|
-------
|3-DES|
-------
|
|
seed
Where the quantity of available physically random input matches the quantity of output desired, of course, producing output from a method like this for purposes of generating session keys or even private keys presents no problem. When this is not the case, techniques such as incrementing the previous input, or, preferably, something stronger, perhaps involving an encryption, for use as the next input might be acceptable for some uses, such as producing session keys. Clearly, though, compromises of this nature should not be accepted when producing the starting values for a search for RSA primes, or a Diffie-Hellman private key. Instead, a sufficient quantity of actual random values will simply have to be insisted upon.
Another possibility is to have a pool of random values; when a random value is available, it is used to produce an output which goes into that pool; when a pseudorandom value is needed, a value from the pool is used as an input. That value, of course, needs to be modified, perhaps by having the output it generates XORed to it. Again, something stronger would likely be preferred.
Such a pool is used by PGP, which uses what can be seen as a very appropriate technique to preventing it from containing dangerous information: before it is used in encrypting a message, it is encrypted based on a hash of the message to be encrypted; after it has been used to encrypt a message, it is encrypted based on a hash of its own contents.
The exit operation makes use of the fact that a hash is not reversible. Since a hash is useless by itself as an entry operation, the entry operation instead makes use of the same unknown value that the program is protecting, the message to be sent.
One way to use a random pool with a generator like the one from x9.17 would be to use three cascaded layers of it.
When physical random input is available, use that input with an input seed to produce an output which is XORed with an element of the pool, pointed to by an input pointer which is incremented when used.
When pseudorandom output is required, using a completely independent output pointer, take an element of the pool, and use it with a pool seed to produce an output which is both XORed with that element of the pool, and also used as an input, with an output seed, to produce the desired output. The output pointer also increments each time it is used.
This separates the values used to modify the pool from those which are used as outputs. Note that the pool seeds and the output seeds are modified in step, the same number of times.
Next
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page