ADVANCED NETWORK SECURITY
Lecture 6 – Stream Ciphers and Random Numbers
M UHAMMAD Z ESHAN Q URASHI
D EPARTMENT OF C OMPUTER S CIENCE
F UUAST,I SLAMABAD
Outline
Random Numbers
◦ Classical Random Number Generators
Stream Ciphers
31-Jan-20 ADVANCED NETWORK SECURITY 2
Introduction
Truly random - is defined as exhibiting ``true'' randomness, such as radiation count, atmospheric
noise, etc.
◦ For Example
◦ a Geiger counter, is a type of particle detector that measures ionizing radiation. It detects the emission
of nuclear radiation — alpha particles, beta particles, and gamma rays — by the ionization produced in a
low-pressure gas in a Geiger–Müller tube[1], which gives its name to the instrument.
Pseudorandom - is defined as having the appearance of randomness, but nevertheless
exhibiting a specific, repeatable pattern.
◦ Random numbers used in programming
◦ PRNG: Pseudo-Random Number Generator
31-Jan-20 ADVANCED NETWORK SECURITY 3
PseudoRandom Numbers
PRN:
◦ Given knowledge of the algorithm used to create the numbers and its internal state (i.e. seed), you can
predict all the numbers returned by subsequent calls to the algorithm,
whereas with truly random numbers, knowledge of one number or an arbitrarily long sequence
of numbers is of no use whatsoever in predicting the next number to be generated.
Computer-generated "random" numbers are more properly referred to as pseudorandom
numbers, and pseudorandom sequences of such numbers.
numbers calculated by a computer through a
deterministic process, cannot, by definition, be random
31-Jan-20 ADVANCED NETWORK SECURITY 4
Random Numbers Usage
Almost all network security protocols rely on the randomness of certain parameters
◦ Nonce - used to avoid replay
◦ Session key
◦ Unique parameters in digital signatures
31-Jan-20 ADVANCED NETWORK SECURITY 5
Desirable Properties of PRN
◦ Uncorrelated Sequences - The sequences of random numbers should be
serially uncorrelated
◦ Long Period - The generator should be of long period (ideally, the generator
should not repeat; practically, the repetition should occur only after the
generation of a very large set of random numbers).
◦ Uniformity - The sequence of random numbers should be uniform, and
unbiased.
◦ E.g. the occurrence of numbers (0 or 1) is equally likely. Probability should be half for each
0 or 1.
◦ Efficiency - The generator should be efficient. Low overhead for massively
parallel computations.
31-Jan-20 ADVANCED NETWORK SECURITY 6
The Random Number Cycle
Almost all random number generators have, as their
basis, a sequence of pseudorandom integers
The integers or ``fixed point'' numbers are manipulated
arithmetically to yield floating point or ``real'' numbers.
The Nature of the cycle
◦ the sequence has a finite number of integers
◦ the sequence gets traversed in a particular order
◦ the sequence repeats if the period of the generator
is reached
◦ the integers need not be distinct; that is, they may
repeat.
31-Jan-20 ADVANCED NETWORK SECURITY 7
Classical PseudoRandom Number Generators
Midsquare method
Linear Congruential generator
Linear Feedback Shift Register
31-Jan-20 ADVANCED NETWORK SECURITY 8
Classical PRNG – MidSquare Method
MidSquare Method Steps
1. Start with an initial seed (e.g. a 4-digit integer).
2. Square the number.
3. Take the middle 4 digits. This value becomes the new seed.
1. Divide the number by 10,000. The result becomes the random number.
2. Repeat Step 2.
31-Jan-20 ADVANCED NETWORK SECURITY 9
MidSquare Method Example
x0 = 5497
x1: 54972 = 30217009 x1 = 2170, R1 = 0.2170
x : 21702 = 04708900 x = 7089, R = 0.7089
2 2 2
x3: 70892 = 50253921 x3 = 2539, R3 = 0.2539
Drawback: Hard to state conditions for picking initial seed that will generate a “good” sequence.
◦ For example, see next slide
31-Jan-20 ADVANCED NETWORK SECURITY 10
MidSquare Example
“Bad” sequences:
x0 = 5197
x1: 51972 = 27008809 x1 = 0088, R1 = 0.0088
x2: 00882 = 00007744 x2 = 0077, R2 = 0.0077
x3: 00772 = 00005929 x3 = 0059, R3 = 0.0059
xi = 6500
xi+1: 65002=42250000 xi+1=2500, Ri+1= 0.0088
xi+2: 25002=06250000 xi+2=2500, Ri+1= 0.0088
31-Jan-20 ADVANCED NETWORK SECURITY 11
Linear Congruential Generators (LCG)
LCG was proposed by Lehmer in 1949.
LCG is one most commonly used for generating random integers (aka randu() )
Next random (sequence) integer is generated using the previous random integer , the integer constants, and
the integer modulus
To get started, the algorithm requires an initial “seed” (X0), which must be provided by some means.
We refer to the sequence generated as
The appearance of randomness is provided by performing modulo arithmetic or remaindering
Note that the next result, depends upon only the previous integer – it minimizes storage requirements
31-Jan-20 ADVANCED NETWORK SECURITY 12
LCG
Let Zi be the ith number (integer) in the sequence
Zi = (aZi-1+c) mod (m) Zi{0,1,2,…,m-1}
where Z0 = seed
a = multiplier
c = increment/counter
m = modulus
Define Ri = Zi /m (to obtain R(0,1) value)
When c = 0 ; Multiplicative LCG
When c > 0 ; Mixed LCG
31-Jan-20 ADVANCED NETWORK SECURITY 13
LCG Example
16-bit machine
a = 1217 c = 0 Z0 = 23 m = 215-1 = 32767
Z1 = (1217*23) mod 32767 = 27991
R1 = 27991/32767 = 0.85424
Z2 = (1217*27991) mod 32767 = 20134
R2 = 20134/32767 = 0.61446
31-Jan-20 ADVANCED NETWORK SECURITY 14
Linear Feedback Shift Register (LFSR)
In computing, a LFSR is a shift register whose input bit is a linear function of its previous
state.
The most commonly used linear function of single bits is XOR. Thus, an LFSR is most often a
shift register whose input bit is driven by the exclusive-or (XOR) of some bits of the overall
shift register value.
31-Jan-20 ADVANCED NETWORK SECURITY 15
LFSR
The initial value of the LFSR is called the seed, and because the operation of the register is
deterministic, the stream of values produced by the register is completely determined by its
current (or previous) state.
However, an LFSR with a well-chosen feedback function can produce a sequence of bits which
appears random and which has a very long cycle.
F(x) = x15 + x13 + x12 + x10 + 1
31-Jan-20 ADVANCED NETWORK SECURITY 16
Stream Ciphers
31-Jan-20 ADVANCED NETWORK SECURITY 17
RC4
A symmetric key encryption algorithm invented by Ron Rivest
◦ A proprietary cipher owned by RSA Data Security Inc. , kept secret
◦ Code released anonymously in Cyberpunks mailing list in 1994
◦ Later posted sci.crypt newsgroup
Variable key size, byte-oriented stream cipher
◦ Normally uses 64 bit and 128 bit key sizes.
Used in
◦ SSL/TLS (Secure socket, transport layer security) between web browsers and servers,
◦ IEEE 802.11 wirelss LAN std:
◦ WEP (Wired Equivalent Privacy), WPA (WiFi Protocol Access) protocol
31-Jan-20 ADVANCED NETWORK SECURITY 18
RC4 Usages
WEP
WPA default
Bit Torrent Protocol Encryption
Microsoft Point-to-Point Encryption
SSL (optionally)
SSH (optionally)
Remote Desktop Protocol
Kerberos (optionally)
31-Jan-20 ADVANCED NETWORK SECURITY 19
RC4 Block Diagram
Secret Key
RC4
Keystream
Encrypted
Plain Text + Text
Cryptographically very strong and easy to implement
31-Jan-20 ADVANCED NETWORK SECURITY 20
Inside RC4
Consists of 2 parts:
◦ Key Scheduling Algorithm (KSA)
◦ Pseudo-Random Generation Algorithm
(PRGA)
KSA
◦ Generate State array KSA
PRGA on the KSA PRGA
◦ Generate keystream
◦ XOR keystream with the data to generated
encrypted stream
31-Jan-20 ADVANCED NETWORK SECURITY 21
RC4 – Key Scheduling Algorithm KSA
Use the secret key to initialize and permutation of state vector S, done
in two steps
Use 8-bit index pointers i and j
1 2
j = 0;
for i = 0 to 255 do for i = 0 to 255 do
S[i] = i; j = (j+S[i]+K[i])mod 256
K[i] = Key[i mod |K|] swap (S[i], S[j])
[S], S is set equal to the values from 0 to 255
S[0]=0, S[1]=1,…, S[255]=255 • Use T to produce initial permutation of S
[K], Array of bytes of secret key • The only operation on S is a swap;
|K| = Keylen, Length of (K)
After KSA, the input key and the temporary vector T will be no longer used
31-Jan-20 ADVANCED NETWORK SECURITY 22
RC4 - PRGA
Generate key stream k , one by one
XOR S[k] with next byte of message to encrypt/decrypt
i = j = 0;
While (more_byte_to_encrypt)
i = (i + 1) (mod 256);
j = (j + S[i]) (mod 256);
swap(S[i], S[j]);
k = (S[i] + S[j]) (mod 256);
Ci = Mi XOR S[k];
Sum of shuffled pair selects "stream key" value
from permutation
31-Jan-20 ADVANCED NETWORK SECURITY 23
RC4 Lookup Stage
The output byte is selected by looking up the values of S[i] and S[j], adding them together
modulo 256, and then looking up the sum in S
S [S[i] + S[j]] is used as a byte of the key stream, K
i = j = 0;
While (more_byte_to_encrypt)
i = (i + 1) (mod 256);
j = (j + S[i]) (mod 256);
swap(S[i], S[j]);
k = (S[i] + S[j]) (mod 256);
Ci = Mi XOR S[k];
http://en.wikipedia.org/wiki/File:RC4.svg
31-Jan-20 ADVANCED NETWORK SECURITY 24
RC4 Overall Operation
31-Jan-20 ADVANCED NETWORK SECURITY 25
A5/1
Used in Global System for Mobil Communications (GSM).
A5/1 was developed in 1987 and kept secret until it was leaked in 1994 and also reversed
engineered within next 5 years.
A5/2 – weaker cipher used in some countries due to export rules
GSM phone conversations are sent as sequences of frames.
One 228 bit frame is sent every 4.6 milliseconds: 114 bits for the communication in each
direction.
A5/1 produces 228 bits key to XOR with the data frame.
A5/1 is based around a combination of three LFSRs with irregular clocking.
31-Jan-20 ADVANCED NETWORK SECURITY 26
A5/1
19 bits
•x18 + x17 + x16 + x13 + 1
•clock bit 8
•tapped bits: 13, 16, 17, 18
22 bits
•x21 + x20 + 1
•clock bit 10
•tapped bits 20, 21
23 bits
•x22 + x21 + x20 + x7 + 1
•clock bit 10
•tapped bits 7, 20, 21, 22
31-Jan-20 ADVANCED NETWORK SECURITY 27
