The role of IV when AES is used as $PRF$

Question

We want to use AES as a pseudorandom function. Given a random master key, we want to derive a set of pseudorandom values/keys, e.g say $n$ keys. Then from each of those derived keys, we want to derive a set of pseudorandom values, say $d$.

I think, one way of doing that is to encrypt $1,...,n$ using the master key. This gives us $n$ ciphertext. Then, we use each ciphertext as a key to encrypt $1,...,d$.

Question 1: In the above case, do we need to generate a random IV each time we encrypt a message. Does that mean we have to store all IV?

Question 2: If the answer to the above question is yes, then which PRF (that requires only one seed and IV) is suitable for the above case? Can we use the hash of each input, i.e. index, as IV?

Note that in the above case, IV does not need to be public.

Answer 1

AES does not itself have a concept of ‘initialization vector’—initialization vectors are basically an artifact of ciphers for long messages built out of fixed-size components. AES is just a keyed family of permutations of 128-bit strings.

You can use the AES permutation as such as you described—with the caveat that you should use AES-192 or AES-256 if you want a standard ‘128-bit security level’. Of course, then you need a 256-bit key which you can't get by a single invocation of AES One way you can use AES-256 to generate 256-bit keys is to alternate between even and odd inputs: derive the $i^{\mathit{th}}$ subkey $k_i$ from the master key $k$ by $$k_i = \operatorname{AES256}_k(2i) \mathbin\| \operatorname{AES256}_k(2i + 1).$$ You'll never get a key that consists of the same 128 bits repeated twice, but the probability of that was negligible anyway; the standard PRF/PRP switching lemma provides bounds on the probability of a problem from this. Essentially this structure is used by, e.g., AES-GCM-SIV (or at least the last incarnation of it that I saw). However, there's another couple of caveats about AES:

1. In software, changing AES keys is expensive.
2. In software, there is a conflict between fast AES implementations and secure AES implementations that don't leak secrets through timing side channels.

Systems like AES-GCM-SIV were designed under the premise that you can actually audit your software stack all the way down to the assembly code to guarantee that you're actually getting hardware AES support. There's a much simpler, safer, and more confidence-inspiring way to do it, which doesn't even involve a PRF/PRP switching cost: use a PRF designed for security in fast software like ChaCha instead.