UNIT - II

SYMMETRIC CIPHERS
Topics to be covered
• Number theory – Algebraic Structures – Modular
Arithmetic - Euclid‘s algorithm – Congruence and
matrices – Group, Rings, Fields, Finite Fields
• SYMMETRIC KEY CIPHERS: SDES – Block Ciphers
– DES, Strength of DES – Differential and linear
cryptanalysis – Block cipher design principles –
Block cipher mode of operation – Evaluation
criteria for AES – Pseudorandom Number
Generators – RC4 – Key distribution.
Algebraic Structures
• Cryptography requires set of integers and
specific operations that are defined for those
sets
• The combination of the set and the operations
that are applied to the elements of the set is
called as algebraic structure
Number Theory
• Modern cryptography is based on Number Theory, a
branch of mathematics concerned with the properties of
integers.
• In order to understand how modern cryptographic
techniques work, and to estimate the extent to which they
are secure, it is important to understand the basics of
number theory.
 Divisibility and Divisors
• A nonzero b divides a if a = mb for some m, where a, b, and m are integers. That is, b divides a if there is no
remainder on division. The notation b a is commonly used to mean b divides a. Also, if b|a, we say that b is a
divisor of a.
Divisibility and Divisors
• A nonzero b divides a if a = mb for some m, where a, b, and m are
integers. That is, b divides a if there is no remainder on division.
The notation b a is commonly used to mean b divides a. Also, if b|a,
we say that b is a divisor of a.
• Here are some relations:
1) If a|1, then a = ± 1
2) If a|b and b|a, then a = ± b
3) Any divides 0
4) If b|g and b|h, then b|(mg + nh) for arbitrary integers m and n
5) If a|b and b|c, then a|c
6) If n is a positive number > 1, and d is the smallest divisor of n that is greater
than 1, then d is prime.

6
The Division Algorithm
• Given any positive integer n and any nonnegative integer a, if we divide a by n, we get an integer quotient q
and an integer remainder r that obey the following relationship:
 THE EUCLIDEAN ALGORITHM
• Euclidean algorithm, is a simple procedure for determining the greatest common divisor of
two positive integers.
• Two integers are relatively prime if and only if their only common positive integer factor is 1.

• find d = gcd(a, b) = gcd(1160718174, 316258250)

 MODULAR ARITHMETIC
• If a is an integer and n is a positive integer, we define a mod n to be the remainder when a is divided by n. The integer n is
called the modulus.
 Modular Arithmetic
⮚ define modulo operator “a mod n” to be remainder
when a is divided by n
● where integer n is called the modulus
⮚ b is called a residue of a mod n
● since with integers can always write: a = qn + b
● usually chose smallest positive remainder as residue
• ie. 0 <= b < n
● process is known as modulo reduction
•eg. -12 mod 7 = -5 mod 7 = 2
⮚ a & b are congruent if: a mod n ≡ b mod n
● when divided by n, a & b have same remainder
● eg. 100 mod 11 ≡ 34 mod 11
so 100 is congruent to 34 mod 11
 Modular Arithmetic
Operations
⮚ can perform arithmetic with residues
⮚ uses a finite number of values, and loops back
from either end
Zn = {0, 1, . . . , (n – 1)}
⮚ modular arithmetic is when do addition &
multiplication and modulo reduce answer
⮚ can do reduction at any point, ie
● a+b mod n = [a mod n + b mod n] mod n
 Modular Arithmetic
Operations
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) – (b mod n)] mod n = (a – b) mod n
3. [(a mod n) x (b mod n)] mod n = (a x b) mod n
e.g.
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2
(11 + 15) mod 8 = 26 mod 8 = 2
[(11 mod 8) – (15 mod 8)] mod 8 = –4 mod 8 = 4
(11 – 15) mod 8 = –4 mod 8 = 4
[(11 mod 8) x (15 mod 8)] mod 8 = 21 mod 8 = 5
(11 x 15) mod 8 = 165 mod 8 = 5
Modular Arithmetic
Properties
 Euclidean Algorithm
⮚ an efficient way to find the GCD(a,b)
⮚ uses theorem that:
● GCD(a,b) = GCD(b, a mod b)
⮚ Euclidean Algorithm to compute GCD(a,b) is:
Euclid(a,b)
if (b=0) then return a;
else return Euclid(b, a mod b);
 Extended Euclidean
