Internet Draft                                   Paul Hoffman
draft-ietf-pkix-okid-00.txt                      VPN Consortium
January 26, 2002
Expires in six months

               Out-of-Band Key Identifier Protocol (OKID)


Status of this memo

This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.

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.


Abstract

In general, certificates need not be communicated with communication or
storage media that are integrity-secure or authentic. This is because
certificates are digitally signed and users are expected to validate the
signatures using configured trust anchors. However, distribution of
trust anchor certificates, or distribution of self-signed end-entity
certificates, requires a mechanism for establishing the authenticity of
the public key contained in such certificates.

When a user receives a certificate of this sort through a communication
or storage medium that is not known to be integrity-secure and
authentic, the user needs to verify the value of the public key
contained in the certificate over an integrity-secure, authentic,
out-of-band channel. Since certificates are signed, independent
verification of the value of the public key value contained in the
certificate, and the correct association of that key with the identity
of the  issuer identity contained in the certificate, enables the user
to verify that the certificate authentic (by verifying the certificate
signature using this key). The Out-of-Band Key Identifier Protocol
(OKID) is a user-friendly key identifier that can be used for the
out-of-band verification of the public key contained in a self-signed
certificate.


. Introduction

A typical scenario for using digital certificates is that an end user or
system will acquire at one or more CA certificates for use as a trust
anchors. Trust anchor certificates are usually self-signed (that is, the
Issuer and Subject names are the same). It is common to acquire trust
anchor certificates through channels that are not integrity-secure or
authenticated such as unprotected data streams or web sites. In such a
scenario, an attacker could substitute a certificate of his own
choosing, for example swapping in his or her own public key and changing
the signature.

In order to detect and reject such attacks, a user receiving a
self-signed certificate must use a method to verify that the public key
in the certificate is correctly bound to the identity specified in the
certificate. One means of achieving this is to communicate the hash of
the public key over a communication path which the user believes to be
integrity-secure and authenticated. (The public key itself is considered
too large a value for users to conveniently and reliably communicate.)
The same requirements apply to self-signed end-entity certificates
acquired under similar circumstances.

The OKID provides a standard representation for out-of-band human
communication of the hash of a public key, in support of the security
requirements described here. The OKID is designed to be easy to transmit
through out-of-band mechanisms. Specifically, it is easy to read on the
telephone, assuming that both parties understand the names of the ASCII
alphabetic characters. It is also easy to type on an ASCII keyboard.


. OKID format

An OKID string has the following format:

WW-XXXX-XXXX-XXXX-XXXX

where "WW" is the type identifier and the Xs are characters from the
hash string. The dash characters in the OKID string MUST be used. All
characters in the OKID string MUST be uppercase. However, a system that
is receiving an OKID MAY accept the OKID string in uppercase or
lowercase and MAY accept the string without hyphens.

2.1 Type identifiers

This document defines two OKID profiles. The identifiers for these
profiles are:

EE - PKIX end entity certificates

CA - PKIX certification authority certificates

Other profiles may be defined later in other RFCs (see the IANA
Considerations appendix). Each new profile will define its own
two-letter type identifier.

2.2 Hash string

The hash string consists of 16 characters that represent an 80-bit hash
of a key. The hash string is created using the following steps:

. Let A equal the SHA-1 [SHA1] hash of the public key being identified.
This will always be 160 bits. For PKIX certificates, the material that
is hashed is only the contents the bit string of the key (just the
contents of subjectPublicKey); the material to be hashed is not the
ASN.1 structure of the bit string (do not include the ASN.1 length in
the hash), and it is not the full structure (do not hash the full
SubjectPublicKeyInfo).

. Let B equal the left-most 80 bits of A (assuming big-endian
representation of A).

. Let C equal the Base32 transformation of B (see Table 1 below). This
will always be 16 characters.

. Let the output be the first four characters of C, followed by a
hyphen, followed by the second four characters of C, followed by a
hyphen, followed by the third four characters of C, followed by a
hyphen, followed by the last four characters of C.

The Base32 algorithm is as follows:

. If there are no more bits in the input, stop.

. If there are fewer than five bits in the input, stop with a fatal
error.

. Remove the left-most five bits from the input and call this value X.
Look up X in Table 1, and add the corresponding character for X to the
string C.

. Go to step 1.

Table 1: Base32 conversion

Bits   Character        Bits   Character
      A            10000      Q
      B            10001      R
      C            10010      S
      D            10011      T
      E            10100      U
      F            10101      V
      G            10110      W
      H            10111      X
      I            11000      Y
      J            11001      Z
      K            11010      2
      L            11011      3
      M            11100      4
      N            11101      5
      O            11110      6
      P            11111      7

(Note that all the characters are uppercase and that the characters "0",
"1", "8", and "9" are not used.)


. OKID profile for PKIX end entity certificates

An end entity certificate is a PKIX [PKIX] certificate that does not
have the CA bit set in the certificate. The CA bit MUST NOT be set in
any certificate used with this profile.

The type identifier in the OKID for a PKIX end entity certificate is
"EE".

Systems that check an end entity OKID MUST verify that the CA bit is not
set in the certificate for which the OKID is being matched. Such systems
MUST verify that the type identifier in the OKID is "EE".

