IEEE P1363 Working Group for Public-Key Cryptography Standards Meeting Minutes Wednesday, March 13, 2002 Nicollet Island Inn, Minneapolis, MN Attendance: William Whyte, NTRU (Chair) Ari Singer, NTRU (Secretary) David Jablon, Phoenix Technologies (Treasurer) Burt Kaliski, RSA Laboratories Handouts: March 2002 Teleconference Minutes (P1363.2) Draft Agenda Chair's Report Voter List August 2001 Draft Meeting Minutes P1363.1 Draft 4 RSA Laboratories Cryptobytes, Vol. 5, No. 1 The meeting was called to order at 9:35 a.m. 1. Approval of agenda ===================== There was not sufficient attendance at this meeting for quorum, so the meeting could not be officially called to order and no motions could be passed. These minutes therefore represent the minutes for an ad hoc P1363 working group meeting. 2. Discussion about public-key encryption techniques ==================================================== Whyte yielded the floor to Kaliski to lead the discussion of DL/ECIES. Kaliski reviewed the general model of DL/ECIES. Allowing the ephemeral public key to be optionally included in the KDF enables a better proof of security, but is not consistent with all existing specifications. This has been settled by having a DHAES mode where the ephemeral public key is included in the KDF and a non-DHAES mode in which the ephemeral public key is not included. Shoup has proposed a new framework for 18033-2 public-key encryption. This is a different way to view the modes for DL/ECIES. DEM stands for data encapsulation mechanism - this mechanism uses symmetric operations and a shared secret key. KEM stands for key encapsulation mechanism - this is used for agreeing on (or transporting) the key to be used for the symmetric operations. There are three DEMs that are described for use in 18033-2: DEM1 - Most robust approach, which is a symmetric key encryption under the first part of the key. The MAC key need only be good enough to be used once securely. The encoding must include both the label and the length of the label in the encoding parameters. DEM2 - Omits the length of the label L for the encoding. Otherwise it is the same as DEM1. DEM3 - Omits the length of the label L and the symmetric key encryption (SKE) is defined to be XOR (it is strongly recommended that m be fixed length). Shoup pointed out an attack on DEM3 that if you know some of the middle bits of the message, you can truncate the message to set those middle bits to be the (known) MAC key used on a shorter encrypted message. Knowing the MAC key also allows an opponent to modify the label. Previously we had discussed the fact that you can change the length of the label and set some bits of the label equal to the last bits of the ciphertext. This doesn’t work on DEM3 because the MAC key would be changed. For DEM2, this might be an issue as long as c decrypts correctly. This can be avoided in DEM2 by requiring that the length of the label be fixed. Kaliski included comments about the DEM3 attack in his ballot comments. There are 4 combinations of DEM: 1) Stream cipher not in DHAES mode (this is basically DEM3). The group agreed to recommend fixed length M and give a reference to Shoup’s attack. 2) Stream cipher with DHAES mode (which is sort of a DEM4) because it is an XOR with the length of the label included. The MAC key is placed first followed by the XOR key. The group agreed to recommend that we specify that the MAC key be placed first in the KDF. 3) Block cipher not in DHAES mode – no change recommended. 4) Block cipher in DHAES mode – no change recommended. We reviewed the changes to the document Kaliski proposed in response to the ballot comments as described in the above discussion. 3. Other P1363a ballot comment discussions ========================================== ACTION: Burt to pursue Certicom and Pitney Bowes with regards to patents on Pintsov-Vanstone signature scheme. Kaliski suggested that Manger’s comments about error handling can be resolved by putting all of the error handling into step 12. There was some discussion about whether making this change makes conformance different for the technique. This does appear to be a change in conformance, but an old implementation that doesn’t have the operations or output conformant, but has other mechanism in place that make it "non-observable" would still be satisfactory. Kaliski will change the note to address the issue of conformance if this kind of attack "is not a concern." Addressing ballot comments from Schlafly: There was a comment about the use of the word "proof." The group agreed that we should just add more words that talk about what it means to have a " security proof." The document should be changed from saying "proved secure" or "proof of security" to saying "security proof" and describe what a security proof is in annex D. The term security proof seems to be a more well understood term that the others. DL/ECIES issues have already been discussed. Comment about the fact that we include a patented method of point compression. In the interest of completing the standard, we felt that we should defer this discussion to future revisions (e.g. P1363b). Using uncompressed form seems to be a reasonable work around to avoid patents. (NOTE: This issue was discussed further on Thursday) Comment to remove signatures with message recovery. There is related standards work on some of these techniques and there is limited interest in message recovery as opposed to no interest. Agreed that message recovery should stay in the document. Comment to remove EME1. Agreed to add a sentence in the security considerations that the security bounds have been shown to be weak in OAEP. However, it was agreed not to remove EME1. Addressing ballot comments from IEEE: The IEEE comments are basically editorial. Kaliski agreed to propose several motions to resolve these comments. We enjoyed a leisurely lunch . . . 4. Discussion about P1363.2 =========================== Whyte yielded the floor to Jablon. SRP-4 has been specified in an Internet draft in the IETF – Draft is called draft-jablon-speke-00.txt. This technique is also mostly specified now in IEEE P1363.2. Jablon reviewed the construction of SRP-4. He stated that he believes that there is a patent pending from Phoenix. One of the motivations for proposing this technique is that it helps to cover the patent issues. The group discussed what the criteria are for inclusion in the document. There should be some compelling reason to include a technique. All the other general considerations such as performance, IP, other standards and deployment should be taken into account as well. The group reviewed the current draft. There was some discussion about the definitions and what their purpose was and how they should be used. Jablon will continue to revise them. There is a new ISO project geared toward key establishment mechanism based on weak secrets (probably going to be 11770-4) proposed by someone in the UK – this is a national body proposal. The working group might consider a joint meeting with the ISO ad hoc meeting at Crypto ‘02 this year. Jablon walked the group through the changes that were made from the last time. Diffie-Hellman is used frequently in this document. Discussed whether 1363 should be a mandatory read for P1363.2. Agreed to leave references in and specify the techniques that are critical to implementing the standard. There was some discussion about the goals of schemes. Schemes traditionally specified techniques to arrive at an agreed key. New protocols (and schemes) do the key agreement plus key confirmation. Unilateral commitment scheme have only one party committing knowledge of a password. The proof being revealed in the wrong direction first breaks the trust. Bilateral commitment does not have this problem. Phil MacKenzie may be submitting a proposal that may require a modification to the current model that we are working under. The group agreed that there should be a requirement that the PRF be specified within the scheme. There was some discussion about the distinction between a protocol and a scheme. Jablon mentioned that the use of ECC is a little bit different in this document than in P1363. Ended discussion for the day at 5:00 pm. Thursday, March 14, 2002 Nicollet Island Inn, Minneapolis, MN Attendance: Ari Singer, NTRU (Secretary - Acting Chair) David Jablon, Phoenix Technologies (Treasurer) Burt Kaliski, RSA Laboratories Jim Hughes, StorageTek 5. Key Encapsulation ==================== Singer yielded the floor to Kaliski to discuss key encapsulation. Key Encapsulation presentation joint work by Burt Kaliski and Russ Housley. Housley was going to be presenting this at the S/MIME meeting at the IETF the following week. Key Encapsulation seems to be more common use of public-key encryption these days rather than using it to just encrypt/decrypt directly. They are recommending the transition to a new model. Limitations of old model include: Message length - limited Malleability - does not protect message integrity Mathematical properties - related messages may encrypt to related values Modeling – DH doesn’t fit well Traditional remedies are techniques such as PKCS #1 & OAEP. Message length is still bounded with these techniques and DH needs its own separate method. The new remedy is to establish two independent layers: Public-key layer – establishes a symmetric key Symmetric-key layer – protects data Public-key layer is used to generate a ciphertext that corresponds to a key by generating the key within the public-key operation. The other party regenerates the secret key from the ciphertext. The RSA example is basically the encryption and decryption of a random seed value. The shared key is the result of a key derivation function on the seed. Note that there is no integrity protection or special checking on the seed in the public-key layer. This is conducive to using the random oracle model (look at calls to encryption/decryption function). For Diffie-Hellman, the random seed is used to generate and ephemeral key to be combined with the other party's public key. The shared key is the result of a key derivation function of the concatenation of the ephemeral public key and the shared secret. The security of this is based on the decision Diffie-Hellman. There was some discussion about the security properties of the DH method. Including both the ephemeral key and the shared secret improves the provability because it prevents the simulator from having to call the DDH oracle many times each time it wants to respond to a request. The technique used for the symmetric-key layer depends on the overall objectives. For encryption only, symmetric encryption may be used. For key transport, encrypt a key and integrity protect with an optional label. ANSI X9.44 draft has an "AES Key Wrap" technique. For general messages, use encryption and integrity protection. There was some discussion about the use of key encapsulation as it relates to SSL/TLS. Key encapsulation is encrypting of pre-master secret + KDF to produce the master secret. Many standards use this technique in some form. There are plans to propose this new concept for several standards, particularly for use of RSA with AES keys. X9.44 may be shifting to the KEM (key encapsulation method) model. Standards that proposals might be made to include: ANSI X9F1 P1363 (if there is a P1363b) ISO/IEC 18033-2 PKCS #1 (to be proposed) S/MIME (being proposed) SSL/TLS (sort of) Kaliski stated that RSA does not hold or intend to apply for patents on these particular techniques. Hughes briefly presented his idea from a previous year on combining RSA encrypt, decrypt and DH to provide similar functionality. 6. Braid Group Discussions ========================== Hughes first reviewed braid groups and the techniques of two braid group algorithms. He is not the author of either of these algorithms. A braid group is built from n different strands. The crossover of two strands has an inverse. The multiplication operation is concatenation. Two problems based on braid groups are: Word problem – Given two words a and b, are they equal? There are algorithms that solve this with low polynomial work (n log n). Conjugacy problem – Given two words a and b, is there a word c such that a can be conjugated by c into b (with a word problem equivalence)? The conjugacy problem was posed by Emil Arten in 1938 and is claimed to be "known hard." The conjugacy search problem states that given an a and b that are known to be conjugates, can one find a conjugate? The Korean braid cryptosystem uses a private word x and x^-1 that only touches the "top" strands. The public word a has all strands. The other private word y touches only the "bottom" strands. One can add one's public key to the other party’s private key to obtain a shared secret. Algorithm proposed by Arithmetica is based on a system of known conjugates. The public word A_i is the conjugate of a public word a_i with some fixed secret c. The secret c may be a selection of the other party’s a_i. The other party uses a fixed d. The common agreed key is c*d*c^-1*d^-1. Hughes stated that it was recently proven that the braid group is linear in a representation that is on the order of an n^2 by n^2 matrix for the number of strands. "Faithful linear form" or Kramer-Laurence representation is at least injective (it is believed by some to be bijective). The Burau representation for braid groups is on the order of n by n. It is a mapping with a non-trivial kernel (i.e. there are two unequal words that map to the same representation mod the kernel). This means that the kernel is not "faithful". Hughes described an attack whereby using the parameters for the Arithemtica algorithm specified at RSA 2001, it is possible to take a Burau representation and map the keys in and out without them being affected by the kernel. Looking at the Burau representation of the unknown c, the values always ended up with non-zero elements only within a certain band of the diagonal. The method used doesn’t always solve it correctly, but it does solve it most of the time (e.g. 90%*95% for each side). So the attack works in the 60% range on all keys in the specified parameter set. There was no analogous attack known on the keys for which this attack was unsuccessful. Hughes recommended that this attack needs to be taken into consideration for specifying recommended parameters. Hughes described a length attack of adding a tangle at the end and seeing whether the canonical representation ends up getting longer or shorter. If a method is found to continuously make the representation shorter, then you may be able to break the key. 7. CryptoBroker Discussion ========================== Hughes presented a self-service web site that was created for the purpose of promoting the exchange of information about crypto algorithms. Algorithms that are coming to P1363 usually need to be published somewhere and often there are limited forums to present proprietary and patented techniques. Cryptobroker was designed to allow proponents of algorithms to post the information on the web site and compare it to other algorithms. This should provide a way for companies to get information together and filter things out themselves. It is intended as a supplement to the other places where you can learn about algorithms. Submitters can put in their own page. CryptoBroker would be willing to accept the P1363 standards group as an advisory board to help direct where this site goes in the future. The group discussed whether the successful implementation of CryptoBroker might make the public-key registry unnecessary. There is a lot of data that needs to go with a registry entry. We discussed whether we want to try to make it like a full registry entry or not. Techniques might be submitted to the working group for consideration and CryptoBroker would be willing to make the content available to P1363 to make changes and give advice on the postings. ACTION: Hughes to bring this issue up to the list. 8. Other standards ================== Hughes mentioned that the IEEE Technical Committee for Information Assurance (TCIA) – Storage Security Working Group was recently formed. This is a storage encryption standard. The intent is to specify methods including an encryption algorithm, an integrity algorithm and key management. There is a Common Criteria protection profile for this. Some of the difficult issues are that it is very difficult to provide random access to protected data, it is difficult to provide the service with absolutely no storage overhead and rekey is complicated. The group is looking for cryptographers and people who will help with solving these problems. Bob Cole is the chair of the TCIA. 9. P1363a (revisited) ===================== After further discussion about the point compression ballot comment, Kaliski suggested that we should bring Schlafly’s comment on point compression to the larger working group and discuss obtaining a patent assurance letter from Certicom regarding their technique. The group should also consider adding Schlafly’s proposed alternative, which Schlafly asserts is unencumbered and which he claims offers performance advantages. The group agreed to bring these issues first to the mailing list and then perhaps to e-votes. 10. P1363.1 Discussion ===================== Singer reviewed the current draft of P1363.1 with the group. There was some discussion about whether NTRUEncrypt uses the Fujisaki-Okamoto form within the scheme itself. If there is no easy way to generalize the FO techniques and include them as an endoding method, it may make more sense to keep the FO techniques combine together in the scheme operation itself. The recommendation was made to change the pseudo-random number generator terminology to pseudo-random octet stream generators. Singer drew a diagram on the board similar to the diagrams in P1363a for NTRUEncrypt. This diagram should be added to the draft. Several minor editorial changes were reviewed and some additional changes were recommended. Sub-clause 6.4.4 should be reviewed for correctness. An informative section should not be called from a normative section and it appears that the value a(1) is used before a is computed. The current draft separated EME4 into two separate encoding methods. The NSS algorithm was removed in the current draft. A form of public-key validation and pseudo-random number generation methods were also added to the draft. The group is still expecting that there may be additional submissions to P1363.1. There was no further discussion on P1363.2 and no additional items raised. The group would like to thank StorageTek and Jim Hughes for their gracious hosting of the meeting. This meeting still counts toward voting membership. The following people were counted as having officially attended this meeting for voting purposes: Jim Hughes, David Jablon, Burt Kaliski, Ari Singer, William Whyte Ad hoc meeting adjourned at 2:45 pm.