Stream Ciphers
Stream Ciphers
Slides Original Source:
1.
C. Paar and J. Pelzl, “Understanding Cryptography – A Textbook for Students and
Practitioners,”
Springer (
)www.crypto-textbook.com
2.
M. Stamp, “Information Security: Principles and Practice,” John Wiley
Understanding Cryptography by Christof Paar and Jan Pelzl
O
u
t
l
i
n
e
•
Intro to stream ciphers
•
Random number generators (RNGs)
•
Linear feedback shift registers (LFSRs)
•
Examples of stream ciphers
•
A5/1
•
RC4
•
Trivium: a modern stream cipher
2/27
Understanding Cryptography by Christof Paar and Jan Pelzl
O
u
t
l
i
n
e
•
Intro to stream ciphers
•
Random number generators (RNGs)
•
Linear feedback shift registers (LFSRs)
•
Examples of stream ciphers
•
A5/1
•
RC4
•
Trivium: a modern stream cipher
3/27
Understanding Cryptography by Christof Paar and Jan Pelzl
S
t
r
e
a
m
C
i
p
h
e
r
s
i
n
t
h
e
F
i
e
l
d
o
f
C
r
y
p
t
o
l
o
g
y
Stream Ciphers were invented in 1917 by Gilbert Vernam
4/27
Understanding Cryptography by Christof Paar and Jan Pelzl
S
t
r
e
a
m
C
i
p
h
e
r
v
s
.
B
l
o
c
k
C
i
p
h
e
r
•
S
t
r
e
a
m
C
i
p
h
e
r
s
•
Encrypt bits individually
•
Usually small and fast
common in embedded devices (e.g., A5/1 for
GSM phones)
•
B
l
o
c
k
C
i
p
h
e
r
s
:
•
Always encrypt a full block (several bits)
•
Are common for Internet applications
5/27
E
n
c
r
y
p
t
i
o
n
a
n
d
D
e
c
r
y
p
t
i
o
n
w
i
t
h
S
t
r
e
a
m
C
i
p
h
e
r
s
•
Encryption and decryption are simple XOR
•
Encryption and decryption are the same functions
•
E
n
c
r
y
p
t
i
o
n
:
y
i
=
E
(
x
i
,
s
i
)
=
x
i
s
i
x
i
,
y
i
,
s
i
∈
{0
,
1
}
•
D
e
c
r
y
p
t
i
o
n
:
x
i
=
D
(
y
i
,
s
i
)
=
y
i
s
i
Understanding Cryptography by Christof Paar and Jan Pelzl
Plaintext
x
i
,
ciphertext
y
i
and key stream
s
i
consist of individual bits
6/27
Understanding Cryptography by Christof Paar and Jan Pelzl
S
y
n
c
h
r
o
n
o
u
s
v
s
.
A
s
y
n
c
h
r
o
n
o
u
s
S
t
r
e
a
m
C
i
p
h
e
r
•
Security of stream cipher depends entirely on the key stream
s
i
:
•
S
h
o
u
l
d
b
e
r
a
n
d
o
m
,
i
.
e
.
,
P
r
(
s
i
=
0
)
=
P
r
(
s
i
=
1
)
=
0
.
5
•
M
u
s
t
b
e
r
e
p
r
o
d
u
c
i
b
l
e
b
y
s
e
n
d
e
r
a
n
d
r
e
c
e
i
v
e
r
•
S
y
n
c
h
r
o
n
o
u
s
S
t
r
e
a
m
C
i
p
h
e
r
•
Key stream depend only on the key (and possibly an initialization vector IV)
•
A
s
y
n
c
h
r
o
n
o
u
s
S
t
r
e
a
m
C
i
p
h
e
r
s
•
Key stream depends also on the ciphertext (dotted feedback enabled)
7/27
S
t
r
e
a
m
C
i
p
h
e
r
:
T
h
r
o
u
g
h
p
u
t
Performance comparison of symmetric ciphers (Pentium4):
Chapter 2 of
Understanding Cryptography
by Christof Paar and Jan Pelzl
Source: Zhao et al., Anatomy and Performance of SSL Processing, ISPASS 2005
8/27
Understanding Cryptography by Christof Paar and Jan Pelzl
O
u
t
l
i
n
e
•
Intro to stream ciphers
•
Random number generators (RNGs)
•
Linear feedback shift registers (LFSRs)
•
Examples of stream ciphers
•
A5/1
•
RC4
•
Trivium: a modern stream cipher
9/27
R
a
n
d
o
m
n
u
m
b
e
r
g
e
n
e
r
a
t
o
r
s
(
R
N
G
s
)
Understanding Cryptography by Christof Paar and Jan Pelzl
10/27
T
r
u
e
R
a
n
d
o
m
N
u
m
b
e
r
G
e
n
e
r
a
t
o
r
s
(
T
R
N
G
s
)
•
Based on physical random processes: coin flipping, dice rolling, semiconductor
noise, radioactive decay, mouse movement, clock jitter of digital circuits, …
•
Output stream
s
i
should have good statistical properties:
Pr(
s
i
= 0) = Pr(
s
i
= 1) = 50% (often achieved by post-processing)
•
Output can neither be predicted nor be reproduced
Typically used for generation of keys, nonces (used only-once values) and for
many other purposes
Understanding Cryptography by Christof Paar and Jan Pelzl
11/27
P
s
e
u
d
o
r
a
n
d
o
m
N
u
m
b
e
r
G
e
n
e
r
a
t
o
r
(
P
R
N
G
)
•
Generate sequences from initial seed value
•
Typically, output stream has good statistical properties (e.g., randomness)
•
Output can be reproduced and can be predicted
Often computed in a recursive way:
Understanding Cryptography by Christof Paar and Jan Pelzl
Example:
rand() function
in ANSI C:
M
o
s
t
P
R
N
G
s
h
a
v
e
b
a
d
c
r
y
p
t
o
g
r
a
p
h
i
c
p
r
o
p
e
r
t
i
e
s
!
12/27
C
r
y
p
t
a
n
a
l
y
z
i
n
g
a
S
i
m
p
l
e
P
R
N
G
A
s
s
u
m
e
•
unknown
A
,
B and S
0
as key
•
Size of
A
,
B
and
S
i
to be 100 bit
•
300 bit of output are known, i.e.
S
1
,
S
2
and
S
3
S
o
l
v
i
n
g
…directly reveals A and B. All
S
i
can be computed easily!
Understanding Cryptography by Christof Paar and Jan Pelzl
S
i
m
p
l
e
P
R
N
G
:
L
i
n
e
a
r
C
o
n
g
r
u
e
n
t
i
a
l
G
e
n
e
r
a
t
o
r
B
a
d
c
r
y
p
t
o
g
r
a
p
h
i
c
p
r
o
p
e
r
t
i
e
s
d
u
e
t
o
t
h
e
l
i
n
e
a
r
i
t
y
o
f
m
o
s
t
P
R
N
G
s
13/27
C
r
y
p
t
o
g
r
a
p
h
i
c
a
l
l
y
S
e
c
u
r
e
P
s
e
u
d
o
r
a
n
d
o
m
N
u
m
b
e
r
G
e
n
e
r
a
t
o
r
(
C
S
P
R
N
G
)
•
Special PRNG with additional property:
•
O
u
t
p
u
t
m
u
s
t
b
e
u
n
p
r
e
d
i
c
t
a
b
l
e
M
o
r
e
p
r
e
c
i
s
e
l
y
:
G
i
v
e
n
n
c
o
n
s
e
c
u
t
i
v
e
b
i
t
s
o
f
o
u
t
p
u
t
s
i
,
t
h
e
f
o
l
l
o
w
i
n
g
o
u
t
p
u
t
b
i
t
s
s
n
+
1
c
a
n
n
o
t
b
e
p
r
e
d
i
c
t
e
d
(
i
n
p
o
l
y
n
o
m
i
a
l
t
i
m
e
)
.
•
Needed in cryptography, in particular for stream ciphers
•
Remark: There are almost no other applications that need unpredictability,
whereas many, many (technical) systems need PRNGs.
Understanding Cryptography by Christof Paar and Jan Pelzl
14/27
Understanding Cryptography by Christof Paar and Jan Pelzl
O
u
t
l
i
n
e
•
Intro to stream ciphers
•
Random number generators (RNGs)
•
Linear feedback shift registers (LFSRs)
•
Examples of stream ciphers
•
A5/1
•
RC4
•
Trivium: a modern stream cipher
15/27
L
i
n
e
a
r
F
e
e
d
b
a
c
k
S
h
i
f
t
R
e
g
i
s
t
e
r
s
(
L
F
S
R
s
)
•
Concatenated
flip-flops (FF
), i.e., a shift register together with a feedback path
•
Feedback computes fresh input by XOR of certain state bits
•
Degree
m
given by number of storage elements
•
If
p
i
= 1, the feedback connection is present (“closed switch), otherwise there is
no feedback from this flip-flop (“open switch”)
•
Output sequence repeats periodically
•
M
a
x
i
m
u
m
o
u
t
p
u
t
l
e
n
g
t
h
:
2
m
-
1
Understanding Cryptography by Christof Paar and Jan Pelzl
16/27
L
i
n
e
a
r
F
e
e
d
b
a
c
k
S
h
i
f
t
R
e
g
i
s
t
e
r
s
(
L
F
S
R
s
)
:
E
x
a
m
p
l
e
w
i
t
h
m
=
3
•
LFSR output described by recursive equation:
•
Maximum output length (of 2
3
-1=7) achieved only for certain
feedback configurations, .e.g., the one shown here.
Understanding Cryptography by Christof Paar and Jan Pelzl
17/27
S
e
c
u
r
i
t
y
o
f
L
F
S
R
s
LFSRs typically described by polynomials:
•
Single LFSRs generate highly predictable output
•
If 2
m
output bits of an LFSR of degree
m
are known, the feedback coefficients
p
i
of the LFSR can be found by solving a system of linear equations*
•
B
e
c
a
u
s
e
o
f
t
h
i
s
m
a
n
y
s
t
r
e
a
m
c
i
p
h
e
r
s
u
s
e
c
o
m
b
i
n
a
t
i
o
n
s
o
f
L
F
S
R
s
*
See Chapter 2 of
Understanding Cryptography
for further details.
Understanding Cryptography by Christof Paar and Jan Pelzl
18/27
Understanding Cryptography by Christof Paar and Jan Pelzl
O
u
t
l
i
n
e
•
Intro to stream ciphers
•
Random number generators (RNGs)
•
Linear feedback shift registers (LFSRs)
•
Examples of stream ciphers
•
A5/1
•
RC4
•
Trivium: a modern stream cipher
19/27
Stream Ciphers
20
Stream Ciphers Examples
A5/1
o
Based on combinations of LFSRs
o
Used in GSM mobile phone system
RC4
o
Based on a changing lookup table
o
Used in WEP, WPA, BitTorrent, MS Office XP, TLS/SSL
(prohibited now by RFC 7465), SSH (optionally), Remote
Desktop (optionally), PDF, Skype (modified form)
RC4
o
Based on combinations of LFSRs
o
Selected by the EU ECRYPT network as Profile II of the
eSTREAM project
Stream Ciphers
21
A5/1
A5/1 uses 3 LFSRs (
X
,
Y
,
Z
)
o
X
: 19 bits
(
x
0
,
x
1
,
x
2
,
…,x
18
)
o
Y
: 22 bits
(
y
0
,
y
1
,
y
2
,
…,y
21
)
o
Z
: 23 bits
(
z
0
,
z
1
,
z
2
,
…,z
22
)
Stream Ciphers
22
A5/1: Keystream
At each step:
m
= maj(
x
8
,
y
10
,
z
10
)
o
Examples:
maj(0
,1,0) = 0
and
maj(1
,1,0) = 1
If
x
8
=
m
then
X
steps
o
t
=
x
13
x
16
x
17
x
18
o
x
i
=
x
i
1
for
i
= 18,17,…,1 and
x
0
=
t
If
y
10
=
m
then
Y
steps
o
t
=
y
20
y
21
o
y
i
=
y
i
1
for
i
= 21,20,…,1 and
y
0
=
t
If
z
10
=
m
then
Z
steps
o
t =
z
7
z
20
z
21
z
22
o
z
i
=
z
i
1
for
i
= 22,21,…,1 and
z
0
=
t
Keystream
bit
is
(
x
18
y
21
z
22
)
Stream Ciphers
23
A5/1: Keystream
Each variable here is a single bit
Key is used as
initial fill
of registers
Each register steps (or not) based on
maj
(
x
8
,
y
10
,
z
10
)
Keystream bit is XOR of rightmost bits of registers
X
Y
Z
Stream Ciphers
24
A5/1
In this example,
m
= maj(
x
8
,
y
10
,
z
10
)
= maj(
1
,
0
,
1
) =
1
Register
X
steps,
Y
does not step, and
Z
steps
Keystream bit is XOR of right bits of registers
Here, keystream bit will be
0
1
0 = 1
X
Y
Z
Stream Ciphers
25
RC4
A self-modifying lookup table
Table always contains a permutation of the
byte values
0,1,…,255
Initialize the permutation using key
At each step, RC4 does the following
o
Swaps elements in current lookup table
o
Selects a keystream
byte
from table
Each step of RC4 produces a
byte
o
Efficient in software
Each step of A5/1 produces only a bit
o
Efficient in hardware
Stream Ciphers
26
RC4 Initialization
S[] is permutation of 0,1,...,255
key[] contains N bytes of key
for i = 0 to 255
S[i] = i
K[i] = key[i (mod N)]
next i
j = 0
for i = 0 to 255
j = (j + S[i] + K[i]) mod 256
swap(S[i], S[j])
next i
i = j = 0
Stream Ciphers
27
RC4 Keystream
For each keystream byte, swap elements in
table and select byte
i = (i + 1) mod 256
j = (j + S[i]) mod 256
swap(S[i], S[j])
t = (S[i] + S[j]) mod 256
keystreamByte = S[t]
Use keystream bytes like a one-time pad
Note:
first 256 bytes should be discarded
o
Otherwise, related key attack exists
A
M
o
d
e
r
n
S
t
r
e
a
m
C
i
p
h
e
r
-
T
r
i
v
i
u
m
•
Three
nonlinear
LFSRs (NLFSR) of length 93, 84, 111
•
XOR-Sum of all three NLFSR outputs generates key stream
s
i
•
Small in Hardware:
•
Total register size: 288 FFs
•
Non-linearity: 3 AND-Gates
•
7 XOR-Gates (4 with three inputs)
Understanding Cryptography by Christof Paar and Jan Pelzl
28/27
T
r
i
v
i
u
m
•
The input of each register is computed as the XOR-sum of two bits:
•
The output bit of another register
•
One register bit at a specific location is fed back to the input (e.g., bit 68 of
register A is fed back to its input)
•
The output of each register is computed as the XOR-sum of three bits:
•
The rightmost register bit
•
One register bit at a specific location is fed forward to the output (e.g., bit 66 of
register A is fed to its output)
•
The output of a logical AND function whose input is two specific register bits
Understanding Cryptography by Christof Paar and Jan Pelzl
29/27
T
r
i
v
i
u
m
I
n
i
t
i
a
l
i
z
a
t
i
o
n
:
•
Load 80-bit IV into leftmost bits of A
•
Load 80-bit key into leftmost bits of B
•
Set
c
109
, c
110
, c
111
= 1, all other bits 0
W
a
r
m
-
U
p
:
•
Clock cipher 4 x 288 = 1152 times without generating output
•
needed for randomizing the cipher sufficiently
•
makes sure the key stream depends on both the key and the IV
K
e
y
s
t
r
e
a
m
:
•
XOR-Sum of all three NLFSR outputs generates key stream
s
i
-
Design can be parallelized to produce up to 64 bits of output per clock cycle
-
Can achieve encryption rates of 2 Gb/s (H/W) and 1 Gb/s (S/W) using moderate clocks
Understanding Cryptography by Christof Paar and Jan Pelzl
30/27
T
r
i
v
i
u
m
S
e
c
u
r
i
t
y
•
A
N
D
o
p
e
r
a
t
i
o
n
i
s
e
q
u
a
l
t
o
m
u
l
t
i
p
l
i
c
a
t
i
o
n
i
n
m
o
d
u
l
o
2
a
r
i
t
h
m
e
t
i
c
•
If we multiply two unknowns, and the register contents are the unknowns that
an attacker wants to recover, the resulting equations are no longer linear
•
i.e., they contain products of two unknowns
•
Feedforward paths involving AND operation are crucial for security of Trivium
as they prevent attacks that exploit the linearity of the cipher (vs. plain LFSRs)
Understanding Cryptography by Christof Paar and Jan Pelzl
31/27
Understanding Cryptography by Christof Paar and Jan Pelzl
L
e
s
s
o
n
s
L
e
a
r
n
e
d
•
Stream ciphers are less popular than block ciphers in most domains such as Internet
security. There are exceptions, for instance, the popular stream cipher RC4.
•
Stream ciphers sometimes require fewer resources, e.g., code size or chip area, for
implementation than block ciphers, and they are attractive for use in constrained
environments such as cell phones.
•
The requirements for a
cryptographically secure pseudorandom number generator
are far
more demanding than the requirements for pseudorandom number generators used in other
applications such as testing or simulation
•
Single LFSRs make poor stream ciphers despite their good statistical properties. However,
careful combinations of several LFSR can yield strong ciphers.
32/27
Stream ciphers are cryptographic algorithms used to encrypt individual bits, offering speed and efficiency. Learn about symmetric ciphers, encryption processes, synchronous vs. asynchronous stream ciphers, and key stream generation. Explore the evolution of stream ciphers in the field of cryptology, including notable examples like A5/1, RC4, and Trivium. Understand the differences between stream ciphers and block ciphers, their applications, and key characteristics essential for secure communication.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Stream Ciphers Slides Original Source: 1. C. Paar and J. Pelzl, Understanding Cryptography A Textbook for Students and Practitioners, Springer (www.crypto-textbook.com) 2. M. Stamp, Information Security: Principles and Practice, John Wiley
Outline Intro to stream ciphers Random number generators (RNGs) Linear feedback shift registers (LFSRs) Examples of stream ciphers A5/1 RC4 Trivium: a modern stream cipher Understanding Cryptography by Christof Paar and Jan Pelzl 2/27
Outline Intro to stream ciphers Random number generators (RNGs) Linear feedback shift registers (LFSRs) Examples of stream ciphers A5/1 RC4 Trivium: a modern stream cipher Understanding Cryptography by Christof Paar and Jan Pelzl 3/27
Stream Ciphers in the Field of Cryptology Cryptology Cryptography Cryptanalysis Protocols Symmetric Ciphers Asymmetric Ciphers Block Ciphers Stream Ciphers Stream Ciphers were invented in 1917 by Gilbert Vernam Understanding Cryptography by Christof Paar and Jan Pelzl 4/27
Stream Cipher vs. Block Cipher Stream Ciphers Encrypt bits individually Usually small and fast common in embedded devices (e.g., A5/1 for GSM phones) Block Ciphers: Always encrypt a full block (several bits) Are common for Internet applications Understanding Cryptography by Christof Paar and Jan Pelzl 5/27
Encryption and Decryption with Stream Ciphers Plaintext xi, ciphertext yiand key stream si consist of individual bits Encryption and decryption are simple XOR Encryption and decryption are the same functions Encryption: yi= E(xi, si) = xi si Decryption: xi= D(yi, si) = yi si xi , yi , si {0,1} Understanding Cryptography by Christof Paar and Jan Pelzl 6/27
Synchronous vs. Asynchronous Stream Cipher Security of stream cipher depends entirely on the key stream si : Should be random , i.e., Pr(si = 0) = Pr(si = 1) = 0.5 Must be reproducible by sender and receiver Synchronous Stream Cipher Key stream depend only on the key (and possibly an initialization vector IV) Asynchronous Stream Ciphers Key stream depends also on the ciphertext (dotted feedback enabled) Understanding Cryptography by Christof Paar and Jan Pelzl 7/27
Stream Cipher: Throughput Performance comparison of symmetric ciphers (Pentium4): Cipher DES 3DES AES Key length 56 112 128 (choosable) Mbit/s 36.95 13.32 51.19 211.34 RC4 (stream cipher) Source: Zhao et al., Anatomy and Performance of SSL Processing, ISPASS 2005 Chapter 2 of Understanding Cryptography by Christof Paar and Jan Pelzl 8/27
Outline Intro to stream ciphers Random number generators (RNGs) Linear feedback shift registers (LFSRs) Examples of stream ciphers A5/1 RC4 Trivium: a modern stream cipher Understanding Cryptography by Christof Paar and Jan Pelzl 9/27
Random number generators (RNGs) RNG Cryptographically Secure RNG True RNG Pseudorandom NG Understanding Cryptography by Christof Paar and Jan Pelzl 10/27
True Random Number Generators (TRNGs) Based on physical random processes: coin flipping, dice rolling, semiconductor noise, radioactive decay, mouse movement, clock jitter of digital circuits, Output stream si should have good statistical properties: Pr(si = 0) = Pr(si = 1) = 50% (often achieved by post-processing) Output can neither be predicted nor be reproduced Typically used for generation of keys, nonces (used only-once values) and for many other purposes Understanding Cryptography by Christof Paar and Jan Pelzl 11/27
Pseudorandom Number Generator (PRNG) Generate sequences from initial seed value Typically, output stream has good statistical properties (e.g., randomness) Output can be reproduced and can be predicted Often computed in a recursive way: = s seed 0 += ( , ,..., ) s f s s s 1 1 i i i i t Example: rand() function in ANSI C: 12345 = + i s = s 0 + 31 1103515245 12345 mod 2 s 1 i Most PRNGs have bad cryptographic properties! Understanding Cryptography by Christof Paar and Jan Pelzl 12/27
Cryptanalyzing a Simple PRNG Simple PRNG: Linear Congruential Generator seed S mod 1 + = + = 0 S AS B m i i Assume unknown A, B and S0as key Size of A, B and Si to be 100 bit 300 bit of output are known, i.e. S1, S2 and S3 Solving B AS S mod 2 3 + = = + mod m 2 1 S AS B m directly reveals A and B. All Si can be computed easily! Bad cryptographic properties due to the linearity of most PRNGs Understanding Cryptography by Christof Paar and Jan Pelzl 13/27
Cryptographically Secure Pseudorandom Number Generator (CSPRNG) Special PRNG with additional property: Output must be unpredictable More precisely: Given n consecutive bits of output si , the following output bits sn+1 cannot be predicted (in polynomial time). Needed in cryptography, in particular for stream ciphers Remark: There are almost no other applications that need unpredictability, whereas many, many (technical) systems need PRNGs. Understanding Cryptography by Christof Paar and Jan Pelzl 14/27
Outline Intro to stream ciphers Random number generators (RNGs) Linear feedback shift registers (LFSRs) Examples of stream ciphers A5/1 RC4 Trivium: a modern stream cipher Understanding Cryptography by Christof Paar and Jan Pelzl 15/27
Linear Feedback Shift Registers (LFSRs) Concatenated flip-flops (FF), i.e., a shift register together with a feedback path Feedback computes fresh input by XOR of certain state bits Degreem given by number of storage elements If pi= 1, the feedback connection is present ( closed switch), otherwise there is no feedback from this flip-flop ( open switch ) Output sequence repeats periodically Maximum output length: 2m-1 Understanding Cryptography by Christof Paar and Jan Pelzl 16/27
Linear Feedback Shift Registers (LFSRs): Example with m=3 clk FF2 1 FF1 0 FF0=si 0 0 LFSR output described by recursive equation: s s s + = + + 1 0 1 0 mod 2 2 1 0 1 3 1 i i i 3 1 1 0 4 1 1 1 Maximum output length (of 23-1=7) achieved only for certain feedback configurations, .e.g., the one shown here. 5 0 1 1 6 0 0 1 7 1 0 0 8 0 1 0 Understanding Cryptography by Christof Paar and Jan Pelzl 17/27
Security of LFSRs LFSRs typically described by polynomials: ) ( p x x P l + = + + + 1 m m ... x p x p 1 1 0 Single LFSRs generate highly predictable output If 2m output bits of an LFSR of degree m are known, the feedback coefficients piof the LFSR can be found by solving a system of linear equations* Because of this many stream ciphers use combinations of LFSRs *See Chapter 2 of Understanding Cryptography for further details. Understanding Cryptography by Christof Paar and Jan Pelzl 18/27
Outline Intro to stream ciphers Random number generators (RNGs) Linear feedback shift registers (LFSRs) Examples of stream ciphers A5/1 RC4 Trivium: a modern stream cipher Understanding Cryptography by Christof Paar and Jan Pelzl 19/27
Stream Ciphers Examples A5/1 o Based on combinations of LFSRs o Used in GSM mobile phone system RC4 o Based on a changing lookup table o Used in WEP, WPA, BitTorrent, MS Office XP, TLS/SSL (prohibited now by RFC 7465), SSH (optionally), Remote Desktop (optionally), PDF, Skype (modified form) RC4 o Based on combinations of LFSRs o Selected by the EU ECRYPT network as Profile II of the eSTREAM project Stream Ciphers 20
A5/1 A5/1 uses 3 LFSRs (X, Y, Z) o X: 19 bits (x0,x1,x2, ,x18) o Y: 22 bits (y0,y1,y2, ,y21) o Z: 23 bits (z0,z1,z2, ,z22) Stream Ciphers 21
A5/1: Keystream At each step: m = maj(x8, y10, z10) o Examples: maj(0,1,0) = 0 and maj(1,1,0) = 1 If x8 = m then Xsteps o t = x13 x16 x17 x18 o xi = xi 1 for i= 18,17, ,1 and x0 = t If y10 = m then Ysteps o t = y20 y21 o yi = yi 1 for i= 21,20, ,1 and y0 =t If z10 = m then Zsteps o t = z7 z20 z21 z22 o zi = zi 1 for i= 22,21, ,1 and z0 = t Keystream bit is (x18 y21 z22) Stream Ciphers 22
A5/1: Keystream X x8 x0 x1 x2 x3 x4 x5 x6 x7 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 Y y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 y20 y21 y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 Z z9z10 z11 z12 z13 z14 z15 z16 z17 z18 z19 z20 z21 z22 z0 z1 z2 z3 z4 z5 z6 z7 z8 Each variable here is a single bit Key is used as initial fill of registers Each register steps (or not) based on maj(x8, y10, z10) Keystream bit is XOR of rightmost bits of registers Stream Ciphers 23
A5/1 X 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 Y 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 Z 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 In this example, m = maj(x8, y10, z10)= maj(1,0,1) = 1 Register X steps, Y does not step, and Z steps Keystream bit is XOR of right bits of registers Here, keystream bit will be 0 1 0 = 1 Stream Ciphers 24
RC4 A self-modifying lookup table Table always contains a permutation of the byte values 0,1, ,255 Initialize the permutation using key At each step, RC4 does the following o Swaps elements in current lookup table o Selects a keystream byte from table Each step of RC4 produces a byte o Efficient in software Each step of A5/1 produces only a bit o Efficient in hardware Stream Ciphers 25
RC4 Initialization S[] is permutation of 0,1,...,255 key[] contains N bytes of key for i = 0 to 255 S[i] = i K[i] = key[i (mod N)] next i j = 0 for i = 0 to 255 j = (j + S[i] + K[i]) mod 256 swap(S[i], S[j]) next i i = j = 0 Stream Ciphers 26
RC4 Keystream For each keystream byte, swap elements in table and select byte i = (i + 1) mod 256 j = (j + S[i]) mod 256 swap(S[i], S[j]) t = (S[i] + S[j]) mod 256 keystreamByte = S[t] Use keystream bytes like a one-time pad Note: first 256 bytes should be discarded o Otherwise, related key attack exists Stream Ciphers 27
A Modern Stream Cipher - Trivium Three nonlinear LFSRs (NLFSR) of length 93, 84, 111 XOR-Sum of all three NLFSR outputs generates key stream si Small in Hardware: Total register size: 288 FFs Non-linearity: 3 AND-Gates 7 XOR-Gates (4 with three inputs) Understanding Cryptography by Christof Paar and Jan Pelzl 28/27
Trivium The input of each register is computed as the XOR-sum of two bits: The output bit of another register One register bit at a specific location is fed back to the input (e.g., bit 68 of register A is fed back to its input) The output of each register is computed as the XOR-sum of three bits: The rightmost register bit One register bit at a specific location is fed forward to the output (e.g., bit 66 of register A is fed to its output) The output of a logical AND function whose input is two specific register bits Understanding Cryptography by Christof Paar and Jan Pelzl 29/27
Trivium Initialization: Load 80-bit IV into leftmost bits of A Load 80-bit key into leftmost bits of B Set c109 , c110 , c111 = 1, all other bits 0 Warm-Up: Clock cipher 4 x 288 = 1152 times without generating output needed for randomizing the cipher sufficiently makes sure the key stream depends on both the key and the IV Key stream: XOR-Sum of all three NLFSR outputs generates key stream si - Design can be parallelized to produce up to 64 bits of output per clock cycle - Can achieve encryption rates of 2 Gb/s (H/W) and 1 Gb/s (S/W) using moderate clocks Register length Feedback bit Feedforward bit AND inputs A 93 69 66 91, 92 B 84 78 69 82, 83 C 111 87 66 109, 110 Understanding Cryptography by Christof Paar and Jan Pelzl 30/27
Trivium Security AND operation is equal to multiplication in modulo 2 arithmetic If we multiply two unknowns, and the register contents are the unknowns that an attacker wants to recover, the resulting equations are no longer linear i.e., they contain products of two unknowns Feedforward paths involving AND operation are crucial for security of Trivium as they prevent attacks that exploit the linearity of the cipher (vs. plain LFSRs) Understanding Cryptography by Christof Paar and Jan Pelzl 31/27
Lessons Learned Stream ciphers are less popular than block ciphers in most domains such as Internet security. There are exceptions, for instance, the popular stream cipher RC4. Stream ciphers sometimes require fewer resources, e.g., code size or chip area, for implementation than block ciphers, and they are attractive for use in constrained environments such as cell phones. The requirements for a cryptographically secure pseudorandom number generator are far more demanding than the requirements for pseudorandom number generators used in other applications such as testing or simulation Single LFSRs make poor stream ciphers despite their good statistical properties. However, careful combinations of several LFSR can yield strong ciphers. Understanding Cryptography by Christof Paar and Jan Pelzl 32/27