Because the result of matching the OKID to the end entity certificate is
that the certificate will now become inherently trusted, the system MUST
inform the user that the end entity certificate has become inherently
trusted. The system SHOULD give the user a method for later removing the
trust in the end entity certificate. The system MUST also check whether
the certificate is properly signed, that is, that the public key in the
certificate is in fact correctly verifies the contents of the
certificate.


. OKID profile for PKIX CA certificates

A certification authority certificate is a PKIX certificate that has the
CA bit set in the certificate. The CA bit MUST be set in any certificate
used with this profile. Note that this certificate may or may not be a
"root" certificate (that is, the issuer name may or may not be the same
as the subject name).

The type identifier in the OKID for a PKIX CA certificate is "CA".

Systems that check a CA certificate OKID MUST verify that the CA bit is
set in the certificate for which the OKID is being matched. Such systems
MUST verify that the type identifier in the OKID is "CA".

Because the result of matching the OKID to the CA certificate is that
the certificate will now become a trust anchor, the system MUST inform
the user of each of the following:

- That the certificate has become a trust anchor

- The policies used by the issuer of this certificate to issue
subordinate certificates ([PKIX] section 4.2.1.5)

- The basic constraints placed on the issuer of this certificate, such
as the depth of subordinate chain that can be issued under this
certificate ([PKIX] section 4.2.1.10)

- The types of names for which the issuer of this certificate can create
certificates ([PKIX] section 4.2.1.11)

- The policy constraints placed on the issuer of this certificate
([PKIX] section 4.2.1.12)

The system SHOULD give the user a method for later removing the trust in
the CA certificate. The system MUST also check whether the certificate
is properly signed, that is, that the public key in the certificate is
in fact correctly verifies the contents of the certificate.

. Example

Assume that the SHA-1 hash of the public key in an end entity
certificate is 0x3e1d170ac994cd73d87f1a6ecb62361a7398ca7c. The steps for
creating the string are:

A = (in hex) 3e1d 170a c994 cd73 d87f 1a6e cb62 361a 7398 ca7c

B = (in hex) 3e1d 170a c994 cd73 d87f
                3   e   1   d   1   7   0   a   c   9   9   4
  = (in binary) 001111100001110100010111000010101100100110010100
                c   d   7   3   d   8   7   f
                11001101011100111101100001111111
  = (as quintets) 00111 11000 01110 10001 01110 00010 10110 01001
                  10010 10011 00110 10111 00111 10110 00011 11111

C = HYOROCWJSTGXHWD7

Output = EE-HYOR-OCWJ-STGX-HWD7


. Security Considerations

6.1 Strength of the 80-bit hash

An 80-bit hash such as the one used in this protocol is currently
adequate for preventing substitution attacks against an unprotected
certificate. If Mallory knows Alice's public key and wants to create a
different certificate that he can substitute for Alice's during an
unprotected certificate exchange, he would have to generate
approximately 2^79 public/private key pairs in order to find one that
would impersonate Alice.

On current general-purpose CPUs, for about $100 you can calculate about
 1024-bit public/private RSA pairs a second (ignoring the cost of
memory, storage, and so on). A single US$100 chip could therefore
calculate 2^79 pairs in about 10,000 trillion years:

   (2^79 keys) / (2 key/sec) * (3.16e7 sec/year)

Viewed another way, if Mallory had US$1 trillion, it would take him
about a million years to generate 2^79 key pairs. Even if the cost
estimate is off by many orders of magnitude, this can be considered
infeasible.

6.2 Security of the out-of-band transfer

The out-of-band transfer must be secure from substitutions. That is, an
attacker must not be able to act as a man-in-the-middle for the transfer
of the OKID.

6.3 Use of OKIDs on other types of certificates

OKIDs can only be used for self-signed certificates; they cannot be used
for certificates where one party signs the public key of another party.
The reason for this restriction is that the OKID covers only the public
key in the certificate, not the entire certificate. If OKIDs were used on
certificates that were not self-signed, an attacker could substitute another
certificate with the same public key into the untrusted stream and trick
the end user into accepting it because the OKID matched. Although this
certificate would not be of direct value to the attacker (because the
attacker still doesn't have the private key associated with the public
key in the certificate), it allows the attacker to get the recipient to
trust a vastly different certificate than the recipient expected.


. Acknowledgements

Stephen Kent and Russ Housley contributed a great deal to the initial
draft of this document.

. References

[PKIX] Internet X.509 Public Key Infrastructure Certificate and CRL
Profile, draft-ietf-pkix-new-part1

[SHA1] US Secure Hash Algorithm 1 (SHA1), RFC 3174


A. IANA Considerations

New OKID profiles can be defined only in standards-track RFCs. The RFC
defining the OKID profile must fully define the environment for the key
usage, and must specify a type identifier that does not conflict with
any previous OKID type identifier.

IANA will set up a registry of OKID profiles. Each entry in the registry
will have three fields:

- Profile name: a string describing the profile

- Defining RFC: the standards-track RFC for the profile

- Type identifier: the two-letter identifier. The letters must be
  upper-case ASCII. The type identifiers must be unique across all
  entries.

The first two entries in the registry are:

Profile name: PKIX end entity certificates
Defining RFC: [ this RFC ]
Type identifier: EE

Profile name: PKIX CA certificates
Defining RFC: [ this RFC ]
Type identifier: CA


B. Author's Address

Paul Hoffman
VPN Consortium
 Segre Place
Santa Cruz, CA  95060 USA
paul.hoffman@vpnc.org