Re: Using a Magic Value in Place of Authentication

Antony Clements schrieb:
"Stefan Tillich" <stefanti@xxxxxxxxxxxx> wrote in message news:49cbb7b1$0$12126$3b214f66@xxxxxxxxxxxxxxxxxxxxxxx
Yes. In fact that means that the two permutations E_k1 and E_k2 (i.e., the encryption functions for keys k1 and k2) share a single mapping from a specifc plaintext to a specific ciphertext.

You don't need a whole lot of resources to map a fixed 1 to 1 transformation, if you know that m is plain english, and that the user only uses "A" through "Z" in the key, then as you can see, it's not that hard as the key, in terms of "c = k xor m" will map to one thing and one thing only for each character in m.

When did we restrict the plaintext or key of an encryption method to plain English? I must have missed that. But ok.

I'm not quite sure what you mean by "fixed 1 to 1 transformation". My guess is that you mean the mapping (M, K) -> C, where M, K, and C and the message space, key space and ciphertext space, respectively.

So let's ignore things like efficient encoding key derivation, etc. and assume that elements of M and K can only consist of 26 characters which are encoded as bytes. For AES-128, that would mean we have 16 characters per plaintext block and key, giving 26^16 ~= 2^75 possibilities each. So we have 2^75 plaintext-ciphertext pairs for each of the 2^75 keys and still require 2^128 bits to store each pair. Our total required storage is now 2^278 ~= 10^83. This is only a thousand times the estimated number of atoms in the Universe, so we're getting closer :-)

However, there's still the problem of calculating the complete mapping (which I've neglected previously).


If you'd have such resources to map all key-dependent permutations of the encryption method to look for such "shared" plaintext-to-ciphertext mappings, then you would be able break the encryption anyway. However, modern block ciphers are dimensioned so that you cannot build up such mapping tables even if you could use every atom in the Universe to store a single bit of your tables. E.g., for AES-128, you have 2^128 mappings (one for each key) with 2^128 entries (one for each plaintext) and each entry has 2^128 bits (the resulting ciphertext), so we have 2^384 ~= 10^115; whereas we have an estimated measly 10^80 atoms in the Universe).

It does depend entirely on the method of encryption. Simple methods require much less resources, and the key can be easily retreivable.

I was presuming modern encryption systems which are deemed secure from our current point of view, not things - to put it blunt - like Ceasar cipher. My point is that you're trying to construct an attack on an encryption method when in fact you just know a bit of the plaintext and it's structure. Modern encryption systems however should be resistant against chosen-plaintext attacks which would cover all of your pretext.


Of course you could just test a single ciphertext over all possible keys and indeed determine after 2^128 encryptions (if you're lucky) that it can only be the result of a specific plaintext and key. Then you could sit tight and try to intercept that exact ciphertext (which you'd get after about 2^127 ~= 10^38 ciphertexts). At a million ciphertexts per second you'd intercept it after 10^32 seconds ~= 3 * 10^15 billion years. If the Universe will revert expansion and will someday collapse, it is probably before that time. If it expands infinitely it is likely that there isn't much energy left anymore to sustain life as we know it.

And if you find a way to handle the limitations of the Universe, we could still switch to AES-256 :-)

It's been shown recently that there are structures beyond what we consider the size of the universe to be, in essense, it's bigger than we thought, and by default there is more matter than we thought, so using the phrase "there isn't enough matter in the universe" needs to be rethought. But your point is taken.

It's nice what you can conjure up with just a couple of bits, isn't is :-)

Stefan
.

Relevant Pages

  • Re: Conspiracy in the Surveillance Society
    ... (requiring brute-forcing the ... that the plaintext is independent of the encryption key. ... But the key ain't transfered in the ciphertext. ...
    (rec.arts.sf.science)
  • Re: Using a Magic Value in Place of Authentication
    ... the encryption functions for keys k1 and k2) share a single mapping from a specifc plaintext to a specific ciphertext. ... If the attacker had some chosen plaintext, then that would lead to a partial if not a total mapping of the key. ... Of course you could just test a single ciphertext over all possible keys and indeed determine after 2^128 encryptions that it can only be the result of a specific plaintext and key. ...
    (sci.crypt)
  • Indistinguishability and integrity in symmetric encryption
    ... "The 'right' security property for general-purpose symmetric encryption". ... >symmetric encryption scheme (for which the empty plaintext is not ... A has interfaces to an encryption oracle ... It is assumed that the ciphertext returned by A is different to all those ...
    (sci.crypt)
  • RE: How to verify a decrypted cyphertext
    ... a given ciphertext might decode into several different ... Mathematical encryption might not be the only encoding of the ... Japanese (nothing guarantees that the plaintext will be in English!) ... But in the case of a encrypted random string ...
    (Security-Basics)
  • one way permutation?
    ... function that nevertheless does a one to one mapping ... between plaintext and ciphertext. ... While it is a known fact that programmers ...
    (sci.crypt)