<<

. 8
( 29)



>>

encryption processors, they can encrypt or decrypt different blocks without regard for each other.

The problem with ECB mode is that if a cryptanalyst has the plaintext and ciphertext for several
messages, he can start to compile a code book without knowing the key. In most real-world situations,
fragments of messages tend to repeat. Different messages may have bit sequences in common.
Computer-generated messages, like electronic mail, may have regular structures. Messages may be
highly redundant or have long strings of zeros or spaces.

If a cryptanalyst learns that the plaintext block “5e081bc5” encrypts to the ciphertext block
“7ea593a4,” he can immediately decrypt that ciphertext block whenever it appears in another
message. If the encrypted messages have a lot of redundancies, and these tend to show up in the same
places in different messages, a cryptanalyst can get a lot of information. He can mount statistical
attacks on the underlying plaintext, irrespective of the strength of the block cipher.

This vulnerability is greatest at the beginning and end of messages, where well-defined headers and
footers contain information about the sender, receiver, date, and so on. This problem is sometimes
called stereotyped beginnings and stereotyped endings.




Page 164 of 666
Applied Cryptography: Second Edition - Bruce Schneier




On the plus side, there is no security risk in encrypting multiple messages with the same key. In fact,
each block can be looked at as a separate message encrypted with the same key. Bit errors in the
ciphertext, when decrypted, will cause the entire plaintext block to decrypt incorrectly but will not
affect the rest of the plaintext. However, if a ciphertext bit is accidentally lost or added, all subsequent
ciphertext will decrypt incorrectly unless there is some kind of frame structure to realign the block
boundaries.

Padding

Most messages don™t divide neatly into 64-bit (or whatever size) encryption blocks; there is usually a
short block at the end. ECB requires 64-bit blocks. Padding is the way to deal with this problem.

Pad the last block with some regular pattern”zeros, ones, alternating ones and zeros”to make it a
complete block. If you need to delete the padding after decryption, add the number of padding bytes
as the last byte of the last block. For example, assume the block size is 64 bits and the last block
consists of 3 bytes (24 bits). Five bytes of padding are required to make the last block 64 bits; add 4
bytes of zeros and a final byte with the number 5. After decryption, delete the last 5 bytes of the last
decryption block. For this method to work correctly, every message must be padded. Even if the
plaintext ends on a block boundary, you have to pad one complete block. Otherwise, you can use an
end-of-file character to denote the final plaintext byte, and then pad after that character.

Figure 9.1 is an alternative, called ciphertext stealing [402]. Pn-1 is the last full plaintext block and Pn
is the final, short, plaintext block. Cn-1 is the last full ciphertext block and Cn is the final, short,
ciphertext block. C™ is just an intermediate result and is not part of the transmitted ciphertext.

9.2 Block Replay

A more serious problem with ECB mode is that an adversary could modify encrypted messages
without knowing the key, or even the algorithm, in such a way as to fool the intended recipient. This
problem was first discussed in [291].


To illustrate the problem, consider a money transfer system that moves money between accounts in
different banks. To make life easier for the bank™s computer systems, banks agree on a standard
message format for money transfer that looks like this:

Bank One: Sending 1.5 blocks
Bank Two: Receiving 1.5 blocks
Depositor™s Name 6 blocks
Depositor™s Account 2 blocks
Amount of Deposit 1 block

A block corresponds to an 8-byte encryption block. The messages are encrypted using some block
algorithm in ECB mode.




Page 165 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Figure 9.1 Ciphertext stealing in ECB mode.

Mallory, who is listening on the communications line between two banks, Bank of Alice and Bank of
Bob, can use this information to get rich. First, he sets up his computer to record all of the encrypted
messages from Bank of Alice to Bank of Bob. Then, he transfers $100 from Bank of Alice to his
account in Bank of Bob. Later, he does it again. Using his computer, he examines the recorded
messages looking for a pair of identical messages. These messages are the ones authorizing the $100
transfers to his account. If he finds more than one pair of identical messages (which is most likely in
real life), he does another money transfer and records those results. Eventually he can isolate the
message that authorized his money transaction.

Now he can insert that message into the communications link at will. Every time he sends the message
to Bank of Bob, another $100 will be credited to his account. When the two banks reconcile their
transfers (probably at the end of the day), they will notice the phantom transfer authorizations; but if
Mallory is clever, he will have already withdrawn the money and headed for some banana republic
without extradition laws. And he probably did his scam with dollar amounts far larger than $100, and
with lots of different banks.

At first glance, the banks could easily prevent this by adding a timestamp to their messages.

Date/Time Stamp: 1 block
Bank One: Sending 1.5 blocks
Bank Two: Receiving 1.5 blocks
Depositor™s Name 6 blocks
Depositor™s Account 2 blocks
Amount of Deposit 1 block

Two identical messages would be easy to spot using this system. Still, using a technique called block
replay, Mallory can still get rich. Figure 9.2 shows that Mallory can pick out the eight ciphertext
blocks that correspond to his own name and account number: blocks 5 through 12. A diabolical laugh
is appropriate at this point, because Mallory is now ready.

He intercepts random messages from Bank of Alice to Bank of Bob and replaces blocks 5 through 12
in the message with the bytes that correspond to his name and account number. Then he sends them
on to Bank of Bob. He doesn™t have to know who the original depositor was; he doesn™t even have to
know what the amount was (although, he could correlate the messages he doctored with the various
deposits into his account and determine the encrypted blocks corresponding to some dollar amount).
He simply changes the name and account numbers to his own and watches his account balance grow.
(I suppose Mallory has to be careful not to modify a withdrawal message, but assume for the moment
that each is a different length or something.)




Figure 9.2 Encryption blocks for an example record.

This will take longer than a day for the banks to catch. When they reconcile their transfers at the end
of the day, everything will match. It probably won™t be until one of the legitimate depositors notices
that his deposits are not being credited, or when someone flags unusual activity in Mallory™s account,
that the banks will figure out the scam. Mallory isn™t stupid, and by then he will have closed his
account, changed his name, and bought a villa in Argentina.

Banks can minimize the problem by changing their keys frequently, but this only means that Mallory



Page 166 of 666
Applied Cryptography: Second Edition - Bruce Schneier



is going to have to work more quickly. Adding a MAC, however, will also solve the problem. Even so,
this is a fundamental problem with ECB mode. Mallory can remove, repeat, or interchange blocks at
will. The solution is a technique called chaining.

9.3 Cipher Block Chaining Mode

Chaining adds a feedback mechanism to a block cipher: The results of the encryption of previous
blocks are fed back into the encryption of the current block. In other words, each block is used to
modify the encryption of the next block. Each ciphertext block is dependent not just on the plaintext
block that generated it but on all the previous plaintext blocks.

In cipher block chaining (CBC) mode, the plaintext is XORed with the previous ciphertext block
before it is encrypted. Figure 9.3a shows CBC encryption in action. After a plaintext block is
encrypted, the resulting ciphertext is also stored in a feedback register. Before the next plaintext block
is encrypted, it is XORed with the feedback register to become the next input to the encrypting
routine. The resulting ciphertext is again stored in the feedback register, to be XORed with the next
plaintext block, and so on until the end of the message. The encryption of each block depends on all
the previous blocks.

