[stir] Rough of sketch of OCSP alternative

[Eric Rescorla <[e-mail]>]

In today's meeting I did a bunch of handwaving about alternatives
to OCSP.

As I understand the situation, the calling provider has a certificate
that covers some TN number range with the usual semantics that the CA
believes that the provider is authorized for that range. However,
that's a dynamic situation and numbers might be ported out of the
provider (see more about numbers being ported in), so the verifier
wants to be able to verify "is this certificate still valid for
number X?"

What I have in mind is something like the following, which is at
least slightly less handwavy, though may still be horribly broken.
It didn't do as good a job of reducing the size of the PASSport
as I was hoping. Naively it's around 600 bytes, though perhaps
we can make it smaller.


# Setup

At the time of issuance the certificate is valid for N numbers E_1,
E_2, ... E_n.  For each time window t (say one day), the CA creates a
set of N random numbers R_1_t, R_2_t, ... R_n_t, with the obvious
mapping:

   E_1 -> R_1_t
   E_2 -> R_2_t
   ...
   E_n -> R_n_t

When it issues the certificate, it then adds hashes of
the R values, conceptually in a big table like so:

   [
     [ Hash(R_1_1), Hash(R_2_1), ... Hash(R_n_1) ],  // Time window 1
     [ Hash(R_1_2), Hash(R_2_2), ... Hash(R_n_2) ],  // Time window 2
     ...
     [ Hash(R_1_T), Hash(R_2_T), ... Hash(R_n_T) ],  // Time window T
   ]

This is obviously huge, but I'll talk about how to compress
it later.

This requires around N*T operations, so if you had 10^6 numbers and
a two week period with one day time windows, it's about 10^7 operations,
but they're just fast symmetric key operations like hashes so this
is practical. The CA does *not* need to store all this data because
it can compute R_i_t as PRF(Secret, i, t).


# Calling

When a provider wants to make a call from number E_i it contacts the
CA, which provides the value R_i_t for that number and for the current
time window t (this value was previously secret. The provider then
includes R_i_t in the PASSporT in a new field.

When the verifier receives the call, it does the following:

1. Verifies the certificate as accurate, proving that the provider
   is legitimate and that the CA attests to the binding of the
   public key to the provider.

2. Checks that R_i_t hashes to the corresponding hash value in the
   certificate, verifying that the provider was still authorized for
   number E_i at time. This replaces the OSCP check for authorization
   for the number, though not the OSCP check for the certificate
   itself.


# Compression

As I mentioned, the certificate is super huge in this design, but
it's possible to compress it because certificate just needs
to *commit* to the hashes, but not contain them. We can improve
the situation using a Merkle Hash Tree. Specifically, for time
window t, the CA lays out a Merkle tree with the leaves:

   Hash(R_1_t) Hash(R_2_t) Hash(R_3_t) ... Hash(R_n_t)

Each time window then hashes up into a tree of depth approximately
log_2(N) values.

The calling provider then provides the path from the leaf node
to the root in the PASSPporT, so that means they provide:

  log_2(N) hashes
  the R value

If N is a million certificates then we're looking at a tree of depth
20 or so. If we use 32 byte hashes, then this is order 640 bytes,
which isn't great. I don't understand the security bounds of Merkle
trees to know well enough if you could get away with shorter hashes,
though obviously that would help. One thing that might help here
is that the CA controls R, so the attack space is narrower
than it might ordinarily be.

In terms of what goes in the certificate, you can either put the root
of each time window tree in the certificate or take the time window
trees and hash them up into a single root, and put that in the
certificate. Given that we are trying to minimize cost in inline
PASSporTs, it's probably better to have more data in the certificate
than we otherwise would.


# Shrinking the PASSporT (partial stapling)

Note that it's not *necessary* that the PASSporT contain the full
Merkle tree path, as that information isn't secret; it's just a matter
of whether it's self-contained. So, for instance, you could do
the following:

- There is an online mechanism to retrieve parts of the tree (this is
  just cacheable stuff).

- The calling provider can only send the most M leafward nodes in the
  PASSport and hope that the verifier has already cached the parent
  nodes.

The calling provider might also keep track of what it sent to
each verifier and start out sending the whole path but then
do less in subsequent calls.

-Ekr