8
$\begingroup$

I have seen a talk by Rüdiger Weis, where he says that you can combine two symmetric ciphers using XOR. According to him, that has the effect that its sufficient if only one of the ciphers is secure.

How does he do that? I have thought of

ciphertext = twofish(message) XOR aes(message)

but I can't see how the receiver would decrypt that, as he does not know either twofish(message) or aes(message).

I also thought of

ciphertext = twofish(aes(message))

But there is no XOR involved. So whats the problem with the above approach?

I have seen this answer but I don't think its relevant anymore. Using multiple ciphers may be needed to defend against NSA mass surveillance.

EDIT: The two formulas is what I came up with. Rüdiger Weis only said, "you can combine ciphers and XOR is involved".

$\endgroup$
  • $\begingroup$ crypto.stackexchange.com/q/25733/991 $\;$ $\endgroup$ – user991 Aug 20 '15 at 8:51
  • $\begingroup$ Your formula: ciphertext = twofish(message) XOR aes(message) Looks more as a kind of random number generation formula. Indeed , aes output will looks like random. twofish output will looks like random. Read Bruce schneier Book 'Applied cryptograpy' and you will learn that the best way to generate a random number is to Xor together random values. $\endgroup$ – user26263 Aug 20 '15 at 14:50
  • 1
    $\begingroup$ "I have seen this answer but I don't think its relevant anymore. Using multiple ciphers may be needed to defend against NSA mass surveillance." That NSA performs mass survaillance does not mean that NSA has broken - for instance - AES, an algorithm that they did not design. That said, if you want to protect yourself against adversaries like intelligence bureaus (of any country), then you may indeed want to take additional steps. The symmetric cipher is however unlikely to be your weakest link. $\endgroup$ – Maarten - reinstate Monica Aug 20 '15 at 17:14
  • $\begingroup$ They may have broken it, though. You can't know. $\endgroup$ – icehawk Aug 20 '15 at 17:21
  • 1
    $\begingroup$ There is no indication whatsoever that they have. And if they have, the ability to do so is far too valuable to disclose by decrypting your data (unless you happen to be, say, Abu Bakr al-Baghdadi). Furthermore, the more you try to glue your own crypto together, the more likely it is for you to commit a mistake that weakens your overall security rather than strengthens it. Modern crypto is already the strongest weapon in our arsenal; it's infinitely more likely you'll get popped by using crappy passwords, poor op-sec, failing to update software, etc. $\endgroup$ – Stephen Touset Aug 20 '15 at 23:04
13
$\begingroup$

The usual method to do this is to turn the block cipher into a stream cipher. In that way the ciphertext is generated by XOR'ing the plaintext with a generated key stream. This key stream in turn is generated by the mode of operation that turns the block cipher into a key stream. There are several of these modes, but CTR mode of operation is most often used (in new protocols anyway). You don't need to do this for stream ciphers of course.

Now you can just use $C = P \oplus K^1 \oplus K^2$ where $C$ is the ciphertext, $P$ is the plaintext and $K^1$ is the key stream of one cipher and $K^2$ is the key stream of the other cipher. As XOR is associative and commutative you can see this as first applying key stream 1 or key stream 2, and then the other. The key streams will have the same size as the plaintext.

This is similar to applying two one-time-pads to the plaintext. Given a secure block cipher, a key stream generated using CTR is secure but not perfectly secure. So it's not identical to using two one-time-pads. One difference with a one time pad is that CTR mode requires a nonce; the same nonce can be used for both stream ciphers though.

In contrast to one time pads it is possible to cryptoanalyze a stream cipher. This means that the key streams should be sufficiently independent of one another. So the stream ciphers should be created using separate keys and ciphers. If you would use the same key, IV and cipher then key streams would cancel each other out, leaving you with the plaintext after encryption.


Small stream cipher introduction

