IEEE P1363 Working Group for Public-Key Cryptography Standards Friday, August 25, 2000 Flying A Studio meeting room, University Center, UCSB, Santa Barbara, CA. MINUTES In attendance: Ari Singer, NTRU (chair, P1363 working group) Don Johnson, Certicom (vice chair, P1363 working group) Dan Lieman, NTRU (treasurer, P1363 working group) William Whyte, Baltimore (secretary, P1363 working group) Dan Bailey, WPI Dan Brown, Certicom Lucien Dancanet, Citigroup Gurgen Khachatryan, Cylink David Kravitz, Wave Systems Corp. Preda Mihailescu, ETH & MEC Consulting Satomi Okazaki, NTT MCL Leo Reyzin, MIT/RSA Security Allen Roginsky, IBM Roger Schlafly, Information Security Corp. Jerry Solinas, NSA David Sowinski, Information Security Corp. Dave Stern, Intel Tom Wu, Arcot Handouts: Agenda Minutes Attendance record Meeting summary P1363a/D5 P1363a/summary of changes (Burt Kaliski) DLKD-KK (Gurgen Khachatryan) List of open questions about P1363a (Burt Kaliski) 1. Approval of Agenda The agenda was slightly amended, as will be reflected below. Motion: approve amended Agenda. Proposed Whyte, seconded Reyzin. Passed by acclamation. 3. Officer Reports 4. Update on status of 1363 document 9. Discussion of patent issues for P1363a Singer reviewed the issue of patent reassurance for techniques in P1363a. There was concern that we hadn't actively pursued patent reassurances. Our sponsor says that as long as we have verbal assurance that a patent letter will be forthcoming, we can do technical work on it; the patent letter has to be made available prior to ballotting. Singer will be contacting all the patent holders identified at the last meeting, and will also be sending out a general letter outlining the areas which we're working in and asking that anyone who is aware of any patent issues make us aware of them too. ACTION: Singer will clarify whether or not we can ballot on a technique without patent assurance if we know that a patent exists. ACTION: Whyte to put up the revised March minutes. Singer announced that the 1363-2000 standard had been published, and will be printed in two weeks. All working group members are entitled to a free copy. Singer thanked everyone for their work on 1363. Treasurer's Report: The working group has a little over $2000 in the bank. We sent all the Deutschmarks to IEEE. The money in the bank is all meeting fees and is owed to IEEE. 2. Approval of Minutes of May/June Meeting The minutes were approved subject to some amendments. Matters arising: * Handouts should be put on the website if possible (modulo copyright etc) * EPOC-3 isn't intended to replace EPOC in 1363. Motion: Approve minutes as amended. Proposed Reyzin, seconded Stern. Passed by acclamation. 10. Discussion of future activities of P1363 working group Motion: P1363 agrees to be the working group for 1363.1 and to have its name put on the PAR to be submitted to the sponsor. Proposed Whyte; seconded Lieman. Passed 14 for, 0 against, 0 abstentions. Motion: P1363 agrees to be the working group for 1363.1 Proposed Lieman; seconded Bailey. Passed 14 for, 0 against, 0 abstentions. Singer asked for volunteers to host the next meeting ACTION: Jerry will look into NSA hosting the week of November 15th. ACTION: Singer to bring it up on the list. Motion: Approve amended Meeting Summary. Proposed Whyte, seconded Roginsky. Passed 12-0-2. 5. Review of P1363a Draft Singer reviewed the changes to the P1363a draft since the last minute. Changes related to EPOC: IFIES has been named IFES. Both EPOC 1 and 2 are handled under IFES-OU. IFES-OU has been removed from section 11.2. In draft 4, IFES was EPOC-1, IFIES was EPOC-2; now IFES-OU covers both encryption schemes, and EPOC-1 and EPOC-2 are distinguished by the encoding scheme used. EPOC-1 uses the encoding scheme in 12.2.2; EPOC-2 uses the encoding scheme in 12.2.3. The difference between the two is that EPOC-1 can only process messages shorter than some key length parameter, while EPOC-2 can process arbitrary-length messages but includes symmetric encryption. 12.2.2 has been updated and rewritten; 12.2.3 (long block encryption using a symmetric algorithm) has been added. In section 8.2.10, the generation of the randomised hash has been removed (because it was already present in the encoding method). Should it be called EPOC or OU? (Note that the original OU paper is broken, and EPOC as presented is due also to Fujisaki). ACTION: Okazaki to ask Okamoto about trademark, and seek permission to use EPOC if it is trademarked. ACTION: Kaliski to seek clarification from Okamoto about keeping v_0 secret. ACTION: Okazaki to seek more clarification from Okamoto on whether EME2 and EME3 should have a minimum seed length. In the current IFES-OU schemes, the message length needs to be known in advance. The Working Group would like to see a scheme where this isn't the case. We need to ask the designers for such a scheme. Okazaki said that Okamoto considers PSS-style padding suitable for use with IFES-OU. ACTION: Working Group to ask Kaliski to seek clarification on this issue from Okamoto. We discussed the place of conventional symmetric encryption in the symmetric "combine" operations which are used in many of the encryption schemes in 1363-2000 and P1363a. Many of the combine operations appear to use SHA-1 as a stream cipher. The possible disadvantages of using SHA-1 in this way have to be weighed against the advantages of giving a single way of instantiating an operation. Reyzin suggested asking the editor to allow for any symmetric encryption, stating what the properties of the encryption algorithm are allowed to be, and saying that instantiations can use AES as the encryption algorithm. We discussed the message representative in EME3. Should it be allowed to include part of the message, for consistency with EME2? Kaliski had previously suggested reworking EME3 as follows: * f becomes M1 || seed (currently just seed) * C becomes M2 XOR G(seed) (currently just M XOR G(seed)) * r stays as it is. A reworked scheme will need some way to specify where the message ends and the seed begins. 6. Discussion of P1363a material 6a. OU & ESIGN Okazaki led the discussion, which covered changes to ESIGN in the current draft and discussion of possible future changes. 8.2.12: * It is proposed to make step 6 mandatory, not optional. * The check for the range of f has been updated. 8.2.13: This new section gives a message-recovery variant of ESIGN. Currently, ESIGN messages in P1363a are only allowed to be octet length. In ISO, ESIGN messages are considered to be bits, not octets, but it's not clear if the intent in ISO is only to allow octet-length messages. The encoding method is subject to change to allow conformance to ISO. ACTION: Okazaki will check with Okamoto about the permissibility of other encoding methods for ESIGN. Other comments on EPOC and ESIGN: When exponentiation is done with a fixed base, we should consider mentioning precomputation techniques. If we include them, we need to mention security issues arising from storing the precomputed values. The re-encryption after decrypting can be done with Chinese Remaindering, in contrast to ordinary encryption. We should mention this in the implementation note. The private key specified in 8.12.11 doesn't include the factors, but we say the private key is stored in any way appropriate. However, the input to the encryption primitive doesn't allow for the factors because it's a public key operation. We considered that we don't require a different primitive for the re-encryption, because we say that operations should be the operation given or a mathematically equivalent operation. ACTION: Solinas will talk to Reyzin about writing this up and putting in a note about CRT mod p^2 q. 6b. PV Signatures Dan Brown talked through the changes since the last meeting. 12.3.2: EMSR2 Changed padding to PEM/PKCS#5/S/MIME-style padding, as suggested at the last meeting. Padding is prefixed to the message, in contrast to padding when encrypting with a block cipher. This doesn't inhibit one-pass processing, as the padding length is a fixed parameter. Used KDF2 rather than KDF1. There were missing security considerations in D.5.2.2. The paragraph that starts "For EMSR2" has been added. If the encryption scheme used with the encoding method has its own padding, should we consider that as additional redundancy? Brown thinks this would be more likely to be confusing than helpful, and would rather see the amount of redundancy fixed by the signer and verifier in advance. There was further discussion of the symmetric "combine" operation. 6c. Arbitrary Finite Fields Dan Bailey reviewed progress to date. We're looking at GF (p^m) for p odd, m > 1. We think there are good reasons to do it in both the DL and EC setting. NTT originally proposed the effort; XTR falls into the category; and systems of this are being deployed by NTT, DSO (Singapore National Laboratories), and others. The following topics have been added since last meeting: D.4.1.4 has been updated: Note 1 has been altered, with different text on DL attacks on odd-characteristic extension fields (OCEFs). In summary, it is conjectured that the index calculus attack on GF (p^m) can be made to take time of order L(1/2), as opposed to order L(1/3) for the GF(p) and GF(2^m) cases. The criterion is that m^1/2 < log p < m^2. We mention this in the security considerations, but don't mandate parameters that give the extra-difficulty Discrete Log. XTR falls in the L(1/3) range. We discussed additional material for this section. * Gordon's Crypto 92 attack cooks the parameters so that the SNFS runs in L (2/5). It doesn't apply to GF (p^m), because in this case it's more difficult to control the subgroup order when selecting parameters. There was disagreement about whether these cooked parameters can or can't be detected. D.4.2.4: For elliptic curves over OCEFs, generic group methods are the best attacks known. The Hess, Gaudry and Smart Weil Descent attack is only known to apply to GF (2^m), though one of the authors expects it can be extended to GF (p^m) for any prime p and composite m. For future consideration as material for this section: Vaudenay's attack, Gordon's paper, the rump session presentation from Crypto 2000 by Menezes and Vanstone. Reyzin requested a change in D.4.2.4: Change GF (q^m), q = 2^n, to GF (2^n^m). 6d. Rest of the document: PSS-R: Note that although EMSR3 allows bit-length messages, it never requires shifting values across bit boundaries, just byte boundaries. Remaining material to be added and issues to be considered: * Security considerations for EPOC, ESIGN; storage-efficient basis conversion: * Kaliski and Reyzin will add examples. * Output formats aren't clear for, for example, techniques which output two or three things. In some cases they aren't of equal length. Annex E talks about how to format the outputs; we need to update it to talk about the new techniques, some of which don't fit the existing model. In general, we don't intend to add extra formats to Annex E, but will take guidance from experts if necessary. * More material on rationale is needed. * The one-time key generation in A.16 doesn't seem to suit OCEF. The working group will ask Kravitz and Kaliski to have a look at it. * There is still no unaniminity on whether or not to exclude elliptic curves over GF (2^m), m composite. 7. New Submissions 7a) DLKD-KK The working group made several comments on the handout: * Names of authors should be changed and references updated. Khachatrian will do this later. * Normally we've worked in prime-order subgroups. * It would be nice to see the EC version as well. * It would be interesting to see if there is a weakness if the same key is used for both this and ElGamal. * There is a typo in the handout: a instead of g. * Is this reducible to the discrete log problem? No action point taken. 8. Discussion of continuing work on a second addendum to P1363 We considered whether there was a need for an additional addendum to P1363. Singer feels that P1363a leaves holes in 1363, and that a 1363b could fill these holes. Missing techniques include: KCDSA; Public Key validation for existing schemes; XTR; Arazi's inversionless scheme; and so on. At the moment we aren't considering starting a 1363b project, unless there's a suitable level of volunteers. But we'll entertain any arguments for additional techniques in P1363a. The following text was suggested as a statement of intent: The working group is seeking volunteers to organise and edit an amendment to the 1363 document in order to further enhance and extend the 1363 standard within the existing framework. In particular, we would like volunteers to seek out and compare techniques which are not currently contained in the standard. Motion: Singer to mail the list, and mail to everyone who's submitted to the site, words to the effect of the above. Proposed Reyzin, seconded by Solinas. Passed by acclamation. 11. Adjourn Motion to adjourn. Proposed Reyzin, seconded Lieman. Passed by general phew. The meeting ended at 5 pm.