# Generating non-repeating N-bit IVs, which are indistinguishable from randomness

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?

-
I question the soundness of that part: the protocol imposes the additional requirement that every byte on the wire be statistically indistinguishable from randomness. –  fgrieu Oct 10 '11 at 10:42
@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). –  Paŭlo Ebermann Oct 10 '11 at 11:03
@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. –  Zack Oct 10 '11 at 15:58

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).

-
Yah, the protocol requires rekeying after 2^32 messages for exactly that reason. –  Zack Oct 10 '11 at 1:48
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.) –  Paŭlo Ebermann Oct 10 '11 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.

-
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. –  Paŭlo Ebermann Oct 10 '11 at 11:08