IEEE P1363: Standard for Public-Key Cryptography MEETING MINUTES Tuesday, November 12, 1996, 8:30-5:00pm Wednesday, November 13, 1996, 8:30-5:00pm Thursday, November 14, 1996, 8:30-5:00pm National Security Agency Fort Meade, Maryland In attendance, we had: D. S. Burns *Lily Chen *Walter Fumy David Jablon *Don Johnson *Burt Kaliski, Chair *Michael Markowitz Mohammad Peyravian *Leo Reyzin *Roger Schlafly, Secretary *Jerry Solinas *Michael Wiener *Yiqun Lisa Yin, Editor Those marked with an asterisk above were qualified to vote. As before, attendance at one of the previous three meetings is required to vote. The agenda is to discuss encryption, signature, key agreement, have a tour of the museum, and wrap-up. The following more detailed agenda was circulated to the email list shortly before the meeting. READING RELEVANT TO THE MEETING AS A WHOLE: -- Comments from Drs. Bellare and Rogaway from September 24 (br1.txt) -- Minutes of the September 27 and October 25 Teleconferences (minSept.txt, minOct.txt) -- Minutes of the August Meeting (minAug.txt) -- August draft, available on-line at ftp://stdsbbs.ieee.org/pub/p1363/predrafts/ -- Lisa Yin's status report (November 6) (yin.txt) TUESDAY, November 12, 1996, NSA Colony 6, Ft. Meade, MD READING: -- Comments from Dr. Zheng from September 27 (zheng1.txt) -- Proposal from Dr. Zheng (See message from Lisa Yin from October 17, 1996) (zheng2.ps, zheng2.doc) -- Response from Drs. Bellare and Rogaway (October 23) (br2.txt) -- Response from Dr. Zheng (October 23) (zheng3.txt) ISSUES: -- Ones arising from the above comments. -- Subcommittee report. SCHEDULE: MORNING (9:00-lunch, breakfast at 8:30) -- Welcome -- Approval of Agenda -- Approval of Minutes of August Meeting -- Officers' Reports, including Editorial Progress Report -- Meeting Proposals -- Report of Subcommittee on Encryption Schemes -- Technical Discussion of Encryption Schemes, Encryption Primitives, and Related Auxiliary Functions AFTERNOON (lunch-5:00) -- Technical Discussion of Encryption Schemes, etc. (cont'd) WEDNESDAY, November 13, 1996, Mykotronx, Columbia, MD READING: -- Comments from Dr. Schnorr (September 13) (schnorr.txt) -- Response by Roger Schlafly (September 14) (schlafly.txt) -- The new and improved MQV2 protocols (mqv2.doc, mqv2.ps) -- Message from David Jablon regarding EKEs (November 1) (jablon.txt) ISSUES: 1) Choice of EC and DL Signature schemes. a) Is it clear that DSA should be in the standard? b) Do we want more than one signature scheme? c) If yes, what other signature schemes? Schnorr? Fiat-Shamir? Nyberg-Rueppel? d) Do we care for message recovery? e) For DSA, how should we protect DSA parameters to guard against attacks, such as Vaudenay's? Should we have a parameter checking scheme, as Roger Schlafly suggested in the teleconference? Should we make DSA more general, as suggested by Bellare and Rogaway? 2) Choice of IF Signature schemes. a) Rabin-Williams Signature Scheme and ISO 9796 formatting compliance (see minutes of the October 25 Teleconference). b) Definitions of RSA signature and BR formatting 3) Definitions of EC and DL Key Agreement. a) The general consensus at the September teleconference was that we did not want to include the "protocol" issues as part of key agreement "scheme." So the question is how Diffie-Hellman key agreement scheme should be defined (i.e., whether and how to allow for multiple static/ephemeral) keys). b) What are the advantages/disadvantages of MQV (MQV2) and why do we need it? 4) EC and DL KGP a) Is there a need to not allow 1 and -1 as a private key if it is generated randomly? 5) Encrypted Key Exchange Methods (EKE), including SPEKE SCHEDULE: MORNING (9:00-lunch, breakfast at 8:30) -- Technical Discussion of Signature Schemes, Signature Primitives, and Related Auxiliary Functions AFTERNOON (lunch-5:00) -- Technical Discussion of Key Agreement Schemes, etc. -- New Contributions (incl. SPEKE) THURSDAY, November 14, 1996, NSA Colony 6, Ft. Meade, MD READING: -- Message from Burt Kaliski regarding multiple parts (October 24)(kaliski.txt) ISSUES: -- Splitting the standard into multiple parts -- Deciding on the rationale for various elements of the standard SCHEDULE: TOUR OF NATIONAL CRYPTOLOGIC MUSEUM (9:00-10:30) MORNING (10:30-lunch) -- Miscellanious AFTERNOON (lunch-4:00) -- Group Drafting of Rationale Section -- Project Strategy and Meeting Schedule -- Conclusions Motion 1. (Wiener, Reyzin) Approve the agenda (circulated to email list). Passed, unanimously. Kaliski reported on his patent solicitation letter. Zheng has no patents. Matyas of IBM identified US patent 5,142,578, and said IBM has there more applications pending, some with Johnson. Kaliski requested name change with the IEEE. The Standards Activities Board is reviewing the project, and will give a decision in early Dec. The approval will also give us four more years. Arnold is out of the country. Kennedy took a job at Novell, and resigned as treasurer. Motion 2. (Schlafly, Wiener) Markowitz is treasurer. Passed, unanimously. We had some discussion of future meeting location. Wiener suggested the RSADSI conference (Jan. 28-31) and Eurocrypt (May 11-15). Menezes had suggested Alabama in March. Schlafly suggested Santa Barbara in August. The first day was devoted to encryption. Johnson gave a report on the Bellare-Rogaway new proposal, and Zheng's. Peyravian gave a slide show on encrypting a long block with short-block encryption. He had a handout, which he described. We discussed the relative advantages, such as 3 rounds versus 4. The purpose of these encryption schemes is to encrypt some extra key bits (such as encrypting a 168-bit triple-DES key with 155- bit EC), and to verify plaintext integrity. Solinas distributed copies of the Aug. draft, appendix, and email from Zheng and Bellare-Rogaway related to encryption schemes. We adjourned for lunch. Johnson, Kaliski led discussion of the three encryption approaches, and diagrammed them on the whiteboard. There were the method that Peyravian presented, Zheng's method, and Bellare- Rogaway's revised method (which was similar to Zheng's). IBM may have a patent or a patent pending on 3 rounds (swizzles), but maybe not 2. There is also an IBM patent on use of control vectors. We discussed whether any of these schemes should be normative, or perhaps in a non-normative appendix. Wiener thought that the methods were too new, and more research is needed. Johnson made a motion to put all 3 encryption schemes into the draft body, but it died, for lack of a 2nd. Motion 3. (Yin, Markowitz) Put all 3 techniques into appendix of current draft. (Not voted on.) The idea was that we would reserve an option to put in body or drop it altogether. After some discussion, the motion was tabled without a vote. Johnson wanted to at least make sure that the encryption proposals were available for public scrutiny. Reyzin said that it is already his policy to post all submissions on the IEEE P1363 server for public access. He said he would add a web page to ease others joining in discussion. We adjourned at 5:20 pm. On Wednesday, we met at Mykotronx. In attendance, D. S. Burns *Lily Chen *Carl Ellison *Walter Fumy David Jablon *Don Johnson *Burt Kaliski, Chair *Michael Markowitz, Treasurer Mohammad Peyravian *Leo Reyzin *Roger Schlafly, Secretary *Sherry Shannon *Jerry Solinas *Scott Vanstone *Michael Wiener *Yiqun Lisa Yin, Editor Peyravian showed us some new slides on his proposed encryption scheme. We had asked if he had provable security similar to Bellare-Rogaway, and we wondered about the precise hypotheses. He had called Matyas, his co-author, and Matyas claimed to have a proof. Peyravian presented a couple of slides on the proof. He wanted us to agree to include the scheme in the draft, but we were not convinced. We discussed signature schemes, and the justification for the various choices we have made. There was clear interest in DSA and RSA. However, including Nyberg-Rueppel and Rabin-Williams, but not Schnorr, Guillou-Quisquater, Fiat-Shamir and others called for some explanation. Nyberg-Rueppel has the advantage that it can be used with message recovery, but we don't have a message recovery scheme because we don't have a satisfactory redundancy primitive. Vanstone also pointed out that Nyberg-Rueppel has code-size and time efficiency advantages in certain implementations. Wiener commented that ISO 9796 has a formatting method for a message recovery scheme which is not great, but it has at least withstood attacks and is a standard. Several signature schemes claim to have "provable security". However, several people thought that the practical significance of such proofs is a research area, and such schemes are not necessarily superior for our purposes. Choosing a data formatting method remained an unresolved problem. It seems likely that we could find a satisfactory method based on Zheng's, Bellare-Rogaway, or IBM swizzles, but we thought the matter needs more research. Motion 4. (Schlafly, Markowitz) Remand the encryption data formatting issue to the subcommittee for further analysis. Passed, unanimously. We took another long lunch. The minutes from the previous meeting were circulated and reviewed. Minor inaccuracies corrected: (1) An asterisk indicating voting privileges should have been present for Fumy and Van Oorschot both days; (2) a reference to a Johnson objection to the previous minutes was indefinite, and should be deleted; and (3) the statement about rejecting message recovery was misleading. It would have been better to say, "We deferred consideration of signature message recovery because there was not strong interest among those present." Motion 5. (Wiener, Fumy) Adopt the minutes, with the suggested corrections. Passed, unanimously. Jablon gave a paper and presentation on password key exchange. These are variants of Diffie-Hellman key exchange, but where the two communicating parties have a prearranged secret password. He calls his scheme SPEKE, and regards it as a simplified variant of DH-EKE. Both schemes appear to be patented. He suggested that we consider adopting one of these schemes, or at least making allowances for them so that they can be built on top of standardized primitives or schemes. Kaliski questioned whether SPEKE was really a public key scheme, and properly within our scope. Wiener argued that it was fair game as an authenticated key exchange, but otherwise did not appear particularly enthusiastic about it. Our new treasurer (Markowitz) collected money. The meeting fees were $32, 20, and 32, for Tues., Wed., and Thurs. We discussed various key agreement issues: Diffie-Hellman definition and model, MQV and MQV2 (an enhancement of MQV), SPEKE, possible IF-based schemes, and whether +1 and -1 should be allowed as private keys. Reyzin made a motion to adopt a Diffie-Hellman model with all 9 flavors of ephemeral and static values to generate a key. Wiener thinks that having 9 flavors is unreasonable. Reyzin pointed out that there is discussion of many flavors already in the spec. It seemed possible that appropriate language might pacify everyone. After realizing that the dicussion is already there and simply needs to be edited to >remove some errors, Reyzin withdrew his motion and promised to use his editorial discretion to compromise. We revisited the issue of whether the DL or EC private key should be in the range [1,...,n-1] or [2,...,n-2]. Wiener thought it was silly to have to test for the narrower range because the end cases will never happen. Johnson thought it was silly to allow keys which we know to be insecure. We debated the triviality of the test versus the triviality of the insecurity exposure. Some thought the whole discussion was silly. Motion 6. (Schlafly, Yin) Change the private key range back to [1,...,n-1]. Passed, 9-2-2. Solinas had a handout on some MQV fixes. Johnson had a handout on a small subgroup attack. Kaliski drew chart of "firm" schemes to be included in the body of the draft, and "semi-firm" items for appendix or version 2. We have no key agreement scheme in the IF case. We considered the possibility of adding one. We adjourned for the day. Thursday morning we had a tour of the National Cryptologic Museum at the NSA. No one suggested standardizing on World War II cipher machines. We started our meeting in the Colony 7 conference room at 10:55 am. Kaliski discussed dates for the next meeting. The choices were Alabama in March, at the RSADSI conference in January (28-31), and in San Diego in the second week of Feb. Kaliski reported on responses to his patent solicitation. Hugh Williams said that there is no patent on Rabin-Williams signatures, to his knowledge. Hitachi said it has US patents 4,982,429 and 5,103,479 covering SHA-1, and a Japanese patent pending. This was a surprise to all. We discussed rationale. Kaliski recorded responses to a number of questions regarding our decisions. He will insert them into our draft. Kaliski said he was shying away from using initials for people's names in the draft. Among other reasons, there is some dispute as to who should properly get the credit in some cases, and we have no desire for any more controversy than we have already. Wiener questioned using DL with characteristic 2. An attacker can precompute a table for each field size, and he considers this a serious security drawback. Menezes is supposed to be writing some text on the security considerations. The matter is deferred until the next meeting. We discussed the next meeting, as well as another meeting after Eurocrypt, May 15-16. We had another leisurely lunch. Menezes called to offer Auburn University anytime in the second half of March 1997. Kaliski suggests Mar. 12-14, 24-26, to avoid Fumy's conflict. The final decision was for the meeting to take place on March 24-26 at Auburn University. Kaliski proposed dividing our subject matter into two sections, and drew a chart with "version 1" and "version 2". The idea was to put the material we can quickly reach closure on into the draft standard, and defer the rest to a next version. Otherwise, settling on specific technologies is likely to significantly delay our standard. The version 2 items are signature with message recovery (DL and EC cases), key agreement in IF case, long block encryption, signature formatting like Bellare-Rogaway '96 or something equivalent, and SPEKE or something equivalent. Johnson wanted some comments on the deferred material in version 1 with references to version 2 work in progress. This seemed acceptable as long as it was carefully limited, and did not imply endorsement of schemes that we have not yet fully considered. Motion 7. (Solinas, Yin) We adopt this chart as our current plan of action. Passed, unanimously. Motion 8. (Kaliski, Reyzin) We ask Kaliski to approach IEEE to approve a version 2 work. Passed, unanimously. The treasurer, Markowitz, reported that he collected $1048, paid $270 for refreshments, owes IEEE $760, leaving a surplus of $18. These figures will change slightly after money is collected from one other attendee. Motion 9. ([name not recorded], Yin) Adjourn. Passed, unanimously. Roger Schlafly Secretary