IEEE P1363 MEETING MINUTES June 29 - July 1, 1998, Bedford, Massachusetts, USA MONDAY, JUNE 29 In attendance: Lily Chen* Don Johnson* Burt Kaliski*, Chair Shirley Kawamoto David Kravitz* Pil Joong Lee* Leo Reyzin* Ari Singer Yiqun Lisa Yin*, Editor Robert Zuccherato* (* means that the participant was qualified to vote) As we had no secretary or treasurer present, Reyzin was appointed the interim secretary and Yin was appointed the interim treasurer. AGENDA Kaliski went over the agenda he had earlier posted to the mailing list: Monday, June 29 -- Morning: Approval of agenda/schedule, officers' reports, review of P1363 body -- Afternoon: Review of P1363 body (cont'd) Tuesday, June 30 -- Morning: Approval of March minutes, review of P1363 annexes -- Afternoon: Review of P1363 annexes (cont'd) Wednesday, July 1 -- Morning: Review of P1363 annexes (cont'd) / open -- Afternoon: Balloting plan; P1363a plan; work assignments; meeting schedule Motion 1. (Kravitz, Yin) Approve the agenda. (Motion approved by acclamation) CHAIR'S REPORT Kaliski reported on the patent issues. He said that many companies had fulfilled their obligations as far as assuring non-discriminatory licensing. The obligation of the working group would be to assure that for every piece of patented technology included, we were justified in doing so. More specifically, according to IEEE, our obligation was to make sure that if we put something in the standard that could not be practiced without a license then (a) it was licensed in a non-discriminatory and reasonable manner; and (b) we were technically justified in including it (e.g., it was superior to unpatented alternatives). One of the questions to consider was whether some technology was encumbered by a patent, or whether just particular implementations (or options) are. He said that these questions would probably come up during the ballot process. Kaliski then reported on P1363a. He had sent out a call for submissions. He had also informed those who had submitted contributions previously that their submissions were appropriate, but it would be helpful if they updated them to the new form. We went over the submissions that were posted on the web site; some of them, most likely, would be presented by their authors at the August meeting after Crypto. Kaliski also noted that all the new submissions that authors submit for inclusion into the standard would have to be public. If included into the Standard, the material would be copyrighted by IEEE. Another item that the working had requested Kaliski to do was to find out about the possibility of standards for random number generation in hardware and/or pseudo-random number generation by algorithms. He had contacted the chair of IEEE MSC and the standards subcommitte chair of the Technical Committee for Security and Privacy, but the conversation hadn't gotten very far as of the date of this meeting. Johnson pointed out that ISO and ANSI were apparently working on this and suggested that we monitor their work and see if we could contribute. Kaliski also reported that he had no new information on the export issues with regard to our standard. EDITOR'S REPORT Yin went over the work that had been underway since the March meeting. There were some changes to the main body: Section 4 (Overview of Techniques) had some new material on conformance; schemes were organized by type (Key Agreement, Signature, Encryption) rather than by family (DL, EC, IF); each primitive and scheme had a conformance region recommendation. There was also a lot of new material for Annexes B, C, D, E (Conformance, Rationale, Security Considerations, Formats). Reyzin reported that there was not much new writing in Annex A (Number-Theoretic Background), but Jerry Solinas was working on the tables. REVIEW OF THE MAIN BODY SECTIONS 1-5 (OVERVIEW INFORMATION AND CONVERSION PRIMITIVES) Editorial suggestions were recorded by Yin and Kaliski, and were not reflected in these minutes. Only suggestions that significantly changed the substance of the document were recorded here. We decided to expand Section 4 (Overview) to give information on what this standard does and does not provide (that it is implementation-focused, rather than security-focused) and give a more thorough overview of the entire document. On Section 5.5 (Data type conversion primitives): make a clearer distinction between normative and informative -- normative is only for conversion within schemes. In particular, we would prune the diagram in 5.5 (to reflect only the normative part used for conversion) and copy it in its entirety into Annex E (to reflect the informative part used for representation of objects as octet strings). MQV AND THE UNKNOWN KEY SHARE ATTACK Kaliski had earlier posted to the mailing list a description of a so-called "unknown key-share" attack on MQV he had uncovered, whereby an adversary Eve could force Bob into thinking he shared a key with Eve while in reality he would be sharing the key with Alice. Kaliski explained that he had uncovered the attack while preparing security notes. The original MQV was resistant to the attack, but the transition that improved the efficiency took away the resistance. However, even the latest paper on MQV (posted on our web site) claimed the resistance. We pointed out that the attack could not be prevented by requiring Eve to prove the knowledge of her static private key; but it could be prevented if her static key pair were derived jointly with the CA (a technique sometimes called "key sterilization"). In light of the new information provided by Kaliski's attack, we discussed whether it was appropriate to continue to support MQV in P1363. The two main options considered were leaving it in and deferring it to P1363a. We also entertained the idea of making technical modifications to it, although after some discussion there was a consensus that last-minute technical changes would be imprudent. Some of the arguments that were made for deferring MQV to P1363a: (a) It's new and immature and it has changed significantly since its birth. (b) Kaliski's attack, while of a limited practical application, because it is potentially preventable by subsequent key confirmation protocol, shows that MQV doesn't quite satisfy its design objectives. The fact that resistance to this attack was still claimed in the latest paper, when the protocol was no longer resistant, highlights MQV's immaturity. (c) The unknown key share attack can be prevented in the -DH1/-DH2 case where a static key-pair is involved by a technique we already recommend -- namely, that a party's possession of the static private key be verified. The same attack against MQV cannot be prevented by this method. To recommend another method of countering the attack would be a significant technical undertaking at such a late stage. (d) MQV is encumbered by patents (Certicom's patent letter indicated that there were patent(s) pending on it; U.S. patent 5,761,305, issued June 2, 1998, listing Vanstone, Menezes and Qu as inventors and Certicom as the assignee, was brought to the working group's attention by Walter Fumy and distributed on Tuesday). On the other hand, some versions of Diffie-Hellman, supported by our -DH1 and -DH2 schemes, using one or two key-pairs, do not have any known applicable patents. (e) Some key pair combinations can produce e = 0 and the identity as the agreed-upon key (and hence no key at all in the EC case); to handle this case in the on-line setting may be inconvenient, and it would be better to resolve this by fixing the algorithm. Some of the arguments that were made for keeping MQV in P1363: (a) Efficiency (2.5 exponentiations for ephemeral key generation and key agreement vs. 3 for the -DH2 scheme). (b) Less reliance on the hash function for producing the first key (because MQV does the mixing of the static and ephemeral keys within itself, rather than rely on the hash function to do it, like -DH2). (c) -DH2 does not provide any particular security properties unless used correctly within a protocol. MQV is not any worse in that respect. (d) -DH2, at least in part, is covered by IBM patents or patents pending; it is better to have an alternative, even if the alternative is also patented. (e) The case of the agreed-upon key being the identity can be easily detected during the protocol. In the EC case, one could pick some pre-agreed value (x, y) to represent the point at infinity. Johnson indicated that more information on MQV would be available from Certicom within the next two days. We decided not to make any decisions, but to revisit the issue of MQV on Wednesday. REVIEW OF THE MAIN BODY SECTIONS 6-8 (DL, EC, IF PRIMITIVES) We continued our review of the main body. We agreed to reword and clarify the conformance region recommendations. We discussed the issue of DSA and the input f (message representative) being bigger than r (prime subgroup order). The document required in the scheme that f and r be the same size (i.e., the size passed to the encoding technique is |r|). But in the primitive it allowed any f, while commenting that there may be security considerations on the size of f. We decided not to put in any other options, and leave everything as is. We also decided to remove the comment on the size of f in the primitive, because our scheme is adequate enough comment on how to use the primitive appropriately. We would also add some security notes in Annex D where we discuss security considerations for the scheme and the encoding method. To prevent the Vaudenay attack, we should emphasize importance of good parameter generation in Annex D. On key validation, we decided to point out that we had no algorithm for IF key validation in the standard. As far as private key validation, we decided not to have any algorithms for it in any of the families, because a party managing its own private key would not need to validate it, most likely. But we decided to mention that private key validation could be performed, if desired. We discussed that IFSP-RSA1 in combination with either of the encoding methods we recommended (for signatures with appendix and with recovery) was not really used by anyone we were aware of, and was not in any other standard. We decided to keep it in, anyway. We decided that every primitive would have a forward pointer to the scheme(s) it was used in. We decided to rename auxiliary functions as follows: KDF-X9.42 to KDF1; EMSA-14888 to EMSA1, etc. TUESDAY, JUNE 30 The same group attended the Tuesday session. APPROVAL OF THE MINUTES OF THE MARCH MEETING We reviewed the minutes of the previous (March) meeting. Some changes were recorded by Yin and Kaliski. Motion 2. (Yin, Zuccherato) Approve the minutes as amended. (Motion approved by acclamation). REVIEW OF ANNEX A (Number-Theoretic Background). We decided to remove the discussion of complexity of discrete log, EC discrete log, and integer factorization problems from Annex A and consolidate them with discussion in Annex D (leaving a pointer to Annex D in Annex A). For EC, we decided to exclude the discussion of supersingular and anomalous curves from Annex A, but point to Annex D whenever these conditions were being checked. Jerry Solinas had simplified the Cunningham tables for Annex A, reducing them down to 20-25 pages by eliminating redundant information. Most people said that 25 pages of the table were too much. We had a discussion of how to provide this information; we decided that these tables really belonged with the Cunningham project, but if we were unable to coordinate with the Cunningham project, we would put the tables onto our web site. We decided to leave Jerry's algorithm for using the Cunningham tables to produce the factorization for 2^m - 1 in the standard. We had a discussion on what subset of the information to include into Annex A (the information provides factorizations of 2^m - 1 and is needed to generate DL parameters for the binary field case). We decided to ask Jerry Solinas and Roger Schlafly to present some suggestions via the discussion mailing list. For curve generation, Johnson requested to modify the method that selects the curve at random and then computed the order, to also allow to select some arbitrary curve satisfying some conditions (e.g. coefficients of a special form) and then compute the order. REVIEW OF ANNEX B (Conformance) There were calls for more concrete examples within the text, and some editorial suggestions. We also decided to add a section that explains the purpose of this Annex, which was to give a common language for claiming conformance; the section would point out that conformance claims could be just that -- claims -- and that we provided no means for verifying such claims. REVIEW OF ANNEX C (Rationale) Lots of suggestions, mainly editorial. We decided to expand the answer on the RSA vs. RW rationale to also include IFSP-RSA1 and IFSP-RSA2. We also decided to add answers to question of why there were no DL/EC encryption schemes or IF key agreement schemes. REVIEW OF ANNEX D (Security Considerations), SECTIONS D.1-D.4 We decided to put in a note about the possibility of key sharing (i.e., two parties purposefully or inadvertently sharing the same private/public key) and the possibility that the CA may want to check that. For Section 4 of the main body, and elsewhere as appropriate, we decided to mention that the standard didn't specify where the keys came from -- they might be generated by the CA, by the user, or jointly. We discussed how the private DL/EC key should be generated. We decided to mention that it might generated not from the whole range, but from a large enough subset of the range; also decided to provide a pointer to the random number generation section (yet to be written). We finished with D.4, and decided to review the remaining section (D.5, Scheme-Specific Considerations) together with the review of schemes on Wednesday. REVIEW OF ANNEX E (Formats) We decided to change ASN.1 recommendations to "may" and list ANSI X9.F1 standards only for the recommendations. We also decided to change the formats to "may" and provide references to the relevant ANSI X9.F1 standards for other output data formats. We also decided to remove the output data format for the key agreement schemes. WEDNESDAY, JULY 1 The same group, plus Alfred Menezes, attended the Wednesday session. Menezes was qualified to vote. REVIEW OF THE REST OF THE MAIN BODY AND ANNEX D.5 We continued the review of the Main Body, going into the sections on schemes. We did it together with security considerations on the schemes. We decided to put, after every scheme, a note on what other standards it might be compatible with (Johnson volunteered to help compile the list). KEY AGREEMENT SCHEMES We decided to change parameter validation within a scheme from "recommended" to "optional." We agreed to remove the recommendation to make key generation parameters fixed-length, but rather just make them prefix-free (pointing out that a simple way to achieve that is to make them fixed-length). We decided to add a section on key confirmation to D.5.1. We had a debate on what properties of key agreement schemes should be discussed in Annex D. In particular, Johnson and Menezes pointed out that if we discussed the unknown key share attack, then we should also discuss other security properties of key agreement schemes in more detail. Reyzin and Kaliski responded that other security properties were also discussed in Annex D. To have further discussion of other properties would be difficult because many were not well defined and it would be hard in the given editorial time frame to come up with a comprehensive discussion of them, especially considering that many were a subject of current research. We agreed that an appropriate way to handle it was to give recommendations on proper use (limited to fairly common uses) and literature references for other possible uses and risks, as we do for other issues in Annex D. We agreed that D.5.1.5 should define the term "small-subgroup attack" to ease the understanding of the differences between -DH and -MQV vs. -DHC and -MQVC primitives. SIGNATURE SCHEMES We decided that a clarification of what the inputs and outputs of schemes with appendix vs. schemes with recovery might be useful. We also decided that, time permitting, we would put a flow chart into each of the scheme sections that would describe the general model. We also agreed to add the discussion of non-repudiation in signature schemes -- in particular, that signatures were unique in that the a dishonest user might be interested in a deliberately weakened key. ENCRYPTION SCHEMES We agreed to add a note to Annex D on encryption and key agreement schemes: it is important, that, in case of error in decryption or key agreement, little information is given as to what the error is (to avoid giving out private information). The same note wasn't needed for signature schemes, because anybody could perform signature verification with a public key. We decided we wouldn't put in a general model describing the steps for encryption schemes (because there was only one scheme), but rather would add a description of inputs/outputs and encoding parameters, together with a flowchart similar to the signature schemes. We had a discussion of what the risks were if the CA didn't validate the possession of the private key before issuing a certificate for the public key in the encryption case. It seemed like a good general practice, but we didn't come up with any specific attacks. REMAINING SECURITY CONSIDERATIONS Random number generation and implementation considerations were yet to be written. For random number generation, we^Òd borrow from previous text by Carl Ellison. For implementation considerations, we wanted to keep it minimal, but to point out that the pieces we gave in the rest of the standard were not the whole picture: there is the physical layer, the network layer, etc., that may all be vulnerable to attacks. MQV TELECONFERENCE We had an hour-long teleconference to revisit the MQV issue. Participating by telephone were: Minghua Qu Bob Reiter Scott Vanstone Ashok Vadekar Qu and Vadekar were qualified to vote. Menezes argued that the unknown key-share attack was not that serious in practice, because every real-life protocol performed key confirmation. He suggested that the correct way to handle the attack in P1363 was to have a security note which would recommend key confirmation should this attack be a concern in practice. While agreeing that the attack itself was not a serious security threat, Kaliski, Reyzin, Yin and Zuccherato argued that its discovery, contrary to the claims of the March 1998 MQV paper, demonstrated that MQV was not mature enough, and needed to be studied more. Reiter (from the NSA) argued that, while MQV may had had a relatively short life, it had been studied intensely. He said that he and Jerry Solinas (who was unable to join the call) both wanted MQV kept in P1363, without any changes. Menezes said that, while MQV was probably not provable, it was not any less well-studied than, for example, our instantiation of OAEP, which used a hash function instead of the random oracles (since OAEP was only proven in the random oracle model). He also pointed out that the unified model for Diffie-Hellman had not been around much longer than MQV; in particular, the EC version of MQV had been the one of the first, if not the first, Diffie-Hellman-type EC protocol to be completely specified. He also said that recently-discovered weaknesses in PKCS #1 or STS (see below) showed that well-studied techniques might also have problems with them. Menezes and Vanstone suggested that if the status of MQV was to be reviewed for security or maturity reasons, then everything else had to be reviewed as well. Kaliski countered that he felt that we, as a working group, had not studied MQV enough before deciding to include it, and that that was possibly our fault. He said that MQV would be better served if it was delayed until the addendum, when a more thorough review would be possible. David Kravitz pointed out that, on the other hand, putting something in the standard would give it more attention. Yin and Reyzin said that, while this might be true, the primary purpose of the standard was to provide interoperability, not to draw attention. We did not come to conclusion, and no motions were put forward. After the teleconference, Menezes provided (privately, to those present at the meeting) a draft of a paper of his and Simon Blake-Wilson's on the vulnerabilities of other key agreement protocols, including STS. BALLOT PROCESS Terry Arnold (Vice-Chair) joined us by telephone for about a half-hour to discuss the ballot process. He told us that the list of people who responded to his ballot call was to small and we had many regulars who had not signed up. He encouraged everyone to sign up and said he would put out another call to the mailing list, with a July 12 deadline for informing him of the intent to be in the ballot group. He also said that we should not worry about IEEE requirements for size or balance, because a lot of people from different companies would most likely sign up. We would provide the MSC with our current draft for their July 13 meeting, and would not need a final draft until about 2 months from then, when the ballot pool would be formed. Kaliski also suggested that we provide a letter explaining our patent rationale and mail that letter out with the draft to the ballot pool. Arnold suggested that we provide the draft of that letter to MSC. Motion 3. (Reyzin, Yin). To request from MSC an authorization to go to ballot at the next MSC meeting, July 13, 1998. (All voting participants were in favor, except for Kaliski, who, as the chair, abstained.) We agreed to try to keep the following schedule for the ballot process. July 10. Deadline for posting the minutes and a list of things to do (or at least circulating them to the meeting participants). Also post the schedule on the main list. July 13. Request MSC an authorization to go to ballot. July 27. Draft incorporating June meeting comments posted (hopefully stand-alone pieces earlier). August 10. Close of comments. August 12. Teleconference, 10 am Pacific Time. August 27-28. Crypto meeting. Thursday -- P1363a presentations. Friday -- P1363a presentations and discussion of the draft. September 11 (or earlier). MSC is done forming the ballot body; final ballot draft due. Late September. Ballot sent out. Late December. Comments and votes due. Early 1999. The ballot resolution process begins. P1363A DISCUSSION We agreed that the August and November meetings would be used as forums for P1363a submissions. At the November meeting we would start planning out in more detail the directions for P1363a to consider. We decided to keep the August meeting open for anyone to present, but to encourage submissions earlier, so that the participants could look at them prior to the presentations. ADMINISTRATIVE MATTERS Yin collected the $60 meeting fee from each participant ($20 from Menezes, who participated for one day only). We decided to collect cash payments as much as possible at the Crypto meeting, in order to simplify the process of paying Crypto and UCSB. Kaliski asked whether we wanted to count those who participated by telephone as meeting participants for purposes of voting eligibility. There were no objections. Motion (Yin, Menezes). Adjourn. (Motion approved by acclamation.) We adjourned at 3:30 p.m.