IEEE P1363 Meeting Minutes ========================== March 3 -- 5, 1998 Siemens, Boca Raton, Florida, USA Agenda ====== 1. Approval of agenda -- discussion of schedule for three days of meeting 2. Approval of minutes from previous meetings 3. Officers' reports -- including update from chair on patent issues 4. Review of work performed since November and further development of annexes to standard -- main body (a) review changes made related to conformance (b) newly introduced primitive DLSVDP-DHC (c) proposed reorganization -- annex A: number-theoretic background (a) review updates and merging of family overviews -- annex B: conformance (a) discuss and finalize conformance definitions -- annex D: security considerations (a) discuss the overall structure (b) identify issues that are not covered -- other annexes (rationale, test vectors, random number generation, ASN.1 syntax) 5. Other technical issues -- point compression -- methods for elliptic curve generation -- alignment with other standards 6. New work assignments -- remaining work on Annexes -- preparation for the balloting process 7. Meeting schedule -- determine the schedule for the June meeting and the meeting after Crypto 8. P1363a launch Tuesday, March 3, 1998 Meeting started at 9:20 am. Attendees: Benjamin Arazi *Ian Blake *Lily Chen *Walter Fumy *Don Johnson *Burt Kaliski, Chair *David Kravitz *Michael Markowitz, Treasurer Aram Perez Anand Rajan *Jerry Solinas *Yiqun Lisa Yin, Editor *Robert Zuccherato (Voting members are marked with * above.) Kaliski reviewed the agenda for the meeting. Motion 1. (Solinas, Yin) Approve the agenda. Since the secretary Roger Schlafly was not present, Yin volunteered to take notes for the meeting. Kaliski had two topics to report as the working group chair. The first report was on IEEE related issues. The two PARs were approved by IEEE NesCom (New Standards Committee) in December. According to our mentor at IEEE NesCom, there was some misunderstanding within NesCom about the P1363 effort. So we need to let IEEE know more about our work to make sure that our balloting process will be a smooth one. Kaliski mentioned that P1363 is now formally coordinating with ANSI and several other committees. Kaliski's second report was on patent issues related to P1363. He handed out a copy of all the letters he has received so far: -- Yuliang Zheng. Authenticated encryption. -- Phil Deck (Certicom). MQV and point compression. Yin pointed out that it might be better for people to give the application number or patent number so that there is no ambiguity. Kaliski agreed to follow up on this issue. -- Claus Schnorr. He claimed that his patent covers DSA. The letter is not acceptable as a letter of assurance since Schnorr has granted the exclusive licensing right to RSA. Fumy pointed out that the licensing is not exclusive, and that Schnorr also licensed the patent to Siemens. Kaliski agreed to follow up on this. -- Mike Matyas (IBM). The "swizzle" method and unified Diffie-Hellman. The letter also lists other patents that might be related to certain uses of the standard. -- Rainer Rueppel (R3). Nyberg-Rueppel signature scheme. -- Hugh Williams. He said in the letter that he has no patents on the RW scheme. Some people raised the question whether Rabin has a patent on RW. Kaliski said that he will follow up on this issue. -- Kazuo Takaragi (Hitachi). Hitachi claimed a patent covering SHA-1. -- Jennifer Seberry (University of New South Wales). She raised copyright issues in her letter, but it is not clear that this is a problem. -- Mihir Bellare and Phil Rogaway (University of California). They have no patents on OAEP, DLES, and ELAES. UC has filed for a patent on PSS. -- Roger Schlafly. He has three patents on certain implementation methods. -- Patent solicitations and a summary from Kaliski. Johnson pointed out that there should be letters from RSA and Cylink. Kaliski mentioned that both companies submitted the letters to IEEE through P1363, but they somehow got lost. Kaliski summarized the patent issues according to the primitives and schemes that are specified in the latest draft (version D1a) of P1363. (Note that the summary does not reflect a definitive position of the working group; mention of an inventor or company merely indicates that it has come into discussion at some point. Mention that there are no patents means that none have been raised as particular issues for a given technique, beyond others that may be associated with other techniques.) Primitives ========= DL/ECSVDP-DH Cylink (expired) -DHC -MQV Certicom DLECSP/VP-DSA Schnorr (no assurance); NIST; Micali -NR R3 IFEP/DP-RSA RSADSI SP/VP-RSA RSADSI -RW Schemes ======= DL/ECKAS-DH1 -DH2 IBM (on unified model); Goss; Sun -MQV DL/ECSSA IFES IBM (on control vectors) IFSSA IFSSR Others ====== SHA1 Hitachi point compression Certicom Addendum ======== DL/ECES, DL/ECAES none (BR) EME-"swizzle" IBM ZS authenticated encryption none (copyright??) SPEKE (Jablon) none SRP (Wu) Stanford (no assurance) PSS/PSS-R UC (no assurance) Kaliski encouraged people to become members of IEEE so that they can later join the balloting pool. He also mentioned the IEEE Standards Association, which he joined recently. Kaliski drew a table for the three-day schedule. Tue. afternoon: security considerations Wed. morning: approve minutes; security considerations afternoon: other annexes and technical issues Thu. morning: open afternoon: next steps Kaliski started reviewing the latest work on conformance. The work still follows what we agreed in the previous meetings. The major change is the following: Most of the material is now in the main body, and Annex B on Conformance is just an index to relevant sections in the main body for each primitive and scheme. The primary reason for this change is that conformance turns out to be sufficiently dependent on particular details of individual primitives and schemes, and therefore it is difficult to define outside the main body. (Our initial approach was to put everything about conformance in the annex.) Review of Annex B. Conformance regions for primitives are mostly simply based on the private key (or the the public key for verification primitives). Johnson asked why there is no conformance for key generation. Solinas and Yin said that there are informative descriptions for key generation in Annex A, but nothing normative in the main body in the current draft. Kaliski said that we should add conformance with keys and parameters, but perhaps not primitives for generating keys and parameters. Review of related sections in the main body. -- Section 4.1 clearly distinguishes "specification" and "implementation" of a primitive. It also defines the behavioral requirements for an implementation of a primitive. Johnson said that according to the definition in Section 4.1, a conformant implementation can output a private key and hence be insecure. A note will be added to address this problem. Also, if key generation is not specified, then requirement 2 cannot be satisfied. (Requirement 2 says that "On all supported inputs, the implementation shall perform steps identical to or equivalent to those specified for the primitive.") Kravitz said that specifying key generation itself may not be enough, and there might be other things that we need to specify, such as key storage. So we need to draw a border line somewhere on what should be specified. -- Section 4.2 deals with similar issues for schemes. Kravitz asked whether which key is static or ephemeral should be part of the "parameters" for a key agreement scheme. Kaliski said that it is not, since it is about the usage of keys and hence belongs to key management considerations. People realized that there are security issues and interoperability issues related to this problem. Johnson said that an implementation claiming conformance should document the risk of operating on inputs that are not supported. -- Sections 6.1.2 and 6.1.3. Slight changes in definitions of parameters and keys: they can be valid or invalid. Markowitz pointed out there were no inputs for some of the conversion primitives and wondered if we want to consider conformance issues for these primitives. . Kravitz said that according to the current definition of a public key, there may not be a corresponding private key. Kaliski explained that the term "public key" is now more like a variable name. In the afternoon, Kaliski continued the review on conformance. Perez asked whether there is definition of conformance (the term itself) and why we need conformance. Kaliski said the need for conformance would be addressed in the annex for rationale. Arazi had some questions on the definition for DL parameters. He felt that the definition is not broad enough to cover the situation in which parameters are secret. -- Section 6.2.1. Johnson suggested that parameters be the first one in the list of inputs. Kravitz raised the issue that the attacker might submit an invalid public key and the primitive does not check for validity. Solinas said that we cannot require the attacker to submit valid inputs. Kaliski explained an implementation would assume the risk (as it is defined in Section 4.2) in this case. Kravitz said that sometimes we want to put restrictions on public keys. For example, an identity-based scheme will assume that the public key has certain form. Such public keys are excluded in the current draft. -- Section 8.1. Establishing parameters is now part of the key agreement operations rather than part of setup ("parameterized"). Johnson asked why we draw a line here. It seems that the parties can agree on parameters before selecting a secret value derivation primitive. Johnson drew a diagram to explain his thoughts on the flow of the DL/ECKAS scheme: DPG (domain parameter generation) -> DPV (domain parameter validation) -> KPG (key pair generation) -> PKV (public key validation) -> DH Kaliski concluded the conformance review and said that that we need to think more to decide how things should be presented. Kaliski moved on to the issues of possible reorganization of the main body. As it stands now, there are many cross references, especially in notes. Kaliski reviewed the new primitive DLSVDP-DHC. The rationale for the change is to separate the descriptions for the primitive that does co-factor multiplication from the primitive that does not. In addition, DLSVDP-DHC is compatible with the original DLSVDP-DH primitive. Johnson said that it might be good to have a third primitive which does co-factor multiplication and is not compatible with DLSVDP-DH. He said that there may be good security reason for this, since we may want to distinguish the situation whether cofactor is involved or not. Markowitz said that another reason is perhaps that there might already be implementations for the third primitive that Johnson hoped to put in. Kaliski said that instead of having three DLSVDPs, we can make DLSVDP-DHC as the recommended implementation for DLSVDP-DH. Solinas pointed out that r^2 should not divide q-1; otherwise, DHC would not work. There were discussion whether this condition should be required for all DL parameters. For EC parameters, this condition is already added in Annex A. Kaliski proposed to leave this issue off-line. Johnson wanted to put the third primitive (which he mentioned above) back in the draft. Yin pointed out version D1a is not an approved draft, and the third primitive is already in version D1. Kaliski said that he will make version D1a an editorial contribution. Solinas gave a review of the changes in Annex A. Four new sections have been added: -- Section 1: Integer and modular arithmetic: overview -- Section 3: Binary finite fields: overview -- Section 8: Elliptic curve: overview -- Section 16: Tables Zuccherato asked why "strong prime" is in Annex A. Solinas said that this is for consistency with ANSI X9.31. Yin suggested that we add the prime number generation algorithm (for DSA) in FIPS 186 to P1363 Annex A. There were discussions on whether we should and can generalize this algorithm. Chen showed people a copy of ANSI X9.42, which has a generalization of the algorithm. Chen said that there are more efficient algorithms for A.2.7 ("Computing the Order of a Given Integer Modulo a Prime"). Kaliski said that we should be careful about putting too much new material into Annex A. Fumy suggested adding an introduction to Annex A. Arazi raised the issue whether Sections 5.3.2.3 and 5.3.2.4 in the main body are needed (the sections describe polynomial and normal bases for GF(2^m) over a subfield GF(2^d) for d>1). We concluded that it is an open issue whether to generalize the two sections or to delete them. Yin gave a quick review of Annex E (Cryptographic random number generation). She said that Section E.3.3 (Algorithms for pseudorandom number generation) was taken from ANSI X9.31 and all the other sections were written by Carl Ellison a while ago. Leo Reyzin brought everything into IEEE style. Blake questioned the advice on "Things to do" given in Section E.2.1.3. Johnson said that we should add a section on pseudorandom number generation validation. There is something in FIPS 140-1. Yin said that she would add a pointer to it. Yin reviewed other changes to the main body after the November meeting. Most changes were based on the decisions made at the November meeting, including -- making cofactor multiplication optional for all key agreement schemes -- changing names of certain techniques -- removing KDF-HMAC. Another change is the addition of Section 14 on output data format. People felt that output data format is outside the scope of the main body. Kaliski suggested that this section be moved to an informative annex. This annex will be called something like "input/output formats" and will include ASN.1 syntax as a subsection. There will not be a separate ASN.1 annex. Fumy suggested that we put back the table in the main body which summarizes all the primitives and schemes for each family. Yin said that the table would be put back after the main body is finalized. We adjourned at 5pm. Wednesday, March 4, 1998 The same group attended the Wednesday meeting. Meeting started at 9am. We reviewed the minutes from the November meeting. People pointed out some minor editorial typos and wording problems. Johnson said that we should take out all the sentences about "taking breaks and having lunches." Motion 2. (Fumy, Johnson) Accept the November minutes with the identified modifications. Adopt the policy of making a summary of each meeting which lists all the decisions, motions, and upcoming meeting schedules. The summary will be posted together with the minutes. Yin started reviewing Annex D (security considerations). Johnson raised the philosophical issue of what we want to put in the annex, such as established attacks vs. "speculations". We had some discussions and the general consensus was that we should only put in established attacks that have appeared in the literature. We considered the case of DLSSA-DSA. There have been no particular attacks on this algorithm. Security considerations include parameters, key sizes, encoding method, and matching hash function output size and subgroup size. We realized that a security consideration itself does not affect conformance. Rajan pointed out that security consideration would help conformance, since we require implementations to conform and recommend them to follow the security considerations. Kaliski said that he hoped that this annex would become a set of useful security guidelines to which other standards can point. Yin summarized the structure of the annex. It has five sections: D.1 Introduction D.2 General security considerations D.3 Security considerations for families of techniques D.4 Security considerations for types of schemes D.5 Security considerations for individual schemes Section D.2 covers -- parameters and keys: generation, validation, and management -- general security guidelines for primitives and schemes -- classification of different levels of attacks -- short discussion on RNG and pointer to Annex E Section D.3 covers for each family -- key size considerations -- security guidelines for parameters and keys -- notes with more information (if needed) Section D.4 covers for each type of scheme -- basic security requirement -- attacks -- additional attributes and how to achieve them Section D.5 covers for each scheme -- requirements on encoding method (or key derivation function) -- notes with more information (if needed) After some discussion, people seemed to be happy with the structure of the annex. Johnson suggested that changing "security requirements" to "security objectives." Yin said that it may be useful to have a table listing all the relevant sections for each schemes. We started considering each individual scheme. Kaliski wrote down a list of choices for DL/ECKAS. The general approach we take was to -- identify the choices (e.g., key sizes, primitives) with respect to a scheme -- give examples of the choices -- consider implications of the choices (attributes of the scheme) In the afternoon, we considered whether in addition to the general approach of "choices --> attributes," we wanted to provide information about the reverse direction, "attributes --> choices." Kravitz said that the complexity goes up since there are combinations of different attributes. The general consensus was that while the reverse direction is useful, it probably will take a long time to write everything up and hence we will focus on the forward direction. We went through each scheme in the current draft and identified the choices. There were some technical discussions, and the identified choices will be edited into Annex D. Johnson raised an issue related to the choices of elliptic curves. He expressed his concerns with the fields GF(2^m), where m is a composite. He said some experts (Schnorr, Frey) had doubt about the security of ECC over such fields, though there is no literature on this. Arazi pointed out that we are scientists, and so we should not base our decisions on speculation. Solinas said that this issue is similar to the issue of using safe primes. Kaliski said that security considerations in P1363 should depend on established common practice. Now the question is whether the use of GF(2^m) where m is prime is a common practice. Johnson said that such fields are used in Certicom's toolkit. Solinas mentioned at the November 1997 Workshop on Elliptic Curve Discrete Logarithm Problem (sponsored by University of Waterloo), Bob Silverman pointed out the time complexity might not be the only measurement for cryptanalysis. Other resources (storage, money, etc.) should also be taken into taken into account. Blake raised again his concerns with annex E (random number generations). The advice on "things to do" may be inappropriate or misleading. He did not want to include the materials in annex E. We realized that the materials had not been reviewed after they were written by Carl Ellison about a year ago. Markowitz said that there may be some merits in the advice. He mentioned some paper written by Taher ElGamal for Netscape. Arazi proposed that we approach the IEEE Microprocessor Committee to solicit its ideas on random number generation. Kaliski said that he will take an action on this. We moved on to "other technical issues." There are three issues on the agenda. We decided to address the issue of alignment with other standards first. Yin said that the potential problem with output format has already been dealt with earlier by moving the section on output format to annex. Another problem is related to DLKAS-DH2 and its compatibility with X9.42. Chen explained what is defined in the current X9.42. Yin said that DH2 in the current P1363 draft is slightly different and an adjustment will be made. In particular, at the beginning of the scheme, we will check whether the two sets of parameters and corresponding keys are the same. If so, we switch back to DH1 to preserve compatibility with DH1. Kaliski raised the question whether we really need DH2. Kravitz observed that unless there are at least three different keys, there is no need to use DH2. Kaliski proposed that we allow the first and second set of parameters to come from different families (EC and DL). Johnson even wanted to include the IF family. Kaliski felt that including the IF family as well is perhaps too much change at this point, but we will consider this in P1363a. We adjoined at 5:00pm. Thursday, March 5, 1998 The same group attended the Thursday meeting. Meeting started at 9:15am. Kravitz had some questions on DL/ECKAS. He wondered whether the scheme covers the case in which parties' public keys are authenticated by signing with other public keys. Kaliski said that this case is handled by security considerations, since we don't want to put too many variants in the main body. We set the schedule for the next two meetings. -- Jun 29 - July 1 in Boston. Kaliski will host it in Boston. -- Aug 27 - 28 in Santa Barbara. This is a short meeting after Crypto98. It seems that Johnson might be able to host the November meeting in Virginia. The tentative schedule was to hold the meeting on November 11--13. We discussed again the issue of basis choices in Sections 5.3.2.3 and 5.3.2.4 in the main body. To generalize the definition, we would replace the phrase "representing an element of GF(2^d) in terms of the polynomial basis" to "representing an element of GF(2^d) in terms of the polynomial or normal basis" in Section 5.3.2.3. Similar changes also apply to 5.3.2.4. Some people didn't like such changes. After some discussion, we decided to remove the two sections and change the second "shall" in the first sentence of Section 5.3 to "should." So we will not mandate any particular representations for finite field, but we will recommend polynomial and normal bases over GF(2) for interoperability Solinas reviewed the three known methods for generating elliptic curves. Constructing E with known #E. 1. Directly count points on (a) random or (b) selected E (pointer in Annex A.11.4-7, full description will be in ANSI TG-17) "warm fuzzy" 2. Complex Multiplication (description in Annex A.12-13) medium warm fuzzy 3. Count points on E over GF(2^d), deduce #E over GF(2^de) (description in Annex A.10.4-6) least warm fuzzy (Note the level of "warm fuzzy" indicates how comfortable people feel about the security of the method.) Solinas said that the first method is the least efficient and the third one is the most efficient. Johnson further classified the first method into "random curves" and "selected curves," and pointed out that the former is more warm fuzzy but less efficient than the latter. The latter allows one to generate special curves such as "Koblitz curves" which have certain implementation advantages. Perez mentioned several patents held by Crandall. Yin mentioned that there were some email messages on the P1363 mailing list which said that there is a patent on the CM method. Solinas said that we don't need to worry about the patent, since the method has been around for a long time. Solinas said that there is no known attack on any of the methods. Kaliski concluded that we will add an overview of the three methods and point to ANSI TG-17. We moved on to the point compression issue. Zuccherato said that point compression is only related to the input/output format, and hence we don't need to describe it in the main body. We agreed to move Section 5.5.3 and Section 5.4.1 (together with the paragraph preceding it) to Annex G (Formats). These sections address point compression and representation of EC points as octet strings. Kaliski said that Section 5.5.4 (representation of polynomials as octet strings) should also go Annex G. Blake explained a new point compression method recently developed by HP, which we considered private to the individual members. We moved on to discuss the work plan for finishing up P1363 and launching P1363a. Kaliski explained the MSC balloting process. Then we agreed on the following tentative plan. P1363 P1363a ====================================================== Apr another draft call for submissions for Annex D Jun final WG review Jul final body for 30-day internal ballot (last call) Aug ballot-related to MSC submissions Nov review of ballot review of submissions Kaliski said that he just talked to the P1363 Vice Chair Terry Arnold. Arnold will help to make sure that the balloting process will be smooth, though it is hard for him to attend regular working group meetings. In order for the balloting process to start at the end of August, we need to inform MSC by the end of May. In the afternoon, Kaliski proposed, based on discussions with Yin and Fumy, to remove Annex F (test vectors) from the draft, but to maintain a page on the Web site, on which test vectors will be posted. We considered the remaining work by sections. -- main body minor -- Annex A: number theoretic background minor work -- Annex B: conformance (normative) review plus example -- Annex C: rationale writing -- Annex D: security considerations major writing -- Annex E: random number generation (gone) merge with annex D and give pointers -- Annex F: test vectors (gone) low priority -- Annex G: formats writing -- Annex H: bibliography Kaliski identified the contents of Annex G (Formats). G.1 Common definitions - field ID and basis G.2 DL family formats - parameters, keys, signatures, algorithm identifiers - examples from X9.42 G.3 EC family formats - material similar to DL plus point compression - examples from X9.62 G.4 IF family formats - keys, output formats, algorithm identifiers - examples from X9.31 Based on the remaining work, we set up a more detailed schedule for the period before the next meeting in June. April 6: first installation for review -- Annex A: edits (Solinas, Reyzin) -- Annex B: edits plus related changes to main body (Kaliski) -- Annex D: first draft (Yin) -- call for submissions for P1363a April 13: first teleconference May 11: second installation for review -- Annex A: tables (Solinas, Reyzin) -- Annex C: draft (Yin) -- Annex D: second draft (Yin) -- Annex G: draft (Markowitz) -- Annex H and other body edits (Reyzin, Yin) May 19: second teleconference June 15: full document review Other things that Kaliski needs to work on are patent and trademark follow-up and balloting preparation. We then reviewed the existing and proposed addendum contributions/suggestions: -- encryption schemes - DL/ECES, DL/ECAES (Bellare/Rogaway, Zheng/Seberry) - IBM swizzle -- password-based protocols - SRP (Wu) - SPEKE (Jablon) -- signature schemes - PSS, PSS-R encoding (Bellare/Rogaway) - Schnorr primitive - deterministic DSA signature - "provably secure" DSA variants -- identification schemes - GQ - Schnorr - Micali -- key agreement schemes - IF family - massively unified model -- key transport schemes -- key and parameter generation/validation -- encoding methods -- key derivation functions -- hash functions We talked about the format for the "call for submissions." -- description of techniques (should be understandable without references) -- claimed attributes and advantages -- security assessment and considerations -- known limitations and disadvantages -- intellectual property issues (the submission will be considered a publication, not confidential) -- references -- presentation at the WG meeting recommended Yin reviewed the highlights of the three-day meeting that have been recorded in the minutes, and Kaliski summarized the major Actions (A), Decisions (D), and Issues (I): A. patent follow up A. conformance edits I. DHC issues A. annex A edits D. move output formats to Annex A. security considerations edits D. DH2 changes per X9.42; DH1 compatibility D. EC/DL mix in DH2 D. schedule D. remove GF(2^d) sections; shall to should D. annex A overview of EC generation method; "TG-17", "Fuzzy" D. point compression to Annex G; also 5.5.4 D. work plan (P1363/P1363a); assignments; teleconference D. annex E to annex D D. annex F to web site D. submission guidelines We had some discussions on the DHC issues. The decision is the following: we will have two primitives DH and DHC, where DHC takes as input a flag which identifies whether compatibility with DH is desired. If desired, then Kaliski's "k-inverse" method will be used. For DHC, whether or not compatibility is desired, it is necessary for r^2 not to divide p-1 (i.e., for k^{-1} mod r to exist). Kaliski raised the question whether we want to modify the MQV primitive accordingly. We realized that unless both public keys from the other party are authenticated, cofactor multiplication is needed. We decided to have both MQV and MQVC. Motion 3. (Solinas, Zuccherato) Adjourn (3:30pm).