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 **E**lectronic
**C**ode**B**ook 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 **C**ipher
**B**lock **C**haining,
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 **O**utput
**F**eed**B**ack,
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 **C**ipher
**F**eed**B**ack.
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] [Up/Previous] [Index]

Next

Chapter Start

Skip to Next Chapter

Table of Contents

Main Page