Sponge-based pseudo-random number generators

Forward security

≤

⌈ ⌉
Our construction does not inherently provide forward security, but it can be explicitly triggered by using the following technique. One can fetch r^′ r bits out of the current PRNG and feed them immediately afterwards. This way, the r^′ bits of the outer part of the state will be set to zero, making this process an irreversible step. By repeating this process c/r^′ times, the adversary has to guess at least c bits when evaluating the state backwards. This process can be activated, for instance, at regular intervals.

5. A concrete example with Keccak

Keccak is a family of sponge functions submitted to the SHA-3 contest or- ganized by NIST [13,6,7]. The family uses seven permutations ranging from a width of 25 bits to a width of 1600 bits. While the SHA-3 proposal uses Keccak-f [1600] only, other members of the family with a smaller width can be interesting in the context of a PRNG in an embedded device. For instance, Keccak[r = 96, c = 104] and Keccak[r = 64, c = 136] both use Keccak-f [200] as underlying permutation. This permutation is suitable for devices with scarse resources as the state can be stored in only 25 bytes. In hardware it can be built in a very compact core and in software it can be implemented with bitwise Boolean instructions and rotations within bytes only. These sponge functions can produce 96 and 64 pseudo-random bits, resp., per call to Keccak-f [200].

In terms of security, Keccak follows what is called the hermetic sponge strat- egy [7,5]. This means that the Keccak-f permutations are designed with the target that they cannot be distinguished from a randomly-chosen permutation. Biased output bits on one of the Keccak members, for instance, would imply a distinguisher on the underlying permutation Keccak-f and would therefore contradict the design strategy.
Against passive state recovery attacks in the generic case, Theorem 2 proves a resistance of 2^c/m(A). If a sequence of ℓr output bits is known, the expected value of m(A) is close to 1 unless ℓ > 2^r/2. One can limit to r2^r/2 the number of output bits between times where the state has gained at least c bits of fresh seed- ing material. This way, Keccak[r = 96, c = 104] and Keccak[r = 64, c = 136] provides a resistance of about 2¹⁰⁴ and 2¹³⁶, resp., against state recovery, at least as long as no distinguisher on Keccak-f [200] is found.
If the PRNG allows the user to provide seeding material, active state recovery attacks must also be considered. Here, the implementation can limit, e.g., to ℓ_max = 2²⁴ or 2³² output blocks before the state has again been fed with c bits of fresh seeding material. In this case, Keccak[r = 64, c = 136] provides a resistance of about 2¹¹² and 2¹⁰⁴, respectively.
We have implemented our PRNG based on Keccak[r = 96, c = 104] and Keccak[r = 64, c = 136] and passed the statistical tests proposed by NIST [15]. The tests were performed on 200 sequences of 10⁶ bits each. The sequences were generated by squeezing 2 × 10⁸ bits after providing the empty string as input,
namely ⌊Keccak[r = 96, c = 104]()⌋_2×108 and ⌊Keccak[r = 64, c = 136]()⌋_2×108 .

6.