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

[Ed Gerck]

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 majordomo at wasabisystems.com


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