Re: [openpgp] Revocations of third-party certifications (TPK+"CRL") [was: draft-dkg-openpgp-abuse-resistant-keystore-04.txt]

[Jon Callas <[e-mail]>]

> On Aug 27, 2019, at 3:43 PM, Daniel Kahn Gillmor <[e-mail]> wrote:
> 
> On Tue 2019-08-27 13:05:35 -0700, Jon Callas wrote:
>> Yeah. I just cringed and said, "Oh, dear me, you just invented CRLs
>> and we *know* those don't work.
> 
> haha, sigh -- the way that CRLs "don't work" is roughly the same way
> that HKP-style keyservers "don't work".  In particular, most users don't
> check CRLs, and they don't refresh keys from keyservers.
> 
> One of the reasons that they don't check CRLs is because the relevant
> time for the check is often a low-latency situation (e.g. TLS session
> establishment) and the implementation doesn't want to block.
> Additionally, the user might not want to leak metadata about their
> activity to the CRL operator.  Both of these reasons are also why
> OpenPGP signature verifiers have a hard time collecting revocation
> information about the signature-issuing certificates.

Yup, this is pretty much what we said about CRLs back in the mid-90s. It's possible this is required at some level, and if it is, let's just skip ahead to an analogue of OCSP stapling (which could be done by a key server) and Certificate Transparency, 'cause the whole ontogeny recapitulates phylogeny thing is predictable.

The underlying issue is that revocation doesn't work. The reason revocation doesn't work comes from the first law of data-driven programming, which is that a datum having been emitted cannot be recalled. A revocation is kinda an anti-cert that we send out on a mission to find the cert, and then they mutually evaporate into raw energy.

If we willing to accept that there will always be copies of the old, unrevoked cert hanging around and things will happen because of that, then we reduced it to a solvable subset.

I believe an example of a reasonable thing to do would be to have the key server put a certification on the certificate that includes a URI back to it, and appropriate metadata (timestamps, TTLs, whatever else) and then we had a protocol by which the user of the cert would look at the key server certification and if it's in an untenable state (like the time has expired, or whatever else you want) that the user gets a fresh copy of that cert -- then we have a first approximation of a distributed CRLish thing and a working protocol. I say distributed because the information isn't in a list, it's on the cert itself. 

Nonetheless, even here there are edge conditions where the answer when the inevitable thing goes wrong is, "Don't do that, you'll hurt yourself." 

