RSA-based authentication and key-agreement protocol

Question

An authentication and key-agreement protocol between devices shall mutually demonstrate their identity, and establish a shared random secret $R$ suitable for securing later communications.

To that purpose, each of the many devices receive a certificate from a certification authority, binding their identity $ID_i$ (including unique serial number and operational characteristics) to their unique RSA public key $(N_i,E_i)$. The legitimate device with $ID_i$ is initially assumed to be the only thing to possess the RSA private key $(N_i,D_i)$ corresponding to its certified public key, and use it per the protocol's rules only.

An adversary's goal is to convince a legitimate device $i$ that another legitimate device $j$ with $ID_j$ was used during the protocol, when it was not; or to breach the confidentiality of $R$ that $i$ will use (with the assumption that $j$ will not breach it); or make that $R$ different from what it would be under normal execution of the protocol.

The protocol must resist disclosure of $R$ from earlier executions, and compromise of the private key of other legitimate devices. Communications are insecure, including ability for an adversary to alter, replay, or create messages (or communicate with other legitimate devices, but compromise of their private key covers that).

We can assume that in preliminary steps of the protocol, the two participating devices have exchanged their alleged identity and certificate, in clear; have verified the certificates using a conventional off-line PKI; and have unambiguously agreed upon Master/Slave roles in the protocol (statically determined from their respective $ID$; or perhaps with the device having the highest alleged $ID$ assuming Master role).

We want something simple, suitable for implementation in a Smart Card. We'd rather avoid use of a block cipher or MAC during that protocol, though we may assume a hash as used in an RSA message/signature encoding scheme.

I'm looking for literature (or an answer) discussing such protocol, hopefully something with a security argument. One theoretical difficulty is that on each side we have a single key for both mutual authentication, and confidentiality of the shared $R$.

One such protocol is specified in a European Regulation: EEC 3821/85 as modified by EC 1360/2002 and EC 432/2004, Annex 1B, Appendix 11, CSM_020, second drawing, as found page 268 of the PDF, starting with Generate Challenge. Incidentally, I'm interested in the origin of this protocol, or if it is reminiscent of something used elsewhere; and in additional security goals that it might have. To the best of my knowledge it is secure in the sense stated above, but I know of no security analysis. I tried to summarize that protocol, but the question's size doubled before I was done with notations, so I gave up for now.

Nothing in this is related to my current professional activity.

Answer 1

What you are looking for is authenticated key agreement with perfect forward secrecy based on certificates.

First, to address @Paulo's comment, TLS/SSL does provide this functionality with any of the Diffie-Hellman based suites. However it is more complicated than you require, as it generates several different shared secrets used for different purposes. SSH and IPSec have similar protocols.

The landmark key exchange protocol with the required properties is called the station-to-station protocol. I recommend the discussion of it (and the whole chapter for context) in the Handbook of Applied Cryptography (ch 12, pg 519).

STS does require an encryption function which you specified you wanted to avoid. A modern key exchange that does not have an encryption function is MQV and its variants. Since you also wanted a rigorous security proof, likely more has been written about MQV and its variant's security than any other protocol (although the history is somewhat sordid). The drawback for you is that it requires the public keys (in the certificates) are discrete log-based not RSA (STS can work with RSA public keys since the long-term secret is only used for signatures). It may also be patent encumbered.

To conclude, I don't have a perfect protocol that both works with RSA and avoids using encryption or MACs but looking into these two protocols should give you a head start on finding something you can work with.

Answer 2

Well, hope that it's not late for this answer. Because it was yesterday that I encountered this problem and I'm new to this wonderful website.

According to your description, and as far as I know, this protocol meets your demands very well.

First, it works with RSA as you have mentioned in the second paragraph. The original version of this protocol is identity-based. But the authors also give the certificate-based version. In the identity-based setting, users won't need the certificate to certify the relationship between the user's identity and its public key; their identities are the public key directly(this concept was introduced by Shamir, personally think think it's better than certificate-based). Well, In the certificate-based setting, the occasion is what you said.

Moreover, this protocol can resist impersonate attack(as you've said in third paragraph), achieve known key security("The protocol must resist disclosure of $R$ from earlier executions"), and offer weak perfect forward security(the leakage of both users' private keys won't disclose previous session key). But you require that "compromise of their private key covers that", in fact what you want is full perfect forward security against active adversary, while the weak perfect forward security is only against passive adversary. Fortunately, this protocol offer full perfect forward security against active adversary. And provide very rigorous security proof. Basically, this protocol is proved secure in the Canetti-Krawczyk model, a relative strong model.

On performance, it needs almost $2$ exponentiations per party when $e=3$. Thus it's very suitable for implementation in the environment of limited computational resource e.g smart card. In addition, it doesn't employ any block cipher or MAC.

In a word, from every aspect I think this protocol is very proper for your choice.