IEEE P1363 Study Group for Future Public-Key Cryptography Standards Wednesday, May 31, 2000 Sheraton Dalton St, Boston, MA MINUTES In attendance: Ari Singer, Pitney Bowes (chair) Don Johnson, Certicom (P1363 vice chair) Dan Lieman, NTRU (P1363 treasurer and host) William Whyte, Baltimore (P1363 secretary) Dan Bailey, WPI Dan Brown, Certicom Lucien Dancanet, Citigroup David Jablon, Integrity Sciences Gurgen Khachatryan, Cylink Burt Kaliski, RSA Security Wenbo Mao, Hewlett-Packard Preda Mihailescu, ETH & MEC Consulting (afternoon only) Satomi Okazaki, NTT MCL Leo Reyzin, MIT Allen Roginsky, IBM Bob Silverman, RSA Security Dave Stern, Intel All attendees of this meeting are considered to be full voting members of the study group. Handouts: Distributed by the chair: Agenda Draft PAR for P1363-PB-AKE Untitled Draft PAR for New Families project Short Certification of Secure RSA modulus (Mao) Registry of Public-Key Cryptographic Techniques (Kaliski) Minutes of Study Group meeting, March 15th, 2000. (unapproved) The XTR public key system, (Lenstra & Verheul) Distributed by Don Johnson (Certicom): Draft PAR for Public Key Validation Distributed by Dan Brown (Certicom): "An Algorithm For Evaluation Of Discrete Logarithms in Some Nonprime Finite Fields" (Semaev) Morning session Introduction of study group --------------------------- Singer reviewed the history of the Working Group to date, and the reasons for the existence of the study group. The P1363 document covered three main families of PK algorithms: Integer Factorization (IF), Discrete Log (DL), and Elliptic Curve Discrete Log (ECDL). These were the most well-understood & best PK techniques available at the time. The group moved some techniques to the addendum document P1363a for reasons of timeliness in getting the standard published. P1363a has now been underway for just over two years, and the contents have finally been fixed. The process of producing the document suffers from the same problem as the original 1363: too much material and a need to simply get the standard published. Also, the group became aware of topics which were outside the original scope but arguably relevant to the aims of 1363 -- eg strong password-based techniques, public key validation, usage guidelines. So the working group formed the study group to: * examine suggested projects * for deserving projects, try to put together a Project Authorization Request (PAR) to submit to our sponsors in the Microprocessor Standards Committee. The lifetime of study group is six months, but this can be extended at the discretion of our sponsors (Don Wright is our main contact on the Microprocessor Standards Committee). In the light of this, we need to consider our approach to PARs: would we like to have a fairly aggressive schedule for submitting PARs, or should we be limiting the PARs we submit in the interests of getting them right? The four criteria a project should fulfill before being the subject of a PAR were detailed in the study group's previous meeting. (See "Matters arising" for further discussion of these criteria.) We haven't yet determined what happens when a PAR is approved: whether 1363 takes over the PAR, or whether new groups are formed. The sponsors originally suggested several small WGs, probably with overlapping memberships. Now they're leaning towards a single WG. They will probably accept guidance from the WG. Minutes ------- Some amendments were proposed. Motion: adopt minutes: Proposed Reyzin; seconded Stern; passed unanimously. Matters arising: Kaliski wondered if officers of the study group were officers of the working group. Singer said that they were, and the study group was subsidiary to the working group. Singer reviewed the four criteria for initiation of an IEEE standards project. A project that satisfied these requirements and went through IEEE process would be passed on to the sponsor for formation of WG. 1. SG wanted, before approving a PAR, to believe that there were enough people interested to make the eventual issuance of a standard likely. 2. SG wants to ensure sufficient variety of input to provide an unbiased output. 3. SG wants to ensure there's a need for the standard. 4. SG wants to believe that the IEEE guidelines can be followed. A PAR needs the following: - date - project title - proposed chair - sponsoring body - whether or not it's an update to an existing standard. Password Based Authenticated Key Exchange ----------------------------------------- Jablon presented on the P1363-PB-AKE draft PAR. First, he reviewed the history of PB-AKE. The techniques have been around since early 90s. There are two basic categories: (1) the two parties share the same secret and derive one or more shared symmetric keys ("symmetric trust model"); (2) one side knows only a password verifier, which is a one-way function of the password ("asymmetric trust model"). (note that the verifier is brute-forceable because the password is assumed to be low entropy). It's only recently that asymmetric techniques have been developed which aren't straightforward extensions of existing symmetric models. The "asymmetric trust model" is also referred to as "extended EKE". Issues to be considered in the PAR include: (1) Naming issue -- do we use generic names or attribute schemes to the inventors? There is no existing convention for PB-AKE methods. (2) Is there a rationale for multiple methods that do essentially the same thing? If not, how do we decide what techniques to include and what to exclude? (3) A working group on this topic could provide a forum for reviewing correctness. There is a need for review, particularly in this area. We opened up the discussion. There was some discussion of whether the techniques belonged in the 1363 group. Jablon referred to recent research showing that PB-AKE requires public key cryptography to make it work. If this is the case, it falls within the general ambit of 1363. Also, if it makes public-key systems easier to deploy, it adds value and is worth studying. Singer pointed out that we shouldn't have tunnel vision about what the group is for. We discussed whether or not the PB-AKE document should specify good practice. Singer said that this is a general policy matter which the Study Group and Working Group will have to address independently of the specific PB-AKE proposal. There is an implied good practice statement in the fact that a technique has been chosen for inclusion in the document at all. However, the group has leaned towards a descriptive approach because it's very hard to give a rationale for why you choose what you choose. The rationale for choices is in the 1363 document, but slightly submerged. Dancanet wondered if the study group was going to investigate techniques for protecting the private key. Singer said that it would be worth our while looking into techniques of that sort, and seeing what has been standardized to date. This can be discussed at meetings or on the mailing list; then a person who is sufficiently motivated can put together a white paper giving motivation for a PAR. Jablon gave out a chart of evolution of strong password methods, and described them on whiteboard. He considers it very important to establish the difference between the symmetric and asymmetric trust models up front. He also considers that the group can play a useful role in standardising the language we use to talk about different PB-AKE techniques. "Extended methods" is his old term for asymmetric methods; in general, there isn't a standard terminology. He also noted that in choosing the wording, we don't want to put a ceiling on the entropy of the password, and that encrypting public keys directly with password can leak information which will rule out a password candidate. Bailey asked if asymmetric techniques include techniques like SAKA. Jablon said that SAKA seems to be symmetric. There was some discussion of what the aim of this discussion would be. Singer would like to produce an outline. This shouldn't be restrictive, but would help us to understand the magnitude of the proposed project. He accepted that we are unlikely to get a PAR at this meeting, but would like the WG to gain an understanding of PB-AKE techniques and of the PAR submission process. Jablon read the scope document and we discussed it. Reyzin pointed out that the techniques described aren't really primitives or schemes, they're protocols. Whyte suggested that in the second sentence we change "primitives and schemes" to "techniques". (agreed). Kaliski questioned the used of the phrase "authenticating electronic transactions". Singer pointed out that the password is not necessarily low-entropy, but is used as if it were low entropy. We discussed alternatives: "low grade" is judgemental. "Low variability"? "Drawn from a small set"? "Potentially weak"? Eventually we agreed to change the second sentence of the scope to: Specifications of techniques designed to safely utilise passwords and other low-grade secrets as a basis for secure communications. and to swap it and the first sentence. We took a break for coffee, and agreed to revisit the discussion later. P1363 Registry of Public-Key Techniques: ---------------------------------------- Kaliski spoke on the strawman proposal. The aim is to reduce the complexity of managing future standards work. Kaliski illustrated this with an extended metaphor about private and public transport, replacing the previously favoured "bucket" imagery. IEEE standards are documents plus addendum documents; the intention is that as the standard document comes up for reaffirmation, the addenda are folded into it. So far we have: P1363: established 1993, approved 2000. P1363a: established 1997, hopefully approved 2002. The numbering sequence is 1363a ... 1363z, 1363aa, 1363ab, .... Each of these documents may contain more than one technique, so the standardization of one technique might be held up by problems with another technique that just happens to be in the same document. The registry idea is intended to address this. Each individual technique would have a document of its own. The Working Group can also add value with additional documents which compare between techniques in the registry. There are some examples in IEEE of a simple registry, such as for organization unique IDs, but no close precedent for this idea. However, Singer said that Don Wright, the chair of our sponsoring group, supports the concept. We need to map out the route from the initial idea to an entry in the registry. * Submit (requires submission process -- already existing). Can develop a standard for submissions. * Evaluation. If you've fulfilled the submission requirements the working group is obliged to put a certain amount of effort into evaluating the submission and determining its suitability for inclusion in the registry. * Ballot. This needs to be determined in conjunction with IEEE. * Maintenance process. The registry would contain techniques. Don Wright thinks it might be possible for documents to be entered into the registry without having to go through the ballot process. It would also be possible for them to be deprecated to historical status by working group action. Supporting documents, such as comparisons of techniques and usage guidelines, would be ballotted as normal. Singer noted that the registry concept requires a commitment on the part of the working group not merely to produce the standard but to maintain it. He wondered if the working group would support the extra effort involved. Johnson expressed concern about what a vendor can claim to be compliant to, given that techniques can be removed from the registry. We agreed that a clear naming and numbering scheme for techniques would be useful. Johnson expressed concern about who would be responsible for spotting interactions between techniques. We broke for lunch and agreed to revisit the subject of the registry at the end of the day. New Families: ------------- Lieman presented on a PAR for a document to cover new families of public key algorithms. This document would include more rationale than the main 1363 document, as techniques would have to justify their inclusion more vigorously. Its value would be in covering techniques which displayed a clear benefit and could be expected to be deployed very fast. There was some discussion of how this project would interact with the registry project. Lieman and Reyzin felt that it would be quicker to produce a new families document than to start up the registry and put the new families techniques into it. Singer observed that there is a trade-off between the synergy you get from discussing all the techniques in a single document, and the efficiency you get from the registry approach. The long-term aim is to move all techniques into the registry. Kaliski sees the benefit of the registry as coming from having an agreed standard for what has to be described about a scheme that is proposed for inclusion. Whyte wondered if existing techniques would have to be retrofitted to conform with this standard if it changed. Singer suggested that a "special considerations" field could hold additional information about a technique. Kaliski suggested a guidance document as part of the registry project. Kaliski suggested limiting the new families document to lattice-based techniques only. There was general agreement. Public-Key Validation: ---------------------- Johnson distributed the draft PAR for a Public Key Validation document, and an outline draft of the document itself. The document itself concentrates on RSA/RW key validation techniques, because the discrete log/ECDL cases are better understood. It distinguishes between validation tests which only require the public key and validation tests which require oracle access to the private key. The PAR states that users should not use a public key unless they can validate the key, or the scheme can cope with the use of bad keys. Otherwise an attacker might be able to decrypt messages or forge signatures. There was vigorous discussion of whether the proposed techniques added value. Johnson said that they gave increased assurance that you'd avoided errors in generation and transmission, and increased the chance that a key that proved to be weak had been deliberately chosen to be weak. They can also provide reassurance if you have been given a key, rather than generating it yourself. Singer and Reyzin expressed the opinion that the group should not be designing sophisticated crypto algorithms to catch a programming bug. Mao wondered about the applicability of the techniques to the case where, for example, two people co-generate an RSA key and only one of them ends up knowing the factorization. Singer felt that secure key generation was a different issue from validating an existing key. Roginsky and Silverman queried the statement in the draft outline document that dividing by all the test primes guarantees primality with a failure probability of 2^-100. The probability of failure is nearer 4%. Singer wondered whether this was an issue similar to keysize, which 1363 doesn't specify. Johnson pointed out that 1363 gives guidance on keysize. XTR: ---- Lieman presented on Lenstra and Verheul's paper on ECSTR, pronounced "X-T-R". The XTR authors claim that the technique combines the benefits of both ECC and RSA. It provides a basic technique which can be used in the same way as discrete log and ECDL problems. Comparison of sizes of (key + all other parameters you need to know) and (key on its own), for equivalent security levels, taken from the Lenstra and Verheul paper: RSA-1024: 1050 XTR: 680 (340) ECC: 766 (171). Timing: Keygen: RSA 1223 ms, XTR 73. Encryption/Decryption: RSA 5 ms / 40 ms; XTR 23 ms / 11 ms. Lieman will post the slides on the website. We opened the topic up for discussion. Brown had circulated a paper by Semaev which generalizes the function field sieve. It shows that if first n, then p, go to infinity, and if p is a polynomial in n, then the difficulty of breaking the discrete log problem goes asymptotically as p, not p^n. Brown observed that the XTR system falls if an attacker can take discrete logs in p^6. Silverman observed that if p has small Hamming weight the system might be vulnerable to the special number field sieve. Final summing up: ----------------- Singer revisited the day's discussions and reviewed the open questions. PB-AKE: Will this be one scheme? Multiple schemes? New primitives (such as Password-based encryption)? There are two questions: (1) PAR needs to be appropriately wordsmithed for presentation to IEEE; (2) We need to understand ourselves what we're trying to do. Johnson's presentation on PKV is a good model for what we want PARs to look like. Johnson was concerned that the scope given might be too open-ended. Singer raised again the issue Reyzin had brought up: these techniques are much nearer the protocol level, and much further away from the primitive/scheme level, than anything P1363 has dealt with before. A PAR should be able to identify primitives, schemes and protocols, and have an idea of whether primitives would be reused from the original P1363 document. We agreed that Jablon should write up a strawman outline document as soon as possible, and that Singer should set up a teleconference for when the document was ready. Kaliski reminded us that the proposal will need to be presented to the sponsor as well as to the study group. Registry: Singer identified two documents that need to be written in order to start the registry process: - the process for submissions; - the format for submissions. This might include subsections for each of the different schemes. Stern and Lieman suggested that a graduate student might be interested in helping to format documents correctly. Singer was reluctant for the group to take on a paid employee. Dancanet wondered what level of evaluation of techniques we would be considering for registry entries, and whether there would be liability issues if someone used a technique thinking that it had been wholly endorsed by the working group. Kaliski didn't consider that there was substantial evaluation in the 1363 document; the approach instead was to present a wide range of research results. Singer will put together strawman versions of the two documents for the August meeting. New Families: Lieman was interested in the possibility of the working group, rather than the study group, drawing up the PAR for P1363b. Kaliski pointed out that it would be similar to the P1363a PAR. He also pointed out that this would be the second addendum document, which is our limit in two years. Lieman and Kaliski felt that XTR was appropriate for 1363b, and that 1363.1 should be restricted to lattice-based systems. Lieman will put together a strawman outline for 1363.1. Singer will try to schedule a teleconference in July if this would be helpful. Public Key Validation: Singer stated that he would like to see a clearer statement of the claimed benefits of PKV. Jablon felt that having a specific PKV document would be strange, because it would spread information about techniques from one family across two documents. Singer proposed that, if the Working Group decides to include PKV techniques, it can put the PKV techniques for the families described in 1363 into 1363b, and include PKV techniques for families in 1363.1 in 1363.1. Bailey asked if a rationale for PKV was given in the relevant ANSI standards. Johnson said that it was. Summary: Singer summarized the potential documents: 1363b: PKV, XTR, other additional techniques 1363.1: NTRU, other lattice-based technqiues. 1363.2: PB-AKE 1363.3: registry documents. Kaliski observed that having multiple documents would have many of the benefits of the registry approach, in that different techiques could be balloted separately. Kaliski wondered if we could proceed to a PAR in July. Singer said that all attendees at either of the two study group meetings would have e-voting rights. Move to adjourn: Proposed Johnson, seconded Jablon. Passed by acclamation.