ńňđ. 1 
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 17 ................................................ 396
Other Stream Ciphers Real Random ..... 396
RC4 ........................................................... 396
SEAL ......................................................... 397
Pseudorandom Function Family .................. 397
Description of SEAL ...................................... 398
Figure 17.1 The inner loop of SEAL. ......... 399
Security of SEAL ....................................... 399
Patents and Licenses ............................... 399
WAKE ............................................................. 399
Figure 17.2 Wake. ..................................... 400
FEEDBACK WITH CARRYSHIFT ............. 401
Figure 17.3 Feedback with carry shift ............ 401
Figure 17.4 3bit FCSR. ................................. 402
STREAM CIPHERS USING ..................... 404
Cascade Genera tots ................................... 404
FCSR Combining Generators ....................... 404
Table 17.1 Connection Integers for ............... 405
Table 17.1 (Cont.) Connection Integers ........ 406
Table 17.2 Tap Sequences for Maximallen . 407
Table 17.2 (Cont.) Tap Sequences for .......... 408
Figure 17.5 Combining Generators. ............... 409
LFSR/FCSR Summation/Parity Cascade ...... 409
Alternating StopandGo Generators ............ 409
Figure 17.6 Concoction Generator. ................ 410
Shrinking Generators .................................... 410
Figure 17.7 Alternating stopandgo ............... 410
NONLINEARFEEDBACK SHIFT ............. 411
Figure 17.8 A nonlinearfeedback shift .......... 411
Figure 17.9 3bit nonlinear feedback shift ...... 412
OTHER CIPHERS .................................... 412
Pless Generator ............................................ 412
Cellular Automaton Generator ...................... 413
l/p Generator ................................................. 413
Crypt(1) .......................................................... 413
Other Schemes ............................................. 413
SYSTEMTHEORETIC APPROACH TO .. 414
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
COMPLEXITYTHEORETIC APPROACH 415
Shamirs PseudoRandomNumber ............... 415
BlumMicah Generator .................................. 415
RSA ............................................................... 416
Blum, and Shub ............................................. 416
OTHER APPROACHES TO STREAMCI . 417
Rip van Winkle Cipher ................................... 417
Stream Cipher ............................................... 418
Figure 17.10 Rip van Winkle cipher. .............. 418
Diffies Randomized ...................................... 418
Maurers Randomized Stream Cipher ........... 418
CASCADING MULTIPLE CIPHERS ....... 418
CHOOSING A STREAM CIPHER ............ 419
GENERATING MULTIPLE FROM .......... 419
Table 17.3 Encryption Speeds of Some ....... 419
REAL RANDOMSEQUENCE GENERA .. 420
Figure 17.11 Multiplebit generator. ............... 420
RAND Tables ................................................ 421
Using Random Noise .................................... 422
Using the Computers Clock ......................... 423
Measuring Keyboard Latency ....................... 423
Biases and Correlations ................................ 424
Distilling Randomness ................................... 425
Page 396
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17
CHAPTER
Other Stream Ciphers
and Real Random
Sequence Generators
17.1 RC4
RC4 is a variablekeysize stream cipher developed in 1987 by Ron Rivest for RSA
Data Security, Inc. For seven years it was proprietary, and details of the algorithm
were only available after signing a nondisclosure agreement.
In September, 1994 someone posted source code to the Cypherpunks mailing
listanonymously. It quickly spread to the Usenet newsgroup sci.crypt, and via the
Internet to ftp sites around the world. Readers with legal copies of RC4 confirmed
compatibility. RSA Data Security, Inc. tried to put the genie back into the bottle,
claiming that it was still a trade secret even though it was public; it was too late. It
has since been discussed and dissected on Usenet, distributed at conferences, and
taught in cryptography courses.
RC4 is simple to describe. The algorithm works in OFB: The keystream is inde
pendent of the plaintext. It has a 8 * 8 Sbox: So, S1, . . . , Szss.
The entries are a per
mutation of the numbers 0 through 2.55, and the permutation is a function of the
variablelength key. It has two counters, i and j, initialized to zero.
To generate a random byte, do the following:
i=(i+l)mod256
j = (j + Si) mod 256
swap S, and Si
t = (S, + Si) mod 256
K= S,
The byte K is XORed with the plaintext to produce ciphertext or XORed with the
ciphertext to produce plaintext. Encryption is fastabout 10 times faster than DES.
Initializing the Sbox is also easy. First, fill it linearly: So= 0, S1= 1, . . . , Szss 255.
=
Then fill another 256byte array with the key, repeating the key as necessary to fill
the entire array: K,,, K1, . . . , Kzs5.Set the index j to zero. Then:
Page 397
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 17 Other Stream Ciphers
for i = 0 to 255:
j=(j+Si+Ki)mod256
swap Si and Si
And thatâ€™s it. RSADSI claims that the algorithm is immune to differential and
linear cryptanalysis, doesnâ€™t seem to have any small cycles, and is highly non
linear. (There are no public cryptanalytic results. RC4 can be in about 2â€ťOâ€ť
(256! x 2562) possible states: an enormous number.) The Sbox slowly evolves with
use: i ensures that every element changes and j ensures that the elements change
randomly. The algorithm is simple enough that most programmers can quickly
code it from memory.
It should be possible to generalize this idea to larger Sboxes and word sizes. The
previous version is 8bit RC4. Thereâ€™s no reason why you canâ€™t define 16bit RC4
with a 16 * 16 Sbox (lOOK of memory) and a 16bit word. Youâ€™d have to iterate the
initial setup a lot more times65,536 to keep with the stated designbut the
resulting algorithm should be faster.
RC4 has special export status if its key length is 40 bits or under (see Section 13.8).
This special export status has nothing to do with the secrecy of the algorithm,
although RSA Data Security, Inc. has hinted for years that it does. The name is
trademarked, so anyone who writes his own code has to call it something else. Var
ious internal documents by RSA Data Security, Inc. have not yet been made public
[1320,1337].
So, whatâ€™s the deal with RC4? Itâ€™s no longer a trade secret, so presumably anyone
can use it. However, RSA Data Security, Inc. will almost certainly sue anyone who
uses unlicensed RC4 in a commercial product. They probably wonâ€™t win, but they
will certainly make it cheaper for a company to license than fight.
RC4 is in dozens of commercial cryptography products, including Lotus Notes,
Apple Computerâ€™s AOCE, and Oracle Secure SQL. It is part of the Cellular Digital
Packet Data specification [37].
17.2 SEAL
SEAL is a softwareefficient stream cipher designed at IBM by Phil Rogaway and
Don Coppersmith [ 13401.The algorithm was optimized for 32bit processors: To run
well it needs eight 32bit registers and a cache of a few kilobytes. Using a relatively
slow operation, SEAL preprocesses the key operation into a set of tables. These
tables are then used to speed up encryption and decryption.
Pseudorandom Function Family
One novel feature of SEAL is that is isnâ€™t really a traditional stream cipher: it is a
pseudorandom function family. Given a 160bit key k, and a %bit n, SEAL stretches
n into an Lbit string k(n). L can take any value less than 64 kilobytes. SEAL is sup
posed to enjoy the property that if k is selected at random, then k(n) should be com
putationally indistinguishable from a random Lbit function of n.
Page 398
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17.2 SEAL
The practical effect of SEAL being a pseudorandom function family is that it is
useful in applications where traditional stream ciphers are not. With most stream
ciphers you generate a sequence of bits in one direction: Knowing the key and a posi
tion i, the only way to determine the ith bit generated is to generate all the bits up
until the ith one. But a pseudorandom function family is different: You get easy
access at any desired position in the key stream. This is very useful.
Imagine you need to secure a hard drive. You want to encrypt each and every 5 12
byte sector. With a pseudorandom function family like SEAL, you can encrypt the
contents of sector n by XORing it with k(n). It is as though the entire disk is XORed
with a long pseudorandom string, where any piece of that long string can be com
puted without any trouble.
A pseudorandom function family also simplifies the synchronization problem
encountered with standard stream ciphers. Suppose you send encrypted messages
over a channel that sometimes drops messages. With a pseudorandom function fam
ily, you can encrypt under k the nth message you transmit, x,, as n together with the
XOR of x, and k(n). The receiver doesnâ€™t need to store any state to recover x,, nor does
he need to worry about lost messages affecting the message decryption process.
Description of SEAL
The inner loop of SEAL is shown by Figure 17.1. Three keyderived tables, called
R, S, and T, drive the algorithm. The preprocessing step maps the key k, to these
tables using a procedure based on SHA (see Section 18.7). The 2kilobyte table, T, is
a 9 * 32 bit Sbox.
SEAL also uses four 32bit registers, A, B, C, and D, whose initial values are deter
mined by n and the kderived tables R and T. These registers get modified over sev
eral iterations, each one involving 8 rounds. In each round 9 bits of a first register
(either A, B, C, or D) are used to index into table T. The value retrieved from T is
then added to or XORed with the contents of a second register: again one of A, B, C,
or D. The first register is then circularly shifted by nine positions. In some rounds
the second register is further modified by adding or XORing it with the (now shifted)
first register. After 8 rounds of this, A, B, C, and D are added to the keystream, each
masked first by adding or XORing it with a certain word from S. The iteration is
completed by adding to A and C additional values dependent on n, nl, n2, n3, n4;
exactly which one depends on the parity of the iteration number.
The important ideas in this design seem to be:
1. Use a large, secret, keyderived Sbox (T).
2. Alternate arithmetic operations which donâ€™t commute (addition and XOR).
3. Use an internal state maintained by the cipher which is not directly man
ifest in the data stream (the ni values which modify A and C at the end of
each iteration).
4. Vary the round function according to the round number, and vary the iter
ation function according to the iteration number.
Page 399
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 17 Other Stream Ciphers
Figure 17.1 The inner loop of SEAL.
SEAL requires about five elementary machine operations to encrypt each byte of
text. It runs at 58 megabits per second on a 50 megahertz 486 machine. This is prob
ably the fastest software algorithm in the book.
On the other hand, SEAL must preprocess its key into internal tables. These tables
total roughly 3 kilobytes in size, and their calculation takes about 200 SHA compu
tations. Thus, SEAL is not appropriate to use in situations where you donâ€™t have the
time to perform the key setup or you donâ€™t have the memory to store the tables.
of SEAL
Security
SEAL is a new algorithm and has yet to be subjected to any published cryptanaly
sis. This suggests caution. However, SEAL seems to be well thought through. Its
peculiarities do, in the end, make a good deal of sense. And Don Coppersmith is gen
erally regarded as the worldâ€™s cleverest cryptanalyst.
Pa tents and Licenses
SEAL is being patented [380]. Anyone wishing to license SEAL should contact the
Director of Licenses, IBM Corporation, 500 Columbus Ave., Thurnwood, NY, 10594.
17.3 WAKE
WAKE is the Word Auto Key Encryption algorithm, invented by David Wheeler
[1589]. It produces a stream of 32bit words which can be XORed with a plaintext
Page 400
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17.3 WAKE
stream to produce ciphertext, or XORed with a ciphertext stream to produce plain
text. And itâ€™s fast.
WAKE works in CFB; the previous ciphertext word is used to generate the next
key word. It also uses an Sbox of 256 32bit values. This Sbox has a special prop
erty: The highorder byte of all the entries is a permutation of all possible bytes, and
the loworder 3 bytes are random.
First, generate the Sbox entries, Sipfrom the key. Then initialize four registers
with the key (or with another key): ao, bo, co, and do. To generate a 32bit keystream
word, K,:
K, = d,
The ciphertext word Ci, is the plaintext word, Iâ€™i XORed with K,.
Then, update the four registers:
a1+ I = M(a,,dil
bi+l=M(bi,ai+l)
M( Ci, bi + I)
Ci+l=
di + 1 = M(dirci + 1)
Function M is
M(x,Y) = (X + Y) >> 8 @ SIX + ye ,+ 255
This is shown in Figure 17.2. The operation >> is a right shift, not a rotation. The
loworder 8 bits of x + y are the input into the Sbox. Wheeler gives a procedure for
4
D
1
C
1
B
1
A
1
K
.
Figure 17.2 Wake.
Page 401
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 17 Other Stream Ciphers
generating the Sbox, but it isnâ€™t really complete. Any algorithm to generate random
bytes and a random permutation will work.
WAKEâ€™s biggest asset is that it is fast. However, itâ€™s insecure against a chosen
plaintext or chosenciphertext attack. It is being used in the current version of Dr.
Solomonâ€™s AntiVirus program.
17.4 FEEDBACK WITH CARRYSHIFTREGISTERS
A feedback with carry shift register, or FCSR, is similar to a LFSR. Both have a shift
register and a feedback function; the difference is that a FCSR also has a carry reg
ister (see Figure 17.3). Instead of XORing all the bits in the tap sequence, add the
bits together and add in the contents of the carry register. The result mod 2
becomes the new bit. The result divided by 2 becomes the new content of the carry
register.
Figure 17.4 is an example of a 3bit FCSR tapped at the first and second bit. Its ini
tial value is 001, and the initial contents of the carry register is 0. The output bit is
the rightmost bit of the shift register.
Shift Register Carry Register
001 0
100 0
010 0
101 0
110 0
111 0
011 1
Shift Register
Sum Div 2
Figure 17.3 Feedback with carry shift register.
Page 402
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
1
101
1
010
1
001
1
000
0
100
Note that the final internal state (including the contents of the carry register) is
the same as the second internal state. The sequence cycles at this point, and has a
period of 10.
There are a few things to note here. First, the carry register is not a single bit; it is
a number. The size of the carry register must be at least log2t, where t is the number
of taps. There are only two taps in the previous example, so the carry register only
has to be 1 bit wide. If there were four taps, the carry register would have to be 2 bits
wide, and could be either 0, 1, 2, or 3.
Second, there is an initial transient before the FCSR settles down into its repeat
ing period. In the previous example, only one state never repeated. For larger and
more complicated FCSRs, there may be more.
Third, the maximum period of a FCSR is not 2â€ť  1, where n is the length of the
shift register. The maximum period is q  1, where q is the connection integer. This
number gives the taps and is defined by:
q = 2q, + 22q, + 24q4+ . . . + 2â€ťq,  1
(Yes, the q,s are numbered from left to right.) And even worse, q has to be a prime
for which 2 is a primitive root. The rest of this discussion assumes q is of this form.
Inthisexample,q=2*0+4*1+8*11=11.And11isaprimewith2asaprim
itive root. So the maximum period is 10.
Not all initial states give you the maximum period. For example, look at the
FCSR when the initial value is 101 and the carry register is set to 4.
Output Bit
Sum Mod 2
bz
. b, h 
.
 Sum
.
Sum Div 2
Figure 17.4 3bit FCSR.
Page 403
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 17 Other Stream Ciphers
Shift Register Carry Register
101 4
110 2
111 1
111 1
At this point the register spits out a neverending stream of 1s.
Any initial state will result in one of four things. First, it is part of the maximum
period. Second, it will fall into the maximum period after an initial transient. Third,
it will fall into a sequence of all zeros after an initial transient. Fourth, it will fall
into a sequence of all ones after an initial transient.
There is a mathematical formula for determining what will happen to a given ini
tial state, but itâ€™s much easier to just test it. Run the FCSR for a while. (If m is the
initial memory, and t is the number of taps, then logz(t) + log,(m) + 1 steps are
enough.) If it degenerates into a neverending stream of OSor 1s within n bits, where
n is the length of the FCSR, donâ€™t use it. If it doesnâ€™t, then use it. Since the initial
state of a FCSR corresponds to the key of the stream cipher, this means that a FCSR
based generator will have a set of weak keys.
Table 17.1 lists all connection integers less than 10,000 for which 2 is a primitive
root. These all have maximum period 4  1. To turn one of these numbers into a tap
sequence, calculate the binary expansion of 4 + 1. For example, 9949 would trans
late to taps on bits 1, 2, 3, 4, 6, 7, 9, 10, and 13, because
9950 = 2l3 + 210 + 29 + 2â€™ + 26 + 24 + 23 + 22 + 2l
Table 17.2 lists all the 4tap tap sequences that result in a maximallength FCSR
for shift register lengths of 32 bits, 64 bits, and 128 bits. Each of the four values, a,
b, c, and d, combine to generate 4, a prime for which 2 is primitive.
q = 2â€ť + 2b + 2â€ť + 2d  I
Any of these tap sequences can be used to create a FCSR with period 4  1.
The idea of using FCSRs for cryptography is still very new; it is being pioneered
by Andy Klapper and Mark Goresky [844,845,654,843,846]. Just as the analysis of
LFSRs is based on the addition of primitive polynomials mod 2, analysis of FCSRs is
based on addition over something called the 2adic numbers. The theory is well
beyond the scope of this book, but there seems to be a 2adic analog for everything.
Just as you can define linear complexity, you can define 2adic complexity. There is
even a 2adic analog to the BerlekampMassey algorithm. What this means is that
the list of potential stream ciphers has just doubledat least. Anything you can do
with a LFSR you can do with a FCSR.
There are further enhancements to this sort of idea, ones that involve multiple
carry registers. The analysis of these sequence generators is based on addition over
the ramified extensions of the 2adic numbers [845,846].
Page 404
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17.5 Stream Ciphers Using FCSRs
17.5 FCSRs
STREAM CIPHERS USING
There arenâ€™t any FCSR stream ciphers in the literature; the theory is still too new.
In the interests of getting the ball rolling, I propose some here. I am taking two dif
ferent tacks: I am proposing FCSR stream ciphers that are identical to previously
proposed LFSR generators, and I am proposing stream ciphers that use both FCSRs
and LFSRs. The security of the former can probably be analyzed using 2adic num
bers; the latter cannot be analyzed using algebraic techniquesthey can probably
only be analyzed indirectly. In any case, it is important to choose LFSRs and FCSRs
whose periods are relatively prime.
All this will come later. Right now I know of no implementation or analysis of any
of these ideas. Wait some years and scan the literature before you trust any of them.
Cascade Genera tots
There are two ways to use FCSRs in a cascade generator:
 FCSR Cascade. The Gollmann cascade with FCSRs instead of LFSRs.
 LFSR/FCSR Cascade. The Gollmann cascade with the generators
alternating between LFSRs and FCSRs.
FCSR Combining Generators
These generators use a variable number of LFSRs and/or FCSRs, and a variety of
functions to combine them. The XOR operation destroys the algebraic properties of
FCSRs, so it makes sense to use it to combine them. The generator, shown in Figure
17.5, uses a variable number of FCSRs. Its output is the XOR of the outputs of the
individual FCSRs.
Other generators along similar lines are:
 FCSR Parity Generator. All registers are FCSRs and the combining
function is XOR.
 LFSR/FCSR Parity Generator. Registers are a mix of LFSRs and
FCSRs and the combining function is XOR.
 FCSR Threshold Generator. All registers are FCSRs and the combin
ing function is the majority function.
 LFSR/FCSR Threshold Generator. Registers are a mix of LFSRs and
FCSRs and the combining function is the majority function.
 FCSR Summation Generator. All registers are FCSRs and the com
bining function is addition with carry.
 LFSR/FCSR Summation Generator. Registers are a mix of LFSRs and
FCSRs and the combining function is addition with carry.
Page 405
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17 Other Stream Ciphers
CHAPTER
Table 17.1
Connection Integers for Maximalperiod FCSRs
2 653 3539
1549 2477
2531
5 659 1571 3547
11 661 2539 3557
1619
3571
13 677 1621 2549
701 3581
19 1637 2557
29 709 3613
1667 2579
37 757 2621 3637
1669
53 773 3643
1693 2659
787 3659
59 1733 2677
61 1741
797 2683 3677
821
67 2693 3691
1747
83 3701
827 1787 2699
101 829 2707
1861 3709
853
107 1867 2741 3733
131 859 2789 3779
1877
139 877 1901 2797 3797
883
149 2803 3803
1907
163 907 1931 2819 3851
173 941 2837 3853
1949
179 947 2843
1973 3877
181 1019 2851
1979 3907
197 1061 1987 2861 3917
211 1091 1997 2909 3923
227 1109 2027 393 1
2939
1117
269 2029 2957 3947
1123
293 2053 2963 3989
317 1171 2069 3011 4003
347 1187 2083 3019 4013
1213
349 2099 3037 4019
373 1229 2131 3067 4021
379 1237 2141 3083 4091
389 1259 2213 3187 4093
419 1277 2221 3203 4099
421 1283 2237 3253 4133
443 1291 2243 3299 4139
461 1301 2267 3307 4157
467 1307 2269 3323 4219
491 1373 2293 3347 4229
509 1381 2309 3371 4243
523 1427 2333 3413 4253
541 1451 2339 3461 4259
547 1453 2357 3467 4261
557 1483 2371 3469 4283
563 1493 2389 3491 4349
587 1499 2437 3499 4357
613 1523 2459 3517 4363
1531 4373
2467 3533
Page 406
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
Table 17.1 (Cont.)
Connection Integers for Maximalperiod FCSRs
8861
4397 5693 6781 7717
8867
4451 5701 6803 7757
8923
4483 5717 6827 7789
6829 7829 8933
4493 5741
8963
5749 6869 7853
4507
8971
4517 6883 7877
5779
9011
5813 7883
4547 6899
9029
4603 5827 6907 7901
9059
4621 5843 6917 7907
9173
6947 7933
4637 5851
9181
4691 7949
5869 6949
8053 9203
4723 5923 6971
9221
4787 5939 7013 8069
9227
4789 5987 7019 8093
8117 9283
4813 6011 7027
4877 6029 7043 8123 9293
8147 9323
4933 6053 7069
8171 9341
4957 6067 7109
4973 6101 7187 8179 9349
7211 8219 9371
4987 6131
6173 8221 9397
5003 7219
5011 6197 8237 9419
7229
9421
5051 6203 7237 8243
5059 6211 7243 8269 9437
5077 6229 7253 8291 9467
5099 6269 7283 8293 9491
5107 6277 7307 8363 9533
733 1
5147 6299 8387 9539
5171 6317 7349 8429 9547
5179 7411 8443
6323 9587
5189 6373 7451 8467 9613
5227 6379 7459 8539 9619
5261 6389 7477 8563 9629
5309 6397 7499 8573 9643
5333 6469 7507 8597 9661
5387 6491 7517 8627 9677
5443 6547 7523 8669 9733
5477 6619 7541 8677 9749
5483 6637 9803
7547 8693
5501 6653 7549 8699 9851
5507 6659 8731 9859
7573
5557 6691 8741 9883
7589
5563 6701 7603 8747 9901
5573 6709 7621 8803 9907
5651 6733 7643 8819 9923
5659 6763 7669 8821 9941
5683 6779 7691 8837 9949
Page 407
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17 Other Stream Ciphers
CHAPTER
Table 17.2
Tap Sequences for Maximallength FCSRs
(64, 59, 28, 2) (96, 55, 53, 2)
(64, 24, 19, 2)
(32, 6 3, 2)
(64, 59, 38, 2)
(32, 7, 5, 2) (64, 2593, 2) (96, 56, 9, 2)
(64, 59, 44, 2) (96, 56, 51, 2)
(64, 25, 4, 2)
(32, 8, 3, 2)
(64, 60, 49, 2)
(64, 25, 11, 2)
(32, 13, 8, 2) (96, 57, 3, 2)
(32, 13, 12, 2) (64, 25, 19, 2) (64, 61, 51, 2) (96, 57, 17, 2)
(96, 57, 47, 2)
(32, 15, 6, 2) (64, 27, 5, 2) (64, 63, 8, 2)
(64, 63, 13, 2) (96, 58, 35, 2)
(64, 27, 16, 2)
(3% 16, 2, 1)
(64, 63, 61, 2) (96, 59, 46, 2)
(64, 27, 22, 2)
(32, 16, 3, 2)
(64, 28, 19, 2) (96, 60, 29, 2)
(32, 16, 5, 2)
(64, 28, 25, 2) (96, 60, 41, 2)
(32, 17, 5, 2) (96, 15, 5, 2)
(96, 21, 17, 2)
(64, 29, 16, 2) (96, 60, 45, 2)
(32, 19, 2, 1)
(64, 29, 28, 2) (96, 61, 17, 2)
(96, 25, 19, 2)
(32, 19, 5, 2)
(64, 31, 12, 2) (96, 25, 20, 2) (96, 63, 20, 2)
(32, 19, 9, 2)
(32, 19, 12, 2) (96, 29, 15, 2)
(64, 32, 21, 2) (96, 65, 12, 2)
(32, 19, 17, 2) (64, 35, 29, 2) (96, 65, 39, 2)
(96, 29, 17, 2)
(32, 20, 17, 2) (96, 65, 51, 2)
(64, 36, 7, 2) (96, 30, 3, 2)
(96, 32, 21, 2)
(32, 21, 9, 2) (64, 37, 2, 1) (96, 67, 5, 2)
(32, 21, 15, 2) (64, 37, 11, 2) (96, 32, 27, 2) (96, 67, 25, 2)
(96, 67, 34, 2)
(64, 39, 4, 2) (96, 33, 5, 2)
(3% 23, 8, 2)
(32, 23, 21, 2) (64, 39, 25, 2) (96, 35, 17, 2) (96, 68, 5, 2)
(96, 35, 33, 2) (96, 68, 19, 2)
(32, 25, 5, 2) (64, 41, 5, 2)
(32, 25, 12, 2) (64, 41, 11, 2) (96, 39, 21, 2) (96, 69, 17, 2)
(32, 27, 25, 2) (96, 40, 25, 2)
(64, 41, 27, 2) (96, 69, 36, 2)
(32, 29, 19, 2) (64, 43, 21, 2) (96, 41, 12, 2) (96, 70, 23, 2)
(32, 29, 20, 2) (64, 43, 28, 2) (96, 41, 27, 2) (96, 71, 6, 2)
(64, 45, 28, 2) (96, 41, 35, 2) (96, 71, 40, 2)
(32, 30, 3, 2)
(64, 45, 41, 2) (96, 42, 35, 2) (96, 72, 53, 2)
(32, 30, 7, 2)
(96, 43, 14, 2) (96, 73, 32, 2)
(32, 31, 5, 2) (64, 47, 5, 2)
(64, 47, 21, 2) (96, 44, 23, 2) (96, 77, 27, 2)
(32, 31, 9, 2)
(32, 31, 30, 2) (64, 47, 30, 2) (96, 45, 41, 2) (96, 77, 31, 2)
(64, 49, 19, 2) (96, 47, 36, 2) (96, 77, 32, 2)
(64, 49, 20, 2) (96, 49, 31, 2) (96, 77, 33, 2)
(64, 3, 2, 1)
(64, 52, 29, 2) (96, 51, 30, 2) (96, 77, 71, 2)
(64, 14, 3, 2)
(96, 53, 17, 2) (96, 78, 39, 2)
(64, 15, 8, 2) (64, 53, 8, 2)
(64, 53, 43, 2) (96, 53, 19, 2)
(64, 17, 2, 1) (96, 79, 4, 2)
(64, 56, 39, 2) (96, 53, 32, 2) (96, 81, 80, 2)
(64, 17, 9, 2)
(64, 17, 16, 2) (64, 56, 45, 2) (96, 53, 48, 2) (96, 83, 14, 2)
(96, 54, 15, 2) (96, 83, 26, 2)
(64, 19, 2, 1) (64, 59, 5, 2)
(64, 19, 18, 2) (96, 55, 44, 2) (96, 83, 54, 2)
(64, 59, 8, 2)
Page 408
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17.5 Stream Ciphers Using FCSRs
Table 17.2 (Cont.)
Tap Sequences for Maximallength FCSRs
(96, 83, 60, 2) (128, 31, 25, 2) 128, 81, 55, 2) (128, 105, 11, 2)
(96, 83, 65, 2) (128, 33, 21, 2) 128, 82, 67, 2) (128, 105, 31, 2)
(96, 83, 78, 2) (128, 35, 22, 2) 128, 83, 60, 2) (128, 105, 48, 2)
(96, 84, 65, 2) (128, 37, 8, 2) 128, 83, 61, 2) (128, 107, 40, 2)
(96, 85, 17, 2) (128, 41, 12, 2) 128, 83, 77, 2) (128, 107, 62, 2)
(96, 85, 31, 2) (128, 42, 35, 2) 128, 84, 15, 2) (128, 107, 102, 2)
(96, 85, 76, 2) (128, 43, 25, 2) 128, 84, 43, 2) (128, 108, 35, 2)
(96, 85, 79, 2) (128, 43, 42, 2) 128, 85, 63, 2) (128, 108, 73, 2)
(96, 86, 39, 2) 128, 87, 57, 2)
(128, 45, 17, 2) (128, 108, 75, 2)
(96, 86, 71, 2) 128, 87, 81, 2)
(128, 45, 27, 2) (128, 108, 89, 2)
(128, 49, 9, 2) 128, 89, 81, 2) (128, 109, 11, 2)
(96, 87, 9, 2)
(96, 87, 44, 2) (128, 51, 9, 2) 128, 90, 43, 2) (128, 109, 108, 2)
(96, 87, 45, 2) (128, 54, 51, 2) 128, 91, 9, 2) (128, 110, 23, 2)
(96, 88, 19, 2) (128, 55, 45, 2) 128, 91, 13, 2) (128, 111, 61, 2)
(96, 88, 35, 2) (128, 56, 15, 2) 128, 91, 44, 2) (128, 113, 59, 2)
(96, 88, 43, 2) 128, 92, 35, 2)
(128, 56, 19, 2) (128, 114, 83, 2)
(96, 88, 79, 2) (128, 56, 55, 2) 128, 95, 94, 2) (128, 115, 73, 2)
(96, 89, 35, 2) (128, 57, 21, 2) 128, 96, 23, 2) (128, 117, 105, 2
(96, 89, 51, 2) (128, 57, 37, 2) 128, 96, 61, 2) (128, 119, 30, 2)
(96, 89, 69, 2) (128, 59, 29, 2) 128, 97, 25, 2) (128, 119, 101, 2
(96, 89, 87, 2) 128, 97, 68, 2)
( 128, 59, 49, 2) (128, 120, 9, 2)
(96, 92, 51, 2) 128, 60, 57, 2) 128, 97, 72, 2) (128, 120, 27, 2)
(96, 92, 71, 2) 128, 61, 9, 2) 128, 97, 75, 2) (128, 120, 37, 2)
(96, 93, 32, 2) 128, 61, 23, 2) 128, 99, 13, 2) (128, 120, 41, 2)
(96, 93, 39, 2) 128, 61, 52, 2) 128, 99, 14, 2) (128, 120, 79, 2)
(96, 94, 35, 2) 128, 63, 40, 2) 128, 99, 26, 2) (128, 120, 81, 2)
128, 63, 62, 2) 128, 99, 54, 2) (128, 121, 5, 2)
(96, 95, 4, 2)
(96, 95, 16, 2) 128, 67, 41, 2) 128, 99, 56, 2) (128, 121, 67, 2)
(96, 95, 32, 2) 128, 69, 33, 2) 128, 99, 78, 2) (128, 121, 95, 2)
(96, 95, 44, 2) 128, 71, 53, 2) 128, 100, 13, 2) (128, 121, 96, 2)
(96, 95, 45, 2) 128, 72, 15, 2) 128, 100, 39, 2) (128, 123, 40, 2)
128, 72, 41, 2) 128, 101, 44, 2) (128, 123, 78, 2)
128, 73, 5, 2) 128, 101, 97, 2) (128, 124, 41, 2)
(128, 5, 4, 2)
(128, 15, 4, 2) 128, 73, 65, 2) 128, 103, 46, 2) (128, 124, 69, 2)
128, 73, 67, 2)
(128, 21, 19, 2) 128, 104, 13, 2) (128, 124, 81, 2)
(128, 25, 5, 2) 128, 75, 13, 2) 128, 104, 19, 2) (128, 125, 33, 2)
(128, 26, 11, 2) 128, 80, 39, 2) 128, 104, 35, 2) (128, 125, 43, 2)
(128, 27, 25, 2) ( 128, 80, 53, 2) (128, 127, 121, 2)
(128, 105, 7, 2)
Page 409
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 17 Other Stream Ciphers
Registerl
b
Register2
Combining
b
Function
b
Register3
Registern
Figure 17.5 Combining Generators.
LFSR/FCSR Summation/Parity Cascade
The theory is that addition with carry destroys the algebraic properties of LFSRs,
and that XOR destroys the algebraic properties of FCSRs. This generator combines
those ideas, as used in the LFSR/FCSR Summation Generator and the LFSR/FCSR
Parity Generator just listed, with the Gollmann cascade.
The generator is a series of arrays of registers, with the clock of each array con
trolled by the output of the previous array. Figure 17.6 is one stage of this generator.
The first array of LFSRs is clocked and the results are combined using addition with
carry. If the output of this combining function is 1, then the next array (of FCSRs) is
clocked and the output of those FCSRs is combined with the output of the previous
combining function using XOR. If the output of the first combining function is 0,
then the array of FCSRs is not clocked and the output is simply added to the carry
from the previous round. If the output of this second combining function is 1, then
the third array of LFSRs is clocked, and so on.
This generator uses a lot of registers: n*m, where n is the number of stages and m
is the number of registers per stage. I recommend n = 10 and m = 5.
Alternating StopandGo Generators
These generators are stopandgo generators with FCSRs instead of some LFSRs.
Additionally, the XOR operation can be replaced with an addition with carry (see
Figure 17.7).
 FCSR StopandGo Generator. Registerl, Register2, and Register3
