Evaluation of Security Level of Cryptography

Key-Sharing Schemes (Summary)Phillip Rogaway
University of California at Davis
Chiang Mai University

January 16, 2001

1

Summary of Files

In support of Information-technology Promotion Agency, Japan, I assembled a team to look at at
the four key-distribution protocols submitted to CRYPTREC. The team consisted of Mihir Bellare(UC San Diego), Dan Boneh (Stanford), and me. Our analysis is contained in the following files:

01
2
3
4
5

HDEF-ECDH
HIME-1
ECDHS (of SEC 1)
ECMQVS (of SEC 1)

ks-cover.pdf
ks-ecdh.pdf
ks-hime1.pdf
ks-ecdhs.pdf
ks-ecmqv.pdf
ks.pdf

3 pages
7 pages
8 pages
24 pages
18 pages
60 pages

Executive Summary
Detailed Report
Detailed Report
Detailed Report
Detailed Report
Concatenation of the above

On each of the detailed reports I have listed the authors in approximate order of contribution.

2

Summary Findings

We briefly summarize our findings.
1. HDEF-ECDH: This proposal is not (primarily) a key-sharing scheme; it is, instead, a method forchoosing elliptic curve domain parameters. For that purpose it is a sensible method; in particular,
the groups it finds will resist all currently known attacks. All the same, CRYPTREC had madeno request for the functionality delivered by this proposal. Even if they had, we see no strong
advantages over simply using the curves published in SEC 2, which likewise resist all currently
known attacks. A section in the proposal describes using the resulting curves for key-sharing
goals, but that section simply says to use the standard Diffie-Hellman approach. Analysis of thatapproach can be found in our report on ECDHS.

12. HIME-1: This isn’t a key-sharing scheme at all; it is a trapdoor function. From such a function
one can build an encryption scheme using standard methods. The intent was for the resulting
encryption scheme to support faster decryption than alternative methods. But, comparing acrossa given level of security, we find that there are alternatives that have comparable or better speed
for decryption, and superior speed for encryption. We see few advantages.
3. ECDHS (of SEC 1): This is an open-ended family of key-sharing schemes. The methods here
are efficient, and are already widely standardized. Still, most of these schemes fail to meet somesignificant security goals, and it is not carefully described in the spec what goals are achieved bywhat schemes. No provable security results are claimed in SEC 1. We sketch one security result,for one of the “strongest” of the instantiations possible. We find the schemes too open-ended, andhaving goals that are too ill-defined.
4. ECMQVS (of SEC 1): This is again family of key-sharing schemes (that is, it supports multiple
trust models). ECMQVS is particularly efficient, and is already widely standardized. For thetrust model of primary interest (static/ephemeral keys for both parties) strong security results
are already known to be impossible, by virtue of an attack described by Kaliski. This attack can
be closed by various counter-measures (still within the scope of the standard). Still, one should
not have to do such things, and the scheme appears rather ad hoc regardless. No provable-security
results have appeared. We show that the scheme depends on an unusual assumption, that we callthe LDH assumption. We do not now how this assumption is related to other, more standards
assumptions.
Overall, we would be happier with key-sharing schemes that are key-sharing schemes, that are not too
open-ended in instantiation possibilities, that claim to solve some clearly-specified problem, and thathave verifiable proofs, under standard assumptions, to back up this claim. We are not there.
Detailed information is found in the four attached reports.

3

Where From Here?

The state-of-the-art for key-sharing schemes is not nearly at the level of the state-of-the-art for othercryptographic goals getting standardized by CRYPTREC (symmetric encryption, asymmetric encryption, digital signatures, and cryptographic hash functions). This is the only domain among those where:(1) there is no complete and agreed-to set of definitions; (2) there are no proven correct protocols formany of the problems one wishes to address; (3) the desired level of variability in security goals, andthe round-cost in achieving them, motivates accepting a plurality of schemes; (4) the associated levelof definitional complexity makes a mathematical treatment long and weighty; (5) even an informal
description of requirements would be the subject of much debate. Thus it would seem to be harderto devise at a good standard for key-sharing than for any other problem considered. It is arguably acouple years premature to have a good standard in this domain.
In the face of this situation, natural options include:• Do nothing. Do not pursue any new standard in this domain. Wait.
• Copy. Just take some existing standard, recognize it as flawed, refer to it, and consider it to begood enough. Revisit in a few years, with the hope of there being better options.

2• Copy-with-added-restrictions. Slightly tweak some existing standard, getting rid of the worst
parts. But don’t invent much.
• Invent. Follow a different methodology than inviting people to submit proposals. Commission awell-chosen group of people to suggest a standard for a very specific purpose.
For a key-sharing scheme it is impossible to do well without a good understanding of the requirements. If the goal were asymmetric encryption, say, people could mostly agree about what is a goodgoal. The same can be said for digital signatures, block ciphers, and numerous other primitives. But for
key-sharing the goals are not clear, and, more than with other primitives, there may be multiple goals,
with their importance depending on the context. The difficulty of doing well in this domain should not
be underestimated.

Sincerely,Phil Rogaway3