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

[Andreas Gunnarsson]

On Fri, Feb 21, 2003 at 06:31:20AM -0800, Ed Gerck wrote:
> Shannon proved that if
> "n" (bits, bytes, letters, etc.) is the unicity distance of a ciphersystem,
> then ANY message  that is larger than "n" bits CAN be uniquely deciphered
> from an analysis of its ciphertext
[...]
> Conversely, Shannon also proved that if the intercepted message has less
> than "n" (bits, bytes, letters, etc.) of plaintext then the message CANNOT
> be uniquely deciphered from an analysis of its ciphertext -- even by trying
> all keys and using unbounded resources.

No, the unicity distance is the amount of ciphertext where the expected
number of spurious keys is zero.

>From Shannon's "Communication Theory of Secrecy Systems"
(http://www.cs.ucla.edu/~jkong/research/security/shannon.html)
  It will be seen from Fig. 7 that the equivocation curves approach zero
  rather sharply. Thus we may, with little ambiguity, speak of a point
  at which the solution becomes unique. This number of letters will be
  called the unicity distance. For the random cipher it is approximately
  H(K)/D.

D (the redundancy in bits/letter) depends on how good the attackers
model of the language is, which is difficult to control for whoever does
the encryption. It should be possible to find two messages of the same
size, one of which has no spurious keys while the other one has at least
one. It is thus not possible to give an exact size for a given cipher
system such that no ciphertexts have spurious keys but there exist
spurious keys for all smaller ciphertexts.

> The following is always true, for any possible plaintext bit pattern:
> 
> "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)."

No, if it was true I could take any plantext message and 2^128 + 1
random ciphertexts and find a key for each of the ciphertexts that
encrypts the plaintext into it, unless you mean that the ciphertexts
must be chosen so that there is a key which encrypts p into c. In the
latter case it may be true if the source language is e.g. English, but
not for an arbitraty language. It also does not hold for any arbitrary
cipher; a trivial counter-example would be a cipher where not all key
bits are used.

Anyway, I believe that the original question was whether there is
exactly one key for every possible pair of *blocks* c, p so that
c=AES-128-Encrypt(p, k). I believe this since the original poster wrote:
"Of course we can look at the generalized case of Rijndael
with block size == key size and ask the same question."
For that question I agree with what others have already said.

/Andreas

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