I'm currently reading "Cryptography Engineering - Design Principles and Practical Applications" written by "Niels Ferguson, Bruce Schneier, Tadayoshi Kohno" published by Wiley in 2010.

In "Chapter 9 Generating Randomness", "Section 9.4 The Generator", there are two paragraphs (see screenshot below) which I do not quite understand.

enter image description here

In particular, how does the author comes with the probability of $2^{-97}$, the number of requests as $2^{97}$, and the total workload for the attacker as $2^{113}$ steps?

enter image description here

This continues from the above question. How does the author mean there are $2^{113}$ steps on both the attacker's machine and the machine that is being attacked?

Any kind folks who can help to explain this clearly greatly appreciated!

Thanks in advance!


1 Answer 1


This section talks about Fortuna, where it uses a block cipher with a 128-bit block and a 256-bit key size. The cipher is used in CTR mode. In the CTR mode, if an attacker can access the internal state than then the security is lost ( the key and current counter value), therefore after a request, 2 new blocks are generated and used as a new key, and the old key is forgotten to eliminate exposure of the old requests.

All talk is about distinguishing the PRP from PRF in the CTR mode. In the CTR mode with a PRP, if you encrypt with one key then $2^{128}$ blocks are distinct since it is a permutation, but we don't expect this from a PRF. So the PRP-PRF switching lemma applies to distinguish the statistical deviation. After $q$ messages the security lost is proportional to $q^2\!/2^{128}$.

In the classical birthday attack, when the outputs are random we expect collisions, remember the CTR mode doesn't generate one with PRP. For a PRF with 128-bit output, approximately

  • Once we generate $2^{64}$ outputs there will be $$\approx (2^{64})^2/2^{128}/2 = 2^{128 - 129} = 1/2$$ change collision. But we will not see one in the Fortuna, it uses PRP in CTR mode! Therefore this is a distinguisher.

  • if you only generate $2^{16}$ blocks for a single key then the probbaility is $$\approx (2^{16})^2/2^{128}/2 = 2^{32 - 129} = \dfrac{1}{2^{97}}$$ this means this distinguish probability is negligible.

Requesting $2^{97}$ blocks is the reverse of the birthday attack. Since one has $\dfrac{1}{2^{97}}$ change of seeing a collision for $2^{16}$ blocks then you need to request $2^{97}$ blocks to see a collision within a $2^{16}$-block. Therefore the cost is $2^{97}\cdot 2^{16} = 2^{113}$.

For 256-bit block sizes, the collision is no more a threat since you need to $2^{128}$ blocks to see one with 1/2 probability.

$$\approx (2^{128})^2/2^{256}/2 = 2^{256 - 257} = 1/2$$

The $2^{113}$ is continuation from the 128-bit attack cost, since $$(2^{113})^2/2^{256}/2 = \dfrac{1}{2^{32}}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.