1
$\begingroup$

Assume you have:

  • A truly random one time pad, $P$
  • A plain text message, $M$
  • Two symmetric ciphers, $C_S$ and $C_W$, where $C_S$ is always more secure than $C_W$

Assume the keys have already been securely exchanged and the attacker intercepts everything Alice transmits.

In theory, can $C_S(P \space \oplus \space M)$ and $C_W(P)$ taken together be less secure $C_S(M)$?

Also, is $C_S(P \space \oplus \space M)$ and $C_W(P)$ always more secure than $C_S(M)$.

In longer form, if I XOR a message with a one time pad and encrypt that with one cipher and encrypt the one time pad with a different cipher, can that be less secure than just using the stronger of the two ciphers? Is it the case that it would always be stronger?

$\endgroup$
5
  • $\begingroup$ Why do you encrypt $P$? What is the purpose? $\endgroup$
    – kelalaka
    Feb 17 '20 at 18:43
  • $\begingroup$ I'm assuming $C_S(P \space xor \space M)$ with $C_W(P)$ can be more secure than $C_S(P)$ and $P$ together. I don't know if that's the case. $\endgroup$ Feb 17 '20 at 18:59
  • $\begingroup$ I don‘t understand: you say the keys are assumed to be exchanged. Then what is P for? Is it used in addition to a key? The weakest part is the key exchange, so this needs to be clear. $\endgroup$
    – not2savvy
    Feb 18 '20 at 8:07
  • $\begingroup$ I'm not sure it's worth it (having a good source of entropy isn't always easy and processing and transmitting twice the bytes is a pretty big cost). But if it can't be worse, all things being equal it can't hurt and might help, it would be fine to do :-) Mostly curious in the abstract. $\endgroup$ Feb 18 '20 at 17:21
  • $\begingroup$ I guess the simplest way to put it is, if $C_S$ is every broken you're still protected by $C_W$ and vice versa. So the attack has to clear two hurdles instead of one. $\endgroup$ Feb 18 '20 at 18:02
0
$\begingroup$

No, it cannot be less secure. The proof is simple: if $P$ is ever found out, then the strong cipher's security still protects $P \oplus M$ and thus $M$.

However, if the one-time-pad $P$ ever leaks, then it can be used to break the weak cipher, and in that case, the result is just as secure as the strong cipher. It is generally not a good idea to rely on data to be kept secret forever. Moreover, it is certainly not a good idea to rely on security that may or may not be present.

Outside of theoretical security, the weak cipher may also have issues with, e.g., padding oracle attacks that could leak $P$, in which case, only the strong cipher will be left.

All in all, without additional details, I would rate this about as secure as the strong cipher, so the one-time pad doesn't seem to have much benefit (certainly compared to, for instance, frequently using fresh keys).

$\endgroup$
2
  • $\begingroup$ My thought was you never know the real strength of a symmetric key system for sure. So if you use two different ciphers you at least get the stronger of the two. So in theory, at worst you get no additional security and at best you get the stronger of the two ciphers even though you might not know which one that is. So at the cost of finding a good source of entropy and transmitting more information, you get potentially safer transmission. $\endgroup$ Feb 18 '20 at 17:15
  • $\begingroup$ I think I have a counterexample to the answer's assertion. $\endgroup$
    – fgrieu
    Aug 11 at 18:29
0
$\begingroup$

I'll only tackle the first question:

In theory, can $C_S(P\oplus M)$ and $C_W(P)$ taken together be less secure $C_S(M)$?

Yes, it can be less secure.

Argument: I'll make an explicit example assuming $M$, $P$, ciphertext and keys are 16-byte, $M$ is UTF-8 text right-padded with zeroes, under an attack model where adversaries get a single ciphertext.

Define an easily computed condition $f(X)$ where $X$ is a 16-byte block and $f(X)$ either true or false, such that

  • $f(M)$ is always true

  • $f(X)$ is true with probability about $1/2$ for random $X$

    A suitable $f$ is: every byte of $X$ is less than $\text{0xF5}=245$. That's because bytes $\text{0xF5}\ldots\text{0xFF}$ are reserved in UTF-8, and $(245/256)^{16}\approx1/2$.

Note $E_K(X)$ the AES-128 encryption of $X$ under keys $K$.

Construct $C_S$ for 16-byte key $K$ and block $X$ as follows:

  • set $K'$ to the all-0x00 or all-0xFF 16-byte block according to the low-order bit of $K$

  • If $f(X)$ holds,

    • then set $X\gets E_K(X)$ repeatedly until $f(X)$ holds
    • otherwise set $X\gets E_{K'}(X)$ repeatedly until $f(X)$ does not hold
  • Output $X$

    Whatever a known $K$ is, $C_S$ is an easily computed and invertible bijection of any 16-byte block, such that $f(E_K(X))=f(X)$ for all blocks $X$. That's using the the standard cycle walking technique. When it encrypts a message $M$, the block cipher $C_S$ is strong. But when it encrypts a random $X$, with probability about $1/2$ it uses $K'$ which can take only take two values, thus is weak.

Make $C_W$ identity regardless of $K$, which insures "$C_S$ is always more secure than $C_W$": block cipher $C_S$ is not good, but still always better than nothing.


When an adversary not knowing keys gets $C_S(M)$, the condition $f(C_S(M))$ holds and practically nothing is learned about $M$ (beyond confirmation that $f(M)$ holds).

When an adversary gets $C_S(P\oplus M)$ and $C_W(P)$, the later yields $P$, and

  • if $f(C_S(P\oplus M)$ holds, which has probability about $1/2$, it's learned that $f(P\oplus M)$ holds

  • otherwise, decryption of $C_S(P\oplus M)$ can be attempted with both all-0x00 or all-0xFF keys, yielding candidates $X_0$ and $X_1$ both with $f(X_0)$ and $f(X_1)$ false. $M$ must be one of the $M_i=X_i\oplus P$. Further, if $f(M_i)$ is false then we can rule that $i$ out, and be certain the other is $M$.

    In the end an adversary learns $M$ with probability about $1/4$, one of two possible values for $M$ with probability about $1/4$, and about one bit worth of information about $M$ otherwise.

We conclude that $C_S(P\oplus M)$ and $C_W(P)$ taken together is less secure than $C_S(M)$.


This could be extended to full-blown ciphers handling variable-length messages, with IV. The idea will remain to have $C_S$ secure when encrypting plaintext $M$ with a certain characteristic, but insecure when encrypting random plaintext (e.g. leak it's key). That's possible even if we add the constraint that encryption never increases size (beyond the IV).

$\endgroup$
2
  • $\begingroup$ Err, if P⊕M and P is truly random, how can the protocol be weaker with more stuff? If Eve is listening, then this question takes on a whole different meaning, $\endgroup$
    – Paul Uszak
    Aug 12 at 2:21
  • $\begingroup$ @Paul Uszak: yes $P\oplus M$ and $P$ (taken individually) are truly random. Basically $C_S$ is crafted to be safer when it's plaintext has a certain characteristic that $M$ has, but $P\oplus M$ does not always have. That's why! $\endgroup$
    – fgrieu
    Aug 12 at 3:50

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.