0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Related and helpful: crypto.stackexchange.com/q/5447/32035 $\endgroup$
    – hardyrama
    Commented Jun 24, 2019 at 13:53
  • $\begingroup$ @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... $\endgroup$
    – Paul Uszak
    Commented Jun 24, 2019 at 20:41

1 Answer 1

Reset to default
1
$\begingroup$

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.)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$
    – Ella Rose
    Commented Jun 24, 2019 at 16:54
  • $\begingroup$ @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. $\endgroup$
    – Future Security
    Commented Jun 24, 2019 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.