I don't understand how we could bruteforce a symmetric cipher.

Let's take AES with a key size of $128$ as an example. It means that there are $2^{128}$ possible keys, and as many ways to decrypt a ciphertext $c$. Given that there are so many different keys, it is theorically possible to decrypt $c$ into multiple plausible messages (e.g. message that read like english). So while we are bruteforcing $c$, if at some point we obtain a plausible message we can't tell for sure that we found the good key because there are plenty of other plausible messages that we haven't found yet.

It's not like with hash functions or asymmetric ciphers, where we have a way to make sure that we found the good antecedent/private key.

So I don't understand what they mean in this article: https://en.wikipedia.org/wiki/Key_size

For example:

For instance, Triple DES was designed to have a $168$ bit key, but an attack of complexity $2^{112}$ is now known (i.e. Triple DES now only has $112$ bits of security, and of the $168$ bits in the key the attack has rendered $56$ 'ineffective' towards security).

Even if Triple DES only had 50 bits of security, we would still be able to decrypt multiple plausible messages that are not the original message, let alone the case where the original message is gibberish and not necessarily natural language. I feel like the notion of "security level" is not the same for hash functions/asymmetric ciphers and symmetric ciphers. For both, it refers to the subset of the antecedent/key space that we know the good antecedent/key is in, but for the latter, we can never be sure that we have found the good secret key, and thus that we bruteforced successfully.

Could you explain it to me please? Thank you for your help.


You are forgetting that messages usually consist of many blocks and that many messages contain much more structure than just English text. For example an RSA private key will, when encoded, have a easy to distinguish header and will consist of many blocks of plaintext / ciphertext when encrypted with a block cipher. The same is true for Word documents, XML messages, images and many other formats.

Otherwise, it is a simple game of chance. At each block that decrypts correctly according to the available information, you get more confident that you've found the right message. However, you can choose a block for which you have the most information and only continue decrypting the next block once you've found a match. That way you can very quickly filter out wrong keys.

For instance, for English text you'll generally know at least one bit: the highest one bit of ASCII text is always zero, so that already makes 8 bits per block that you need to get right. Assume that you've got another 2 bits per byte / character simply by checking if the English text is consistent after that. Then you only need to advance to the next block once in $2^{8 \cdot 3} = 2^{24} = 16,777,216$. During the calculation of cryptographic strength, we can safely ignore that kind of detail. If the message is very small then such analysis will indeed fail, and you cannot tell if the key is correct or not. This is easy to show by looking at single bit encryption, e.g. using stream cipher mode such as CTR.

As indicated in the comments, generally we also assume that messages have integrity protection and provide message authentication, usually through authenticated cipher modes or explicit inclusion of a Message Authentication Code (MAC) / authentication tag. In that case, the correctness of the key can also be verified through that code. For most modes that add at least 64 bits to test (128 bits for most authenticated modes and 256 or more if HMAC is used).

Usually, for attacks, we assume that (part of) the message is known, i.e. known plaintext for a known-plaintext attack at the very minimum. Ciphers are expected to be even more secure than that: allowing the attacker to choose which messages get encrypted while leaking no information about the data (other then information about the message size). In other words, the ciphertext should be INDistinguishable from random under a Chosen Plaintext Attack, i.e. IND-CPA secure.

  • $\begingroup$ But even in the ideal setting you're describing, if the block size is 128 and the key size is 256, if we know 24 bits per block, then the remaining number of plausible keys is $2^{256}/2^{24}=2^{212}$ which is still insanely huge. Is it still really too unlikely to decrypt 2 different well-formed HTTP requests from the same ciphertext? Even if you add optimizations like "the request always starts with 'GET' or 'POST'", the remaining key space is still huge. $\endgroup$ – JacopoStanchi Oct 28 '20 at 12:16
  • $\begingroup$ Besides, I understand that authenticated encryption (HMAC and other) prevents chosen ciphertext/plaintext attacks, but if it comes at the price of letting a way for the attacker to check if the secret key he is testing is the good one, is it really worth it? $\endgroup$ – JacopoStanchi Oct 28 '20 at 12:18
  • $\begingroup$ And without even realizing it, we're doing a ton of of ad-hoc assumptions like "we assume that the attacker has access to a encryption/decryption oracle" or "we assume the attacker knows the value of certain bits in the message", whereas when we are talking about bruteforcing a hash function/asymmetric cryptosystem, we just say "here is a hash/public key, find the corresponding antecedent/private key". $\endgroup$ – JacopoStanchi Oct 28 '20 at 12:35
  • 3
    $\begingroup$ We're always very generous to attackers. That's because in some real cases the attackers do have some knowledge of the plaintext, so we want systems to be secure even then. EG Authentication does mean that the multiple-plaintext issue is gone, but it's such a tiny improvement for the attacker that they still need more than $2^{128}$ effort to break the system, and it's thus secure. $\endgroup$ – SAI Peregrinus Oct 28 '20 at 13:14
  • $\begingroup$ Ok you won the argument. But I just wanted to point out that we are usually far more generous towards attackers bruteforcing a symmetric cipher (oracles, knowledge on the original plaintext) than towards attackers bruteforcing a hash function or an asymmetric cipher (just access to the hash or public key) because symmetric schemes are far more secure. $\endgroup$ – JacopoStanchi Oct 28 '20 at 14:02

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