SAFER, RC5, and other block ciphers

SAFER

SAFER K-64 (Secure And Fast Encryption Routine, with 64-bit key) is an iterated block cipher with 64-bit plaintext and ciphertext blocks. It consists of r identical rounds followed by an output transformation. The original recommendation of 6 rounds was followed by a recommendation to adopt a slightly modified key schedule (yielding SAFER SK-64, which should be used rather than SAFER K-64 - see Note 7.110) and to use 8 rounds (maximum r = 10). Both key schedules expand the 64-bit external key into 2r +1 subkeys each of 64- bits (two for each round plus one for the output transformation). SAFER consists entirely of simple byte operations, aside from byte-rotations in the key schedule; it is thus suitable for processors with small word size such as chipcards (cf. FEAL).

Details of SAFER K-64 are given in Algorithm 7.108 and Figure 7.12 (see also page 280 regarding SAFER K-128 and SAFER SK-128). The XOR-addition stage beginning each round (identical to the output transformation) XORs bytes 1, 4, 5, and 8 of the (first) round subkey with the respective round input bytes, and respectively adds (mod 256) the remaining 4 subkey bytes to the others. The XOR and addition (mod 256) operations are interchanged in the subsequent addition-XOR stage. The S-boxes are an invertible byte-to-byte substitution using one fixed 8-bit bijection (see Note 7.111). A linear transformation / (the Pseudo-Hadamard Transform) used in the 3-level linear layer was specially constructed for rapid diffusion. The introduction of additive key biases in the key schedule eliminates weak keys (cf. DES, IDEA). In contrast to Feistel-like and many other ciphers, in SAFER the operations used for encryption differ from those for decryption (see Note 7.113). SAFER may be viewed as an SP network (Definition 7.79).

Algorithm 7.108 uses the following definitions (L, R denote left, right 8-bit inputs):

  • 1. f(L, R) = (2L + R. L + R). Addition here is mod 256 (also denoted by EB);
  • 2. tables S and Sjnv, and the constant table for key biases Bi[j} as per Note 7.111.
SAFER K-64 computation path (r rounds)

Figure 7.12: SAFER K-64 computation path (r rounds).

7.108 Algorithm SAFER K-64 encryption (r rounds)

INPUT: r, 6 < r < 10; 64-bit plaintext M = mi • • • m64 and key К = k - ■ kG4. OUTPUT: 64-bit ciphertext block Y = (Yi,... , Yg). (For decryption, see Note 7.113.)

  • 1. Compute 64-bit subkeys K,... , K2r+ by Algorithm 7.109 with inputs К and r.
  • 2. (.Xi,X2,X8) 4- (mi ■■■mg, m9--m 16, ... , m57---m64).
  • 3. For i from 1 to r do: (XOR-addition, S-box, addition-XOR, and 3 linear layers)
  • (a) For j = 1,4,5,8: Xj 4- Xj ® K2i-i[j].

For j = 2,3,6,7: Xj 4- Xj EB [?].

  • (b) For j = 1,4,5,8: Xj 4- 5[Xj]. For j = 2,3,6,7: Xj 4- 5inv[X,].
  • (c) For j = 1,4,5,8: Xj 4- X, EB K2ij], For j = 2,3,6,7: Xj 4- Xj ф K2i[j.
  • (d) For j = 1,3,5,7: {Xj,XJ+1) 4- f(Xj,Xj+1).
  • (e) (Y^Y*) 4- f(XuX3), {Y3,Y4)4-f{X6,X7),
  • (Y6,Ye) 4- f(X2,X4), (Y7,Y8) <- f(X6,X8).

For j from 1 to 8 do: X} 4- Yj.

  • (f) {Y,Y3) 4- f(Xi,X3), (Y3,YA)4-f(X6,X7),
  • (Y6,Ye) 4- f(X2,X4), (Y7,Y8) <- f(X6,X8).

For j from 1 to 8 do: Xj 4- Yj. (This mimics the previous step.)

4. (output transformation):

For j = 1,4,5,8: Yj 4- Xj ф K2r+Xj]. For j = 2,3,6,7: Yj 4- Xj EB I<2r+ij].

7.109 Algorithm SAFER K-64 key schedule

INPUT: 64-bit key К = k4 ■ ■ ■ k64; number of rounds r.

