Aug. '96 IEEE P1363 minutes (corrected on Jan. 25, 1997) IEEE P1363: Standard for RSA, Diffie-Hellman and Related Public-Key Cryptography MEETING NOTICE Thursday, August 22, 1996, 1:00-6:00pm Friday, August 23, 1996, 9:00-6:00pm University of California, Santa Barbara, CA This meeting of the P1363 working group, open to the public, will continue the development of a standard for RSA, discrete logarithm and elliptic curve cryptography. The Thursday afternoon portion will consist of a presentation of the proposed draft standard as developed over the summer based on directions at the May meeting, and the Friday portion will focus on editorial review of the proposed draft leading toward the first formal P1363 draft standard. The meeting follows the CRYPTO '96 conference, held August 18-22 at the same location. The Thursday afternoon portion is intended for those attending CRYPTO '96 who wish to learn more about the P1363 standard; the Friday portion is primarily for the working group members though all are welcome to participate. AGENDA Thursday Afternoon 1. Approval of Agenda 2. Presentation of Proposed Draft Standard Friday 3. Approval of Minutes from May Meeting 4. Officers' Reports 5. Proposals for New Sections 6. Editorial Review of Proposed Draft 7. Meeting Schedule 8. New Work Assignments If you'd like to participate, contact Burt Kaliski, the working group's chair, at RSA Laboratories, 100 Marine Parkway, Redwood City, CA 94065. Phone: (415) 595-7703, FAX: (415) 595-4126, E-mail: burt@rsa.com. Draft sections and copies of previous minutes are available on , which is also accessible through . The working group's electronic mailing list is ; to join, send e-mail to . There will be a meeting fee, though the amount has not yet been established, pending arrangements with the university. It should also be possible for participants to arrange accommodations at the university. Details will be announced as soon as they are available. DIRECTIONS (excerpted from the CRYPTO announcement) The campus is located approximately two miles from the Santa Barbara airport, which is served by several airlines including American, America West, Delta, United, and US Air. All major rental car agencies are also represented in Santa Barbara, and AMTRAK has rail connections from San Francisco to the north and Los Angeles to the south. Santa Barbara is approximately 100 miles (160 km) north of the Los Angeles airport and 350 miles (560 km) south of San Francisco. For more information on the CRYPTO '96 conference, see the conference description on , or send email to . Meeting minutes =============== The meeting began at 1:30 pm in the Formal Lounge of Anacapa Hall, UCSB. In attendance, we had: Francois Bayen *Lily Chen Whitfield Diffie Carl Ellison Ed Eytchison *Walter Fumy Roger Golliver Louis Guillou *Don Johnson *Burt Kaliski, Chair *John Kennedy, Treasurer Xuejia Lai Michael Markowitz *Alfred Menezes Victor Miller Jean-Jacques Quisquater Leo Reyzin Phil Rogaway *Roger Schlafly, Secretary Brian Snow *Jerry Solinas Kazuo Takaragi *Paul Van Oorschot *Michael Wiener *Yiqun Lisa Yin, Editor Yuliang Zheng We also had these observers: Mihir Bellare David Cuccia Ivan Damgard Chris Gorsuch Gary Graunke Alko Meijer Roland Mueller Jim Reeds Claus Schnorr Ray Sidney Brian Snow Leonid Vayner Those marked with an asterisk above were qualified to vote. As before, attendance at one of the previous three meetings is required to vote. Kaliski handed out the agenda. Motion 1. The agenda is approved. Passed, unanimously. We introduced ourselves, and passed around a signup sheet. The RSADSI tag team gave a slide show with a summary of the current draft standard. Copies of the drafts and slides were distributed. Copies of the current draft were also handed out. Yin gave an overview. Yin and others at RSADSI have taken over editing all of the sections, for now. Among other things, she said the patent issues were resolved in Nov. 1995, and we hope to go to ballot in Nov. 1996. Reyzin presented detail on the major public key families, discrete logarithms (DL), elliptic curves (EC), and RSA. He also explained how the functions had been divided into "primitives" and "schemes". Guillou was an ISO 9796 enthusiast who asked several times about differences between our draft and 9796. In particular, he asked why we don't have signature message recovery, Rabin signatures, and 9796 signature formatting. Kaliski explained that we had not been tracking ISO standards, due partly to not having a formal liaison between IEEE and ISO. But supporting the 9796 data format seemed reasonable. He said that we rejected message recovery because we didn't have a good way of doing it securely in the DL case. We thought Rabin signature was a good suggestion. Snow asked about the "extensions" in the Bellare-Rogaway message formatting. He questioned endorsing what could be used as an ordinary cipher when we have no analysis that it is secure for that purpose, and suggested that we stick to public key schemes. Extensions had crept into our draft because key material might be greater that what would fit into an EC message block. We thought the issue could be adequately dealt with by a comment in the security notes, although there was also discussion of removing the extensions. After Yin finished the presentation, we took a break. Kennedy announced the fees as $60 for 1 day, $100 for 2 days. Observers who sneak out before the money is collected are not required to pay. (The fee was later reduced.) Kaliski listed our main open issues: ISO 9796 data format Rabin even exponent message recovery in signatures ASN.1 alternatives char p deg > 1 (p^deg field) ISO 14888 (identity/certs) title of standard use of RSA name ONB v. polynomial basis conformance - generality/specificity point compression (encoding v. parameter setup) Diffie-Hellman - x9.42 alignment "hash" function (HMAC) v. random function control info - AES simpler RSA encryption scheme "extension" / symmetric v. asymmetric techniques RIPEMD-160, other hash functions projective point representation SHA-1 in xxSSA-DSA ? security notes, rationale, app notes We wanted someone to be able to comply with ISO 9796 and P1363. Fumy talked about the field GF(p^k) for p a prime near a power of 2, such as 2^16 - 15. He thought this might be attractive in software for a smart card. Wiener and Schlafly were interested in limiting complexity, and unless somebody really wants to push this option, it is too much for us right now. We revisited the issue of optimal normal bases (ONB) compared to polynomial bases. Solinas volunteered to revise the draft, making the GF(2^n) basis more general. He would make the normative text more general, covering both polynomial and normal bases. This would even allow non-optimal normal bases. He would move most of the trinomial & ONB material to the informative appendix. Cylink and Certicom have still not produced letters regarding licenses for their normal basis patents. There was some argument about whether these patents only covered particular implementations, and whether there were competitive patent-free alternatives. Motion 2. (Solinas) Rewrite sections 3.4.2, 3.5.2-3, and make consequential changes. Passed, unanimously. Fumy wrote a document on polynomial basis examples, but it apparently got lost. He produced another copy, and Yin arranged to have it duplicated. We agreed on the Weierstrass form of an elliptic curve, as we had been using. Kaliski summarized the motivation for moving the point compress bit option to the EC setup parameters, which is outlined in the current draft. This slightly simplifies some data formats. Everyone agreed. Schlafly questioned using the name "RSA" in the standard, and raised two objections to its appropriateness. (1) Trademark. A standard should not use names which are trademarked because it artificially hinders others from complying. A company may wish to mark products as complying with the RSA part of the standard, but doing so will necessarily put it dangerously close to infringing trademarks of RSA Data Security Inc. (2) Endorsement. The term "RSA" is popularly identified with a particular company (RSA Data Security Inc.), so an "RSA" standard would be popularly construed as an endorsement of that company's products. Schlafly noted that we don't use "Certicom", "Cylink", or "IBM" in the draft, even though we have technologies promoted by those companies. Reyzin showed us a slide with claimed RSADSI trademarks. There were several logos and seals with "RSA" in big letters and some additional text. These were: RSA Data Security RSA Laboratories RSA Public Key Cryptosystem Additional trademarks claimed by RSADSI were: RSA Digital Signature RSA Digital Envelope RSA Secure RSA Sign (R) RSA Check (R) RSA Public Key Cryptosystem There were also some marks without "RSA", including: Because some things are better left unread. (R) The keys to privacy and authentication. (R) MD, MD2, RC2, BSAFE, TIPEM, MailSafe, ... Someone commented that other public key standards use "RSA", although someone else said ISO 9796 conspicuously avoids use of the term. Markowitz complained that RSADSI has gone to court to protect the "RSA" mark before, and that he suffers from a judgment prohibiting use of "RSA". Motion 3. (Kennedy, Fumy) Change title to "Standard for Public Key Cryptography". Passed, 6-3. Motion 4. (Schlafly) Change "RSA" to Composite Modulus throughout. Motion died for lack of a second. Ellison argued that use of the "RSA" term predated the RSA company. He also said that avoiding "RSA" would sound like we were trying to be "politically correct". Others argued that "RSA" had entered the popular lexicon. At around 6:00 pm, we adjourned for the day. We started on Friday at 8:50 am. In attendance, *Lily Chen Carl Ellison *Walter Fumy *Don Johnson *Burt Kaliski, Chair *John Kennedy, Treasurer Xuejia Lai Michael Markowitz *Alfred Menezes Leo Reyzin *Roger Schlafly, Secretary *Jerry Solinas *Paul Van Oorschot *Yiqun Lisa Yin, Editor Yin brought copies of ISO 9796-2, as there had been a lot of discussion of it the day before. Kennedy gave a treasurer's report. We have about $2K in the bank, but some money is owed to Kaliski. About $800 was collected at this meeting. He promised a more complete report via email. Kaliski gave the chair's report. The web page stays as is because Kopsa never made any enhancements. We had a couple of teleconferences. Oliver has resigned as editor because of other work commitments. Yin was co-editor, so she is now the sole editor. There is a patent pending on the MQV protocol. Certicom wrote a letter for ANSI, but it does not apply to us. Johnson promised that Certicom will write a letter for us. There was a short discussion on whether to even use MQV. One cited advantage is that there is no small subgroup attack. One alternative is the X9.42 unified model, but Johnson says IBM may have a patent on that. (Johnson recently switched jobs from IBM to Certicom.) Motion 5. (Solinas,Kennedy) Kaliski will attach a cover letter to the standard at an appropriate time listing technologies and asking for patent holders to notify the IEEE of patent coverage and policy. Passed, unanimously. It was suggested that Kaliski send a letter to the P1363 mailing list plus IBM expeditiously asking about patents. We are particularly concerned about Nyberg-Rueppel, Bellare-Rogaway, MQV, and normal bases. (According to Fumy, Nyberg and Rueppel have filed European Patent Application 0639907 in February 95 for 'Digital signature method and key agreement method'.) Motion 6. (Kennedy, Johnson) Kaliski will send letter to mailing list plus identified parties who might reasonably have an interest (eg, IBM), covering major areas of technology to be covered by the draft standard, requesting identification of any patents or patent applications which are relevant. Passed, unanimously. We took a break at 10:00. Yin (editor) and Schlafly (secretary) had nothing special for their officer's reports. Kaliski said he was mistaken about the IEEE meeting tax, so Kennedy overcharged us. Kennedy made refunds. We read the minutes from the last meeting. A few minor typos were found. We decided to give Wiener credit for his telephone attendance. Kaliski said "OAP" should be "OAEP". Motion 7. (Schlafly, Kennedy) The minutes are accepted [with amendments as discussed]. Passed, unanimously. Schlafly will upload the amended minutes. Fumy tried to talk us into a European meeting again. He suggested Munich, 2nd week of Nov. Solinas offered the hospitality of his employer, the agency which runs the National Cryptologic Museum. Markowitz suggested having it in conjunction with the Oct 22-25 NISSC NIST conference in Baltimore, but others wanted a 3-day meeting not cramped by the schedule of another meeting. Motion 8. (Schlafly, Yin) We have the next meeting in Ft. Meade, Nov. 12-14. Passed, unanimously. For a backup date, someone had a conflict the previous week, but the following week seemed to be ok. We didn't schedule any future meetings, but suggestions were EuroCrypt, Germany, and Auburn, Alabama. Menezes said Auburn is driving distance from the Atlanta airport and is pleasant during spring break, the week of Mar. 17. This ended discussions of administrative matters. Kaliski brought up the subject of conformance. What level of conformance do we expect? Will people be able to interoperate? How much is normative, and how much informative? ISO CD 10118-3 has 3 dedicated hash functions: SHA-1, RIPEMD-160, and RIPEMD-128. The earlier ISO 10118-2 had a generalized version of MDC-2. (MDC-2 is an IBM patented DES-based scheme). (Van Oorschot clarified this point afterwards.) Kaliski suggested moving SHA-1 out of our DSA signature scheme, putting it in the hash func section, and specifying generally how hash functions convert bits for signatures. There could be some informative text on converting SHA-1. Some people actually thought implementations should be free to scramble the hash function bits as they please. Reyzin proposed to have normative text showing how auxiliary functions are to order the octet, whether it is defined in terms of bits, bytes, 32-bit words, or whatever. Kaliski asks if we need Nyberg-Rueppel signatures. ISO 14888 covers digital sign with appendix, but not mature enough for us. We left it as an open issue, leaving it in for now. It is easier to kill something later, than to reinstate something. Some patent issues remain to be resolved. (DSA, Schnorr, Rueppel.) We recessed for lunch. Kennedy wanted an MQV terminology change. He wants the private key to be X, the public key to be Y, the shared secret to be Z, and U,V changed to R,T. (Not necessarily capitalized.) Someone asked about the exact meaning of requiring random key generation. Johnson said one of the ANSI committees changed "random" to "statistically unique and unpredictable". Yin wanted to put key pair generation techniques in an informative appendix. Kennedy wanted DLKAS consistent with X9.42. There are 2 kinds of keys -- static and ephemeral. Since the keys might be used in various was, it might give greater flexibility to call them "primary" and secondary". More discussion offline was planned. We revisited the issue of ASN.1 encodings. Kaliski said that the spec was not intended to require ASN.1, but if you build an X.509 certificate, it specifies how public keys are to be coded to put into the X.509 ASN.1 framework. Ellison, our anti-ASN.1 zealot, conceded that "don't quote me, but it is possible to use ASN.1 right" by say, defining structures in C, and then translating to ASN.1. We discussed whether to include DL with characteristic 2. There was not much demand for it, but we get it almost for free because all of the necessary machinery is included for EC in characteristic 2 anyway. Menezes volunteered to add some security notes. Johnson spoke in favor of it. Fumy suggested using projective coordinates in ECDSA. He had a short handout on the subject, and an argument that it might be a computational shortcut for some users. Solinas found a flaw in his scheme which makes it too easy to forge signatures. That was the end of that. (It may still be advantageous for an implementation to use projective coordinates. Perhaps someone will mention this in an implementation note.) We took an afternoon break. We discussed GF(p^k) some more, where p is odd. Most of us felt that there was not a compelling reason to do it. Maybe it will be attractive for smart cards, but we are not sure. So we are putting some flexibility in the spec so that it could be accommodated easily in a future revision of the standard. Yin suggested distinguishing "hash function" from "random function". Sometimes we use a hash function as a fancy pseudo- random number generator, and there might be functions which have this property but which are not necessarily collision-resistant. Even though we aren't supplying both kinds of functions, it seemed like a useful terminological distinction. We deferred consideration of signature message recovery because there was not strong interest among those present. (ISO 9796, and 9796-2 include message recovery.) Kaliski, Yin, Reyzin discussed whether to use simple RSA encryption, or extensions? The extension gives a stream cipher of unknown strength. Maybe we could recommend in the notes that it is good for encrypting random data like keys, and not for data. Johnson suggested using more swizzles, but wouldn't tell us whether or not IBM has a patent pending on multiple swizzles. Motion 9. (Johnson, Yin) Make an appeal to Matyas, Bellare, Rogaway, etc. to help us come up with encryption schemes. Kaliski is the point man, Johnson the technical coordinator. Not passed. Fumy said we should concentrate on well-established techniques, not research. The motion was rephrased. Motion 10. (Johnson, Yin) Form a subcommittee of the working group and other interested parties, chaired by Johnson to study encryption schemes and present findings and recommendations. Passed, unanimously. (Fumy abstained.) Motion 11. (Solinas, Fumy) Support for ISO 9796 even exponent signatures. Passed, unanimously. Reyzin will put it into the draft. Solinas will add material in the appendix on the Jacobi symbol. We revisited the "RSA" name issue. Motion 12. (Yin, Johnson) Rename the 3 families: Discrete Logarithm Problem Elliptic Curve Discrete Logarithm Problem Integer Factorization Problem Passed, 7-1. We discussed the remaining use of "RSA", which is in the names of all of the primitives and schemes in the third family. Someone suggested using "RW" (Rabin-Williams) for the even exponent case. Schlafly reiterated his objections, as still being applicable, since we are allowing implementations of pieces of the standard to be conforming. Motion 13. (Solinas, Fumy) Keep the RSA designators as is, except for "RW" to label the new Rabin stuff. Passed, 4-3. Schlafly noted that the patent issues are not solved. There are several technologies in the draft with patents (issued or pending) for which we have no letter promising a reasonable and nondiscriminatory licensing policy. There are also several cases in the draft were we have considered patented and unpatented technologies as alternatives (EC v. RSA, DSA v. Nyberg-Rueppel, polynomial v. ONB, Diffie-Hellman v. MQV, SHA-1 v. DES-based hash functions, etc.), and there has been no justification given for the extra hassle and expense of the patented alternative. Kaliski suggested changing our draft status from "working draft" to "approved draft", but said we surrender some control to the IEEE when we do that. Solinas and Fumy said to wait until next meeting, so we postponed the change. Kaliski suggested a teleconference schedule. Two calls, 10:00 am Pacific time, with one in late Sept. and one in late Oct. Details to be provided by email. Motion 14. (Menezes, Yin) Adjourn. Passed. Roger Schlafly Secretary