2
$\begingroup$

This is a purely theoretical question. I've found some similar questions, but they're not what I'm asking.

Most importantly, I'm not asking whether anyone can find the hypothetical duplicate. I'm not asking about the probability of encountering a collision, or how long it would take. In short, for my purposes, pretend you're coming to this from a non-crypto math background, and consider all finite numbers to be small, and imagine that you're allowed to do exhaustive searches of any finite space.

For any given key, there is obviously a 1:1 mapping from plaintext to ciphertext.

Now, consider a specific fixed plaintext. There are 1<<128 possible keys. There are 1<<128 possible ciphertexts.

Either there's exactly one key that produces each ciphertext, or at least one ciphertext results from at least two keys, and at least one ciphertext results from zero keys.

If you imagine AES as simply selecting random permutations, this is the birthday problem, and it's effectively certain that there are duplicates -- at least two keys will produce the same ciphertext from your given plaintext, and at least one ciphertext will never occur from that plaintext.

But AES doesn't select random permutations. It selects pseudo-random permutations. The selection process can't select every possible permutation; it can only select some of them. And it is conceivable that the set of permutations it can select has such a trait.

It is trivial to devise a scheme which produces non-overlapping permutations, as long as the number of keys doesn't exceed the number of possible plaintexts. For instance, "treat key and plaintext as unsigned 128-bit values, add them, that's your ciphertext" would have this property.

I have no practical applications for this, but if you want an impractical application: If AES did have this property, then you could interchange the roles of key and plaintext. You could send people blocks that were AES encryptions of a known plaintext, and they could simply look up the key in their table of "which key produces each ciphertext from that fixed plaintext". (Sadly, that table appears to require more storage space than our universe has atoms, but practicality is not my strong suit.)

EDIT: I did find AES-128. Do there exist two different keys for a pair (text, encrypted text)?, but I think that answer contains a flaw, which is that it assumes that the permutations are random, and that the way they are generated isn't influencing the selection of permutations, for instance, making them less likely (or more likely!) to overlap. I'm questioning that underlying assumption.

Specifically, it's this bit here:

What if instead of uniform random πi we had πi=AESki for uniform random strings ki? If you could predict how that would affect the distribution nonnegligibly, you could distinguish AES from a uniform random permutation, violating the pseudorandom permutation family property that it is conjectured to exhibit, and there would be lots of cryptographers who would like to have a word with you.

(sorry for cut and paste formatting)

This isn't right, though. Think about block-cipher mode with a fixed key, and cycling through the (1<<128) possible plaintexts. You can't distinguish the output from a series of 128-bit random values in any way... But with an actual series of 128-bit random values, you'd virtually certainly get at least one duplicate by the time you did all the inputs, and with AES-128, you won't. But that's the only observable distinction, so far as I know. There's no ranges that are more or less likely, there's no connection from one to the next, and yet, you will somehow just magically never hit a duplicate value.

So we already know that AES-128 has, in one context, the weird property that a series of values it generates is indistinguishable from a random series of 128-bit values, with the sole exception of "but you never get a duplicate until you've hit everything". I'm wondering if it might have that property in a different direction also.