OUTPUT: 64-bit subkeys h,.... K2r+. K,[j is byte j of K, (numbered left to right).

  • 1. Let Д[г] denote an 8-bit data store and let Bt [j] denote byte j of B, (Note 7.111).
  • 2. (Д[1], Д[2],... , Д[8]) 4— (ki ■ ■ ■ kg, k9 ■ ■ ■ кщ, ... , kG7 • • • kG4).
  • 3. (iTi[l), K[2),... , ATi[8]) 4- (Д[1], Д[2],... , Д[8]).
  • 4. For i from 2 to 2r + 1 do: (rotate key bytes left 3 bits, then add in the bias)
  • (a) For j from 1 to 8 do: R[j] 4- (Rj] <-> 3).
  • (b) For j from 1 to 8 do: K,[j] 4- R[j] ffl B, [j], (See Note 7.110.)
  • 7.110 Note (SAFER SK-64 - strengthened key schedule) An improved key schedule for Algorithm 7.108, resulting in SAFER SK-64, involves three changes as follows, (i) After initializing the Д[г] in step 1 of Algorithm 7.109, set Д[9] 4- Д[1]фД[2]ф • • • фД[8]. (ii) Change the upper bound on the loop index in step 4a from 8 to 9. (iii) Replace the iterated line in step 4b by: K,[j] 4- R[((i + j - 2) mod 9) + 1] EB B,[j]. Thus, key bytes 1,... ,8 of Д [•] are used for К4, bytes 2,... ,9 for K2 bytes 3,... 9.1 for Kg, etc. Here and originally, EB denotes addition mod 256. No attack against SAFER SK-64 better than exhaustive key search is known.
  • 7.111 Note (S-boxes and key biases in SAFER) The S-box, inverse S-box, and key biases for Algorithm 7.108 are constant tables as follows, д 4- 45. S[0] 4- 1, 5;пу[1] 4- 0. for i from 1 to 255 do: t 4— д ■ 5[г — 1] mod 257, 5[г] 4— t, 5jnv[f] 4- i. Finally, 5(128] 4— 0, 5jnv[0] 4- 128. (Since д generates Щ57, 5[г] is a bijection on {0.1,... , 255}. (Note that gi28 = 256 (mod 257), and associating 256 with 0 makes 5 a mapping with 8-bit input and output.) The additive key biases are 8-bit constants used in the key schedule (Algorithm 7.109), intended to behave as random numbers, and defined B, [j] = 5[5[9г + j]] for i from 2 to 2r+1 and j from 1 to 8. For example: B2 = (22,115,59,30,142,112,189.134) and Biz = (143,41,221,4.128,222,231,49).
  • 7.112 Remark (S-box mapping) The S-box of Note 7.111 is based on the function S(x) = gx mod 257 using a primitive element g = 45 € Z257. This mapping is nonlinear with respect to both Z257 arithmetic and the vector space of 8-tuples over F2 under the XOR operation. The inverse S-box is based on the base-/-/ logarithm function.
  • 7.113 Note (SAFER K-64 decryption) For decryption of Algorithm 7.108, the same key К and subkeys K, are used as for encryption. Each encryption step is undone in reverse order, from last to first. Begin with an input transformation (XOR-subtraction stage) with key К2r+1 to undo the output transformation, replacing modular addition with subtraction. Follow with r decryption rounds using keys K2r through K (two-per-round), inverting each round in turn. Each starts with a 3-stage inverse linear layer using fm(L, R) = (L - R. 2R - L), with subtraction here mod 256, in a 3-step sequence defined as follows (to invert the byte-permutations between encryption stages):

Level 1 (for j = 1.3,5,7): (Xj, Xj+i) <- fimiXj, Xj+i).

Levels 2 and 3 (each): (У), Y2) <— fmw{X,Xs), (У3, У) <— fmv(X2, Xa),

(Ys, У;) <— Im(X,. X7), (У7, У8) <— /inv(^4, X$) for j from 1 to 8 do: Xj <— Yj.

A subtraction-XOR stage follows (replace modular addition with subtraction), then an inverse substitution stage (exchange S and S-1), and an XOR-subtraction stage.

  • 7.114 Example (SAFER test vectors) Using 6-round SAFER K-64 (Algorithm 7.108) on the 64- bit plaintext M = (1,2,3,4,5,6,7,8) with the key К = (8,7,6,5,4,3,2,1) results in the ciphertext C = (200,242,156,221,135,120,62,217), written as 8 bytes in decimal. Using 6-round SAFER SK-64 (Note 7.110) on the plaintext M above with the key К =
  • (1,2,3,4,5,6,7,8) results in the ciphertext C = (95,206,155,162,5,132,56,199). □
 
Source
< Prev   CONTENTS   Source   Next >