Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
Hmm. another simpler theory to remove Shannon from the discussion. assume that the original assertion is correct - that for each plaintext p and each cyphertext c there exists only one key k that is valid to map encrypt(p,k)=c. In this case, for each possible cyphertext c, *every* possible plaintext p is a valid translation given a unique key k. for that reason, the uniary distance for encrypt() must be larger than one block - as it is self evidently not possible to map *any* c to a unique p without knowledge of the key. For that reason, Shannon cannot be applied to a single block of encrypt(), and can be safely ignored :) - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
At 2:18 PM -0800 2/19/03, Ed Gerck wrote:
Anton Stiglic wrote:
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.
While your reformulation of the problem is interesting, the initial question
was regarding plaintext/ciphertext pairs, which usually just refers to the
pair
of elements from {0,1}^n, {0,1}^n, where n is the block cipher length.
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. So unicity can't be used to
answer the original question* definitively.
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.
Furthermore they are usually subject to chosen plaintext attack which
is always harsher.
Arnold Reinhold
* 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).
Of course we can look at the generalized case of Rijndael
with block size == key size and ask the same question. I'd
be happy with an answer for AES-128 nonetheless.
At first I thought this was a trivial question since the round
function minus AddRoundKey is bijective. But I haven't been
able to come up with anything thus far, so I thought I'd
ask the list.
Any ideas?
Cheers,
Ralf
p.s.: I am familiar with Wernsdorf's paper, but it hasn't
helped me thus far.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
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 [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
Anton Stiglic wrote:
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.
While your reformulation of the problem is interesting, the initial question
was regarding plaintext/ciphertext pairs, which usually just refers to the
pair
of elements from {0,1}^n, {0,1}^n, where n is the block cipher length.
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.
Cheers,
Ed Gerck
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
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]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
... 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)? But then you didn't answer your own question. You gave the expected number of collisions, but not the probability that at least one exists. That probability the sum over k from 1 to 2^128 of (-1)^(k+1)/k!, or about as close to 1-1/e as makes no difference. But here's the more interesting question. If S = Z/2^128 and F is the set of all bijections S-S, what is the probability that a set G of 2^128 randomly chosen members of F contains no two functions f1, f2 such that there exists x in S such that f1(x) = f2(x)? G is a relatively miniscule subset of F but I'm thinking that the fact that |G| = |S| makes the probability very, very small. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
At 5:45 PM -0600 2/18/03, Matt Crawford wrote: ... 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)? But then you didn't answer your own question. You gave the expected number of collisions, but not the probability that at least one exists. That probability the sum over k from 1 to 2^128 of (-1)^(k+1)/k!, or about as close to 1-1/e as makes no difference. But here's the more interesting question. If S = Z/2^128 and F is the set of all bijections S-S, what is the probability that a set G of 2^128 randomly chosen members of F contains no two functions f1, f2 such that there exists x in S such that f1(x) = f2(x)? In general, if G has n randomly chosen members of F, isn't the answer just 1/e**(n**2)? There are n**2 pairs of functions in G (ok n*(n-1)) and the probability of no collision for each pair is 1/e as you point out above. G is a relatively miniscule subset of F Just plain minuscule: |G| = 2**128, |F| = (2**128)! ~= 2**(2**135) but I'm thinking that the fact that |G| = |S| makes the probability very, very small. Even if |G| |F| that is true. If G contains 5 functions, there are 20 pairs and 1/e**20 ~= 2.06E-9. Arnold Reinhold - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
Matt Crawford wrote: But here's the more interesting question. If S = Z/2^128 and F is the set of all bijections S-S, what is the probability that a set G of 2^128 randomly chosen members of F contains no two functions f1, f2 such that there exists x in S such that f1(x) = f2(x)? Vanishingly small, as you guessed. Fix x0 in S. Your probability is at most the probability that G has no two functions f1, f2 with f1(x0) = f2(x0). The latter is the same as the probability that a set of 2^128 randomly chosen 128-bit values contains no repeated elements, which is indeed vanishingly small (it is (2^128)! / (2^128)^(2^128), which is something like 1/e^(2^128)). - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
Ed Gerck [EMAIL PROTECTED] wrote: 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). Excuse my naivete in the math for this, but is it relevant that the unicity distance of ASCII text encrypted with a 128 bit key is about 150 bits [Schneier, p 236] and the AES block size is only 128 bits? If you use plain ECB mode is the plaintext/ciphertext length in the above statement 128 bits, or does the statement imply that you have an arbitrary length (c,p) pair using whatever mode, possibly chaining, makes sense for your purpose? -- sidney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
The relevant aspect is that the plaintext and key statistics are the determining factors as to whether the assertion is correct or not. In your case, for example, with random keys and ASCII text in English, one expects that a 128-bit ciphertext segment would NOT satisfy the requirement for a unique solution -- which is 150 bits of ciphertext. However, since most cipher systems begin with a magic number or has a message format that begins with the usual Received, To:, From:, etc., it may be safer to consider a much lower unicity, for example less than 128 bits. In that case, even one block of AES would satisfy the requirements -- and compression would NOT help. Of course, keeping the same key while encrypting the next block would also satisfy the requirements for the resulting 256-bit ciphertext/plaintext pair to have a unique solution.[*] Cheers, Ed Gerck [*] But note that if the plaintext has the full entropy of ASCII text in English (as in your example) and compression is used, then the unicity should increase to above 300 bits of ciphertext. The result is that a two-block segment of ASCII text in English that is encrypted with the same key would NOT satisfy the requirement for a unique solution. Sidney Markowitz wrote: Ed Gerck [EMAIL PROTECTED] wrote: 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). Excuse my naivete in the math for this, but is it relevant that the unicity distance of ASCII text encrypted with a 128 bit key is about 150 bits [Schneier, p 236] and the AES block size is only 128 bits? If you use plain ECB mode is the plaintext/ciphertext length in the above statement 128 bits, or does the statement imply that you have an arbitrary length (c,p) pair using whatever mode, possibly chaining, makes sense for your purpose? -- sidney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES-128 keys unique for fixed plaintext/ciphertext pair?
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. Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
