Hi List, IEEE P1363 E-MOTION 2003-6 was PASSED: 9 YES, 0 NO, 0 ABSTAIN. The voters were: Mike Brenner, Dan Brown, David Jablon, Don Johnson, Burt Kaliski, David Kravitz, Roger Schlafly, Ari Singer, William Whyte. The original email containing the motion is appended. With any luck that means we're finally done with 1363a, barring accidents in the recirculation ballot. That ballot should be started shortly. Thanks! Cheers, William =================================== William Whyte Chair, IEEE P1363 Working Group NTRU Cryptosystems 5 Burlington Woods Burlington, MA 01803 tel: +1.781.418.2500 fax: +1.781.418.2532 -----Original Message----- From: Whyte, William Sent: Thursday, October 09, 2003 11:16 PM To: 1363 List (E-mail); 1363-Discuss List (E-mail) Subject: E-MOTION 2003-6: Approve P1363a draft for recirculation ballot Hi List, Below is IEEE P1363 E-MOTION 2003-6: Approve P1363a draft for recirculation ballot. Votes MUST be sent by email to myself and to Ari Singer at wwhyte@ntru.com, asinger@ntru.com. Votes should be of the form: NAME votes on E-MOTION 2003-6 E-MOTION 2003-6: The IEEE P1363 working group approves the changes to IEEE P1363a D12 outlined below, and authorizes the chair to forward updated documents for a recirculation ballot. Minor editorial changes and updates to the patent information annex may be made if needed at the chair's discretion without further vote. Proposed: Burt Kaliski Seconded: Don Johnson E-Voting opens: Friday, October 9th, 9 am EST E-Voting closes: Monday, October 19th, 9 am EST Eligible e-voters: Mike Brenner, Dan Brown, Wei Dai, David Jablon, Don Johnson, Burt Kaliski, Pieter Kasselman, David Kravitz, Pil Joong Lee, Tatsuaki Okamoto, Roger Schlafly, Ari Singer, Jerry Solinas, William Whyte (14). The voters list was updated after the January 2003 meeting, and is available at http://grouper.ieee.org/groups/1363/WorkingGroup/voters.html. Nobody's membership status has changed as a result of the August meeting. An updated voters list will be posted shortly. 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. The total number of votes for YES, NO and ABSTAIN, and the names of the individual voters (but not the individual votes) will be published on the mailing list. ===== Final Changes to P1363a _inserted text_ [deleted text] D.4.1.4 Notes (for D.4.1 DL family; this note is also referenced by D.5.1 EC family) Change Note 7 as follows: 7. (Private keys.) A private key should be generated _in an unbiased manner (i.e., randomly or pseudorandomly in the full interval [1, r-1])_ [uniformly at random from the range [1, r-1]] since this maximizes the difficulty of recovering the private key by collision-search methods _and prevents attacks based on partial information about the private key_. A desired level of security can _sometimes_ [also] be provided when the private key is restricted to a large enough subset of the _interval_ [range], e.g., is shorter than the subgroup order, has low weight, or has some other structure. Such choices require _careful_ [further] security analysis by the implementer. _In particular, attacks are known on the various DL/EC signature primitives (see D.5.2.1 Note 3) such that if _too much information is available to an opponent about the one-time private key,_ [the one-time private key is not drawn uniformly at random from the range [1, r-1],] the signer's private key may be revealed after some number of runs of the primitive. See D.5.2.1, Note 3, for further discussion of these attacks, and for discussion of how to generate integers uniformly from some interval. D.5.1.1, Note 1, discusses a similar attack, though one that is less directly linked to choice of the second private key on the DLSVDP-MQV, DLSVDP-MQVC, ECSVDP-MQV, and ECSVDP-MQVC primitives._ See also D.6 for more on random number generation. D.5.1.1 Primitives (for D.5.1 Key agreement schemes) Insert the following sentence and note at the end of the final paragraph: Security considerations related to the generation of the second key pair in the -MQV and -MQVC primitives are addressed in the Note below. NOTE - For the MQV Secret Value Derivation Primitives (DLSVDP-MQV, DLSVDP-MQVC, ECSVDP-MQV, and ECSVDP-MQVC), Leadbitter and Smart [LS03] have shown in the case of 160-bit r that if an opponent, participating in runs of the primitive, can determine the six most significant bits of the other party's quantity e = ts+u, calculated in step 5, and can do this for 20 runs of the primitive, then the opponent can recover the other party's first private key s by solving a discrete logarithm problem that requires about 2^40 effort. Similar results apply to the least significant bits, and to smaller amounts of bits with greater numbers of primitive invocations and a lower probability of success. It appears that even if one party is known to select the second private key u other than randomly or pseudorandomly in the full interval [1, r-1] (for example, by restricting it to subset of the interval), this knowledge alone is not enough to allow the other party to the primitive to mount the attack. The type of information that would be required to mount this attack is currently only known to be leaked by side-channel analysis, which is out of scope of this standard. D.5.2.1 Primitives (for D.5.2 Signature schemes) Change Note 3 as follows: 3-One-time private key generation: The one-time private key u in the DL and EC primitives should generally be selected in an unbiased manner (i.e., randomly or pseudorandomly in the full interval _[1, r-1]_ [[0, r-1]]), because if too much information is available to an opponent about the one-time private key, the opponent may be able to determine the signer's private key s. In particular, following earlier work by Howgrave-Graham and Smart [HS01] and Nguyen [Ngu01], Shparlinski and Nguyen have shown [NS02a] that if an opponent can determine the three least significant bits of the one-time private key in each of about 100 DLSP-DSA signatures, the opponent can solve for the signer's private key. They also give attacks for the case that other bits of the one-time private key are known. A similar attack applies to ECSP-DSA (since the signature equation is essentially the same after the one-time key pair is generated) and a related (though more complex) attack applies to the -NR (and hence -PV) primitives (see Nguyen and Shparlinski [NS02b] and El Mahassni, Nguyen and Shparlinski [ENS01]). Bleichenbacher [Ble01] has given an even more effective attack that can recover the signer's private key given only a slight bias in the distribution of one-time private keys, without actually knowing any bits of the one-time private keys. This attack is particularly significant in that methods suggested for generating one-time private keys in ANSI X9.30:1-1997 [B4] and FIPS PUB 186-2 [B56] as well as in the Naccache et al. and M'Raïhi et al. proposals above have exactly the kind of bias that Bleichenbacher's attack exploits, as they directly use a hash function to generate a value in an interval slightly larger than the subgroup order r. Specifically, for a 160-bit value r, a one-time private key is produced by pseudorandomly generating a 160-bit string, converting it to an integer in the interval [0, 2^160-1], and then reducing the integer modulo r. As a result the private key is biased toward the lower end of the interval _[1, r-1]_ [[0, r-1]], which is sufficient to enable the attack. Bleichenbacher's attack is currently infeasible as long as only on the order of 1,000,000 signatures are generated with a given private key. Hence, limiting the number of signatures is an interim solution to prevent the attack. To avoid the potential for further attacks, it is preferable to produce the one-time private keys _in_ [is] a different way. Two examples are the following: - Select from a larger interval before reducing. Generate a 2l-bit string where l = \lceil log2 \rceil, convert it to an integer in the interval [0, 2^{2l}-1], and then reduce it modulo r. Assuming the _string_ [strong] is uniformly distributed, the private key will be nearly uniformly distributed. This method is attractive because it has a fixed running time. - Reselect rather than reducing. Generate an l-bit string where l = \lceil log2 r\rceil, convert it to an integer in the interval [0, 2^l-1], and if the integer isn't _between 1 and r-1_ [less than r], select another one. Assuming the _string_ [strong] is uniformly distributed, the private key will also be uniformly distributed. This method has a variable running time. Variations of these methods may also provide acceptable security _, but methods with greater bias than the above ones should be carefully analyzed to ensure that the security is indeed acceptable_. For instance, in the first method, the length of the string doesn't have to be exactly 2l bits, just sufficiently longer than l bits to ensure a nearly uniform distribution after reduction. [Recommended] _Specific_ countermeasures are _given in FIPS 186-2, Change Notice 1, and_ are expected to be added to ANSI X9.30:1 [and FIPS PUB 186-2]. [While it is possible that an adequate security level may be obtained when the one-time private key is not selected in an unbiased manner, such a choice requires further security analysis by the implementer.] Annex G (Informative) Bibliography Insert the following reference: [LS03] Leadbitter, P. J. and Smart, N. "Cryptanalysis of MQV with partially known nonces," 6th Information Security Conference, ISC 2003, Springer, to appear. Earlier version available from http://eprint.iacr.org/2002/145/.