Internet Draft                                   Paul Hoffman
draft-ietf-pkix-okid-01.txt                      VPN Consortium
February 24, 2002
Expires in six months


      Out-of-Band Certificate and Key Identifier Protocol (OCKID)

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, self-signed end-entity certificates, or bare
(unsigned) public keys requires a mechanism for establishing the
authenticity of the certificate or public key.

When a user receives a certificate or public key 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 certificate or
public key over an integrity-secure, authentic, out-of-band channel. The
Out-of-Band Certificate and Key Identifier Protocol (OCKID) is a
user-friendly key identifier that can be used for the out-of-band
verification of a certificate or bare public key.


. 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. The same attack can be used in protocols that use bare public
keys as trust anchors.

In order to detect and reject such attacks, a user receiving a
certificate or bare public key must use a method to verify that the
certificate or public key is the one that the sender intended. One means
of achieving this is to communicate the hash of the certificate or
public key over a communication path which the user believes to be
integrity-secure and authenticated. (The certificate or public key
itself is considered too large a value for users to conveniently and
reliably communicate.)

The OCKID provides a standard representation for out-of-band human
communication of the hash of a certificate or public key, in support of
the security requirements described here. The OCKID 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 a
keyboard with ASCII capabilities.


. OCKID format

An OCKID string has the following format:

WW-XXXX-XXXX-XXXX-XXXX-XXXX

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

2.1 Type identifiers

This document defines four OCKID profiles. The identifiers for these
profiles are:

EE - PKIX end entity certificates

CA - PKIX certification authority certificates

AA - PKIX attribute authorities

BK - Bare key

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 certificate or bare public
key being identified. This will always be 160 bits.

. 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 fourth 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   Charac
      A            10000      S
      B            10001      T
      C            10010      U
      D            10011      V
      E            10100      W
      F            10101      X
      G            10110      Y
      H            10111      Z
      J            11000      2
      K            11001      3
      L            11010      4
      M            11011      5
      N            11100      6
      P            11101      7
      Q            11110      8
      R            11111      9

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


. OCKID 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 OCKID for a PKIX end entity certificate is
"EE".

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

Because the result of matching the OCKID 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.

. OCKID 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 OCKID for a PKIX CA certificate is "CA".

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

Because the result of matching the OCKID 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.

. OCKID profile for PKIX attribute authority certificates

Attribute certificates are described in [ATCERT]. The entities that can
issue attribute certificates are called "attribute certificate issuers"
and "attribute authorities". The rules governing the certificates that
can be used to issue attribute certificates are given in section 4.5 of
[ATCERT]. Basically, any end entity (but not a CA) can be an attribute
authority.

The type identifier in the OKID for a PKIX attribute authority
certificate is "AA".

Systems that check an attribute authority 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 "AA".

If the result of matching the OKID to the attribute authority
certificate is that the certificate will now become inherently trusted
for attribute certificates, the system MUST inform the user that the
attribute authority certificate has become inherently trusted. The
system SHOULD give the user a method for later removing the trust in the
attribute authority certificate.

The system SHOULD give the user a method for later removing the trust in
the AA 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.

. OCKID profile for bare public keys

A bare public key is simply a bit string.

The type identifier in the OCKID for bare public keys is "BK".

In systems where the result of matching the OCKID to the bare public key
is that the public key will now become inherently trusted, the system
MUST inform the user that the bare public key has become inherently
trusted. The system SHOULD give the user a method for later removing the
trust in the bare public key.


. Example

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

A = (in hex) cc487d7aa6228613e997d760a10a9e920fb06f49

B = (in hex) cc487d7aa6228613e997

                c    c    4    8    7    d    7    a    a    6
B = (in binary) 1100 1100 0100 1000 0111 1101 0111 1010 1010 0110
                2    2    8    6    1    3    e    9    9    7
                0010 0010 1000 0110 0001 0011 1110 1001 1001 0111

                  3     T     E     H     4     8     X     G
B = (as quintets) 11001 10001 00100 00111 11010 11110 10101 00110
                  E     L     D     B     H     4     N     Z
                  00100 01010 00011 00001 00111 11010 01100 10111

C = 3TEH48XGELDBH4NZ

Output = EE-3TEH-48XG-ELDB-H4NZ


. Security Considerations

8.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 certificate 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 certificates in order to find one that would
impersonate Alice.

Note that Mallory would not have to compute 2^79 signatures; he could
alter the contents of the unsigned parts of the certificate and
therefore only need to calculate 2^79 hashes. Creating 2^79 hashes is
currently infeasible.

Chips that do DES encryption at 100 megabits (1e8) per second cost about
$100 dollars in quantity today. Assuming that SHA-1 runs about as fast
as DES, and that a typical certificate is 5000 bits long, a $100 chip
could do about 2e4 hashes per second on these 5e3-bit certificates.
It takes each $100 chip about trillion (1e12) years to do 2^79
hashes:

   x = 2^79 hashes / ( (2e4 hash/sec) * (3.16e7 sec/year) )

If Mallory wanted to duplicate Alice's OCKID within 10 years, he would
have to spend about ten trillion dollars.

OCKIDs for bare public keys are even stronger, because Mallory would
have to produce 2^79 valid key pairs instead of 2^79 hashes in order for
the result to be useful. Creating key pairs is orders of magnitude
slower than calculating hashes.

Moore's laws probably apply to hash accelerator chips, but even with the
speed of the chips doubling every 1.5 years, the attack for Mallory is
infeasible for certificates and keys that have a lifetime of less than
 years. In 20 years, today's chips will run about 2^12 (4096) times as
fast, meaning that Mallory would need to spend tens of billions of
dollars to duplicate a certificate within a year.

8.2 Birthday attack

If Mallory is only attacking Alice's OCKID, he has to do 2^79
operations. If he can attack a very large number of certificates or
keys, the birthday attack makes it easier for him to find a certificate
or key to attack, but doesn't make it easier for him to specifically
attack Alice. Mallory needs to do a smaller number of hash operations in
order to find one collision he can use.

This effect is mitigated by the fact that Mallory not only needs to find
a matching OCKID, he also must be able to inject the bogus certificate
or key into the stream just as Bob is retrieving it. Because the main
use of OCKIDs is for trusted certificates and keys, people will retrieve
them much less often than certs in a hierarchical trust chain. Injecting
bogus certificates or keys is easy for Mallory if he controls a common
certificate or key repository.

8.3 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 OCKID.


. Acknowledgements

Stephen Kent and Russ Housley contributed a great deal to the initial
draft of this document. Peter Gutmann helped refine the Base32. Many
people pointed out problems with the initial idea of hashing just
the public key in a PKIX certificate.


. References

[ATCERT] Internet Attribute Certificate Profile for Authorization,
draft-ietf-pkix-ac509prof

[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 OCKID profiles can be defined only in standards-track RFCs. The RFC
defining the OCKID profile must fully define the environment for the key
usage, and must specify a type identifier that does not conflict with
any previous OCKID type identifier.

IANA will set up a registry of OCKID 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 four 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

Profile name: PKIX attribute authority certificates
Defining RFC: [ this RFC ]
Type identifier: AA

Profile name: Bare public keys
Defining RFC: [ this RFC ]
Type identifier: BK


B. Author's Address

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


C. Changes between -00 and -01

- Changed the title.

- Changed the hash from being over the key to being over the whole cert.

- Changed the Base32 characters.

- Added profiles for attribute authorities and bare keys

- Changed the Security Considerations section considerably.