What cryptanalysis is possible against two independent keystreams XORed against plaintext?

If a wise person was unsure about which commercial cryptography standards are truly secure from the fascist powers that be, it would seem the obvious option for companies and individuals is to now use two independent algorithms to encrypt. To be clear I am not talking about a cascade cipher in CBC mode e.g. $Encryption_2$($Encryption_1$($plaintext$)), where an attacker can unravel one layer of encryption at a time because they have direct access to the resulting ciphertext from each algorithm.

I am talking about using two unique keys and two block cipher algorithms in Counter Mode (or stream cipher algorithms) to generate two unique keystreams, then XORing (⊕) them together with the plaintext. For example:

• $Key_1$ = 256 bit random key
• $Key_2$ = different 256 bit random key
• $IV$ = 128 bit random initialization vector for AES
• $Nonce$ = 192 bit random nonce for XSalsa20

• $Keystream_1$ = $AES$$_C$$_T$$_R$$(Key_1, IV, Counter)$

• $Keystream_2$ = $XSalsa20(Key_2, Nonce, Counter)$

• Ciphertext = $Keystream_1$ ⊕ $Keystream_2$ ⊕ $Plaintext$

• Decryption = $Keystream_1$ ⊕ $Keystream_2$ ⊕ $Plaintext$
• Data sent over wire = $IV$ | $Nonce$ | $Ciphertext$

The key exchange, MAC and transport protocol are out of scope for the question, I want to focus on the encryption part.

• It would appear that an attacker's methods of cryptanalysis for each individual algorithm would not work as they do not have access to the plain ciphertext of either algorithm because the keystreams from each algorithm are XORed together.
• Known plaintext cryptanalysis would not work either. For example the first 5 bytes are hello, and they have a resulting ciphertext of xAi3z. With a single keystream they could get those 5 bytes of the keystream which would be the plaintext ⊕ the ciphertext. Then over the course of multiple ciphertexts/known plaintexts there might be a weakness to deduce the original key which generated the keystream. However with two independent keystreams, a cryptanalyst can't know which combination of bits make up the combined keystream. For example: they know plaintext bit 0 and ciphertext bit 1, but do not know whether the keystream bits were definitively a 1 or a 0 bit, nor which bit came from which keystream.

• Protection from non-public flaws or weaknesses in either encryption algorithm.
• Cryptanalysis is almost impossible?
• Decryption requires breaking both algorithms.
• Brute force required to find two random keys instead of one ($2^{256} + 2^{256}$) or $2^{128} + 2^{128}$ (on a quantum computer).

• Generating and exchanging two keys instead of one.
• Slightly more network traffic required to send an extra IV or nonce with each transmission.
• Slower encryption and decryption.

My questions:

1. Assuming both algorithms are implemented properly, the random number generators produce truly random data and there is an attacker in a privileged network position intercepting multiple ciphertexts, how or what kind of cryptanalysis could the attacker perform against this scheme to break the confidentiality of messages?

2. Is there a faster method than brute force to find the two encryption keys or break the confidentiality of messages?

• Your question seems interesting. BTW, what you are proposing is exactly a cascade cipher, in this case of two stream ciphers. – cygnusv Jan 14 '15 at 9:54

Asmuth and Blakley provided a proof that, assuming the keys for each cryptosystem are chosen independently, breaking their composite cryptosystem is at least as hard as breaking the hardest part of either. [1] Building on their work, cascade ciphers have been shown to in fact be harder to break than the hardest part of either.

Admittedly, what you're talking about sits in an awkward place between cryptographic exponentials and cascade ciphers. A cryptographic exponential (of two ciphers) is defined as: $$M\oplus R\oplus R'\>\|\>E(R)\>\|\>E'(R')$$ where R and R' are truly random bitstrings.

I can't give much of anything concrete other than that. Hope this answers your question.

1. C. Asmuth, G. Blakley. "An efficient algorithm for constructing a cryptosystem which is harder to break than two other cryptosystems"
• What he's talking about is a cascade of stream ciphers. $\;$ – user991 Jan 14 '15 at 5:44
• It would be nice if you could find this reference online or post relevant snippets from it, but it seems to be behind a paywall. The conclusion doesn't seem to be fully fleshed out. For example if I know XSalsa20 is more secure than AES, then I can easily come to the conclusion that a XOR cascade cipher is at least as strong as XSalsa20. However it doesn't explain that it may not be possible to perform cryptanalysis on either algorithm because a cryptanalyst does not have access to the raw ciphertext produced from either algorithm. Are there methods that can attack a stream cipher cascade? – subfree Jan 15 '15 at 21:49

In your example, $Encryption_1$ is $\textsf{AES}_{CTR}$ and $Encryption_2$ is $\textsf{Salsa20}$. Then, the encryption method you are proposing is $Encryption_1(Encryption_2(plaintext))$, which is in fact a cascade of stream ciphers. Note that, because you simply XOR the streams, this cascade cipher commutes, that is, you will have the same result if you use $Encryption_2(Encryption_1(plaintext))$.

In [1], Maurer and Massey prove the following result:

Corollary 1. A cascade of commuting ciphers is at least as difficult to break as the most difficult-to-break component cipher.

So, basically, you can at least be sure that your proposed encryption method will not be weaker than the original stream ciphers used.

References:

• It would be nice if you could find this reference somewhere online or post relevant snippets from it but it seems to be behind a paywall. The conclusion doesn't seem to be fully fleshed out. For example if I know XSalsa20 is more secure than AES, then sure I can easily come to the conclusion that a XOR cascade cipher is at least as strong as XSalsa20. However it does not explain if it's even possible to perform cryptanalysis on this kind of scheme because the cryptanalyst does not have access to the raw ciphertext produced from either algorithm. – subfree Jan 15 '15 at 21:45
• @subfree Yes, it has. Let $C = Encryption1(Encryption2(plaintext))$. Then clearly $C$ is the ciphertext for the first stream cipher $Encryption_1$. Now, since the cascade commutes, then $C = Encryption2(Encryption1(plaintext))$ too, so $C$ is the ciphertext for $Encryption_2$. In the first case you simply consider $Encryption_2(plaintext)$ as the plaintext for $Encryption_1$, while in the second case you consider the converse. – cygnusv Jan 16 '15 at 7:26
• @subfree I have added a link to an online version of the paper. – cygnusv Jan 16 '15 at 7:30
• Thanks for adding the paper. I think it's clear that you can do Keystream1 XOR Keystream2 XOR Plaintext, or Keystream2 XOR Keystream1 XOR Plaintext, or any combination really for encryption or decryption, the order doesn't make a difference. However that is not the point. In cracking the encryption, even if you have known or chosen plaintext, a cryptanalyst only ever gets the combined keystream C which is Keystream1 XOR Keystream2. With the combined XORed stream it is impossible to determine which bits came from either random keystream. – subfree Feb 26 '15 at 3:33
• @subfree Are you saying that even if we assume that we are able to break Encryption1 and Encryption2 separately, we cannot break the combination? – cygnusv Feb 26 '15 at 8:00