Decryption is just as straightforward (see Figure 9.3b). A ciphertext block is decrypted normally and
also saved in a feedback register. After the next block is decrypted, it is XORed with the results of the
feedback register. Then the next ciphertext block is stored in the feedback register, and so on, until
the end of the message.

Mathematically, this looks like:

Ci = EK(Pi Ci-1)
Pi = Ci-1 DK(Ci)




Figure 9.3 Cipher block chaining mode.

Initialization Vector

CBC mode forces identical plaintext blocks to encrypt to different ciphertext blocks only when some
previous plaintext block is different. Two identical messages will still encrypt to the same ciphertext.
Even worse, two messages that begin the same will encrypt in the same way up to the first difference.


Some messages have a common header: a letterhead, or a “From” line, or whatever. While block
replay would still be impossible, this identical beginning might give a cryptanalyst some useful
information.




Page 167 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Prevent this by encrypting random data as the first block. This block of random data is called the
initialization vector (IV), initializing variable, or initial chaining value. The IV has no meaning; it™s
just there to make each message unique. When the receiver decrypts this block, he just uses it to fill
the feedback register and otherwise ignores it. A timestamp often makes a good IV. Otherwise, use
some random bits from someplace.

With the addition of IVs, identical plaintext messages encrypt to different ciphertext messages. Thus,
it is impossible for an eavesdropper to attempt block replay, and more difficult for him to build a code
book. While the IV should be unique for each message encrypted with the same key, it is not an
absolute requirement.

The IV need not be secret; it can be transmitted in the clear with the ciphertext. If this seems wrong,
consider the following argument. Assume that we have a message of several blocks: B1, B2,..., Bi. B1 is
encrypted with the IV. B2 is encrypted using the ciphertext of B1 as the IV. B3 is encrypted using the
ciphertext of B2 as the IV, and so on. So, if there are n blocks, there are n-1 exposed “IVs,” even if the
original IV is kept secret. So there™s no reason to keep the IV secret; the IV is just a dummy ciphertext
block”you can think of it as B0 to start the chaining.

Padding

Padding works just like ECB mode, but in some applications the ciphertext has to be exactly the same
size as the plaintext. Perhaps a plaintext file has to be encrypted and then replaced in the exact same
memory location. In this case, you have to encrypt the last short block differently. Assume the last
block has j bits. After encrypting the last full block, encrypt the ciphertext again, select the left-most j
bits of the encrypted ciphertext, and XOR that with the short block to generate the ciphertext. Figure
9.4 illustrates this.

The weakness here is that while Mallory cannot recover the last plaintext block, he can change it
systematically by changing individual bits in the ciphertext. If the last few bits of the ciphertext
contain essential information, this is a weakness. If the last bits simply contain housekeeping
information, it isn™t a problem.

Ciphertext stealing is a better way (see Figure 9.5) [402]. Pn-1 is the last full plaintext block, and Pn is
the final, short, plaintext block. Cn-1 is the last full ciphertext block, and Cn is the final, short,
ciphertext block. C™ is just an intermediate result and is not part of the transmitted ciphertext. The
benefit of this method is that all the bits of the plaintext message go through the encryption algorithm.

Error Propagation

CBC mode can be characterized as feedback of the ciphertext at the encryption end and feedforward
of the ciphertext at the decryption end. This has implications having to do with errors. A single bit
error in a plaintext block will affect that ciphertext block and all subsequent ciphertext blocks. This
isn™t significant because decryption will reverse that effect, and the recovered plaintext will have the
same single error.

Ciphertext errors are more common. They can easily result from a noisy communications path or a
malfunction in the storage medium. In CBC mode, a single-bit error in the ciphertext affects one
block and one bit of the recovered plaintext. The block containing the error is completely garbled.
The subsequent block has a 1-bit error in the same bit position as the error.




Page 168 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Figure 9.4 Encrypting the last short block in CBC mode.




Figure 9.5 Ciphertext stealing in CBC mode.

This property of taking a small ciphertext error and converting it into a large plaintext error is called
error extension. It is a major annoyance. Blocks after the second are not affected by the error, so CBC
mode is self-recovering. Two blocks are affected by an error, but the system recovers and continues to
work correctly for all subsequent blocks. CBC is an example of a block cipher being used in a self-
synchronizing manner, but only at the block level.

While CBC mode recovers quickly from bit errors, it doesn™t recover at all from synchronization
errors. If a bit is added or lost from the ciphertext stream, then all subsequent blocks are shifted one
bit out of position and decryption will generate garbage indefinitely. Any cryptosystem that uses CBC
mode must ensure that the block structure remains intact, either by framing or by storing data in
multiple-block-sized chunks.

Security Problems

Some potential problems are caused by the structure of CBC. First, because a ciphertext block affects
the following block in a simple way, Mallory can add blocks to the end of an encrypted message
without being detected. Sure, it will probably decrypt to gibberish, but in some situations this is
undesirable.

If you are using CBC, you should structure your plaintext so that you know where the message ends
and can detect the addition of extra blocks.

Second, Mallory can alter a ciphertext block to introduce controlled changes in the following
decrypted plaintext block. For example, if Mallory toggles a single ciphertext bit, the entire block will
decrypt incorrectly, but the following block will have a 1-bit error in the corresponding bit position.
There are situations where this is desirable. The entire plaintext message should include some kind of
controlled redundancy or authentication.

Finally, although plaintext patterns are concealed by chaining, very long messages will still have
patterns. The birthday paradox predicts that there will be identical blocks after 2m/2 blocks, where m
is the block size. For a 64-bit block size, that™s about 34 gigabytes. A message has to be pretty long
before this is a problem.




Page 169 of 666
Applied Cryptography: Second Edition - Bruce Schneier




9.4 Stream Ciphers

Stream ciphers convert plaintext to ciphertext 1 bit at a time. The simplest implementation of a
stream cipher is shown in Figure 9.6. A keystream generator (sometimes called a running-key
generator) outputs a stream of bits: k1, k2, k3,..., ki. This keystream (sometimes called a running key)
is XORed with a stream of plaintext bits, p1, p2, p3,..., pi, to produce the stream of ciphertext bits.

ci = pi ki

At the decryption end, the ciphertext bits are XORed with an identical keystream to recover the
plaintext bits.

pi = ci ki

Since

pi ki ki = pi

this works nicely.

The system™s security depends entirely on the insides of the keystream generator. If the keystream
generator outputs an endless stream of zeros, the ciphertext will equal the plaintext and the whole
operation will be worthless. If the keystream generator spits out a repeating 16-bit pattern, the
algorithm will be a simple XOR with negligible security (see Section 1.4). If the keystream generator
spits out an endless stream of random (not pseudo-random, but real random”see Section 2.8) bits,
you have a one-time pad and perfect security.

The reality of stream cipher security lies somewhere between the simple XOR and the one-time pad.
The keystream generator generates a bit stream that looks random, but is actually a deterministic
stream that can be flawlessly reproduced at decryption time. The closer the keystream generator™s
output is to random, the harder time a cryptanalyst will have breaking it.




Figure 9.6 Stream cipher.

If, however, the keystream generator produces the same bit stream every time it is turned on, the
resulting cryptosystem will be trivial to break. An example will show why.

