Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

### 14.11 Using one-Way Hash Functions

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:

Ci = PiH(K,Ci - 1)
Pi = CiH(K,Ci - 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:

Ci = PiSi; Si = H(K,Ci - 1)
Pi = CiSi; Si = H(K,Ci - 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: P1 and Pr. Then, split the key into two 48-byte halves: K1 and Kr.

P = P1,Pr
K = K1,Kr

Append K1 to P1 and hash it with a one-way hash function, then XoR the result of the hash with Pr to produce Cr, the right half of the ciphertext. Then, append Kr to Cr and hash it with the one-way hash function. XoR the result with P1 to produce C1. Finally, append Cr to C1 to produce the ciphertext.

Cr = PrH(P1,K 1)
C1 = P1H(Cr,Kr)
C = C1,Cr

To decrypt, simply reverse the process. Append Kr to Cr, hash and XoR with C1 to produce P1. Append K1 to P1, hash and XoR with Cr to produce Pr.

P1 = C1H(Cr,Kr)
Pr = CrH(P1,K1)
P = P1,Pr

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: H1, H2, and H3. Further work shows that H1 can equal H2, or that H2 can equal H3, but not both [1193]. Also, H1, H2, and H3 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: K1 and Kr.
(2)  Divide the plaintext block into two halves: L0 and R0.
(3)  Append K1 to L0 and hash it. XoR the result of the hash with R0 to produce R1:
R1 = R0H(K1,L0)
(4)  Append Kr to R1 and hash it. XOR the result of the hash with L0 to produce L1:
L1 = L0H(Kr,R1)
(5)  Append K1 to L1 and hash it. XOR the result of the hash with R1 to produce R2:
R2 = R1H(K1,L1)
(6)  Append L1 to R1 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].

[an error occurred while processing this directive]