Study Group for Future Public-Key Cryptography Standards Wednesday, March 15, 2000 Technische Universitaet Berlin Fachbereich Mathematik MINUTES (unapproved) Handouts: * Meeting agenda * Study group charter * NTRU/PASS proposal * Password-based authenticated-key-exchange methods proposal * Public Key Validation: A Piece of the PKI Puzzle * Advanced Cryptographic Engine Proposal In attendance: Ari Singer (P1363 chair), Pitney Bowes Don Johnson (P1363 vice chair), Certicom Dan Lieman (P1363 treasurer), NTRU Wael Adi, TU Braunschweig Dan Brown, Certicom Ernst Giessmann, Deutsche Telekom Burt Kaliski, RSA Laboratories Mario Koppen, FLG IPK Berlin David Kravitz, Wave Systems Corp. Franck Leprevost (host), CNRS-Paris & TU Berlin Preda Mihailescu, ETH Zürich Tatsuaki Okamoto, NTT Allen Roginsky, IBM Andreaz M. Schöpp, TU Berlin Martin Schulze, University Bonn Victor Shoup, IBM Zurich Research All attendees of this meeting are considered to be full voting members of the study group. Morning session 1. Introduction of Study Group The meeting began with introductions by the participants and a review of the agenda. Singer indicated that Safuat Hamdy had decided to defer his presentation on "IQ Cryptography" (former item 6a) to a future meeting. He asked if any participants wanted to give a presentation in addition to those on the agenda. Victor Shoup offered to give a presentation on the Advanced Cryptographic Engine. Burt Kaliski asked to discuss a registry of public-key algorithms. 2. Establish meeting goals and guidelines Singer reviewed the history of the IEEE P1363 working group, which was started in 1994. In the interest of completion of the IEEE P1363 document, the working group decided several years ago to establish a second project, IEEE P1363a, for material that could not be included in the first document in a timely fashion. Many contributions were received for IEEE P1363a, but not all fit into the model of that document as a supplement of IEEE P1363. The purpose of the study group is to review those contributions and make recommendations to our sponsor, the IEEE Microprocessor Standards Committee, for new standards projects. If those projects are approved, then the working group(s) will begin developing new documents. This meeting is the beginning of the study group discussion, and includes several presentations on the contributions. 3. Review criteria for initiation of an IEEE Standards project Singer presented the four criteria for starting a new project, which are outlined in the study group's charter: 1) There is sufficient interest and availability of resources to carry the project through to completion. In particular, the project needs an editor and interested participants. 2) There is sufficient expertise available to make sound choices of content. This includes the need for strongly supported claims and an unbiased standardization process. 3) There is a perceived value in creating the standard to the cryptographic and commercial world and there exists a lack of other standardization in that area. 4) It is believed that it will be feasible to satisfy IEEE guidelines for approval of the standard. Kravitz asked whether the study group, in considering the proposed project on public-key validation, was covering techniques other than cryptographic schemes, which were the focus of IEEE P1363. Johnson said that public-key validation was omitted from IEEE P1363 and was a useful technique for a new project. Kaliski remarked that public-key validation and key generation are both elements of schemes. Singer said another project the study group might consider is usage guidelines of IEEE P1363. 4. Discuss basic guidelines for scope of a project Singer then reviewed the process for developing IEEE standards. There are three types of documents: * Standard: Documents with mandatory requirements * Recommended practices: Documents in which procedures and positions preferred by the IEEE are presented * Guides: Documents in which alternative approaches to good practice are suggested, but no clear cut recommendations are made. A standard of any of the three types can be full-use or trial-use. A full-use standard is effective for five years; a trial-use standard is effective for not more than two years. IEEE P1363 is a standard, but is also like a guide in the sense that it gives alternative techniques, although there are mandatory elements in the specification of individual techniques. IEEE P1363 will be published as a full-use standard. The IEEE P1363a addendum is expected to be merged into IEEE P1363 when IEEE P1363 is reaffirmed in five years. 5. Begin presentations on potential future projects 5a) Don Johnson - Public-Key Validation Johnson gave a presentation "Public Key Validation: A Piece of the PKI Puzzle", arguing for the importance of public-key validation in cryptographic protocols. There was general discussion about the assurances provided by public-key validation. Kravitz asked why, if a certificate authority could not be trusted in some scenarios to generate valid domain parameters, it should be trusted to validate public keys. Of course, the CA must at least be trusted to issue authentic certificates. Shoup commented that one should place the "least possible" trust in a certificate authority. Johnson stated that multiple entities could do DPV and KPV, as appropriate, so that trust was not needed to be entirely with one entity (such as a CA). Singer asked for clarification on the assurance provided by proof of possession techniques, in particular how the certificate authority knows who the possessor is. Johnson said that proof of possession is normally done during the registration and proof of identity processes. Shoup said that it is important that parties not rely on public-key validation as providing more assurance than appropriate. Perhaps it is better if the certificate authority is only trusted for registration, where relying parties perform the validation and other checks directly. Kravitz stated that in e-commerce, an entity such as a CA should not "touch" an issue unless it is willing to provide full assurance, which public-key validation and proof of possession alone may not provide. (For instance, the techniques do not assure that the key pair was generated from a strong random source.) Johnson responded that some people might feel that partial assurance may be of more value than no assurance at all. Singer asked about how public-key validation would be handled as a standards project. Lieman asked whether the techniques could be included as an addendum to IEEE P1363 for the families in IEEE P1363; Johnson agreed. Roginsky said that a discussion on the role of the certificate authority would be useful in a standard for public-key validation. It could also include techniques for shared generation of key pairs. Johnson agreed and continued that in order to make sense, the standard would need to discuss key pair generation methods and public-key validation of the output. Singer suggested that the group consider these issues and be prepared to discuss a specific project proposal at the next meeting. 5b) Dan Lieman - New Families Lieman gave a blackboard presentation on NTRU as a motivation for a "new families" project. The project would be for new families in general; the project proposal would not specifically mention NTRU. The presentation covered the mathematical specification of NTRU, its computational advantages, and an analysis of security against lattice reduction. He continued with a discussion based on the proposal to consider NTRU/PASS, which addressed the four criteria for starting a new project. Singer mentioned that when a new project is started, it could be handled by a new working group. When the study group proposes a new project, it should have some sense of whether the project would be handled by a new working group or by IEEE P1363. Lieman suggested that the braid-group cryptosystems recently proposed by Arithmetica Inc. might also be appropriate for the "new families" project. Singer asked whether EPOC and ESIGN might also be considered for this project; Okamoto replied that since they are based on integer factorization, they would be more appropriate for IEEE P1363a. Singer asked whether a new family should include the same range of techniques as other families -- key agreement, signature, encryption, public-key validation. The general sense was that although a family may not need to provide all types of technique, all types for a new family should be in the same document. Afternoon session 6. Continue presentations on potential future projects 6a) (removed) 6c) Additional topics (moved up) Victor Shoup - Advanced Cryptographic Engine Shoup gave a presentation on two new cryptographic schemes: ACE Encrypt, bas ed on [Cramer & Shoup, Crypto '98], and ACE Sign, based on [Cramer & Shoup, ACM CCS '99]. Both are provably secure without the "random oracle" model. ACE Encrypt's proof is based on the decisional Diffie-Hellman assumption; a less tight proof is available in the random oracle model under the computational Diffie-Hellman assumption. ACE Sign's proof is based on the strong RSA assumption, but with a small modification a less tight proof is also available under the traditional RSA assumption. A complete specification is publicly available and an implementation should be available soon. IBM has applied for a patent on ACE Encrypt. Burt Kaliski - Registry of Public-Key Algorithms Kaliski introduced an alternative model for the continued development of IEEE P1363, where instead of collecting additional cryptographic techniques into one or more addenda, the techniques would be published as entries in an algorithm registry. Kaliski observed that some P1363 ballotters had commented that the P1363 document fell between two extremes, each of which might be more useful: a small set of "best" techniques and a large set of "good" alternative techniques. Instead, the document is a medium-size set of "good" techniques. There are generally several alternatives for different purposes, but many alternative techniques were not included. One way to document those alternative techniques is in a new standard; another way is as entries of a registry. [Break for 6b) conference call] Kaliski outlined a possible model for the registry and related standards. A main document would describe the overall plan for the registry and define the process for adding entries and maintaining the registry. Additional documents would describe the format of registry entries for various types of technique (primitives, schemes, etc.). The additional documents would give precise definitions of the attributes that may be claimed for techniques, such as security against certain kinds of attack. The working group's role would be to ensure the correctness of registry entries - that claimed attributes hold and that a technique is presented accurately and in a useful way. An entry, when approved by the working group, would then be forwarded for balloting. There was some discussion about whether to specify minimum security requirements for registry entries, since inclusion in the registry implies some working group endorsement. One way to handle this is for the entry to include a working group-approved statement on the rationale for including the entry. Since security attributes will be explicitly stated in the entry, an "insecure" entry will be clearly identified. (Not all entries are expected to have every possible attribute; there will be various tradeoffs.) In Kaliski's proposal, the current P1363 techniques would be entered in the registry, but the P1363 document itself would continue to be maintained until its five-year revision. After then, it could be broken up, and its background material (e.g., number-theoretic algorithms) would be maintained in separate documents. Kaliski expressed willingness to transfer his work on P1363a over to the registry. (However, subsequent discussion questioned the timing of such a transfer - P1363a is scheduled for ballot in April 2001, but the registry will probably take until 2002 to be approved.) 6b) David Jablon - Password-based Authenticated Key Exchange (during 6c) above) David Jablon led a discussion by teleconference of his proposal, along with a number of other contributors, to develop a standard for password-based authenticated key exchange. The discussion generally followed the presentation outline that was distributed. Some additional points: * Singer observed that this is a useful area for standardization, given that these methods are in use, and there are no standards yet. Jablon added that it's also important to consider that there are many places where these methods are not in use, and passwords are at risk. * Singer also asked about how the methods compare to the common practice of supplying a password through a browser over a secure connection, where the server is authenticated by public-key operations and the client is authenticated by password. Jablon pointed out that such protocols rely on the user to verify that the right server has been authenticated. For instance, in a recent prominent case where the Domain Name Service was hacked to redirect users from a company's real Web site to a fake one, the fake site could potentially have presented its own certificate to users, which would have led to a "secure" connection. However, if a user supplied a password without first checking that the right company's name was in the certificate, the user would have been tricked into disclosing the password to the attacker. * Jablon said that key confirmation is not essential to specify in the proposed protocols, since it can be performed by other protocols once the strong secret is obtained. * Jablon said that the password-based protocols assume a three-tier model for security: only the user knows the password; the server knows a one-way function of the password, but not the password; and other parties know neither. The server (or an attacker who compromises the server) is thus able to try a dictionary attack against the user, but cannot directly obtain the password. * Shoup brought up the question of initial registration - the user must first establish the password with the server, and this step may involve protocols with less assurance of security. Jablon said that establishing a temporary password may be one way to get around this. * At Singer's request, Jablon addressed the four criteria for new projects (see above), which appeared to be satisfied. Jablon expressed willingness to serve as editor. Singer asked the participants whether they'd prefer to have the P1363 working group or a new working group responsible for the project; the general consensus was for the P1363 working group to handle it. * For the next meeting, Singer requested that Jablon submit a scope and purpose statement for the new project, as well as a rough outline of the document. 7. Create voting and functioning guidelines for the study group (discussed in section 8) 8. Plan future work of the study group Continuing discussion on the registry approach, Lieman said that if the working group decided on the registry approach, the "new families" document would no longer be needed. He could then assist in developing the registry. Singer said that the group should decide whether to pursue a "new families" document or the registry approach. Lieman said that the "new families" document could be developed as a prototype for the registry. For instance, the attributes of a technique would be stated explicitly along with the specification of the technique (in contrast to IEEE P1363). Singer said that he expected three draft project authorization requests (PARs) for the next meeting: * Jablon - password-based authenticated key exchange * Kaliski - registry * Lieman - new families The drafts should be distributed electronically before the next meeting, and will be subject to possible vote then. The study group will determine voting rules at the next meeting; Singer will check beforehand with the sponsor. An initial suggestion to have similar rules to P1363, such as a 2/3 majority of voters present. There was some discussion about how to ensure that voting is not abused, but the consensus was to let all participants vote. Lieman asked about how to follow up on the key validation and ACE presentations. Singer said he would like to see a more concrete proposal for each, such as a scope and purpose. Proposals for PARs are welcome for the next meeting (which will be in conjunction with the next P1363 meeting, probably in June in the US). 9. Adjourn MOTION 1. Adjourn. (Kravitz, Lieman, PASSED by acclamation)