5
$\begingroup$

If we have some random data (with length a multiple of block size to avoid padding) and encrypt it with a block cipher with a weak key (maybe it's derived from a four digit number for example), would it be possible to break the encryption? If there is no MAC and we are not using authenticated encryption, assuming the attacker has no knowledge of the key (besides it's weakness) or of the data that was encrypted, could the attacker find out which key and decrypted data is correct?

As far as I understand it, is that for modern block ciphers and unauthenticated block cipher modes, there should be no pattern in the decrypted data. Decrypting with the incorrect key gives a random-looking result, and decrypting with the correct key also gives a random-looking result since we encrypted random-looking data. Is this correct or is there some way to see or deduce which is the correct key?

$\endgroup$
3
  • 2
    $\begingroup$ "Random" and "Random-looking" are completely different things. $\endgroup$ Commented May 30 at 8:11
  • 2
    $\begingroup$ If we generate a random number with a CSPRNG, it is practically true random. When we choose to use that number it start having some meaning for us. It will no longer be just a random number but it will still be indistinguishable from other random data for someone that doesn't have the knowledge of this use. For the use case behind this question, random-looking data like this is random enough. $\endgroup$
    – n-l-i
    Commented May 30 at 8:53
  • 1
    $\begingroup$ And the result of decryption with the incorrect key should also be sufficiently random-looking for this use case. $\endgroup$
    – n-l-i
    Commented May 30 at 9:00

1 Answer 1

6
$\begingroup$

If there is no MAC and we are not using authenticated encryption, assuming the attacker has no knowledge of the key (besides it's weakness) or of the data that was encrypted

What is considered a break? If you have a limited key space then you will be able to decrypt to a specific number of plaintext as well. All the other possible plaintext values are excluded so an attacker would have information about the plaintext.

It is distinguishable from random due to the exclusion of messages. So in that sense the scheme is broken (unless all the message space is covered by the keys, but that would leave a very small message space indeed). What the applicability of that is depends on the use case of course, but semantic security is out of the window.

Imagine that you are encrypting a winning lottery ticket. If there are $s$ keys then there are also $s$ possible plaintext messages, i.e. lottery tickets that may have won. Assuming that there are $n$ fully random lottery tickets and $n \gt s$ then an adversary can go over all possible keys and make sure that they choose a lottery ticket that can actually win.

Is this correct or is there some way to see or deduce which is the correct key?

No, if there is no way to distinguish the correct plaintext from the other possible plaintext then there is no way to find the right key. This is mainly a thing if the key is reused for separate messages of course; avoiding key recovery is ultimately not the goal of encryption; it's the confidentiality of the data.

Presuming that the keyspace remains the same that means you won't be able to find the right plaintext over multiple messages either, but you can for each candidate still create a set of plaintext messages.


Beware that this is a very uncommon scenario, usually there is something that can be distinguished from random, and in that case it's usually pretty easy to find the correct key from a small set. This scenario is possible when wrapping fully random challenges or symmetric keys, but often there is some kind of meta data or Oracle that is able to indicate failure or success that spoils the day.

$\endgroup$
5
  • 2
    $\begingroup$ “usually there is something that can be distinguished from random”, For example, protocol handshake success/failure indications. I think this is worth adding. $\endgroup$
    – DannyNiu
    Commented May 30 at 1:00
  • $\begingroup$ @DannyNiu Yep, added that to the last sentence. $\endgroup$
    – Maarten Bodewes
    Commented May 30 at 1:01
  • 1
    $\begingroup$ I hadn't thought of the limited key space and the implications you covered in response to your first quote. The actual weaknesses I had in mind are more of the biased but unlimited key space type rather than the strictly limited I used as an example. Same point applies but with probabilities instead. $\endgroup$
    – n-l-i
    Commented May 30 at 5:18
  • $\begingroup$ For unlimited key space you'd get a different answer. The bias will translate into a weakness of course, but at least the attacker would not be able to go over all the keys and look at all the possible plaintext messages. Unfortunately the sentence "maybe it's derived from a four digit number for example" does clearly indicate a limited key space, so I went with that. $\endgroup$
    – Maarten Bodewes
    Commented May 30 at 11:32
  • $\begingroup$ I agree that I implied a limited key space and I'm happy you managed to give me a very useful answer despite that :D $\endgroup$
    – n-l-i
    Commented May 30 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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