IEEE P1363 Working Group for Public-Key Cryptography Standards Meeting Minutes (Unapproved) Wednesday, March 7, 2001 MITRE, Bedford, MA Attendance: Ari Singer, NTRU (Chair) Daniel Lieman, NTRU (Treasurer) Mike Brenner, MITRE Lucien Dancanet, Citigroup David Jablon, Integrity Sciences Burt Kaliski, RSA Laboratories David Kravitz, Wave Systems Joe Silverman, NTRU Handouts: Meeting notice and agenda. Working Group Meeting Summary (unapproved) Working Group Meeting Minutes (unapproved) P1363.1 Draft 1 with discussion topics NTRU Signature Scheme Slides Password-based techniques overview slides Extended Password Key Exchange Protocols Immune to Dictionary Attack Letter from Burt Kaliski on P1363a draft D7 Letter from Dan Bailey on OCEF changes in P1363a Notes on changes from P1363a draft D7 to draft D7.1 P1363a Draft D7.1 Quantum Cryptanalysis of Hidden Linear Functions Meeting started 1:00 pm. 1. Approval of working group agenda Due to weather conditions, the meeting started after lunch on Wednesday. The agenda was shifted around, but nothing was omitted. Section numbers reflect numbers on meeting announcement (the items were taken out of order, however). MOTION 1: Approve agenda. Proposed Kravitz, seconded Jablon. Passed by acclamation. 2. Approval of working group minutes and summary Reviewed November working group minutes and summary. Various editorial changes made. Decided to add information about Bleichenbacher paper now that it is publicized. ACTION: Singer and Whyte to amend minutes to include Bleichenbacher presentation. Discussed removing some of the material related to DSA that is affected by this attack. No action recommended. MOTION 2: Approve minutes and summary as amended: Proposed Lieman, seconded Jablon. Passed unanimously. 3. Officer Reports Chair (Singer): Most of the issues are related to the different documents and will be reported later in the meeting. 1) Wording on P1363a PAR seems fine. Need clarification about desired change. 2) The P1363a document, when complete, must be purchased separate from the base document. Errata may be inserted into copies of the original document. 3) Will report on IP during P1363a discussion 4) Has not discussed balloting with sponsor yet. Will begin process after meeting if the group feels we are ready. 5) Pil Joong Lee reiterated his offer to host a meeting this year in Korea 6) Would like the group to discuss issues with voting and attendance on Friday Treasurer (Lieman): 1) The group has approx. $3500 in the bank, most of which is due to the IEEE. 4. Presentations for P1363.1 4a. NTRU Signature Scheme (NSS) Presentation by Joe Silverman on NSS. This scheme was submitted to the working group shortly before the meeting. Handouts were passed out. 5. Review of draft of P1363.1 Lieman led discussion about questions posed to the WG in his cover letter to D1 of P1363.1 There was discussion about the way you generate r (the blinding value) in NTRU. It was decided that this is a security parameter and needs to be agreed on by the two parties using the scheme before the operations take place. In the new method of defining schemes, it must be unambiguously defined in the scheme each time it is used (explicitly or implicitly). Silverman commented that you need to choose R from a hash function from the plaintext. Question 1: Should we call the family SV or SV/NTRU? There was general agreement that the family itself would be called SV, but that particular algorithms such as NTRU, NSS and others proposed might have different types of parameters from each other. Question 2: Is the organization of the document the way we want it to be? There was general agreement that P1363.1 organization/format is on the right track. There was discussion about when the random value is generated for NTRU. There was general agreement to change the way the scheme and primitive works. The random should be removed from the primitive in SVEP and put in at the scheme level. Question 3: How are schemes to be specified? To make a scheme complete, you need: 1) Scheme options 2) Security parameters 3) Domain parameters 4) Inputs Discussed how to couple all of the NTRU parameters. This should be included in the security considerations section. The group agreed to plan on a vote to include NTRU in P1363.1 at the next meeting 6. Action items for P1363.1 ACTION: Lieman to update P1363.1 by 1 month before the next meeting ACTION: Lieman to prepare group to vote on inclusion of SVEP-NTRU at the next meeting. 10. Presentations for P1363.2 10a.WETICE í97 paper: Extended Password Key Exchange Protocols Immune to Dictionary Attack David Jablon presented on the different kinds of password-based methods that exist to date. 11. Discussion about P1363.2 Kravitz asked about the distinction between letting the server have a hash of the password or not. We need to understand the attack models to know whether an attack that breaks these schemes would already be broken because an attacker can probably get at the information stored on the server anyway. Singer wonder if we could have some overriding "balloons" that cover most of these different techniques instead of picking a few from the list of available techniques. Characteristics of password (how it is generated) may cause a problem in the scheme No new draft of the P1363.2 document was available for this meeting. 12. Action items for P1363.2 ACTION: Jablon to get the next draft out that shows the structure from the last meeting. To be done by late April. ACTION: Jablon to obtain official submissions and updates from other submitters on techniques for P1363.2. ACTION: (Ongoing) Jablon to help lead discussions on baseline for comparison of techniques in P1363.2. Rationale section should be more complete. What are the differentiators? Thursday, March 8, 2001 MITRE, Bedford, MA Started around 9:00 Attendance: Ari Singer, NTRU (Chair) Mike Brenner, MITRE David Jablon, Integrity Sciences Burt Kaliski, RSA Laboratories David Kravitz, Wave Systems David Stern, Intel 7. Update on P1363a document Singer asked what the issue was that we had with the PAR. Kaliski said that the PAR stated that the IEEE P1363 project was not complete (instead of is not) ACTION: Singer to review specific change with IEEE ACTION: Singer to ask IEEE about patent issues with AES that we need to obtain ñ can we get reasonable and non-discriminatory (from Hitachi). ACTION: Singer to get clarification about the meaning of reciprocity from NTT? **Patent status: 1) Note from Hugh Williams that he has no further patent issues 2) Hitachi reiterated claims about SHA-1 and RIPEMD-160 3) RSA has previously submitted some patent materials on basis conversion and has indicated they will be sending a new letter shortly if there are any additional issues. Kaliski stated that he did not think there were any. 4) NTT claims patent coverage on EPOC and ESIGN with a free license on the basis of reciprocity. 5) Entrust sent letter on NR (#EP 0639907) offering reasonable and non- discriminatory licensing. They also pointed out that Certicom holds patent 5,600,725 in the US regarding this technique. Singer asked if we are getting ready to ballot P1363a and if he should contact Don Wright (Chair, MSC) after the meeting? We discussed later the timeline for P1363a. Kaliski reviewed the status of coordination with other standards bodies. The group reviewed changes made to get to Draft 7 and Draft 7.1 Kaliski reviewed changes from D6 to D7. Changes included the following among others: 1) Reorganized annex D 2) Added symmetric encryption and hashing info and others Kaliski reviewed plans for changes in the future. The group went through the list of discussion topics listed on Burtís sheet. 8. Detailed review of P1363a draft (part 1) The group decided that it would be too time consuming to review the draft line by line and this had already been done to some extent at the Fort Meade meeting. The plan is to publish a proposed draft between meetings and have comments and reviewing done remotely. At the meeting, we could address any serious unresolved issues if necessary. Otherwise, the vote for approval could take place via e-vote. The group discussed the use of hash functions, MACs, symmetric encryption and encoding methods. It was agreed that what is included in the draft currently (with some minor modifications) should be sufficient. 9. Presentations to Working Group 9a. Update on Braid Group Cryptography Brenner said that progress was made to answer the working group's questions about braid groups. There is a braid group scheme that will use a symmetric key for the encryption after a fast public-key key exchange. Public-key encryption (without the use of a symmetric key) might be slow with braid groups -- independent research is being done to determine how fast braid group encryption is. Brenner passed out a paper on quantum computing. He stated that the authors of the paper say that it is possible to break any cryptosystem based on what they call a "hidden linear form" in quantum polynomial time. The authors state in particular that this would include problems based on discrete logs, elliptic curve discrete logs and factoring. Brenner said that braid groups might turn out not to be susceptible to these attacks because of their non-abelian nature, but research is required to find out. There was general discussion about state of the art quantum computing techniques. There is no current threat to modern cryptosystems using quantum computers. Brenner stated that he believes that quantum computing could become a serious threat in about 10 years, assuming that new quantum hardware continues to be invented which continues to increase the number of coherent qbits. This is not a current emergency as the experts agree that there will be plenty of warning before such an attack could be mounted. Brenner discussed a method for doing quantum programming. It uses expansion methods to make every operation invertible (using Junk bits for instance), which is a requirement for quantum programming. BREAK FOR STUDY GROUP Friday, March 9, 2001 MITRE, Bedford, MA Attendees: Ari Singer, NTRU (Chair) Dan Bailey, NTRU (am only) Mike Brenner, MITRE Wei Dai Burt Kaliski, RSA Laboratories David Kravitz, Wave Systems Satomi Okazaki, NTT David Stern, Intel Started at 9:00 am. 13. Update on related standards activities Burt Kaliski reported about efforts on other standards and coordination of P1363a with those standards. ISO 18033 ñ specifies some public-key encryption schemes ñ Victor Shoup ISO 15946 ñ Omnibus ECC standard ñ PV Signatures recently added ISO 9796-2 ñ PSS with message recovery ñ Chris Mitchell There is an issue with hash function identification Agreed to allow the possibility of allowing hash ID if ISO supports it X9.63 just balloted 16. Discussion of major issues I) Supporting techniques The group discussed about MAC, Hashes and Symmetric Algorithms. Other techniques not included in the standard will still be supported. No additional work or techniques are needed for P13631. II) DL/ECIES Reviewed DL/ECIES scheme Discussed security considerations for small subgroup attacks on recipient private key 1) Add key validation considerations to discussion of encryption schemes in annex D 2) Amend DL/ECIES to select vs. generate the (u,v) key pair and add a note explaining that you might not have to generate a new one every time. 3) Mailing list discussion on including v in the KDF is planned. Should add text in annex D on non-malleability. a) Maintain input w/SEC-1 in stream cipher case b) Allow v as an optional input c) Conversion issue for v needs to be addressed 4) Recommended in block cipher case, append length of label when using as an input to the MAC 5) Recommend adding a note about handling bit string messages in block cipher case. 6) Encourage development of block cipher modes w/ labels ACTION: Brenner and Stern offered to help Kaliski with diagrams for P1363a techniques. III) Odd characteristic extension fields Bailey discussed the Vaudenay attack and the SNFS. Use cyclotomic polynomials to factor p^m ñ 1 to see if there is a good r (e.g a prime r around 2^160). Talked about function field sieve (for m >= (log p)^2) and number field sieve (for log p > m^2) (FFS and NFS). Decided to move OCEF material out of section 16 and fill section 17 with OCEF ACTION: Kaliski and Bailey to write approximately 8 sub-sections for section 17 (key and domain parameters). IV) EPOC and ESIGN Review of the OU and ESIGN schemes. Not aligned with 14888-3, but they have a correction that is in process. (ESIGN) 15. Detailed review of P1363a Detailed review was already done at the last meeting (mostly) and will be carried out offline on the final drafts. There should not be too many dramatic changes before then. 14. P1363a timeline This section includes discussion about balloting (item 17 on the agenda). Action Items 1) Draft 7.1 to be published March 12 2) Questions answered by end of March 3) Draft D8 to be published April 3 (ballot candidate) 4) Draft D8Reviewed during April and list of new changed compiled 5) E-vote on D8 with changes planned for April 30 - May 10 - including summary of P1363a (provided by Kaliski). 6) Meeting May 16-18 (Paris) tentatively recommended ACTION: Singer to write introduction ACTION: Singer to ask for host of next meeting ACTION: Kaliski to prepare draft for balloting and summary for vote. 18. P1363b Singer asked if there are any new offers for P1363b. Can the group still absorb this? There are few members that attend regularly that are not editors or officers. There are no offers yet to edit P1363b and the registry format document. Official Attendance for the meeting (must have attended at least half of the meeting (1 day): Mike Brenner, MITRE Wei Dai David Jablon, Integrity Sciences Burt Kaliski, RSA Laboratories David Kravitz, Wave Systems Satomi Okazaki, NTT Ari Singer, NTRU David Stern, Intel MOTION 3: Adjourn. Proposed Stern, seconded Kravitz. Passed unanimously.