Functional difference between stream cipher, XOF, seed expander, KDF, etc

Question

This question is a request for terminology clarification.

1. In a canonical XOF interface, the output can be extended as much as needed, but does input has to be variable-length or can be fixed-length in certain constructs?

SHAKE{128|256} are the first well-known standardized XOFs, there are many ad-hoc constructs before it such as OAEP-MGF, AES-CTR, RC4/ChaCha20-based arc4random() function.

2. For AES-CTR and RC4/ChaCha20, are they also XOF in any sense? If not, what are they strictly speaking?

3. What does a seed-expander do? Does it take a fixed/variable-length bitstring as input and produce another fixed/variable-length bitstring as output?

4. What exactly is the relationship between XOF, Seed-Expander, (optionally bring up KDF).

Answer 1

Before we start answering the subquestions, let's bring up some background knowledge.

The sponge construct was first proposed by the Keccak team as a bridging element in a security proof for the older RadioGatún hash function. On their web page, they describe it as a generalization of both hash function (var->fix) and stream cipher (fix->var).

Since SHAKE-128/256 are directly based on sponge constructs, we'll just assume for now that the authors intended XOF as the generic term for their trademark product Sponge.

type                input                  output
stream cipher       fixed-length key       variable-length key-stream
xof                 variable-length data   variable-length data
hash function       variable-length data   fixed-length digest

So question 1 can be answered as follows: no, that would violate the definition of XOF.

And question 2: no. They're stream ciphers, two of which use the counter construct.

If you search "cryptographic seed-expander" on Bing in 2018-02, then the first few results unrelated to Crypto.SE refer to the NIST page for post-quantum cryptography. The story goes like this:

Back in the early days of preparing for the contest, NIST specified that submitters obtain randomness source for their keygen-signing-encrypt functions using libc rand(). This was correctly met with protest by notable participants on the official mailing list.

After discussion, it was decided there would be separate randomness calls for 1.) generating small amounts of keying material sufficient for a given security level, and for 2.) expanding keying material into a longer bitstring from which mathematical objects could be extracted.

The latter has since been called "seed expander" in official NIST documents, which roughly corresponds to DRBG.

So question 3 can be answered as follows: It does what a DRBG/PRNG does. The interface of a DRBG applies.

I'd like to answer question 4 as follows: It doesn't make sense to compare them, because their purposes are different. And this difference in purpose makes their programming interface different as well. For example, the typical interface for a XOF function is much simpler than that for a DRBG, and has many fewer parameters to tune than KDF.

Answer 2

XOF: Input is a message drawn from some message space (usually arbitrary length); output is an extremely long bit string (that the user truncates to their desired length). XOFs have security requirements that correspond to those of traditional cryptographic hash functions: must resist preimage and collision attacks even though there are no secret inputs.

Stream cipher: Input is a uniform random secret key and usually a nonce as well; output is a long bit string that's pseudorandom—an attacker must not be able to tell it apart from a random bit string in any reasonable amount of time.

Seed expander: I'm not sure what precise definition applies here, but it sounds like a function that takes a uniform random seed and outputs a long pseudorandom bit string. Fundamentally similar to a stream cipher, except perhaps with a connotation that each random seed is only ever used once.

KDF: In the strongest sense, this is a function that takes non-uniform random input, produces close-to-uniform pseudorandom output. There's also a weaker sense: a function that takes a uniform random key and produces longer, strong derived pseudorandom keys. (The first sense is embodied by HKDF-Extract, the second by HKDF-Expand, the two halves of the HKDF scheme.)

---

The most important concept here by far I'd say is functions that take random secret inputs vs. functions that don't. That distinguishes XOFs from the rest of the list more than anything about input or output lengths. You can feed an input that contains a random secret key into an XOF, but that's a contingent detail of the way you're using it; the function is designed to resist attacks in scenarios where there isn't any secret (e.g., hashing messages for digital signatures).

Conversely, you must feed a random secret key to a stream cipher, which isn't designed to resist attacks in scenarios where there isn't one. Which answers one common newbie question: "Can I use a stream cipher as a hash?" Not in general, because fitness as a stream cipher doesn't guarantee fitness as a hash.