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