Hi List, IEEE P1363 E-MOTION 2002-4 was PASSED: 9 YES, 0 NO, 0 ABSTAIN. The voters were: Wei Dai, David Jablon, Don Johnson, Burt Kaliski, David Kravitz, Pil Joong Lee, Roger Schlafly, Ari Singer, William Whyte Details of the motion are appended below. I anticipate that the next E-MOTION we entertain will be to move to ballot on P1363a. Here's hoping... Cheers, William ======================================================================= IEEE P1363 E-MOTION 2002-4: The IEEE P1363 working group authorizes the additional changes outlined below to IEEE P1363a beyond those already approved in E-MOTIONs 2002-1 and 2002-2 and at the August 2002 working group meeting, and authorizes the chair to submit a draft implementing these changes for a recirculation ballot. Minor editorial changes and updates to Annex G may be made if needed at the chair's discretion without further vote. Proposed: Burt Kaliski Seconded: Roger Schlafly E-voting opens: Friday, October 25th, 2002, 9:00 am EST E-voting closes: Monday, November 4th, 2002, 9:00 am EST Eligible e-voters: Wei Dai, David Jablon, Don Johnson, Burt Kaliski, Pieter Kasselman, David Kravitz, Pil Joong Lee, Tatsuaki Okamoto, Roger Schlafly, Ari Singer, Jerry Solinas, David Stern, William Whyte (13) A minimum of 7 votes is required for quorum with at least 2/3 YES among YES/NO votes required for the motion to pass. Individual votes will be distributed among the e-voters for verification, but only the total count will be recorded in the working group's records. =========================================================================== Draft D10.9 Changes (previously circulated Oct. 4, 2002) 1. Clarify that the notation GF(p^m) and the term "odd-characteristic finite field", for purposes of the Standard, assumes m > 1. This was already stated in A.3.1, but was not consistent throughout the document: * In Clause 3, add the following definitions: ----- binary field: a finite field containing 2^m elements for some integer m > 0. Also known as characteristic two finite field. odd-charateristic extension field: a finite field containing pm elements for some integer m > 1 where p is an odd prime number. NOTE - Although mathematically, the various techniques based on odd-characteristic extension fields may generally be employed when m = 1, for the purposes of this standard, it will be assumed that m > 1 when the term "odd-characteristic extension field" is given. prime field: a finite field of p elements, where p is an odd prime number. Also known as prime finite field. ----- * In 5.1, update the definition of GF(p^m) to restrict m > 1. Also, add the following note: ----- NOTE-Although mathematically, the various techniques based on GF(p^m) may generally also be employed when m = 1, for the purposes of this standard, it will be assumed that m > 1 when the notation "GF(p^m)" or the term "odd-characteristic extension field" is given. The cases GF(p^m) and GF(p) are thus treated separately. ----- * In 5.3.3, update the definition of "odd-characteristic extension field" to restrict m > 1 and delete the note that stated "A prime finite field ... is a special case of an odd-characteristic extension field" 2. Clarify that the MSB compressed form is not employed for GF(p) in the representations given in the Standard: Add the following note to 5.5.6.1.2: ----- Although the MSB compressed form is defined here for any field, in the representations below it is only employed for elliptic curves over GF(2m) and GF(pm). ----- 3. Clarify the approach taken to supporting bit strings and octet strings in the various auxiliary functions, per David Hopwood's comment. This affects the notes for KDF2, MGF1, MAC1, and the hash functions clause. Example change for KDF2: ==== 1-KDF2 can accept and return either octet strings or bit strings to support the varying requirements of techniques in IEEE Std 1363-2000 and this amendment. For convenience, octet string operands are converted to bit strings here, and only bit strings are passed to the underlying hash function. This conversion assumes that the underlying hash function would convert an octet string to a bit string the same way that KDF2 does, i.e., most significant bit first. While this is true for the hash functions allowed by IEEE Std 1363-2000 and this amendment (SHA-1, SHA-256, SHA-384, SHA-512, and RIPEMD-160), it is not true in general for all hash functions. When the operands are all octet strings, KDF2 can be implemented with octet string operations only, skipping the conversion to bit strings and passing octet strings directly to the underlying hash function. ==== 4. Clarify A.6.1 step 1: Replacing "Compute" with "Represent the successive squares of t (mod p(t))" and delete "modulo 2 via repeated squaring" 5. Revise the notes to A.17.1.3 (Square Roots in GF(p^m)) to advise on "safer" implementations and to point to a more efficient algorithm: ---- NOTES 1-Steps 3 and 4 are convenient if p = 3 mod 4 and m is odd, and can be skipped in any case. 2-The i of step 12 will always be less than e, assuming that the computations are performed in a valid field (i.e., p is prime, the field polynomial is primitive, etc.). For assurance, implementations may wish to check that i <= e, and output an error message otherwise. 3-Steps 11-13 will take at most e iterations, again assuming a valid field. To avoid an infinite loop if the parameters are invalid, implementations may wish to stop explicitly after e iterations. 4-A more efficient square root algorithm is described by Barreto et al. [BKL+02]. ---- Also, correct the typo in step 3 (A should be z). 6. Add a reference to the paper by Biehl et al. on EC point validation: In D.5.1.6, insert the following sentence at the end of the second paragraph: ----- Biehl, Meyer and Muller [BMM00] describe further attacks in the elliptic curve case if the public key is not a valid point on the elliptic curve. ----- 7. Add the following references: [BKL+02] Barreto, P. S. L. M., Kim, H. Y., Lynn, B., and Scott, M. "Efficient Algorithms for Pairing-Based Cryptosystems," M. Yung, Ed., Advances in Cryptology, CRYPTO 2002, Lecture Notes in Computer Science 2442 (2002), Springer, 354-368. Revised version available at http://eprint.iacr.org/2002/088. [BMM00] Biehl, I., Meyer, B., Muller, V. "Differential Fault Attacks on Elliptic Curve Cryptosystems," M. Bellare, Ed., Advances in Cryptology, CRYPTO 2000, Lecture Notes in Compute Science 1880 (2000), Springer, pp. 131-146. 8. Updated the contact information in Annex G for RSA Security Inc. Draft D10.8 Changes (previously circulated on Sept. 12, 2002) 1. Complete the revisions to elliptic curve point representation: * Change the title of 5.5.6.2 to "Two-coordinate point representations" to clarify its distinction from the x-coordinate only representation in 5.5.6.3 * Mention in 5.5.6.2 that OS2ECP may output error if the recovered point is not on the elliptic curve, in the uncompressed case. (The compressed cases check automatically as part of solving the elliptic curve equation.) * Move the summary of point representations to a new clause, 5.5.6.4. * For flexibility, mention in note 2 after the table that "Of course, implementations may support other, non-standard formats that employ the reserved bits, but these formats would not conform with the ones defined in this clause." This is consistent with the flexibility to choose other formats given in ECIES. * In several places, change "primitive" to "representation" for clarity, and change the titles of the subclauses of 5.5.6.2 to mention the name of the representation first, and add a sentence later at the end about the names of the primitives * Reorganize 5.5.6.3 to place emphasis on the representation rather than the primitives, and add the following note: NOTE - In some situations, only the x-coordinate is needed. For instance, the shared secret value computed by ECSVDP-DH or ECSVDP-DHC depends only on the x-coordinate of other party's public key, not the y-coordinate. If this representation is employed in such a situation, then when the "octet-string-to-point" conversion primitive is called, the implementation need not compute a y-coordinate at all (though it may output "error" if no point exists with the given x-coordinate). * Add the following note to D.5.3: - The specific choice of primitives for converting elliptic curve points to and from octet strings is not known to affect security. However, to avoid any potential for attacks based on "collisions" between different primitives (i.e., where the same octet string corresponds to different points in different representations), it is beneficial if the sets of octet strings for different representations are non-overlapping (except perhaps at the point at infinity). This is the case for the various primitives specified in 5.5.6. 2. Delete the various editor's notes about methods being "subject to change" to align with some other standard. At this point, we do not expect to change any of the methods, and they are well aligned with the other standards mentioned. 3. Add a reference to the latest version of PKCS #1. This affects 10.3.3 Note 2, 11.2.3 Note 2, 12.1.3 paragraph 1, C.3.6, and E.1, where PKCS #1 was previously referenced and/or should be listed among compatible standards. 4. Add the following paragraph to 12.2.1.2 Note 2, indicating that implementations of EME1 according to IEEE Std 1363-2000 may claim conformance with the improved specification of EME1 in P1363a in certain cases: ----- As stated in B.1, conformance with may be achieved by implementing either "identical" or "equivalent" steps to those specified. An implementation of a scheme that follows the steps specified for EME1 in IEEE Std 1363-2000, yet does not reveal information distinguishing which error occurred, may thus claim conformance with EME1 as specified here on the basis of "equivalence". ----- 5. Correct 12.2.3 Note 1, which incorrectly stated that EME3 involved signatures (a cut-and-paste error) and supported single-pass processing (this was true for an earlier version, but not for the version in D10). The new note reads: ----- EME3 is not amenable to "single-pass" processing since the entire message M must be processed by the hash function before the encrypted message C is processed. ----- 6. Add a brief discussion of "tightness" of security bounds to the second paragraph of D.1, replacing the previously approved "Furthermore ..." sentence with the following: ----- Furthermore, while for some schemes the difficulty of breaking the scheme is argued to be close to the difficulty of the underlying hard problem, for other schemes the relationship is not so "tight". (For example, the published security bounds given for EME1 are not very tight compared to other schemes; for the most part these distinctions are overlooked in the discussion here.) Finally, as with any research, the security arguments may be subject to improvement or correction. ----- 7. Revise the notes to A.12.11 (Decompression of y-coordinates, MSB form) to indicate that the MSB form is only employed for binary fields and odd-characteristic extension fields in the standard, to explain that although the algorithm supports OCEF, which are not defined until A.17, it is included in A.12 for convenience, and to indicate how to solve the elliptic curve equation in the OCEF case: ----- 1 - This algorithm works for all finite fields defined in this standard. Although it supports odd-characteristic extension fields, the algorithm is defined in this clause rather than A.17 for convenience. 2 - The MSB form is only employed for binary fields and odd-characteristic extension fields in the elliptic curve point representations in Clause 5. 3 - Finding z and z' requires one to solve the elliptic curve equation at x. Steps 1 and 2 of A.12.8 do this for the prime case and steps 1-4 of A.12.9 do so for the binary case (in the notation of A.12.9, the roots are zx and zx + x). For odd-characteristic extension fields, a procedure similar to steps 1 and 2 of A.12.8 may be applied, with square roots implemented via A.17.1.3 rather than A.2.5. Once one element is found, the other can be determined directly; if q is odd, then z' = -z, and if q is even, then z' = x + z. ----- 8. Add a square root algorithm for odd-characteristic extension fields, thanks to a contribution by Roger Schlalfy and Bodo Möller (details separately). 9. In a few places, replace the "extension field case" with the more precise "binary and odd characteristic extension field cases". This affects D.4.1.2, D.4.1.3, and D.4.2.3. 10. Add a reference to the recent work by Bernstein and Lenstra et al. on circuits for integer factorization. The following text is added to D.4.3.4 Note 1: ----- Very recently, there has been significant discussion on the actual cost of hardware for integer factorization, particularly at the 1024-bit level; Bernstein [Ber01] and Lenstra et al. [LST+02] give treatments of this issue. ----- The new references are: [Ber01] Bernstein, D. J. "Circuits for Integer Factorization: A Proposal," manuscript, November 9, 2001. Available via http://cr.yp.to/papers.html. [LST+02] Lenstra, A. K., Shamir, A., Tomlinson, J., and Tromer, E. "Analysis of Bernstein's Factorization Circuit," manuscript, 2002. Available via http://www.wisdom.weizmann.ac.il/~tromer/. 11. Update references based on publication information; this affects (so far as I'm aware) [B9] (ANSI X9.44), [Cor00b], [JQ99], [NS00], [NS01], [PV00], and [Sho01b]. 12. Rename 'MSB method' as 'SORT method' and replace 'M' with 'S' appropriately. 13. Add notes explaining the names 'LSB' and 'SORT' to 5.5.6.1.1 and 5.5.6.1.2.