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.
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 [EMAIL PROTECTED]
