Re: [Cfrg] [CFRG] Dual use (vs key separation) questions

["Paterson, Kenny" <[e-mail]>]

Dan,

I think I can answer some of your questions - see in-line below. Let me know if I mis-understood anything.

On 8 Jun 2012, at 19:44, Dan Brown wrote:

Dear CFRG members,

My colleague Alex Truskovsky has brought to my attention the issue of dual use of a single private key (of a public key scheme, e.g. RSA or ECC), where the private key is used for both signing and for key exchange (such as decryption or key agreement).  Some standards address dual use:

1: NIST Special Publication 800-57 forbids a dual use with one exception: a key exchange private key may be used to sign a certificate request.

2: PKIX certificates (a) can be configured to allow or forbid dual use (though this may only apply to the public key side), and (b) when a cert for key exchange key forbids “dual use”, a signed certificate request is also forbidden.

Restrictions against dual use are usually called key separation.  Above, 1 is key separation (with exception), and 2b is key separation (when the cert asks for it).

Questions (not necessarily independent):

So, in terms of “dual use”, NIST and PKIX are not totally aligned.  Should there be better alignment?  For example, should PKIX move towards NIST by hardening (a) to forbid dual use, and softening (b) to allow dual use signed cert requests?

No idea, sorry.

Are there scheme-generic attacks of dual use?  Of course, dual use introduces a potential risk, which can be shown by using a contrived pathological example, in which any use of the signature scheme reveals the private, but I am asking here if there is an attack that applies for schemes, even when both schemes are secure.

Here, I think you mean: can it be shown that dual use always leads to cryptographic weakness, no matter what the key or algorithm? The answer is then "no", in the sense that there are combined signature and encryption (CSE) schemes which are provably "jointly secure", i.e. where the dual use of the key provides both a secure encryption and a secure signature scheme, even when the adversary has simultaneous access to signing/decryption oracles for the two schemes. For a recent paper on this, with constructions of schemes in the standard model, and extensive references to the prior literature, see:

K.G. Paterson, J.C.N. Schuldt, M. Stam and S. Thomson, On the Joint Security of Encryption and Signature, Revisited. In D.H. Lee and X. Wang (eds.), Asiacrypt 2011, Lecture Notes in Computer Science Vol. 7073, pp. 161-178, Springer, 2011.

(Full version at: http://eprint.iacr.org/2011/486)

This paper also contains pathological examples of the type you mention. For example, we describe encryption and signature schemes that are individually IND-CCA and UF-CMA secure, but whose security totally falls apart once dual use is allowed.

Dual use raw RSA, i.e. without padding, is subject to some severe attacks: (i) chosen-ciphertext forgery, where a signature is forged using a decryption oracle, and (ii) chosen-message decipherment, where a challenge ciphertext is deciphered using a signing oracle, because decryption and signing are the same operation in raw RSA.  In both attacks the private key owner follows key separation, so key separation prevents these attacks only if done on the public key side.  Are these attacks the main justification for key separation?  Are there any other scheme-specific attacks with dual use?  For example, is there any other attack (e.g. even stronger, not using an oracle for the private key operation, i.e. a more passive attack) on raw RSA?  Is there any attack on any type of padded RSA? (I think I saw one paper on it.)

Yes. See for example:

J.P. Degabriele, A. Lehmann, K.G. Paterson, N.P. Smart and M. Strefler, On the Joint Security of Encryption and Signature in EMV. In O. Dunkelmann (ed.), CT-RSA 2012, Lecture Notes in Computer Science Vol. 7178, pp. 116-135, Springer, 2012.

(Full version at: http://eprint.iacr.org/2011/615)

This paper gives an attack which shows how to use a Bleichenbacher-style oracle for RSA-PKCS#1v1.5 encryption to forge EMV signatures for the same RSA key pair , in the specific context of EMV. So it's an example of the type you seek.

Is there an attack on ECDH and ECDSA dual use?

Not currently known. But the above paper does prove security of dual use for ECDSA +ECIES and EC-Schnorr+ECIES. And ECDH is sufficiently close to ECIES that I'd guess the proofs could be adapted to the ECDH case. Let me know if you are seriously interested in knowing the answer to this question.

Security proofs, e.g. for RSA-OAEP, often assume dual use is forbidden.  What security analysis (e.g. proofs) work under “dual use”?  A paper by Paterson
does this, and mentions some others, but they seem not to cover the usual IETF schemes?

Thanks for the mention. I guess this is the Asiacrypt paper above, which answers some of your earlier questions. If there are specific pairs of schemes which you are interested in (e.g. RSA-OAEP + ???) let me know and I can put a student to work on it :-).

Offhand, generally schemes in the ROM are OK, especially if you allow a bit of domain separation in the inputs to the Random Oracle(s).

Does universal composability also address dual use?

I'm not an expert on UC, but I very much doubt it automatically covers this. Maybe the UC experts can pitch in here.

Do the current conventional most common suite of public key schemes in IETF sufficiently resist dual attacks?

Again, what specific schemes do you have in mind? (Note that TLS still uses PKCS#1 v1.5 for RSA encryption, so we won't be able to prove anything there...)

So, is key separation overkill for these schemes?  Or, should key separation be added as precaution, because of a lack of thorough study?

Clearly, it's a good idea to enforce it if you can afford the additional costs of key generation (non-trivial if you have a deployment involving millions of EMV cards, each containing a unique RSA key pair), certificate management, etc.

What general expectations should there be for public key schemes regarding dual use?  Suppose a new public key scheme is proposed (e.g. pairing-based, quantum-resistant, homomorphic, etc.). Should developers of application standards, who may be using signatures and encryption at a high level interface allowing algorithm agility, always use key separation to prevent potential dual use attacks?

Personally, I would recommend this, because it's hard to anticipate exactly what schemes people will try to use and how they will end up being implemented. If there's a general principle we can apply which improves security and which is not too costly, then we should apply it. I say this despite the many known positive results on the security of dual use.

 Or should developers and cryptographers have to keep a sharp eye out for dual use attacks, or else proofs of security against dual use, before considering public key schemes secure?

See above.


Best regards,

Daniel Brown

Research In Motion Limited



Cheers

Kenny