Re: [stir] Rough of sketch of OCSP alternative
Eric Rescorla <ekr@rtfm.com> Mon, 31 July 2023 13:03 UTC
Return-Path: <ekr@rtfm.com>
X-Original-To: stir@ietfa.amsl.com
Delivered-To: stir@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BB41FC151062 for <stir@ietfa.amsl.com>; Mon, 31 Jul 2023 06:03:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.903
X-Spam-Level:
X-Spam-Status: No, score=-1.903 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=rtfm-com.20221208.gappssmtp.com
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id QRaRqGla7N1R for <stir@ietfa.amsl.com>; Mon, 31 Jul 2023 06:03:42 -0700 (PDT)
Received: from mail-yw1-x112d.google.com (mail-yw1-x112d.google.com [IPv6:2607:f8b0:4864:20::112d]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 1695BC14CE4C for <stir@ietf.org>; Mon, 31 Jul 2023 06:03:42 -0700 (PDT)
Received: by mail-yw1-x112d.google.com with SMTP id 00721157ae682-57045429f76so48325167b3.0 for <stir@ietf.org>; Mon, 31 Jul 2023 06:03:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rtfm-com.20221208.gappssmtp.com; s=20221208; t=1690808621; x=1691413421; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=GpSoxouEMfSebSnMnoowXbrtwWtGrjbgOneRq4OHauk=; b=13kKP+Rce7FNOEfMrcrOHZoiCYrxcohaP/syHDMze/icF5WTGHN/pkpD0szPqTJQ6f 39niY8EXXM8iT8YCe4g+m6+0k3NsNKMR16gPq7XzaHowY0W3Emj1783E/tDq8Qifw5jl am2O6SPu8V0covRXpbCtk/H43fhHjbiy1QWQvCfQJ63xlLRaIlfSqCjwabr1w7hG8Js/ dh+V9aUo5I1RDmXSMcVUMXXQp3vwqSCDU5ccV+0YKFwyfHPrznRxtO28NQ7pCemwVyDs z5ZSeh5syt4NcAHVhKvbkZAIY8z/kPTT0giJIUdMX/roPHBRLYYQ9SRAx2wbgoxFV/p3 MVoA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690808621; x=1691413421; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=GpSoxouEMfSebSnMnoowXbrtwWtGrjbgOneRq4OHauk=; b=hVBtZwpg4wyiGIkODB9yOjRKB69eTOqPfK7UdQl7D5Z7Yd1GMlbuceSyvJBlwa+fBe xfQBaJpyNPc3zGY40i8w0/00ou3xmyF9IcgrNLp2e73mpYgVbtF5MM0d40/e0s1ktHTT iZM0wymMiYxm29LjcUstBxALNfdEPoCC71wsCh5qSvdSLmYjALDorXNc8D5KexTIhgmx CJIUsZRsnrcXqdhSwmoFuxxIYOnggIZ+4L9qs3Eu9pj7ubVlsbRjgJhDk1N4C4bvab08 endHXdExIsFPDwIIfLrKBOZ4BiuDKGzwebZ/ulAFaWwTQJDBGfdqqxq9JnNTqa60HqGD m6+Q==
X-Gm-Message-State: ABy/qLbxpGpSdTkDdUZ87SQfrHbCI9JM7rLEd8e7UjgTe/uAkLN4QMQp 6qVXl09i7ydYFPJ8FK5RrC7vyl6TmMlUity5Z7YcJF/cWaESCiRf
X-Google-Smtp-Source: APBJJlGaiQA+Y2zCZhKdUQMpPbYTD8/f+X4v4PRrXvdRQUSqezOxLgTyQH1t0IwMIpM/4M8HqvTWvHHa0sAAomg0JVI=
X-Received: by 2002:a81:4886:0:b0:56d:3b91:7e76 with SMTP id v128-20020a814886000000b0056d3b917e76mr10255840ywa.12.1690808621120; Mon, 31 Jul 2023 06:03:41 -0700 (PDT)
MIME-Version: 1.0
References: <CABcZeBPy4ERQabAhKaMN2HuJ3jXf735aWzrL-jJmt0EbTD0jUQ@mail.gmail.com> <E2CDD174-8A95-40A3-AA38-C0BBC3916222@vigilsec.com>
In-Reply-To: <E2CDD174-8A95-40A3-AA38-C0BBC3916222@vigilsec.com>
From: Eric Rescorla <ekr@rtfm.com>
Date: Mon, 31 Jul 2023 06:03:04 -0700
Message-ID: <CABcZeBOinZgFZS6dRaOmDWWZaqN0KsZfrg-yN4OO3o4fTrh-Qw@mail.gmail.com>
To: Russ Housley <housley@vigilsec.com>
Cc: IETF STIR Mail List <stir@ietf.org>, Dennis Jackson <ietf@dennis-jackson.uk>
Content-Type: multipart/alternative; boundary="0000000000003ed4dc0601c80f9a"
Archived-At: <https://mailarchive.ietf.org/arch/msg/stir/DE2aJ5wBdwzwDlDNoboF8lHNIgA>
Subject: Re: [stir] Rough of sketch of OCSP alternative
X-BeenThere: stir@ietf.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Secure Telephone Identity Revisited <stir.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/stir>, <mailto:stir-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/stir/>
List-Post: <mailto:stir@ietf.org>
List-Help: <mailto:stir-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/stir>, <mailto:stir-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 31 Jul 2023 13:03:45 -0000
One more thought. The design as described requires announcing which hashes correspond to which phone numbers in order to know the corresponding R value. However, if instead of just hashing R we instead hash R || phone number, then I believe this will allow the CA to hide the possible set of numbers. -Ekr On Fri, Jul 28, 2023 at 12:15 PM Russ Housley <housley@vigilsec.com> wrote: > 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 <ekr@rtfm.com> 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 > stir@ietf.org > https://www.ietf.org/mailman/listinfo/stir > > >
- [stir] Rough of sketch of OCSP alternative Eric Rescorla
- Re: [stir] Rough of sketch of OCSP alternative Russ Housley
- Re: [stir] Rough of sketch of OCSP alternative Eric Rescorla