Module 5��Pseudo-Random-Sequence Generators and Stream Ciphers: Linear Congruential Generators, Linear Feedback Shift Registers, Design and analysis of stream ciphers, Stream ciphers using LFSRs, A5, Hughes XPD/KPD, Nanoteq, Rambutan, Additive generators, Gifford, Algorithm M, PKZIP (Text 2: Chapter 16)��Text Books:�1. William Stallings , “Cryptography and Network Security Principles and Practice”, � Pearson Education Inc., 6th Edition, 2014, ISBN: 978-93-325-1877-3�2. Bruce Schneier, “Applied Cryptography Protocols, Algorithms, and Source code in � C”, Wiley Publications, 2nd Edition, ISBN: 9971-51-348-X.� � Reference Books: �1. Cryptography and Network Security, Behrouz A. Forouzan, TMH, 2007.�2. Cryptography and Network Security, Atul Kahate, TMH, 2003.

1

Random Number Generators

• Random number generation is a method of producing a sequence of numbers that lack any discernible pattern.

​

• Random Number Generators (RNGs) have applications in a wide range of different fields and are used heavily in computational simulations.

2

What is Random?

• What do we mean by Random?
• Uncorrelated
• Quantum systems are truly random
• Some times we want repeatability from a random number generator.

3

Pseudo RNGs

• With the exception of some specially made add-on cards, computer generated random numbers are obviously not truly random.

​

• Computational RNGs are referred to as Pseudo Random Number Generators, meaning they are random enough.

4

Pseudo RNGs

• PRNGs usually generate very long sequences of random numbers. For example the commonly used Mersenne Twister MT19937 has a sequence length of 2¹⁹⁹³⁷-1.

​

• Basically a sequence that will not recur in any practice compute time – eg the lifetime of the known universe.

5

Pseudo RNGs

• While long sequence length is a good property of a PRNG, it is not sufficient to ensure that the numbers generated are random.

​

• We can define a number of properties that random numbers should have and use them to test PRNGs.

6

Bit Properties

• Ideally a generator will produce numbers that are made up of completely random bits.

​

• From these numbers we can produce any sort of number we want.

​

• In practice, algorithms normally generate integers. We must be careful how we transform them. Uniform floating point values don't have random bits.

7

Linear Congruential Generator

• Many built-in RNGs use the Linear Congruential Generator or LCG. This generator is very fast, has low memory requirements but for most serious applications where randomness actually matters, it is useless.

8

Linear Congruential Generator

• A sequence of random values X_n where:

X_n+1 = ( a X_n + c ) mod m

• with well-chosen values of a, c, m

​

• Period is at most m (and can be shorter for “bad” choices..)

9

Linear Congruential Generator

• Example Sequences:

10

m=10, a=2, c=1

​

1

3 (2*1 + 1 % 10)

7 (2*3 + 1 % 10)

5 (2*7 + 1 % 10)

1 (2*5 + 1 % 10)

3 (2*1 + 1 % 10)

7 (2*3 + 1 % 10)

5 (2*7 + 1 % 10)

…

m=10, a=1, c=7

​

1

8 (1*1 + 7 % 10)

5 (1*8 + 7 % 10)

2 (1*5 + 7 % 10)

9 (1*2 + 7 % 10)

6 (1*9 + 7 % 10)

3 (1*6 + 7 % 10)

0 (1*3 + 7 % 10)

…

Linear Congruential Generator

• Various sources use different parameters for the LCG:

​

• Numerical Recipes
• m = 2³² a = 1664525 c = 1013904223
• GCC
• m = 2³² a = 1103515245 c = 12345
• MMIX
• m = 2⁶⁴ a = 6364136223846793005 c = 1442695040888963407

11

Stream Ciphers using LFSR

• A5
• Hughes XPD/KPD
• Nanoteq
• Rambutan
• Additive Generators
• Gifford
• Algorithm M
• PKZIP

​

​

A5

• A5 is the stream cipher used to encrypt GSM (Group Special Mobile). That’s the non-American standard for digital cellular mobile telephones.
• t 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.

• 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 240 encryptions: Guess the contents of the first two LFSRs, then try to determine the third LFSR from the keystream.
• 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.

Hughes XPD/KPD

• This algorithm is brought to you by Hughes Aircraft Corp. They put it in army tactical 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.
• The algorithm uses a 61-bit LFSR. There are 210 different primitive feedback polynomials, which were approved by the NSA. The key selects one of these polynomials (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.

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 presumably for other uses as well.
• 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(x1,x2,x3,x4,x5) = x1 + x2 + (x1 + x3) (x2 + x4 + x5) + (x1 + 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 detailed in the papers. This algorithm is only available in hardware.

Rambutan

• 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 module 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 112-bit key (plus parity bits) and can operate in three modes: ECB, CBC, and 8-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.

Additive Generators

• Additive generators (sometimes called lagged Fibonacci generators) are extremely efficient because they produce random words instead of random bits . They are not secure on their own, but can be used as building blocks for secure generators.
• The initial state of the generator is an array of n-bit words: 8-bit words, 16-bit words, 32-bit words, whatever: X1, X2, X3,..., Xm. This initial state is the key. The ith word of the generator is

Xi = (Xi-a + Xi-b + Xi-c +...+ Xi-m) mod 2ⁿ

• If the coefficients a, b, c,..., m are chosen right, the period of this generator is at least 2n - 1. One of the requirements on the coefficients is that the least significant bit forms a maximal-length LFSR.

Gifford

• The algorithm has a single 8-byte register: b0, b1,..., b7. The key is the initial state of the register. The algorithm works in OFB; the plaintext does not affect the algorithm at all.
• To generate a key byte ki, concatenate b0 and b2 and concatenate b4 and b7. Multiply the two together to get a 32-bit number. The third byte from the left is ki . To update the register, take b1 and sticky right shift it 1 bit. This means the left-most bit is both shifted and also remains in place. Take b7 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 b1, the modified b7, and b0. Shift the original register 1 byte to the right and put this byte in the left-most position.

Algorithm M

#define ARR_SIZE (8192) /* for example — the larger the better */

static unsigned char delay[ ARR_SIZE ] ;

unsigned char prngA( void ) ;

long prngB( void ) ;

void init_algM( void )

{

long i ;

for ( i = 0 ; i < ARR_SIZE ; i++ )

delay = prngA() ;

} /* init_algM */

unsigned char algM( void )

{

long j,v ;

j = prngB() % ARR_SIZE ; /* get the delay[] index */

v = delay[j] ; /* get the value to return */

delay[j] = prngA() ; /* replace it */

return ( v ) ;

} /* algM */

PKZIP

• Roger Schlafly designed the encryption algorithm built into the PKZIP data compression program. It’s a stream cipher that encrypts data one byte at a time.
• The algorithm uses three 32-bit variables, initialized as follows: K0 = 305419896 K1 = 591751049 K2 = 878082192
• It has an 8-bit key, K3, derived from K2. Here is the algorithm (all symbols are standard C notation):

• Ci = Pi ^ K3
• K0 = crc32 (K0, Pi )
• K1 = K1 + (K0 & 0×000000ff)
• K1 = K1 * 134775813 + 1
• K2 = crc32 (K2, K1 >> 24)
• K3 = ((K2 | 2) * ((K2 | 2) ^ 1)) >> 8