Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.