ńňđ. 1 |

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 16 ................................................ 368

Pseudo-Random- Sequence Generators . 368

LINEAR CONGRUENTIAL GENERATO ... 368

Table 16.1 Constants for Linear .................... 369

Combining Linear Congruential Generators ... 370

LINEAR FEEDBACK SHIFT REGISTER .. 371

Figure 16.1 Feedback shift register. ............... 372

Figure 16.2 Linear feedback shift register. ..... 373

Figure 16.3 4-bit LFSR. .................................. 373

Figure 16.4 32-bit long maximal-length .......... 374

Table 16.2 Some Primitive Polynomials Mod 375

Table 16.2 (Cont.) Some Primitive ................ 376

LFSRs in Software ......................................... 377

DESIGN AND ANALYSIS OF STREAM .... 378

Linear Complexity .......................................... 379

Correlation Immunity ..................................... 379

Other Attacks ................................................. 380

CIPHERS USING ..................................... 380

Geffe Generator ............................................ 381

Generalized Geffe Generator ........................ 381

Figure 16.6 Geffe generator. .......................... 381

Jennings Generator ....................................... 382

Beth-Piper Stop-and-Go Generator ............... 382

Alterna ting Stop-and-Go Generator ............. 382

Figure 16.7 Generalized Geffe generator. ...... 382

Figure 16.8 Jennings generator. .................... 383

Bilateral Stop-and-Go Generator ................... 383

Threshold Generator ..................................... 383

Figure 16.10 Alternating stop-and-go ............. 384

Self-Decimated Generators ........................... 384

Figure 16.11 Bilateral stop-and-go ................. 384

Figure 16.12 Threshold generator. ................. 385

Multispeed InnerProduct Generator .............. 385

Summation Genera for .................................. 385

Figure 16.13 Rueppels self-decimated .......... 385

Figure 16.14 Chamberss and Gollmanns ..... 386

DNRSG ......................................................... 386

Gollmann Cascade ........................................ 386

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Figure 16.15 Multispeed inner-product ........... 386

CHAPTER ..................................................... 387

Shrinking Generator ...................................... 387

Self-Shrinking Generator ............................... 387

Figure 16.16 Gollmann cascade. ................... 387

HUGHES XPD /KPD ................................. 388

NANOTEQ ................................................ 389

RAMBUTAN .............................................. 389

ADDITIVE GENERATORS ....................... 389

Fish ................................................................ 390

Pike ............................................................... 390

Mush .............................................................. 391

GIFFORD ................................................. 391

Figure 16.17 Gifford. ...................................... 392

ALGORITHM ............................................ 392

Security PKZlP .............................................. 394

Page 368

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16

CHAPTER

Pseudo-Random-

Sequence Generators

and Stream Ciphers

16.1 LINEAR CONGRUENTIAL GENERATORS

Linear congruential generators are pseudo-random-sequence generators of the form

X,=(aX,,-l+b)modm

in which X,, is the nth number of the sequence, and X, _ i is the previous number of

the sequence. The variables a, b, and m are constants: a is the multiplier, b is the

increment, and m is the modulus. The key, or seed, is the value of X0.

This generator has a period no greater than m. If a, b, and m are properly chosen,

then the generator will be a maximal period generator (sometimes called maximal

length) and have period of m. (For example, b should be relatively prime to m.)

Details on choosing constants to ensure maximal period can be found in [863,942].

