The Fortuna PRNG uses AES-256 for generating output blocks by encrypting a counter value $C$ in CTR mode using a 256-bit key $K$. For the analysis, it seems the block size of 128 is the limiting factor, as the argument goes that by the birthday bound we expect a block collision after $2^{64}$ encrypted blocks, but CTR mode only collides after $2^{128}$.

All of this depends really only on the block size, so my question is, what is the effect of the key size for the underlying block cipher, and why was it chosen to be 256 bits rather than using AES-128, say?

  • $\begingroup$ AES-256 isn't much more expensive than AES-128, so might as well use that for one of the most critical components in the system. $\endgroup$ – SEJPM Sep 13 '16 at 11:43
  • $\begingroup$ Well, let's forget about AES for a second and think of an arbitrary block cipher. I am interested in how using a block cipher with a 128-bit key and 128-bit block size would affect security. Or, for generality: what if we use an n-bit block cipher and n-bit key, together with a suitable choice of 2n-bit hash function? $\endgroup$ – quantifier Sep 13 '16 at 11:45
  • $\begingroup$ I think Fortuna suffers from multi-target attacks, so you need larger keys to compensate. $\endgroup$ – CodesInChaos Sep 13 '16 at 14:08
  • $\begingroup$ @CodesInChaos can you elaborate on that a bit? Here's my observation. If you repeatedly call (in sequence) 1) initialize 2) seed using fresh seed each time and 3) generate e.g. a single output block, then using a 256-bit hash gives you a colliding CTR mode key after 2^128 attempts. If one was to use a 128-bit key, obtained by e.g. truncating the 256-bit hash, this would probably be less. Is that what you're referring to? $\endgroup$ – quantifier Sep 13 '16 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.