9
$\begingroup$

Why do we always assume in cryptographic schemes that the key and plaintext are independent? What if the plaintext depends on the key? How can this endanger security? Is this assumption essential for both symmetric and asymmetric algorithms?

$\endgroup$
2
  • 3
    $\begingroup$ You seem to be hinting at some relationship. Do you have a specific example for us to consider? $\endgroup$
    – Paul Uszak
    Commented Jul 20, 2017 at 20:33
  • $\begingroup$ @PaulUszak : I was thinking about the situation when you are generating the plaintext by the usage of the key when I asked the question. ponch's was a nice guide for a better view as well. I found an example here under the topic he introduced: In some popular disk encryption utilities, the disk encryption key can end up being stored in the page file, and thus is encrypted along with the disk content. $\endgroup$
    – ssss
    Commented Jul 21, 2017 at 12:11

5 Answers 5

12
$\begingroup$

What if the plaintext depends on the key? How it can endanger security?

Well, one trivial example where it can is if you are using RSA (without padding), and encrypt one of the prime factors. Someone seeing the ciphertext could immediately factor the modulus (by computing the GCD of the modulus and the ciphertext), thus endangering security.

There is a formal name for systems where this provably can't happen; circular security. See this paper for a public key cryptosystem that can securely encrypt any polynomial function of the private key (up to a degree bound).

My personal opinion: If you really need to do this sort of thing, I think a hybrid scheme such as the Integrated Encryption System would suit your requirement quite nicely.

$\endgroup$
2
  • $\begingroup$ Thank you for your quick answer, clear counterexample, and mentioning the title of the topic _circular security_along with the paper you introduced. All of them were useful. $\endgroup$
    – ssss
    Commented Jul 21, 2017 at 10:51
  • $\begingroup$ Another similar line of work is "key-dependent message" security. See this paper from Krawczyk and Halevi: eprint.iacr.org/2007/315.pdf $\endgroup$
    – pg1989
    Commented Jul 31, 2017 at 20:43
2
$\begingroup$

Fix a 256-bit key $k$. What ciphertext you get if you try to encrypt the plaintext $\mathrm{AES}256_k(0)$ with AES-256 in CTR mode with a zero nonce? When you have found the answer, what is your gut feeling about whether that looks like encryption or not?

More formally: If an adversary knows you are using AES-256 in CTR mode but not the key—as you should assume they do, by Kerckhoffs' principle—will they be able to distinguish your ciphertext from a uniform random string of 128 bits, as the security contract of AES-256 in CTR mode guarantees under correct use that they cannot?

