Pseudorandom Number Generator (PRNG)¶
links: AC1 TOC - Randomness - Index
A PRNG is a deterministic function which produces a bit-string of length \(l\) which "looks like" random. This means that there isn't a pattern to be found that could predict the next bit. While RNG must guarantee randomness and be effectively random, a PRNG is allowed to create \(l\)-bit-strings which are almost random. This means that a distinguisher \(D\) is unable to distinguish the output of the PRNG from the true RNG with negligible deviation from the optimal probability. A PRNG is deterministic which means, that the output of a PRNG can be reproduced if you know the seed (the initialization value of the PRNG). The optimal probability is \(1 \over {k_{states}}\) , where \(k_{states}\) is the number of possible states a sign in the generated output-string can have (e.g. in a bit-string a sign can have to states: \(1\) and \(0\), which results in \(\mathbb{P}(s_i = 1) \approx \mathbb{P}(s_i = 0) \approx {1 \over 2}\) for each sign \(s_i \in s\), \(s\) a bit-string).
Distinguisher¶
To understand PRNG it is important to understand the concept of the distinguisher (as described by Lindell & Katz, p. 61). A distinguisher is a statistical test which shall return 1, given the output string of a PRNG, with the same probability as if the input to \(D\) was a uniformly distributed string of same length.
Requirements¶
For a PRNG to be secure, it requires a few assumptions to be met:
- \(l(n) > n\) . This means that for any security parameter \(n\), the length of the output must be at least as long as the security parameter (otherwise it would mean a security downgrade, because this would lead to shorter pads resulting in a lower security parameter.
- The probability for a bit \(s_i, i \in 1,.., l(n)\) in bit-string \(s\) to be 1 or 0 must be equal \(1 \over 2\) with some negligible deviation \(negl(n)\) which is dependent from the security parameter \(n\)
- If using a PRNG for security purposes, the seed of the PRNG must be kept secret, otherwise it's easy to recreate the random bit-strings.
Construct PRG (Pseudo Random Generator) from PRF (Pseudo Random Function)¶
Let's assume \(F\) is a pseudorandom function that takes a secret key \(k\) and an input \(x\), and produces a pseudorandom output \(y\). So \(F(k, x) = y\).
- Choose an initial seed \(s_0\) as the secret key for the PRF. The seed \(s_0\) must be chosen randomly and kept secret.
- For generating the n-th pseudorandom number, use the PRF \(F\) with the seed \(s_0\) and \(n\) as the inputs. The output of the PRF is the n-th pseudorandom number. So the n-th pseudorandom number is \(F(s_0, n)\).
- Repeat step 2 for generating more pseudorandom numbers. Each new pseudorandom number can be generated by simply incrementing n.
In this construction, the PRF is essentially acting as the PRNG's deterministic algorithm, generating a sequence of pseudorandom numbers based on the initial seed \(s_0\).
Other properties¶
When we talk about PRNGs in cryptography we always talk about CSPRNGs (Cryptographically secure pseudorandom number generator). A CSPRNG must have two properties:
- Satisfy next-bit test. That is, given the first \(k\) bits of a random sequence, there is no polynomial-time algorithm that can predict the (\(k+1\))th bit with probability of success non-negligibly better than 50%
- Withstand state compromise extensions. In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input's state to predict future conditions of the CSPRNG state.
Linearity of a PRNG
If a PRNG is linear, so the next step is predictable. We need multiple rounds therefore in one step to solve this. If you stir Latte Macchiato for one round you could still see where each atom went (maybe not^^). But after some time has passed it will become impossible.
Periods in a PRNG
A PRNG can end up in a loop at some point or depending on the size start again at the beginning. The shorter this period is the less entropy a PRNG has. Therefore we use a big seed to begin with already. This seed depends on the security level also. A higher seed means also a higher period.
If a PRNG is used for a long time without re-seeding, there's a potential risk that the output sequence could start to repeat or that an attacker could start to infer the internal state of the PRNG. To counter this we re-seed the PRNG using true randomness again from the TRNG.
links: AC1 TOC - Randomness - Index