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
Search WWH ::




Custom Search