Re: NEWBIE QUESTION: Key space exhaustion - How do I know when I'm there?

According to <TommieTippee@xxxxxxxxx>:
Can someone help? Is it possible to sieve out improbable key values
without having to analyze part or all of the plaintext? I'm assuming
key exhaustion is the only option, and weaknesses in the particular
encryption algorithms, availability of plaintexts etc. cannot be
exploited.

If you can rule out keys faster than by trying each possible key and
looking at the result of a block decryption, then by all means you have
found a big fat weakness in the encryption system. Consequently, if you
assume that the encryption algorithm has no known weakness, then
exhaustive search has an uncompressible cost of one block encryption per
tried key.

Of course key exhaustion makes sense only if you have a way to tell that
you have found the right key. E.g. the resulting plaintext "makes sense"
in a way such that a random bunch of bytes has very low probability of
making sense. For instance, let's assume that you want to decrypt a
message which consists of 100 DES-encrypted blocks, i.e. 800 bytes (in a
realistic situation, the blocks use some kind of chaining such as CBC
but this is not an issue here). Now, suppose that you have gained some
outsider knowledge that the encrypted message is an English text encoded
as ASCII. ASCII has the property that valid character codes are between
0 and 127. Actually, only a few values between 0 and 31 are plausible;
most others are control characters which are unlikely to be found in a
text meant for human consumption. Besides, random sequences of ASCII
characters are unlikely to produce English words, much less meaningful
sentences. But asserting whether a given sequence of characters is
proper English is not an easy task for a computer. Hence we will
concentrate on the simple test of checking whether all bytes have a
value between 0 and 127.

In a correctly decrypted message, all 800 plaintext bytes will have a
value between 0 and 127. On the other hand, a random byte will have a
value between 0 and 127 with a probability of 0.5 only. This means that
a bunch of 800 random bytes has only a 2^-800 probability of consisting
only of values between 0 and 127. This is a really small probability. In
other words, if you decrypt with the wrong key, the risk of obtaining
800 bytes which will somehow "look like" ASCII text (by the simple test
of looking at the upper bits of all those bytes, at least) is very
small. Since there are 2^56 possible DES keys only, you would be very
unlucky if there really existed such a wrong key.

In the example above, you could imagine that each test for a single key
requires the decryption of 100 blocks (and then analysis of the
resulting bytes, but looking at the upper bits is way faster than
performing the decryption). However, you can easily do much faster than
that by testing blocks as they are obtained. I.e., you first decrypt the
first block, and look at the plaintext for that block. If any of those 8
bytes has a value of 128 or more, then you know that the key is not
right, and you do not need to try it on the remaining 99 blocks. Since 8
random bytes have 1/256 probability of consisting of values below 128,
this simple test, requiring the decryption of a single block per key,
will rule out 255/256 of the wrong keys. For the 2^48 keys which pass
the test, simply proceed with the second block: only 2^40 will yield an
ASCII-compatible plaintext for the second block. After 6 blocks, the
number of keys which yield something which looks like ASCII (at least in
the eye of a computer) will be about 256, and at that point you can
really try them by hand and see if one of them yields something in
English. Your average cost per tried key will be about 1.004 block
encryption, which is really close to the theoretical minimum of 1.


All of the above assumes that you "know something" about the plaintext,
enough to rule out "bad candidates". But if you do not know anything on
the plaintext, if that plaintext is, for all you know, a bunch of random
bytes, then why on earth would you want to decrypt it ?

ASCII text is easy to talk about because the "good decryption test" is
simple. Other ways include locating headers for some data formats, or
even recognizing words with the help of a dictionary. It may be somewhat
difficult to really assess the effectiveness of automated tests for
correct decryption. The really easiest way to solve this, from the point
of view of the one trying to protect his data, is to use a good
cryptosystem with a wide enough key space, so as to make exhaustive
search unrealistic. For instance, use AES with a 128-bit key. Even the
theoretical minimum of one block encryption per key makes exhaustive
search totally unfeasible. At that point, you may even assume that the
attacker knows exactly 99 of 100 plaintext blocks (which allows for very
accurate filtering of wrong keys), and he will still be at a complete
loss with regards to the 100th block. With a proper cryptosystem and a
proper key size, all of the above becomes moot.

Note that academic researchers, when they try to break an algorithm,
consider that the attacker has access to an awful lot of plaintext
blocks and their encrypted counterpart. It is not that it really happens
in practice. Rather, they are really cautious when they talk about an
encryption algorithm, and will not deem one secure unless it resists
attackers which such academic-granted powers. When an attacker has
several exactly known plaintext/ciphertext pairs, he is already way
beyond the problem of recognizing English text.


--Thomas Pornin
.

Relevant Pages

  • Transform Lag
    ... using the TransformBlock method in the ICryptoTransform ... The strange behavior is that the decryption ... lags the encryption by 1 block. ... plaintext block P, decrypt 1 block, and the decryption ...
    (microsoft.public.dotnet.security)
  • 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: Encrypted Communications and Predictable Communications?
    ... There are more sophisticated attacks which might use known plaintext ... consider a database system, with a client application on one machine and a database server on another. ... How much does the predictability of such message exchanges ... Should the encryption system take steps to ensure that the encrypted data contains random information to pad out messages to at least the minimum ...
    (SecProg)
  • Re: "Rule 30" CA encryption implementation
    ... > never ever let the plaintext touch the hard disk. ... > plaintext file, encrypt it to a ciphertext file, and delete the ... The encryption program I am considering uses special memory management ...
    (sci.crypt)
  • Re: News: Encrypted GSM Voice Calls & SMS Messages Hacked in Minutes
    ... This follows from the fact that encryption by an additive key is represented by one equation with two unknowns. ... If the length of the key equals the length of the plaintext and is never reused, then it is impossible to decrypt the ciphertext. ... If, on the other hand, the key is reused, then decryption of an XOR encryption is a laughably trivial exercise. ... Very few of these devices are secure against such attack. ...
    (alt.cellular.verizon)