If Eve has a ciphertext and associated plaintext, she can XOR the plaintext and the ciphertext to
recover the keystream. Or, if she has two different ciphertexts encrypted with the same keystream,
she can XOR them together and get two plaintext messages XORed with each other. This is easy to
break, and then she can XOR one of the plaintexts with the ciphertext to get the keystream.

Now, whenever she intercepts another ciphertext message, she has the keystream bits necessary to



Page 170 of 666
Applied Cryptography: Second Edition - Bruce Schneier



decrypt it. In addition, she can decrypt and read any old ciphertext messages she has previously
intercepted. When Eve gets a single plaintext/ciphertext pair, she can read everything.

This is why all stream ciphers have keys. The output of the keystream generator is a function of the
key. Now, if Eve gets a plaintext/ciphertext pair, she can only read messages encrypted with a single
key. Change the key, and the adversary is back to square one. Stream ciphers are especially useful to
encrypt never-ending streams of communications traffic: a T-1 link between two computers, for
example.

A keystream generator has three basic parts (see Figure 9.7). The internal state describes the current
state of the keystream generator. Two keystream generators, with the same key and the same internal
state, will produce the same keystream. The output function takes the internal state and generates a
keystream bit. The next-state function takes the internal state and generates a new internal state.

9.5 Self-Synchronizing Stream Ciphers

For a self-synchronizing stream cipher, each keystream bit is a function of a fixed number of previous
ciphertext bits [1378]. The military calls this ciphertext auto key (CTAK). The basic idea was
patented in 1946 [667].




Figure 9.7 Inside a keystream generator.

Figure 9.8 shows a self-synchronizing stream cipher. The internal state is a function of the previous n
ciphertext bits. The cryptographic complexity is in the output function, which takes the internal state
and generates a keystream bit.

Since the internal state depends wholly on the previous n ciphertext bits, the decryption keystream
generator will automatically synchronize with the encryption keystream generator after receiving n
ciphertext bits.

In smart implementations of this mode, each message begins with a random header n bits long. That
header is encrypted, transmitted, and then decrypted. The decryption will be incorrect, but after
those n bits both keystream generators will be synchronized.

The down side of a self-synchronizing stream cipher is error propagation. For each ciphertext bit
garbled in transmission, the decryption keystream generator will incorrectly produce n keystream
bits. Therefore, for each ciphertext error, there will be n corresponding plaintext errors, until the
garbled bit works its way out of the internal state.

Security Problems

Self-synchronizing stream ciphers are also vulnerable to a playback attack. First Mallory records
some ciphertext bits. Then, at a later time, he substitutes this recording into current traffic. After
some initial garbage while the receiving end resynchronizes, the old ciphertext will decrypt as normal.
The receiving end has no way of knowing that this is not current data, but old data being replayed.
Unless timestamps are used, Mallory can convince a bank to credit his account again and again, by



Page 171 of 666
Applied Cryptography: Second Edition - Bruce Schneier



replaying the same message (assuming the key hasn™t been changed, of course). Other weaknesses in
this type of scheme could be exploited in the cases of very frequent resynchronization [408].




Figure 9.8 A self-synchronizing keystream generator.

9.6 Cipher-Feedback Mode

Block ciphers can also be implemented as a self-synchronizing stream cipher; this is called cipher-
feedback (CFB) mode. With CBC mode, encryption cannot begin until a complete block of data is
received. This is a problem in some network applications. In a secure network environment, for
example, a terminal must be able to transmit each character to the host as it is entered. When data
has to be processed in byte-sized chunks, CBC mode just won™t do.


In CFB mode, data can be encrypted in units smaller than the block size. The following example will
encrypt one ASCII character at a time (this is called 8-bit CFB), but nothing is sacred about the
number eight. You can encrypt data one bit at a time using 1-bit CFB, although using one complete
encryption of a block cipher for a single bit seems like a whole lot of work; a stream cipher might be a
better idea. (Reducing the number of rounds of the block cipher to speed things up is not
recommended [1269].) You can also use 64-bit CFB, or any n-bit CFB where n is less than or equal to
the block size.

Figure 9.9 shows 8-bit CFB mode working with a 64-bit block algorithm. A block algorithm in CFB
mode operates on a queue the size of the input block. Initially, the queue is filled with an IV, as in
CBC mode. The queue is encrypted and the left-most eight bits of the result are XORed with the first
8-bit character of the plaintext to become the first 8-bit character of the ciphertext. This character can
now be transmitted. The same eight bits are also moved to the right-most eight bit positions of the
queue, and all the other bits move eight to the left. The eight left-most bits are discarded. Then the
next plaintext character is encrypted in the same manner. Decryption is the reverse of this process. On
both the encryption and the decryption side, the block algorithm is used in its encryption mode.




Figure 9.9 8-bit cipher-feedback mode.




Page 172 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Figure 9.10 n-bit CFB with an n-bit algorithm.

If the block size of the algorithm is n, then n-bit CFB looks like (see Figure 9.10):

Ci = Pi EK(Ci-1)
Pi = Ci EK(Ci-1)

Like CBC mode, CFB mode links the plaintext characters together so that the ciphertext depends on
all the preceding plaintext.

Initialization Vector

To initialize the CFB process, the input to the block algorithm must be initialized with an IV. Like the
IV used in CBC mode, it need not be secret.

The IV must be unique, though. (This is different from the IV in CBC mode, which should be unique
but does not have to be.) If the IV in CFB is not unique, a cryptanalyst can recover the corresponding
plaintext. The IV must be changed with every message. It can be a serial number, which increments
after each message and does not repeat during the lifetime of the key. For data encrypted for storage,
it can be a function of the index used to look up the data.

Error Propagation

With CFB mode, an error in the plaintext affects all subsequent ciphertext and reverses itself at
decryption. An error in the ciphertext is more interesting. The first effect of a single-bit error in the
ciphertext is to cause a single error in the plaintext. After that, the error enters the shift register,
where it causes ciphertext to be garbled until it falls off the other end of the register. In 8-bit CFB
mode, 9 bytes of decrypted plaintext are garbled by a single-bit error in the ciphertext. After that, the
system recovers and all subsequent ciphertext is decrypted correctly. In general, in n-bit CFB a single
ciphertext error will affect the decryption of the current and following m/n-1 blocks, where m is the
block size.

One subtle problem with this kind of error propagation is that if Mallory knows the plaintext of a
transmission, he can toggle bits in a given block and make it decrypt to whatever he wants. The next
block will decrypt to garbage, but the damage may already be done. And he can change the final bits
of a message without detection.

CFB is self-recovering with respect to synchronization errors as well. The error enters the shift
register, where it garbles 8 bytes of data until it falls off the other end. CFB is an example of block
cipher being used as a self-synchronizing stream cipher (at the block level).

9.7 Synchronous Stream Ciphers

In a synchronous stream cipher the keystream is generated independent of the message stream. The




Page 173 of 666
Applied Cryptography: Second Edition - Bruce Schneier



military calls this Key Auto-Key (KAK). On the encryption side, a keystream generator spits out
keystream bits, one after the other. On the decryption side, another keystream generator spits out the
identical keystream bits, one after the other. This works, as long as the two keystream generators are
synchronized. If one of them skips a cycle or if a ciphertext bit gets lost during transmission, then
every ciphertext character after the error will decrypt incorrectly.