are FCSRs. The combining operation is XOR.
 FCSR/LFSR StopandGo Generator. Registerl is a FCSR, and Regis
ters2 and 3 are LFSRs. The combining operation is addition with
carry.
Page 410
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
1
I
IT7 I 1 FCSR L
I
FCSR
A
Adder
XOR
with
..
FCSR
Carry
A
.
.
.
FCSR
A
Figure 17.6 Concoction Generator.
 LFSR/FCSR StopandGo Generator. Registerl is a LFSR, and Regis
ters2 and 3 are FCSRs. The combining operation is XOR.
Shrinking Generators
There are four basic generator types using FCSRs:
 FCSR Shrinking Generator. A shrinking generator with FCSRs
instead of LFSRs.
 FCSR/LFSR Shrinking Generator. A shrinking generator with a LFSR
shrinking a FCSR.
 LFSR/FCSR Shrinking Generator: A shrinking generator with a FCSR
shrinking a LFSR.
r
Combining
Function
Figure 17.7 Alternating stopandgo generators.
Page 411
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17 Other Stream Ciphers
CHAPTER
 FCSR SelfShrinking Generator. A selfshrinking generator with a
FCSR instead of a LFSR.
17.6 NONLINEARFEEDBACK SHIFT REGISTERS
It is easy to imagine a more complicated feedback sequence than the ones used in
LFSRs or FCSRs. The problem is that there isnâ€™t any mathematical theory that can
analyze them. Youâ€™ll get something, but who knows what it is? In particular, here
are some problems with nonlinearfeedback shift register sequences.
 There may be biases, such as more ones than zeros or fewer runs than