With a stream cipher a key and a nonce are used with the cipher to generate a key stream of any size. Usually the plaintext is not needed as input at this stage. The key stream is then XOR'ed with the plaintext. As the key stream should be indistinguishable from random to an attacker, it should be impossible to invert this operation without the key and nonce. Decryption is identical to encryption and if a block cipher is used then you may only need to use the block cipher in one direction (encryption or decryption). You can encrypt and decrypt by applying the key streams in any order as the XOR operation is associative and commutative.

$\endgroup$
  • $\begingroup$ You might want to mention that for this to be secure, both ciphers must be sufficiently non-similar so they don't cancel each other out, or have independent keys, preferably both. $\endgroup$ – Paŭlo Ebermann Aug 20 '15 at 19:25
  • $\begingroup$ @PaŭloEbermann Thanks, integrated your comment into the answer. $\endgroup$ – Maarten - reinstate Monica Aug 20 '15 at 20:07
  • 3
    $\begingroup$ As long as at least one of the ciphers is secure, it's enough for their keys to be independent; the ciphers themselves don't have to be "non-similar." $\endgroup$ – Chris Peikert Aug 21 '15 at 1:35
  • $\begingroup$ Yeah, I thought of that as well, but I'll leave it as an upvoted comment as the goal of the question was to use two dissimilar ciphers anyway. It's always beneficial to use two separate keys though. $\endgroup$ – Maarten - reinstate Monica Aug 21 '15 at 7:57
3
$\begingroup$

There is a very simple, completely generic solution, that unlike the other solution doesn't assume anything about how the two encryption schemes work internally (e.g., that they are built from block ciphers or have pseudorandom ciphertexts): given a message $m$, choose a uniformly random $m_1$ of the same length and let $m_2 = m \oplus m_1$. Then encrypt $m_1$ under the first scheme and $m_2$ under the second (using independent keys), sending both ciphertexts. To decrypt, recover $m_1$ and $m_2$ and output the message $m=m_1 \oplus m_2$. (This is all just a simple secret-sharing of the message.)

This works because even if the attacker can break, say, the first scheme and recover $m_1$, the security of the second scheme hides $m_2$ and thereby $m$.

$\endgroup$
  • $\begingroup$ The disadvantage here is only that you need to send/store double the amount of data. Apart from that, sounds sound to me. Great answer. $\endgroup$ – Josef Aug 21 '15 at 6:54
0
$\begingroup$

If you have a uniformly random string $s$ as long as your message $m$, then $s \oplus m$ is a one-time pad (using $\oplus$ for XOR).

If a cipher is secure, then its ciphertext should look like uniform randomness to anyone who does not have the key (even if they know the message). The XOR combination is then effectively a one-time pad.

At least, that's the intuition. The formal study of these things goes by the name of robust combiners

There's no security problem with doing the two in sequence as in your example. But the XOR combination allows you to do the two encryptions in parallel, which may be more efficient in some cases.

EDIT: I see what you mean now. Are you sure that's exactly what he said? It looks to me like that construction is not going to be decryptable, like you suspected. Are you sure it's not something along the lines of Maarten's answer (which does decrypt), or a RNG (which doesn't need to)?

$\endgroup$
  • $\begingroup$ I know what a one-time-pad is, but I can't see how that relates to my question. I do not want to exchange another key for every message. $\endgroup$ – icehawk Aug 20 '15 at 8:55
  • $\begingroup$ It was just an intuitive example. If AES is real-or-random secure, then you should not be able to tell AES(m) from a random string r of the same length. It follows by reduction that you also cannot tell (AES(m) XOR Twofish(m)) from (r XOR Twofish(m)) - as long as you use different keys for the two ciphers. But (r XOR Twofish(m)) is a one-time pad, hence it gives you no information on m, even if Twofish is broken. $\endgroup$ – Bristol Aug 20 '15 at 9:00
  • 3
    $\begingroup$ Please don't use the word "one-time pad" for a stream cipher. This is not the same. $\endgroup$ – Paŭlo Ebermann Aug 20 '15 at 19:24
  • $\begingroup$ There is a security problem, it is vulnerable to meet-in-the-middle, that's why the XOR method is preferred. $\endgroup$ – eckes Apr 24 '17 at 8:00

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.