$\endgroup$
2
  • $\begingroup$ As to your example: $AES256_k(AES256_k(0))$ looks fine to me ($k = b6cb23d499f01558f5910e8034d782c9fa53c4a33547524e9a0531d97c81d0dc_{16}$`, output = $f7a76f22fe016f779f2f19d217b8d535_{16}$) $\endgroup$
    – marstato
    Commented Jul 21, 2017 at 9:31
  • 1
    $\begingroup$ That's not CTR mode. Phrased as a ‘mode of operation’, that's a single block of ECB mode—*i.e.,* just applying the AES-256 permutation to a block. The plaintext/ciphertext equation of ECB mode for a 128-bit message is $C = \mathrm{AES256}_k(P)$. What's the plaintext/ciphertext equation for CTR mode of AES-256 under a zero nonce for a 128-bit message? $\endgroup$ Commented Jul 21, 2017 at 12:54
1
$\begingroup$

my 5c

Why do we always assume in cryptographic schemes that the key and plaintext are independent?

The whole point of cryptography is to hide your messages. If you use a type of encryption that gives you a hint about what the plaintext is, there is a vector for an attack or brute forcing. Let's say in this case you use a size n key against your message of size n. See if you can guess the following messages:

yes

noyoushouldwaituntilthefollowingdaytosetoffthepackagefredwillbetherebecareful

So given the size of the key and the message being related (admittedly a simple case), information from one can be used in an attack on the other. You'll see many cryptography schemes use messages padded/offset/use static key length for this purpose.

What if the plaintext depends on the key

Perhaps something to think about here is the encryption scheme itself and how it generates keys. The enigma machine used in WWII generated encrypted text based upon the initial settings of the key-generator. Using this knowledge the British code-breakers broke enigma messages by having an idea of the plaintext based on the time of day, location, message patterns, predictability of human operators and message conventions. Given this guess (or variations thereof) and brute force gave up the key for the day. Whilst the relationship between the two doesn't clearly exist, but given they know how the encryption scheme worked they were able to brute force the text against all the key permutations and see if the output was proper text. (All messages on that service used the same key that day, which is a big help to codebreakers. If they all used different keys...)

$\endgroup$
2
  • $\begingroup$ in your example noyoushouldwaituntilthefollowingdaytosetoffthepackagefredwillbetherebecareful, how could you use this information for an attack?! $\endgroup$
    – ssss
    Commented Jul 21, 2017 at 10:57
  • $\begingroup$ I need to be more specific - the shorter message is more obvious than a long one, but that's the plaintext being short to begin with, nothing to do with the key $\endgroup$
    – David M
    Commented Jul 22, 2017 at 23:43
1
$\begingroup$

Let's first take a look at ciphers and confidentiality.

A cipher is normally used to obtain confidentiality. Now if you already know at decryption time the content of your message then there is no need to encrypt it anymore: you already know (that part of) the contents of the message.

One of the main requirements for a cipher is that it remains secure even in the worst of circumstances. For that there are different attack factors, and one is a chosen plaintext attack. In this scenario the adversary chooses the plaintext message and the ciphertext should remains indistinguishable from random (in the given domain, i.e. it may of course leak the message length). Obviously this IND_CPA security cannot be achieved when the secret key is partially known to the attacker.

In the end though it's not so much that the plaintext depends on the key, it's that the key depends on the plaintext that's the main issue. The plaintext doesn't need to be secret forever, but knowing parts of the key breaks security for all the other messages. Including a secure one-way hash over the key in the plaintext is unlikely to break security.

For asymmetric primitives: it's not such a huge problem if the public key - used for encryption - is derived in any way from the plaintext message. However, that key is usually generated as a pair with the private key; if the private key is somehow related to the plaintext then you've got the same issues as with dependent symmetric keys.


For signature schemes the plaintext / message is assumed known, so having the key depend in any way on the plaintext is quite obviously not a good idea.


With regards to security proofs: it is often not possible to create a security proof of a cryptographic primitive if there are dependencies between parts of the input.

$\endgroup$
2
  • $\begingroup$ My question exactly aroused from the point that "it is often not possible to create a security proof...". Actually, to me, it just means that whenever we have this assumption we easily proof the security, but it doesn't mean that the scheme is not secure when we don't have it. $\endgroup$
    – ssss
    Commented Jul 21, 2017 at 10:05
  • $\begingroup$ Generally I see this kind of questions when people are just starting with crypto. It's basically a question of key management: were to get the key from. After that has become clear to the asker the idea of having a key depend on the plaintext disappears. Sure, you can possibly make a scheme secure (e.g. using a secure hash, or using the scheme defined by Poncho) and prove it secure. It's just that in general it unnecessarily complicates the protocol or algorithm design. $\endgroup$
    – Maarten Bodewes
    Commented Jul 21, 2017 at 11:56
0
$\begingroup$

One very general answer is that when we analyze the security of an encryption scheme, we often assume that the adversary may actually know quite a lot about what the plaintext is likely to be. Put more formally, we model the adversary's hypotheses as a probability distribution over the plaintexts, one which may well be accurate. See for example, this definition of perfect secrecy from this set of lecture notes by Prof. Jonathan Katz:

Definition 1: An encryption scheme over message space $M$ is perfectly secure if, for all distributions over $M$, for all $m \in M$, and for all ciphertexts $c$ we have $\mathrm{Pr}[m|c] = \mathrm{Pr}[m]$. In other words, the a posteriori probability that a message $m$ was sent, given that we observe ciphertext $c$, is exactly equal to the a priori probability that message $m$ was sent.

This definition works even in cases where the adversary has a really excellent a priori hypotheses of what the message $m$ might be. What that the definition implies is that knowledge of the ciphertext (by itself) must never help the adversary improve their hypotheses. For example, the adversary might independently learn that, with 99% probability, the plaintext is "We attack at dawn"; the cipher's job is to prevent the adversary from using the ciphertext $c$ to further confirm or disconfirm it.

But if the plaintexts and keys are correlated, then an adversary who can independently formulate good hypotheses about the plaintexts might be able to infer accurate probability distributions for the keys. And with such distributions at hand, they might in turn manage to build an a posteriori model of $\mathrm{Pr}[m|c]$ that improves on their a priori model for $\mathrm{Pr}[m]$. Why? Very roughly, because if for an unusually likely plaintext $m$ the key $k$ is also unusually likely, then the ciphertext $c = E_k(m)$ is unusually likely as well, so seeing $c$ allows the adversary to boost their subjective probability that the plaintext is $m$.

The independence of the key from the plaintext helps to straightforwardly forestall any such attacks.

$\endgroup$

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.