Table of Contents:

Other stream ciphers

While the LFSR-based stream ciphers discussed in §6.3 are well-suited to hardware implementation, they are not especially amenable to software implementation. This has led to several recent proposals for stream ciphers designed particularly for fast software implementation. Most of these proposals are either proprietary, or are relatively new and have not received sufficient scrutiny from the cryptographic community; for this reason, they are not presented in this section, and instead only mentioned in the chapter notes on page 222.

Two promising stream ciphers specifically designed for fast software implementation are SEAL and RC4. SEAL is presented in §6.4.1. RC4 is used in commercial products, and has a variable key-size, but it remains proprietary and is not presented here. Two other widely used stream ciphers not based on LFSRs are the Output Feedback (OFB; see §7.2.2(iv)) and Cipher Feedback (CFB; see §7.2.2(iii)) modes of block ciphers. Another class of keystream generators not based on LFSRs are those whose security relies on the intractability of an underlying number-theoretic problem; these generators are much slower than those based on LFSRs and are discussed in §5.5.


SEAL (Software-optimized Encryption Algorithm) is a binary additive stream cipher (see Definition 6.4) that was proposed in 1993. Since it is relatively new, it has not yet received much scrutiny from the cryptographic community. However, it is presented here because it is one of the few stream ciphers that was specifically designed for efficient software implementation and, in particular, for 32-bit processors.

SEAL is a length-increasing pseudorandom function which maps a 32-bit sequence number n to an I,-bit keystream under control of a 160-bit secret key a. In the preprocessing stage (step 1 of Algorithm 6.68), the key is stretched into larger tables using the table- generation function G„ specified in Algorithm 6.67; this function is based on the Secure Hash Algorithm SHA-1 (Algorithm 9.53). Subsequent to this preprocessing, keystream generation requires about 5 machine instructions per byte, and is an order of magnitude faster than DES (Algorithm 7.82).

The following notation is used in SEAL for 32-bit quantities А, В, C, D, Xt, and Yf

  • A: bitwise complement of A
  • А Л В, A V B, A®B: bitwise AND, inclusive-OR, exclusive-OR
  • • “A <-> s”: 32-bit result of rotating A left through s positions
  • • “A <-» s”: 32-bit result of rotating A right through s positions
  • • A + B: mod 232 sum of the unsigned integers A and В

. f(B,C,D) d= (BaC)v(BaD); g{B, C, D) d= (ВАС) V(BaD) V(CaD); h(B, C, D) d= B®C®D

  • AB: concatenation of A and В
  • • (Xi,... , Xj)(Yi, ... , Yj) simultaneous assignments (A'j'i-Y',), where (Yi,... , Yj) is evaluated prior to any assignments.
  • 6.65 Note (SEAL 1.0 vs. SEAL 2.0) The table-generation function (Algorithm 6.67) for the first version of SEAL (SEAL 1.0) was based on the Secure Hash Algorithm (SHA). SEAL 2.0 differs from SEAL 1.0 in that the table-generation function for the former is based on the modified Secure Hash Algorithm SHA-1 (Algorithm 9.53).
  • 6.66 Note (tobies) The table generation (step 1 of Algorithm 6.68) uses the compression function of SHA-1 to expand the secret key a into larger tables T, 5, and R. These tables can be precomputed, but only after the secret key a has been established. Tables T and S are 2K bytes and IK byte in size, respectively. The size of table R depends on the desired bitlength L of the keystream — each IK byte of keystream requires 16 bytes of R.

6.67 Algorithm Table-generation function for SEAL 2.0


INPUT: a 160-bit string a and an integer i, 0 < г < 232.

OUTPUT: a 160-bit string, denoted Ga(i).

  • 1. Definition of constants. Define four 32-bit constants (in hex): y = 0x5a827999, У2 = 0x6ed9ebal, уз = 0x8flbbcdc, y4 = 0xca62cld6.
  • 2. Table-generation function.

Unitialize 80 32-bit words X0, X,... , X79)

Set X0 <- i. For j from 1 to 15 do: Xj<- 0x00000000.

For j from 16 to 79 do: Xj <— ((Xj_3ф Xj_g0Xj_ 4 4фXj 10) **—> 1).

Unitialize working variables)

Break up the 160-bit string a into five 32-bit words: a = H0H1H2H3H4. (A.B.C,D,E) (Яо,ЯьЯ234).

  • (execute four rounds of 20 steps, then update; t is a temporary variable)
  • (Round 1) For j from 0 to 19 do the following: t ((A 5) + f(B, C, D) + E + Xj + ?/i),
  • (А, В, С, E), E) i(t, A, В i5 30, C, D).
  • (Round 2) For j from 20 to 39 do the following: t i— ((A -t—’ 5) + h(B, C, D) + E + Xj + 3/2).
  • (A. В. C, D, E) — ('t, A, В i5 30, G, L)).
  • (Round 5) For j from 40 to 59 do the following: t <— ((Л p5) + д{В, C. D) + E + Xj + y$),
  • (A, В, G, D, E) — (t, A, В i5 30, G, D).
  • (Round 4) For j from 60 to 79 do the folio whig: t i— ((.A ’ 5) + h(B, C, D) + E + Xj + 3/4),
  • (A, В, G, E), E) i— (f, A, В i5 30, С, E)).
  • (update chaining values)
  • (tfo, HX.H2, Я3, Я4) <- (Но + A.Hi + В, H2 + С,Н3 + D, Я4 + Е).
  • (completion) The value of Ga(i) is the 160-bit string Яо||Я1||Я2||Яз||Я4.
  • 6.68 Algorithm Keystream generator for SEAL 2.0