> 
> In either case (X.509 or PGP), though, if we're willing to accept a
> delay (i.e., we don't support low-latency requirements), and we can do
> scheduled/backgrounded onion-routed updates to our certificate stores to
> obscure the metadata patterns, we can mitigate some of those concerns.
> 
> But an additional concern for OpenPGP certificates (which X.509 doesn't
> have) is that the common keyservers are vulnerable to flooding attacks,
> as outlined in the draft under discussion here.
> 
> So while this discussion isn't aiming to fix the low-latency or metadata
> leakage concerns, it is trying to address the abuse concerns.  Maybe we
> can focus on that?

Sure. The abuse problem has been around, as well, and I'm glad you're taking up the cause.

> 
>> I think that it's better to keep things more or less the way we've
>> done them.
> 
> The way we've done them in OpenPGP up to now is vulnerable to abuse, as
> we've seen.  I'm hoping we can concretely specify what we need to do to
> avoid leaving the door open to that abuse.

I said more or less, not exactly. Look, I agree it's a problem worth solving. I'm the one who calls all those key servers "The La Brea Tar Pits" and I don't mean it as a compliment.

> 
>> Alice's revocation attaches to her prior certification, and they
>> travel together. They could both be dropped, but not only one. (Even
>> though I can't really imagine the case of no certification, but only a
>> revocation, in completeness.)
> 
> The case of an omitted certification but included revocation seems
> sensible to me.  If the keystore knows that a given certification is
> revoked, it might very sensibly want to refrain from redistributing it.
> 
> At the same time, it knows that the certification is out there, some
> people might have a copy of it, and those people need to know that a
> revocation has been issued.

Yeah. An issue with OpenPGP certificates is that they are ultimately a list of statements, and those statements can be rewritten with impunity. Overall, I think it's far more of a feature than a bug, because an alternative would make it so no one would be able to do anything without the key owner's permission, and that would disrupt things like key signings.

> 
>> If Alice isn't a good citizen and makes an abusive revocation, the
>> server can and should drop it.
> 
> How would you define "abusive revocation" in this context?  Is it a
> universal view of "abuse", or might different people have different
> perspectives?

I define it the way it's defined. An abusive revocation is something we'll learn over time, and it's something that the key server decides. 

> 
> For example, if we define abuse as being simply "too large", then
> perhaps we can fix a byte limit on what a "redistributable" revocation
> looks lke.  And if Bob attests to Alice's certification, he is
> implicitly willing to accept her (as yet unseen) revocation as well.

Why not both? Why not all?

Right now, we're dealing with abuse in the form of "too large." In the paragraphs below, you have other things that could also be abuse worth solving. 

> 
> This gets thornier if we look at arbitrary data in the revocation.  For
> example, if Alice's certification revocation contains a Reason for
> Revocation subpacket with a text string that says "the King is an
> imbecile" (and Bob needs his certificate to be distributable in a place
> where it's illegal to insult the King) or it says "Joe Smith was born on
> 1957-03-25" (and Bob lives needs his certificate to be distributable
> somwhere it's illegal to distribute "personal information" without the
> person's consent), then that would make Bob's certificate difficult to
> redistribute where he needs it to be.  This is where i get uncomfortable
> about the idea that there is some universally-applicable view of what an
> "abusive" revocation is, and why i think that Bob's sovereignty over his
> own certificate makes it really important.

This is why I declined to define it. It doesn't matter what it is at this point and we *will* be faced with abuse that is so clever we didn't think of it ahead of time. Update the server and roll.

> 
> Perhaps we could say that the most narrowly-tailored third-party
> certification revocation signature is acceptable -- the only three
> subpackets allowed:
> 
> * Issuer Fingerprint
> * Signature Creation Time
> * Reason For Revocation -- only with a code, and string MUST be empty
> 
> And of course the abuse-resistant keystore would have to
> cryptographically verify the certification revocation signature.

That works. I don't think it has to be that narrow, but that would work.

> 
> But does that mean that *any* revocation is freely attachable to any
> certificate?  What if Bob doesn't ask for a distribution of Alice's
> certification in the first place?  Is Alice allowed to slap a revocation
> onto Bob's certificate?

Yes. Alice is revoking *her* certification of Bob's key. Bob owns Bob's key, but Alice owns her certification of Bob's key. Bob can freely discard the certification or the certification+revocation, but he should not be allowed to keep Alice's certification without its matching revocation.

Part of my prologue of revocation not working is that Bob can always go do key surgery. To some extent, anyone can do key surgery. Bob can go in with a hex editor and pull off Alice's revocation, but general tools shouldn't allow it. Moreover, a key server shouldn't allow it. If Bob uploads a new copy of his key without Alice's mention at all, that's fine. The key server MUST not allow the revocation to be vanished alone.

We have not seen the abuse problem of certificates being nonsensical, but that could really happen. I am sure that if you did something like take the first part of Bob's key, threw in one of Aice's user ids along with all its certifications, and some subways and other things from Charlie's key, that some implementation's going to barf in amusing ways -- or worse, just accept it.

> 
> This brings us to this case:
> 
>> If Bob wants to just drop Alice's certification along with her
>> revocation, that's fine too.
> 
> So let's say Mallory gets ahold of Bob's secret key, and Bob's
> certificate has a certification from Alice, which Mallory likes.  Alice
> learns that Bob's secret key has been compromised, and she wants to
> revoke her certification of Bob.  But Mallory (masquerading as Bob)
> indicates "actually, do not distribute Alice's certification".  Then
> Mallory can hide Alice's revocation.  I don't think that's an acceptable
> outcome.

Any problem that starts with "Mallory gets ahold of Bob's secret key" and then goes on, is kinda like discussing an operating system exploit that starts with, "okay, the attacker is in kernel mode." In general, the attacker can have much more fun than whatever's described. Yes, yes, if Malloy has Bob's secret key, Mallory can do anything.

However, this is part of why we have designated revokers. The whole problem if an adversary having a copy of the key has to be solved with something irrevocable pointing to a third party. (This is preparing for death, too, and sadly it has to be done in advance.) If you have a designated revoker listed on the key server, then that entity can revoke even if the key is compromised. There isn't a way to solve this if the only actor is that one key.

The biggest fly in the ointment, though is that not only can Mallory masquerade as Bob, but Mallory can also make a "new" key (add in new user ids, delete the old ones) that points somewhere else but has the same key as Bob's. Mallory has the private key and so can do *anything* not just masquerade.

> 
> Furthermore, it's possible that Bob has *never* attested to (requested
> redistribution of) Alice's certification, though Alice's certification
> is known to some other party, let's say "Carol".  How should Carol be
> confident that she will learn of Alice's revocation, if it is created
> and published?

See first paragraph. This is part of why I say revocation does not and cannot work. A subset can.

Perhaps a key server ought to be a designated revoker itself in some but not all cases. Perhaps even the default one. Of course, I'm handwaving away things like accounts on that server, authentication, takeover policies, and lots of other things that will be fun for someone else.

The PGP key server used expiry time for this rather than a special signature. It just went and resigned things regularly.

> 
> Something like a CRL seems to still be required.

Or a signature on the key that's made by the key server itself that has a timeout and a lot of policy coded in it.

	Jon