13
$\begingroup$

I read somewhere that if a cipher has a known-plaintext attack, then it is considered completely broken.

Say there is a cipher that someone uses where the algorithm is understood and a known-plaintext attack is trivial to perform, however a ciphertext only attack is as impractical as brute force. The XOR-Cipher with the key length equal to message length, for example.

If the user changes the key for every message sent, then what use is a known-plaintext attack?

It's always been my understanding that if one finds the key to a message they already know but to nothing else, then that is just as useless as not being able to perform a known-plaintext attack at all.

So what use is a known-plaintext attack in a world where a key is never used more than once (effectively a one-pad pad)? How is that "a complete break"?

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ If you use a one-time pad, then all the notions of modern cryptography are irrelevant. $\endgroup$ – fkraiem Jul 18 '16 at 15:25
  • $\begingroup$ @fkraiem - Okay, say it wasn't entirely a one time pad, but the key was never used more than once per message (in short the key is smaller than the message). Would it have a use then? $\endgroup$ – Danegraphics Jul 18 '16 at 15:28
  • 2
    $\begingroup$ Then your security depends mostly on your key management (and your key derivation). Basically you just shifted the problem, but solved nothing. That is the most crucial point for OTP: You have perfect secrecy under certain conditions. And fulfilling those requirements for the keys is just as difficult as for the original setting - in most scenarios at least, but there are exceptions. $\endgroup$ – tylo Jul 18 '16 at 16:30
  • $\begingroup$ @Danegraphics: if the key has to change for every plaintext, then the method considered does not match the modern definition of a cipher, which is implies allowing key reuse. Notice that the One Time Pad (or equivalently, the XOR-Cipher with the key length equal to message length and no key reuse allowed) is not considered a cipher. $\endgroup$ – fgrieu♦ Jul 18 '16 at 16:40
  • 1
    $\begingroup$ "but the key was never used more than once" - Err... if I have only one known plaintext then I already know all plaintexts encrypted with that key... :o) $\endgroup$ – JimmyB Jul 19 '16 at 16:09
23
$\begingroup$

if a cipher has a known-plaintext attack, then it is considered completely broken.

Yes, pretty much...

[Paraphrased] But can't we come up with a case where this isn't true, such as a One Time Pad?

Yes, we can come up with cases like that; however the requirements of such a case (key as long as the plaintext, no key reuse) make such a cipher impractical.

Instead, when we talk about such a cipher:

  • We generally use the same key to encrypt multiple messages (for example, consider TLS, where the the symmetric key is used to encrypt all records going in the same direction)

  • And, even when we use a key to encrypt only one message, the attacker might be able to guess parts of it; if he can use those guessed parts as known plaintexts, and recover the parts he didn't know (or even to verify if his guess is accurate), well, the cipher didn't do its job.

"Known plaintexts implies total break" is an excellent rule-of-thumb, even if you can come up with cases where it is not true.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Huh. It had always been my assumption that using a key more than once was terrible practice anywhere. It has also been my assumption that a good cipher diffuses/confuses enough that even if part of the message is guessed the rest cannot be. So I guess my question now is: Why would anyone ever use a key more than once? $\endgroup$ – Danegraphics Jul 18 '16 at 15:37
  • 5
    $\begingroup$ @Danegraphics: how do you think TLS works? Do you think they renegotiate a fresh key for every encrypted record? Or, for an example at a different level, consider a block cipher (in any standard mode); the block cipher will be applied with the same key with a number of different plaintext blocks. $\endgroup$ – poncho Jul 18 '16 at 15:39
  • 2
    $\begingroup$ I did, but apparently not. Is it because negotiating a key uses a lot of resources each time? $\endgroup$ – Danegraphics Jul 18 '16 at 15:42
  • $\begingroup$ As for block ciphers, I had assumed that the key undergoes some sort of transformation based on the previous block before encrypting the next. But now I see how that would be completely useless in a known-plaintext attack (mikeazo gave a good example with the html docs). Thanks for the help! $\endgroup$ – Danegraphics Jul 18 '16 at 15:45
  • 1
    $\begingroup$ Yes, negotiating a key each time is too slow. Protecting messages given a shared key involves symmetric cryptography (such as AES), and these ciphers are very efficient. However, exchanging a key, which is necessary to use tools from symmetric crypto, requires asymmetric crypto (like, e.g., RSA or ElGamal). All asymmetric primitives known are considerably slower than, e.g., AES. This is because they involve complex modular operations (such as exponentiations) or produce huge ciphertexts, while AES produces short ciphertexts and involves very simple operations (permutations, xors, etc). $\endgroup$ – Geoffroy Couteau Jul 18 '16 at 17:36
16
$\begingroup$

If the user changes the key for every message sent, then what use is a known-plaintext attack?

Stop right there. This is not what we are trying to prove when conducting a known-plaintext attack. A known-plaintext attack is one where we are given a bunch of ciphertexts, all stemming from encryption using a fixed key. We are then given one plaintext/ciphertext pair, that was formed using the same fixed key. The question we want to answer is wether or not having this known plaintext/ciphertext pair gives the attacker some sort of advantage in breaking the other ciphertexts.