Algorithm
⮚ calculates not only GCD but x & y:
ax + by = d = gcd(a, b)
⮚ useful for later crypto computations
⮚ follow sequence of divisions for GCD but
assume at each step i, can find x &y:
r = ax + by
⮚ at end find GCD value and also x & y
⮚ if GCD(a,b)=1 these values are inverses
 Finding Inverses
EXTENDED EUCLID(m, b)
1. (A1, A2, A3)=(1, 0, m);
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1 mod m
4. Q = A3 div B3
5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
 Inverse of 550 in
GF(1759)
Q A1 A2 A3 B1 B2 B3
— 1 0 1759 0 1 550

3 0 1 550 1 –3 109
5 1 –3 109 –5 16 5
21 –5 16 5 106 –339 4

1 106 –339 4 –111 355 1

355 is inverse of 550
• Find gcd(8976,345) using Euclidean algorithm
• Find the multiplicative inverse of 438 in mod 2567
 Group
⮚ a set S of elements or “numbers” may be finite or infinite
⮚ A group G denoted by {G,.}, is a set under some operation
(.) if it satisfies the CAiN properties
⮚ A group is said to be Abelian if it already a group and
commutative property is also satisfied i.e (a.b) = (b.a) for
all a,b in G
⮚ if commutative a.b = b.a then forms an abelian group
 Cyclic Group
• A group G denoted by {G,.}, is said to be cyclic group, if it
contains atleast one generator element.
Modular Exponentiation
• 23³ mod 30
• 31500 mod 30
• 242329 mod 243
• 887 mod 187
• 295 mod 100
Euler’s Totient Function (Phi Function)

• Euler's Totient function Φ(n)

• for an input n is the count of numbers in {1, 2, 3, …, n-
1} that are relatively prime to n,
• i.e., the numbers whose GCD (Greatest Common Divisor)
with n is 1.
• Eg:Φ(5) , Φ(11), Φ(8)
•
•
• Eg:Φ(5), Φ(31), Φ(35), Φ(1000){find distinct prime
factors}, Φ(7000), Φ(369), Φ(372)
Fermat's Little Theorem

• Does Fermat theorem holds true for p=5, a=2.

• Does Fermat theorem holds true for p=13, a=11.
• Does Fermat theorem holds true for p=6, a=2
• Does Fermat theorem holds true for p=11, a=5
Euler's Theorem

• Prove Euler’s theorem holds true for a=3 & n=10

• Does Euler’s theorem holds true for a=2 & n=10
• Prove Euler’s theorem holds true for a=10 & n=11
Primitive Roots

eg:
Is 2 a primitive root of prime number 5?
Is 3 a primitive root of prime number 7?
Is 2 a primitive root of prime number 7?
What are the primitive roots of number 5?
Polynomial Arithmetic
 add or subtract corresponding coefficients
 multiply all terms by each other, GCD
 eg
let f(x) = x3 + x2 + 2 and g(x) = x2 – x + 1
f(x) + g(x) = x3 + 2x2 – x + 3
f(x) – g(x) = x3 + x + 1
f(x) x g(x) = x5 + 3x2 – 2x + 2
The Chinese Remainder Theorem
 Stream Ciphers and Block
•
Ciphers
A stream cipher is one that encrypts a digital data
stream one bit or one byte at a time. E.g:Vigenère cipher
and the Vernam cipher.

A block cipher is one in which a block of plaintext is

treated as a whole and used to produce a cipher text
block of equal length. Typically, a block size of 64 or
128 bits is used.
 The Feistel Cipher
 Claude Shannon introduced idea of substitution-permutation (S-
P) networks in 1949 paper
 form basis of modern block ciphers
 S-P nets are based on the two primitive cryptographic
operations seen before:
 substitution (S-box)
 permutation (P-box)
• Substitution: Each plaintext element or group of elements is
uniquely replaced by a corresponding ciphertext element or
group of elements.
• Permutation: A sequence of plaintext elements is replaced by
a permutation of that sequence. That is, no elements are added
or deleted or replaced in the sequence, rather the order in
which the elements appear in the sequence is changed.
The Feistel Cipher
• Diffusion means that if we change a character of the
plaintext, then several characters of the ciphertext
should change, and similarly, if we change a character
of the ciphertext, then several characters of the
plaintext should change.
• Confusion means that the key does not relate in a
simple way to the ciphertext. In particular, each
character of the ciphertext should depend on several
parts of the key.
Feistel Cipher Structure
 Feistel Cipher Design
