These are operations in the finite field GF(257), and 45 is a primitive element in that field. In practical implementations of SAFER K-64, it is quicker to implement this in a lookup table than to calculate new results all the time.

Then, sub-blocks are either XORed or added with bytes of subkey K_2r. The results of this operation are fed through three layers of linear operations designed to increase the avalanche effect. Each operation is called a Pseudo-Hadamard Transform (PHT). If the inputs to a PHT are a₁ and a₂, then the outputs are:

b₁ = (2a₁ + a₂) mod 256

b₂ = (a₁ + a₂) mod 256

After r rounds, there is a final output transformation. This is the same as the first step of each round. B₁, B₄, B₅, and B₈ are XORed with the corresponding bytes of the last subkey, and B₂, B₃, B₆, and B₇ are added to the corresponding bytes of the last subkey. The result is the ciphertext.

Figure 14.4  One round of SAFER.

Decryption is the reverse process: the output transformation (with subtraction instead of addition), then r reverse rounds. The Inverse PHT (IPHT) is:

a₁ = (b₁ – b₂) mod 256

a₂ = (–b₁ + 2b₂) mod 256

Massey recommends 6 rounds, but you can increase that if you want greater security.

Generating subkeys is easy. The first subkey, K₁, is simply the user key. Subsequent subkeys are generated by the following procedure:

K_i+1 = (K₁ <<< 3i) + c_i

The symbol “<<<” is a left circular shift or a left rotation. The rotation is byte by byte, and c_i is a round constant. If c_ij is the jth byte of the ith round constant, then you can calculate all of the round constants by the formula

c_ij = 45^{45^((9i + j) mod 256) mod 257} mod 257

Generally, these values are stored in a table.

SAFER K-128

This alternate key schedule was developed by the Ministry of Home Affairs in Singapore, and then incorporated into SAFER by Massey [1010]. It uses two keys, K_a and K_b, each 64-bits long. The trick is to generate two subkey sequences in parallel, and then alternate subkeys from each sequence. This means that if you choose K_a = K_b, then the 128-bit key is compatible with the 64-bit key K_a.

Security of SAFER K-64

Massey showed that SAFER K-64 is immune to differential cryptanalysis after 8 rounds and is adequately secure against the attack after 6 rounds. After only 3 rounds linear cryptanalysis is ineffective against this algorithm [1010].

Knudsen found a weakness in the key schedule: For virtually every key, there exists at least one (and sometimes as many as nine) other key that encrypts some different plaintext to identical ciphertexts [862]. The number of different plaintexts that encrypt to identical ciphertexts after 6 rounds is anywhere from 2²² to 2²⁸. While this attack may not impact SAFER’s security when used as an encryption algorithm, it greatly reduces its security when used as a one-way hash function. In any case, Knudsen recommends at least 8 rounds.

SAFER was designed for Cylink, and Cylink is tainted by the NSA [80]. I recommend years of intense cryptanalysis before using SAFER in any form.

14.5 3-Way

3-Way is a block cipher designed by Joan Daemen [402,410]. It has a 96-bit block length and key length, and is designed to be very efficient in hardware.

3-Way is not a Feistel network, but it is an iterated block cipher. 3-Way can have n rounds; Daemen recommends 11.

Description of 3-Way

The algorithm is simple to describe. To encrypt a plaintext block, x:

For i = 0 to n – 1

x = x XOR K_i

x = theta (x)

x = pi – 1 (x)

x = gamma (x)

x = pi – 2 (x)

x = x ⊕ K_n

x = theta (x)

The functions are:

—  theta(x) is a linear substitution function—basically a bunch of circular shifts and XORs.

—  pi–1(x) and pi–2(x) are simple permutations.

—  gamma(x) is a nonlinear substitution function. This is the step that gives 3-Way its name; it is the parallel execution of the substitution step on 3-bit blocks of the input.

Decryption is similar to encryption, except that the bits of the input have to be reversed and the bits of the output have to be reversed. Code to implement 3-Way can be found in the back of this book.

So far, there has been no successful cryptanalysis of 3-Way. The algorithm is unpatented.

14.6 Crab

This algorithm was developed by Burt Kaliski and Matt Robshaw of RSA Laboratories [810]. The idea behind Crab is to use techniques from one-way hash functions to make a fast encryption algorithm. Hence, Crab is very similar to MD5, and this section assumes you are familiar with Section 18.5.

Crab has a very large block: 1024 bytes. Since Crab is presented more as a research contribution than a real algorithm, no definitive key-generation routines are presented. The authors suggest a method that could turn an 80-bit key into three requisite subkeys, although the algorithm could easily accept variable-length keys.

Crab uses two sets of large subkeys:

A permutation of the numbers 0 through 255: P₀, P₁, P₂,..., P₂₅₅.

A 2048-entry array of 32-bit numbers: S₀, S₁, S₂,..., S₂₀₄₇.