$$AES_{k_1}(C_1) \oplus AES_{k_2}(C_2)$$

where AES is used in CTR mode, $C$ is a 128 bit incrementing counter, keys and counters for both transforms are random as well as unique, and the XOR occurs on every 16 byte block.

If I did this, would the XORed output be less secure than the size of state used to seed the generator? Does this method reduce security or introduce vulnerabilities to the random output?

  • $\begingroup$ You should fix your notation so that different variables get different symbols. (e.g. $k_1$ and $k_2$). With its current definition your function is simply zero. $\endgroup$ – CodesInChaos Sep 4 '14 at 15:19
  • $\begingroup$ Meet-in-the-middle means that this isn't stronger against brute-force than single AES in some popular cost models. (Not sure if they are realistic models) $\endgroup$ – CodesInChaos Sep 4 '14 at 15:20
  • $\begingroup$ Notation changed, thanks CodesInChaos. So long as the periods between state exchange are relatively short, (100kb), doesn't this mitigate meet in the middle and timing attacks? $\endgroup$ – JGU Sep 4 '14 at 15:29

No, this is safe.

In fact, if you show a way of distinguish the stream $AES_{k_1}(C) \oplus AES_{k_2}(C)$ from a random stream with fewer than $2^{64}$ outputs, you have just demonstrated a way of distinguishing AES from a random permutation.

Here is how this works: suppose we are given Oracle assess to a permutation $P$, which might be $AES_{k_1}$ for some unknown key $k_1$, or might be a truly random permutation.

Then, we ask the Oracle for the values $P(C), P(C+1), ..., P(C+n)$, select a random $k_2$, and compute the sequence $P(C)\oplus AES_{k_2}(C), P(C+1)\oplus AES_{k_2}(C+1), ..., P(C+n)\oplus AES_{k_2}(C+n)$. Then, we run our stream distinguisher on that.

If $P = AES_{k_1}$ for some $k_1$, then this is precisely your stream, and the distinguisher will say "Yes"

If $P$ is a random permutation, well, with fewer than $2^{64}$ outputs, we can treat it as a random function (as collisions are inprobable). With $P$ as a random function, any value $(C+i)\oplus AES_{k_2}(C+i)$ is a random value; hence the whole stream is a random string, and so the distinguisher will say "No".

  • $\begingroup$ Thank you so much.. this is what I thought, (though I'm not as good at math as you ;o) So to brute force something like this, with a seed size of 768 bits, it would require 2 pow (768 - 1), is that correct? $\endgroup$ – JGU Sep 4 '14 at 15:22
  • $\begingroup$ @John: no, there are cleverer ways to recover the initial state. However, if you use AES-256, any such method would have to start out with "try to find a 256 key which...", which is completely infeasible. Of course, is there a specific reason why you just don't do simple counter mode with a single AES-256 key? $\endgroup$ – poncho Sep 4 '14 at 15:26
  • 4
    $\begingroup$ That pseudo OTP sounds like a stream cipher to me, and when you use CTR with AES-256 (correctly) then you've already met the criteria (given that AES-256 isn't broken in the mean time, but that goes for any algorithm). $\endgroup$ – Maarten Bodewes Sep 4 '14 at 15:39
  • 3
    $\begingroup$ @John, if you use pseudorandom numbers, it's by definition "pseudo-OTP", i.e. a stream cipher. A true one time pad requires as much entropy as the enciphered text, meaning your key has to be at least as long as that. There's no way around that. $\endgroup$ – otus Sep 4 '14 at 15:59
  • 1
    $\begingroup$ Using the expression 'pseudo-OTP' gives you a false sense of security, as you already said: "... so a higher level of security is implied". This is just plain wrong, if you use anything else than true randomness for every single bit of they entire keystring. As otus said, this is a stream cipher, and you should treat it that way. $\endgroup$ – tylo Sep 4 '14 at 16:15

The sum of PRPs is a secure PRF. That paper gives as a security bound for a sum of two independent PRPs $q^3/2^{2n-1}$, where $q$ is the number of queries and $n$ the block size (i.e. 128 for AES).

That means that your construction, correctly used, is more secure than a single PRP, for which the bound is $q^2/2^n$. If you wanted to give an adversary an advantage at most $2^{-k}$ then you could use the sum $2^{(2n-k)/3}$ times. For e.g. $k=64$ that's $2^{64}$, which should be enough (256 exbibytes). In comparison, with a single PRP you could only use it $2^{32}$ times (32 gibibytes).

Note, the advantage is not about revealing the key, it's about revealing anything about the numbers. In stream cipher use that could mean something like: "most likely these two blocks that have the same ciphertext differ in their plaintexts".

In practice this won't matter. As long as you follow normal key lifetimes you can just use AES in a proper cipher mode for encryption, or use it in CTR DRBG if you need random numbers for another purpose.

  • $\begingroup$ Actually, I hadn't considered length in that context, so a dual implementation could be implemented say for a vpn technology, that would require far fewer state transitions to remain viable? I'll read the paper, very interesting.. thanks $\endgroup$ – JGU Sep 4 '14 at 16:24
  • $\begingroup$ @John, not sure what you mean by dual, but yes, a XOR construction requires less frequent rekeying. $\endgroup$ – otus Sep 4 '14 at 18:08
  • $\begingroup$ I mean the proposed algorithm stated in the question; 'dual' AES-CTR xored. So is there any downside to this construction that you can think of, other than the additional time required to produce the output? $\endgroup$ – JGU Sep 4 '14 at 18:23
  • $\begingroup$ @John, well, one downside is the fact that there are weak keys: if you end up with $k_1 = k_2$ and $C_1 = C_2$ the random numbers will all be zero. To avoid this, you could e.g. always set the high bit of $C_1$ to be 0 and $C_2$ to be 1. However, the main thing is that normal AES is simpler and sufficient, unless rekeying is somehow impossible or impractical. $\endgroup$ – otus Sep 4 '14 at 18:32
  • $\begingroup$ the internal state machine insures that such duplications are practically impossible. Thanks Otus.. $\endgroup$ – JGU Sep 4 '14 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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