Elements
 block size(usually 64 bits)
 key size (64 bit or 128 bit)
 number of rounds
 subkey generation algorithm
 round function
 fast software en/decryption
 ease of analysis
 SDES
• The overall structure of the simplified DES. The S-DES encryption
algorithm takes an 8-bit block of plaintext (example: 10111101) and a 10-
bit key as input and produces an 8-bit block of ciphertext as output.
• The S-DES decryption algorithm takes an 8-bit block of ciphertext and
the same 10-bit key used to produce that ciphertext as input and produces
the original 8-bit block of plaintext.
SDES
 SDES
• Generate K1 & K2
• Apply Initial Permutation on plain text
• Apply EP(Expansion permutation) on second half bit of IP
• Perform EP XOR k1
• Split first 4bits as S0 & second 4bits as S1
• Then from matrix S0 & S1 obtain the row column values and
output will be 4 bits
• Apply P4 on the 4 bits
• P4 xor (S0S1) xor first 4bits of IP
• merge above 4 bit output & last 4 bits of IP
• Swap first 4 bits & last 4 bits
• This is output of Round 1
 Data Encryption Standard
(DES)
 most widely used block cipher in world
 adopted in 1977 by NBS (now NIST)
 encrypts 64-bit data using 56-bit key
 has widespread use
 has been considerable controversy over its security
 DES History
 IBM developed Lucifer cipher
by team led by Feistel in late 60’s
used 64-bit data blocks with 128-bit key
 then redeveloped as a commercial cipher with input
from NSA and others
 in 1973 NBS issued request for proposals for a
national cipher standard
 IBM submitted their revised Lucifer which was
eventually accepted as the DES
THE DATA ENCRYPTION STANDARD
• DES is based on the Feistel block cipher, called LUCIFER,
developed in 1971 by IBM cryptography researcher Horst
Feistel. DES uses 16 rounds of the Feistel structure, using a
different key for each round.
• DES stands for Data Encryption Standard.
• The DES algorithm uses a key of 64-bit size.
• 16 Number of sub keys of 48 bits will be used
• Using this key, the DES takes a block of 64-bit plain text as input
and generates a block of 64-bit cipher text.
• The DES process has several steps involved in it, where each
step is called a round. Depending upon the size of the key being
used, the number of rounds varies. For example, a 128-bit key
requires 10 rounds, a 192-bit key requires 12 rounds, and so on.
• Initial Permutation (IP) :The IP is performed before the
first round. This phase describes the implementation of
the transposition process. For example, the 58th bit
replaces the first bit, the 50th bit replaces the second bit,
and so on. The resultant 64-bit text is split into two equal
halves of 32-bit each called Left Plain Text (LPT) and Right
Plain Text (RPT).
 DES Round Structure
 uses two 32-bit L & R halves
 as for any Feistel cipher can describe as:
Li = Ri–1
Ri = Li–1 F(Ri–1, Ki)
 F takes 32-bit R half and 48-bit subkey:
expands R to 48-bits using perm E
adds to subkey using XOR
passes through 8 S-boxes to get 32-bit result
finally permutes using 32-bit perm P
Expansion Permutation
 Substitution Boxes S
 have eight S-boxes which map 6 to 4 bits
 each S-box is actually 4 little 4 bit boxes
outer bits 1 & 6 (row bits) select one row of 4
inner bits 2-5 (col bits) are substituted
result is 8 lots of 4 bits, or 32 bits
 row selection depends on both data & key
feature known as autoclaving (autokeying)
 example:
S(18 09 12 3d 11 17 38 39) = 5fd25e03
Substitution Boxes S
 each of the eight s-boxes is
different
input symbol  each s-box reduces 6 bits to
control 4 bits
Si  so the 8 s-boxes implement
the 48-bit to 32-bit
output symbol contraction substitution
 Permutation Box P
S1 S2 S3 S4 S5 S6 S7 S8

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

 P-box at end of each round

 Increases diffusion/avalanche effect
• Key Transformation: DES process uses a 56-bit key,
which is obtained by eliminating all the bits present in
every 8th position in a 64-bit key. In this step, a 48-bit
key is generated. The 56-bit key is split into two equal
halves and depending upon the number of rounds the
bits are shifted to the left in a circular fashion.
Permutation
Initial Inverse Permutation
 Avalanche Effect
 key desirable property of encryption algorithm
 where a change of one input or key bit results in
