Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

The simplest way to encrypt with a one-way function is to hash the previous ciphertext block concatenated with the key, then XoR the result with the current plaintext block:

*C*_{i}=*P*_{i}⊕*H*(*K,C*_{i - 1})*P*_{i}=*C*_{i}⊕*H*(*K,C*_{i - 1})

Set the block length equal to the output of the one-way hash function. This, in effect uses the one-way function as a block cipher in CFB mode. A similar construction can use the one-way function in OFB mode:

*C*_{i}=*P*_{i}⊕*S*_{i};*S*_{i}=*H*(*K,C*_{i - 1})*P*_{i}=*C*_{i}⊕*S*_{i};*S*_{i}=*H*(*K,C*_{i - 1})

The security of this scheme depends on the security of the one-way function.

*Karn*

This method, invented by Phil Karn and placed in the public domain, makes an invertible encryption algorithm out of certain one-way hash functions.

The algorithm operates on plaintext and ciphertext in 32-byte blocks. The key can be any length, although certain key lengths will be more efficient for certain one-way hash functions. For the one-way hash functions MD4 and MD5, 96-byte keys work best.

To encrypt, first split the plaintext into two 16-byte halves: *P*_{1} and *P*_{r}. Then, split the key into two 48-byte halves: *K*_{1} and *K*_{r}.

*P*=*P*_{1},*P*_{r}*K*=*K*_{1},*K*_{r}

Append *K*_{1} to *P*_{1} and hash it with a one-way hash function, then XoR the result of the hash with *P*_{r} to produce *C*_{r}, the right half of the ciphertext. Then, append *K*_{r} to *C*_{r} and hash it with the one-way hash function. XoR the result with *P*_{1} to produce *C*_{1}. Finally, append C_{r} to *C*_{1} to produce the ciphertext.

*C*_{r}=*P*_{r}⊕*H*(*P*_{1},*K*_{1})*C*_{1}=*P*_{1}⊕*H*(*C*_{r},*K*_{r})*C*=*C*_{1},*C*_{r}

To decrypt, simply reverse the process. Append *K*_{r} to *C*_{r}, hash and XoR with *C*_{1} to produce *P*_{1}. Append *K*_{1} to *P*_{1}, hash and XoR with *C*_{r} to produce *P*_{r}.

*P*_{1}=*C*_{1}⊕*H*(*C*_{r},*K*_{r})*P*_{r}=*C*_{r}⊕*H*(*P*_{1},*K*_{1})*P*=*P*_{1},*P*_{r}

The overall structure of Karn is the same as many of the other block algorithms discussed in this section. It has only two rounds, because the complexity of the algorithm is embedded in the one-way hash function. And since the key is used only as the input to the hash function, it cannot be recovered even using a chosen-plaintext attack—assuming, of course, that the one-way hash function is secure.

*Luby-Rackoff*

Michael Luby and Charles Rackoff showed that Karn is not secure [992]. Consider two single-block messages: *AB* and *AC*. If a cryptanalyst knows both the plaintext and the ciphertext of the first message, and knows the first half of the plaintext of the second message, then he can easily compute the entire second message. This known-plaintext attack is useful only in certain circumstances, but it is a major security problem.

A three-round encryption algorithm avoids this problem [992,1643,1644]. It uses three different hash functions: *H*_{1}, *H*_{2}, and *H*_{3}. Further work shows that *H*_{1} can equal *H*_{2}, or that *H*_{2} can equal *H*_{3}, but not both [1193]. Also, *H*_{1}, *H*_{2}, and *H*_{3} cannot be based on iterating the same basic function [1643]. Anyway, assuming that *H*(*k,x*) behaves like a pseudo-random function, here is a three-round version:

**(1)**Divide the key into two halves:*K*_{1}and*K*_{r}.**(2)**Divide the plaintext block into two halves:*L*_{0}and*R*_{0}.**(3)**Append*K*_{1}to*L*_{0}and hash it. XoR the result of the hash with*R*_{0}to produce*R*_{1}:*R*_{1}=*R*_{0}⊕*H*(*K*_{1},*L*_{0})

**(4)**Append*K*_{r}to*R*_{1}and hash it. XOR the result of the hash with*L*_{0}to produce*L*_{1}:*L*_{1}=*L*_{0}⊕*H*(*K*_{r},*R*_{1})

**(5)**Append*K*_{1}to*L*_{1}and hash it. XOR the result of the hash with*R*_{1}to produce*R*_{2}:*R*_{2}=*R*_{1}⊕*H*(*K*_{1},*L*_{1})

**(6)**Append*L*_{1}to*R*_{1}to generate the message.

*Message Digest Cipher (MDC)*

MDC, invented by Peter Gutmann [676], is a means of turning one-way hash functions into a block cipher that runs in CFB mode. The cipher runs almost as fast as the hash function and is at least as secure as the hash function. The rest of this section assumes you are familiar with Chapter 18.

Hash functions such as MD5 and SHA use a 512-bit text block to transform an input value (128 bits with MD5, and 160 bits with SHA) into an output value of equal size. This transformation is not reversible, but it is perfect for CFB mode: The same operation is used for both encryption and decryption.

Let’s look at MDC with SHA. MDC has a 160-bit block size and a 512-bit key. The hash function is run “sideways,” with the old hash state as the input plaintext block (160 bits) and the 512-bit hash input as a key (see Figure 14.5). Normally, when using the hash to simply hash some input, the 512-bit input to the hash is varied as each new 512-bit block is hashed. But in this case the 512-bit input becomes an unchanging key.

MDC can be used with any one-way hash function: MD4, MD5, Snefru, and others. It is unpatented. Anyone can use it at any time, in any way, royalty-free [676].

Previous | Table of Contents | Next |