# Can you defeat AES-CTR's birthday boundary with a 2nd AES?

This follows on from How do I produce a stream of secure random numbers from AES-Counter mode?

Consider then the generator:-

$$\operatorname{AES_{k1}}(n) \oplus \operatorname{AES_{k2}}(n)$$

where $$k1 \ne k2$$, and $$n$$ is the single counter variable. And we take care to ensure that there is no relationship between $$k1$$ and $$k2$$. If this really does create a pseudo random function, will the birthday boundary for AES-CTR output be overcome?

• Related and helpful: crypto.stackexchange.com/q/5447/32035 – hardyrama Jun 24 '19 at 13:53
• @hardyrama Indeed very. Apologies for the repetition then. I haven't used the PRF acronym so the related ones didn't pop up when I authored it... – Paul Uszak Jun 24 '19 at 20:41

Yes. The number of $$n$$-bit blocks you can encrypt with this construction is proportional to $$2^n$$ instead of just $$2^{n/2}$$. So for AES this shouldn't be a problem because you can't process anything near $$2^{128}$$ blocks.

A secure stream cipher can be constructed from a PRF using something similar to AES-CTR.

AES is more accurately described as a PRP than a PRF, but this distinction is unimportant if the number of queries an attacker is allowed to make under a given key is much much less than $$2^{64}$$.

(See PRF switching lemma. If the number of queries the attacker can make is much less than $$2^{n/2}$$, then it is safe to substitute an $$n$$-bit PRP for a PRF. This is where AES-CTR's limit comes from.)

However it has been proven that the XOR of two PRPs is a secure PRF instead for up to $$\mathcal{O}(2^n)$$ queries. 1 2

Readers should note that this isn't the same as saying that you can use up to precisely $$2^n$$ blocks. For this reason, I strongly discourage using a block cipher algorithm with smaller blocks (like DES, Simon, or Speck) in this kind of construct. (Or any other mode, I suppose.)

• Are you sure that 2 instance of AES-CTR xor'd together gives $2^n$ blocks for the bound? Unless I am misreading something, that appears to directly contradict with this answer, which claims security up to $2^{2b/3}$ queries for the construction – Ella Rose Jun 24 '19 at 16:54
• @EllaRose One of the papers I linked to cites Lucks for prior work. (As well as another paper that improved on Lucks' bounds.) Each of these sources, I think, give a minimum number of queries an attacker needs to make. Lucks provided a bound on how few q the best possible attack must require. Subsequent work provided tighter bounds. None were numbers from actual discovered attacks. "At least this difficult" in other words. – Future Security Jun 24 '19 at 17:40