Arnold G. Reinhold
Tue, 18 Feb 2003 13:53:24 -0800
At 1:09 PM +1100 2/18/03, Greg Rose wrote:
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.At 02:06 PM 2/17/2003 +0100, Ralf-Philipp Weinmann wrote: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."For each AES-128 plaintext/ciphertext (c,p) pair there exists exactly one key k such that c=AES-128-Encrypt(p, k)."
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.