expected, in the output sequence.
 The maximum period of the sequence may be much lower than
expected.
 The period of the sequence might be different for different starting
values.
 The sequence may appear random for a while, but then â€śdead endâ€ť
into a single value. (This can easily be solved by XORing the nonlin
ear function with the rightmost bit.)
On the plus side, if there is no theory to analyze nonlinearfeedback shift registers
for security, there are few tools to cryptanalyze stream ciphers based on them. We
can use nonlinearfeedback shift registers in streamcipher design, but we have to be
careful.
In a nonlinearfeedback shift register, the feedback function can be anything you
want (see Figure 17.8).
J
Figure 17.8 A nonlinearfeedback shift register (probably insecure).
Page 412
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17.7 Other Stream Ciphers
I
Figure 17.9 3bit nonlinear feedback shift register.
Figure 17.9 is a 3bit shift register with the following feedback function: The new
bit is the first bit times the second bit. If it is initialized with the value 110, it pro
duces the following sequence of internal states:
110
011
101
010
001
000
000
And so on forever.
The output sequence is the string of least significant bits:
011010000000....
This isnâ€™t terribly useful.
It gets even worse. If the initial value is 100, it produces 010,001, then repeats for
ever at 000. If the initial value is 111, it repeats itself forever right from the start.
Some work has been done on computing the linear complexity of the product of
two LFSRs [ 1650,726,1364,630,658,659]. A construction that involved computing
LFSRs over a field of odd characteristic [310] is insecure [842].
17.7 STREAM
OTHER CIPHERS
Many other stream ciphers have appeared in the literature here and there. Here are
some of them.
Pless Generator
This generator is designed around the capabilities of the JK flipflop [ 12501. Eight
LFSRs drive four JK flipflops; each flipflop acts as a nonlinear combiner for two of
Page 413
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17 Other Stream Ciphers
CHAPTER
the LFSRs. To avoid the problem that knowledge of an output of the flipflop identi
fies both the source and value of the next output bit, clock the four flipflops and
then interleave the outputs to yield the final keystream.
This algorithm has been cryptanalyzed by attacking each of the four flipflops
independently [ 13561. Additionally, combining JK flipflops is cryptographically
weak; generators of this type succumb to correlation attacks [ 145 11.
Cellular Automaton Generator
In [ 1608,1609], Steve Wolfram proposed using a onedimensional cellular automa
ton as a pseudorandomnumber generator. Cellular automata is not the subject of
this book, but Wolframâ€™s generator consisted of a onedimensional array of bits, al,
. . . , a,, and an update function:
a& 03, . . , , ak,
ai=akl@(akvak+l)
The bit is extracted from one of the ak values; which one really doesnâ€™t matter.
The generatorâ€™s behavior appears to be quite random. However, there is a known
plaintext attack against these generators [ 10521.This attack works on a PC with val
ues of n up to 500 bits. Additionally, Paul Bardell proved that the output of a cellular
automaton can also be generated by a linearfeedback shift register of equal length
and is therefore no more secure [83].
l/p Generator
This generator was proposed, and then cryptanalyzed, in [ 1931.If the internal state
of the generator at time t is x,, then
t+l=bxtmodp
X
The output of the generator is the least significant bit of x, div p, where div is the
truncated integer division. For maximum period, the constants b and p should be
chosen so that p is prime and b is a primitive root mod p, Unfortunately, this gen
erator isnâ€™t secure. (Note that for b = 2, an FCSR with a connection integer p outputs
the reverse of this sequence.)
The original UNIX encryption algorithm, crypt(l), is a stream cipher based on the
same ideas as the Enigma. This is a 256element, singlerotor substitution cipher
with a reflector. Both the rotor and the reflector are generated from the key. This
algorithm is far simpler than the World War II German Enigma and, for a skilled
cryptanalyst, very easy to break [ 1576,1299]. A publicdomain UNIX program,
called Crypt Breakers Workbench (CBW), can be used to break files encrypted with
cwt( 1).
Other Schemes
Another generator is based on the knapsack problem (see Section 19.2) [1363].
CRYPTOLEGGO is insecure [301]. Joan Daemen has developed SubStream, Jam,
and StepRightUp [402]; they are all too new to comment on. Many other algorithms
Page 414
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
are described in the literature, and even more are kept secret and incorporated
into equipment.
17.8 SYSTEMTHEORETIC APPROACH TO STREAMCIPHER
DESIGN
In practice, streamcipher design is a lot like blockcipher design. It involves more
mathematical theory, but in the end a cryptographer proposes a design and then
tries to analyze it.
According to Rainer Rueppel, there are four different approaches to the construc
tion of stream ciphers [ 1360,1362]:
 Systemtheoretic approach. Try to make sure that each design creates
a difficult and unknown problem for the cryptanalyst, using a set of
fundamental design principles and criteria.
 Informationtheoretic approach. Try to keep the cryptanalyst in the
dark about the plaintext. No matter how much work the cryptanalyst
invests, he will never get a unique solution.
 Complexitytheoretic approach. Try to base the cryptosystem on, or
make it equivalent to, some known and difficult problem such as fac
toring or taking discrete logarithms.
 Randomized approach. Try to generate an unmanageably large prob
lem by forcing the cryptanalyst to examine lots of useless data in his
attempts at cryptanalysis.
The approaches differ in their assumptions about the capabilities and opportuni
ties of the cryptanalyst, the definition of cryptographic success, and the notion of
security. Most of the research in this field is theoretical, but there are some good
stream ciphers among the impractical ones.
The systemtheoretic approach was used in all the stream ciphers previously
listed; it produces most of the stream ciphers that are practical enough to be used in
the real world. A cryptographer designs keystream generators that have testable
security propertiesperiod, distribution of bit patterns, linear complexity, and so
onand not ciphers based on mathematical theory. The cryptographer also studies
various cryptanalytic techniques against these generators and makes sure the gen
erators are immune to these attacks.
Over the years, the approach has resulted in a set of design criteria for stream
ciphers [1432,99,1357,1249]. These were discussed by Rueppel in [1362], in which
he details the theory behind them.
 Long period, no repetitions.
 Linear complexity criteria large linear complexity, linear complex
ity profile, local linear complexity, and so forth.
Page 415
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17 Other Stream Ciphers
CHAPTER
 Statistical criteria such as ideal ktuple distributions.
 Confusionevery keystream bit must be a complex transformation
of all or most of the key bits.
 Diffusionredundancies in substructures must be dissipated into
longrange statistics.
 Nonlinearity criteria for Boolean functions like mthorder correlation
immunity, distance to linear functions, avalanche criterion, and so on.
This list of design criteria is not unique for stream ciphers designed by the
systemtheoretic approach; it is true for all stream ciphers. It is even true for all
block ciphers. The unique point about the systemtheoretic approach is that stream
ciphers are designed to satisfy these goals directly.
The major problem with these cryptosystems is that nothing can be proven about
their security; the design criteria have never been proved to be either necessary or
sufficient for security. A keystream generator may satisfy all the design principles,
but could still turn out to be insecure. Another could turn out to be secure. There is
still some magic to the process.
On the other hand, breaking each of these keystream generators is a different
problem for a cryptanalyst. If enough different generators are out there, it may not
be worth the cryptanalystâ€™s time to try to break each one. He may better achieve
fame and glory by figuring out better ways to factor large numbers or calculating dis
crete logarithms.
17.9 STREAM
COMPLEXITYTHEORETIC APPROACH TO
CIPHER DESIGN
Rueppel also delineated a complexitytheoretic approach to streamcipher design.
Here, a cryptographer attempts to use complexity theory to prove that his genera
tors are secure. Consequently, the generators tend to be more complicated, based on
the same sorts of hard problems as publickey cryptography. And like publickey
algorithms, they tend to be slow and cumbersome.
Shamirâ€™s PseudoRandomNumber Generator
Adi Shamir used the RSA algorithm as a pseudorandomnumber generator [ 14171.
While Shamir showed that predicting the output of the pseudorandomnumber gen
erator is equivalent to breaking RSA, potential biases in the output were demon
strated in [1401,200].
BlumMicah Generator
This generator gets its security from the difficulty of computing discrete loga
rithms [200]. Let g be a prime and p be an odd prime. A key x0, starts off the process:
@modp
Xi+l=
The output of the generator is 1 if x, < (p  1)/2, and 0 otherwise.
Page 416
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17.9 ComplexityTheoretic Approach to StreamCipher De
If p is large enough so that computing discrete logarithms mod p is infeasible,
then this generator is secure. Additional theoretical results can be found in [1627,
986,985,1237,896,799].
RSA
This RSA generator [35,36] is a modification of [200]. The initial parameters are a
modulus N which is the product of two large primes p and 4, an integer e which is
relatively prime to (p  1) (4  l), and a random seed x0, where x0 is less than N.
l+l=x;modN
X
The output of the generator is the least significant bit of xi. The security of this
generator is based on the difficulty of breaking RSA. If N is large enough, then the
generator is secure. Additional theory can be found in [1569,1570,1571,30,354].
Blum, and Shub
Blum,
The simplest and most efficient complexitytheoretic generator is called the
Blum, Blum, and Shub generator, after its inventors. Mercifully, we shall abbreviate
it to BBS, although it is sometimes called the quadratic residue generator [ 1931.
The theory behind the BBS generator has to do with quadratic residues modulo n
(see Section 11.3). Hereâ€™s how it works.
First find two large prime numbers, p and 4, which are congruent to 3 modulo 4.
The product of those numbers, n, is a Blum integer. Choose another random integer,
x, which is relatively prime to n. Compute
x0=x2modn
Thatâ€™s the seed for the generator.
Now you can start computing bits. The ith pseudorandom bit is the least signifi
cant bit of xi, where
x, = xi  12mod n
The most intriguing property of this generator is that you donâ€™t have to iterate
through all i  1 bits to get the ith bit. If you know p and 4, you can compute the ith
bit directly.
b, is the least significant bit of xi, where x, = x$ modâ€ťp lâ€ťâ€™  â€śI

This property means you can use this cryptographically strong pseudorandombit
generator as a stream cryptosystem for a randomaccess file.
The security of this scheme rests on the difficulty of factoring n. You can make n
public, so anyone can generate bits using the generator. However, unless a cryptan
alyst can factor n, he can never predict the output of the generatornot even with a
statement like: â€śThe next bit has a 5 1 percent chance of being a 1.â€ť
More strongly, the BBS generator is unpredictable to the left and unpredictable to
the right. This means that given a sequence generated by the generator, a cryptana
lyst cannot predict the next bit in the sequence nor the previous bit in the sequence.
This is not security based on some complicated bit generator that no one under
stands, but the mathematics behind factoring n.
Page 417
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
17 Other Stream Ciphers
CHAPTER
This algorithm is slow, but there are speedups. As it turns out, you can use more
than the least significant bit of each xi as a pseudorandom bit. According to [1569,
1570,1571,35,36], if n is the length of xi, the least significant log,n bits of xi can be
used. The BBS generator is comparatively slow and isnâ€™t useful for stream ciphers.
However, for highsecurity applications, such as key generation, this generator is
the best of the lot.
17.10 OTHER APPROACHES TO STREAMCIPHER DESIGN
In an informationtheoretic approach to stream ciphers, the cryptanalyst is assumed
to have unlimited time and computing power. The only practical stream cipher that
is secure against an adversary like this is a onetime pad (see Section 1.5). Since bits
would be impractical on a pad, this is sometimes called a onetime tape. Two mag
netic tapes, one at the encryption end and the other at the decryption end, would
have the same random keystream on them. To encrypt, simply XOR the plaintext
with the bits on the tape. To decrypt, XOR the ciphertext with the bits on the other,
identical, tape. You never use the same keystream bits twice. Since the keystream
bits are truly random, no one can predict the keystream. If you burn the tapes when
you are through with them, youâ€™ve got perfect secrecy (assuming no one else has
copies of the tape).
Another informationtheoretic stream cipher, developed by Claus Schnorr,
assumes that the cryptanalyst only has access to a limited number of ciphertext bits
[ 13951.The results are highly theoretical and have no practical value, at least not yet.
For more details, consult [ 1361,1643,1193].
In a randomized stream cipher, the cryptographer tries to ensure that the crypt
analyst has an infeasibly large problem to solve. The objective is to increase the
number of bits the cryptanalyst has to work with, while keeping the secret key
small. This can be done by making use of a large public random string for encryption
and decryption. The key would specify which parts of the large random string are to
be used for encryption and decryption. The cryptanalyst, not knowing the key, is
forced to pursue a bruteforce search through the random string. The security of this
sort of cipher can be expressed by the average number of bits a cryptanalyst must
examine before the chances of determining the key improve over pure guessing.
Rip van Winkle Cipher
James Massey and Ingemar Ingemarsson proposed the Rip van Winkle cipher
[lo1 11, so named because the receiver has to receive 2â€ť bits of ciphertext before
attempting decryption. The algorithm, illustrated in Figure 17.10, is simple to
implement, provably secure, and completely impractical. Simply XOR the plaintext
with the keystream, and delay the keystream by 0 to 20 yearsthe exact delay is
part of the key. In Masseyâ€™s words: â€śOne can easily guarantee that the enemy crypt
analyst will need thousands of years to break the cipher, if one is willing to wait mil
lions of years to read the plaintext.â€ť Further work on this idea can be found in
[ 1577,755].
Page 418
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
Random w Channel
Sit Stream
(multi
Plaintext Delay plexed)
Bit Stream
Plaintext
I I
O20 years
(Length is secret and dependent on key)
Figure 17.10 Rip van Winkle cipher.
Diffieâ€™s Randomized Stream Cipher
This scheme was first proposed by Whitfield Diffie [ 13621.The data are 2â€ť random
sequences. The key is k, a random nbit string. To encrypt a message, Alice uses the
kth random string as a onetime pad. She then sends the ciphertext plus the 2â€ť ran
dom strings over 2â€ť + 1 different communications channels.
Bob knows k, so he can easily choose which onetime pad to decrypt the message
with. Eve has no choice but to examine the random sequences one at a time until
she finds the correct onetime pad. Any attack must examine an expected number
of bits which is in O(2â€ť). Rueppel points out that if you send n random strings
instead of 2â€ť, and if the key is used to specify a linear combination of those random
strings, the security is the same.
Maurerâ€™s Randomized Stream Cipher
Ueli Maurer described a scheme based on XORing the plaintext with several large
public randombit sequences [ 1034,1029,1030]. The key is the set of starting positions
within each sequence. This turns out to be provably almost secure, with a calculable
probability of being broken based on how much memory the attacker has at his dis
posal, without regard to the amount of computing power he has. Maurer claims that
this scheme would be practical with about 100 different sequences of 10zorandom bits
each. Digitizing the face of the moon might be one way to get this many bits.
17.11 STREAM
CASCADING MULTIPLE CIPHERS
If performance is no issue, thereâ€™s no reason not to choose multiple stream ciphers
and cascade them. Simply XOR the output of each generator with the plaintext to
get the ciphertext. Ueli Maurerâ€™s result (see Section 15.7) says that if the generators
have independent keys, then the security of the cascade is at least as secure as the
strongest algorithm in the cascade. It is probably much more secure than that.
Stream ciphers can be combined in all the same ways as block ciphers (see Chap
ter 15). Stream ciphers can be cascaded (see Section 15.7) with other stream ciphers,
or together with block ciphers.
Page 419
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER 17 Other Stream Ciphers
A clever trick is to use one algorithm, either a block or stream algorithm, to fre
quently rekey a fast stream algorithm (which could even be a block algorithm in
OFB mode). The fast algorithm could be weak, since a cryptanalyst would never see
very much plaintext encrypted with any one key.
Thereâ€™s a tradeoff between the size of the fast algorithmâ€™s internal state (which
may impact security) and how often you can afford to rekey. The rekey needs to be
relatively fast; algorithms that have a long key setup routine arenâ€™t suitable for this
kind of application. And the rekeying should be independent of the internal state of
the fast algorithm.
17.12 STREAM CIPHER
CHOOSING A
If the study of stream ciphers offers any lessons, itâ€™s that new types of attacks are
invented with alarming regularity. Classically, stream ciphers have been based on
considerable mathematical theory. This theory can be used to prove good properties
about the cipher, but can also be used to find new attacks against the cipher. I worry
about any stream cipher based solely on LFSRs for this reason.
I prefer stream ciphers that are designed more along the lines of block ciphers:
nonlinear transformations, large Sboxes, and so on. RC4 is my favorite, and SEAL
ńňđ. 1 