# RSA-based authentication and key-agreement protocol

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.

-
What about TLS with client certificates? Or SSH with public-key authentication? –  Paŭlo Ebermann Dec 11 '11 at 19:10
@PaŭloEbermann: Notice that I have added requirements, including simplicity, and non-reliance on block cipher and MAC. I do not know TLS or SSH enough to tell if they fit in some variant, but I'm frightened by protocols which are so complex that I can't find a complete and readable statement, with a reputation of being hard to demonstrate secure, and an history including some failures. –  fgrieu Dec 12 '11 at 3:06