Stream Ciphers - Understanding Cryptography - page 39

y i ≡ x i + s i mod 2

where s i are the bits of the binary representation of the PRNG output symbols S j .
But Oscar can easily launch an attack. Assume he knows the first 300 bits of
plaintext (this is only 300/8=37.5 byte), e.g., file header information, or he guesses
part of the plaintext. Since he certainly knows the ciphertext, he can now compute
the first 300 bits of key stream as:

s i ≡ y i + x i mod m , i = 1 , 2 ,..., 300

These 300 bits immediately give the first three output symbols of the PRNG: S 1 =
( s 1 ,..., s 100 ), S 2 =( s 101 ,..., s 200 ) and S 3 =( s 201 ,..., s 300 ). Oscar can now generate
two equations:

S 2 ≡ AS 1 + B mod m

S 3 ≡ AS 2 + B mod m

Z

This is a system of linear equations over m with two unknowns A and B . But those

two values are the key, and we can immediately solve the system, yielding:

A ≡ ( S 2 − S 3 ) / ( S 1 − S 2 ) mod m

B ≡ S 2 − S 1 ( S 2 − S 3 ) / ( S 1 − S 2 ) mod m

In case gcd(( S 1 − S 2 ) , m )) = 1 we get multiple solutions since this is an equation sys-

tem over Z m . However, with a fourth piece of known plaintext the key can uniquely

be detected in almost all cases. Alternatively, Oscar simply tries to encrypt the mes-
sage with each of the multiple solutions found. Hence, in summary: if we know a
few pieces of plaintext, we can compute the key and decrypt the entire ciphertext!

This type of attack is why the notation of CSPRNG was invented.

Building Key Streams from CSPRNGs

What we need to do to prevent the attack above is to use a CSPRNG, which assures
that the key stream is unpredictable. We recall that this means that given the first n
output bits of the key stream s 1 , s 2 ,..., s n , it is computationally infeasible to com-
pute the bits s n +1 , s n +2 ,... . Unfortunately, pretty much all pseudorandom number
generators that are used for applications outside cryptography are not cryptograph-
ically secure. Hence, in practice, we need to use specially designed pseudorandom
number generators for stream ciphers.
The question now is how practical stream ciphers actually look. There are many
proposals for stream ciphers out in the literature. They can roughly be classified as
ciphers either optimized for software implementation or optimized for hardware im-
plementation. In the former case, the ciphers typically require few CPU instructions