IEEE P1363: Standard for Public-Key Cryptography MEETING MINUTES Monday, March 24, 1997, 8:30-5:00pm Tuesday, March 25, 1997, 8:30-5:00pm Wednesday, March 26, 1997, 8:30-5:00pm Auburn University Auburn, Alabama, USA Monday, March 24 We began at 8:45. In attendance, we had: Simon Blake-Wilson *Lily Chen *Walter Fumy *David Jablon *Don Johnson *Burt Kaliski, Chair *Michael Markowitz, Treasurer *Alfred Menezes Minghua Qu *Leo Reyzin *Jerry Solinas Those marked with an asterisk above were qualified to vote. As before, attendance at one of the previous three meetings was required to vote. Mike informed us that Roger Schlafly, the Secretary, would not be coming to the meeting. Motion 1 (Leo, Don): Leo is the interim secretary. (Approved by acclamation) Motion 2: Approve the agenda from the meeting notice, with the amendment that we may take things on in a different order and on different dates than announced. (Approved by acclamation) Motion 3 (Jerry, Alfred): Approve the minutes of the last (November 1996) meeting, with two stylistic corrections, as recorded by Leo. (Approved by acclamation) We then heard the officers' reports. Burt reported that he had missed the first deadline for submitting the PAR (Project Authorization Request) for the addendum to the standard, because he had been attempting to submit it to the IEEE Standard Board rather than the Microprocessor Standards Committee. He was hoping we would draft the PAR at this meeting, which he would then submit to our sponsor, the Microprocessor Standards Committee. Burt also reported that regarding patents, he had received a letter from Roger Schlafly identifying three patents, which may cover some particular implementations, but not any general technique in the standard. Burt had also been working with Mike Matyas to identify coverage by Mike's or IBM's patents. The University of California may obtain a patent on the PSS signature format. Hugh Williams and Yuliang Zheng had said they were not aware of any patents that were related to them and covered techniques in the standard. Silvio Micali had been claiming some potential patent coverage of precomputation techniques in signatures. Hitachi had withdrawn its letter asserting coverage of SHA-1, because SHA-1 was not mandated in the standard. Burt also reported that the project's name change had been approved and we were officially called "Standard for Public-Key Cryptography." Lisa Yin, the Editor, was not present at the meeting. Leo said that he had a report from her in the form of the editorial contribution and a presentation on it, which was heard later. Burt reported that Terry, the Vice-Chair, had been busy with many other projects. Mike reported that he inherited $2380 for our account from John, our previous treasurer. He also received $830 from the November meeting. $429.93 was owed to the ISC for the Crypto Meeting. So we had $2780.07 left. He said that most of it was probably owed to IEEE, but had yet to establish the exact amount. He then informed us that the meeting fee for the meeting would be $60 (prorated to $20/day for those not present all three days). The meeting fee consisted only of the IEEE tax; other expenses were covered by Certicom. The meeting fee was collected at the end of the day. Leo presented an overview of current editorial contribution, including the appendices, in preparation for detailed review. Regarding the appendices, Leo had the following comments: Appendix A, "Rationale," has some material from the last meeting, but needs further work. Appendix B, "Mathematical Background," is fairly complete. Appendices C, D and E, the background on DL, EC and IF techniques, take different approaches: DL is more technical, EC is more tutorial, and IF is empty. One issue is whether to bring these into a common format. Appendix F, "Number-Theoretic Algorithms," continues to become more accurate, and is in good shape. Appendix G, "Cryptographic Random Numbers," has been stable for some time, focusing mainly on hardware sources of randomness. It is useful information, but it is not referenced enough in the rest of the document, so its usage may not be very clear. Don suggested adding the pseudorandom generators from X9.31 to Appendix G. Appendix H, "Conformance," and Appendix I, "Application Notes," are both empty. Application notes can be added to the background appendices, though we need to discuss how to handle these further. We currently have no security notes appendix. Appendix J, "References," needs to be linked to the rest of the document; this will be deferred until other sections are complete. We then discussed Section 3, "Mathematical Conventions and Definitions." We agreed to add a primitive, OS2PNP, for converting from an octet string to a polynomial, for completeness in specifying the ASN.1 representation of polynomials. We discussed the representation of polynomial and normal basis elements as bit strings. We proposed to maintain the difference in the ordering of bits, following established conventions: the x^{m-1} term of a polynomial basis representation goes first, whereas the \theta term of a normal basis representation goes first. Motion 4 (Jerry, Leo): Maintain the difference in ordering following established conventions, and revise document accordingly where it suggests otherwise. (Approved by acclamation) Bit strings are indexed s_1, ..., s_m; we need additional text to make explicit the correspondence between the bit string terms and field element terms such as a_0, a_1, ..., a_{m-1} for each basis. (The correspondence depends on the basis.) As suggested by Don, we agreed to separate three representations defined in section 3: and internal representation (which is up to the implementation), a notational representation (whose sole purpose is to have a well-defined notation used within the standard), and an octet string representation (used for communication and interoperability among implementations). In particular, we agreed to reword section 3 to say something of the form, suggested by Don, "For the purposes of this standard, the elements of the finite field F_p shall be represented by the integers 0, 1, 2, ..., p-1 according to the natural mapping between reduced residue classes and integers. However, implementations with different internal representations that produce equivalent results are allowed." We continued with a number of editorial comments related to representation and conversion in on Sections 3, which Leo recorded and will incorporate into the document. We agreed to change FE2IP to call FE2OSP and OS2IP in the even-characteristic case. We also agreed to make I2OSP more constructive, and to provide examples of each primitive. We then spent some time restructuring Section 3.5, and agreed to bring in more text on elliptic curves, with Mike's help. We agreed to move the point compression and representation text from Section 3.5 to Section 3.6. We also had some further discussions on the bits in the PC octet representing an elliptic curve point, and agreed to include a representation of the point at infinity. (The specific representation was left unresolved.) We adjourned for lunch. Continuing our discussion on elliptic curve point representation, following Burt's comments, we agreed to replace the U and C arguments to EC2OSP with "an indication of how the point is to be represented (compressed, uncompressed, or hybrid)." We also agreed to add "an indication of the representation used for F_q." This makes it more clear that the implementation of the primitive depends on how points are to be represented, a conformance issue. Mike then observed that "octet-string to elliptic curve point conversion" suggests that any octet string could be converted to an elliptic curve point. Based on this, we changed our entire approach on conversion primitives, putting the focus on representation, rather than conversion. Section 3.6 was reorganized as follows: 3.6 Octet string representations 3.6.1 Representing an integer as an octet string I2OSP, OS2IP 3.6.2 Representing a field element as an octet string FE2OSP, OS2FEP 3.6.3 Representing an elliptic curve point as an octet string EC2OSP, OS2ECP 3.6.4 Representing a polynomial as an octet string PN2OSP, OS2PNP Each section will give the representation of a type as an octet string. The primitives will be defined simply as converting to and from that representation. The conversion from octet strings will check that the strings are correct and were produced by the appropriate conversion primitive to octet string (e.g., that PC makes sense for the elliptic curve case), but will not check that the data are correct (e.g., that the point is on the curve). We resolved the representation of elliptic curve points including the point at infinity as follows: 00000 000 = point at infinity 00000 01y X = compressed (X,y) 00000 100 X Y = uncompressed (X,Y) 00000 11y X Y = hybrid (X,Y,y) other = error The polynomial to octet string conversion section will be updated to include F_{2^r} polynomials. (Polynomials will be represented in the essentially same way as field elements, the only difference being that there is one more term for the leading coefficient.) We moved next to Section 4, "Discrete Logarithm Primitives." Considering a memo by Roger on what the added support would involve, we agreed to add support for even-characteristic discrete logarithm systems. Additional security notes will be needed, but the changes are otherwise straightforward at this point in the editing process. Jerry volunteered to add the necessary material to Appendix F, including the Cunningham tables. We then addressed some notational issues, which are a consequence in part of the support for even-characteristic discrete logarithm systems, with the goal of harmonizing notation between discrete logarithm and elliptic curve systems. The general consensus was the following, for discrete logarithm and elliptic curve systems: p = characteristic of the field m = degree of the field q = order of the field = p^m Notation for the order of the discrete logarithm or elliptic curve subgroup, and the degree of a subfield, if coefficients are defined over a subfield, will be discussed off-line by Jerry and Leo. (The notation does not apply to integer factorization systems, for which p and q are the prime factors.) Another issue is the fact that x and y are both point coordinates, and elements of a public/private key pair. There was some discussion about whether DLPSP should be a primitive, and more generally, what conditions to require on the parameters, and how to check that an implementation conforms with them. One possibility discussed was to have a specific primitive for parameter generation similar to the X9.30 approach for generating DSA parameters (appropriately generalized). We agreed that such a primitive should be put in an appendix. DLPSP will be removed from the body, and in its place we will put general conditions on the DL system parameters, with pointers to security recommendations and to the primitive in the appendix. A seed or other verification information will be an optional output of parameter generation (verifiable by a companion parameter verification procedure); a seed could also be an optional input. The conformance appendix will deal with what it means to conform with parameter generation, along with other issues. We adjourned for the day at 5:00. Tuesday, March 25 We began at 8:35. In attendance, we had: Simon Blake-Wilson *Lily Chen *Walter Fumy *David Jablon *Don Johnson *Burt Kaliski, Chair *Michael Markowitz, Treasurer *Alfred Menezes Minghua Qu *Leo Reyzin *Jerry Solinas We continued our discussions of Section 4, agreeing to reorganize the section as follows: 4.1 The DL Setting 4.1.1 Notation 4.1.2 Generating and Verifying Parameters 4.1.3 Generating Key Pairs 4.2 Cryptographic Primitives 4.3 Cryptographic Schemes The key generation discussion should give a pointer to notes about key management and key usage (much like other sections). Similar to how we handled conversion yesterday, we agreed to remove the focus from the parameter setup and key generation primitives, and put it instead on the parameters and the keys. DLKGP will be given as the name of a primitive that produces a key pair, which may do so by any of a number of means. The text will recommend or require that the private key be unpredictable and stored securely. We will provide for a public key verification primitive in the new Section 4.1.3, which will test that the public key is not 1 and is in the subgroup of order q, giving algorithms for performing the test in Appendix F. (Two algorithms mentioned by Jerry are to exponentiate to the power q and to compute a Jacobi symbol, depending on p and q.) An implementation may or may not provide this primitive (as is the case with all primitives), and an application would call it as required by security policy and the level of trust in a public key. The cryptographic primitives will mention this primitive. DLSVDP-DH should note that the primitive produces the same shared secret value from the party's public key and other party's private key. Regarding DLSVDP-MQV, we agreed to mention the additional condition that the public key mod 2^L (where L is half of the key size) is nonzero for MQV keys. We will add a note to MQV explaining why step 4 is there. The value of L should be computed as an optional parameter, not in the primitive. (There appeared to be an error in the value of L.) The primitive should note that it produces the same shared secret value for the other party. We agreed that DLSP-NR should restrict e to the range [0,q-1]. The signature and verification primitives should say (for example) "This primitive is used by the schemes to verify ..." rather "This primitive verifies ...", to defer attention to the scheme. We also agreed that the meanings of "valid" and "invalid" should be stated more clearly, i.e. that they imply that the inputs are valid, not that the signature is necessarily valid. We moved to DLSSA-NR and DLSSA-DSA to continue with the signature topic. An important issue is support for additional information, such as hash function identifier, in a hash function. We will call this a "formatted cryptographic hash function." DLSSA-NR and -DSA both encode a signature by concatenating octet string representations of the integers r and s. However, X9.30 encodes the signature as an ASN.1 type SEQUENCE {INTEGER, INTEGER}. DSS does not include a formatting step at all. In the interest of supporting different encodings, we will make signature encoding or formatting a separate function. This will result in the following approach for DLSSA-NR, -DSA, and more generally for other schemes: * scheme begins with a discussion of what the parties need to agree on to communicate: parameters, keys, hash function, signature format, etc. * signature generation function is presented next, which does not include a signature formatting step * signature verification function is then presented This ties in again with the conformance appendix. We will also give a matrix relating other standards to the signature schemes and their options, such as the following: scheme DSS X9.30 hash SHA1 SHA1 sig gen DLSSA-DSA sig gen DLSSA-DSA sig gen sig ver DLSSA-DSA sig ver DLSSA-DSA sig ver format n/a ASN1 Parameter generation, including p, q length restrictions could also be included in the table. We adjourned for lunch. Regarding mod q reduction issues in the signature schemes, we agreed that the formatted cryptographic hash function should produce a bit string of a length agreed upon by the parties to the scheme. The signature generation or verification function will convert the bit string to an integer. For NR, the specified length must be less than the length of q, so the integer is always less than q. For DSA, it will be recommended that the specified length be less than the length of q, but it need not be (this accommodates DSS, and may involve a mod q reduction). We then took on the Diffie-Hellman key agreement for the DL family. Leo presented the current unified model DLKAS-DH and explained the issues involved. The scheme currently takes one or two keys from each party as input, processes them through the Diffie-Hellman output. He and David pointed out that it wasn't clear for a reader how to do vanilla Diffie-Hellman, and the notes didn't make it any clearer. Don objected to the word "perfect" in "perfect forward secrecy." We weren't sure whether to remove the word or to keep it (pro: it's accepted usage; con: it's not perfect from information-theory perspective). Burt brought up that we should consider what we want from the scheme. We agreed that we wanted to support all possibilities (one or two key pairs from each party). Burt pointed out that there are many more flexibilities for Diffie-Hellman (e.g., you can have one EC and one DL shared secret, or can have a prior shared secret and add one to it, etc.). We considered different possibilities for presenting the unified model, such as separating it into four schemes, separating the plain vanilla Diffie-Hellman out, etc. Notation may help, suffixing keys according to whether they are ephemeral or static. We can also improve the presentation. An issue is where the notes belong. Leo offered to revise the presentation according to the discussion and to post the section for review. We decided to send a note to Dave Maher (AT&T) regarding the unified model patents. We agreed to the following approach: present a "vanilla" Diffie-Hellman where there is only one key pair per party, and a "unified" Diffie-Hellman where there are two key pairs per party, with notes discussing the degenerate cases where a party has only one key pair. The goal is to be compatible with X9.42 and between the two schemes in the one key pair per party case (which will probably involve checking that z = z'). The parameters must be the same for the two parties in the "vanilla" scheme, but there may be a different set of parameters for ephemeral keys and static keys in the "unified" scheme. We agreed to make the key agreement schemes output keys rather than octet strings. When two parties agree on a key derivation function, they are also agreeing on the type of key to be derived. In the case of DES, for instance, the key derivation function might include setting parity bits. We turned next to the elliptic curve techniques. The issues were generally the same as for discrete logarithm techniques, and Leo made some further notes. There were some issues related to verifying the value of k (the cofactor) in elliptic curve parameters; we will add k to the parameters, and Alfred and Jerry will discuss off-line the process for verifying it. We agreed to add a note to the signature schemes (EC and DL) stating that if the one-time key pair is used more than once, the private key can be recovered from signatures. ECSVDP-DH has a slight difference from the DL version: if the public key is not valid (and its validity is not checked for whatever reason), the point S may be the point at infinity, in which case the shared secret value will be undefined. In the DL version, the shared secret value is always defined. Also, for ECSVDP-DH, the validity of the public key in some cases may be easily checked by multiplying by the cofactor (without the need for a separate primitive); we agreed to add that to the primitive. ECSVDP-MQV has some differences from the DL version; Jerry and Leo will discuss this off-line. We adjourned for the day at 5:35. Wednesday, March 26 We began at 8:35. In attendance, we had: *Lily Chen *Walter Fumy *David Jablon *Don Johnson *Burt Kaliski, Chair *Michael Markowitz, Treasurer *Alfred Menezes Minghua Qu *Leo Reyzin *Jerry Solinas Burt presented a plan for the day, which was accepted: in the morning, complete the review of the EC techniques, begin review of the IF techniques, covering at least the primitives and the signature schemes, and in the afternoon, discuss meeting plans and strategy for the document, and prepare the PAR for the addendum. Returning to Section 5, Don proposed we provide for optional "audit information" such as random generation seeds with private keys. We will discuss seeding along with pseudorandom number generation in Appendix G, and explain the issues related to storing the seed. We agreed to give this further thought. Jerry offered to provide rationale for why some of the steps in EC and DL Diffie-Hellman are different (it's due to the expectation that the order of the subgroup will be close to the order of the curve in the EC case, but not in the DL case). We deferred to further off-line discussions issues related to verifying that public keys (long-term and one-time) are in the subgroup in the DL and EC signature schemes. We then brought up again the issue of rationale for checking or not checking s = 0 in Nyberg-Rueppel, and deferred it to off-line discussion. Minghua agreed to check this. The EC schemes will be modified following the new model for the DL schemes. We discussed briefly the possibility of merging DL and EC schemes further, to the extent that the scheme does not depend on the particular family, but deferred this until the current changes are made to the schemes. We turned next to the IF schemes. Leo mentioned that there are no boxes with definitions in this section, because there are so few definitions. Leo intends to drop the requirement that the modulus length in bits is a multiple of 8, with small changes to the schemes. We agreed to add the requirement that p, q \equiv 3 mod 4 for RW keys (which is implied by the current requirements, but is more explicit). We agreed to add security notes on the size of d, and to explain that there are many acceptable d's, and it is an implementation option which to choose. The text currently says that p and q are not part of the keys, but we agreed to leave this as an implementation option. For the purposes of the standard, the private key is defined as (n,d), but other forms are acceptable. ASN.1 can give multiple ways of representing the private key. The values p and q should be considered sensitive information. Strong prime conditions will be covered in security considerations. Appendix F gives some methods. We still need to agree on the handling of this issue. Burt offered to forward a copy of Ron Rivest's strong primes paper, Ari Juels' note to X9F1, and Bob Silverman's paper regarding EMV to the P1363 working group. Don will forward other X9F1 correspondence. A variety of key generation issues related to auditing can be included in Appendix G. (Such as comparing hashes of private keys, to prevent duplication.) What particular issues are relevant remains to be determined. Another issue for security considerations is the size of the RSA public exponent. Don mentioned that there may be both lower bounds and upper bounds, and will forward relevant papers as they become available. To avoid confusion with the other sections and make the standard look more uniform, a table of notation will be included in Section 6. A lengthy discussion of system parameters for RSA followed, leading to the conclusion that we will add text for the IF family describing what conventions parties to a system must agree upon, such as supported modulus lengths and exponent values. This will have substantially the same flavor as what is done in the DL and EC cases, and as in those cases will tie in to the conformance appendix. The important point is that although there have traditionally been no cryptographic parameters in the RSA case, conventions must be established first. We will add text describing the use of the various primitives, similar to those for the DL schemes. A discussion of checks on the message input to RSA encryption followed, including whether to filter messages (for example, exclude small messages) before encryption, and countermeasures, such as OAEP and strong random generation. The general sense was to explain some of these issues in the security considerations. A discussion of RSA/RW signature primitive. Three alternatives were identified: regular RSA, 2-way ambiguous RSA (currently in the draft) and the 4-way ambiguous RW (currently in the draft). It seemed like most people wanted all three in the standard. Disambiguation happens in the primitives, not in the schemes. RSAVP and RWVP need error outputs. RWSP should have a reference to the appendix for computing the Jacobi symbol. Don suggested that we have a note explaining why the math in RSADP is the same as in RSASP (similar to RSAEP / RSAVP), which is to separate encryption from signatures. We agreed against merging these primitives together. We need a security note to deal with the possibility that a signature with appendix and a signature with message recovery could be confused, and one could be substituted for the other. There was lengthy discussion about whether we agreed at the last meeting to include a message recovery scheme for integer factorization. Since the minutes of the last meeting were inconclusive, we put it to a vote. Motion 6 (Jerry, Walter): Keep the RSA/RW/ISO 9796 signature scheme with message recovery. (Approved 6-0-3, Alfred, David, Don abstaining). We adjourned for lunch. Burt distributed a document "Some Revised DL Schemes," containing proposed revisions to the DL schemes incorporating the previous day's discussions. He suggested that we model the IF schemes similarly and asked whether we should require the ISO/IEC 9796 format for the IF schemes, or leave it as a recommended option. This led to the issue of whether we should require auxiliary functions and formats in general, or strongly recommend them. One of the arguments for mandating them was that since they are a crucial component of security in a scheme, they should be required. Some of the arguments against mandating them were that this committee would not be able to react to changes in hash functions fast enough to add and remove them (in addenda) promptly, and that by mandating particular hash functions we would be restricting the key size range. The issue was put to a vote. Motion 7 (Leo, Jerry): Specific auxiliary functions including hash functions and the ISO/IEC 9796 format will not be mandated by the standard. The level of emphasis placed on their security will be as high as for key sizes. A list of recommended auxiliary functions will be given and the use of other functions will be discouraged. The list can be revised in addenda. (6-2-0, Alfred and Don opposing, David absent) Burt will find out about the technical correction process, should we need to revise the list of recommended functions. Don pointed out that we should explain what is not in the scope of the standard (such as standardizing particular hash functions), to better define the boundaries. We then discussed our meeting schedule. The Eurocrypt '97 meeting will be at the Ramada Halm in Konstanz, on the afternoon of Thursday, May 15, and all day Friday May 16. The purpose of the meeting will be to introduce the standard to the Eurocrypt participants, to solicit contributions to the addendum, and to align with international activities. This will not be an editing meeting; instead, we will have an editing meeting in June in Chicago, to be hosted by Mike. Details will be announced. The Crypto '97 meeting will be both an informative meeting and an editing meeting as it was last year, and we will probably continue through Saturday. We will have a teleconference on Friday, April 25, at 10 am Pacific Time. We then discussed the PAR for the addendum briefly, observing that the scope should be the same as for P1363 (since it's a supplement), and that the purpose should be basically the same. Motion 8 (Alfred, Leo): The working group authorizes the chair to submit a PAR for a supplement to the standard, with the same scope as P1363, and purpose amended to reflect the work that has taken place in P1363. The P1363 working group will be the initial working group for the addendum project, if approved. (7-0-0, David, Mike absent) Leo and Lisa are working on extracting supplementary material from earlier P1363 documents, for posting on the Web. Other contributions are already on the Web. Burt will solicit additional contributions, in particular at the Eurocrypt meeting. The notes on the scope of the P1363 document should explain why we separated the main document from the addendum. Motion 9 (Leo, Jerry): To adjourn. (Approved by acclamation) We adjourned at 3:00pm, leaving time for off-line technical discussions.