IEEE P1363 Working Group for Public-Key Cryptography Standards Wednesday, November 15, 2000 NSA, Fort Meade, MD MINUTES Attendance: Ari Singer, NTRU (Chair) Daniel Lieman, NTRU (Treasurer) William Whyte, Baltimore Technologies (Secretary) Dan Bailey, NTRU/Brown University Daniel Bleichenbacher, Bell Labs Mike Brenner, MITRE Carlin Covey, Cylink Corp. Lucien Dancanet, Citigroup David Jablon, Integrity Sciences Burt Kaliski, RSA Laboratories David Kravitz, Wave Systems Pil Joong Lee, Postech Preda Mihailescu, University of Paderborn Hong Nguyen, Infineon Technologies Jerry Solinas, NSA David Stern, Intel Handouts: Meeting notice and agenda. Study Group Meeting Summary (unapproved) Study Group Meeting Minutes (unapproved) Working Group Meeting Summary (unapproved) Working Group Meeting Minutes (unapproved) P1363.1 Call For Submissions. Proposed Timeline for P1363.1 Strawman Outline of P1363 Registry Format Standard Strawman Outline of P1363 Registry Process Standard Proposed Timeline for P1363.2 P1363.2 draft D2000-11-09 Scope, purpose and example entry for registry List of voters. Introduction to Liner Time GT-1 Encryption (Mike Brenner) On the generation of one-time keys in DL signature schemes (Daniel Bleichenbacher) Meeting started 1.45 pm. 0. Introduction 1. Approval of working group agenda Motion: Approve agenda. Proposed Kaliski, seconded Whyte. Passed by acclamation. David Jablon and Lucien Dancanet have temporary voting rights at this meeting, and will be full members if they attend half of it. 2. Approval of August minutes Motion: Approve summary. Proposed Dancanet, seconded Lieman. Passed unanimously. Motion: Approve minutes subject to amendments. Proposed Lieman, seconded Johnson. Passed unanimously. 3. Officer reports Chair (Singer): Singer completed the PAR forms and submitted them to our sponsor, who approved them and submitted them to the IEEE. The IEEE asked for clarification on the time for completion, and our sponsor estimated January 2003. The IEEE will determine whether or not to approve the PARs on December 7th. Singer is going to put out an additional call for a primary editor. If no-one applies, possibly we will turn out not to need one. The primary editor's job is to ensure that the indivdual documents have active editors, and that the documents conform to IEEE standards. IEEE informs us that you are allowed to ballot on a standard without having all the relevant patent assurance letters in hand, but any approval will be provisional on a patent assurance letter being received within two and a half months of RevCom approving the standard. Treasurer (Lieman): The meeting fees are $10 per half day. We have about $3,000 [ CHECK ] in the bank. The catering fee for this meeting will be paid to the treasurer in addition to the meeting fee. Secretary (Whyte): March and June minutes revised as instructed, and put up on the website. Webmaster (Solinas): The website will need to be revised once the study group has wound down. 4. Update on status of new projects Singer confirmed that Yuliang Zheng [ CHECK ] and Mike Brenner have expressed interest in the P1363b project. 5. New presentations to the working group: 5a. Nonabelian Braid Groups Brenner presented on Nonabelian Braid Groups, with reference to his handout. He is in the process of setting up a website with the technical details and the timing results. It should be ready in a few weeks at the following URI. http://math.gc.cuny.edu/ResearchGroups/Crypto/ Arithmetica corp. owns the patent on these algorithms. They will require licensing for commercial use but not for non-profit. 5b. One-time DL keys Bleichenbacher presented on the generation of one-time keys in DL signature schemes. The results presented were preliminary and Bleichenbacher requested that the group not publicly disclose the contents of the presentation until after February 15th. The attack focuses on the bias of the FIPS approved random number generator for generating one-time keys for DSA signatures. This attack is not known to be practical using currently available technologies, but it is also not known to what extent improvements can be made to make the attack more practical. The working group considered the attack to be significant enough to warrant including a security note on DL signatures indicating that it is desirable to eliminate any bias in the key generation method for one-time keys in order to prevent attacks such as the one proposed by Bleichenbacher. A reference to this attack will be included in the document when there is a paper available to reference. 6. P1363.1 Lieman led the discussion. He proposed to post a call for submissions as soon as IEEE approves the PAR, and to set a close of submissions date of October 1, 2001. We plan to vote shortly after the close of submissions on the final inclusions for P1363.1, depending on the number of submissions and when they come in. We reviewed the call for submissions and suggested the following changes: * Add text to the initial paragraph explaining the document's relationship to 1363-2000, and giving examples of hard problems over lattices. * After the sentence beginning "IEEE Std 1363-2000", add "for families based on IF, DL, ECDL. The aim of this document is to standardize corresponding techniques based on lattice problems." * In "Submission format", point 5, change "addendum" to "draft standard" and change "standard" to "draft standard". * P2, second paragraph: change "here" to the appropriate URL. * Give a deadline for transmissions. ACTION: Lieman will implement the suggested changes and circulate the mailing list with the revised document. Singer will publicize it when this becomes possible. The meeting adjourned at 4.59 pm. We resumed at 10.45. Attendance: Ari Singer, NTRU (Chair) Don Johnson, Certicom (Vice-Chair) Daniel Lieman, NTRU (Treasurer) William Whyte, Baltimore Technologies (Secretary) Dan Bailey, NTRU/Brown University Dan Brown, Certicom Mike Brenner, MITRE Lucien Dancanet, Citigroup David Jablon, Integrity Sciences Burt Kaliski, RSA Laboratories David Kravitz, Wave Systems Pil Joong Lee, Postech Preda Mihailescu, University of Paderborn Hong Nguyen, Infineon Technologies Jerry Solinas, NSA David Stern, Intel Additional handouts: IEEE P1363a/D6 P1363 D6 Summary and work plan P1363 discussion topics update Implicit Signatures and Certificates (slides) Provably Secure Implicit Certificate Schemes 5c. Implicit Certificates Brown presented on Implicit Signatures and Certificates. An implicit certificate is some data that together with the public key of the CA can be used by the verifier to: - Recover the subject's public key - Provide identification data for the Applicant, such that the Verifier can trust that only the identified Applicant can possess the private key. The subject (called the "applicant" in the presentation) generates a random pre-keypair, and sends the public part of this to the CA. The CA combines this with the subject's identity information, a random value, and its own private key, to produce an implicit certificate, which is a triple of values, two mathematical and one consisting of the identity information used. One of the mathematical values allows the subject to derive a long-term private key; the other can be combined with the subject's identity information and the CA's public key to derive a long-term public key. This form of implicit certificate facilitates verification of certificate chains, in contrast to previous ones. It is suggested that this technique can fit into the 1363 documents, with three operations: * Generate/issue * Apply * Recover Singer suggested that this be considered a protocol, with schemes and primitives within it; Generate/issue can be considered a protocol in its own right. Kaliski pointed out that this doesn't have to be considered a signature scheme in its own right. Whyte suggested that this be considered a two-party key generation scheme. 7. P1363.2 Singer reviewed the P1363.2 timeline. It's very similar to the 1363.1 timeline; the call for submissions is scheduled for a month later, but this might change at the discretion of the editor and the Working Group Chair. The call for submissions may be distributed and discussed electronically before the next meeting. We also anticipate that this document will have a few more drafts than 1363.1, because there will probably be more submissions for this than for 1363.1. There will be a close of comments before the vote on final inclusions. ACTION: Jablon and Singer to circulate draft call for submissions on the list, and publicize it after the PAR is approved. Jablon led the discussion of the strawman draft of P1363.2, emphasising the structure, terminology and concepts rather than issues of the accuracy or specific content of the current draft. Structure: * Should we move towards the registry format? * Dependencies on P1363 * Schemes needed to support protocols? * How much discussion of concepts? Terminology: * "Password-entangled keyset /pairs" * Symmetric/assymetric trust model * What is a protocol? Should we instead say "abstract protocol"? * Commitment. All these methods are a process of proof of knowledge of a password. Concepts: * Trust models * Explicit vs implicit authentication * Order of message flow (in subsequent proofs) * Pasword "entanglement" * Commitment * Abstract protocol "Password-entangled public key" is the term coined to describe Alice and Bob's outputs in the intermediate stages. The structure of the public keys may be different from classical Diffie-Hellman keys, although in the case of SPEKE the structure is the same. The use of the password is what distinguishes this collection of techniques from ordinary Diffie-Hellman and its EC equivalents. Kaliski reviewed the difference between schemes and protocols in 1363. Diffie-Hellman was chosen to be a scheme rather than a protocol because there are many possible protocols in which the same collection of Diffie-Hellman operations can be used. He doesn't see a variety of SPEKEs that could be based on the SPEKE shown here (except that the messages can be transmitted in either order for SPEKE). The question is, is there a logical way of using these operations other than in this protocol? We broke for lunch at 12.30, and reconvened at 1.50 pm. We discussed what we'd like to see in the next version of the draft. Johnson and Kaliski requested a model, with an overall picture, structure of schemes, objectives and so on spelled out more clearly than in the current draft. Johnson requested more background material. Johnson wondered if we wanted to ask all previous submissions to explicitly request that their submissions move from 1363a to 1363.2. Jablon and Whyte considered that people who have already submitted need not resubmit. It was widely felt that people who have already submitted should be personally contacted by the chair and told about the 1363.2 project. ACTION: Singer will contact all the submitters of password-based techniques, and NTRU in the case of lattice-based techniques, to let them know officially about the new documents. Kravitz wondered what the situation was with IP. There are relevant patents belonging to Lucent, Integrity Sciences and IBM. Integrity Sciences has presented the P1363 working group with a letter of assurance. 9. Update on related standards activities Brown presented about the NESSIE meeting which was on the same week as the P1363 meeting. NESSIE is a three-year project whose aim is to recommend one each of asymmetric, block, stream, hash functions. (possibly more than one each). The project will come to an end on January 1, 2003. Main criterion: Security. Also interested in flexibility and in encouraging European research. It's funded by IST, the Information, Standards and Technology body in the EU. Once they've made their recommendations, they'll try to advance them in other standards. There are a number of submissions, but they're willing to consider submissions from other standards. There were six submissions for asymmetric schemes: * RSA-OAEP, RSA-PSS * ECDSA, ECIES * Shoup's ACE scheme * PSEC 1-3, EPOC 1-3 and ESIGN * QUARTZ, SFLASH and FLASH (Patarin) * GPS identification protocol. Johnson: ISO SC27 working group 2 has a number of techniques in common with 1363. There is also a call for encryption algorithms, similar to the NESSIE project, which will be 18033. This is looking for symmetric block ciphers, symmetric stream ciphers, and asymmetric encryption. There were 20 submissions for block ciphers, including all the AES finalists and 8 or 10 from Japan. ISO requested the Japanese to reduce the number; after the AES announcement, it was decided that Triple DES and Rijndael would be the baselines for the strawman draft, with other algorithms added if they had any advantages. For the stream cipher, IBM didn't submit SEAL, but they might yet. There was discussion (at the ISO meeting) of how many techniques they should aim to include. They're going to put together an initial draft with several techniques and decide as they go along. Singer wondered if there was a more formal way to organize coordination between P1363 and the other standards bodies, so that, for example, we could make it easier to get current working drafts of other standards and make sure we conformed to them. Johnson is the official liaison between ANSI X9F1 and ANSI T3 (which is the body that sends to ISO SC27). ANSI only gives the draft standards to people who attend meetings. Johnson has to get permission from the Secretariat to take an ANSI X9F1 document to ISO. Stern mentioned that W3C are starting up a crypto consortium to cover XML stuff. Kaliski said that when we looked at coordination with other standards bodies, it was hard to set up formal contacts because of the IEEE structures. However, we can ensure that PARs are sent to relevant bodies. He considers that himself and Johnson are covering the informal contacts reasonably well. Kaliski updated us on Cryptorec. This is going along much the same lines as NESSIE and P1363. He mentioned the ISO 9796-2 revision, which is intended to be aligned with the P1363 version of PSS. PV is now in part 4 of the elliptic curve omnibus project. How do we handle it if a technique is being discussed in ISO? Do we standardize and run the risk that we end up being incompatible? Do we hold up the document? Kaliski would like to consider any comments that come back to ISO, and to pass on to ISO any comments that come to us. Johnson pointed out that ISO can only received comments from national member bodies. 8. Update on P1363a document 10. Review of P1363a timeline 11. Discussion of major issues with P1363a 12. Detailed review of P1363a draft Singer has posted the patent letter to the people identified at the June meeting. Kaliski talked us through the "discussion topics" document. ESIGN: In IFSSA, should other encoding methods than EMSA2 be allowed for the ESIGN primitive? Okamoto said that he thought EMSA3 could also be allowed, but didn't see a compelling reason to use it. The requirement is only that the encoding method produces a message representative one byte shorter than the prime lenght. The ISO standard containing ESIGN uses EMSA2. For ESIGN, should the value k be constrained so that EMSA2 aligns with ISO techniques? This is problematic, because ISO requires that the message length is a multiple of 8 bits, but the prime length isn't necessary a multiple of 8 bits for EPOC. Okamato has offered requiring that the prime length is a multiple of 8, so the modulus will be a multiple of 24. (This is in 14333). Kaliski will go back and do whatever ISO does. ISO tends towards bit string messages; we have tended to require octet strings. 1363a is moving towards allowing bit strings. OU Should it be renamed EPOC? What is the trademark status? NTT doesn't hold any trademarks, and Okamoto would rather see the encryption scheme be named EPOC and the primitives be named OU. Must v_0 be kept secret? No. Should EME2 and EME3 have a minimum seed length? No other encoding methods have a minimum seed length. We should give strong recommendations in the security considerations clause. Kaliski has adjusted EME2 so the seed length is now an application-controlled parameter. In EME2, should the encoded message EM delimit the message M so the message length doesn't have to be passed to the decoding operation? We delimit on the left by prepending 00 ... 01, and we delimit on the right by appending the seed of known length. Should conventional symmetric encryption be allowed in EME3? Yes. We'll revisit this. For the time being, note that in Draft 6 we allow a stream cipher based on KDF2 or a block cipher whose key is derived using KDF2. Should the message representative in EME3 be allowed to include part of the mesage M to reduce message expansion? Okamoto doesn't see any advantage to this, so Kaliski has dropped it. PV signatures Should the two methods of encrypting the message in EMSR2 be combined into one? No. Keep with current practice. Should a note be added to EMSR2 that if the summetric encryption method includes its own padding it can reduce the amount of additional padding? Kaliski has added a note to D6 to the effect (in D.5.2.2) that the amount of padding in a symmetric encryption scheme "may also be considered" when determining the amount of redundancy. DL/ECIES Should it be generalised to support other methods of protecting the message with the shared secret value than the one currently specified? For example, why not use ElGamal with Swizzle or OAEP? Still open to discussion. We'll come back to it. Rationale: What questions should be added to Annex C? Still open to discussion. Kaliski's new agenda: Symmetric encryption (to include DL/ECIES discussion) Rationale KCDSA Format DL/EC keypair generation Conformance. DSA key generation: The defenses against the Bleichenbacher and Vaudenay attacks seem to contradict each other. Naccache's paper assumes the one-time keys are generated using a random oracle. Kaliski suggested pulling the one-time key generation methods from P1363a. But we should also review P1363 and consider putting a technical correction on the web page. ACTION: Singer to ensure a P1363 Security Alerts page goes up. Kaliski doesn't want to put something in Annex A until the broader community has had a chance to look at it. Summary of changes on document: Kaliski reviewed the changes that had been made. Only those changes which were the subject of substantive discussion are included in these minutes. 8.2.10: Can use CRT when re-encrypting in EPOC. Added note to this effect. Johnson asked if we should have two or three private key representations. Kaliski observed that p is already in the private key, and this is enough to derive q. He suggested putting an algorithm in Annex A about how to use the CRT in this case. If Reyzin and Solinas come up with a note on this Kaliski will incorporate it into P1363a, but he doesn't consider it vital to completion of the document. Kravitz wondered if there was a possible timing attack from the fact that the message is being encrypted twice, once by the sender with the public key, once by the receiver with the CRT information. Kaliski and Singer didn't feel we needed any additional material about timing attacks. Whyte pointed out that if there is a vulnerability it'll affect the initial decryption, regardless of how the re-encryption is performed. ACTION: Singer to clarify whether it's the amendment that's ballotted on or the resulting merged standard, and at what point the amendment is folded into the document. Kaliski expects to have a draft available for review before the next meeting. Remaining issues: - Symmetric encryption (to include DL/ECIES discussion) - Rationale - KCDSA - Format Whyte wondered if we should consider these almost free message integrity modes instead of MAC-and-encrypt. Johnson considered that these messages are so short that there's no gain, and that we shouldn't be putting extra evaluation burden on ourselves. Kaliski reviewed the history of symmetric combine operations. EMSR2 (PV) -- allows KDF2-XOR stream, KDF+unspecified symmetric block. EME3 (EPOC) -- used to allow MGF1-XOR stream. After consultation with Okamoto, changed to be the same as EMSR2. DL/ECIES -- uses HMAC as well as encryption. Used to just allow KDF2 XOR + HMAC. Has been changed to use EMSR2 techniques. Now is a useful time to consider: * specifying symmetric encryption; * other options for MAC + Encrypt. Singer feels that the group should be stating what properties the symmetric encryption and hash function provide, rather than specfying hash functions and symmetric algorithms. Kaliski feels that even doing that is outside our area of expertise. Instead, we should invite people to do more investigation. Kaliski also feels that we should recommend specific symmetric encryption algorithms, and that if we go beyond AES and Triple DES we have to justify excluding the rest of the universe. We also need to specify a mode. Singer suggested supporting Triple-DES, anticipating AES. If we are to conform with ANSI X9.17, we need to say whether it's two-key or three-key triple DES. Singer pointed out that the requirements vary from scheme to scheme. CBC mode, can be used with a fixed zero IV and it'll satisfy the requirements we believe to exist. Can't use ECB as it doesn't give semantic security. These algorithms are recommended good practice, not requirements, similar to our recommendation of SHA-1 and RIPEMD. Wei Dai commented on the construction of DL/ECIES. As it appears in P1363a, he would prefer to have the MAC key first to facilitate single-pass processing. In this case it isn't much of an issue for transporting keys, but it may be an issue with longer messages. There isn't anything we can do about this, as it'd break alignment with other standards. Also: If you're using it for long messages, you probably won't use the KDF2 stream cipher, you'll use AES; and in this case you only need 128 bits of output from KDF2. Kaliski will put in a note to this effect. We adjourned for the day at 5.30, and reconvened at 8.50 the following morning. Attendance: Ari Singer, NTRU (Chair) Don Johnson, Certicom (Vice-Chair) Daniel Lieman, NTRU (Treasurer) William Whyte, Baltimore Technologies (Secretary) Dan Bailey, NTRU/Brown University Burt Kaliski, RSA Laboratories David Kravitz, Wave Systems Pil Joong Lee, Postech Hong Nguyen, Infineon Technologies Jerry Solinas, NSA David Stern, Intel Additional handout: P1363a with KCDSA Kaliski led the discussion of P1363a. Only those sections which provoked substantive discussion are included in the minutes. Rationale clause: Kaliski suggested a C.4 clause on auxiliary techniques. - Why SHA-1? - Why HMAC? - Why (or why not) the specific symmetric algorithms? Kaliski to provide preliminary text, and circulate to list before incorporating into document. Formats E.2.3.1: We need some new text on compressing elliptic curve points for curves over an OCEF. Bailey will investigate this. He isn't aware of any existing conventions for it. It would be legitimate to say "no compression method is specfied". Bailey will coordinate with author[s] of the IETF Internet-Draft which covers OCEF representations. Detailed review of document We went through the document section-by-section. Again, only substantive discussions are included in the minutes. Introduction: Kaliski will add introductory material. Overview: The Scope and Purpose are slightly altered from the PAR. Kaliski has altered them to be in the past tense. ACTION: Singer to check with IEEE that this is okay (or appoint an Editor officer to do it). ACTION: Singer to clarify on whether the amendment is purchased separately from the standard, and on whether we can insert errata or security updates into physical copies of Std 1363-2000. KCDSA Details were presented at the Santa Barbara meeting, August 1998. KCDSA is a DSA-like algorithm which doesn't require inversions for signing or verification, uses hash functions to generate the first part of the signature, and has provable security properties. The handout incorporates KCDSA into P1363a. Singer felt that the inclusion of KCDSA would at a minimum require the editor's accepatance, but that barring good editorial reasons he would recommend that the working group seriously consider its inclusion. ACTION: Lee to provide the working group with 1363-ized security considerations and rationale text. Whyte asked whether HAS-160 is being used by implementors and so should be included in conformance regions. Lee considered a general hash function with 160-bit output to be sufficient. Singer suggested adding a note to the effect that you can use HAS-160 and still conform to 1363, but that this hash function wasn't endorsed by the WG. Johnson thought that in the original paper the domain parameters were calculated differently from ordinary DSA -- there is a special form for the prime p, such that (p-1)/2 only has large prime factors. Lee said that this isn't necessary. Kaliski clarified that KCDSA works over arbitrary finite fields. ACTION: Solinas and Bailey to review the Gordon attack and come to some conclusion about the text we need to cover it. Vaudenay et al proved that this is secure in a weaker model than Random Oracle at PKC 2000. Kaliski also noted that the primitives have hash functions inside them, which is unusual for P1363 primitives. This can be corrected with editing. Vote on inclusion of KCDSA in P1363a Lee clarified that KCDSA version 2 is not interoperable with KCDSA version 1 deployments. There are about 100 Korean companies who have been using some variant of KCDSA over the last two years. Motion: The working group authorizes the editor to include KCDSA in the next draft of P1363a, provided that enough progress is made before that draft. Proposed Kravitz, Seconded Lieman. 3 for, 3 against, 3 abstentions. Defeated. P1363a Timeline Kaliski anticipates having a draft ready for review one month before the next meeting. The final draft, D8, will be issued following comments at the first meting of 2001, and can be submitted to IEEE for balloting before the May meeting. KCDSA could be included in draft D7, but this would make it it unlikely that D8 would be the final pre-ballot draft and would push the submission to the IETF back by a couple of months. The timeline depends on Okamoto responding on the security considerations questions, and on whether or not the working group is satisfied with the response. If we're not satisfied by February, we have the choice of either excluding EPOC/ESIGN or delaying. In this case KCDSA wouldn't have significantly delayed the standard. P1363b Singer raised the issue of whether or not we will proceed to P1363b. Mike Brenner (braid groups), Yuliang Zheng (signcryption) have expressed interest in contributing. Singer considers that we can raise a PAR between now and the next meeting, but we need to find an editor. Review of document: Annexes Annex D: D.4.3: Awaiting security considerations from Okamoto. Kaliski will write the scheme considerations, but Okamoto has to write the family considerations. Kaliski will contact Okamoto and request the security considerations in satisfactory form by December 1st. If they fail to arrive, the working group will exclude the techniques. If they arrive, the working group can consider whether the form is satisfactory, and possibly entertain a motion on whether or not to exclude the techniques from draft D7. ACTION: Kaliski to request security considerations by December 1st. Singer thanked Kaliski for his work on P1363a. The document is being finalized aggressively, and Singer anticipates being able to publicize this soon. Wrapping up Whyte reviewed the attendance list and stated that the following had attended for voting purposes (attended the meeting for more than one day of the two and a half days of the meeting) Bailey Brenner Dancanet Jablon Johnson Kaliski Kravitz Lee Lieman Mihailescu Nguyen Singer Solinas Stern Whyte Singer reviewed the action items. * Singer to make another call for primary editor * Kaliski to request security considerations by December 1st. * Kaliski to complete draft D7 by one month before the meeting (date TBD -- Kaliski's provisional deadline is January 15th). Singer reviewed the status of patent inquiries. He has contacted all the companies who have already sent us patent letters, and all those identified at previous meetings. According to the letters he sent, replies should be received by the start of March 2001. This means they won't affect balloting. ACTION: Whyte to try and get contact details for Rainer Rueppel. Singer will encourage written comments on D7, and set the agenda for the March meeting around written comments that have been received. The deadline for written comments will be one week before the meeting. Motion: Thank host: Proposed kaliski, seconded Stern. Passed by joyous unanimity. Adjourn: Proposed Kaliski, seconded Whyte. General phew.