Re: [stir] Rough of sketch of OCSP alternative

[Russ Housley <[e-mail]>]

Eric:

https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-208.pdf

This supports the truncation of SHA-256 to 192 bits.  If this truncation is safe for a hash-based signature, it should be okay in your proposal too.

Russ

> On Jul 28, 2023, at 2:11 PM, Eric Rescorla <[e-mail]> wrote:
> 
> 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
> 
> 
> 
> 
> 
> 
> 
> 
> 
>   
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
>    
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> stir mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/stir