If this happens, the sender and receiver must resynchronize their keystream generators before they
can proceed. Frustrating matters even further, they must do this in such a way as to ensure that no
part of the keystream is repeated, so the obvious solution of resetting the keystream generator to an
earlier state won™t work.

On the plus side, synchronous ciphers do not propagate transmission errors. If a bit is garbled during
transmission, which is far more likely than a bit being lost altogether, then only the garbled bit will be
decrypted incorrectly. All preceding and subsequent bits will be unaffected.

Since a keystream generator must generate the same output on both the encryption and decryption
ends, it must be deterministic. Because it is implemented in a finite-state machine (i.e., a computer),
the sequence will eventually repeat. These keystream generators are called periodic. Except for one-
time pads, all keystream generators are periodic.

The keystream generator must have a long period, one far longer than the number of bits the
generator will output between key changes. If the period is less than the plaintext, then different parts
of the plaintext will be encrypted the same way”a severe weakness. If a cryptanalyst knows a piece of
the plaintext, he can recover a piece of the keystream and use that to recover more of the plaintext.
Even if the analyst only has the ciphertext, he can XOR the sections encrypted with the same
keystream and get the XOR of plaintext with plaintext. This is just the simple XOR algorithm with a
very long key.

How long a period is long enough depends on the application. A keystream generator encrypting a
continuous T-1 link will encrypt 237 bits per day. The keystream generator™s period must be orders of
magnitude larger than that, even if the key is changed daily. If the period is long enough, you might
only have to change the key weekly or even monthly.


Synchronous stream ciphers also protect against any insertions and deletions in the ciphertext,
because these cause a loss of synchronization and will be immediately detected. They do not, however,
fully protect against bit toggling. Like block ciphers in CFB mode, Mallory can toggle individual bits
in the stream. If he knows the plaintext, he can make those bits decrypt to whatever he wants.
Subsequent bits will decrypt correctly, so in certain applications Mallory can still do considerable
damage.

Insertion Attack

Synchronous stream ciphers are vulnerable to an insertion attack [93]. Mallory has recorded a
ciphertext stream, but does not know the plaintext or the keystream used to encrypt the plaintext.

Original plaintext: p1 p2 p3 p4 ...
Original keystream: k1 k2 k3 k4 ...
Original ciphertext: c1 c2 c3 c4 ...


Mallory inserts a single known bit, p™, into the plaintext after p1 and then manages to get the modified
plaintext encrypted with the same keystream. He records the resultant new ciphertext:




Page 174 of 666
Applied Cryptography: Second Edition - Bruce Schneier




New plaintext: p1 p™ p2 p3 p4 ...
Original keystream: k1 k2 k3 k4 k5 ...
Updated ciphertext: c1 c™2 c™3 c™4 c™5 ...


Assuming he knows the value of p™, he can determine the entire plaintext after that bit from the
original ciphertext and new ciphertext:

k2 = c™2 p™, and then p2 = c2 k2
k3 = c™3 p2, and then p3 = c3 k3
k4 = c™4 p3, and then p4 = c4 k4


Mallory doesn™t even have to know the exact position in which the bit was inserted; he can just
compare the original and updated ciphertexts to see where they begin to differ. To protect against this
attack, never use the same keystream to encrypt two different messages.

9.8 Output-Feedback Mode

Output-feedback (OFB) mode is a method of running a block cipher as a synchronous stream cipher.
It is similar to CFB mode, except that n bits of the previous output block are moved into the right-
most positions of the queue (see Figure 9.11). Decryption is the reverse of this process. This is called n-
bit OFB. On both the encryption and the decryption sides, the block algorithm is used in its
encryption mode. This is sometimes called internal feedback, because the feedback mechanism is
independent of both the plaintext and the ciphertext streams [291].

If n is the block size of the algorithm, then n-bit OFB looks like (see Figure 9.12):

Ci = Pi Si; Si = EK(Si-1)
Pi = Ci S1; Si = EK(Si-1)




Figure 9.11 8-bit output-feedback mode.

Si is the state, which is independent of either the plaintext or the ciphertext.

One nice feature of OFB mode is that most of the work can occur offline, before the plaintext message
even exists. When the message finally arrives, it can be XORed with the output of the algorithm to
produce the ciphertext.

Initialization Vector

The OFB shift register must also be initially loaded with an IV. It should be unique but does not have
to be secret.




Page 175 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Error Propagation

OFB mode has no error extension. A single-bit error in the ciphertext causes a single-bit error in the
recovered plaintext. This can be useful in some digitized analog transmissions, like digitized voice or
video, where the occasional single-bit error can be tolerated but error extension cannot.

On the other hand, a loss of synchronization is fatal. If the shift registers on the encryption end and
the decryption end are not identical, then the recovered plaintext will be gibberish. Any system that
uses OFB mode must have a mechanism for detecting a synchronization loss and a mechanism to fill
both shift registers with a new (or the same) IV to regain synchronization.




Figure 9.12 n-bit OFB with an n-bit algorithm.

Security Problems with OFB

An analysis of OFB mode [588,430,431,789] demonstrates that OFB should be used only when the
feedback size is the same as the block size. For example, you should only use a 64-bit algorithm in 64-
bit OFB mode. Even though the U.S. government authorizes other feedback sizes for DES [1143],
avoid them.

OFB mode XORs a keystream with the text. This keystream will eventually repeat. It is important
that it does not repeat with the same key; otherwise, there is no security. When the feedback size
equals the block size, the block cipher acts as a permutation of m-bit values (where m is the block
length) and the average cycle length is 2m- 1. For a 64-bit block length, this is a very long number.
When the feedback size n is less than the block length, the average cycle length drops to around 2m/2.
For a 64-bit block cipher, this is only 232”not long enough.

Stream Ciphers in OFB

A stream cipher can also run in OFB mode. In this case, the key affects the next-state function (see
Figure 9.13). The output function does not depend on the key; very often it is something simple like a
single bit of the internal state or the XOR of multiple bits of the internal state. The cryptographic
complexity is in the next-state function; this function is key-dependent. This method is also called
internal feedback [291], because the feedback mechanism is internal to the key generation algorithm.

In a variant of this mode, the key determines just the initial state of the keystream generator. After
the key sets the internal state of the generator, the generator runs undisturbed from then on.


9.9 Counter Mode

Block ciphers in counter mode use sequence numbers as the input to the algorithm [824,498,715].
Instead of using the output of the encryption algorithm to fill the register, the input to the register is a
counter. After each block encryption, the counter increments by some constant, typically one. The
synchronization and error propagation characteristics of this mode are identical to those of OFB.



Page 176 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Counter mode solves the OFB mode problem of n-bit output where n is less than the block length.




Figure 9.13 A keystream generator in output-feedback mode.

Nothing is sacred about the counter; it does not have to count through all the possible inputs in order.
You can use any of the random-sequence generators in Chapters 16 and 17, whether
cryptographically secure or not, as input to the block algorithm.

Stream Ciphers in Counter Mode