changing approx half output bits
 1 bit change in plain text => 34 bit in cyber text
 1 bit change in key text => 35 bit in cyber text
 making attempts to “home-in” by guessing keys
impossible
 DES exhibits strong avalanche
 Strength of DES – Key
Size 16
 56-bit keys have 2 = 7.2 x 10 values
56

 brute force search looks hard

 One DES encryption per microsecond then it requires
more than 1000 years to break the cipher
 recent advances have shown is possible
in 1997 on Internet in a few months
in 1998 on dedicated h/w (EFF) in a few days
in 1999 above combined in 22hrs!
 DES cracker is available for $250000 to break in 3
days
 still must be able to recognize plaintext
 Strength of DES – Analytic
Attacks
 now have several analytic attacks on DES
 these utilise some deep structure of the cipher
by gathering information about encryptions
can eventually recover some/all of the sub-key bits
if necessary then exhaustively search for the rest
 generally these are statistical attacks
differential cryptanalysis
linear cryptanalysis
related key attacks
 Strength of DES – Timing
Attacks
 attacks actual implementation of cipher
 use knowledge of consequences of
implementation to derive information about
some/all subkey bits
 specifically use fact that calculations can take
varying times depending on the value of the
inputs to it
 particularly problematic on smartcards
 Differential Cryptanalysis
 one of the most significant recent (public) advances
in cryptanalysis
 known by NSA in 70's cf DES design
 Murphy, Biham & Shamir published in 90’s
 powerful method to analyse block ciphers
 used to analyse most current block ciphers with
varying degrees of success
 Differential Cryptanalysis
 a statistical attack against Feistel ciphers
 uses cipher structure not previously used
 design of S-P networks has output of function f
influenced by both input & key
 hence cannot trace values back through cipher
without knowing value of the key
 differential cryptanalysis “eliminates” key by using
differenced input
 Differential Cryptanalysis
Compares Pairs of
Encryptions
 differential cryptanalysis compares two related pairs
of encryptions
 with a known difference in the input
 searching for a known difference in output
 when same subkeys are used
 Differential Cryptanalysis
Compares Pairs of
Encryptions
 Let mi-1 be the left half of the input to round i, and mi
be the right half

 f(mi,Ki) = P(S(Ki XOR E(mi))), where P is the PBox

transposition, S is the Sbox substitution, and E is the
expansion perm.
 Differential Cryptanalysis
Takes Advantage of
Linearity
 f(mi,Ki) = P(S(Ki XOR E(mi))), where P is the PBox
transposition, S is the Sbox substitution, and E is the
expansion perm.
 So E(mi) XOR E(m’i) = E(mi XOR m’i), i.e., the
expansion permutation preserves differences (E is
linear)
 XOR with Ki also preserves differences
 E changes the input in a known way, so difference
changes in known way
 Differential Cryptanalysis
Takes Advantage of Non-
Uniformity
 For all pairs of inputs with the same difference,
compute differences in output
 Build a table with Δx as row index and Δy as column
