# How can we implement a PRF with 1bit input space and 1024bit output space using AES securely?

I'm considering an implementation of PRF $$F:\{0,1\} \times \mathcal{K} \rightarrow \{0,1\}^{1024}$$ with a key space $$\mathcal{K}$$ in particular with AES-128 in counter mode.

Since output space is 1024 bit and one block size is 128 bit, we need to use 8 blocks to encrypt a counter and a nonce. The counter is incremented in some way every time a block encryption is finished. Then, an input $$m$$ is XORed to each of the encrypted blocks. So a string that concatenates 8 encrypted blocks is considered as an output of the function.

Is this secure? Any correlation between two encrypted blocks?

• You may want to note that a PRF has to be stateless and deterministic, so XOR'ing the message with a fixed AES counter output has similar security properties to $F_k(x)=k\oplus x$. – SEJPM Dec 17 '19 at 16:19
• Thank you the comment. Does it imply the encryption is secure even if the counter is public? – user9414424 Dec 18 '19 at 0:49

It is secure. There would be an issue if that you generalize the idea to ridiculously long outputs. Any time you use two distinct inputs with a PRP using the same key, the outputs will necessarily be different. But for an ideal PRF there is a tiny chance that different 128-bit blocks could share the same value.

Because you only have 8 blocks, though, you wouldn't actually see duplicate blocks from an ideal black box PRF in practice. As a rule of thumb, you would not expect to see any duplicates until you look at around $$2^{64}$$ blocks. (See the "birthday paradox" and switching lemma.)

I'd discourage someone from doing anything more complicated with AES to mask that potential artifact. ECB encrypting the blocks with values 0 through 7, if the input is 0, or the values 8-15, if the input is 1, would be sufficient.

A variable nonce isn't actually needed. You can just use a constant, such as zero.

Alternatively you could replace AES with a (non-block-cipher) PRF. HMAC or ChaCha20, for example.

• Thank you for the excellent answer! Do you have any source for the information about zero nonce is even secure? – user9414424 Dec 18 '19 at 3:15
• @user9414424 The idea behind CTR mode is that you derive a random keystream by using a non-repeating sequence of input blocks. A block cipher acts like a random mapping between input block values and output block values. Because of that (pseudo)random quality, it doesn't matter to security what your non-repeating sequence is, as long as it is independent of the key. (But obviously it matters to interoperability, if that's important, that you use the standard method to generate that sequence. And that method is just concatenating a single-use number (nonce) with a counter.) – Future Security Dec 18 '19 at 5:12
• A nonce is a number used only once with a given key. Usually a nonce A) Is safe to reuse if and only if a different secret key is used for the two separate usages, B) Does not need to be secret, and C) Doesn't need to be random. CTR mode, specifically, uses a nonce with all three properties. A constant nonce is acceptable for CTR-mode encryption if you will only ever encrypt one message. It is also not unusual to use a counter value for nonces. (You then, of course, need to keep that counter from getting rolled back or reset under any circumstances. Like if you lose power.) – Future Security Dec 18 '19 at 5:45