9
$\begingroup$

As defined by Shannon, a cipher is perfectly secure if ciphertext leaks no information about the plain text.

Under this definition, can ciphertext leak something about the key? Are there any ciphers for which this is true?

| improve this question | |
$\endgroup$
9
$\begingroup$

Sure, it can leak something about the key as long as that doesn't leak anything about the plaintext.

Consider the following cipher, I'll call it 2-OTP. 2-OTP takes as input a message $M$ and two keys $K_1$ and $K_2$. Each key must be truly random, independent of one another, and each the same length as the message $M$. Define encryption as $ENC(M,K_1,K_2)=K_1,M\oplus K_1 \oplus K_2$. Notice that encryption leaks the entire $K_1$.

Clearly this leaks nothing about the message $M$ as with the information given, we can compute $M\oplus K_2$, but that leaks nothing about $M$.

As an example of something a that won't work (i.e., leaking something about the key leaks something about the plaintext), consider OTP' where OTP' is just the one-time-pad but leaks the first bit of the key. Clearly this leaks the first bit of the message, so it is no longer perfectly secure.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This sound's like a cheater's answer as we can simply to a form that doesn't leak any key without losing strength. $\endgroup$ – Joshua Nov 13 '14 at 17:29
  • 4
    $\begingroup$ @Joshua, if you know of a cipher that does leak key bits while still retaining perfect secrecy that can not easily be converted to a form that doesn't leak key information and is still informational theoretically secure, by all means, post it as an answer. $\endgroup$ – mikeazo Nov 13 '14 at 17:38
  • $\begingroup$ @Joshua: It's not a cheater's answer. This type of construction is sometimes called contrived, which is solely meant to demonstrate the point, not to be used in practice. $\endgroup$ – M.S. Dousti Jul 14 '17 at 13:21
10
$\begingroup$

mikeazo's answer clearly covers what the question asks. However, I want to go further and answer this:

How much information does a perfectly secure cipher leak about the key?

Exactly all the excessive information of the key that does not help in finding anything about the message.

In simple words: if the key length is $k$ bits and the message is $m$ bits long then in case of a perfectly secure cipher by knowing the ciphertext you know exactly $(k-m)$ bits of the key.

Formally: By knowing a ciphertext which is ciphered using a perfectly secure cipher the uncertainty about the key is exactly equal to the uncertainty about the message.

Or using entropy function:

$$H(K|C)=H(M)$$

Where $H(K)$ is the entropy of the key, $H(C)$ is the entropy of the ciphertext, and $H(M)$ is the entropy of the message.

The equation above can be deduced from the following equations:

$H(M)=H(M|C)$, $H(M|C,K)=0$

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Are you sure about $H(K|C)=H(M)$? I think it should be corrected as $H(K|C) = H(K) + H(M) − H(C)$, as stated an proven under the name "key equivocation" in here. (The proof assumes the independence of $M$ and $K$, as well as non-probabilistic encryption, in an essential way.) $\endgroup$ – Incredible Apr 29 '16 at 13:15
  • 2
    $\begingroup$ @Incredible: What you said is correct regarding a general deterministic cipher with independence of $M$ and $K$. Habib is talking about a perfectly secure cipher. In section 7.3 of the book Codes and Ciphers, an even more general identity is proven (it assumes neither determinism nor independence of $M$ and $K$): $H(K | C) = H(M | C) + H(K | M, C)$. In case of a perfectly secure cipher, $H(M | C) = H(M)$, and it can be written as $H(K | C) = H(M) + H(K | M, C)$. $\endgroup$ – M.S. Dousti Apr 29 '16 at 17:05
  • 2
    $\begingroup$ Cont'd: The extra term (w.r.t what Habib wrote) vanishes only if $K$ is uniquely determined from $M$ and $C$, which is the case with one-time pad. However, $H(K|M,C) = 0$ does NOT hold for all perfectly secure ciphers. For instance, assume the message & ciphertext spaces are $\{00,11\}$, the key space is $\{00,01,10,11\}$. It's easy to define a perfectly secure cipher over these spaces. Since the key space is larger than either of the message and ciphertext spaces, the key will not be uniquely determined from $M$ and $C$. $\endgroup$ – M.S. Dousti Apr 29 '16 at 17:19
5
$\begingroup$

The one-time pad is perfectly secure. It will also leak the complete key to any attacker who knows the message (and will leak some information about the key to any attacker who knows something about the message).

It's important to note that there's nothing in the definition of perfect security that says that the attacker can't already know something, or even everything, about the message. On the contrary, the definition explicitly allows for the possibility that an attacker might already have some information about the message, and merely requires that observing the ciphertext will not give the attacker any new information about the message.

In fact, against a computationally unbounded attacker who already knows the message, any encryption scheme will leak either the key or a set of equivalent keys. This is because the attacker can simply test all possible keys, attempting to decrypt the ciphertext with each of them, and discard those that don't yield the correct message.

| improve this answer | |
$\endgroup$
0
$\begingroup$

A theoretically secure cypher that leaks bits is OTP over a short message where naive message extension is used to prevent length-based attacks.

All the key bits after the end of the message are leaked. If your pad random source is good there is no attack.

Example:

PAD: 1 4 3 7 2 9 4 3
MSG: 3 1 2 3
ENC: 4 5 5 0 2 9 4 3

If the attacker were to learn the length of the message is 3 digits (say by a timing attack), it is now obvious the whole rest of the pad was leaked.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Let me make sure I understand, you pad a message with random data, then encrypt with OTP. Leak the key bits that encrypt the padding? $\endgroup$ – mikeazo Nov 13 '14 at 17:52
  • $\begingroup$ You pad with constant data then encrypt with OTP. This leaks the remaining key bits. Yes, you should be padding with random, but that's not the point. $\endgroup$ – Joshua Nov 13 '14 at 18:15
  • $\begingroup$ @Joshua I am finding it difficult to understand how will the remaining key bits will be leaked? $\endgroup$ – Pratik Soni Nov 14 '14 at 3:37
0
$\begingroup$

For a Public-Key cryptosystem (e.g. RSA), the ciphertext could presumably leak the whole Public-Key if desired (e.g. by appending it to the "usual" ciphertext).

(Assuming a perfectly secure Public-Key cryptosystem is theoretically possible).

Would be interested to know if Habib's equation can be extended to the relationship between the Public and Private Keys in such a cryptosystem.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Perfectly secure Public Key encryption is impossible. Because in the theory of computer science it has been proven that any turing machine (even a quantum turing machine) that does not "throw away information" is reversible. An encryption algorithm should not throw away information since the information is required for decryption. As a result, in case of public key encryption we only stand against a computationally bounded attacker. And, the only possible security is computational security. $\endgroup$ – Habib Nov 15 '14 at 12:45

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.