# AES-128 keys unique for fixed plaintext/ciphertext pair?

Arnold G. Reinhold reinhold at world.std.com
Tue Feb 18 16:19:23 EST 2003

```At 1:09 PM +1100 2/18/03, Greg Rose wrote:
>At 02:06 PM 2/17/2003 +0100, Ralf-Philipp Weinmann wrote:
>>"For each AES-128 plaintext/ciphertext (c,p) pair there
>>  exists exactly one key k such that c=AES-128-Encrypt(p, k)."
>
>I'd be very surprised if this were true, and if it was, it might
>have bad implications for related key attacks and the use of AES for
>hashing/MACing.
>
>Basically, block encryption with a given key should form a
>pseudo-random permutation of its inputs, but encryption of a
>constant input with a varying key is usually expected to behave like
>

Here is another way to look at this question. Each 128-bit block
cipher is a 1-1 function from the set S = {0,1,...,(2**128-1)] on to
itself, i.e. a bijection. Suppose we have two such functions f and g
that are randomly selected from the set of all possible bijections
S-->S (not necessarily ones specified by AES). We can ask what is the
probability of a collision between f and g, i.e. that there exists
some value, x, in S such that f(x) = g(x)?  For each possible x in S,
the probability that f(x) = g(x) is 2**-128. But there are 2**128
members of S, so we should expect an average of one collision for
each pair of bijections.

If the ciphers specified by AES behave like randomly selected
bijections, we should expect one collision for each pair of AES keys
or 2**256 collisions.  Just one collision violates Mr. Weinmann's
hypothesis.  So it would be remarkable indeed if there were none.
Still it would be very interesting to exhibit one.

For ciphers with smaller block sizes (perhaps a 32-bit model of
Rijndael), counting collisions and matching them against the expected
distribution might be a useful way to test whether the bijections
specified by the cipher are randomly distributed among all possible
bijections.

Arnold Reinhold

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com

```