стр. 2 |

tive generators: A and B. If the carry bit of A is set, clock B. If the carry bit of B is

set, clock A. Clock A, and set the carry bit if there is a carry. Clock B, and set the

carry bit if there is a carry. The final output is the XOR of the output of A and B.

The easiest generators to use are the ones from Fish:

32

Ai=(Ai-55+Al-24)mod2

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

On the average, three generator iterations are required to produce one output

word. And if the coefficients of the additive generators are chosen correctly and are

relatively prime, the output sequence will be maximal length. I know of no suc-

cessful attacks, but remember that this algorithm is very new.

16.10 GIFFORD

David Gifford invented a stream cipher and used it to encrypt news wire reports in

the Boston area from 1984 until 1988 [608,607,609]. The algorithm has a single

g-byte register: bo, hi, . . . , b,. The key is the initial state of the register. The algorithm

works in OFB; the plaintext does not affect the algorithm at all. (SeeFigure 16.17).

To generate a key byte k,, concatenate b. and bz and concatenate b4 and b7. Multi-

ply the two together to get a 32-bit number. The third byte from the left is ki.

To update the register, take b, and sticky right shift it 1 bit. This means the left-

most bit is both shifted and also remains in place. Take b, and shift it 1 bit to the

left; there should be a 0 in the right-most bit position. Take the XOR of the modified

bl, the modified b7, and bo. Shift the original register 1 byte to the right and put this

byte in the left-most position.

This algorithm remained secure throughout its life, but was broken in 1994 [287].

It turns out that the feedback polynomial isnвЂ™t primitive and can be attacked that

way-oops.

Page 392

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Figure 16.17 Gifford.

16.11 M

ALGORITHM

The name is from Knuth [863]. ItвЂ™s a method for combining multiple pseudo-random

streams that increases their security. One generatorвЂ™s output is used to select a

delayed output from the other generator [996,1003]. In C:

#define ARR-SIZE (8192) /* for example - the larger the better

*/

static unsigned char delayI: ARR-SIZE 1;

unsigned char prngA( void );

long prngB( void ) ;

void init-algM( void )

long i ;

for ( i = 0 ; i < ARR-SIZE ; i++ 1

delayCi1 = prngA0 ;

1 /* init-algM */

unsigned char algM( void 1

(

long j,v ;

Page 393

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 16 Pseudo-Random-Sequence Generators

/* get the delay[l index */

j = prngB0 % ARRKSIZE ;

/* get the value to return */

v = delay[jl ;

/* replace it */

delay[jl = prngA0 ;

return (v);

I I* algM *I

This has strength in that if prngA were truly random, one could not learn any-

thing about prngB (and could therefore not cryptanalyze it). If prngA were of the

form that it could be cryptanalyzed only if its output were available in order (i.e.,

only if prngB were cryptanalyzed first) and otherwise it was effectively truly ran-

dom, then the combination would be secure.

16.12 PKZIP

Roger Schlafly designed the encryption algorithm built into the PKZIP data com-

pression program. ItвЂ™s a stream cipher that encrypts data one byte at a time. At least,

this is the algorithm in version 2.04g. I canвЂ™t speak for later versions, but unless

there is some announcement you can probably assume that they are identical.

The algorithm uses three 32-bit variables, initialized as follows:

KO= 305419896

K1= 591751049

Kz = 878082192

It has an g-bit key, K3, derived from Kz. Here is the algorithm (all symbols are stan-

dard C notation):

Ci = Pi h KS

Ko = crc32 (Ko, Pi)

K1 = K1 + (K,, & OxOOOOOOff)

K1 = K1 134775813 + 1

l

Kz = crc32 (K,, K1 >> 24)

K3 = ((Kz I 2) ((Kz I 2) A 1)) >> 8

l

The function crc32 takes the previous value and a byte, XORs them, and calcu-

lates the next value by the CRC polynomial denoted by Oxedb88320. In practice, a

256-entry table can be precomputed and the crc32 calculation becomes:

crc32 (a, b) = (a >> 8) h table [(a & Oxff) 0 b]

The table is precomputed by the original definition of crc32:

table [i] = crc32 (i, 0)

To encrypt a plaintext stream, first loop the key bytes through the encryption

algorithm to update the keys. Ignore the ciphertext output in this step. Then

encrypt the plaintext, one byte at a time. Twelve random bytes are prepended to the

Page 394

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

16.12 PKZIP

plaintext, but thatвЂ™s not really important. Decryption is similar to encryption,

except that Ci is used in the second step of the algorithm instead of Pi.

of PKZlP

Security

Unfortunately, itвЂ™s not that great. An attack requires 40 to 200 bytes of known

plaintext and has a time complexity of about 2вЂќ [166]. You can do it in a few hours

on your personal computer. If the compressed file has any standard headers, getting

the known plaintext is no problem. DonвЂ™t use the built-in encryption in PKZII?

стр. 2 |