Cryptography Reference
In-Depth Information
Chapter 2
Stream Ciphers and RC4
2.1 Introduction to Stream Ciphers
In general, stream ciphers have faster throughput and are easier to im-
plement compared to block ciphers. However, a specific instance of a block
cipher may be more e
cient than a specific instance of a stream cipher in
terms of speed and implementation.
Let m
1
,m
2
,... be the message bits, k
1
,k
2
,... the keystream bits and
c
1
,c
2
,... the corresponding ciphertext bits. For a typical stream cipher, the
encryption is performed as
c
r
= m
r
⊕k
r
and the decryption is performed as
m
r
= c
r
⊕k
r
.
This bitwise encryption-decryption is also called the Vernam cipher after the
name of its inventor. When a different keystream is used with each different
plaintext message, the Vernam cipher is called a one-time pad. One time pads
have the property of perfect secrecy [164], i.e., the conditional probability of
a message given the ciphertext is the same as the probability of the message;
or, in other words, the ciphertext reveals no information about the plaintext.
Any finite state machine can generate a pseudo-random sequence of a finite
period only. A plaintext message of length larger than this period would cause
violation of the perfect secrecy condition. Hence, ideal one-time pads cannot
be realized in practice.
A practical implementation of stream cipher involves “seeding” a finite
state machine with a finite length key and then deriving the current keystream
bit (or byte or word) as a function of the current internal state. The generated
keystream bit sequence should satisfy the standard randomness tests [88].
Linear Feedback Shift Registers (LFSR) are frequently used as keystream
generators of stream ciphers. A detailed discussion on LFSR is available
in [62]. There exists significant literature on the analysis and design of LFSR-
based stream ciphers that employ Boolean functions (see [32, 142] and the
references therein for details) as non-linear elements. Apart from hardware-
friendly LFSR-based stream ciphers, there have been many works on software-