Now, how could this help in a real world attack. Well, often there will be some known plaintext/ciphertext pairs in a long message. If, for example, we are encrypting an HTML document, there is a lot of header information that will likely be consistent. So, say the program encrypts with ECB mode. If I have a pretty good guess what the first block of plaintext is, and I can perform a known-plaintext attack, I can recover the key and get the remaining blocks. That key won't help me decrypt other blocks, but I can break them using the same method since all of the HTML documents are likely to have some known (or easily guessable) beginning.

And don't believe that this is only because my example used ECB. In other modes, similar attacks can be constructed.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The known plaintext attack is a bit different from what you describe. In the known plaintext setting we are provided an arbitrary amount of plaintext/cyphertext pairs. The question is whether we can use these to have a more than 50% chance to pass the following test: if we choose two truly different plaintexts but only receive one of them as cyphertext, can we decide which of the two plaintexts it was? It sounds like we (the attacker) get to choose a lot here - but it is actually not that difficult to devise scenarios where this is what is actually happening. $\endgroup$ – example Jul 18 '16 at 19:55
  • $\begingroup$ @example, how is the game you describe different from a chosen-plaintext attack? $\endgroup$ – mikeazo Jul 18 '16 at 20:18
  • $\begingroup$ In a chosen plaintext scenario we are able to get an arbitrary amount of plaintext/cyphertext pairs for plaintexts that we have chosen. In the known plaintext scenario we are only given both without a means to choose them beforehand. $\endgroup$ – example Jul 19 '16 at 16:48
4
$\begingroup$

Another, more indirect take on this: because of the semantic security requirement, we evaluate ciphers by their ability to resist an adaptive chosen-plaintext attack—where the attack not only sees some plaintext/ciphertext pairs, but also:

  1. Gets to choose which plaintexts they wish to see ciphertexts for;
  2. Gets to use the knowledge they gain from earlier choices to make later ones.

And not only that, we don't require that the attacker be able to actually decipher messages before we declare them victorious. They win if they meet the much lower bar of distinguishability.

Compared to this, the ability to decipher messages from non-chosen known plaintexts is a scenario where an attacker has fewer advantages and yet accomplishes more. So totally broken, yes.

Of course, that shifts your question around. Why do we consider ciphers to be broken if there's a distinguishing attack with adaptive chosen-plaintexts? Several reasons:

  • Semantic security: We don't just want that the attacker be unable to recover the plaintext. We want the attacker not to be able to learn anything about the plaintext. That's why cryptography aims for the high bar of indistinguishability—it's the one thing that guarantees semantic security.
  • Interactive protocols: Cryptography today is used by programs that communicate through interactive client/server protocols, where attackers are often able to cause servers to encrypt plaintexts of their choice. So safety from adaptive chosen-plaintext attacks is a suitable high bar to guarantees that this doesn't give attackers any advantages.
  • Other applications: Ciphers aren't just used for encryption. They're also routinely used for random number generation, for example by running a block cipher in CTR mode. In this case the plaintext is a sequence of blocks with public nonce and counter values, so the attacker knows all of the plaintexts!
  • Conservativeness: Setting a very high bar for the defender and a very low one for the attacker is just safer. Remember that the attacker always has the advantage:
    • The cipher's designer has to defend against attacks that nobody has though of yet;
    • The attacker is free to come up with new attacks years after the cipher design was done.

And note additionally that even though it is good and common practice to rekey often, modern cryptography almost always involve some amount of key reuse—either literally (using the same key to encrypt more than one message), indirectly (using a block cipher mode of operation to encrypt a message longer than the key), or in the very loose sense of just using a key shorter than the message.

But the other thing to say is that many of the motivations for rekeying are driven not by the fear not that cipher will be broken, but rather by key management concerns—the fear that some of keys will be disclosed. Rekeying frequently limits the damage in such scenarios.

Improve this answer
$\endgroup$
1
$\begingroup$

Here's an analogue of your question:

What is the use of cars which can seat six people when there are only four people in my family?

If a key is not used more than once, then you do not need security against chosen plaintext attacks. But other (most) people do need it.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Actually, known plaintext attacks can matter even if you don't have key reuse (which does come up sometimes, for example, if the symmetric cipher you're being used as part of a hybrid public key encryption system); see my answer. $\endgroup$ – poncho Jul 18 '16 at 15:33
  • $\begingroup$ @poncho Come to think of it, I don't think I have ever encountered a (formal) definition of security against known plaintext attacks, but it seems to me that a reasonable one should forbid having the challenge ciphertext equal to that in one of the known plaintext-ciphertext pairs. Also I'm not sure how to formalise 'partially-known plaintexts'. $\endgroup$ – fkraiem Jul 18 '16 at 15:51
  • $\begingroup$ Actually, I was thinking more of cases such as plaintexts of the form :"My password is XXXXXX"; if the attacker guesses that the first 15 characters are "My password is ", perhaps he can use that as a known plaintext to recover the key; once he has that, he can then use the key to recover the password. $\endgroup$ – poncho Jul 18 '16 at 16:27
  • $\begingroup$ @poncho Depends on the length of your key - if your key or algorithm is such that 15 characters of known plaintext can bust open the whole message, I think it'd be known to be insecure well before we get to the question of "Is there a known plaintext attack". $\endgroup$ – Tin Wizard Jul 18 '16 at 20:16

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.