Improve this question
$\endgroup$
8
  • $\begingroup$ In that post, I separately considered permutations specifically (where outputs do not repeat) and functions in general (where outputs may repeat). The fragment you quoted is specifically about permutations. After that paragraph, I took a detour to analyze the more general case of functions, and then concluded by showing that the bound from the analysis of functions applies to permutations too. $\endgroup$
    – Squeamish Ossifrage
    Sep 3, 2019 at 16:17
  • $\begingroup$ I think we may be talking at cross purposes. Yes, functions in general may repeat. But it would be entirely possible to make a thing which selected arbitrary permutations, except with the trait that the permutations it selected wouldn't overlap in the first 1<<128 cases, and there'd still be no impact on distribution in the senses we can test for. $\endgroup$
    – Seebs
    Sep 3, 2019 at 16:32
  • $\begingroup$ I don't understand what flaw you're pointing out. For any $k$, $\operatorname{AES}_k$ is a permutation of 128-bit strings. Nothing magic about it; it is easy to design things to be permutations. Since it is a permutation, if $x \ne y$, $\operatorname{AES}_k(x) \ne \operatorname{AES}_k(y)$, so you are guaranteed to get $2^{128}$ distinct outputs for $2^{128}$ distinct inputs. $\endgroup$
    – Squeamish Ossifrage
    Sep 3, 2019 at 17:00
  • $\begingroup$ I modeled $\operatorname{AES}_k$ as an independent uniform random permutation for every distinct $k$, which is not a very good model (e.g., see the related key attacks on AES) but serves as a heuristic to study this question and I don't know anything about AES in particular that makes it a bad model for this question. (The real AES security conjecture—which remains essentially unbroken—is pseudorandom permutation security, meaning that if $k$ is uniformly distributed then it is hard to distinguish $\operatorname{AES}_k$ from a uniform random permutation. Not applicable here, though.) $\endgroup$
    – Squeamish Ossifrage
    Sep 3, 2019 at 17:02
  • $\begingroup$ Yeah. I'm basically wondering whether it might be a bad model for the question. AES for a given key looks like random noise, except that it turns out not to be. AES for variable keys with a given plaintext looks like random noise, and I wonder whether it ends up having the same trait -- for 128-bit keys, that AES(k1)(x) != AES(k2)(x) for all k1 != k2. I can't see any reason it has to, but the way in which it generates its permutations might have interesting side-effects. So I'm curious. $\endgroup$
    – Seebs
    Sep 3, 2019 at 17:39

1 Answer 1

Reset to default
4
$\begingroup$

So we already know that AES-128 has, in one context, the weird property that a series of values it generates is indistinguishable from a random series of 128-bit values, with the sole exception of "but you never get a duplicate until you've hit everything". I'm wondering if it might have that property in a different direction also.

Highly unlikely. The weird property you point out was actually a design goal of AES (actually, of any block cipher), and is fairly easily seen if you open up the hood of AES and look inside - it's the concatenation of a number of fairly trivial permutations, and concatenating permutations together always gives you a permutation.

In contrast, it was never a design goal that two different 128 bit AES keys never map the same plaintext block to the same ciphertext block; as you point out:

But with an actual series of 128-bit random values, you'd virtually certainly get at least one duplicate by the time you did all the inputs

So, unless AES-128 has some special properties that no one (even the designers) expect, there is almost certainly two keys that map one particular plaintext block to the same ciphertext block.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks! So it's not a design goal, but it's not specifically known-or-unknown to be the case. Well, back to checking Best Buy occasionally to see when they start selling machines with 2^140 bits of storage. $\endgroup$
    – Seebs
    Sep 3, 2019 at 18:07
  • $\begingroup$ @Seebs: actually, most likely you could verify that there exists two different keys that encrypt "0" to the same value (e.g. by using Pollard Rho) with "only" circa $2^{66}$ or so AES evaluations (and a relatively small amount of memory...) $\endgroup$
    – poncho
    Sep 3, 2019 at 18:33
  • $\begingroup$ yeah, but that's still probably a bit beyond my resources at the moment. but yes, i suppose that's a point -- if you do even a significant portion of the space, for a single plaintext, and don't get a duplicate, it's suspicious, and if you do, you're done. $\endgroup$
    – Seebs
    Sep 3, 2019 at 18:48
  • $\begingroup$ @poncho, what sort of computational setup is needed (for a non state actor) to perform $2^{66}$ evaluations? $\endgroup$
    – kodlu
    Sep 3, 2019 at 21:48
  • 1
    $\begingroup$ @kodlu A van Oorschot–Wiener parallel collision search machine to find a collision in $k \mapsto \operatorname{AES}_k(0)$. $\endgroup$
    – Squeamish Ossifrage
    Sep 5, 2019 at 3:09

Your Answer

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

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