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

[Ed Gerck]

"Arnold G. Reinhold" wrote:

> At 2:18 PM -0800 2/19/03, Ed Gerck wrote:
> >The previous considerations hinted at but did not consider that a
> >plaintext/ciphertext pair is not only a random bit pair.
> >
> >Also, if you consider plaintext to be random bits you're considering a very
> >special -- and least used -- subset of what plaintext can be. And, it's a
> >much easier problem to securely encrypt random bits.
> >
> >The most interesting solution space for the problem, I submit, is in the
> >encryption of human-readable text such as English, for which the previous
> >considerations I read in this list do not apply, and provide a false sense of
> >strength. For this case, the proposition applies -- when qualified for  the
> >unicity.
> >
>
> Maybe I'm missing something here, but the unicity rule as I
> understand it is a probabilistic result.  The likelihood of two keys
> producing different natural language plaintexts from the same cipher
> text falls exponentially as the message length exceeds the unicity
> distance, but it never goes to zero.

Arnold,

This may sound intuitive but is not correct. 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 -- even though that may require some
large (actually, unspecified) amount of work. Thus, the likelihood of
of two keys producing valid decipherments (as plaintexts that can be
enciphered to the same ciphertext, natural language or not), from the
same ciphertext is ZERO after the message length exceeds the unicity
distance -- otherwise the message could not be uniquely deciphered
after the unicity condition is reached, breaking Shannon's result.

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.

> So unicity can't be used to
> answer the original question* definitively.

As above, it can. And the answer formulated in terms of the unicity
is valid for any plaintext/ciphertext pair, even for random bits. It
answers the question in all generality.

> I'd also point out that modern ciphers are expected to be secure
> against know plaintext attacks, which is generally a harsher
> condition than knowing the plaintext is in natural language.

No cipher is theoretically secure above the unicity distance, even though
it may be practically secure.

> * Here is the original question. It seems clear to me that he is
> asking about all possible plaintext bit patterns:
>
> At 2:06 PM +0100 2/17/03, Ralf-Philipp Weinmann wrote:
> >I was wondering whether the following is true:
> >
> >"For each AES-128 plaintext/ciphertext (c,p) pair there
> >  exists exactly one key k such that c=AES-128-Encrypt(p, k)."

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)."

Cheers,
Ed Gerck


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