Why is ISAAC not a pseudo random number generator?

Question

I have been accused of confusion over the nature of the ISAAC algorithm. The bulk of evidence suggests that it is a cryptographically strong pseudo random number generator. By bulk I mean the number of authoritative references pointed to by a Google search of "isaac prng cipher". I offer:-

Bob, the guy who wrote it

Apache Commons random number generator

The Aumasson paper assessing it as a generator

CCAN random number module

Yuen, Practical Cryptology and Web Security

In fact, the only place that describes ISAAC as definitely a cipher is crypto.SE and the Wikipedia article and we all know the authority that can be attributed to Wikipedia.

Yuen's book is perhaps the most telling. It clearly categorises ISAAC as a PRNG but then goes onto construct a cipher system using it as a key stream generator. Yuen goes into great detail how to create a seeding mechanism as there is no official key entry, and codes an XOR mechanism for enciphering. This approach is repeated in the Rosetta Code entry for ISAAC, as is the description of ISAAC as a PRNG.

It appears to be the case that ISAAC is a PRNG. As such, and as any PRNG can, that qualifies it to be a building block of a cipher. In that respect, so can the middle square method be used as a construct within a cipher system if you add some XOR code onto the end. I suggest that is the basis of all of the confusion. But ISAAC is first and foremost a PRNG, isn't it?

Answer 1

Trying to distinguish a synchronous stream cipher from a CSPRNG seems to me a bit like trying to distinguish ice from frozen water. Any secure stream cipher is a CSPRNG, and any CSPRNG can be used as a stream cipher.

Insofar as there is any difference, it mostly comes down to intended purpose and API design. A typical CSPRNG API might take an initial seed value (equivalent to the key of a stream cipher), and allow the user to request small chunks of random output bits, whereas a typical stream cipher API would be initialized with a key and (usually, for modern cipher designs) an IV / nonce, and allow the user to pass in plaintext or ciphertext to be XORed with the output keystream.

Also, speed may not be as important a design criterion for general CSPRNGs as for stream ciphers, since one rarely needs a lot of pseudorandomness quickly unless one is using it as a keystream for encryption.

Now, the ISAAC reference implementation definitely provides a PRNG-style API: you pass in a seed array of 256 32-bit integers, and then request output in 32-bit chunks (either one at a time, or 256 chunks at a time by directly accessing the input/output buffer). The C API does effectively allow treating the seed / output buffer as an array of 1024 bytes (as shown e.g. in the ISAAC challenge code, which seeds the generator with an ASCII string), but the conversion is implicit and platform-dependent (due to endianness issues).

However, while the ISAAC API is that of a PRNG, the algorithm itself is clearly designed with performance in mind, and intended to be competitive with earlier stream cipher designs such as RC4. So, yes, ISAAC as presented by Jenkins is primarily a PRNG, but it's meant to be usable as a stream cipher.

Answer 2

I've certainly been confused over the definitions and scope of these terms as well. Over time, as I've learned more, I've come to see it in terms of two use cases.

---

The first is when two parties share a small random secret, and they need to deterministically expand it into a long pseudorandom one (pseudorandom in the cryptographer's sense, that implies computational security). The key requirement here is that both parties, given the same secret input and no interaction with each other, should be able to deterministically produce the same expansion. Stream ciphers are the paradigm example here.

---

The second case is applications where one party needs to make random choices that other parties cannot reproduce or predict. For example, generating an asymmetric key pair, or choosing random IVs for CBC mode. The prime examples here are operating system random number generators that incorporate:

• Backtracking resistance mechanisms, so that a compromise of the state of the RNG cannot be used to reconstruct earlier outputs;
• Mechanisms for updating the state of the RNG with external entropy data, in order to limit the time window during which an attacker who compromises the RNG state can predict its output.

Generators in this second category could be replaced by a private source of true randomness without affecting the correctness of the applications that use them. These generators use deterministic algorithms because of engineering tradeoffs, not because they need the determinism.

---

Now, in my experience:

1. The terms "random number generator," "pseudorandom number generator," "RNG," "PRNG" and "CSPRNG" in practice are routinely applied to both categories indistinctly. Generally when I encounter those terms I have to look for contextual cues to see which of the two categories is being referred to.
2. The term "stream cipher" is used almost exclusively to refer to the first category. In fact, you often see people refer to this first category as "stream ciphers" even in applications where no message is XORed with the keystream.
3. The only common term I know that is uniquely associated with the second category is NIST's "DRBG" ("deterministic random bit generator"), but it's not in fact a very popular term.

So I'd label ISAAC as a stream cipher, because counterintuitive as it sounds at first, in practice it just communicates what ISAAC is more precisely than the other common terms. But on the other hand if somebody labels it a "(pseudo) random number generator" I certainly wouldn't say they're wrong, but I might have a harder time knowing exactly what they meant.