PKIX Working Group Jongwook Park(KISA) Internet Draft Jaeho Yoon(KISA) Document: draft-ietf-pkix-sim-02.txt Seungjoo Kim(KISA) Expires : August, 2004 Sangjoon Park(BCQRE) Target category: Standard Track Jaeil Lee(KISA) Hongsub Lee(ISTF) Polk, Tim(NIST) February, 2004 Internet X.509 Public Key Infrastructure Subject Identification Method (SIM) Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of [RFC 2026]. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright (C) The Internet Society (2002). All Rights Reserved. Abstract This document defines Privacy-Enhanced Protected Subject Identifier (PEPSI) format for including a privacy sensitive identifier in the subjectAltName extension of a certificate. The PEPSI is an optional feature that may be used by a relying parties can determine whether the subject of a particular certificate is also the person corresponding to a particular sensitive Park, et. al. Expires - August 2004 [Page 1] INTERNET-DRAFT Subject Identification Method February 2004 identifier. 1. Introduction The key words "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document (in uppercase, as shown) are to be interpreted as described in [RFC2119]. A Certification Authority (CA) issues X.509 public key certificates to bind a public key to a subject. The subject is specified through one or more subject names in the "subject" and/or "subjectAltName" fields of a certificate. The "subject" field contains a hierarchically structured distinguished name. The "subjectAltName field" may contain an electronic mail address, IP address, or other name forms that correspond to the subject. For each particular CA, a subject name corresponds to a unique person, device, group, or role. The CA will not knowingly issue certificates to multiple entities under the same name. That is, for a particular certificate issuer, all currently valid certificates asserting the same subject name(s) are bound to the same entity. Where the subject is a person, the name that is specified in the subject field of the certificate typically reflects the legal name of the individual and affiliated entities (e.g., their corporate affiliation). In reality, however, there are individuals or corporations that have the same or similar names. It may be difficult for a relying party (e.g., a person or application) to associate the certificate with a specific person. This ambiguity presents a problem for many applications. In some cases, applications need to ensure that the subject of certificates issued by different CAs are in fact the same entity. This requirement may be met by including a "permanent identifier" in all certificates issued to the same subject, which is unique across multiple CAs. By comparing the "permanent identifier", the relying party may identify certificates from different CAs that are bound to the same subject. This solution is defined in [PI]. In many cases, such as a Social Security Number, a person or corporation's identifier is regarded as a sensitive, private or personal data. Such an identifier cannot simply be included as part of the subject field, since its disclosure to lead to misuse. Therefore, privacy sensitive identifiers cannot be included in certificates as plaintext. On the other hand, such an identifier is not actually a secret. People choose to disclose these identifiers for certain classes of Park, et. al. Expires - August 2004 [Page 2] INTERNET-DRAFT Subject Identification Method February 2004 transactions. For example, people may disclose their Social Security Number to open a bank account or obtain a loan. This is typically corroborated by presenting physical credentials (e.g., a driver license) which confirms the person's name or address. To support such applications in an online environment, relying parties need to determine whether the subject of a particular certificate is also the person corresponding to a particular sensitive identifier. Ideally, applications would leverage the applicants's electronic credential (e.g., the X.509 public key certificate) to corroborate this identifier, but the subject field of a certificate does not provide sufficient information. To fulfill these demands, this document defines the Privacy-Enhanced Protected Subject Identifier (PEPSI) format for including a privacy sensitive identifier in a certificate. When the subject of the certificate chooses to disclose the identifier and the relying party may verify the identifier. A party that obtains the certificate containing a PEPSI can not determine the privacy sensitive identifier without performing a brute force attack, and each certificate must be attacked separately. Furthermore, the subject can prove to the relying party that they are associated with a valid identification without disclosing the identifier. For example, a person could prove they possessed a valid social security number without disclosing the identifier itself. In addition, this document defines an Encrypted PEPSI(EPEPSI) so that the RA and CA can exchange sensitive identifier information without disclosing the identifier. This document is organized as follows: - Section 2 establishes security and usability requirements; - Section 3 provides an overview of the mechanism; - Section 4 defines syntax and generation rules. 2. Requirements 2.1 Security Requirements Given - Alice, a certificate holder, with an a sensitive identifier SIIa (such as her Social Security Number, SSN) - Bob, a relying party who will rely on knowing Alice's true SII - Eve an attacker who has Alice's certificate - An RA to whom Alice must divulge her PEPSI; and - A CA who will issue Alice's certificate. Park, et. al. Expires - August 2004 [Page 3] INTERNET-DRAFT Subject Identification Method February 2004 We wish to design a PEPSI, using a password that Alice chooses, that has the following properties: - Alice can prove her true SII, SIIa to Bob; - Eve has a large work factor to determine the Alice's SSN from her certificate, even if Alice chooses a weak password, and a very large work factor if Alice chooses a good password; - Even if Eve can determine SIIa she has an equally hard problem to find any other SII from any other PEPSI; that is,there is nothing she can pre-compute that helps every attack against a PEPSI, and nothing she learns from a successful attack that helps in any other attack; - The CA does not learn Alice's SIIa or her password; - The CA can treat the PEPSI as an additional name form in the "subjectAltName" extesnion with no special processing; and - Alice cannot find another SII, password combination that will allow her to use the certificate to prove a false SII to Bob. 2.2 Usability Requirements In addition to the security properties stated above, we have the following usability requirements: - When the PEPSI is used, any custom processing occurs at the relying party. Alice can use commercial off the shelf software (e.g., a standard browser) without modifications. 2.3 Solution The solution: Let PEPSI = H(H( P || R || SIItype || SII)) Then: 1. Alice picks a password, Pa, and gives Pa, SIIa to the RA. SIIa is composed of identifier type (SIItype) and identifier value SII. 2. The RA validates SIIa. 3. The RA generates a Random value R. 4. The RA generates the PEPSIa = H(H( Pa || R || SIItype || SIIa)). 5. The RA passes the PEPSIa to the CA which generates Alice's certificate including the PEPSI in the "subjectAltName" extension. 6. Alice sends Bob her Cert, as well as Pa, SIIa 7. Bob can get R from the PEPSI in the cert, PEPSIa, then compute H(H(Pa || R || SIItype || SIIa)) and compare it to the value in SIMa, thereby verifying SIIa. Park, et. al. Expires - August 2004 [Page 4] INTERNET-DRAFT Subject Identification Method February 2004 If Alice wishes to prove she has a valid identifier, without disclosing it, then steps 6 and 7 are as follows: 6. Alice sends intermediate value H(Pa || R || SIItype || SIIa)) and her certificate to Bob. 7. Bob can compute H(H(Pa || R || SIItype || SIIa)) and compare it to the value in PEPSIa, thereby verifying Alice's knowledge of Pa and SIIa. Eve has to exhaustively search the H(P || R || SIItype || SII) space to find Alice's SIIa. This is a fairly hard problem even if Alice uses a poor password, and a really hard problem if Alice uses a fairly good password. Even if Eve finds Alice's Pa, SIIa, pair or constructs a massive dictionary of P, SII pairs, it doesn't help find any other SII, because a new R is used for each PEPSI. 3. Procedures 3.1 Symbols The following cryptography symbols will be used in this document. H() Cryptographically secure hash algorithm. SHA-1[FIPS 180-1] or more secure hash function is required. SII Sensitive Identification Information. (e.g, Social Security Number or Maryland Driver License) SIItype Object Identifier that identifies the type of SII. P A user chosen password. R The 160-bit random number value generated by RA. PEPSI Privacy-Enhnaced Protected Subject Information. Calculated from the input value P, R, SIItype, SII using two iteration of H(). E() The public key encryption algorithm used by RA. Used for encrypting the PEPSI. EPEPSI Encrypted PEPSI. D() The public key decryption algorithm used by CA. Park, et. al. Expires - August 2004 [Page 5] INTERNET-DRAFT Subject Identification Method February 2004 Used for decrypting the EPEPSI. 3.2 SII and SIItype The user presents evidence that a particular SII has been assigned to them. The SII is composed of an alphanumeric string and has a type assigned as well. For closed communities, the SII type value (e.g., SSN or Social Security number) may be assigned by the CA itself. For interoperability, a SII type value should be registered with IANA. 3.3 User Chosen Password The user selects a password as one of the input values for the PEPSI. The strength of the password is critical to protection of the user's SII. User should be encouraged to select passwords that will be difficult to guess and long enough to protect against bute force attacks. Implementations of this specification MUST permit a user to select passwords of up to 28 characters. RAs SHOULD implement password selection rules to prevent user selection of trivial passwords. 3.4 Random Number Generation A RA generates a 160-bit random number, "R". A new R MUST be generated for each PEPSI in a certificate. Whenever a certificate or key needs to be updated, a new R SHOULD be generated and the PEPSI SHOULD be recomputed. Replicating the value of the previous PEPSI from a previous certificate permits an attacker to identify certificates associated with the same physical person, which may be undesirable. A Random Number Generator(RNG) meets the requirements defined in [FIPS 140-2] is strongly recommended. 3.5 Generation of PEPSI The PEPSI in the subjectAltName extension within the certificate identifies an entity even it has multiple names in its certificates. The unique value of the PEPSI MUST be derived from the designated inputs according to the following algorithm: PEPSI = H(H(P || R || SIItype || SII)) Note that the SII is known to a RA at user enrollment. For this specification, H() may be SHA-1 or SHA-256. Park, et. al. Expires - August 2004 [Page 6] INTERNET-DRAFT Subject Identification Method February 2004 The syntax and associated the OID for PEPSI are also provided in the ASN.1 modules in Section 4.2. 3.6 Encryption of PEPSI This section will establish procedures for encrypting a PEPSI and SII along with the user chosen password for transmission across a network. This may be required where the CA itself verifies SII before issuing the certificate. Encrypting PEPSI with the public key of CA MUST be derived from PEPSI along with SII according to the following algorithm: EPEPSI = E(SII || PEPSI) The syntax and associated the OID for EPEPSI are also provided in the ASN.1 modules in Section 4.3. 3.7 Certification Request As described above, the certification request message MAY contain the EPEPSI. [PKCS#10] and [RFC2511] are widely used message syntaxes for certification requests. An EPEPSI MAY be included in optional attributes for conveying attributes to the CA with additional information. Basically, PKCS#10 is composed of the entity name and public key. To satisfy this specification, EPEPSI SHOULD be included in the attribute field of 'CertificateRequestInfo'. In case of using the RFC2511(CRMF) for certificate request message, an EPEPSI SHOULD enter into the 'regToken' control defined in section 6.1 of [RFC2511]. 3.8 Certification A CA issue certificate including the PEPSI as contained in "GeneralName.Othername" field of "subjectAltName" extension. In an environment in which a CA verifies SII before issuing the certificate, a CA MUST decrypt EPEPSI first with its own private key according to the following algorithm. It then checks the decrypted SII. SII, PEPSI = D(PEPSI) Park, et. al. Expires - August 2004 [Page 7] INTERNET-DRAFT Subject Identification Method February 2004 4. Definition 4.1 SIM Naming Syntax This section specifies the syntax for SIM name form included in "subjectAltName" extension. The SIM is composed of the two fields, the hash algorithm identifier, and the value of the PEPSI itself. id-on-sim OBJECT IDENTIFIER ::= {id-on ?} SIM ::= SEQUENCE { hashAlg AlgorithmIdentifier, pEPSI OCTET STRING, -- hash of HashContent -- with algorithm hashAlg } 4.2 PEPSI This section specifies the syntax for PEPSI. The PEPSI is generated by performing the same hash function twice. PEPSI is generated over the ASN.1 structure HashConent. HashContent has four values: the user selected password, the authority chosen random number, the identifer type, and the identifier itself. id-on-sim-pepsi OBJECT IDENTIFIER ::= {id-on-sim 1} HashContent ::= SEQUENCE { userPassword BIT STRING -- user supplied password authorityRandom BIT STRING, -- RA chosen random number identifierType OBJECT IDENTIFIER, -- SIItype identifier UTF8String, -- SII } 4.3 Encrypted PEPSI This section describes the syntax for Encrypted PEPSI. The Encrypted PEPSI has two fields: identifier and PEPSI. id-on-sim-epepsi OBJECT IDENTIFIER ::= {id-on-sim 2} EncryptedPEPSI ::= SEQUENCE { identifier UTF8String, -- SII pEPSI OCTET STRING -- hash of HashContent } Park, et. al. Expires - August 2004 [Page 8] INTERNET-DRAFT Subject Identification Method February 2004 5. Example Usage of PEPSI Depending on a different security environments, there are possible three use cases with PEPSI. 1. When a relying party doesn't have any information about the certificate user. 2. When a relying party already have the SII of certificate user. 3. When a certificate user want to disclose his SII. For the use case 1, a user chosen password, P which only a user know MUST be sent to a relying party via secure commnuication. Together with the password, the certificate including the PEPSI must be transmitted. Then the relying party can obtain the user's SII from a RA. The relying party can verify that the subject of certificate issued by a CA is in fact the same entity who sends the password and the certificate. If comparing first two use cases, their overall procedure is almost same except that the SII isn't required by the relying party. Threfore, a certificate user transmit simply the password and the PEPSI included in his certificate. The rest of detailed procedure is the same as that of the use case 1. For the last speical use case that a certificate user want to disclose his SII, the only information sent by a ceritificate user is the intermediate value of the PEPSI, H(H(R || P || SIItype || SII)). Upon receiving of it, the relying party can verify the user by rehashing the value. 6. Security Considerations PEPSI is secure against the brute-force attack by using a 160-bit long random number generated by reliable RA. Although attacker is accurately able to guess a SII with partical information about sex, age and date of birth due to the short length of the SII, there is no way to verify whether the guessed SII is accurate or not unless the attacker can obtain both the user chosen password and the random number. In addition, since the PEPSI is based on SHA-1 that has cryptographically secure characteristic, it is impossible to find another SII, R, P that will generate same hash value. In case of birthday problem, the PEPSI can be cryptographically secure since it requires 2^80 where 160 is the bit-length of the hash value of SHA-1. Park, et. al. Expires - August 2004 [Page 9] INTERNET-DRAFT Subject Identification Method February 2004 7. Authors' Address Jongwook Park Korea Information Security Agency 78, Garak-Dong, Songpa-Gu, Seoul, 138-803 REPUBLIC OF KOREA Phone: +82-2-405-5432 Email: khopri@kisa.or.kr Jaeho Yoon Korea Information Security Agency Phone: +82-2-405-5434 Email: jhyoon@kisa.or.kr Seungjoo Kim Korea Information Security Agency Phone: +82-2-405-5440 Email: skim@kisa.or.kr Jaeil Lee Korea Information Security Agency Phone: +82-2-405-5300 Email: jilee@kisa.or.kr Sangjoon, Park BCQRE 467-12, Dogok-Dong, Kangnam-Gu, Seoul, 135-270 REPUBLIC OF KOREA Phone: +82-2-3453-1114 (Ext. 200) EMail: sangjoon@bcqre.com Hongsub, Lee Internet Security Technology Forum 78, Garak-Dong, Songpa-Gu, Seoul, 138-803 REPUBLIC OF KOREA Phone: +82-2-405-5200 EMail: hslee@kisa.or.kr Tim Polk National Institute of Standards and Technology 100 Bureau Drive, MS 8930 Gaithersburg, MD 20899 Email: tim.polk@nist.gov 8. References 8.1 Normative Reference Park, et. al. Expires - August 2004 [Page 10] INTERNET-DRAFT Subject Identification Method February 2004 [RFC2510] Adams, C. and S. Farrell, "Internet X.509 Public Key Infrastructure, Certificate Management Protocols", RFC 2510, March 1999. [RFC2511] Myers, M., Adams, C., Solo, D. and D. Kemp, "Internet X.509 Certificate Request Message Format", RFC 2511, March 1999. [RFC3280] Housley, R., Polk, T, Ford, W. and Solo, D., "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 3280, April 2002. [RFC2119] S. Bradner, "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2026] S. Bradner, "The Internet Standards Process - Revision 3", November 1996. 8.2 Informative Reference [PI] D. Pinkas, T. Gindin, "Internet X.509 Public Key Infrastructure Permanent Identifier", Internet-Draft, January 2004. [X.509] ITU-T Recommendation X.509: The Directory - Public-Key and Attribute Certificate Frameworks. 2000. [PKCS#10] RSA Laboratories, "PKCS #10: Certification Request Syntax Version 1.7", November 2001. [FIPS 180-1] Federal Information Processing Standards Publication (FIPS PUB) 180-1, Secure Hash Standard, 17 April 1995. [Supersedes FIPS PUB 180 dated 11 May 1993.] [FIPS 140-2] Federal Information Processing Standards Publication (FIPS PUB) 140-2, Security Requirements for Cryptographic Modules, 25 May 2001. 9. Intellectual Property Statement The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it Park, et. al. Expires - August 2004 [Page 11] INTERNET-DRAFT Subject Identification Method February 2004 has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. 10. Acknowledgments Bill Burr and Morri Dworkin have contributed significantly to work on the PEPSI concept and identified a potential security attack. Also their comments on the set of desirable properties for the PEPSI and enhancements to the PEPSI were most illumination. Also, thanks for Russell Housely, Stephen Kent for their contribution for this document. Appendix A. "Compilable" ASN.1 Module PKIXSIM {iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) id-mod-sim(?) } DEFINITIONS EXPLICIT TAGS ::= BEGIN -- EXPORTS ALL IMPORTS AlgorithmIdentifier, AttributeTypeAndValue FROM PKIX1Explicit88 {iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) id-mod(0) id-pkix1-explicit-88(1)} -- Arc for other name forms id-on OBJECT IDENTIFIER ::= { id-pkix 8 } -- Arcs for SIM, PEPSI, and EPEPSI id-on-sim OBJECT IDENTIFIER ::= {id-on ?} id-on-sim-pepsi OBJECT IDENTIFIER ::= {id-on-sim 1} Park, et. al. Expires - August 2004 [Page 12] INTERNET-DRAFT Subject Identification Method February 2004 id-on-sim-epepsi OBJECT IDENTIFIER ::= {id-on-sim 2} -- SIM SIM ::= SEQUENCE { hashAlg AlgorithmIdentifier, pEPSI OCTET STRING, -- hash of HashContent -- with algorithm hashAlg } -- PEPSI HashContent ::= SEQUENCE { userPassword BIT STRING -- user supplied password authorityRandom BIT STRING, -- RA chosen random number identifierType OBJECT IDENTIFIER, -- SIItype identifier UTF8String, -- SII } -- Encrypted PEPSI EncryptedPEPSI ::= SEQUENCE { identifier UTF8String, -- SII pEPSI OCTET STRING -- hash of HashContent } END Full Copyright Statement Copyright (C) The Internet Society (2003). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implmentation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING Park, et. al. Expires - August 2004 [Page 13] INTERNET-DRAFT Subject Identification Method February 2004 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." Park, et. al. Expires - August 2004 [Page 14]