Stream ciphers in counter mode have simple next-state functions and complicated output functions
dependent on the key. This technique, illustrated in Figure 9.14, was suggested in [498,715]. The next-
state function can be something as simple as a counter, adding one to the previous state.

With a counter mode stream cipher, it is possible to generate the ith key bit, ki, without first
generating all the previous key bits. Simply set the counter manually to the ith internal state and
generate the bit. This is useful to secure random-access data files; you can decrypt a specific block of
data without decrypting the entire file.

9.10 Other Block-Cipher Modes

Block Chaining Mode

To use a block algorithm in block chaining (BC) mode, simply XOR the input to the block cipher with
the XOR of all the previous ciphertext blocks. As with CBC, an IV starts the process.

Mathematically, this looks like:

Ci = EK(Pi Fi); Fi+1 = Fi Ci
Pi = Fi DK(Ci); Fi+1 = Fi Ci

Like CBC, BC™s feedback process extends errors in the plaintext. The primary problem with BC is
that because the decryption of a ciphertext block depends on all the previous ciphertext blocks, a
single error in the ciphertext will result in the incorrect decryption of all subsequent ciphertext
blocks.




Figure 9.14 A keystream generator in counter mode.



Page 177 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Propagating Cipher Block Chaining Mode

Propagating cipher block chaining (PCBC) [1080] mode is similar to CBC mode, except that both the
previous plaintext block and the previous ciphertext block are XORed with the current plaintext
block before encryption (or after decryption) (see Figure 9.15).

Ci = EK(Pi Ci-1 Pi-1)
Pi = Ci-1 Pi-1 DK(Ci)

PCBC was used in Kerberos version 4 (see Section 24.5) to perform both encryption and integrity
checking in one pass. In PCBC mode, an error in the ciphertext will result in incorrect decryption of
all blocks that follow. This means that checking a standard block at the end of a message will ensure
the integrity of the entire message.

Unfortunately, there is a problem with this mode [875]. Swapping two ciphertext blocks results in the
incorrect decryption of the two corresponding plaintext blocks, but due to the nature of the XOR with
the plaintext and the ciphertext, the errors cancel. So if the integrity checker looks only at the last few
blocks of the decrypted plaintext, it could be fooled into accepting a partially garbled message.
Although no one has figured out how to exploit this weakness, Kerberos version 5 switched to CBC
mode after the flaw was discovered.

Cipher Block Chaining with Checksum

Cipher block chaining with checksum (CBCC) is a CBC variant [1618]. Keep a running XOR of all
the plaintext blocks, and XOR that with the last plaintext block before encryption. CBCC ensures
that any change made to any ciphertext block changes the decrypted output of the last block. If the
last block contains any sort of integrity check or a constant, then the integrity of the decrypted
plaintext can be checked with very little additional overhead.




Figure 9.15 Propagating cipher block chaining mode.

Output Feedback with a Nonlinear Function

Output feedback with a nonlinear function (OFBNLF) [777] is a variant of both OFB and ECB where
the key changes with every block:

Ci = EKi(Pi); Ki = EK(Ki-1)
Pi = DKi(Ci); Ki = EK(Ki-1)

A single bit error in the ciphertext propagates to only one plaintext block. However, if a single bit is
lost or added, then there is infinite error extension. With a block algorithm that has a complicated key
scheduling algorithm, like DES, this mode is slow. I know of no cryptanalysis of this mode.



Page 178 of 666
Applied Cryptography: Second Edition - Bruce Schneier




More Modes

Other modes are possible, although they are not extensively used. Plaintext block chaining (PBC) is
like CBC except the previous plaintext block is XORed with the plaintext block instead of with the
ciphertext block. Plaintext feedback (PFB) is like CFB, except the plaintext, not the ciphertext, is used
for feedback. These two modes allow chosen-plaintext attacks in order to resist known-plaintext
attacks. There is also cipher block chaining of plaintext difference (CBCPD). I™m sure it gets even
weirder.

If a cryptanalyst has a brute-force keysearch machine, then he can recover the key if he can guess one
of the plaintext blocks. Some of these stranger modes amount to light encryption before applying the
encryption algorithm: for example, XORing the text with a fixed secret string or permuting the text.
Almost anything nonstandard will frustrate this sort of cryptanalysis.


9.11 Choosing a Cipher Mode

If simplicity and speed are your main concerns, ECB is the easiest and fastest mode to use a block
cipher. It is also the weakest. Besides being vulnerable to replay attacks, an algorithm in ECB mode is
the easiest to cryptanalyze. I don™t recommend ECB for message encryption.

For encrypting random data, such as other keys, ECB is a good mode to use. Since the data is short
and random, none of the shortcomings of ECB matter for this application.

For normal plaintext, use CBC, CFB, or OFB. Which mode you choose depends on your specific
requirements. Table 9.1 gives a summary of the security and efficiency of the various modes.

CBC is generally best for encrypting files. The increase in security is significant; and while there are
sometimes bit errors in stored data, there are almost never synchronization errors. If your application
is software-based, CBC is almost always the best choice.

CFB”specifically 8-bit CFB”is generally the mode of choice for encrypting streams of characters
when each character has to be treated individually, as in a link between a terminal and a host. OFB is
most often used in high-speed synchronous systems where error propagation is intolerable. OFB is
also the mode of choice if preprocessing is required.

OFB is the mode of choice in a error-prone environment, because it has no error extension.

Stay away from the weird modes. One of the four basic modes”ECB, CBC, OFB, and CFB”is
suitable for almost any application. These modes are not overly complex and probably do not reduce
the security of the system. While it is possible that a complicated mode might increase the security of a
system, most likely it just increases the complexity. None of the weird modes has any better error
propagation or error recovery characteristics.

9.12 Interleaving

With most modes, encryption of a bit (or block) depends on the encryption of the previous bits (or
blocks). This can often make it impossible to parallelize encryption. For example, consider a
hardware box that does encryption in CBC mode. Even if the box contains four encryption chips, only
one can work at any time. The next chip needs the results of the previous chip before it starts
working.




Page 179 of 666
Applied Cryptography: Second Edition - Bruce Schneier




The solution is to interleave multiple encryption streams. (This is not multiple encryption; that™s
covered in Sections 15.1 and 15.2). Instead of a single CBC chain, use four. The first, fifth, and every
fourth block thereafter are encrypted in CBC mode with one IV. The second, sixth, and every fourth
block thereafter are encrypted in CBC mode with another IV, and so on. The total IV is much longer
than it would have been without interleaving.

Think of it as encrypting four different messages with the same key and four different IVs. These
messages are all interleaved.

This trick can also be used to increase the overall speed of hardware encryption. If you have three
encryption chips, each capable of encrypting data at 33 megabits/second, you can interleave them to
encrypt a single 100 megabit/second data channel.

Figure 9.16 shows three parallel streams interleaved in CFB mode. The idea can also work in CBC
and OFB modes, and with any number of parallel streams. Just remember that each stream needs its
own IV. Don™t share.

9.13 Block Ciphers versus Stream Ciphers

Although block and stream ciphers are very different, block ciphers can be implemented as stream
ciphers and stream ciphers can be implemented as block ciphers. The best definition of the difference
I™ve found is from Rainer Rueppel [1362]:

Block ciphers operate on data with a fixed transformation on large blocks of plaintext
data; stream ciphers operate with a time-varying transformation on individual plaintext
digits.




Figure 9.16 Interleaving three CFB encryptions.

In the real world, block ciphers seem to be more general (i.e., they can be used in any of the four
modes) and stream ciphers seem to be easier to analyze mathematically. There is a large body of
theoretical work on the analysis and design of stream ciphers”most of it done in Europe, for some
reason. They have been used by the world™s militaries since the invention of electronics. This seems to
be changing; recently a whole slew of theoretical papers have been written on block cipher design.
Maybe soon there will be a theory of block cipher design as rich as our current theory of stream
cipher design.

Otherwise, the differences between stream ciphers and block ciphers are in the implementation.
Stream ciphers that only encrypt and decrypt data one bit at a time are not really suitable for
software implementation. Block ciphers can be easier to implement in software, because they often
avoid time-consuming bit manipulations and they operate on data in computer-sized blocks. On the
other hand, stream ciphers can be more suitable for hardware implementation because they can be
implemented very efficiently in silicon.

These are important considerations. It makes sense for a hardware encryption device on a digital
communications channel to encrypt the individual bits as they go by. This is what the device sees. On
the other hand, it makes no sense for a software encryption device to encrypt each individual bit



Page 180 of 666
Applied Cryptography: Second Edition - Bruce Schneier



separately. There are some specific instances where bit- and byte-wise encryption might be necessary
in a computer system”encrypting the link between the keyboard and the CPU, for example”but
generally the encryption block should be at least the width of the data bus.


Chapter 10
Using Algorithms
Think of security”data security, communications security, information security, whatever”as a
chain. The security of the entire system is only as strong as the weakest link. Everything has to be
secure: cryptographic algorithms, protocols, key management, and more. If your algorithms are great
but your random-number generator stinks, any smart cryptanalyst is going to attack your system
through the random-number generation. If you patch that hole but forget to securely erase a memory
location that contains the key, a cryptanalyst will break your system via that route. If you do
everything right and accidentally e-mail a copy of your secure files to The Wall Street Journal, you
might as well not have bothered.

It™s not fair. As the designer of a secure system, you have to think of every possible means of attack
and protect against them all, but a cryptanalyst only has to find one hole in your security and exploit
it.

Cryptography is only a part of security, and often a very small part. It is the mathematics of making a
system secure, which is different from actually making a system secure. Cryptography has its “size
queens”: people who spend so much time arguing about how long a key should be that they forget
about everything else. If the secret police want to know what is on your computer, it is far easier for
them to break into your house and install a camera that can record what is on your computer screen
than it is for them to cryptanalze your hard drive.

Additionally, the traditional view of computer cryptography as “spy versus spy” technology is
becoming increasingly inappropriate. Over 99 percent of the cryptography used in the world is not
protecting military secrets; it™s in applications such as bank cards, pay-TV, road tolls, office building
and computer access tokens, lottery terminals, and prepayment electricity meters [43,44]. In these
applications, the role of cryptography is to make petty crime slightly more difficult; the paradigm of
the well-funded adversary with a rabbit warren of cryptanalysts and roomsful of computers just
doesn™t apply.

Most of those applications have used lousy cryptography, but successful attacks against them had
nothing to do with cryptanalysis. They involved crooked employees, clever sting operations, stupid
implementations, integration blunders, and random idiocies. (I strongly recommend Ross Anderson™s
paper, “Why Cryptosytems Fail” [44]; it should be required reading for anyone involved in this field.)
Even the NSA has admitted that most security failures in its area of interest are due to failures in
implementation, and not failures in algorithms or protocols [1119]. In these instances it didn™t matter
how good the cryptography was; the successful attacks bypassed it completely.

10.1 Choosing an Algorithm

When it comes to evaluating and choosing algorithms, people have several alternatives:

” They can choose a published algorithm, based on the belief that a published algorithm
has been scrutinized by many cryptographers; if no one has broken the algorithm yet, then it
must be pretty good.
” They can trust a manufacturer, based on the belief that a well-known manufacturer



Page 181 of 666
Applied Cryptography: Second Edition - Bruce Schneier



has a reputation to uphold and is unlikely to risk that reputation by selling equipment or
programs with inferior algorithms.
” They can trust a private consultant, based on the belief that an impartial consultant is
best equipped to make a reliable evaluation of different algorithms.
” They can trust the government, based on the belief that the government is trustworthy
and wouldn™t steer its citizens wrong.
” They can write their own algorithms, based on the belief that their cryptographic
ability is second-to-none and that they should trust nobody but themselves.

Any of these alternatives is problematic, but the first seems to be the most sensible. Putting your trust
in a single manufacturer, consultant, or government is asking for trouble. Most people who call
themselves security consultants (even those from big-name firms) usually don™t know anything about
encryption. Most security product manufacturers are no better. The NSA has some of the world™s best
cryptographers working for it, but they™re not telling all they know. They have their own interests to
further which are not congruent with those of their citizens. And even if you™re a genius, writing your
own algorithm and then using it without any peer review is just plain foolish.

The algorithms in this book are public. Most have appeared in the open literature and many have
been cryptanalyzed by experts in the field. I list all published results, both positive and negative. I
don™t have access to the cryptanalysis done by any of the myriad military security organizations in the
world (which are probably better than the academic institutions”they™ve been doing it longer and
are better funded), so it is possible that these algorithms are easier to break than it appears. Even so,
it is far more likely that they are more secure than an algorithm designed and implemented in secret
in some corporate basement.

The hole in all this reasoning is that we don™t know the abilities of the various military cryptanalysis
organizations.

What algorithms can the NSA break? For the majority of us, there™s really no way of knowing. If you
are arrested with a DES-encrypted computer hard drive, the FBI is unlikely to introduce the
decrypted plaintext at your trial; the fact that they can break an algorithm is often a bigger secret
than any information that is recovered. During WWII, the Allies were forbidden from using
decrypted German Ultra traffic unless they could have plausibly gotten the information elsewhere.
The only way to get the NSA to admit to the ability to break a given algorithm is to encrypt something
so valuable that its public dissemination is worth the admission. Or, better yet, create a really funny
joke and send it via encrypted e-mail to shady characters in shadowy countries. NSA employees are
people, too; I doubt even they can keep a good joke secret.

A good working assumption is that the NSA can read any message that it chooses, but that it cannot
read all messages that it chooses. The NSA is limited by resources, and has to pick and choose among
its various targets. Another good assumption is that they prefer breaking knuckles to breaking codes;
this preference is so strong that they will only resort to breaking codes when they wish to preserve the
secret that they have read the message.

In any case, the best most of us can do is to choose among public algorithms that have withstood a
reasonable amount of public scrutiny and cryptanalysis.


Algorithms for Export

Algorithms for export out of the United States must be approved by the U.S. government (actually, by
the NSA”see Section 25.1). It is widely believed that these export-approved algorithms can be broken
by the NSA. Although no one has admitted this on the record, these are some of the things the NSA is



Page 182 of 666
Applied Cryptography: Second Edition - Bruce Schneier



rumored to privately suggest to companies wishing to export their cryptographic products:

” Leak a key bit once in a while, embedded in the ciphertext.
” “Dumb down” the effective key to something in the 30-bit range. For example, while
the algorithm might accept a 100-bit key, most of those keys might be equivalent.
” Use a fixed IV, or encrypt a fixed header at the beginning of each encrypted message.
This facilitates a known-plaintext attack.
” Generate a few random bytes, encrypt them with the key, and then put both the
plaintext and the ciphertext of those random bytes at the beginning of the encrypted message.
This also facilitates a known-plaintext attack.

NSA gets a copy of the source code, but the algorithm™s details remain secret from everyone else.
Certainly no one advertises any of these deliberate weaknesses, but beware if you buy a U.S.
encryption product that has been approved for export.

10.2 Public-Key Cryptography versus Symmetric Cryptography

Which is better, public-key cryptography or symmetric cryptography? This question doesn™t make
any sense, but has been debated since public-key cryptography was invented. The debate assumes that
the two types of cryptography can be compared on an equal footing. They can™t.

Needham and Schroeder [1159] pointed out that the number and length of messages are far greater
with public-key algorithms than with symmetric algorithms. Their conclusion was that the symmetric
algorithm was more efficient than the public-key algorithm. While true, this analysis overlooks the
significant security benefits of public-key cryptography.

Whitfield Diffie writes [492,494]:

In viewing public-key cryptography as a new form of cryptosystem rather than a new
form of key management, I set the stage for criticism on grounds of both security and
performance. Opponents were quick to point out that the RSA system ran about one-
thousandth as fast as DES and required keys about ten times as large. Although it had
been obvious from the beginning that the use of public key systems could be limited to
exchanging keys for conventional [symmetric] cryptography, it was not immediately clear
that this was necessary. In this context, the proposal to build hybrid systems [879] was
hailed as a discovery in its own right.

Public-key cryptography and symmetric cryptography are different sorts of animals; they solve
different sorts of problems. Symmetric cryptography is best for encrypting data. It is orders of
magnitude faster and is not susceptible to chosen-ciphertext attacks. Public-key cryptography can do
things that symmetric cryptography can™t; it is best for key management and a myriad of protocols
discussed in Part I.

Other primitives were discussed in Part I: one-way hash functions, message authentication codes, and
so on. Table 10.1 lists different types of algorithms and their properties [804].

10.3 Encrypting Communications Channels

This is the classic Alice and Bob problem: Alice wants to send Bob a secure message. What does she
do? She encrypts the message.

In theory, this encryption can take place at any layer in the OSI (Open Systems Interconnect)




Page 183 of 666
Applied Cryptography: Second Edition - Bruce Schneier



communications model. (See the OSI security architecture standard for more information [305].) In
practice, it takes place either at the lowest layers (one and two) or at higher layers. If it takes place at
the lowest layers, it is called link-by-link encryption; everything going through a particular data link
is encrypted. If it takes place at higher layers, it is called end-to-end encryption; the data are
encrypted selectively and stay encrypted until they are decrypted by the intended final recipient. Each
approach has its own benefits and drawbacks.

Table 10.1
Classes of Algorithms
Key
Algorithm Confidentiality Authentication Integrity Management
Symmetric encryption Yes No No Yes
algorithms
Public-key encryption Yes No No Yes
algorithms
Digital signature algorithms No Yes Yes No
Key-agreement algorithms Yes Optional No Yes
One-way hash functions No No Yes No
Message authentication codes No Yes Yes No


Link-by-Link Encryption

The easiest place to add encryption is at the physical layer (see Figure 10.1). This is called link-by-link
encryption. The interfaces to the physical layer are generally standardized and it is easy to connect
hardware encryption devices at this point. These devices encrypt all data passing through them,
including data, routing information, and protocol information. They can be used on any type of
digital communication link. On the other hand, any intelligent switching or storing nodes between the
sender and the receiver need to decrypt the data stream before processing it.

This type of encryption is very effective. Because everything is encrypted, a cryptanalyst can get no
information about the structure of the information. He has no idea who is talking to whom, how long
the messages they are sending are, what times of day they communicate, and so on. This is called
traffic-flow security: the enemy is not only denied access to the information, but also access to the
knowledge of where and how much information is flowing.

Security does not depend on any traffic management techniques. Key management is also simple; only
the two endpoints of the line need a common key, and they can change their key independently from
the rest of the network.




Figure 10.1 Link encryption.


Imagine a synchronous communications line, encrypted using 1-bit CFB. After initialization, the line
can run indefinitely, recovering automatically from bit or synchronization errors. The line encrypts
whenever messages are sent from one end to the other; otherwise it just encrypts and decrypts
random data. Eve has no idea when messages are being sent and when they are not; she has no idea



Page 184 of 666
Applied Cryptography: Second Edition - Bruce Schneier



when messages begin and end. All she sees is an endless stream of random-looking bits.

If the communications line is asynchronous, the same 1-bit CFB mode can be used. The difference is
that the adversary can get information about the rate of transmission. If this information must be
concealed, make some provision for passing dummy messages during idle times.

The biggest problem with encryption at the physical layer is that each physical link in the network
needs to be encrypted: Leaving any link unencrypted jeopardizes the security of the entire network. If
the network is large, the cost may quickly become prohibitive for this kind of encryption.

Additionally, every node in the network must be protected, since it processes unencrypted data. If all
the network™s users trust one another, and all nodes are in secure locations, this may be tolerable. But
this is unlikely. Even in a single corporation, information might have to be kept secret within a
department. If the network accidentally misroutes information, anyone can read it. Table 10.2
summarizes the pros and cons of link-by-link encryption.

End-to-End Encryption

Another approach is to put encryption equipment between the network layer and the transport layer.
The encryption device must understand the data according to the protocols up to layer three and
encrypt only the transport data units, which are then recombined with the unencrypted routing
information and sent to lower layers for transmission.

This approach avoids the encryption/decryption problem at the physical layer. By providing end-to-
end encryption, the data remains encrypted until it reaches its final destination (see Figure 10.2). The
primary problem with end-to-end encryption is that the routing information for the data is not
encrypted; a good cryptanalyst can learn much from who is talking to whom, at what times and for
how long, without ever knowing the contents of those conversations. Key management is also more
difficult, since individual users must make sure they have common keys.

Table 10.2
Link-by-Link Encryption: Advantages and Disadvantages
Advantages:
Easier operation, since it can be made transparent to the user. That is, everything is encrypted
before being sent over the link.
Only one set of keys per link is required.
Provides traffic-flow security, since any routing information is encrypted.
Encryption is online.
Disadvantages:
Data is exposed in the intermediate nodes.




Figure 10.2 End-to-end encryption.

Building end-to-end encryption equipment is difficult. Each particular communications system has its
own protocols. Sometimes the interfaces between the levels are not well-defined, making the task even
more difficult.




Page 185 of 666
Applied Cryptography: Second Edition - Bruce Schneier




If encryption takes place at a high layer of the communications architecture, like the applications
layer or the presentation layer, then it can be independent of the type of communication network
used. It is still end-to-end encryption, but the encryption implementation does not have to bother
about line codes, synchronization between modems, physical interfaces, and so forth. In the early days
of electromechanical cryptography, encryption and decryption took place entirely offline; this is only
one step removed from that.

