Cryptography Reference
In-Depth Information
Chapter 6
Distinguishing Attacks
The keystream of a stream cipher should ideally be random, i.e., just by
observing the keystream, one should not be able to differentiate it from any
random bitstream.
The best method of generating a random bitstream is to toss an unbi-
ased coin or to record thermal noise in an environment or to probe any such
stochastic process in nature. These random number generators are called True
Random Number Generators (TRNG).
However, when the sender and receiver are far apart, establishing a com-
mon keystream between them by synchronizing TRNGs at both ends is not
feasible in practice. A pragmatic method would be to design a Finite State
Machine (FSM) that generates the same pseudo-random sequence when fed
with a common seed shared between the sender and the receiver. Such an
FSM is called a Pseudo-Random Number Generator (PRNG).
A stream cipher is nothing but a PRNG with the secret key as the seed.
If by analyzing the cipher, one can establish a bias in the probability of oc-
currence of some keystream-based event, then we have a distinguishing attack
or a distinguisher on the cipher.
6.1 A Theoretical Framework of Distinguishing Attacks
Before describing the distinguishing attacks on RC4, let us discuss the
necessary theoretical framework.
The effectiveness of a distinguishing attack is measured by the number of
keystream bits that needs to be inspected for the frequencies of the desired
event to be substantially different in the two streams, the keystream of the
cipher and the random stream. The less this number, the more e
cient is the
attack. The following technical result on the number of samples required to
mount a successful attack appears as Theorem 2 in [107, Section 3.3].
Theorem 6.1.1. Suppose the event A happens in distribution X with proba-
bility p
0
and in distribution Y with probability p
0
(1+ǫ). Then for small p
0
and
ǫ, O(
1
p
0
ǫ
2
) samples su
ce to distinguish X from Y with a constant probability
of success.