index, with frequency in cells (i.e., T(Δx,Δy) = # times
inputs x and x’ have outputs y and y’
 with Δx = x XOR x’ and Δy = y XOR y’
 Rows have non-uniformity, so some output
differences are more likely than others for a given
input difference
 Differential Cryptanalysis
 have some input difference giving some output
difference with probability p
 if find instances of some higher probability input /
output difference pairs occurring
 can infer subkey that was used in round
 then must iterate process over many rounds (with
decreasing probabilities)
Differential Cryptanalysis
 Differential Cryptanalysis
 perform attack by repeatedly encrypting plaintext pairs with known
input XOR until obtain desired output XOR
 when found
 if intermediate rounds match required XOR have a right pair
 if not then have a wrong pair, relative ratio is S/N for attack
 can then deduce keys values for the rounds
 right pairs suggest same key bits
 wrong pairs give random values
 for large numbers of rounds, probability is so low that more pairs are
required than exist with 64-bit inputs
 Biham and Shamir have shown how a 13-round iterated
characteristic can break the full 16-round DES
 Linear Cryptanalysis
 another recent development
 also a statistical method
 must be iterated over rounds, with decreasing
probabilities
 developed by Matsui et al in early 90's
 based on finding linear approximations
 can attack DES with 243 known plaintexts, easier but
still in practise infeasible
 Linear Cryptanalysis
 find linear approximations with prob p != ½
P[i1,i2,...,ia]  C[j1,j2,...,jb] = K[k1,k2,...,kc]
where ia,jb,kc are bit locations in P,C,K
 gives linear equation for key bits
 get one key bit using max likelihood alg
 using a large number of trial encryptions
 effectiveness given by: |p–1/2|
 DES Design Criteria
 as reported by Coppersmith in
[COPP94]
 7 criteria for S-boxes provide for
non-linearity
resistance to differential cryptanalysis
good confusion
 3 criteria for permutation P provide
for
increased diffusion
 Block Cipher Design
 basic principles still like Feistel’s in 1970’s
 number of rounds
more is better – make exhaustive search best attack
 function f:
provides “confusion”, is nonlinear, avalanche
have issues of how S-boxes are selected
 key schedule
complex subkey creation, key avalanche
BLOCK CIPHER MODES OF OPERATION
• ECB(Electronic Code Book)
• CBC(Cipher Block Chaining)
• OFB(Output FeedBack)
• CFB(Cipher FeedBack Mode)
• Counter Mode
ECB(Electronic Code Book)
CBC(Cipher Block Chaining)
OFB(Output FeedBack)
CFB(Cipher FeedBack Mode)
Counter Mode
Triple DES
• Drawbacks of DES
• Potential vulnerability of DES to a brute-force attack
• Use of multiple encryption with DES and multiple keys
• Double DES
Triple DES

• Brute force not practically possible

• Very slow for software implementation
 AES
(Advanced
Encryption
Standard)
 The AES Cipher - Rijndael
 designed by Rijmen-Daemen in Belgium
 has 128/192/256 bit keys, 128 bit data
 an iterative rather than Feistel cipher

processes data as block of 4 columns of 4 bytes

operates on entire data block in every round
 designed to have:

resistance against known attacks

speed and code compactness on many CPUs

design simplicity
AES Parameters
 AES
Encryptio
n Process
AES Structure
 AES Structure
 data block of 4 columns of 4 bytes is state
 key is expanded to array of words
 has 9/11/13 rounds in which state undergoes:

byte substitution (1 S-box used on every byte)

shift rows (permute bytes between groups/columns)

mix columns (subs using GF(28)

add round key (XOR with current block & portion of
expanded key)

view as alternating XOR key & scramble data bytes
 initial XOR key material & incomplete last round
 with fast XOR & table lookup implementation
 Some Comments on AES
1. an iterative rather than Feistel cipher
2. key expanded into array of 32-bit words four
words form round key in each round
3. 4 different stages are used as shown has a
simple structure
4. only AddRoundKey uses key
5. AddRoundKey a form of Vernam cipher
6. each stage is easily reversible
7. decryption uses keys in reverse order
8. decryption does recover plaintext
9. final round has only 3 stages
AES Round
 Substitute Bytes
 a simple substitution of each byte
 uses one table of 16x16 bytes containing a permutation of
all 256 8-bit values
 each byte of state is replaced by byte indexed by row (left
4-bits) & column (right 4-bits)

eg. byte {95} is replaced by byte in row 9 column 5

which has value {2A}
 S-box constructed using defined transformation of values in
GF(28) [Multiplicative Inverse]
 designed to be resistant to all known attacks
Substitute Bytes
S-Box
 Shift Rows
 a circular byte shift in each row

1st row is unchanged

2nd row does 1 byte circular shift to left

3rd row does 2 byte circular shift to left

4th row does 3 byte circular shift to left
 decrypt inverts using shifts to right
 since state is processed by columns, this step
permutes bytes between the columns
Shift Rows
 Mix Columns
 each column is processed separately
 each byte is replaced by a value dependent on all
4 bytes in the column
 effectively a matrix multiplication in GF(2 8) using
prime poly m(x) =x8+x4+x3+x+1
Mix Columns
Mix columns Transformation
Mix Columns Example
 Mix Columns
 can express each col as 4 equations

to derive each new byte in col
 decryption requires use of inverse matrix

with larger coefficients, hence a little harder
 have an alternate characterisation

each column a 4-term polynomial

with coefficients in GF(28)

and polynomials multiplied modulo (x4+1)
 coefficients based on linear code with maximal distance
between codewords
 Add Round Key
 XOR state with 128-bits of the round key
 again processed by column (though effectively a
series of byte operations)
 inverse for decryption identical

since XOR own inverse, with reversed keys
 designed to be as simple as possible

a form of Vernam cipher on expanded key

requires other stages for complexity / security
Add Round Key
 AES Key Expansion
 takes 128-bit (16-byte) key and
expands into array of 44/52/60 32-bit
words
 start by copying key into first 4 words
 then loop creating words that depend
on values in previous & 4 places back

in 3 of 4 cases just XOR these together

1st word in 4 has rotate + S-box + XOR
round constant on previous, before XOR
4th back
AES Key Expansion
Pseudorandom Number
Generator
 Random Numbers
 many uses of random numbers in cryptography

nonces in authentication protocols to prevent replay

session keys

public key generation

keystream for a one-time pad
 in all cases its critical that these values be

statistically random, uniform distribution, independent

unpredictability of future values from previous values
 true random numbers provide this
 care needed with generated random numbers
 Pseudorandom Number Generators
(PRNGs)
 oftenuse deterministic algorithmic techniques to
create “random numbers”

although are not truly random

can pass many tests of “randomness”
 known as “pseudorandom numbers”
 created by “Pseudorandom Number Generators
(PRNGs)”
Random & Pseudorandom
Number Generators
 PRNG Requirements
 randomness

uniformity, scalability, consistency
 unpredictability

forward & backward unpredictability

use same tests to check
 characteristics of the seed

secure

if known adversary can determine output

so must be random or pseudorandom
number
 PRNG Requirements
 Randomness

Uniformity – at any point in the generation of the PRN
sequence, the occurrence of a zero or a one is equally
likely (i.e., p = 0.5)

Scalability – any test for randomness applicable to a
sequence can also be applied to any random
subsequence (it should pass)

Consistency – the characteristics of the PRN sequence of
the PRNG must not depend on the seed used
 Linear Congruential Generator
 common iterative technique using:
Xn+1 = (aXn + c) mod m
 given suitable values of parameters can produce a long
random-like sequence
 suitable criteria to have are:

function generates a full-period

generated sequence should appear random

efficient implementation with 32-bit arithmetic
 note that an attacker can reconstruct sequence given a
small number of values
 have possibilities for making this harder
 E.g X0=27; a=17; c=43; m=100;
 Blum Blum Shub
Generator
 based on public key algorithms
 use least significant bit from iterative equation:

xi = xi-12 mod n

where n=p.q, and primes p,q=3 mod 4
 unpredictable, passes next-bit test
 security rests on difficulty of factoring N
 is unpredictable given any run of bits
 slow, since very large numbers must be used
 too slow for cipher use, good for key generation
 Using Block Ciphers as

PRNGs
for cryptographic applications, can use a block cipher
to generate random numbers
 often for creating session keys from master key
 CTR
Xi = EK[Vi]
 OFB
Xi = EK[Xi-1]
 Stream Ciphers
 process message bit by bit (as a stream)
 have a pseudo random keystream
 combined (XOR) with plaintext bit by bit
 randomness of stream key completely
destroys statistically properties in message

Ci = Mi XOR StreamKeyi
 but must never reuse stream key

otherwise can recover messages (cf book cipher)
Stream Cipher Structure
 Stream Cipher Properties
 some design considerations are:

long period with no repetitions

statistically random

depends on large enough key

large linear complexity
 properly designed, can be as secure as a
block cipher with same size key
 but usually simpler & faster
 RC4
a proprietary cipher owned by RSA DSI
 another Ron Rivest design, simple but
effective
 variable key size, byte-oriented stream
cipher
 widely used (web SSL/TLS, wireless
WEP/WPA)
 key forms random permutation of all 8-bit
values
 uses that permutation to scramble input
 RC4 Key Schedule
 startswith an array S of numbers: 0..255
 use key to well and truly shuffle
 S forms internal state of the cipher
for i = 0 to 255 do
S[i] = i // init S to identity
T[i] = K[i mod keylen]) // extend key
j=0 // location of swap
for i = 0 to 255 do // for each element
// update location of swap
j = (j + S[i] + T[i]) (mod 256)
swap (S[i], S[j]) // permute
 RC4 Encryption
 encryption continues shuffling array values
 sum of shuffled pair selects "stream key" value from
permutation
 XOR S[t] with next byte of message to en/decrypt
i=j=0
for each message byte Mi
i = (i + 1) (mod 256) // rotate thru S
j = (j + S[i]) (mod 256) // update swap location
swap(S[i], S[j]) // update permutation S
t = (S[i] + S[j]) (mod 256) // pick key index
Ci = Mi XOR S[t] // encrypt
 update
extend key
permutation
RC4 Overview

initialize shuffle
permutation permutation
 RC4 Security
 claimed secure against known attacks

However, have some analyses, some on the verge of
practical

first 256 bytes have bias

multiple keys/same plaintext attack
 resultis very non-linear
 since RC4 is a stream cipher, must never reuse a
key
 have a concern with WEP, but due to key handling
rather than RC4 itself
 RC4 Security

Probability of recovery of plaintext from 2 24 ciphertexts vs. byte position

 Natural Random Noise
 best source is natural randomness in real world
 find a regular but random event and monitor
 do generally need special h/w to do this

eg. radiation counters, radio noise, audio noise,
thermal noise in diodes, leaky capacitors, mercury
discharge tubes etc
 starting to see such h/w in new CPUs
– Intel Ivy Bridge, Via Padlock
 problems of bias or uneven distribution in signal

have to compensate for this when sample, often by
passing bits through a hash function

best to only use a few noisiest bits from each sample

RFC4086 recommends using multiple sources + hash
 Intel Ivy Bridge TRNG
Entropy Source
- shared by all cores Detect when
- RS-NOR latch settled, and
becomes metastable store output
when input
De-asserted
- Output settles to 0 or 1, RS-NOR
depending on thermal latch
Noise
- Feedback helps reach
Metastable state Negative
- Output detects when feedback
settled, stores result,
reasserts input Entropy Source
http://electronicdesign.com/learning-resources/understanding-intels-ivy-bridge-random-number-generator
 Intel Ivy Bridge TRNG

DRNG output fed to all processors

hardware instruction-level access
https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide
Intel Ivy Bridge TRNG
- Output is biased
due to feedback
- 800 MHz clock
Conditioner
outputs 256 bits
every few
microseconds
Expand rate using
NIST SP800-90
PRNG to rate of
800 MBps
 Intel Ivy Bridge TRNG

Built-In
Self Test

Health tests are basic, ad hoc, but detect RNG failure

Output zero with carry zero on failure (can't read a 0)
 Trustworthiness of TRNGs
 Design appears to be very sound
 Possible back doors

Snowden leaks show NSA coerced hardware and
software manufacturers to introduce back doors

Intel and Via hardware considered suspect
 Approach by FreeBSD

Use hardware PRNG as a source

Pass through Yarrow PRNG algorithm when
producing cryptographically significant random
numbers
See: https://www.schneier.com/paper-yarrow.pdf
 Published Sources
 a few published collections of random numbers
 Rand Co, in 1955, published 1 million numbers

generated using an electronic roulette wheel

has been used in some cipher designs cf Khafre
 earlier Tippett in 1927 published a collection
 issues are that:

these are limited

too well-known for most uses
 Summary
 pseudorandom number generation
 stream ciphers
 RC4
 true random numbers
 Cyclic Group
⮚ define exponentiation as repeated
application of operator
●example: a3 = a.a.a
⮚ and let identity be: e=a0
⮚ a group is cyclic if every element is a
power of some fixed element a
●i.e., b = ak for some a and every b in
group
⮚ a is said to be a generator of the group
 Ring
⮚ a set of “numbers”
⮚ with two operations (addition and multiplication) which
form:
⮚ an abelian group with addition operation
⮚ and multiplication:
● has closure
● is associative
● distributive over addition: a(b+c) = ab + ac
⮚ if multiplication operation is commutative, it forms a
commutative ring
⮚ if multiplication operation has an identity and no zero
divisors, it forms an integral domain
 Field
⮚ a set of numbers
⮚ with two operations which form:
●abelian group for addition
●abelian group for multiplication (ignoring 0)
●ring
⮚ have hierarchy with more axioms/laws
●group -> ring -> field
Group, Ring, Field
 Finite (Galois) Fields
⮚ finite fields play a key role in cryptography
⮚ can show number of elements in a finite field
must be a power of a prime pn
⮚ known as Galois fields
⮚ denoted GF(pn)
⮚ in particular often use the fields:
●GF(p)
●GF(2n)
 Prime Numbers
• A positive integer p is called prime if it has just two
divisors: 1 and p
• A positive integer that has three or more divisors is known
as a composite.
• Every integer > 1 is either prime or composite, but not both.
• Note:
• 2 is a prime
• 1 is not a prime
• The sequence of primes starts:
2,3,5,7,11,13,17,19,23,29,31,37,41,...
149