Cryptography Reference
In-Depth Information
Cryptographically Secure Pseudorandom Number Generators (CSPRNG)
Cryptographically secure pseudorandom number generators (CSPRNGs)
are a spe-
cial type of PRNG which possess the following additional property: A CSPRNG is
PRNG which is
unpredictable
. Informally, this means that given
n
output bits of the
key stream
s
i
,
s
i
+1
,...,
s
i
+
n
−
1
, where
n
is some integer, it is computationally infea-
sible to compute the subsequent bits
s
i
+
n
,
s
i
+
n
+1
,...
. A more exact definition is that
given
n
consecutive bits of the key stream, there is no polynomial time algorithm
that can predict the next bit
s
n
+1
with better than 50% chance of success. Another
property of CSPRNG is that given the above sequence, it should be computationally
infeasible to compute any preceding bits
s
i
−
1
,
s
i
−
2
,...
.
Note that the need for unpredictability of CSPRNGs is unique to cryptography.
In virtually all other situations where pseudorandom numbers are needed in com-
puter science or engineering, unpredictability is not needed. As a consequence, the
distinction between PRNG and CSPRN and their relevance for stream ciphers is of-
ten not clear to non-cryptographers. Almost all PRNG that were designed without
the clear purpose of being stream ciphers are not CSPRNGs.
2.2.2 The One-Time Pad
In the following we discuss what happens if we use the three types of random num-
bers as generators for the key stream sequence
s
0
,
s
1
,
s
2
,...
of a stream cipher. Let's
first define what a perfect cipher should be:
Definition 2.2.1
Unconditional Security
A cryptosystem is unconditionally or information-theoretically se-
cure if it cannot be broken even with infinite computational re-
sources.
Unconditional security is based on information theory and assumes no limit on
the attacker's computational power. This looks like a pretty straightforward defini-
tion. It is in fact straightforward, but the requirements for a cipher to be uncondi-
tionally secure are tremendous. Let's look at it using a gedankenexperiment: As-
sume we have a symmetric encryption algorithm (it doesn't matter whether it's a
block cipher or stream cipher) with a key length of 10,000 bits, and the only attack
that works is an exhaustive key search, i.e, a brute-force attack. From the discussion
in Sect. 1.3.2, we recall that 128 bits are more than enough for long-term security.
So, is a cipher with 10,000 bits unconditionally secure? The answer is simple: No!
Since an attacker can have
infinite
computational resources, we can simply assume
that the attacker has 2
10000
computers available and every computer checks exactly
one key. This will give us a correct key in one time step. Of course, there is no way
that 2
10000
computer can ever be built, the number is too large. (It is estimated that