Security Level Estimate when Cascading/Compositing Ciphers?

Way back when, DES had a theoretical security level 56-bits. 2-key TDEA provides about 80-bits of security, and 3-key TDEA provides about 112-bits of security. Obviously, those security levels are not linear in the cascading of the underlying block cipher.

First question

How does one estimate the increase in security level when compositing?

Second question

Is it necessary that the composition is not closed so that the composite does not form a group? I.e, if A(B(C(x))) = y, then there cannot be a A' such that A'(x) = y. (I believe so).

Third question

How does this apply to Diffie-Hellman over integers? If I run the Diffie-Hellman algorithm twice with 3072 moduli (i.e., 128-bits of security each) and concatenate the two shared secrets, then how many effective bits of security are present? (Intuitively, I think its around 128-bits or 129-bits).

Fourth question

How does this apply to RSA? If I run the RSA algorithm twice with 3072 moduli (i.e., 128-bits of security each) and transport two shared secrets, then how many effective bits of security are present? (Intuitively, I think its around 128-bits or 129-bits).

Sorry to ask these questions. The back story has to do with elliptic curves and patents, and I'm trying to figure out if its feasible to exchange/agree/transport an AES-256 key in distinct pieces using traditional crypto primitives while maintaining security levels and avoiding elliptic curves.

• You've loaded too many questions together into one. Please pick one question per question. Your first question is too broad; the answer will depend upon whether you're talking about a block cipher or something else. I suggest you just tell us about the real problem you have; or else ask multiple separate questions. – D.W. Dec 26 '13 at 2:40
• You might find this interesting. – mikeazo Dec 26 '13 at 2:46
• Nowadays the reason for cascading is guarding against cryptoanalytic advances against one primitive ensuring that the whole system is as secure as the strongest primitive. It's not a good way to raise the security level. – CodesInChaos Dec 26 '13 at 10:04

First question

It depends upon the scheme. It also depends upon what kind of composition you are talking about. Triple-DES uses multiple encryption. That's one kind of composition. The approaches you talk about in your third and fourth questions are a different sort of composition. They will have different security properties.

Second question

Yes. If the operation forms a group, then using multiple encryption does not add security.

Third question

This provides only 128-129 bits of security, but not for the reasons you expected. The reason is Diffie-Hellman with a 3072 bit modulus provides only about 128 bits of security; one can break Diffie-Hellman with a 3072 bit modulus using something like $2^{128}$ work (very roughly). So, one can break two Diffie-Hellman exchanges using $2^{129}$ work (very roughly). In other words, this does not add security.

This is not a practical weakness in practice, because in practice 128 bits of security is more than enough; no one is going to be able to perform a computation that requires $2^{128}$ work (not in my lifetime). That said, this is a certificational weakness in the protocol, and no one would consider this to be good protocol design; it is rather crummy protocol design.