At the same time that DES was brought to public attention, a number of ways of using DES were recommended.
The obvious way of using DES is simply to apply it directly to plaintext, transforming each 64-bit block of plaintext. This is called ECB, or Electronic CodeBook mode.
There are two reasons this mode might not be found satisfactory. If the same message is sent twice, with the same key, its enciphered form will also be identical. Also, one needs to have eight bytes of plaintext available before performing encipherment. Thus, other ways of using DES were proposed. None of them strengthened the basic cipher, or added to the size of the key.
CBC, for Cipher Block Chaining, is one of the most popular modes. It addresses the first of the two problems with ECB mode. Each plaintext block, before being encrypted normally by DES (as in ECB mode) is XORed with the previous ciphertext block. The first plaintext block is XORed with a random 64-bit block, called the initialization vector, which is transmitted in the clear. This mode looks like this:
Plaintext
| |
--->XOR -------->XOR
| | |
----------- | -----------
| DES | | | DES |
----------- | -----------
| | |
| | |
|--------- |-----
| |
| |
Ciphertext
The useful properties of CBC mode can be illustrated by means of the following short demonstration:
Let's imagine a block cipher that operates on three-letter groups, and uses Vigenere instead of XOR...
Plain: BIL LNE EDS MON EYX
Previous cipher: ZQT MNM VTI UTU LKE
--- --- --- --- --- Vigenere step
AYE XAQ ZWA GHI PIB
=== === === === === Block cipher step
Cipher: ZQT MNM VTI UTU LKE MRV
Now, if we change the message at the beginning, everything changes all the way through, because information indeed keeps getting propagated:
Plain: MIK ENE EDS MON EYX
Previous cipher: ZQT RJY QEI RMQ LVI
--- --- --- --- --- Vigenere step
LYD VWC UHA DAD PTF
=== === === === === Block cipher step
Cipher: ZQT RJY QEI RMQ LVI SZR
But if, instead, it is the original message that is sent, and a transmission error takes place, so that instead of recieving
ZQT MNM VTI UTU LKE MRV
the reciever gets
ZQT MKM VTI UTU LKE MRV
then only two blocks are destroyed. Since each ciphertext block was a function of the plaintext block and the previous ciphertext block, each plaintext block is a function of the ciphertext block and the previous ciphertext block. As long as those two ciphertext blocks are right, the rest of the message is irrelevant.
Cipher: ZQT MKM VTI UTU LKE MRV
=== === === === === Inverse block cipher step
PQK XAQ ZWA GHI PIB (1)
Previous cipher: ZQT MKM VTI UTU LKE (2)
--- --- --- --- --- Inverse Vigenere ((1)-(2))
Plaintext: QAR LPE EDS MON EYX
In this decipherment example, the first plaintext block is totally garbled, because the erroneous ciphertext block is the input into the block cipher; the second plaintext block only has an error which matches that of the plaintext block, because the erroneous block is used in a Vigenere calculation after the block cipher.
Thus, someone could even note that ...EDSMONEY is probably NEEDSMONEY, and work out that LPE should become LNE. That would allow MKM to be corrected to MNM, and the message recovered.
In the binary case, a transmission error in one block will garble that block, and modify the succeeding block by inverting exactly those bits which were in error in the preceding transmitted ciphertext block. Note that since the IV has no corresponding "plaintext", altering bits in the IV can be used by an attacker as a technique for altering corresponding bits of the first plaintext block without causing a garble.
OFB, for Output FeedBack, addresses both the first and second problems noted earlier that exist with ECB mode. An initialization vector is again sent in the clear. It is repeatedly encrypted by DES, and the result of doing so is XORed with the successive blocks of the plaintext.
This mode has two problems of its own. The plaintext itself is only subjected to an XOR. This means that if the plaintext is known, another plaintext can be substituted by inverting the same bits of the ciphertext as one would need to invert of the plaintext to do so. This is called a bit-flipping attack. And there is always the possibility, admittedly a slim one, that one might choose a key and an initialization vector such that the successive blocks generated might repeat in a short loop.
A mode which seems to avoid most of the problems so far encountered is CFB, for Cipher FeedBack. Here, a plaintext block is enciphered by being XORed to the DES encryption of the previous ciphertext block. For the first plaintext block, an initialization vector again takes the role of the first plaintext block. This mode can be illustrated as follows:
Plaintext
| |
| |
--->XOR |---| -------->XOR
| | | | |
| | D | | |
|-----| E |---- |-----
| | S | |
| | | |
| |---| |
Ciphertext
A bit-flipping attack will garble subsequent blocks, and so if one takes care that messages have checksums, straddle more than one block, and so on, that is prevented despite the fact that the plaintext is only subjected to an XOR at the time of being enciphered. If no precautions are taken, however, since the last block of the message has no block following it, a bit-flipping attack may be performed against that block.
Since the plaintext modifies what is used to XOR later parts, there is no problem of a generator falling into a short loop.
This mode limits the propagation of transmission errors to the same extent as CBC mode. Once again, this can be illustrated using an alphabetic cipher as an example. To simplify matters, the same block cipher key and the same plaintext are used as in the previous example, and this will show that these two modes are very closely related.
Previous cipher: QXD AYE XAQ ZWA GHI
=== === === === === Block cipher step
Enciphered previous: ZQT MNM VTI UTU LKE
Plain: BIL LNE EDS MON EYX
--- --- --- --- --- Vigenere step
Cipher: QXD AYE XAQ ZWA GHI PIB
Now, if we change the message at the beginning, everything changes all the way through, because information indeed keeps getting propagated:
QXD LYD VWC UHA DAD
=== === === === === Block cipher step
Enciphered previous: ZQT RJY QEI RMQ LVI
Plain: MIK ENE EDS MON EYX
--- --- --- --- --- Vigenere step
Cipher: QXD LYD VWC UHA DAD PTF
But if, instead, it is the original message that is sent, and a transmission error takes place, so that instead of recieving
QXD AYE XAQ ZWA GHI PTB
the reciever gets
QXD AYE XCQ ZWA GHI PTB
then only two blocks are destroyed. Since each ciphertext block was a function of the plaintext block and the previous ciphertext block, each plaintext block is a function of the ciphertext block and the previous ciphertext block. As long as those two ciphertext blocks are right, the rest of the message is irrelevant.
Previous cipher: QXD AYE XCQ ZWA GHI
=== === === === === Block cipher step
Enciphered previous: ZQT MNM JRP UTU LKE (1)
Cipher: QXD AYE XCQ ZWA GHI PTB (2)
--- --- --- --- --- Inverse Vigenere ((2)-(1))
Plaintext: BIL LPE QFL MON EYX
In this decipherment example, the first plaintext block only has an error which matches that of the plaintext block, but the second block is totally garbled, because the erroneous ciphertext block went through the block cipher before being applied to the plaintext.
This mode has variants that involve performing DES encryptions more often, such as once for each bit or byte. Some problems have been claimed with these variants, and they require more computation without increasing security.
One other mode among those originally suggested for use with DES was Output Feedback Mode (OFB): this mode encrypted an initial value with DES, and then the result of the encryption was encrypted again repeatedly. The resulting values were used as a keystream to XOR with messages.
This mode was not often used, because of concerns that one might accidentally choose a starting value that led to a short cycle.
This could be avoided with counter mode. This mode was not included among the modes originally recommended for use with DES, but it is included among the basic modes of operation recommended for use with the new AES standard.
Here, a starting value is encrypted in DES to supply the first block of keystream bits, and then the starting value is incremented, and the next block of keystream bits is the encrypted form of it, and so on. This was considered dangerous, because one might accidentally choose a starting value that created a sequence that overlapped with one previously used; starting values would only need to be near each other, not identical, and keeping track of every starting value previously used with a key would excessively complicate the definition of the mode.
To my way of thinking, one could combine both approaches, feeding back the output and XORing the value of a counter to it, thus making it difficult for a short cycle to happen, and making identical sequences much more unlikely. But for some reason this idea has not caught on.
The paper "Guaranteeing the diversity of number generators" by Adi Shamir and Boaz Tsaban discusses a similar mode, but with a second encryption step applied to the XOR of the counter and the first encryption output. For that type of generator, they provide a proof that even if the block ciphers used are bad, it will not make them worse. The example they give of a pathological block cipher for the mode given above, however, is one that is non-bijective; and block ciphers can be easily proved to be bijective, even if it is much more difficult to prove they are secure.
Next
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page