PKIX Working Group Jongwook Park(KISA) Internet Draft Jaeil Lee(KISA) Document: draft-ietf-pkix-sim-03.txt Hongsub Lee(KISA) Expires : January, 2005 Polk, Tim(NIST) Target category: Standard Track July, 2004 Internet X.509 Public Key Infrastructure Subject Identification Method (SIM) Status of this Memo By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. 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. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "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 Notice Copyright (C) The Internet Society (2004). 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. Park, et. al. Expires - January 2005 [Page 1] INTERNET-DRAFT Subject Identification Method July 2004 The PEPSI is an optional feature that may be used by a relying parties to determine whether the subject of a particular certificate is also the person corresponding to a particular sensitive 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 lead to misuse. Therefore, privacy sensitive identifiers cannot be included in certificates as plaintext. Park, et. al. Expires - January 2005 [Page 2] INTERNET-DRAFT Subject Identification Method July 2004 On the other hand, such an identifier is not actually a secret. People choose to disclose these identifiers for certain classes of 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 SIIa - Eve an attacker who has Alice's certificate Park, et. al. Expires - January 2005 [Page 3] INTERNET-DRAFT Subject Identification Method July 2004 - An RA to whom Alice must divulge her SIIa; and - A CA who will issue Alice's certificate. 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 SIIa 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'a 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 except the case where the CA needs to validate the SII passed by the RA. - 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'a, 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 SIM = R || PEPSI where PEPSI = H(H( P || R || SIItype || SII)) Then: 1. Alice picks a password P, and gives P, SIItype, and SII to the RA. 2. The RA validates SIItype and SII. 3. The RA generates a random value R. 4. The RA generates the SIM = R, PEPSI where PEPSI = H(H(P || R || SIItype || SII)). 5. The RA passes the SIM to the CA which generates Alice's certificate including the SIM as a form of otherName from the GeneralName structure in SubjectAltName extension. Park, et. al. Expires - January 2005 [Page 4] INTERNET-DRAFT Subject Identification Method July 2004 6. Alice sends Bob her Cert, as well as P, SIItype, and SII. 7. Bob can get R from the SIM in the certificate, then compute PEPSI' = H(H(P || R || SIItype || SII)) and compare SIM' = R || PEPSI' to the value in SIM, thereby verifying SII. 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(P || R || SIItype || SII)) and her certificate to Bob. 7. Bob can get R form the SIM in the certificate, then compute H(intermediate value) and compare it to the value in SIM, thereby verifying Alice's knowledge of P and SII. Eve has to exhaustively search the H(P || R || SIItype || SII) space to find Alice's SII. 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 P, SIItype, SII pairs or constructs a massive dictionary of P, SIItype, 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 are defined in this document. H() Cryptographically secure hash algorithm. SHA-1[FIPS 180-1] or more secure hash function is specification 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(). Park, et. al. Expires - January 2005 [Page 5] INTERNET-DRAFT Subject Identification Method July 2004 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. 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. The SIItype is an OID which defines the format and scope of the SII value. 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 SIM. 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. See [FIPS 112] and [FIPS 180-1] for selecting security criteria for password and an automated password generator algorithm that randomly creates simple pronounceable syllables as passwords. 3.4 Random Number Generation A RA generates a 160-bit random number, R. A new R MUST be generated for each SIM in a certificate. Whenever a certificate or key needs to be updated, a new R SHOULD be generated and the SIM SHOULD be recomputed. Replicating the value of the previous SIM 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. Park, et. al. Expires - January 2005 [Page 6] INTERNET-DRAFT Subject Identification Method July 2004 3.5 Generation of PEPSI The SIM in the subjectAltName extension within the certificate identifies an entity even if it has multiple names in its certificates. RAs MUST calculate the unique value of the SIM withe the designated inputs according to the following algorithm: SIM = R || PEPSI PEPSI = H(H(P || R || SIItype || SII)) The SII is known to a RA at user enrollment. One of SHA-1 or SHA-256 MUST be used for ensuring the integrity of PEPSI. Note that the P, SIItype, and SII passing from the end entity to the RA SHOULD be protected. The syntax and associated the OID for SIM are also provided in the ASN.1 modules in Section 4.1. Also, Section 4.2 describes the syntax for PEPSI in the ASN.1 modules. 3.6 Encryption of PEPSI This section describes procedures for encrypting the SIItype, SII and SIM including the user chosen password for transmission across a network. This may be required where the CA itself verifies SII before issuing the certificate. To meet this requirement, RAs SHOULD encrypt the SIItype, SII, and SIM with the CA's public key. Therefore, RA MUST acquire the CA's public encryption certificate although the way of obtaining it is not covered in this document. EPEPSI = E(SIItype || SII || SIM) The syntax and associated the OID for EPEPSI are 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. [RFC2314] and [RFC2511] are widely used message syntaxes for certification requests. Basically, PKCS#10 is consists of a distinguished name, a public key and a optionally a set of attributes, collectively signed by the end entity. The EPEPSI SHOULD be included in the attribute field of 'CertificateRequestInfo'. Park, et. al. Expires - January 2005 [Page 7] INTERNET-DRAFT Subject Identification Method July 2004 In case of using the RFC2511(CRMF) for certificate request message, an EPEPSI SHOULD be included in the 'regInfo' field defined in Section 3 of [RFC2511]. 3.8 Certification A CA issue certificate containing the SIM as a form of otherName from the GeneralName structure in "SubjectAltName" extension. In an environment in which a CA verifies SII before issuing the certificate, a CA decrypts the EPEPSI with its own private key according to the following algorithm. It then validates that the SII value is correct. SIItype, SII, SIM = D(EPEPSI) 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 three fields, the hash algorithm identifier, the authority chosen random value, and the value of the PEPSI itself. id-on-sim OBJECT IDENTIFIER ::= {id-on ?} SIM ::= SEQUENCE { hashAlg AlgorithmIdentifier, authorityRandom BIT STRING, -- RA chosen radom number -- used in computation of -- pEPSI 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. The 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. HashContent ::= SEQUENCE { userPassword BIT STRING, -- user supplied password authorityRandom BIT STRING OPTIONAL, -- RA chosen random number Park, et. al. Expires - January 2005 [Page 8] INTERNET-DRAFT Subject Identification Method July 2004 identifierType OBJECT IDENTIFIER, -- SIItype identifier UTF8String, -- SII } 4.3 Encrypted PEPSI This section describes the syntax for Encrypted PEPSI. The Encrypted PEPSI has three fields: identifierType, identifier, and PEPSI. EncryptedPEPSI ::= SEQUENCE { identifierType OBJECT IDENTIFIER -- SIItype identifier UTF8String, -- SII sIM OCTET STRING -- SIM } 5. Example Usage of SIM Depending on a different security environments, there are three possible use cases with SIM. 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, SII and 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 SIM must be transmitted. Then the relying party can get R from the certificate. 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, P, and the 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(R || P || SIItype || SII). Upon receiving of it, the relying party can verify the user by rehashing the value and comparing it with SIM in the certificate. Park, et. al. Expires - January 2005 [Page 9] INTERNET-DRAFT Subject Identification Method July 2004 6. Security Considerations A cryptographically secure hash function such as SHA-1 and SHA-256 must be used for maintaining the integrity of the PEPSI since the security of the PEPSI by composing hash value of R, SIItype, and SII is totally depending on hash function. Specifically, it is impossible for an attacker to find user P, authority random number, and SII which generate the same value of the SIM since SHA-1 requires 2^80 work factor where 160 is the bit-length of the hash value of SHA-1. In addition, a fairly good password is needed to protect against the brute force attacks on H(P || R || SIItype || SII) space. Due to the short length of the SII, it is likely that an attacker can reasonably guess it with partial information about gender, age, and date of birth. Therefore it is important for users to select a fairly good password in order that an attacker is unable to verify whether the guessed SII is accurate or not unless he collects all input values for SIM. 7. IANA Considerations [TBD] 8. Appendix. "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-epepsi OBJECT IDENTIFIER ::= {id-on-sim 1} Park, et. al. Expires - January 2005 [Page 10] INTERNET-DRAFT Subject Identification Method July 2004 -- SIM SIM ::= SEQUENCE { hashAlg AlgorithmIdentifier, authorityRandom BIT STRING, -- RA chosen radom number -- used in computation of -- pEPSI pEPSI OCTET STRING, -- hash of HashContent -- with algorithm hashAlg } -- PEPSI HashContent ::= SEQUENCE { userPassword BIT STRING, -- user supplied password authorityRandom BIT STRING OPTIONAL, -- RA chosen random number identifierType OBJECT IDENTIFIER, -- SIItype identifier UTF8String, -- SII } -- Encrypted PEPSI EncryptedPEPSI ::= SEQUENCE { identifierType OBJECT IDENTIFIER, -- SIItype identifier UTF8String, -- SII sIM OCTET STRING -- SIM } END 9. References 9.1 Normative Reference [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. [RFC2314] Kaliski, B., "PKCS #10: Certification Request Syntax Version 1.5", RFC 2314, March 1998. Park, et. al. Expires - January 2005 [Page 11] INTERNET-DRAFT Subject Identification Method July 2004 [RFC2119] S. Bradner, "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 9.2 Informative Reference [PI] D. Pinkas, T. Gindin, "Internet X.509 Public Key Infrastructure Permanent Identifier", Internet-Draft, July 2004. [FIPS 112] Fedreal Information Processing Standards Publication (FIPS PUB) 112, "Password Usage", 30 May 1985. [FIPS 180-1] Federal Information Processing Standards Publication (FIPS PUB) 180-1, "Secure Hash Standard", 17 April 1995. [FIPS 181] Federal Information Processing Standards Publication (FIPS PUB) 181, "Automated Password Generator(APG)", 5 October 1993. [FIPS 140-2] Federal Information Processing Standards Publication (FIPS PUB) 140-2, "Security Requirements for Cryptographic Modules", 25 May 2001. 10. Acknowledgments Seungjoo Kim, Jaeho Yoon(KISA), Sangjoon Park(BCQRE), Bill Burr, Morri Dworkin(NIST), and ISTF(Internet Security Technical Forum, http://www.istf.org) 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. 11. 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 Jaeil Lee Korea Information Security Agency Phone: +82-2-405-5300 Park, et. al. Expires - January 2005 [Page 12] INTERNET-DRAFT Subject Identification Method July 2004 Email: jilee@kisa.or.kr Hongsub, Lee Korea Information Security Agency 78, Garak-Dong, Songpa-Gu, Seoul, 138-803 REPUBLIC OF KOREA Phone: +82-2-405-5100 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 12. Full Copyright Statement Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78 and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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. Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights 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; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat 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 implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any Park, et. al. Expires - January 2005 [Page 13] INTERNET-DRAFT Subject Identification Method July 2004 copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf- ipr@ietf.org. Park, et. al. Expires - January 2005 [Page 14]