Encryption at these high layers interacts with the user software. This software is different for
different computer architectures, and so the encryption must be optimized for different computer
systems. Encryption can occur in the software itself or in specialized hardware. In the latter case, the
computer will send the data to the specialized hardware for encryption before sending it to lower
layers of the communication architecture for transmission. This process requires some intelligence
and is not suitable for dumb terminals. Additionally, there may be compatibility problems with
different types of computers.

The major disadvantage of end-to-end encryption is that it allows traffic analysis. Traffic analysis is
the analysis of encrypted messages: where they come from, where they go to, how long they are, when
they are sent, how frequent or infrequent they are, whether they coincide with outside events like
meetings, and more. A lot of good information is buried in that data, and a cryptanalyst will want to
get his hands on it. Table 10.3 presents the positive and negative aspects of end-to-end encryption.

Combining the Two

Table 10.4, primarily from [1244], compares link-by-link and end-to-end encryption. Combining the
two, while most expensive, is the most effective way of securing a network. Encryption of each
physical link makes any analysis of the routing information impossible, while end-to-end encryption
reduces the threat of unencrypted data at the various nodes in the network. Key management for the
two schemes can be completely separate: The network managers can take care of encryption at the
physical level, while the individual users have responsibility for end-to-end encryption.

Table 10.3
End-to-End Encryption: Advantages and Disadvantages
Advantages:
Higher secrecy level.
Disadvantages:
Requires a more complex key-management system.
Traffic analysis is possible, since routing information is not encrypted.
Encryption is offline.


10.4 Encrypting Data for Storage

Encrypting data for storage and later retrieval can also be thought of in the Alice and Bob model.
Alice is still sending a message to Bob, but in this case “Bob” is Alice at some future time. However,
the problem is fundamentally different.

In communications channels, messages in transit have no intrinsic value. If Bob doesn™t receive a
particular message, Alice can always resend it. This is not true for data encrypted for storage. If Alice
can™t decrypt her message, she can™t go back in time and re-encrypt it. She has lost it forever. This
means that encryption applications for data storage should have some mechanisms to prevent



Page 186 of 666
Applied Cryptography: Second Edition - Bruce Schneier



unrecoverable errors from creeping into the ciphertext.

The encryption key has the same value as the message, only it is smaller. In effect, cryptography
converts large secrets into smaller ones. Being smaller, they can be easily lost. Key management
procedures should assume that the same keys will be used again and again, and that data may sit on a
disk for years before being decrypted.

Furthermore, the keys will be around for a long time. A key used on a communications link should,
ideally, exist only for the length of the communication. A key used for data storage might be needed
for years, and hence must be stored securely for years.

Other problems particular to encrypting computer data for storage were listed in [357]:

” The data may also exist in plaintext form, either on another disk, in another computer,
or on paper. There is much more opportunity for a cryptanalyst to perform a known-plaintext
attack.
” In database applications, pieces of data may be smaller than the block size of most
algorithms. This will cause the ciphertext to be considerably larger than the plaintext.
” The speed of I/O devices demands fast encryption and decryption, and will probably
require encryption hardware. In some applications, special high-speed algorithms may be
required.
” Safe, long-term storage for keys is required.
” Key management is much more complicated, since different people need access to
different files, different portions of the same file, and so forth.


Table 10.4
Comparing Link-by-Link and End-to-End Encryption
Link-by-link encryption End-to-end encryption
Security within Hosts
Message exposed in sending host Message encrypted in sending host
Message exposed in intermediate nodes Message encrypted inintermediate nodes
Role of User
Applied by sending host Applied by sending process
Invisible to user User applies encryption
Host maintains encryption User must find algorithm
One facility for all users User selects encryption
Can be done in hardware More easily done in software
All or no messages encrypted User chooses to encrypt or not, for each message
Implementation Concerns
Requires one key per host pair Requires one key per user pair
Requires encryption hardware or software Requires encryption hardware or software at each node
at each host
Provides node authentication Provides user authentication


If the encrypted files are not structured as records and fields, such as text files, retrieval is easier: The
entire file is decrypted before use. If the encrypted files are database files, this solution is problematic.
Decrypting the entire database to access a single record is inefficient, but encrypting records



Page 187 of 666
Applied Cryptography: Second Edition - Bruce Schneier



independently might be susceptible to a block-replay kind of attack.

In addition, you must make sure the unencrypted file is erased after encryption (see Section 10.9). For
further details and insights, consult [425,569].

Dereferencing Keys

When encrypting a large hard drive, you have two options. You can encrypt all the data using a single
key. This gives a cryptanalyst a large amount of ciphertext to analyze and makes it impossible to allow
multiple users to see only parts of the drive. Or, you can encrypt each file with a different key, forcing
users to memorize a different key for each file.

The solution is to encrypt each file with a separate key, and to encrypt the keys with another key
known by the users. Each user only has to remember that one key. Different users can have different
subsets of the file-encryption keys encrypted with their key. And there can even be a master key
under which every file-encryption key is encrypted. This is even more secure because the file-
encryption keys are random and less susceptible to a dictionary attack.

Driver-Level vs. File-Level Encryption

There are two ways to encrypt a hard drive: at the file level and at the driver level. Encryption at the
file level means that every file is encrypted separately. To use a file that™s been encrypted, you must
first decrypt the file, then use it, and then re-encrypt it.

Driver-level encryption maintains a logical drive on the user™s machine that has all data on it
encrypted. If done well, this can provide security that, beyond choosing good passwords, requires
little worry on the part of the user. The driver must be considerably more complex than a simple file-
encryption program, however, because it must deal with the issues of being an installed device driver,
allocation of new sectors to files, recycling of old sectors from files, random-access read and update
requests for any data on the logical disk, and so on.

Typically, the driver prompts the user for a password before starting up. This is used to generate the
master decryption key, which may then be used to decrypt actual decryption keys used on different
data.

Providing Random Access to an Encrypted Drive

Most systems expect to be able to access individual disk sectors randomly. This adds some
complication for using many stream ciphers and block ciphers in any chaining mode. Several
solutions are possible.

Use the sector address to generate a unique IV for each sector being encrypted or decrypted. The
drawback is that each sector will always be encrypted with the same IV. Make sure this is not a
security problem.

For the master key, generate a pseudo-random block as large as one sector. (You can do this by
running an algorithm in OFB mode, for example.) To encrypt any sector, first XOR in this pseudo-
random block, then encrypt normally with a block cipher in ECB mode. This is called ECB+OFB (see
Section 15.4).

Since CBC and CFB are error-recovering modes, you can use all but the first block or two in the
sector to generate the IV for that sector. For example, the IV for sector 3001 may be the hash of the all




Page 188 of 666
Applied Cryptography: Second Edition - Bruce Schneier



but the first 128 bits of the sector™s data. After generating the IV, encrypt normally in CBC mode. To
decrypt the sector, you use the second 64-bit block of the sector as an IV, and decrypt the remainder
of the sector. Then, using the decrypted data, you regenerate the IV and decrypt the first 128 bits.

You can use a block cipher with a large enough block size that it can encrypt the whole sector at once.
Crab (see Section 14.6) is an example.

10.5 Hardware Encryption versus Software Encryption

Hardware

<<

. 8
( 29)



>>