CYS201: Modern Cryptography
Lecture 3: Symmetric Cryptography – Stream Ciphers (Part I)
Ciphertext = Keystream ⊕ Plaintext
Dr Iftekhar Salam
[Link]@[Link]
Xiamen Univesity Malaysia
Iftekhar Salam (XMUM) CYS201 1 / 44
Presentation outline
1 Cryptography and Confidentiality
2 Pseudorandomness
3 Intro to Stream Ciphers
4 Pseudorandom Number Generators using LFSRs
5 Stream Cipher Constructions using LFSRs
Iftekhar Salam (XMUM) CYS201 2 / 44
Cryptography and Confidentiality
Presentation Outline
1 Cryptography and Confidentiality
2 Pseudorandomness
3 Intro to Stream Ciphers
4 Pseudorandom Number Generators using LFSRs
5 Stream Cipher Constructions using LFSRs
Iftekhar Salam (XMUM) CYS201 3 / 44
Cryptography and Confidentiality
Confidentiality using Cryptography
Ciphers are used to deliver confidentiality services for information which is:
In storage:
If you can't prevent unauthorized access to data files, then encrypting the files can
prevent unauthorized access to the information (that is, the attacker can't read the
file contents)
Example: Microsoft’s Encrypting File System, BitLocker
During transmission:
Information sent over network communication links can be encrypted to prevent
eavesdroppers gaining unauthorized access to information
Example: SSL/TLS, IPSec, WEP, WPA
Iftekhar Salam (XMUM) CYS201 4 / 44
Cryptography and Confidentiality
Types of Ciphers
Symmetric Ciphers
Also known as secret key cipher
Same key is used for encryption and decryption
The cryptographic key must be kept secret
distribution of key, storage of the key has to be
secure
Example: RC4
Asymmetric Ciphers
Also known as public key cipher
A much newer, radically different approach
Uses two keys
One for encryption Figure: Taxonomy of modern ciphers
And the other for decryption
disclosing one does not compromise the other
Example: RSA
Iftekhar Salam (XMUM) CYS201 5 / 44
Cryptography and Confidentiality
Symmetric Ciphers
The same key (symmetric key) is used at both end
Can be divided into mainly two classes:
Stream cipher
Block cipher
Other methods/modes: Sponge permutations, duplex mode, ...
Iftekhar Salam (XMUM) CYS201 6 / 44
Pseudorandomness
Presentation Outline
1 Cryptography and Confidentiality
2 Pseudorandomness
3 Intro to Stream Ciphers
4 Pseudorandom Number Generators using LFSRs
5 Stream Cipher Constructions using LFSRs
Iftekhar Salam (XMUM) CYS201 7 / 44
Pseudorandomness
Pseudorandomness
Pseudorandom generators (PRGs) are important building blocks for private-key
encryption
Pseudorandomness – important building block for computationally secure
encryption
Important concept in cryptography
Iftekhar Salam (XMUM) CYS201 8 / 44
Pseudorandomness
Pseudorandomness
A property of probability distribution imposed on a set of binary strings of length `, say
S. Consider two probability distributions on the set S:
G: Some probability distribution on S
U: Uniform probability distribution on S
Iftekhar Salam (XMUM) CYS201 9 / 44
Pseudorandomness
Pseudorandomness
A property of probability distribution imposed on a set of binary strings of length `, say
S. Consider two probability distributions on the set S:
G: Some probability distribution on S
U: Uniform probability distribution on S
Then, G is called pseudorandom if a string drawn according to G (called pseudorandom)
is indistinguishable from a string drawn according to U (called random),to a PPT
adversary.
Iftekhar Salam (XMUM) CYS201 9 / 44
Pseudorandomness
Pseudorandom Generator
Let G be a deterministic polynomial-time algorithm such that for any n and any input
s ∈ {0, 1}n , the result G(s) is a string of length `(n). G is a pseudorandom generator if
the following conditions hold:
Expansion : ∀n, `(n) > n
The output of G looks like a uniform string to any PPT observer
Iftekhar Salam (XMUM) CYS201 10 / 44
Pseudorandomness
Pseudorandom Generator
Iftekhar Salam (XMUM) CYS201 11 / 44
Pseudorandomness
Pseudorandom Generator
Iftekhar Salam (XMUM) CYS201 11 / 44
Pseudorandomness
Pseudorandom Generator
Iftekhar Salam (XMUM) CYS201 11 / 44
Pseudorandomness
Pseudorandom Generator
Iftekhar Salam (XMUM) CYS201 11 / 44
Pseudorandomness
Pseudorandom Generator
Iftekhar Salam (XMUM) CYS201 11 / 44
Pseudorandomness
Pseudorandom Generator
Iftekhar Salam (XMUM) CYS201 11 / 44
Pseudorandomness
Pseudorandom Generator
Iftekhar Salam (XMUM) CYS201 11 / 44
Pseudorandomness
Pseudorandom Generator
Let,
A(U ) = 1 be the event that adversary A answers U and it is correct
A(G(s)) = 1 be the event that adversary A answers G and it is correct
Iftekhar Salam (XMUM) CYS201 12 / 44
Pseudorandomness
Pseudorandom Generator
Let,
A(U ) = 1 be the event that adversary A answers U and it is correct
A(G(s)) = 1 be the event that adversary A answers G and it is correct
Definition: Pseudorandom Generator (PRG)
G is a pseudorandom generator, if ∀ PPT adversary A, ∃ a negligible function ε such that
|P r[A(U ) = 1] − P r[A(G(s))]| ≤ ε(n)
Iftekhar Salam (XMUM) CYS201 12 / 44
Pseudorandomness
Is this a Secure PRG?
Ln
Define G(s) to output s followed by i=1 si
the expansion factor of G is `(n) = n + 1
Iftekhar Salam (XMUM) CYS201 13 / 44
Pseudorandomness
Do PRGs exist?
We don’t know
We will assume PRGs exist
In practice, we have several algorithms believed to be PRGs
Stream ciphers
Can construct PRGs from weaker assumptions (that one-way functions exist)
Iftekhar Salam (XMUM) CYS201 14 / 44
Pseudorandomness
EAV-Security from a Pseudorandom Generator
Let G be a pseudorandom generator with expansion factor `(n). Define a fixed-length
private-key encryption scheme Π for messages of length `(n) as follows:
Gen: on input 1n , choose uniform key k ∈ {0, 1}n and output it as the key
Enc: on input key k ∈ {0, 1}n and a message (plaintext) m ∈ {0, 1}`(n) , output the
ciphertext
c : G(k) ⊕ m
Dec: on input key k ∈ {0, 1} and a ciphertext c ∈ {0, 1}`(n) , output the message
n
(plaintext)
m : G(k) ⊕ c
Iftekhar Salam (XMUM) CYS201 15 / 44
Pseudorandomness
EAV-Security from a Pseudorandom Generator
Let G be a pseudorandom generator with expansion factor `(n). Define a fixed-length
private-key encryption scheme Π for messages of length `(n) as follows:
Gen: on input 1n , choose uniform key k ∈ {0, 1}n and output it as the key
Enc: on input key k ∈ {0, 1}n and a message (plaintext) m ∈ {0, 1}`(n) , output the
ciphertext
c : G(k) ⊕ m
Dec: on input key k ∈ {0, 1} and a ciphertext c ∈ {0, 1}`(n) , output the message
n
(plaintext)
m : G(k) ⊕ c
Theorem
If G is a pseudorandom generator, then Π is an EAV-secure, fixed-length private-key
encryption scheme for messages of length `(n).
Iftekhar Salam (XMUM) CYS201 15 / 44
Pseudorandomness
EAV-Security from a Pseudorandom Generator
Let G be a pseudorandom generator with expansion factor `(n). Define a fixed-length
private-key encryption scheme Π for messages of length `(n) as follows:
Gen: on input 1n , choose uniform key k ∈ {0, 1}n and output it as the key
Enc: on input key k ∈ {0, 1}n and a message (plaintext) m ∈ {0, 1}`(n) , output the
ciphertext
c : G(k) ⊕ m
Dec: on input key k ∈ {0, 1} and a ciphertext c ∈ {0, 1}`(n) , output the message
n
(plaintext)
m : G(k) ⊕ c
Theorem
If G is a pseudorandom generator, then Π is an EAV-secure, fixed-length private-key
encryption scheme for messages of length `(n).
Intuition:
A pseudorandom string “looks random” to any polynomial-time adversary
So, a computationally bounded eavesdropper cannot distinguish between a message
encrypted using the one-time pad or a message encrypted using this
“pseudo-”one-time pad encryption scheme.
Iftekhar Salam (XMUM) CYS201 15 / 44
Intro to Stream Ciphers
Presentation Outline
1 Cryptography and Confidentiality
2 Pseudorandomness
3 Intro to Stream Ciphers
4 Pseudorandom Number Generators using LFSRs
5 Stream Cipher Constructions using LFSRs
Iftekhar Salam (XMUM) CYS201 16 / 44
Intro to Stream Ciphers
Remember the problem with one-time pad?
The One-Time Pad can provide perfectly secret encryption!
However, there is a practical problem: Can’t reuse keys
the same key (truly random, same length as message, pre-distrib) is required to
encrypt and decrypt a message, and we can not reuse keys, so:
If you are transmitting info, can you distribute the key to the receiver securely?
Can you store the key securely?
Now...If you can send/store the key securely
May be you can just send/store the original message securely?
Major problem: Key management
Iftekhar Salam (XMUM) CYS201 17 / 44
Intro to Stream Ciphers
A more practical alternative is a stream cipher
1 We generate a pseudorandom “keystream” from a seed, a “real key” much shorter
than the full “keystream” added to the message
replace “rand (key)” in OTP by “pseudo rand (keystream)” in stream cipher
Use Pseudo Random Number Generator
PRNG: {0, 1}s → {0, 1}n
Expand a short (e.g., 128-bit) random seed into a long (e.g., 106 bit) string that “looks
random”
2 We try to make the set of possible seeds, the real keys, so large that exhaustive
search is impossible in practice
3 We try to eliminate any shortcuts to finding this key from the “keystream”
Iftekhar Salam (XMUM) CYS201 18 / 44
Intro to Stream Ciphers
Stream Ciphers
The plaintext and ciphertext are viewed as streams of characters
Character size may be one bit, or n-bit word, e.g., 8-bit byte...
How it works?
Plaintext is encrypted one character at a time, by combining it with the keystream
Ciphertext is decrypted one character at a time, by
combining it with the same keystream that was used in the encryption
Most common type is binary additive stream cipher
Plaintext, ciphertext and keystream are all stream of bits
The combining function is just XOR (addition modulo 2) operation
Iftekhar Salam (XMUM) CYS201 19 / 44
Intro to Stream Ciphers
Stream Ciphers
Most practical stream ciphers are binary additive stream ciphers
They imitate the one time pad, BUT don't use a truly random binary sequence
Instead they use a keystream generator
The keystream generator takes input a short key (and may be some additional public
information)
The keystream generator outputs a longer pseudo-random sequence, called the
keystream
The same keystream should not be used to encrypt two different messages
Keystream should be the same length of the message
XOR the keystream with the plaintext bit streams, one bit at a time
A good keystream generator should produces binary sequences that look random
Iftekhar Salam (XMUM) CYS201 20 / 44
Intro to Stream Ciphers
Binary Additive Stream Cipher
Encryption Process
The key is input to the keystream
generator
A pseudo-random keystream of
required length is produced at the
sender
Each plaintext bit is XORed with the
corresponding keystream bit to
produce the ciphertext bits
Figure: Encryption Process
Iftekhar Salam (XMUM) CYS201 21 / 44
Intro to Stream Ciphers
Binary Additive Stream Cipher
Encryption Process Decryption Process
The key is input to the keystream The (same key) is input to the
generator keystream generator
A pseudo-random keystream of Generate the same pseudo-random
required length is produced at the keystream of required length at the
sender receiver
Each plaintext bit is XORed with the XOR each of the ciphertext bit with
corresponding keystream bit to the corresponding keystream bit to
produce the ciphertext bits recover the plaintext bits
Figure: Encryption Process Figure: Decryption Process
Iftekhar Salam (XMUM) CYS201 21 / 44
Intro to Stream Ciphers
Binary Additive Stream Cipher
Most modern stream ciphers use two inputs:
a secret key and known initialisation vector (IV)
The IV is sometimes also called a nonce
So a new (different) keystream can be formed from the same key by changing the IV
Common for stream ciphers used for mobile phones, or over the internet. The IV
can be:
the frame number (phone conversation), or
the packet number (internet communications).
The IV is made public, only the key is secret
Figure: Binary additive stream cipher1
1
Source: [Link]
Iftekhar Salam (XMUM) CYS201 22 / 44
Pseudorandom Number Generators using LFSRs
Presentation Outline
1 Cryptography and Confidentiality
2 Pseudorandomness
3 Intro to Stream Ciphers
4 Pseudorandom Number Generators using LFSRs
5 Stream Cipher Constructions using LFSRs
Iftekhar Salam (XMUM) CYS201 23 / 44
Pseudorandom Number Generators using LFSRs
Pseudorandom Number Generators (PRNGs)
Often use deterministic algorithmic techniques to create random like numbers
although are not truly random
can pass many tests of randomness
known as pseudorandom numbers
created by Pseudorandom Number Generators (PRNGs)
Characteristics of the seed?
Need to be secret?
Can be known to the adversary?
Figure: Pseudorandom Number Generators
Iftekhar Salam (XMUM) CYS201 24 / 44
Pseudorandom Number Generators using LFSRs
Linear Feedback Shift Registers as PRNGs
Figure: Feedback Shift Register (FSR)
Iftekhar Salam (XMUM) CYS201 25 / 44
Pseudorandom Number Generators using LFSRs
Linear Feedback Shift Registers as PRNGs
Figure: Feedback Shift Register (FSR)
Linear Feedback Shift Register (LFSR): Feedback function is linear over F2 , i.e., an XOR
Ln−1
Linear function F : bn−1 = i=0 αi bi for αi ∈ {0, 1}
All the rest of the bits are updated by shifting: bi = bi+1 for i = 0, · · · , n − 2
Iftekhar Salam (XMUM) CYS201 25 / 44
Pseudorandom Number Generators using LFSRs
Example of LFSRS
Figure: What is the updated state?
Iftekhar Salam (XMUM) CYS201 26 / 44
Pseudorandom Number Generators using LFSRs
Example of LFSRS
Figure: Output bit euqal to the right most bit, and shift all the rest of the bits one bit to the right
Iftekhar Salam (XMUM) CYS201 26 / 44
Pseudorandom Number Generators using LFSRs
Example of LFSRS
Figure: Compute the feedback to update the left most bit
Iftekhar Salam (XMUM) CYS201 26 / 44
Pseudorandom Number Generators using LFSRs
Period of LFSRs
These are basically finite state machines, so the state will repeat itself at some point
One feature should be that the stream should not repeat itself too quickly
The maximum period/cycle for an n-bit register is 2n − 1
Why not 2n ?
Maximal period - m-sequences
The tap sequence defines the linear feedback function and is often regarded as a
finite field polynomial
You have to choose the tap sequence very carefully
Some choices provide a maximal length period
These are primitive polynomials (also called irreducible polynomial)
Iftekhar Salam (XMUM) CYS201 27 / 44
Pseudorandom Number Generators using LFSRs
Period of LFSRs - Primitive Polynomials Give m-Sequences
Iftekhar Salam (XMUM) CYS201 28 / 44
Pseudorandom Number Generators using LFSRs
Period of LFSRs - Some Polynomials Do Not Give m-Sequences
Iftekhar Salam (XMUM) CYS201 29 / 44
Pseudorandom Number Generators using LFSRs
Should we use the output of a LFSR as the keystream?
Consider a 64 bit register. Can this be used as a key stream generator?
No
Once you know a very small amount of plaintext (e.g. 32 consecutive bits) then
you can calculate the corresponding key stream and so you know the rightmost 32
bits in the register
You can now try in turn all other 232 combinations for the rest
And so plaintext should make sense
This is just too easy to break
But LFSRs are very easy to implement; and execute quickly
Can we fix this?
How about a less primitive way of extracting the key stream
How about combining several streams to achieve any better security?
Iftekhar Salam (XMUM) CYS201 30 / 44
Stream Cipher Constructions using LFSRs
Presentation Outline
1 Cryptography and Confidentiality
2 Pseudorandomness
3 Intro to Stream Ciphers
4 Pseudorandom Number Generators using LFSRs
5 Stream Cipher Constructions using LFSRs
Iftekhar Salam (XMUM) CYS201 31 / 44
Stream Cipher Constructions using LFSRs
A very simple keystream generator model using LFSR
Figure: A simple model of keystream generator using a single LFSR
Iftekhar Salam (XMUM) CYS201 32 / 44
Stream Cipher Constructions using LFSRs
A very simple keystream generator model using LFSR
Figure: A simple model of keystream generator using a single LFSR
Iftekhar Salam (XMUM) CYS201 32 / 44
Stream Cipher Constructions using LFSRs
Boolean functions - Algebraic Normal Form (ANF)
A Boolean function on n-inputs can be represented in minimal sum (XOR +) of
products (AND .) form:
f (x1 , · · · , xn ) = a0 + a1 .x1 + · · · + an .xn + · · · a1,2 .x1 .x2 + · · · + an−1,n .xn−1 .xn +
· · · + a1,2,···,n x1 .x2 · · · .xn
This is the ANF of the function
The algebraic degree of the function is the size of the largest subset of inputs (i.e.
the number of xj in it) associated with a non-zero co-efficient.
Need to consider the algebraic degree of the output keystream
1 is a constant function (as is 0)
x1 ⊕ x3 ⊕ x5 is a linear function
x1 x5 ⊕ x3 is a quadratic function
x1 x5 x3 ⊕ x2 x1 ⊕ x10 is a cubic function
Iftekhar Salam (XMUM) CYS201 33 / 44
Stream Cipher Constructions using LFSRs
A very simple keystream generator model using LFSR
Figure: A simple model of keystream generator using a single LFSR
How about using a linear function for the keystream generator?
Not a very good choice
The seed can be easily recovered by generating and solving a set of linear equations
that defines the state update of the cipher
Iftekhar Salam (XMUM) CYS201 34 / 44
Stream Cipher Constructions using LFSRs
Why a linear keystream generation function is not a good choice?
Figure: A hypothetical keystream generator
Feedback function/ state update function:
(
sti+1 for i = 0, · · · , 2
st+1
i =
st0 ⊕ st3 for i = 3.
Output function/ Keystream generation function: Zt = st0 ⊕ st2
Suppose we know a sequence of keystream bits zt=0 , zt=1 , zt=2 , zt=3 = 1, 1, 1, 1,
respectively
Can generate a set of linear independent equations and solve them to recover the
initial seed
Iftekhar Salam (XMUM) CYS201 35 / 44
Stream Cipher Constructions using LFSRs
Why a linear keystream generation function is not a good choice?
Figure: A hypothetical keystream generator
Feedback function/ state update function:
(
sti+1 for i = 0, · · · , 2
st+1
i =
st0 ⊕ st3 for i = 3.
Output function/ Keystream generation function: Zt = st0 ⊕ st2
Suppose we know a sequence of keystream bits zt=0 , zt=1 , zt=2 , zt=3 = 1, 1, 1, 1,
respectively
Can generate a set of linear independent equations and solve them to recover the
initial seed
Iftekhar Salam (XMUM) CYS201 35 / 44
Stream Cipher Constructions using LFSRs
Why a linear keystream generation function is not a good choice?
Keystream Zt = st0 ⊕ st2
Set of linear equations:
s0 ⊕ s2 = 1 (1)
s1 ⊕ s3 = 1 (2)
s0 ⊕ s2 ⊕ s3 = 1 (3)
s0 ⊕ s1 = 1 (4)
Figure: Representing the states for different time instants
Solving these linear equations result in:
s0 = 0, s1 = 1, s2 = 1, s3 = 0
The initial seed (secret key) is recovered!
Iftekhar Salam (XMUM) CYS201 36 / 44
Stream Cipher Constructions using LFSRs
A relatively harder keystream generator model using LFSR
What about a nonlinear keystream generation function?
This is better but it is still possible to attack such systems if f is approximated by a
linear function.
Iftekhar Salam (XMUM) CYS201 37 / 44
Stream Cipher Constructions using LFSRs
Classical stream cipher model using LFSRs
The classical model of stream cipher combines the output of several LFSRs using a
Boolean function f
Iftekhar Salam (XMUM) CYS201 38 / 44
Stream Cipher Constructions using LFSRs
Keystream generation function: is this a good choice?
This is a very poor choice. Two LFSRs are used, but LFSR 2 is completely ignored.
Iftekhar Salam (XMUM) CYS201 39 / 44
Stream Cipher Constructions using LFSRs
Keystream generation function: is this a good choice?
Congratulations! You have not ignored LFSR 2! Key size = 64 bits?
Iftekhar Salam (XMUM) CYS201 40 / 44
Stream Cipher Constructions using LFSRs
Better but still awful choice for f
Why this is not a good choice?
Suppose you know 32 consecutive bits of plaintext (or can guess them correctly).
Calculate the 32 bits of key stream.
But if stream bit is 0 then there are only 2 possible pairs. Similarly, if stream value
is 1.
Effective key size = 232
Iftekhar Salam (XMUM) CYS201 41 / 44
Stream Cipher Constructions using LFSRs
Better but still awful choice for f
Why this is not a good choice?
Suppose you know 32 consecutive bits of plaintext (or can guess them correctly).
Calculate the 32 bits of key stream.
But if stream bit is 0 then there are only 2 possible pairs. Similarly, if stream value
is 1.
Effective key size = 232
Iftekhar Salam (XMUM) CYS201 41 / 44
Stream Cipher Constructions using LFSRs
Better but still awful choice for f
Moreover f is still a linear function. Given 64 independent linear output functions and
the corresponding keystream bits, an adversary would be able to recover the LFSR
contents
How do an adversary get access to the keystream?
Known-plaintext attack
Data complexity: 26
Time complexity: Negligible
Iftekhar Salam (XMUM) CYS201 42 / 44
Stream Cipher Constructions using LFSRs
Introduce non-linearity?
Must introduce some nonlinearity, i.e., some operations other than XOR, to thwart
attacks
Nonlinear feedback
Nonlinear combination generators
Nonlinear filter generators
Clock controlled generators
. . . or some combination of the above
To be continued . . .
Iftekhar Salam (XMUM) CYS201 43 / 44
Stream Cipher Constructions using LFSRs
End of lecture 3! ,
Summary
Cryptographic tools can be used to provide information security goals
Need to select the right tool based on the requirements
Symmetric cryptography
Stream cipher is one type of symmetric primitive – provides confidentiality
can be constructed using PRGs
Can also provide integrity assurance – look for authenticated encryption stream ciphers
Fast and suitable for real time applications
Next week lecture
Symmetric Cryptography - Stream Ciphers (Part II)
Desirable properties of the stream cipher output function
Modern stream ciphers
QUESTIONS?
Iftekhar Salam (XMUM) CYS201 44 / 44