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:

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₁ and P_r. Then, split the key into two 48-byte halves: K₁ and K_r.

P = P₁,P_r

K = K₁,K_r

Append K₁ to P₁ 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₁ to produce C₁. Finally, append C_r to C₁ to produce the ciphertext.

C_r = P_r ⊕ H(P₁,K ₁)

C₁ = P₁ ⊕ H(C_r,K_r)

C = C₁,C_r

To decrypt, simply reverse the process. Append K_r to C_r, hash and XoR with C₁ to produce P₁. Append K₁ to P₁, hash and XoR with C_r to produce P_r.

P₁ = C₁ ⊕ H(C_r,K_r)

P_r = C_r ⊕ H(P₁,K₁)

P = P₁,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₁, H₂, and H₃. Further work shows that H₁ can equal H₂, or that H₂ can equal H₃, but not both [1193]. Also, H₁, H₂, and H₃ 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₁ and K_r.

(2)  Divide the plaintext block into two halves: L₀ and R₀.

(3)  Append K₁ to L₀ and hash it. XoR the result of the hash with R₀ to produce R₁:

R₁ = R₀ ⊕ H(K₁,L₀)

(4)  Append K_r to R₁ and hash it. XOR the result of the hash with L₀ to produce L₁:

L₁ = L₀ ⊕ H(K_r,R₁)

(5)  Append K₁ to L₁ and hash it. XOR the result of the hash with R₁ to produce R₂:

R₂ = R₁ ⊕ H(K₁,L₁)

(6)  Append L₁ to R₁ 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].