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

[Arnold G. Reinhold]

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 
>a pseudo-random *function* instead.
>

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