2
$\begingroup$

As you add length to an encryption key, at some point the message becomes impossible to brute-force decrypt. This is because at that point, if you go through all the possible keys, you'll get many meaningful decryptions just by random chance and you won't be able to determine which was the original message.

As you add length to the message though, these meaningful decryptions become rarer until there is once again a small enough number of them left to figure out which is the right one (if you know what you're looking for, that is).

Has anybody figured out a way to estimate the required key length for this obfuscation by quantity to happen for more popular encryption algorithms?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What does "meaningful" mean? Suppose I encrypt twice; while this does not add security (and may even decrease it!), you certainly won't recognize the real message by looking at the result of decrypting once. $\endgroup$ – Raphael♦ Jul 2 '15 at 12:29
4
$\begingroup$

That's not how security works. Sometimes you want to use encryption in circumstances in which there are two possible messages, and you want encryption to be secure even in these cases. That's because encryption is used as a building block in more complicated cryptographic protocols. Also, attacks could be based on multiple related (or even unrelated) messages.

Instead, security is based on the fact that nobody can try and decrypt a message with respect to all possible keys since there are too many, and there is no better way of finding the key. The second requirement is security of the cryptosystem, and currently there is no way to prove it. Instead, we use standard systems which are being researched and so far have revealed no weaknesses.

Suppose that our system is cryptographically secure. How can we guarantee that there are too many keys to try all of them? The standard approach is to agree on a key length in advance, usually 128 bits (or more). Classical (rather than quantum!) computation cannot run $2^{128}$ steps even if you parallelize it across atoms of the universe, and wait a million years. That's considered secure enough.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

I very much doubt that anyone has done such an analysis. Trying every key isn't a plausible attack so it isn't worth defending against or studying its effectiveness.

Even if you can try a billion keys a second (i.e., roughly one key per clock cycle on a commodity PC), a $64$-bit key is too long to brute-force decrypt: trying all $2^{64}\approx 2\times 10^{19}$ keys would take nearly $600$ years. Every extra bit makes it take twice as long to try all the keys. In reality, keys are much longer than $64$ bits and are often hundreds or thousands of bits long. It would take many, many orders of magnitude longer than the current age of the universe to try every key.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 128 bit keys are pretty standard. $\endgroup$ – Yuval Filmus Jul 2 '15 at 13:59
  • 1
    $\begingroup$ As to the length of the keys representations, you have to distinguish symmetric (private key, 128 bits) vs. asymmetric (public key, 2048 bits) encryption. $\endgroup$ – JimmyB Jul 2 '15 at 14:58
0
$\begingroup$

Not quite sure I fully understand your question, but let me share some thoughts:

  • Provably safe encryption requires a key of the same length k (in bits) as the message (n), with 2^n possible keys and decryptions of the same ciphertext.
  • If you take a key of length k=n-1 instead, you'll have half as many keys and possible decryptions, and have 1 extra bit of the message to check for plausibility. Best case, you can discard half of the possible decryptions as implausible.
  • If you take a key of length k=n-2 instead, ... and so on.
  • If you take a key of length k=1, you've got two possible decryptions, one of which is correct while the other is more or less recognizably incorrect.

The expectancy value for getting more than one plausible messages for a given key length then roughly depends on two factors:

a. n-k, and

b. the total number of plausible messages of length n.

Notice that, to detect if a decrypted message is plausible or not, there has to be redundancy in the plain text in the first place. If there were no redundancy in the plain text, it would be indistinguishable from pure random content. This redundancy may exist inside the message, like it is given in any natural language text for example, or it may exist outside of the message itself which is the case in the more general known plaintext attacks.

However, measuring the number of plausible messages may prove to be difficult, and definitely depends on the kind of message. The (typical) plaintext's entropy might give a rough estimate. This is a factor that's independent of the encryption algorithm or key.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.