IEEE P1363 Working Group for Public-Key Cryptography Standards Wednesday, May 31, 2000 Sheraton Dalton St, Boston, MA THURSDAY, JUNE 1, 2000 Morning Session In attendance: Ari Singer, Pitney Bowes (chair) Don Johnson, Certicom (vice chair) Dan Lieman, NTRU (treasurer, host) William Whyte, Baltimore (secretary) Dan Bailey, WPI Dan Brown, Certicom Lucien Dancanet, Citigroup (morning only) David Jablon, Integrity Sciences Gurgen Khachatryan, Cylink Burt Kaliski, RSA Security David Kravitz, Wave Systems Preda Mihailescu, ETH & MEC Consulting Satomi Okazaki, NTT MCL Leo Reyzin, MIT Allen Roginsky, IBM Dave Stern, Intel Approval of Agenda ------------------ Agenda was approved unanimously. Minutes of March Meeting ------------------------ The minutes as amended were approved unanimously. Std-1363-2000 status: --------------------- Singer reported that the 1363 document was in its final stages of editing. Jennifer Longman, the IEEE editor assigned to 1363, had completed her edits on the document and had sent them to Singer for final review. Reyzin had offered to lead the editing effort and Kaliski, Yin and Johnson had offered to contribute as well. Copies of the edited document were sent to each and the editing has begun. Reyzin commented that since the IEEE changed the numbering scheme for many of the algorithms, there was a serious risk that the meaning of the algorithms would be changed. P1363a status: -------------- Kaliski talked us through the changes made to P1363a since the last meeting. P1363a is presented as a delta to P1363. Johnson wondered if a full document would be easier to follow. Kaliski said that producing a delta is more consistent with IEEE standards, but that to make things easier he could include the section headings even for those sections that weren't changed, and possibly include more context for added table entries. He will consider the best way of doing this. Section 4: Johnson suggested we be consistent with the terminology for ISO signature standards. This identifies Signature Schemes with Full Message Recovery, Signature Schemes with Partial Message Recovery, and Signature Schemes with Appendix as separate schemes. Section 5: We deferred comments until the discussion of Bailey's contribution on arbitrary finite fields. Johnson commented that the supersuperscripts are very small -- r looks like '. Section 6: The main change to this section is the incorporation of PV scheme. Kaliski thanked Johnson and Brown for making it easy to incorporate the submission into the body of the addendum. The notation used for signatures with partial message recovery is M1 -- recoverable, M2 -- non-recoverable. There was no desire to change this. The DL domain parameters description has been updated to allow arbitrary finite fields. This should be systematic. Reyzin suggested striking the definition of q from section 6.1.2 and Kaliski agreed. Section 6.2.13 is very like 6.2.11. It might be possible to do more work and merge the two, as was done with the pre-signature primitives. 6.2.5, 6.2.7: added note to see Annex D.5.2.1. Kravitz recommended that we change "precomputation in advance of the signature generation" to "precomputation in advance of the availability of the message representative". 6.2.9: changed "discarded" to "securely deleted" in the note 6.2.10: added note about rarity of error output from NR signature primitive (there is possibility that c = 0). There was some discussion of this. In DSA the signature primitive can be defined so there is no possibility of an invalid output (an output that either can't be verified or can be verified by any public key -- in the case of DSA, r = 0 is invalid), because we can simply check for validity and loop back to the start of the primitive if necessary. In PV, looping back to the start of the signature primitive isn't sufficient; we need to loop back to the pre-signature primitive, and this must be handled at the scheme level. Reyzin pointed out that the definition of a signature scheme is that it always produces a valid signature. Kaliski will put in text indicating that the note is for information only. Section 7: The changes all parallel those in section 6. Brown asked that in the note in section 7.2.9 we write "ECSP-NR2 and ECSP-PV" instead of "ECSP-NR2/PV". Section 8: EPOC and ESIGN primitives were added, and will be discussed later. We now have four types of primitive in the family. IFEP-OU and EPOC are different names for the same thing. Kravitz felt that, since we were calling ESIGN ESIGN, we should call EPOC EPOC. Section 10: 10.1: added text about total message recovery and partial message recovery, and will add figures. Also added text on tradeoff between recovery & appendix (second para). Kaliski suggested changing "typically" to "potentially" in this text. Conformance region recommendations were updated in general; for PV, made it explicit that conformance may be claimed for total message recovery only. Johnson pointed out that in ISO, to claim conformance with message recovery, you must recover at least one bit. He would like a scheme-by-scheme analysis of the effects of leaving message recovery out of the message recovery schemes. 10.4.2 (DL/ECSSR): Converted presignature from octet string to bit string. Added note about error case. 10.5. (DL/ECSSR-PV): Will be discussed later in the meeting. Kaliski chose to separate this from other DL/ECSSR because: * It was submitted separately; * They treat the messages differently. Section 11: Main changes arose from adding references to EPOC and key validation. 11.4 (IFIES): Added this entire section. 11.3 (DL-ECIES): Added the note about using the same ephemeral keypair for multiple recipients. Kravitz asked about the introduction of the "message authentication code" technique. Kaliski explained that it's a new additional technique which is described in section 15. Section 12: 12: Updated to take into account possibility that message isn't an integer. Encoding methods used to output integer; now they can output octet string. 12.1.3 (EMSA3): This now calls EMSR3. 12.2.2 (EME2): Added this section. 12.3.2, 12.3.3: Renamed EMSR2 to EMSR3 to keep the ordering of IF before DL/ECDL. Johnson suggested moving PKCS#1 signatures to before PSS. Kaliski agreed to swap EMSA4 and EMSA3. 12.3.1 (EMSR1): For ISO compatibility, we might need to change octet strings to bit strings throughout. Johnson said that an implementation can conform to ISO with just bit strings. 12.3.2 (EMSR2): Added changes to handle PV. 12.3.3 (EMSR3): PSS uses octet strings; ISO SC27 has agreed to confirm to this but has always used bit strings. In reference to the hash function identification, Kaliski noted that ISO 9796 doesn't specify hash ids, but assumes 10118 ids. Reyzin pointed out that the note giving the hash ids is wrong. We broke for lunch. Afternoon: In attendance: Ari Singer, Pitney Bowes (chair) Don Johnson, Certicom (vice chair) Dan Lieman, NTRU (treasurer, host) William Whyte, Baltimore (secretary) Dan Bailey, WPI Dan Brown, Certicom David Jablon, Integrity Sciences Gurgen Khachatryan, Cylink Burt Kaliski, RSA Security David Kravitz, Wave Systems Preda Mihailescu, ETH & MEC Consulting Satomi Okazaki, NTT MCL Allen Roginsky, IBM Dave Stern, Intel 12.3.3.1 (Message encoding for PSS signature generation) Kaliski talked us through the changes in this technique. The encoded message is a combination of (masked) message stuff and (cleartext) technique identification stuff, and was originally as follows: | header | stuff | trailer | 1 byte 2 bytes The header and trailer contain identification stuff come from ISO 9796-2, following the agreement of the ISO 9796 WG to support PSS while keeping the header and the trailer. Header byte: 4b (no message recovery) or 6b (message recovery) Trailer bytes: 31 cc (SHA) or 33 cc (RIPEMD-160). The cc is necessary for Rabin disambiguation. Original PSS had no header or trailer. Header and trailer affect security proofs of relationship between forgery and ability to invert underlying function on an arbitrary input -- to be precise, they affect the ratio of the difficulty of forging to the difficulty of inverting. Three bytes of header means that general inversion costs 2^24 additional group ops (exponentiations) times the number of oracle queries. Kaliski argued that the structure of the recovered decoded message reveals whether or not message recovery is being used, and that there is no value in the hash function identifier (to be explained in detail tomorrow). The only useful cleartext in the encoded message is the final "c" nibble. Kaliski proposes using the "bc" byte, as this is the behaviour specified in ISO 9796 when the header cleartext byte isn't present. Talk through 12.3.3.1. The whole message and the salt have to be involved in computing the hash value H. M1 (rec) M2 (non-rec) | v +----------------------------+ (hash) | v v | _____________________________ v | len (M1) | M1 | H2 | salt | ______________________________ ----------------------------- | 00 ... 00 | 01 | M1 | salt | | ------------------------------ v | (hash) v | (XOR)<--------------(mgf)<---------+ | | v v | maskedDB | H | bc | = Message representative F. The data block containing len (M1) uses the hash of M2, rather than M2 itself, so you can complete verification within a hardware device without having to perform bulk hashing within that device. The input to verification is simply the signature and H2. If you have to hash M1 + M2 externally to the device, you need to perform the public key operation before you can get the data block to be hashed. At the PKCS workshop in Stockholm, some hardware vendors expressed a preference for the current approach. In the case of total message recovery, M2 vanishes and H2 becomes fixed as the hash of NULL. FDH is like this with no salt. There will be a paper at Crypto 2000 on the security of FDH. The requirement on the hash function is that it's collision resistant; it doesn't have to be a random oracle. Brown pointed out that if there is a collision between the hashes of M2, M2', then the signature on M1 || M2 is the signature on M1 || M2' for free. Kaliski said that M2 can be salted. Johnson suggested changing the rationale to point out that message recovery is generally only used with relatively small messages. Kaliski emphasized that other standards bodies are doing similar work, and we need to align with them and decide a definitive version of PSS relatively fast. Sections 13-15: Section 13: Added KDF2 based on X9.63. Useful because it outputs variable-length keys. Note that this is written in terms of bit strings, but calls functions whose input is defined in terms as octet strings. Section 14: Added reference to anticipated SHA-2. Section 15: Entirely new. Lengths are in bits for compatibility with X9.63. Annexes: Annex A: Changes are to take into account the use of arbitrary finite fields. A.7.8, note 1: Added as per last time's discussions. There is no patent note about it. Annex A contains several patented techniques already. Annex D: Updated notes on precomputation (note 1, section D.5.2.1). Will change "advance of signature generation" to "advance of availability of message representative". Updated note on ephemeral keypairs without availability of a PRNG (note 2, section D.5.2.1). Same change as above. Added reference to use of counter to avoid determinism, so that you don't end up unable to generate a signature. Reflects previous meeting's discussion. Encoding methods: Kaliski will look for expert review over the next few weeks rather than looking for immediate response in meeting. Updated discussion to take into account DLIES -- D.5.3.3. Kaliski will add extra context here. Kravitz suggested changing "message representative" to "message" in the final sentence of D.5.2.1. Annex F: More references have gone in. A few details will be added. Extra concerns: Johnson requested a note about why the salt length isn't necessary. Kaliski will add a note about why the MGF is tightly coupled to the hash function; this strengthens against hash function substitution attacks, as will be discussed tomorrow. There are some open questions about the structure of the document. * Should DL/ECIES be generalized to support other methods of protecting the message with the shared secret value Z? We discussed whether we should support a range of key derivation functions, and a range of ways of combining the key with the message to protect it. Johnson pointed out that DL-ECIES has a specific name in a specific context. The "I" which stands for "Integrated" might need to be removed. Singer worried that allowing too many options would lose the normative value of the standard. Johnson noted that X9.42 supports both the X9.42 and the X9.63 KDFs. The old KDF and the new KDF have different APIs. Kaliski will correct this in the next revision. * Should DL/ECSSR with EMSR1 be reorganized so that it can be defined in terms of the PV primitives, rather than having separate NR2 primitives? Kaliski will investigate. Remaining work: * Minor stylistic changes from IEEE. * Add more context. * Conformance updates. * Rationale updates -- need to remove rationale for no message recovery schemes. Would be a good thing to develop over the mailing list. * ASN.1 formats updates. Will rely on submitters to identify relevant ASN.1 * Security considerations for arbitrary finite fields and EPOC/ESIGN; will need a fair amount of work. Kaliski is relying on the submitters to write that text. Time-permitting work: * Diagrams. * Example methods for one-time keypairs for precomputation * Example methods for keypairs without an rng/prng. Both the latter two might need patent assurances. We have assumed that a bibliographic reference doesn't need patent assurances, but a recommendation of a specific method probably does. Arbitrary finite fields ----------------------- Bailey reviewed the work on arbitrary finite fields which is to be incorporated into P1363a. Elliptic curves over GF (2^m), m composite: Last meeting mentioned Hess, Gaudry, Smart's paper about attacks on ECDLP in F(2^m), m composite. Last meeting Bailey recommended excluding fields with composite m. In the absence of this attack, a typical value for composite m would be 176 = 16.11 (for efficiency reasons). Now a composite m must be around 512 for the same level of security as prime m around 160. ANSI and NIST have traditionally excluded these curves. Should we too? We discussed whether the attack was considered strong, and whether we should exclude techniques because other standards bodies had excluded them. Roginsky felt that the strength of the attack was not clear. He had previously voted against removing these curves from ANSI because the evidence against them was essentially hearsay. He would like proper peer review of the Hess et al. preprint, and would like to see the m composite curves retained here while there was a possibility they would turn out to be useful. Mihailescu felt the attack was likely to be extended. Singer suggested moving the discussion into Security considerations, as was done with Koblitz curves. Johnson wanted the new text to say that NIST and ANSI explicitly chose to exclude these curves. Bailey felt that it was out of line with IEEE's historical approach to exclude techniques simply because other bodies had, and suggested that in the meantime we mention the attacks in the security considerations. Section 5: We suggested several typographical changes: * change exponent r to something that looks less like a ' when supersuperscripted. * change lower-case p to upper-case P to denote an irreducible polynomial, to avoid ambiguity with p for "prime". * change "unique field" to "unique field (up to isomorphism)". 5.3.3: Odd characteristic extension fields are the ones that aren't even characteristic. Kaliski observed that GF (p) is subsumed in the general section on GF (p^m). Bailey agreed, and said the new text is compatible with the old GF (p) text when m = 1. The change to section 5.4 is because for ECC there are three distinct sets of behaviour for GF (2^m), GF (3^m), and all other GFs. 5.5.4: Added way to convert between field elements and octet strings; this conversion is densely packed. Annex A: Bailey had provided several definitions, which Kaliski had worked in inline. A.5.8: Title should be "over GF(q)", not "over GF (q^m)". A.7: The basis conversion text was supplied by Kaliski, so Bailey didn't cover it. A.9: Added Weierstrass equation for p = 3. A.10: Reminded people that everywhere we're doing operations in GF (p^m) *. Added EC operations for p = 3. Reference is Koblitz's Algebraic Aspects of Cryptography. We will also put a reference in this section. Mihailescu worried that the reader has to do too much work to work out what to do in GF (p). Bailey had considered including algorithms for GF (p) and GF (p^m) separately, but the text for the two sections would be identical. Khachatryan noted that references to binomial irreducibility in A.5.8 are to Koblitz's book, not the original papers. Bailey suggested that these references could be to specific statements in the book, which would conform with current practice when referring to (for example) the Handbook of Applied Cryptography. A.16.13: New, but non-controversial. A.17.2: Odd characteristic extension fields, like XTR, have ONB-type behaviour available. A.17.3.4: maybe too discursive: should be put in note. This is also where Kaliski embedded Bailey's definitions. Should also remove use of "we". A.17.3.6: Can use Extended Riemann Hypothesis to make this faster. Need to have omega -> omega + 1 at some point. Put in note that we expect this to terminate with a given order. A.17.3.8: Bailey has database of 5,500,000-odd OEFs and will transfer some into this document. This section should be A.17.3.7. Khachatryan noted that this section doesn't say anything about fast modular multiplication in these fields. We say that reduction is faster, but not multiplication. Bailey said that the design principle behind OEF is to pick p to be as big as possible, so you can use the built-in multiply instruction. In this case, the degree of the extension field will tend to be relatively low. We noted some typos: A.17.2: Missing paragraph mark between steps 1 and 2 in section A.17.2. A.17.3.2: Hyphen should be minus in step 3; step 2.1 should be step 3. A.17.3.7: The table splits across a page. Outstanding issues These are to be addressed by Bailey: * Gordon's attack on DSA case with special parameters. * Johnson's mention of use of DSA with canonical random parameters: this is more appropriate for GF (p); when we use OEFs, we pick the parameters for system reasons not security reasons. We need to address security issues arising from the cyclotomic polynomials associated with the subfield. * Compelling reason for odd composite fields in EC case: there are no known attacks in the odd composite case. We considered recommending that people choose a prime extension degree. Singer considered this a warm fuzzy, which we have tended to put in security considerations if we have included them at all. Kaliski observed that the techniques in Hess et al don't extend from 2^m to p^m. Bailey agreed to mention this in the text. Mihaelescu is establishing tables of DSA parameters (where the subgroup is exactly 160 bits) and of type 2 OEFs. Bailey has a table of 5,000,000 OEFs. Singer considered putting in the algorithm used to build the table rather than the table itself. Bailey plans to provide pseudocode for Lenstra's method for generating OEFs with large subgroups. He is not convinced by the use of canonical random parameters. Johnson pointed out that Semaev's article gives another condition to be taken into account when generating DSA parameters. Bailey will take that into account and include appropriate text when generating the DSA parameters. We finished for the day at 4.56 pm. Friday Start: 8.43 In attendance: Ari Singer, Pitney Bowes (chair) Don Johnson, Certicom (vice chair) Dan Lieman, NTRU (treasurer, host) William Whyte, Baltimore (secretary) Dan Bailey, WPI Dan Brown, Certicom Lucien Dancanet, Citigroup (morning only) David Jablon, Integrity Sciences Gurgen Khachatryan, Cylink Burt Kaliski, RSA Security David Kravitz, Wave Systems Preda Mihailescu, ETH & MEC Consulting Satomi Okazaki, NTT MCL Leo Reyzin, MIT Allen Roginsky, IBM Dave Stern, Intel Singer reviewed the agenda for the day: - EPOC & ESIGN - PV Signatures - Patent and other administrative issues - Inclusion criteria for 1363a, 1363.1, etc. (to be short) - Discussion of final inclusion - EPOC-3, PSEC-3 - Hash function identifiers - Submission process - Future work/plans. New handout: note on security of EMSR2 (Dan Brown). EPOC/ESIGN ---------- Kaliski presented on EPOC/ESIGN. ESIGN The following sections have been added to P1363a for ESIGN: 8.1.3.4: ESIGN keypairs. 8.2.12: Signature generation primitive. 8.2.13: Verification primitive. 10.3: Extension of IFSSA to include ESIGN. 8.1.3.4 ESIGN uses the approximate eth root problem for security. It is included in Integer Factorization techniques because factorizing the modulus recovers the private key. Public key: n = p^2 . q; k = (bitlength of p) - 1; e, 8 <= e < n Private key: p, q. We don't specify if p can be longer than q. The message representative f is the same length as p, but when verifying we compare on (log2 q) bits. Reyzin wondered if it was worth using the Chinese Remainder Theorem when signing, and how this affected the form of the key if so. Kaliski and Reyzin felt the CRT offered less benefit in this case than for RSA, because e might be small, and because we still have to do operations mod p^2. Kaliski also pointed out that, in contrast to RSA, knowledge of the modulus but not its factorization doesn't allow private key operations. He will consider whether the text should be altered to reflect this. 8.2.12 Reyzin wondered if the r generated in step 1 of section 8.2.12 needed to be random, or simply non-repeating. There is a typo in the conformance region text in 8.2.12: should change "RSA" to "ESIGN". 10.3 In section 10.3, we need to establish the encoding method to be used with ESIGN to produce the message representative f. Additional considerations We also need security considerations text to cover: - factoring integers of this type - approximate eth root problem - encoding methods - is there a reduction between approximate eth root instances? EPOC The following, more complex, changes needed to be made for EPOC. 8.1.3.3: definition of OU keypairs. 8.2.10: OU encryption primitive. 8.2.11: OU decryption primitive. 11.2: added text to cover IFEP-OU, IFDP-OU. 11.4: first draft of IFIES, the integrated encryption scheme which uses IFEP-OU. 12.2.2: added new encoding method. 8.1.3.3 Public key: n = p^2 . q, length k = length of p, value of u st the order of (u mod p^2) is p; v = v_0 ^n mod n. Private key is (p, L(u_p)) where L(u_p) = (u_p -1)/p Reyzin felt that the text about the order of u could be rephrased, and that it's not clear what must be made secret and can be made public. He would like to see clear guidance on values that aren't explicitly part of the private key, such as u_p and v_0. He also wondered whether L(u_p) needs to be relatively prime to p and q. In general, it would be nice to see a good key generation primitive. 8.2.10, 8.2.11 The working group doesn't yet fully understand the "magic" that makes encryption and decryption work. 12.2.2.1, 12.2.2.2 Some corrections need to be made: * Although l' is an input, it isn't used in the processing. * Step 4: mLen should be m. The encoding scheme differs from previous encoding schemes in that it outputs two integers (f,r), where other encoding schemes have only one output f. Likewise, the decoding operation requires r to obtain reassurance that decryption has happened properly. (result of decryption is self-consistent). So each of the encryption and decryption primitives require an extra input. This is not yet fully integrated into section 11.2.2. 11.4 The scheme gains its non-malleability properties by requiring the message recipient to perform what is effectively an additional public-key encryption following decryption. The encryption function used to create the ciphertext -- in this case, mask generation + XOR -- does not have to preserve integrity, because a hash of the message is included in the encrypted message. There was concern about the use of MGF + XOR to mask the message. Reyzin said that MGF is usually used as a random oracle rather than a stream cipher. He would oppose the current wording. Singer is concerned that the standard should not specify arbitrary symmetric encryption functions. We also wondered whether we should have explicit exponentiation in the middle of scheme specification, as in section 11.4.3, step 10. Whyte also observed that the scheme doesn't seem to support one-pass processing. Pintsov - Vanstone Signatures ----------------------------- Dan Brown presented on Pintsov-Vanstone signatures. The following sections have been added to P1363a: 6.2.9: DL Pre-signature primitives. 6.2.12: DL Signature primitive. 6.2.12: DL Verification primitive. 7.2.9: ECDL Pre-signature primitives. 7.2.12: ECDL Signature primitive. 7.2.12: ECDL Verification primitive. 10.5: Signature Scheme 12.3.2: Associated encoding methods. Brown gave an overview of the method and how it integrates into the document. A signature is generated as follows: - Split message into M1, recoverable; M2, non-recoverable. - scheme takes recoverable part and adds "prefix padding" P for redundancy. - Choose randomizer u (one-time private key). - get one-time public V from u. - combine P || M1 and V in some way (using MGF). - Output of masking is C, output of hashing C || M2 is H. - combine u, H, s in signing equation which outputs a further integer, d. How this is organized in 1363a draft: - EMSR2 (12.3.2) tells you how to produce C given V, M1 - ECSP-PV (7.2.12) tells you how to produce d given "presignature" (u, V), h, private key s. - ECPSP-PV/NR (7.2.9) tells you how to produce u, V. - hashing C || M2 is covered at the scheme level (10.5). 12.3.2.1 We suggest MGF1 for masking function, with V as the seed. Or could use KDF2 and symmetric encryption, which might be more consistent with X9.63. The masking is simply to combine a commitment to the one-time key with a commitment to the message, and the two could as easily be concatenated. We discussed the redundancy. Whyte suggested that the padding method used in PKCS#5 and S/MIME should be used instead of the method given. Reyzin requested text that noted that the maximum amount of padding is 256 bytes. He was concerned that an attacker could vary the message M and V such that the masked message stays constant. Brown felt that if the padding added sufficient redundancy, it was unlikely that an attacker could find two (V, T) pairs which gave the same C. The handout discusses this issue in its security considerations section. Reyzin requested more discussion of the need for redundancy in M2, and in M1+M2. We also need to define a way of measuring redundancy in this context, probably by specifying a range of acceptable padding lengths. Corrections: * change references to 10.6.1 to 10.5.1; 10.6.2 to 10.5.2. Primitives and Schemes We considered generating u and v deterministically. Brown said that u should be non-repeating for distinct hash values, and so should be derived from the entire message. Kaliski noted that if H = 0 the private key vanishes from the signing equation (we discussed this while discussing section 6 yesterday). He recommended that the verification primitive reject if H = 0. Patent issues: -------------- Kaliski reviewed the use of patented techniques in P1363a. The working group doesn't have to judge whether patents cover techniques; instead it should try and establish if patents exist, to avoid surprises for people who use the standard. Theoretically the group will include non-patented techniques instead of equivalent patented ones in the standard. In practice, no two techniques are exactly equivalent. Areas of techniques in P1363a: - arbitrary finite fields - NR2 primitives - PV primivites - precomputation of one-time key pairs - deterministic generation of one-time key pairs - OU primitives - ESIGN primitives - IFSSA with ESIGN - IFSSA with new encoding methods: EMSR3 (= PSS), EMSR4 (= PKCS1) (note that the names of these two methods will be swapped). Note: We're not trying to make judgments on which patents apply, we're trying to work out where patents might exist and sources of information for those patents. No legal judgment implied! We established the following contacts for IP in the following fields: - arbitrary finite fields: Mihailescu; NTT (for techniques patented by Itoh and Tsuji); Certicom; Entrust. - NR2: Certicom, Entrust. - PV: Certicom, Pitney Bowes. - precomputation: Micali, Naccache (using "coupons"), NIST. - deterministic computation: Naccache. - OU, ESIGN: NTT, RSA (is the modulus form covered by the Multi-prime RSA patent?). Reyzin felt that we should finalise P1363a before contacting NTT, as we already have a letter of clarification from them about the version of their techniques in a previous version of P1363a. - IFSSA w. EMSR3, EMSR4: RSA, University of Southern California. - Basis conversion: RSA, Certicom - DL/ECSSR: Related to NR, so Certicom, Entrust. - DL/ECSSR-PV: Pitney Bowes, Certicom - IFSSR-PSS: University of Southern California, RSA - IFES-OU: NTT - DL/ECIES: X9.63, possibly with generalizations. Bellare-Rogaway, Abdalla, University of Southern California, Certicom - IFIES: NTT - EMSA3: USC - EMSA4 (PKCS#1): RSA - EME2: NTT - EMSR1 (DL/ECSSR): Entrust, Certicom - EMSR2 (DL/ECSSR-PV): Pitney Bowes, Certicom - EMSR3 (PSS): University of Southern California - KDF2: University of Southern California - MAC1: IBM. (HMAC is not believed to be encumbered) Lunch! In attendance: Ari Singer, Pitney Bowes (chair) Dan Lieman, NTRU (treasurer, host) William Whyte, Baltimore (secretary) Dan Bailey, WPI Dan Brown, Certicom David Jablon, Integrity Sciences Gurgen Khachatryan, Cylink Burt Kaliski, RSA Security David Kravitz, Wave Systems Preda Mihailescu, ETH & MEC Consulting Satomi Okazaki, NTT MCL Leo Reyzin, RSA Security Allen Roginsky, IBM Dave Stern, Intel EPOC-3, PSEC-3 --------------- Okazaki presented on EPOC-3 and PSEC-3. EPOC-3 and PSEC-3 are based on the same generic underlying method as the previously submitted EPOC and PSEC algorithms. Of these, EPOC-1 has been accepted for P1363a subject to writing up; PSEC was not accepted. EPOC-3 EPOC-3 is derived from the primitive encryption function known as the OU function. It has provable security and semantic security (it is chosen-ciphertext secure in the random oracle model), and is almost as efficient as the underlying OU function (in comparison, EPOC decryption takes two function evaluations). The underlying problem is the Gap-High-Residuosity problem. The output of encryption is a triple (c1, c2, c3). c1 is mod n; c2 is symmetric encryption of message; c3 is hash of (c1, random R, m). Ciphertext is longer than in EPOC-1 by the length of c3. The output of decryption is plaintext or NULL. Decryption is faster than equivalent RSA op; encryption is slower (with small RSA exponent). The algorithm will be submitted to ISO in September. Patent applications have been made in Japan, USA, UK, France, and Germany; NTT will provide the usual licensing letter. We discussed EPOC-3 before moving on to PSEC-3 (this discussion refers to notation used in the submission). Bailey wondered if there was a way to speed up the exponentiation to p-1 mod p^2. The check on the length of R' is necessary because we assume that the length of the inputs to the hash function is fixed; this gives potential ambiguity at the boundary betweeen R' and the message. Kaliski noted that EPOC-3 seemed to be suitable for one-pass processing. Reyzin wondered if the symmetric cipher needed to be secure against passive or active attacks. Patent applications in Japan, USA, UK, France, Germany; usual licencing stuff. Kaliski asked if the technique was intended to replace EPOC in P1363a. Okazaki will clarify. PSEC-3 Very similar to EPOC-3, but uses EC Elgamal primitive instead of OU primitive. Almost as efficient as basic EC Elgamal (previously decryption was twice as slow). PSEC-3 is chosen-ciphertext secure in the random oracle model, so long as the Gap Diffie-Hellman assumption holds and the symmetric encryption algorithm is secure against passive attacks. The execution time is two hashes longer than EC Elgamal for both encryption and decryption. It's more than 3 times faster than EC-Cramer-Shoup (but makes stronger assumptions -- RO as against Cramer-Shoup's Decision Diffie-Hellman). Singer noted that x_T doesn't exactly cover all possible values of R. Kaliski said that it gives away one bit of R. Whyte suggested the algorithm should output "error" rather than null string on error. We considered the differences between this technique and EC-IES using X9.63. Kaliski said that PSEC-3 can be considered a different way of combining the shared secret with the message. Whyte noted that X9.63 uses a keyed hash, and PSEC-3 uses a hash of the key. Reyzin and Kaliski noted that the assumptions are different (Gap Diffie-Hellman against Decision Diffie-Hellman). Kaliski asked if PSEC-3 is intended as a submission for inclusion in P1363a. Okazaki will clarify. Hash function identifiers: -------------------------- Kaliski presented on the use of hash function identifiers in the message encoding schemes that produce message representatives for use in signature schemes. In the absence of hash function identifiers, it is conceivable that two different documents can have the same signature if the hash of document A with hash function A is the same as the hash of document B with hash function B. The threat model is that an attacker can reverse hash function B and so can produce at will a document B which will produce the same hash as document A hashed with (strong) hash A, and then get the victim's signature on document A with hash A and pass it off as a signature on document B with hash B. If the message representative includes a hash function identifier, the attack is not possible. Kaliski demonstrated that the hash ID prevents an attack from reusing an existing signature. But: - Do not protect against signature forgery with a weak hash function. - A verifier who accepts weak hash function can always be victimized by the attacker. Some presented schemes with hash ID are forgeable, and the ones that aren't don't have provable security properties. RSA-style key distribution with Diffie-Hellman-style keys --------------------------------------------------------- Khachatryan presented on this subject. He had previously presented it to the Second INTAS International Seminar on Coding Theory and Combinatorics in Essen, Germany, in 1997. Given a discrete log public key, g^x mod p, to send a secret g^r, send (g^x)^r. The private key owner can calculate ((g^x)^r)^1/x = g^r. Jablon said that this is previously due to Hughes. Whyte noted that the secret is g^r, but the sender needs to know r, so this method can't send an arbitrary secret. Bailey suggested that Khachatryan submit the method to P1363 website. Future Plans ------------ Singer led a discussion on future activities for the working group and the study group. Topics to consider for P1363b include: - might contain PKV - KCDSA - Arazi's inversionless scheme - XTR - ACE - EPOC-3 and PSEC-3. - Identification schemes - Signature schemes based on identification (Schnorr, GQ) Stern suggested that we consider performance analysis. Bailey reckoned it would be immensely difficult to do this work, and we'd probably be sued. We discussed how the group might deal with new submissions. In the past, submissions have needed specific backers, and whether or not a high-quality technique is included in the standard depends greatly on the energy put in by its backers. Singer is going to write to our sponsor about P1363a; in the course of this letter he may have to justify the omission or inclusion of particular schemes. Reyzin said that if the standard, particularly in the registry form, is to be a listing of Good Things, we should be more energetic in looking for the Good Things. Singer felt that the best we can do is to put in place a framework that forces us to be unbiased, and details exactly what a submitter has to do to get into the standard/registry. Jablon emphasized that the registry will need a filtration process. Various people expressed concern that if the registry is adopted, the group will lose the effect of people who came to argue for one technique being able to contribute to the discussion of another one. Several people felt that the meetings are educational in their own right, and that that will encourage contributors to attend for the entire meeting, not just discussion of their own technique. Kravitz noted that not getting sent to conferences is an oracle for when to leave your company. We discussed the specific techniques suggested above for inclusion. Reyzin said that once we consider including techniques that don't have a widely deployed base, we need clearer selection methods. Could value be added by comparing techniques? Kaliski pointed out that to compare techniques means we're behaving like the European NESSIE group, which is full-time and funded by the EU. We're not so cut out to do evaluation; we might need to do documentation. If we were to fill a registry with schemes that NESSIE could use that might be useful. Summing up, Singer said that we should feel good. 1363a is going pretty well, and will be relatively on time. The next meeting will be in August, after Crypto. Singer will look for volunteers for the November meeting. He thanked everyone for coming to the meeting. Motion: Thank host: proposed Singer. seconded Whyte. Carried by acclamation. Motion: Adjourn. Proposed Bailey. seconded Whyte. Carried by acclamation. Attendance for voting purposes: Ari Singer, Pitney Bowes (chair) Don Johnson, Certicom (vice chair) Dan Lieman, NTRU (treasurer, host) William Whyte, Baltimore (secretary) Dan Bailey, WPI Dan Brown, Certicom Lucien Dancanet, Citigroup (morning only) David Jablon, Integrity Sciences Gurgen Khachatryan, Cylink Burt Kaliski, RSA Security David Kravitz, Wave Systems Preda Mihailescu, ETH & MEC Consulting Satomi Okazaki, NTT MCL Leo Reyzin, RSA Security Allen Roginsky, IBM Dave Stern, Intel