The statement was for a plaintext/ciphertext pair, not for a random-bit/ random-bit pair. Thus, if we model it terms of a bijection on random-bit pairs, we confuse the different statistics for plaintext, ciphertext, keys and we include non-AES bijections. Hence, I believe that what we got so far is a good result... but for a different problem.
In this case, it seems to me that we need to take into account the maximum possible entropy for the plaintext as well as the entropy of the actual plaintext, and the entropy of the keys. With these considerations, with the usual assumption that AES is a random cipher, we can say indeed [*]: "For each AES-128 plaintext/ciphertext (c,p) pair with length equal to or larger than the unicity distance, there exists exactly one key k such that c=AES-128-Encrypt(p, k)." Cheers, Ed Gerck [*] If AES is a random cipher and if the unicity distance "n" calculated by the usual expression n = H(K)/[|M| - H(M)] for a random cipher, where the quantities are: H(K) = entropy of keys effectively used in encryption |M| = maximum possible entropy for the plaintext H(M) = entropy of actual message, the given plaintext is equal to or smaller than the given ciphertext's length, then there is only possible decipherment of the given ciphertext -- ie, there is only one key k such that p=AES-128-Decrypt(c, k) and c=AES-128-Encrypt(p, k). "Arnold G. Reinhold" wrote: > 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 [EMAIL PROTECTED] --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]