Chapter 4.
Stream Ciphers
• Cryptographic systems
o Symmetrical key cryptographic systems
▪ Stream ciphers (to be covered in this chapter)
▪ Block ciphers
□ Classical ciphers (covered in Chapter 2)
□ Modern block ciphers (AES will be covered in Chapter 5)
o Public key cryptographic systems
▪ RSA
▪ ECC (to be covered in Chapter 7)
o Post-quantum cryptographic systems
▪ NTRU
Some figures are from W. Stalling’s book “Cryptography and network security”, 7th edition. ©2017 Pearson Education, Inc
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
1
Stream Ciphers (vs Block Ciphers)
• Belong to modern cipher (still used today)
• Stream cipher and block cipher are two major types of
symmetric key cipher.
• Compared to block ciphers, stream ciphers usually
• Treat plaintext as a stream of bits or digits, rather than blocks.
• Have simpler and faster en/decryption operations
• Have much larger key
• Do not recycle the key
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
2
Stream Cipher
• En/decryption are extremely simple:
• XOR operation between plaintext and key
• Very fast operations
• Key generator is the most complex unit in the system:
• Generates long and not-recyclable key-stream.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
3
Stream Cipher
• Sometimes the key generator alone is referred to as the stream
cipher, where a small key is used as input to generate a long
key-stream for stream cipher.
• Key generator (stream cipher) is usually built with LFSR or
NLFSR based circuits.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
4
LFSR: Linear Feedback Shift Register
• Module diagram: A 4-bit LFSR built with 4 one-bit registers and a mod 2
adder.
• Circuit diagram: The 4-bit LFSR implemented with 4 D flip-flops and one
XOR gate.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
5
LFSR: Linear Feedback Shift Register
• Example: A 4-bit LFSR
o Built based on f(x)=x4+x+1
o Let the initial state be 0001. What is the output sequence? Find its
period.
o Draw the state transition diagram.
o Add two more feedback connections and redo the above.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
6
State Transition Diagram
• A 4-bit LFSR
• State transition diagram
• Output sequence:
o 0001 1110 1011 0010 0011 1101 0110 0100 …
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
7
LFSR as Pseudorandom Sequence Generator
• Maximal period for an n-bit LFSR is 2n-1.
• Always use suitable polynomial to build an LFSR for long
period output sequence.
o Primitive polynomials (a subset of irreducible polynomials)
• Test of the randomness of a binary sequence:
o The number of ones and zeros
o The number of one-runs and zero-runs
• Many modern stream ciphers are based on LFSR.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
8
LFSR based Stream Cipher: A5/1
• Developed in 1987.
• A5/1 is used for providing privacy for GSM cell phone.
• Estimated in 2011 that there were 4 billions GSM phones
installed with A5/1.
• A5/1 is still used in US and Europe.
• A5/2 was a weaker version for purpose of export.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
9
Stream Cipher Used for GSM Encryption
Characteristic polynomials for the LFSRs used in A5/1 Generator:
• LFSR1:
x19 + x18 + x17 + x14 + 1
• LFSR2:
x22 + x21 + 1
• LFSR3:
x23 + x22 + x21 + x8 + 1
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
10
A5/1 Generator Architecture
• A5/1 Sequence Generator:
LFSR1
LFSR2
LFSR3
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
11
NLFSR: Non-Linear Feedback Shift Register
• Feedback function is non-linear:
• An example of 4-bit NLFSR:
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
12
Some Popular Stream Ciphers in Use
• A5/1 (1989) – broken
• RC4 (1987) – broken
• FISH (1993) – broken
• Rabbit (2003) – ?
• eSTREAM portfolio by ECRYPT project (2008) – safe
1. Profile 1 (software):
HC-128, Rabbit, Salsa20/12, SOSEMANUK
2. Profile 2 (hardware):
Grain, MICKEY, Trivium
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
13
eSTREAM portfolio Project: Profile 2
• Project completed in 2008:
o Grain
▪ Use both large LFSR and NLFSR
o MICKEY
▪ Use two 100-bit registers with irregular clocking circuitry
o Trivium
▪ Use a few long shift registers
▪ Based binary finite field operations
▪ Regulated as an International Standard under ISO/IEC 29192-3.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
14
Trivium
• Let the 80-bit key and the l-bit initial vector are given as
K = (k0, k1, … , k79),
IV = (v0, v1, … , vl-1), 0 ≤ l ≤ 80, and
ki and vi each represents one bit.
• Initialize three vectors of lengths 93, 84, and 111, respectively:
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
15
Trivium (con’t)
• Then use recursive steps to obtain aj, bj, cj , j=−1152, −1151, …,
as
• The output bits r0 ... rN are given by (N=264-1)
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
16
Trivium (con’t)
• The operations + and • are GF(2) operations, or can be
implemented with XOR and AND gates, respectively.
• 1152 recursive steps are required before output is produced.
o Because of the large negative indices on the initial values
• State-of-art work on Trivium implementation:
o Use 3488 logic gates and produce one bit per cycle.
o For parallel implementation it uses 5504 gates for faster clocking.
• For those interested in hardware design, an efficient
implementation of Trivium cipher would be a nice project.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
17
An Architecture for Implementing Trivium
• The rectangular □ denotes 1-bit register; Sign circle with a
plus is an XOR gate, while Sign circle with a dot denotes an
AND gate.
Data Security & Cryptography, 2020F Huapeng Wu @ U Windsor
18