INPUT: a 160-bit string a (the secret key), a (non-secret) integer n, 0 < n < 232 (the sequence number), and the desired bitlength L of the keystream.

OUTPUT: keystream у of bitlength L', where L' is the least multiple of 128 which is > L.

  • 1. Table generation. Generate the tables T, S, and R, whose entries are 32-bit words. The function F used below is defined by Fa(i) = Щтойъ, where Я(,Я[ Н!2Н!ЛН = GQ(Li/5j), and where the function Ga is defined in Algorithm 6.67.
  • 1.1 For i from 0 to 511 do the following: T[i]^Fa(i).
  • 1.2 For j from 0 to 255 do the following: F„ (0x00001000 + j).
  • 1.3 For к from 0 to 4 • (L - 1)/8192] - 1 do: (0x00002000 + k).
  • 2. Initialization procedure. The following is a description of the subroutine Initialize^, /, А. В. C, D,n, n2, П3, n4) which takes as input a 32-bit word n and an integer l, and outputs eight 32-bit words А, В, C, D, n, n2, П3, and n4. This subroutine is used in step 4.

Ai—пфЯ[4/], Bt(n <—^ 8)фЯ[4/ + l], Ci(n <—^ 16)фЯ[4/ -I- 2],

D^(n <-> 24)фЯ[4/ + 3].

For j from 1 to 2 do the following:

P<—AA0x000007fc, B^B + T[P/4], A<-(A -4 9),

P^PA0x000007fc, C^C + T[P/4], P<-(P-4 9),

P<—C7x000007fc, P<^P + TPj4], C<-(C -4 9),

P^PA0x000007fc, Л^Л + T[P/4], P<^(P -4 9).

(ni, П2, n3, n4)<-(P, P. Л, C).

Pt-AA0x000007fc, P<^P + T[P/4], A

P'S—PA0x000007fc, C'S—C + T[P/4], P<-(P -4 9).

P'S—CA0x000007fc, P<^P + T[P/4], C4-(C -4 9).

P'S—PA0x000007fc, Л^Л + T[P/4], D<-(D -4 9).

  • 3. Initialize у to be the empty string, and U—0.
  • 4. Repeat the following:
  • 4Л Execute the procedure Initialize(n, l, А, В, C, D, ni,712,713,714).
  • 4.2 For i from 1 to 64 do the folio whig:

Р^ЛА 0x000007fc, P-s—P + P[P/4], А<-(Л <^4 9), Р^РфЛ,

Qi—PA0x000007fc, CiC®T[Q/4], B<—(P <—^ 9), C-i—C -|- P,

P<-(P + C)A0x000007fc, P-s-P + P[P/4], C<-(C -4 9), Р^РфР,

Qi—(Q + P)A0x000007fc, Л^—ЛфР[С^/4], P^—(P 1^ 9), Ai—Л -{- P, P-S-(P + Л)Л0х000007^, P'S—РфР[Р/4], ЛЦЛ4 9),

P)A0x000007fc, P-s—C ~~ P[Q/4], P-s—(P <—^ 9),

P-s-(P + C)A0x000007fc, P-s—РфТ[Р/4], С<н(С -4 9),

Q<-(Q + P)A0x000007fc, Л<-Л + T[<5/4], Ps-(P^9),

y<-y || (P + S[4i - 4]) || (Сф5[4г - 3]) || (P + S[4i - 2]) || (A©S[4i - 1]).

If у is > L bits in length then retum(y) and stop.

If г is odd, set (Л, C)'*—(Л+rii, Р-Игг). Otherwise, (Л, C)t- (A+n3, C+n4).

4.3 Set Ы—l -b 1.

The table S consists of words S[0], S[l],... , S[255]:

907cle3d ce71ef0a 48f559ef 2b7ab8bc 4557f4b8 033e9b05 4fdeOefa Ia845f94 38512c3b d4b44591 53765dce 469efa02

bd7dea87 fd036d87 53aa3013 ec60e282 Ieaef8f9 0b5a0949

The output у of Algorithm 6.68 consists of 1024 words ?/[()]. y[l],... , у[1023]:

  • 37a00595 9b84c49c a4bele05 0673530f 0ac8389d c5878ec8 da6666d0 6da71328 1419bdf2 d258bebb b6a42a4d 8a311a72
  • 547dfde9 668d50b5 ba9e2567 413403c5 43120b5a ecf9d062

The XOR of the 1024 words of у is 0x098045fc. □

< Prev   CONTENTS   Source   Next >