I'm implementing a protocol which needs a 64-bit IV for every encrypted packet. The cipher in use (AES-GCM, more or less as specified in RFC 4106) does not require that these IVs are random, only that they are not repeated for any given key. However, the protocol imposes the additional requirement that every byte on the wire be statistically indistinguishable from randomness.

What I need, therefore, is a PRNG that produces successive 64-bit numbers, and is guaranteed not to repeat itself until all 264 possibilities are exhausted. I don't think this PRNG has to be cryptographically secure, but I imagine it would not hurt. I would seed this PRNG at the same time as I generate the AES key (which is a short-lived session key) from a source of true randomness.

What PRNG algorithm should I use?

  • $\begingroup$ I question the soundness of that part: the protocol imposes the additional requirement that every byte on the wire be statistically indistinguishable from randomness. $\endgroup$
    – fgrieu
    Oct 10, 2011 at 10:42
  • $\begingroup$ @fgrieu I can imaging that if using some steganography scheme, which hides the whole protocol data inside the noise of other data (e.g. low bits of images). $\endgroup$ Oct 10, 2011 at 11:03
  • $\begingroup$ @PaŭloEbermann: Exactly. We don't want any patterns in the steg input that an observer could use to detect the presence of a covert message. $\endgroup$
    – zwol
    Oct 10, 2011 at 15:58

2 Answers 2


I suppose the easiest way to generate these initialization vectors is to use a 64-bit block cipher (like Blowfish or DES/3DES), and encrypt sequential values of a 64-bit counter.

Of course, the "indistinguishable from true randomness" property of good block ciphers is only valid if the attacker can't observe much more than $2^{32}$ such initialization vectors, as then a truly random sequence would start to show duplicate elements, while your one would not, by your requirement.

Actually, if the only requirement is a nonce, and your protocol messages arrive in sending order (like over a TCP connection), you don't have to send it with the actual stream data, as long as the other side has the necessary information to generate it. Then a simple counter, counted up at both sides (and never transmitted), will do nicely (and you don't have to think about another key which needs to be managed).

  • $\begingroup$ Yah, the protocol requires rekeying after 2^32 messages for exactly that reason. $\endgroup$
    – zwol
    Oct 10, 2011 at 1:48
  • $\begingroup$ Ah, if you have that anyways, I think you can also use any cryptographic PRNG - the probability of repetitions is quite small before that. (You might shift the rekeying a bit earlier to be more on the safe side.) $\endgroup$ Oct 10, 2011 at 2:08

My suggestion would be to use the ANSI X9.31 PRNG based on AES. In this case the it must only repeat after $2^{64}$ because the underlying block cipher have a length of 128 bits. The other advantage of this PRNG is that it's too uses AES.

  • $\begingroup$ While the whole sequence of outputs of a PRNG will not repeat early, individual output numbers (128-bit blocks) as well as any 64-bit blocks derived from this will have duplicates earlier. $\endgroup$ Oct 10, 2011 at 11:08

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.