Another good article on linear congruential generators and their theory is [ 14461.

Table 16.1, taken from [ 12721,gives a list of good constants for linear congruential

generators. They all produce maximal period generators and even more important,

pass the spectral test for randomness for dimensions 2,3,4, 5, and 6 [385,863]. They

are organized by the largest product that does not overflow a specific word length.

The advantage of linear congruential generators is that they are fast, requiring few

operations per bit.

Unfortunately, linear congruential generators cannot be used for cryptography;

they are predictable. Linear congruential generators were first broken by Jim Reeds

[ 1294,1295,1296] and then by Joan Boyar [ 125 11.She also broke quadratic generators:

Xn=(aXn-i2+bX,-,+c)modm

and cubic generators:

Xn=(aX,-i3+bX,-i2+cX,-i+d)modm

Other researchers extended Boyarâ€™s work to break any polynomial congruential

generator [923,899,900]. Truncated linear congruential generators were also broken

Page 369

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16 Pseudo-Random-Sequence Generators

CHAPTER

Table 16.1

Constants for Linear Congruential Generators

m

b

a

Overflow At:

6075

220 106 1283

7875

221 211 1663

1663 7875

222 421

11979

2531

430

223

6655

1399

936

6075

1283

1366

11213 53125

171

224

2531 11979

859

29282

6173

419

3041 14406

967

134456

225 28411

141

31104

6571

625

14000

1541 2957

12960

2731

1741

21870

4621

1291

139968

205 29573

226 17117 81000

421

29282

6173

1255

28411 134456

281

86436

227 18257

1093

259200

421 54773

116640

1021 2463 1

1021 25673 121500

117128

228 24749

1277

312500

66037

741

121500

2041 25673

120050

2311 25367

229

214326

45289

1807

244944

51749

1597

233280

1861 49297

175000

2661 36979

25673 121500

4081

30809 145800

3661

139968

3877 29573

230

214326

45289

3613

714025

1366 150889

23â€™ 134456

8121 28411

243000

4561 51349

259200

7141 54773

233280

9301 49297

232

150889 714025

4096

374441 1771875

2416

233

510300

17221 107839

234

312500

36261 66037

217728

84589 45989

235

Page 370

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

[581,705,580], as were truncated linear congruential generators with unknown

parameters [1500,212]. The preponderance of evidence is that congruential genera-

tors arenâ€™t useful for cryptography.

Linear congruential generators remain useful for noncryptographic applications,

however, such as simulations. They are efficient and show good statistical behavior

with respect to most reasonable empirical tests. Considerable information on linear

congruential generators and their implementations can be found in [942].

Combining Linear Congruential Generators

Various people examined the combination of linear congruential generators

[1595,941]. The results are no more cryptographically secure, but the combinations

have longer periods and perform better in some randomness tests.

Use this generator for 32-bit computers [941]:

= 1 ; /* A "long" must be 32 bits long. */ static long s2 = 1 ;

static long sl

#define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if (s<O) s+=m ;

/* MODMlJLT(a,b,c,m,s) computes s*b mod m, provided that m=a*b+c and 0 <= c <

m. *I

/* combinedLCG returns a pseudorandom real value in the range

* (0,l). It combines linear congruential generators with

* periods of 231-85 and 231-249, and has a period that is the

* product of these two prime numbers. */

double combinedLCG ( void )

long 4 ;

long z;

MODMULT ( 53668, 40014, 12211, 2147483563L, sl )

MODMULT ( 52774, 40692, 3791, 2147483399L, s2 )

z = sl - s2 ;

if (z <l)

z += 2147483562 ;

return z * 4.656613e-10 ;

/* In general, call initLCG before using combinedLCG. */

void initLCG ( long InitSl, long InitS 1

i

sl = InitSl ;

s2 = InitS ;

This generator works as long as the machine can represent all integers between

-231 + 85 and 231- 85. The variables, s1 and sz, are global; they hold the current state

of the generator. Before the first call, they must be initialized. The variable s1needs

an initial value between 1 and 2147483562; the variable s2 needs an initial value

between 1 and 2147483398. The generator has a period somewhere in the neighbor-

hood of loâ€™*.

Page 371

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER16 Pseudo-Random-Sequence Generators

If you only have a 16-bit computer, use this generator instead:

static int sl = 1 ; /* An "int" must be 16 bits long. */

static int s2 = 1 ;

static int s3 = 1 :

#define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if

(s<O) s+=m :

/* combined LCG returns a pseudorandom real value in the

range

* (0,lI. It combines linear congruential generators with

* periods of 215-405, 215-1041, and 215-1111, and has a period

* that is the product of these three prime numbers. */

double combinedLCG ( void )

I

int q ;

int z ;

MODMULT ( 206, 157, 21, 32363, sl )

MODMULT ( 217, 146, 45, 31727, s2 )

MODMULT ( 222, 142, 133, 31657, s3 I

z = sl - s2 ;

if ( z > 706 )

z -= 32362 ;

2 += s3 ;

if(z<l)

z += 32362 ;

return z * 3.0899e-5 ;

I

/* In general, call initLCG before using combinedLCG. */

void initLCG ( int InitSl, int InitSP, InitS I

sl = InitSl ;

s2 = InitSP ;

s3 = InitS ;

t

This generator works as long as the machine can represent all integers between

-32363 and 32363. The variables, sl, s2,and ˜3,are global; they hold the current state

of the generator. Before the first call, they must be initialized. The variable s1 needs

an initial value between 1 and 32362. The variable s2 needs an initial value between

1 and 31726. The variable s3 needs an initial value between 1 and 31656. This gen-

erator has a period of 1.6* 1013.

For both of these generators, the constant term b in the linear congruence is 0.

16.2 SHIFTREGISTERS

LINEARFEEDBACK

Shift register sequences are used in both cryptography and coding theory. There 1s ?

wealth of theory about them; stream ciphers based on shift registers have been the

workhorse of military cryptography since the beginnings of electronics.

Page 372

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16.2 Linear Feedback Shift Registers

A feedback shift register is made up of two parts: a shift register and a feedback

function (see Figure 16.1). The shift register is a sequence of bits. (The length of a

shift register is figured in bits; if it is n bits long, it is called an n-bit shift register.)

Each time a bit is needed, all of the bits in the shift register are shifted 1 bit to the

right. The new left-most bit is computed as a function of the other bits in the regis-

ter. The output of the shift register is 1 bit, often the least significant bit. The period

of a shift register is the length of the output sequence before it starts repeating.

Cryptographers have liked stream ciphers made up of shift registers: They are

easily implemented in digital hardware. I will only touch on the mathematical the-

ory. Ernst Selmer, the Norwegian governmentâ€™s chief cryptographer, worked out

the theory of shift register sequences in 1965 [1411]. Solomon Golomb, an NSA

mathematician, wrote a book with Selmerâ€™s results and some of his own [643]. See

also [970,971,1647].

The simplest kind of feedback shift register is a linear feedback shift register, or

LFSR (see Figure 16.2). The feedback function is simply the XOR of certain bits in

the register; the list of these bits is called a tap sequence. Sometimes this is called a

Fibonacci configuration. Because of the simple feedback sequence, a large body of

mathematical theory can be applied to analyzing LFSRs. Cryptographers like to ana-

lyze sequences to convince themselves that they are random enough to be secure.

LFSRs are the most common type of shift registers used in cryptography.

Figure 16.3 is a 4-bit LFSR tapped at the first and fourth bit. If it is initialized with

the value 1111, it produces the following sequence of internal states before repeating:

1111

0111

1011

0101

1010

1101

0110

0011

1001

e b, b,-, -â€˘* c

b, 4 b, â€˜a

l

i

I I 1 I

I

Feedback Function

Figure 16.1 Feedback shift register.

Page 373

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER16 Pseudo-Random-Sequence Generators

Shift Register

Figure 16.2 Linear feedback shift register.

0100

0010

0001

1000

1100

1110

The output sequence is the string of least significant bits:

111101011001000....

An n-bit LFSR can be in one of 2â€ť - 1 internal states. This means that it can, in

theory, generate a 2â€ť - l-bit-long pseudo-random sequence before repeating. (Itâ€™s

2* - 1 and not 2â€ť because a shift register filled with zeros will cause the LFSR to out-

put a neverending stream of zeros-this is not particularly useful.) Only LFSRs with

certain tap sequences will cycle through all 2â€ť - 1 internal states; these are the

maximal-period LFSRs. The resulting output sequence is called an m-sequence.

In order for a particular LFSR to be a maximal-period LFSR, the polynomial

formed from a tap sequence plus the constant 1 must be a primitive polynomial

mod 2. The degree of the polynomial is the length of the shift register. A primitive

polynomial of degree n is an irreducible polynomial that divides x2â€ť- â€™ + 1, but not

xd + 1 for any d that divides 2â€ť - 1 (see Section 11.3). For the mathematical theory

behind all this, consult [643,1649,1648].

Figure 16.3 4-bit LFSR.

Page 374

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

In general, there is no easy way to generate primitive polynomials mod 2 for a

given degree. The easiest way is to choose a random polynomial and test whether it

is primitive. This is complicated-something like testing random numbers for pri-

mality-but many mathematical software packages do this. See [970,971] for some

methods.

Table 16.2 lists some, but by no means all, primitive polynomials mod 2 of vary-

ing degrees [1583,643,1649,1648,1272,691]. For example, the listing (32, 7, 5, 3, 2,

1, 0) means that the following polynomial is primitive modulo 2:

22+xâ€™+2+2+x2+x+ 1

Itâ€™s easy to turn this into a maximal-period LFSR. The first number is the length of

the LFSR. The last number is always 0 and can be ignored. All the numbers, except

the 0, specify the tap sequence, counting from the left of the shift register. That is,

low degree terms in the polynomial correspond to taps near the left-hand side of the

register.

To continue the example, the listing (32, 7, 5, 3, 2, 1, 0) means that if you take a

32-bit shift register and generate the new bit by XORing the thirty-second, seventh,

fifth, third, second, and first bits together (see Figure 16.4), the resultant LFSR will

be maximal length; it will cycle through 232- 1 values before repeating.

The C code for this LFSR looks like:

int LFSR 0 1

static unsigned long ShiftRegister = 1;

/* Anything but 0. */

ShiftRegister = ((((ShiftRegister >> 31)

n (ShiftRegister >> 6)

h (ShiftRegister >> 4)

n (ShiftRegister >> 2)

n (ShiftRegister >> 1)

n ShiftRegister))

& 0x00000001)

<< 31)

1 (ShiftRegister >> 1) ;

return ShiftRegister & 0x00000001;

,

Figure 16.4 32-bit long maximal-length LFSR.

Page 375

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16 Pseudo-Random-Sequence Generators

CHAPTER

Table 16.2

Some Primitive Polynomials Mod 2

(LOI (36, 11, 01 (68, 9, 01 (97, 6, 01

(2, 1,

01 (98, 11, 01

(68, 7, 5, 1, 0)

(36, 6, 5, 4, 2, 1, 01

(98, 7, 4, 3, 1, 0)

(3, 1, 01 (37, 6, 4, 1, 0) (69, 6, 5, 2, 0)

(4, 1, 0) (37, 5, 4, 3, 2, 1, 0) (70, 5, 3, 1, 01 (99, 7, 5, 4, 0)

01 (100, 37, 0)

(5, 2, (38, 6, 5, 1, 01 (71, 6, 01

(6, 1,

01 (39, 4, 0) (71, 5, 3, 1, 01 (100, 8, 7, 2, 01

(72, 10, 9, 3, 0)

(40, 5, 4, 3, 01 (101, 7, 6, 1, 0)

k kJ ii (102, 6 5 3 0)

(41, 3, 0) (72, 6, 4, 3, 2, 1, 0)

(103, 9, 9)

(8: 4: 3, 2, 01 (42, 7, 4, 3, 0) (73, 25, 01

(104, 11, 10, 1, 0)

(9, 4, 0) (42, 5, 4, 3, 2, 1, 01 (73, 4, 3, 2, 01

(105, 16, 0)

(10, 3, 0) (43, 6, 4, 3, 01 (74, 7, 4, 3, 01

01 (75, 6, 3, 1, 0) (106, 15, 0)

(11, 2, (44, 6, 5, 2, 01

(12, 6, 4, 1, 01 (45, 4, 3, 1, 0) (76, 5, 4, 2, 01 (107, 9, 7, 4, 01

(108, 31, 0)

(13, 4, 3, 1, 01 (46, 8, 7, 6, 0) (77, 6, 5, 2, 01

8, 5, 3, 2, 1, 0)

(14, 5, 3, 1, 01 (46, (78, 7, 2, 1, 01 (109, 5, 4, 2, 01

(15, 1, 01 (47, 5, 0) (79, 9, 01 (110, 6, 4, 1, 0)

(111, 10, 0)

(16, 5, 3, 2, 01 (48, 9, 7, 4, 0) (79, 4, 3, 2, 01

(111,49, 0)

(17, 3, 01 (48, 7, 5, 4, 2, 1, 0) (80, 9, 4, 2, 01

(17, 5, 01 (49, 9, 01 (80, 7, 5, 3, 2, 1, 01 (113, 9, 01

(113, 15,O)

(17, 6, 01 (49, 6, 5, 4, 01 (81, 4, 01

(113, 30, 0)

(18, 7, 01 (82, 9, 6, 4, 0)

(50, 4, 3, 2, 01

(114, 11, 2, 1, 0)

(18, 5, 2, 1, 0) (51, 6, 3, 1, 0) (82, 8, 7, 6, 1, 0)

(19, 5, 2, 1, 0) (52, 3, 01 (83, 7, 4, 2, 01 (115, 8, 7, 5, 01

(20, 3, 01 (53, 6, 2, 1, 01 (84, 13, 01 (116, 6, 5, 2, 0)

0)

(21, 2, (54, 8, 6, 3, 0) (84, 8, 7, 5, 3, 1, 0) (117, 5, 2, 1, 0)

1,01

(2% (118, 33, 0)

(85, 8, 2, 1, 01

(54, 6, 5, 4, 3, 2, 01

(23, 5, 01 (55, 24, 01 (86, 6, 5, 2, 01 (119, 8, 01

(119, 45, 0)

(24, 4, 3, 1, 01 (55, 6, 2, 1, 01 (87, 13, 0)

(25, 3, 01 (56, 7, 4, 2, 0) (87, 7, 5, 1, 01 (120, 9, 6, 2, 01

1,0)

(26, 6, 2, (121, 18, 0)

(57, 7, 0) (88, 11, 9, 8, 0)

(122, 6, 2, 1, 0)

(27, 5, 2, 1, 0) (57, 5, 3, 2, 0) (88, 8, 5, 4, 3, 1, 0)

(8% 38, 01 (123, 2, 01

(28, 3, 01 (58, 19, 01

(124, 37, 0)

(89, 51, 01

(29, 2, 0) (58, 6, 5, 1, 01

(30, 6, 4, 1, 0) (59, 7, 4, 2, 0) (89, 6, 5, 3, 0) (125, 7, 6, 5, 0)

6, 5, 4, 3, 1, 0)

(31, 3, 01 (59, (90, 5, 3, 2, 01 (126, 7, 4, 2, 0)

(60, 1, 01

(31, 6, 01 (91, 8, 5, 1, 0) (127, 1, 01

(61, 5, 2, 1, 0)

(31, 7, 01 (91, 7, 6, 5, 3, 2, 0) (127, 7, 0)

(127, 63, 0)

(31, 13,Ol (62, 6, 5, 3, 0) (92, 6, 5, 2, 01

(63, 1, 01

(32, 7, 6, 2, 0) (93, 2, 01 (128, 7, 2, 1, 0)

(32, 7, 5, 3, 2, 1, 0) (64, 4, 3, 1, 0) (94, 21, 0) (129, 5, 01

(33, 13, 0) (65, 18, 0) (94, 6, 5, 1, 01 (130,3, 01

(33, 16, 4, 1, 0) (65, 4, 3, 1, 0) (95, 11, 0) (131, 8, 3, 2, 0)

(132, 29, 0)

(34, 8, 4, 3, 0) (66, 9, 8, 6, 01 (95, 6, 5, 4, 2, 1, 01

(34, 7, 6, 5, 2, 1, 0) (66, 8, 6, 5, 3, 2, 0) (96, 10, 9, 6, 0) (133, 9, 8, 2, 01

(134, 57, 0)

(35, 2, 0) (67, 5, 2, 1, 01 (96, 7, 6, 4, 3, 2, 0)

Page 376

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16.2 Linear Feedback Shift Registers

Table 16.2 (Cont.)

Some Primitive Polynomials Mod 2

6, 3, 2, 0)

(135, 11, 0) (178, 87, 0) (270, 133, 0)

(152,

(135, 16, 0) (183, 56, 0) (282, 35, 0)

(153, 1, 0)

8, 0)

(135, 22, 0) (194, 87, 0) (282, 43, 0)

(153,

(198, 65, 0) (286, 69, 0)

(136, 8, 3, 2, 0) (154, 9, 5, 1, 01

(137, 21, 0) (201, 14, 0) (286, 73, 0)

(155, 7, 5, 4, 01

(201, 17, 0) (294, 61, 0)

(138, 8, 7, 1, 0) (156, 9, 5, 3, 0)

6, 5, 2, 0) (322, 67, 0)

(201, 59, 0)

(139, 8, 5, 3, 0) (157,

(140, 29, 0) (201, 79, 0)

(158, 8, 6, 5, 01 (333, 2, 0)

(141, 13, 6, 1, 0) (159, 31, 0) (202, 55, 0) (350, 53, 0)

(142, 21, 0) (159, 34, 0) (207, 43, 0) (366, 29, 0)

(159, 40, 0) (212, 105, 0) (378, 43, 0)

(143, 5, 3, 2, 01

(218, 11, 0) (378, 107, 0)

(144, 7, 4, 2, 01 (160, 5, 3, 2, 01

(145, 52, 0) (161, 18, 0) (218, 15, 0) (390, 89, 0)

( 145, 69, 0) (161, 39, 0) (218, 71, 0) (462, 73, 0)

(161, 60, 0) (218, 83, 0) (521, 32, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0) (225, 32, 0) (521, 48, 0)

(162, 8, 7, 4, 0)

(148, 27, 0) (521, 158, 0)

(225, 74, 0)

(163, 7, 6, 3, 01

(149, 10, 9, 7, 0) (164, 12, 6, 5, 0) (225, 88, 0) (521, 168, 0)

9, 8,3, 0)

(150, 53, 0) (225, 97, 0) (607, 105, 0)

(165,

(166, 10, 3, 2, 0) (225, 109, 0) (607, 147, 0)

(151,3, 0)

(167, 6, 0) (231, 26, 0) (607, 273, 0)

(151, 9, 0)

(151, 15,O) (170, 23, 0) (231, 34, 0) (1279, 216, 0)

(151, 31, 0) (234, 31, 0) (1279, 418, 0)

(172, 2, 0)

(151, 39, 0) (174, 13, 0) (234, 103, 0) (2281, 715, 0)

6, 0)

(151,43, 0) (2281, 915, 0)

(175, (236, 5,Ol

(151, 46, 0) (175, 16, 0) (250, 103, 0) (2281, 1029, 0)

(151, 51, 0) (175, 18, 0) (255, 52, 0) (3217, 67, 0)

(151, 63, 0) (175, 57,O) (255, 56, 0) (3217, 576, 0)

(151,66,0) (255, 82, 0) (4423, 271, 0)

(177, 8, 0)

(151, 67, 0) (177, 22, 0) (258, 83, 0) (9689, 84, 0)

(151, 70,O) (177, 88,O) (266, 47, 0)

The code is a little more complicated when the shift register is longer than the com-

puterâ€™s word size, but not significantly so.

Note that all of these listings have an odd number of coefficients. I have provided

such a large table because LFSRs are often used for stream-cipher cryptography and

I wanted many examples so that different people would pick different primitive

polynomials. Since, if p(x) is primitive, then so is xâ€™$( l/x); each entry on the table is

actually two primitive polynomials.

For example, if (a, b, 0) is primitive, then (a, a - b, 0) is also primitive. If (a, b, c,

d, 0) is primitive, then (a, a - d, a - c, a - b, 0) is also primitive. Mathematically:

if xâ€ť + xb + 1 is primitive, so is xâ€ť + Xa- b + 1

ifxâ€ť+xb+XC+Xd+1isprimitive,soisxQ+xâ€ť-d+xâ€ť-â€ť+xâ€ť-b+1

Page 377

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER16 Pseudo-Random-Sequence Generators

Primitive trinomials are fastest in software, because only two bits of the shift reg-

ister have to be XORed to generate each new bit. Actually, all the feedback polyno-

mials listed in Table 16.2 are sparse, meaning that they only have a few coefficients.

Sparseness is always a source of weakness, sometimes enough to break the algo-

rithm. It is far better to use dense primitive polynomials, those with a lot of coeffi-

cients, for cryptographic applications. If you use dense polynomials, and especially

if you make them part of the key, you can live with much shorter LFSRs.

Generating dense primitive polynomials modulo 2 is not easy. In general, to gen-

erate primitive polynomials of degree k you need to know the factorization of 2k - 1.

Three good references for finding primitive polynomials are [652,1285,1287].

LFSRs are competent pseudo-random-sequence generators all by themselves, but

they have some annoying nonrandom properties. Sequential bits are linear, which

makes them useless for encryption. For an LFSR of length n, the internal state is the

next n output bits of the generator. Even if the feedback scheme is unknown, it can

be determined from only 2n output bits of the generator, by using the highly effi-

cient Berlekamp-Massey algorithm [ 1082,1083]: see Section 16.3.

Also, large random numbers generated from sequential bits of this sequence are

highly correlated and, for certain types of applications, not very random at all. Even

so, LFSRs are often used as building blocks in encryption algorithms.

LFSRs in Software

LFSRs are slow in software, but theyâ€™re faster in assembly language than in C. One

solution is to run 16 LFSRs (or 32, depending on your computerâ€™s word size) in paral-

lel. This scheme uses an array of words that is the length of the LFSR, with each bit

position in the words representing a different LFSR. Assuming all the feedback poly-

nomials are the same, this can run pretty quickly. In general, the best way to update

shift registers is to multiply the current state by suitable binary matrices [901].

It is also possible to modify the LFSRâ€™s feedback scheme. The resultant generator

is no better cryptographically, but it still has a maximal period and is easy to imple-

ment in software [ 12721.Instead of using the bits in the tap sequence to generate the

new left-most bit, each bit in the tap sequence is XORed with the output of the gen-

erator and replaced; then the output of the generator becomes the new left-most bit

(see Figure 16.5). This is sometimes called a Galois configuration.

In C, this looks like:

#define mask Ox80000057

static unsigned long ShiftRegister=l;

void seed_LFSR (unsigned long seed)

if (seed == 0) /* avoid calamity */

seed = 1;

ShiftRegister = seed;

1

int modified_LFSR (void)

Page 378

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16.3 Design and Analysis of Stream Ciphers

Figure 16.5 Galois LFSR.

if (ShiftRegister & 0x00000001) (

ShiftRegister = ((ShiftRegister n mask >> 1) )

0x8000000;

return 1;

I else (

ShiftRegister >>= 1;

return 0;

The savings here is that all the XORs can be done as a single operation. This can

also be parallelized, and the different feedback polynomials can be different. The

Galois configuration can also be faster in hardware, especially in custom VLSI imple-

mentations. In general, if you are using hardware that is good at shifts, use a Fibonacci

configuration; if you can exploit parallelism, use a Galois configuration.

16.3 DESIGN AND ANALYSIS OF STREAM CIPHERS

Most practical stream-cipher designs center around LFSRs. In the early days of elec-

tronics, they were very easy to build. A shift register is nothing more than an array

of bit memories and the feedback sequence is just a series of XOR gates. Even in

VLSI circuitry, a LFSR-based stream cipher can give you a lot of security with only

a few logic gates.

The problem with LFSRs is that they are very inefficient in software. You want to

avoid sparse feedback polynomials-they facilitate correlation attacks [ 105 1,1090,

350]-and dense feedback polynomials are inefficient. Any stream cipher outputs a

bit at a time; you have to iterate the algorithm 64 times to encrypt what a single

iteration of DES can encrypt. In fact, a simple LFSR algorithm like the shrinking

generator described later is no faster in software than DES.

This branch of cryptography is fast-paced and very politically charged. Most

designs are secret; a majority of military encryptions systems in use today are based

on LFSRs. In fact, most Cray computers (Cray 1, Cray X-MP, Cray Y-MP) have a

rather curious instruction generally known as â€śpopulation count.â€ť It counts the 1

bits in a register and can be used both to efficiently calculate the Hamming distance

Page 379

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER16 Pseudo-Random-Sequence Generators

between two binary words and to implement a vectorized version of a LFSR. Iâ€™ve

heard this called the canonical NSA instruction, demanded by almost all computer

contracts.

On the other hand, an astonishingly large number of seemingly complex shift-

register-based generators have been cracked. And certainly military cryptanalysis

institutions such as the NSA have cracked a lot more. Sometimes itâ€™s amazing to see

the simple ones proposed again and again.

Linear Complexity

Analyzing stream ciphers is often easier than analyzing block ciphers. For exam-

ple, one important metric used to analyze LFSR-based generators is linear complex-

ity, or linear span. This is defined as the length, n, of the shortest LFSR that can

mimic the generator output. Any sequence generated by a finite-state machine over

a finite field has a finite linear complexity [1006]. Linear complexity is important

because a simple algorithm, called the Berlekamp-Massey algorithm, can generate

this LFSR after examining only 2n bits of the keystream [ 10051. Once youâ€™ve gener-

ated this LFSR, youâ€™ve broken the stream cipher.

This idea has extensions from fields to rings [ 12981,and when the output sequence

is viewed as numbers over fields of odd characteristic [842]. A further enhancement

is the notion of a linear complexity profile, which measures the linear complexity of

the sequence as it gets longer and longer [ 1357,1168,411,1582]. Another algorithm

for computing linear complexity is useful only in very specialized circumstances

[597,595,596,1333]. A generalization of linear complexity is in [776]. There is also the

notion of sphere complexity [SO21 and 2-adic complexity [844].

In any case, remember that a high linear complexity does not necessarily indicate

a secure generator, but a low linear complexity indicates an insecure one [ 1357,1249].

Correlation Immunity

Cryptographers try to get a high linear complexity by combining the output of

several output sequences in some nonlinear manner. The danger here is that one or

more of the internal output sequences-often just outputs of individual LFSRs-can

be correlated with the combined keystream and attacked using linear algebra. Often

this is called a correlation attack or a divide-and-conquer attack. Thomas Siegen-

thaler has shown that correlation immunity can be precisely defined, and that there

is a trade-off between correlation immunity and linear complexity [ 14501.

The basic idea behind a correlation attack is to identify some correlation between

the output of the generator and the output of one of its internal pieces. Then, by

observing the output sequence, you can obtain information about that internal out-

put. Using that information and other correlations, collect information about the

other internal outputs until the entire generator is broken.

Correlation attacks and variations such as fast correlation attacks-these offer a

trade-off between computational complexity and effectiveness-have been success-

fully applied to a number of LFSR-based keystream generators [ 1451,278,1452,572,

1636,1051,1090,350,633,1054,1089,995]. Some interesting new ideas along these

lines are in (46,1641].

Page 380

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Other Attacks

There are other general attacks against keystream generators. The linear consistency

test attempts to identify some subset of the encryption key using matrix techniques

[ 16381.There is also the meet-in-the-middle consistency attack [39,41]. The linear syn-

drome algorithm relies on being able to write a fragment of the output sequence as a

linear equation [ 1636,1637]. There is the best affine approximation attack [502] and the

derived sequence attack [42]. The techniques of differential cryptanalysis have even

been applied to stream ciphers [501], as has linear cryptanalysis 16311.

16.4 CIPHERS USING LFSRs

STREAM

The basic approach to designing a keystream generator using LFSRs is simple. First

you take one or more LFSRs, generally of different lengths and with different feed-

back polynomials. (If the lengths are all relatively prime and the feedback polynomi-

als are all primitive, the whole generator is maximal length.) The key is the initial

state of the LFSRs. Every time you want a bit, shift the LFSRs once (this is sometimes

called clocking). The output bit is a function, preferably a nonlinear function, of

some of the bits of the LFSRs. This function is called the combining function, and the

whole generator is called a combination generator. (If the output bit is a function of

a single LFSR, the generator is called a filter generator.) Much of the theoretical back-

ground for this kind of thing was laid down by Selmer and Neal Zierler [1647].

Complications have been added. Some generators have LFSRs clocked at different

rates; sometimes the clocking of one generator depends on the output of another.

These are all electronic versions of pre-WWII cipher machine ideas, and are called

clock-controlled generators [641]. Clock control can be feedforward, where the out-

put of one LFSR controls the clocking of another, or feedback, where the output of

one LFSR controls its own clocking.

Although these generators are, at least in theory, susceptible to embedding and

probabilistic correlation attacks [634,632], many are secure for now. Additional the-

ory on clock-controlled shift registers is in [89].

Ian Cassells, once the head of pure mathematics at Cambridge and a former

Bletchly Park cryptanalyst, said that â€ścryptography is a mixture of mathematics and

muddle, and without the muddle the mathematics can be used against you.â€ś What

he meant was that in stream ciphers, you need some kind of mathematical struc-

ture-such as a LFSR-to guarantee maximal-length and other properties, and then

some complicated nonlinear muddle to stop someone from getting at the register

and solving it. This advice also holds true for block algorithms.

What follows is a smattering of LFSR-based keystream generators that have

appeared in the literature. I donâ€™t know if any of them have been used in actual cryp-

tographic products. Most of them are of theoretical interest only. Some have been

broken; some may still be secure.

Since LFSR-based ciphers are generally implemented in hardware, electronics

logic symbols will be used in the figures. In the text, 0 is XOR, A is AND, v is OR,

and --, is NOT.

Page 381

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER16 Pseudo-Random-Sequence Generators

Geffe Generator

This keystream generator uses three LFSRs, combined in a nonlinear manner (see

Figure 16.6) [606]. Two of the LFSRs are inputs into a multiplexer, and the third

LFSR controls the output of the multiplexer. If a,, a2, and a3 are the outputs of the

three LFSRs, the output of the Geffe generator can be described by:

b = (al A 4 @ (I- 4 A 4

If the LFSRs have lengths nl, n2, and n3, respectively, then the linear complexity

of the generator is

In1 + IIn2 + w3

The period of the generator is the least common multiple of the periods of the

three generators. Assuming the degrees of the three primitive feedback polynomials

are relatively prime, the period of this generator is the product of the periods of the

three LFSRs.

Although this generator looks good on paper, it is cryptographically weak and falls

to a correlation attack [829,1638]. The output of the generator equals the output of

LFSR-2 75 percent of the time. So, if the feedback taps are known, you can guess the

initial value for LFSR-2 and generate the output sequence of that register. Then you

can count the number of times the output of the LFSR-2 agrees with the output of the

generator. If you guessed wrong, the two sequences will agree about 50 percent of the

time; if you guessed right, the two sequences will agree about 75 percent of the time.

Similarly, the output of the generator equals the output of LFSR3 about 75 per-

cent of the time. With those correlations, the keystream generator can be easily

cracked. For example, if the primitive polynomials only have three terms each, and

the largest LFSR is of length n, it only takes a segment of the output sequence 37n-

bits long to reconstruct the internal states of all three LFSRs [ 16391.

Generalized Geffe Generator

Instead of choosing between two LFSRs, this scheme chooses between k LFSRs, as

long as k is a power of 2. There are k + 1 LFSRs total (see Figure 16.7). LFSR-1 must

be clocked log,k times faster than the other k LFSRs.

240-l

Multiplexer

LFSR-2

t

LFSR-1

Figure 16.6 Geffe generator.

Page 382

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16.4 Stream Ciphers Using LFSRs

Even though this scheme is more complex than the Geffe generator, the same

kind of correlation attack is possible. I donâ€™t recommend this generator.

Jennings Generator

This scheme uses a multiplexer to combine two LFSRs [778,779,780]. The multi-

plexer, controlled by LFSR-1, selects 1 bit of LFSR-2 for each output bit. There is

also a function that maps the output of LFSR-2 to the input of the multiplexer (see

Figure 16.8).

The key is the initial state of the two LFSRs and the mapping function. Although

this generator has great statistical properties, it fell to Ross Andersonâ€™s meet-in-the-

middle consistency attack [39] and the linear consistency attack [1638,442]. Donâ€™t

use this generator.

Beth-Piper Stop-and-Go Generator

This generator, shown in Figure 16.9, uses the output of one LFSR to control the

clock of another LFSR [ 1511. The clock input of LFSR-2 is controlled by the output

of LFSR-1, so that LFSR-2 can change its state at time t only if the output of LFSR-1

was 1 at time t- 1.

No one has been able to prove results about this generatorâ€™s linear complexity in

the general case. However, it falls to a correlation attack [ 16391.

Al terna ting Stop-and-Go Generator

This generator uses three LFSRs of different length. LFSR-2 is clocked when the

output of LFSR-1 is 1; LFSR3 is clocked when the output of LFSR-1 is 0. The output

of the generator is the XOR of LFSR-2 and LFSR-3 (see Figure 16.10) [673].

This generator has a long period and large linear complexity. The authors found a

correlation attack against LFSR-1, but it does not substantially weaken the genera-

tor. There have been other attempts at keystream generators along these lines [ 1534,

1574,1477].

LFSR-n + 1

.

.

.

n-to-1

.

â€˜-â€˜(t)

Multiplexer

b

LFSR-3 I

t-

LFSRQ

Figure 16.7 Generalized Geffe generator.

Page 383

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16 Pseudo-Random-Sequence Generators

CHAPTER

+

s

a

* 0

z Multiplexer A b(t)

. ..

rj . .. B

. . . n-1

- 01

Kl K2

K3

Figure 16.8 Jennings generator.

Bilateral Stop-and-Go Generator

This generator uses two LFSRs, both of length n (see Figure 16.11) [ 16381.The out-

put of the generator is the XOR of the outputs of each LFSR. If the output of LFSR-2

at time t - 1 is 0 and the output at time t - 2 is 1, then LFSR-2 does not clock at

time t. Conversely, if the output of LFSR-1 at time t - 1 is 0 and the output at t - 2

is 1, and if LFSR-1 clocked at time t, then LFSR-2 does not clock at time t.

The linear complexity of this system is roughly equal to the period. According to

[ 16381, â€śno evident key redundancy has been observed in this system.â€ť

Threshold Generator

This generator tries to get around the security problems of the previous generators

by using a variable number of LFSRs [277]. The theory is that if you use a lot of

LFSRs, itâ€™s harder to break the cipher.

This generator is illustrated in Figure 16.12. Take the output of a large number of

LFSRs (use an odd number of them). Make sure the lengths of all the LFSRs are rel-

atively prime and all the feedback polynomials are primitive: maximize the period.

If more than half the output bits are 1, then the output of the generator is 1. If more

than half the output bits are 0, then the output of the generator is 0.

LFSRP

Figure 16.9 Beth-Piper stop-and-go generator.

Page 384

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

LFSR-2

LFSR-1 I

(> *b(t)

I

LFSR-3

(D(t) -

Figure 16.10 Alternating stop-and-go generator.

With three LFSRs, the output generator can be written as:

b = (aI A a2) 0 (a, A a3) 0 (a2 A a3)

This is very similar to the Geffe generator, except that it has a larger linear com-

plexity of

nln2 + n1n3 + n2n3

where nl, n2, and n3 are the lengths of the first, second, and third LFSRs.

This generator isnâ€™t great. Each output bit of the generator yields some informa-

tion about the state of the LFSRs-0.189 bit to be exact-and the whole thing falls

to a correlation attack. I donâ€™t recommend using it.

Self-Decimated Generators

Self-decimated generators are generators that control their own clock. Two have

been proposed, one by Rainer Rueppel (see Figure 16.13) [ 13591 and another by Bill

Figure 16.11 Bilateral stop-and-go generator.

Page 385

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16 Pseudo-Random-Sequence Generators

CHAPTER

LFSR-1

LFSR-2

LFSR-3

I

I

LkSR-n

Figure 16.12 Threshold generator.

Chambers and Dieter Gollmann [308] (see Figure 16.14). In Rueppelâ€™s generator,

when the output of the LFSR is 0, the LFSR is clocked d times. When the output of

the LFSR is 1, the LFSR is clocked k times. Chambersâ€™s and Gollmannâ€™s generator is

more complicated, but the idea is the same. Unfortunately, both generators are inse-

cure [ 16391, although some modifications have been proposed that may correct the

problems [ 13621.

Multispeed InnerProduct Generator

This generator, by Massey and Rueppel [ 10141,uses two LFSRs clocked at two dif-

ferent speeds (see Figure 16.15). LFSR-2 is clocked d times as fast as LFSR-1. The

individual bits of the two LFSRs are ANDed together and then XORed with each

other to produce the final output bit of the generator.

Although this generator has high linear complexity and it possesses excellent sta-

tistical properties, it still falls to a linear consistency attack [ 16391.If nl is the length

of LFSR-1, n2 is the length of the LFSR-2, and d is the speed multiple between the

two, then the internal state of the generator can be recovered from an output

sequence of length

nl + n2 + log,d

Summation Genera for

More work by Rainer Rueppel, this generator adds the output of two LFSRs (with

carry) [1358,1357]. This operation is highly nonlinear. Through the late 1980s this

LFSR ) b(r)

,>

Figure 16.13 Rueppelâ€™s self-decimated generator.

Page 386

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Figure 16.14 Chambersâ€™s and Gollmannâ€™s self-decimated generator.

generator was the security front-runner, but it fell to a correlation attack [1053,

1054,1091]. And it has been shown that this is an example of a feedback with carry

shift register (see Section 17.4), and can be broken [844].

DNRSG

That stands for â€śdynamic random-sequence generatorâ€ť [ 11171.The idea is to have

two different filter generators-threshold, summation, or whatever-fed by a single

set of LFSRs and controlled by another LFSR.

First clock all the LFSRs. If the output of LFSR-0 is 1, then compute the output of

the first filter generator. If the output of LFSR-0 is 0, then compute the output of the

second filter generator. The final output is the first output XOR the second.

Gollmann Cascade

The Gollmann cascade (see Figure 16.16), described in (636,309], is a strengthened

version of a stop-and-go generator. It consists of a series of LFSRs, with the clock of

each controlled by the previous LFSR. If the output of LFSR-1 is 1 at time t - 1, then

LFSR-2 clocks. If the output of LFSR-2 is 1 at time t - 1, then LFSR-3 clocks, and so

on. The output of the final LFSR is the output of the generator. If all the LFSRs have

the same length, n, the linear complexity of a system with k LFSRs is

n(2â€ť- l)k-l

1

I -stage LFSR-1

b(t)

J)iiD

d*a) n -stage LFSR-2

Figure 16.15 Multispeed inner-product generator.

Page 387

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 16 Pseudo-Random-Sequence Generators

Cascades are a cool idea: They are conceptually very simple and they can be used

to generate sequences with huge periods, huge linear complexities, and good statis-

tical properties. They are vulnerable to an attack called lock-in [640]. This is a tech-

nique by which a cryptanalyst reconstructs the input to the last shift register in the

cascade, then proceeds to break the cascade register by register. This is a serious

problem in some situations and weakens the effective key length of the algorithm,

but precautions can be taken to minimize the attack.

Further analysis has indicated that the sequence approaches random as k gets

larger [637,638,642,639]. Based on recent attacks on short Gollmann cascades

[1063], I recommend using a k of at least 15. Youâ€™re better off using more LFSRs of

shorter length than fewer LFSRs of longer length.

Shrinking Generator

The shrinking generator [378] uses a different form of clock control than the pre-

vious generators. Take two LFSRs: LFSR-1 and LFSR-2. Clock both of them. If the

output of LFSR-1 is 1, then the output of the generator is LFSR-2. If the output of

LFSR-1 is 0, discard the two bits, clock both LFSRs, and try again.

This idea is simple, reasonably efficient, and looks secure. If the feedback polyno-

mials are sparse, the generator is vulnerable, but no other problems have been

found. Even so, itâ€™s new. One implementation problem is that the output rate is not

regular; if LFSR- 1 has a long string of zeros then the generator outputs nothing. The

authors suggest buffering to solve this problem [378]. Practical implementation of

the shrinking generator is discussed in [901].

Self-Shrinking Generator

The self-shrinking generator [1050] is a variant of the shrinking generator.

Instead of using two LFSRs, use pairs of bits from a single LFSR. Clock a LFSR

twice. If the first bit in the pair is 1, the output of the generator is the second bit.

If the first bit is 0, discard both bits and try again. While the self-shrinking gener-

ator requires about half the memory space as the shrinking generator, it is also

half the speed.

While the self-shrinking generator also seems secure, it still has some unexplained

behavior and unknown properties. This is a very new generator; give it some time.

LFSR-1

h

Figure 16.16 Gollmann cascade.

Page 388

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16.5 A5

16.5 A5

A5 is the stream cipher used to encrypt GSM (Group Special Mobile). Thatâ€™s the

non-American standard for digital cellular mobile telephones. It is used to encrypt

the link from the telephone to the base station. The rest of the link is unencrypted;

the telephone company can easily eavesdrop on your conversations.

A lot of strange politics surrounds this one. Originally it was thought that

GSMâ€™s cryptography would prohibit export of the phones to some countries. Now

some officials are discussing whether A5 might harm export sales, implying that

it is so weak as to be an embarrassment. Rumor has it that the various NATO

intelligence agencies had a catfight in the mid-1980s over whether GSM encryp-

tion should be strong or weak. The Germans wanted strong cryptography, as they

were sitting near the Soviet Union. The other countries overruled them, and A5 is

a French design.

We know most of the details. A British telephone company gave all the docu-

mentation to Bradford University without remembering to get them to sign a

nondisclosure agreement. It leaked here and there, and was eventually posted to the

Internet. A paper describing A5 is [ 16221; there is also code at the back of this book.

A5 consists of three LFSRs; the register lengths are 19,22, and 23; all the feedback

polynomials are sparse. The output is the XOR of the three LFSRs. A5 uses variable

clock control. Each register is clocked based on its own middle bit, XORed with the

inverse threshold function of the middle bits of all three registers. Usually, two of

the LFSRs clock in each round.

There is a trivial attack requiring 240encryptions: Guess the contents of the first

two LFSRs, then try to determine the third LFSR from the keystream. (Whether this

attack is actually feasible is under debate, but a hardware key search machine cur-

rently under design should resolve the matter soon [45].)

Nonetheless, it is becoming clear that the basic ideas behind A5 are good. It is

very efficient. It passes all known statistical tests; its only known weakness is that

its registers are short enough to make exhaustive search feasible. Variants of A5

with longer shift registers and denser feedback polynomials should be secure.

16.6 XPD/WD

HUGHES

This algorithm is brought to you by Hughes Aircraft Corp. They put it in army tac-

tical radios and direction-finding equipment for sale to foreign militaries. It was

designed in 1986 and called XPD, for Exportable Protection Device. Later it was

renamed KPD-Kinetic Protection Device-and declassified [ 1037,1036].

The algorithm uses a 61-bit LFSR. There are 21Â° different primitive feedback poly-

nomials, which were approved by the NSA. The key selects one of these polynomi-

als (they are all stored in ROM somewhere), as well as the initial state of the LFSR.

It has eight different nonlinear filters, each of which has six taps from the LFSR

and which produces 1 bit. The bits combine to generate a byte, which is used to

encrypt or decrypt the datastream.

Page 389

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 16 Pseudo-Random-Sequence Generators

This algorithm looks pretty impressive, but I doubt it is. The NSA allows export,

so there must be some attack on the order of 240or less. What is it?

16.7 NANOTEQ

Nanoteq is a South African electronics company. This is their algorithm that has

been fielded by the South African police to encrypt their fax transmissions, and pre-

sumably for other uses as well.

The algorithm is described, more or less, in [902,903]. It uses a 127-bit LFSR with

a fixed feedback polynomial; the key is the initial state of the feedback register. The

127 bits of the register are reduced to a single keystream bit using 25 primitive cells.

Each cell has five inputs and one output:

f(XlrX2,X37X47X5) = Xl + x2 + (Xl + x3) (x2 + x4 + 3) + (Xl + x4) (x2 + x3) + x5

Each input of the function is XORed with some bit of the key. There is also a

secret permutation that depends on the particular implementation, and is not de-

tailed in the papers. This algorithm is only available in hardware.

Is this algorithm secure? I doubt it. During the transition to majority rule, embar-

rassing faxes from one police station to another would sometimes turn up in the lib-

eral newspapers. These could easily have been the results of U.S., U.K., or Soviet

intelligence efforts. Ross Anderson took some initial steps towards cryptanalyzing

this algorithm in [46]; I expect more results to come soon.

16.8 FXAMBUTAN

Rambutan is a British algorithm, designed by the Communications Electronics

Security Group (one of the aliases used by GCHQ). It is only sold as a hardware mod-

ule and is approved for the protection of classified material up to â€śConfidential.â€ť

The algorithm itself is secret, and the chip is not generally commercially available.

Rambutan has a 1l%-bit key (plus parity bits) and can operate in three modes: ECB,

CBC, and g-bit CFB. This strongly indicates that it is a block algorithm, but rumors

point elsewhere. Supposedly, it is a LFSR stream cipher. It has five shift registers,

each one of a different length around 80 bits. The feedback polynomials are fairly

sparse, with only about 10 taps each. Each shift register provides four inputs to a very

large and complex nonlinear function which eventually spits out a single bit.

Why call it Rambutan? Perhaps, like the fruit, itâ€™s spiny and forbidding on the out-

side but soft and yielding inside. On the other hand, maybe thatâ€™s not the reason.

16.9 ADDITIVE GENERATORS

Additive generators (sometimes called lagged Fibonacci generators) are extremely

efficient because they produce random words instead of random bits [863]. They are

not secure on their own, but can be used as building blocks for secure generators.

Page 390

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

26.9 Additive Generators

The initial state of the generator is an array of n-bit words: g-bit words, 16-bit

words, 32-bit words, whatever: XI, X,, X,, . . . , X,. This initial state is the key. The

ith word of the generator is

Xi=(X˜-˜+Xi-b+Xi-c+. . .+X1-,)mod2â€ť

If the coefficients a, b, c, . . . , m are chosen right, the period of this generator is at

least 2â€ť - 1. One of the requirements on the coefficients is that the least significant

bit forms a maximal-length LFSR.

For example, (55,24,0) is a primitive polynomial mod 2 from Table 16.2. This

means that the following additive generator is maximal length.

Xl=(Xi-55+Xi-24) mod2â€ť

This works because the primitive polynomial has three coefficients. If it has more

than three, you need some additional requirements to make it maximal length. See

[249] for details.

Fish

Fish is an additive generator based on techniques used in the shrinking generator

[190]. It produces a stream of 32-bit words which can be XORed with a plaintext

stream to produce ciphertext, or XORed with a ciphertext stream to produce plain-

text. The algorithm is named as it is because it is a Fibonacci shrinking generator.

First, use these two additive generators. The key is the initial values of these

generators.

Ai = (Ai - 55+ A, - 24) mod 232

Bi = (Bj - 52+ Bi - 19)mod 232

These sequences are shrunk, as a pair, depending on the least significant bit of B,:

if it is 1, use the pair; if it is 0, ignore the pair. C, is the sequence of used words from

Ai, and Di is the sequence of used words from Bi. These words are used in pairs-&,

C2i + 19 Dzi, and D,, + l-to generate two 32-bit output words: KZi and Kzi + ,.

&i = C21@ (D2/ A D2i + 1)

F2i=D2i+l˜(E2i˜C2i+l)

K2, = E2i @ F2,

Kti+l=C2i+l@F2j

This algorithm is fast. On a 33 megahertz 486, a C implementation of Fish

encrypts data at 15 megabits per second. Unfortunately, it is also insecure; an attack

has a work factor of about 24014.5).

Pike

Pike is a leaner, meaner version of Fish, brought to you by Ross Anderson, the

man who broke Fish (451. It uses three additive generators. For example:

A, = (Ai - 55+ Ai - 24) mod 232

Page 391

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 16 Pseudo-Random-Sequence Generators

Bi = (Bi - 57+ Bi - 7) mod 232

C, = (C, - 58+ C, - 19)mod 232

To generate the keystream word, look at the addition carry bits. If all three agree

(all are 0 or all are l), then clock all three generators. If they do not, just clock the

two generators that agree. Save the carry bits for next time. The final output is the

XOR of the three generators.

Pike is faster than Fish, since on the average 2.75 steps will be required per output

rather than 3. It is far too new to trust, but looks good so far.

Mush

ńňđ. 1 |