7
$\begingroup$

Very related to this question but not addressed there.

Does the following construction risk introducing any vulnerabilities that render it less secure than using either of its individual components in isolation?:

EncryptAB(K1||K2, PT) = EncryptA(K1, EncryptB(K2, PT))

EncryptA and EncryptB may be different algorithms. K1 and K2 my be of different lengths. The result need not be more secure than the better of it's components, just not less secure.

A related question is: are there any potential problems with interleaving the rounds of two or more independent algorithms?

(BTW: I'm not planning on doing either, it's more a matter of curiosity.)

Edit: I'm only thinking of the bare block cipher primitives rather then chaining modes and such.

Improve this question
$\endgroup$
1
  • $\begingroup$ In fact even if the keys are not independent and there are methods to deterministically generate the keys from a single base key, such that one can compose the ciphers and security is never reduced. Shown here: crypto.stackexchange.com/questions/741/… $\endgroup$
    – Ethan Heilman
    Jan 25, 2012 at 15:18

3 Answers 3

Reset to default
7
$\begingroup$

In your construct:

EncryptAB(K1||K2, PT) = EncryptA(K1, EncryptB(K2, PT))

it is easy to show that, as long as the keys K1 and K2 are independent, that this cannot be any less secure than the stronger of EncryptA and EncryptB.

Here is a sketch of how this is shown; suppose that there is a chosen plaintext attack against EncryptAB; that is, the attacker submits known values to EncryptAB, examines its results, and somehow rederive the value K1||K2. Then, this method can be used to attack EncryptA; the attacker would choose a random value for K2; he would take his chosen plaintexts, EncryptB them with his K2 value, and then submit them as chosen plaintexts to the EncryptA with the known key. Then, he can use those encrypted values to rederive the K1||K2 values, which includes the value K1 which he was interested in. The attack against EncryptB works in exactly the same manner.

Now, this method doesn't prove that EncryptAB is any stronger than the stronger of EncryptA and EncryptB (and, indeed, it might not be); however, it does show that using the two of them doesn't make things any worse. Also, we need to assume that that keys K1 and K2 are independent, because this simulation has the attacker picking one of those values; if they are interrelated, he wouldn't be able to do that.

Now, for your related question: how about interleaving the rounds of two different ciphers. That doesn't have any such security reduction, and in practice, it would give me the willies. Encryption round functions don't have that much strength in themselves (that's why we use multiple rounds); what a good round function is designed to do is play nicely with the round functions that'll be next to it in the designed cipher. For example, if there is a good differential through one round, it's going to be the case that it doesn't have any good paths through the next one (or the one after that). This is not by accident; the cipher designer (at least, if they knew what they were doing) went through some serious analysis to make sure that was the case.

In contrast, if you interleave the round functions from two different ciphers, well, no one has done any such analysis. Yes, it might be secure, but without someone spending a lot of time looking at it, you couldn't be certain. It'd be far better to use your original suggestion, and do a full set of rounds from your first cipher, and then do a second set of rounds from your second.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The only surprising result there is the elegance of the sketch. -- OTOH the 2nd result leads to the question of if there are any common ciphers that have more than one unrelated round function and/or a non-regular round structure. (I'm sure if I knew the right terms I could answer that myself but I have no idea what to Google for. :) $\endgroup$
    – BCS
    Jan 24, 2012 at 21:49
  • $\begingroup$ @BCS: about the most irregular round structure I've come across in a serious design would be MARS en.wikipedia.org/wiki/MARS_(cryptography) -- that has both keyed and nonkeyed rounds. I haven't gone into enough detail to see how different the nonkeyed rounds are from the keyed rounds $\endgroup$
    – poncho
    Jan 24, 2012 at 22:26
  • 1
    $\begingroup$ It is easy to construct two iterated ciphers with no obvious defect, but such that the composite cipher obtained by interleaving the rounds is very unsafe, e.g. always leave some (or even all but 1 bit) of the input unchanged. An example is a symmetric Feistel cipher, and a variant with left and right inverted. $\endgroup$
    – fgrieu ♦
    Jan 27, 2012 at 11:44
  • $\begingroup$ @fgrieu: so you would never use a composed rounds cipher without careful analyses, but I haven't seen any suggestion that it would be inherently worse than a uniform round cipher. $\endgroup$
    – BCS
    Jan 28, 2012 at 0:49
  • $\begingroup$ @BCS: no one can make a blanket statement that a nonuniform cipher is apriori worse. However, it does appear likely to make the cipher harder to analyze, and to give a cryptanalysis more options in attacking the cipher (as there are more specific things to attack). So, while it might be as secure, it looks like it would make it harder to attempt to validate that it is secure. $\endgroup$
    – poncho
    Jan 28, 2012 at 4:03
7
$\begingroup$

Yes, it is possible for the composed scheme to be less secure, but the answer is a bit wonky -- and has to do with the way we define security for encryption schemes. If ENCRYPTB is secure under Chosen Ciphertext Attack (IND-CCA) and ENCRYPTA is secure under Chosen Plaintext Attack (IND-CPA), then the composed ENCRYPTAB is /not/ necessarily secure under Chosen Ciphertext Attack. So you've actually weakened the security of the scheme.

For a concrete example involving ciphers, let ENCRYPTB be an authenticated encryption mode like AES-GCM. This mode provides both confidentiality (can't read the message) and authenticity (can't tamper with the message). In general, it should not be possible for you to tamper with the ciphertext in any way -- i.e., create a new slightly different ciphertext, for example, even one that encrypts the same underlying message.

But now let ENCRYPTA be an encryption scheme that /does/ permit you to tamper with the ciphertext, thus creating new ciphertexts. An example of ENCRYPTA is something like AES-CTR with padding at the end. You can tamper with AES-CTR messages, and if you only tamper with the padding it won't change the contents of the plaintext.

If you encrypt with ENCRYPTB alone, you have a very strong authenticated encryption scheme -- you can't change a bit of the ciphertext without it being detected. If you encrypt with ENCRYPTA(ENCRYPTB()) you /can/ tamper with the ciphertexts -- to a limited extent, by messing with that padding.

I realize this sounds like a theoretical concern, but it does come up in real applications.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I assume those modes are with respect to the block chaining and such. (And that is interesting and important information. +1) However, the problem I was thinking of is only with regards to the non-chained bare block cipher. (E.g. AES rather than AES-*.) $\endgroup$
    – BCS
    Jan 28, 2012 at 0:40
3
$\begingroup$

You should read the following paper:

It covers exactly this topic. The conclusion is: if you use independent keys, and if we are talking about ciphertext-only or known-plaintext attacks, the combination is certainly as strong as the first cipher; but, at least in theory, the combination might not be as strong as the second cipher. However, there is some reason to doubt whether the latter result is of any significant danger in practice.

For chosen-plaintext attacks, the combination is at least as strong as the stronger of the two (as always, assuming independent keys).

See also this discussion from sci.crypt.

Improve this answer
$\endgroup$

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.