Subject: [openpgp] [[email-masked]] New Version Notification for draft-dkg-openpgp-abuse-resistant-keystore-04.txt

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 22 Aug 2019 17:08:44 -0400

Hi all--

I've just released version -04 of the OpenPGP Abuse-Resistant Keystores
draft.

substantive changes bewteen -03 and -04:

 * change "certificate update" to "certificate refresh" for clarity
 * relax first-party-attested third-party certification constraints
   at the suggestion of Valodim
 * introduce "primary key sovereignty" concept explicitly
 * describe how to distribute and consume attestation revocations
 * introduce augmentation to TPK for third-party certification revocation
   distribution

Please take a look!

       --dkg

Subject: New Version Notification for draft-dkg-openpgp-abuse-resistant-keystore-04.txt
From: [email-masked]
To: "Daniel Kahn Gillmor" <[email-masked]>, "Daniel Gillmor" <[email-masked]>
Date: Thu, 22 Aug 2019 12:39:00 -0700

A new version of I-D, draft-dkg-openpgp-abuse-resistant-keystore-04.txt
has been successfully submitted by Daniel Kahn Gillmor and posted to the
IETF repository.

Name:		draft-dkg-openpgp-abuse-resistant-keystore
Revision:	04
Title:		Abuse-Resistant OpenPGP Keystores
Document date:	2019-08-22
Group:		Individual Submission
Pages:		58
URL:            https://www.ietf.org/internet-drafts/draft-dkg-openpgp-abuse-resistant-keystore-04.txt
Status:         https://datatracker.ietf.org/doc/draft-dkg-openpgp-abuse-resistant-keystore/
Htmlized:       https://tools.ietf.org/html/draft-dkg-openpgp-abuse-resistant-keystore-04
Htmlized:       https://datatracker.ietf.org/doc/html/draft-dkg-openpgp-abuse-resistant-keystore
Diff:           https://www.ietf.org/rfcdiff?url2=draft-dkg-openpgp-abuse-resistant-keystore-04

Abstract:
   OpenPGP transferable public keys are composite certificates, made up
   of primary keys, direct key signatures, user IDs, identity
   certifications ("signature packets"), subkeys, and so on.  They are
   often assembled by merging multiple certificates that all share the
   same primary key, and are distributed in public keystores.

   Unfortunately, since many keystores permit any third-party to add a
   certification with any content to any OpenPGP certificate, the
   assembled/merged form of a certificate can become unwieldy or
   undistributable.  Furthermore, keystores that are searched by user ID
   or fingerprint can be made unusable for specific searches by public
   submission of bogus certificates.  And finally, keystores open to
   public submission can also face simple resource exhaustion from
   flooding with bogus submissions, or legal or other risks from uploads
   of toxic data.

   This draft documents techniques that an archive of OpenPGP
   certificates can use to mitigate the impact of these various attacks,
   and the implications of these concerns and mitigations for the rest
   of the OpenPGP ecosystem.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 22 Aug 2019 18:01:23 -0400

>  * introduce augmentation to TPK for third-party certification revocation

This bit is likely to be the most-controversial part of this update, so
i wanted to explain it more.  Sorry that this note is so long.

The "first-party sovereignty" idea is that the certificate-holder (and
*only* the certificate-holder) gets to decide what gets shipped with
their certificate.  But that makes for trouble when the first party
appears to want to distribute a third-party certification, but the
keystore is aware of a revocation from the third-party.

A concrete example:

- Alice is a popular and well-respected certifier.

- Bob meets Alice and they exchange fingerprints.  Alice certifies Bob's
  identity, and Bob attests to Alice's 3rd-party certification, shipping
  it with his OpenPGP certificate.

- They go their separate ways.

- Later, Alice learns from a reliable source that Bob's OpenPGP secret
  key material has fallen into the hands of Eve, or that Bob was not who
  he claimed to be, or whatever.  She decides to revoke her
  certification, and she tries to reach Bob but he is uncontactable.

- Alice pushes her revocation to the keystore so that it learns of it,
  and it can cryptographically verify it.

- How does Alice's revocation get attached to Bob's certificate for
  redistribution?  How does a keystore client learn of Alice's
  revocation?

My first instinct option is for the keystore to just slap the revocation
onto Bob's certificate directly.  This is how SKS and other
non-abuse-resistant keystores have done it in the past.

This has a few problems:

 * It violates the "first-party sovereignty" idea.  Bob doesn't get to
   decide whether this revocation is attached to his certificate or not.

 * It's open to abuse.  What if Alice makes an abusively large
   revocation signature, or a revocation signature that contains toxic
   data?

 * What if Bob then revokes his attestation over Alice's third-party
   certification, so that the keystore won't ship it?  Then presumably
   the keystore won't ship the revocation as well.  But then clients
   that already know about Alice's certification don't get the
   revocation.

All this is unsatisfactory, so there needs to be another approach.

The approach i'm proposing in this draft is that revocations of
third-party certifications are shipped with the *revoker*'s certificate
(Alice, in the example above), not with the targeted certificate.

This has some nice properties:

 * "Sovereignty" still holds: Alice still controls what's attached to
   her certificate, because she can avoid making a revocation if she
   doesn't want it to be visible there.

 * it's abuse-resistant, because Alice has a strong incentive not to
   make the revocation abusively large or toxic.

 * A user who cares about Alice's certifications should be regularly
   refreshing Alice's certificate anyway.  Users who don't care about
   Alice's certifications don't need to care about her revocations
   either.

You can see this as the keystore performing a CRL-like distribution
service for each certificate that they distribute.  That is, each
OpenPGP certificate is followed by a "CRL" of zero or more certification
revocation signature packets, issued by that certificate's
certification-capable primary key.

There are two downsides to this approach:

 A) it violates the definition of a transferable public key in RFC4880
    (clients aren't expecting these packets)

 B) It's not obvious to to match up these revocation certificates with
    the certifications they revoke

(A) isn't really a problem -- we can just update the spec; legacy
clients will ignore the trailing "CRL" and discard it anyway.

(B) requires a bit more engineering, but not much.  Clients that know
about this CRL can keep an index of all third-party certifications based
on the SHA256 digest of the certifications.  If all revocations have one
or more "Target Signature" subpackets that use SHA256, to point to the
certification(s) that they revoke, then an indexed keystore can find
them and revoke them without much trouble.

Note that this only works if there is a well-established convention
about what digest algorithm to use.  I don't want to keep a SHA256 and a
SHA512 and a blake2b index of all the certifications i know about.  Note
also that SHA256 isn't used here for strong cryptographic purposes --
it's just a hash table indexer.

For bandwidth optimizations, one can imagine a keystore that provides
two "refresh" interfaces for a certificate: one with the "CRL" attached,
and one without it.  I think that would only be useful for a certificate
that issues lots and lots of revocations (not common in the OpenPGP
world), and if a client only selects "with CRL" for the certificates
that it "trusts" as a certifier, it would expose the user's trust model,
so i'm not inclined to propose such an interface explicitly.

Anyway, i'm thinking that this "CRL" extension to the Transferable
Public Key might belong in RFC4880bis.  I will propose it as a separate
patch to that draft, but i wanted to give some motivation behind why i
think it's important and useful.

I welcome feedback,

      --dkg

---

From: [email-masked]
Date: Fri, 23 Aug 2019 11:48:41 -0400

On 8/22/2019 at 6:03 PM, "Daniel Kahn Gillmor" <[email-masked]> wrote:
>>  * introduce augmentation to TPK for third-party certification 
>revocation  distribution

>- Bob meets Alice and they exchange fingerprints.  Alice certifies 
>Bob's identity, and Bob attests to Alice's 3rd-party certification, 
>shipping it with his OpenPGP certificate.
>
>- Later, Alice learns from a reliable source that Bob's OpenPGP 
>secret key material has fallen into the hands of Eve, or that Bob was 
>not who he claimed to be, or whatever.  She decides to revoke her

=====

What if the third party signature just had an 'expiration' option ?

(e.g.    Signature validity:  0,  Forever;     1,  1 year;    n,  n years)

This allows for 'expiration' of validation in the event of possible compromise, 
and if it is not compromised, then the signer can 're-sign'/'update' the certification, 
send it to the key owner, who can then upload it to the server.

vedaal

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 23 Aug 2019 16:41:46 -0400

> (e.g.    Signature validity:  0,  Forever;     1,  1 year;    n,  n years)

This is already possible!  Most third-party certifications i make have
such an expiration.  It works fine with most implementations afaict.

however, expirations are not the same as revocations.

> send it to the key owner, who can then upload it to the server.

In the scenario i described, the "key owner" is non-responsive, but the
certifier still wants to make sure her certification is visibly revoked.
She can't rely on the key owner's responsiveness -- they could even be
dead!  Her obligations are to the people who rely on her certifications,
and she needs to make the revocation visible to them promptly,
regardless of how the first party behaves.

          --dkg

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 26 Aug 2019 02:19:12 -0500

> i wanted to explain it more.  Sorry that this note is so long.
[...]
> it's just a hash table indexer.

This sounds an awful lot like (my understanding of) what PHB's UDF [1]
(uniform data fingerprint) is supposed to be.  Sadly, I've not had time
yet to give it a proper read...

-Ben

[1] https://tools.ietf.org/html/draft-hallambaker-mesh-udf

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 26 Aug 2019 14:43:15 -0400

> [1] https://tools.ietf.org/html/draft-hallambaker-mesh-udf

I don't think that this is the same thing as i'm proposing above -- my
understanding is that PHB's UDF is intended to have some level of
cryptographic resilience -- to collisions at least, and maybe to
pre-images in some contexts.

In the scheme i've proposed above, the digest is simply used to find a
certification in an index.  It could conceivably be non-unique, even,
since the verification is expected to be done over the full underlying
certification data.  (i.e. it's an index to a non-keyed hashtable)

To avoid malicious attacks against the efficiency of the non-keyed
hashtable (e.g. if we used CRC32, an adversary could flood the user with
certifications that produce identical checksums, reducing them to linear
search), we probably *do* want it to be collision-resistant, but it's
not going to need the same level of cryptographic rigor that we'd need
for a fingerprint, where the fingerprint itself is used to prove
identity of data.

         --dkg

---

From: Jon Callas <[email-masked]>
Date: Tue, 27 Aug 2019 13:05:35 -0700

> On Aug 22, 2019, at 3:01 PM, Daniel Kahn Gillmor <[email-masked]> wrote:
> 

Thank you, thank you for "first-party sovereignty" even if I'd say "ownership." This might be relevant below.

In 4880, 5.2.3.17 and the no-modify flag is there intentionally to provide an affirmation that the owner wants sovereignty.

[...]

> non-abuse-resistant keystores have done it in the past.

That's also mine. Of course there is more to it than that, there always is.

>   decide whether this revocation is attached to his certificate or not.

Yes, but it's Alice's certification. I think I can argue that she has a right to revoke her signature, that her signature does not transfer over to Bob.

If this is false, then there's a lot of reason never to sign anyone else's key, because it's therefore irrevocable.

>   revocation signature, or a revocation signature that contains toxic

I think that can be taken care of. If Alice did that, I, the key server might decide that my sovereignty overrides hers, and I'm not going to be a party to her abusing Bob.

>   that already know about Alice's certification don't get the

Well, this is why "sovereignty" might be the wrong term.

In my idealized way that I think a key server should work, it should defer to the rules of the game, and one of those rules is that it's Bob's key, and another is that it's Alice's signature. 

A resolution that shipped neither Alice's certification nor her revocation of same is to me an adequate compromise.

> certification-capable primary key.

Yeah. I just cringed and said, "Oh, dear me, you just invented CRLs and we *know* those don't work.

[...]

> think it's important and useful.

I think that it's better to keep things more or less the way we've done them.

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.)

If Alice isn't a good citizen and makes an abusive revocation, the server can and should drop it. If Bob wants to just drop Alice's certification along with her revocation, that's fine too.

	Jon

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 27 Aug 2019 18:43:44 -0400

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

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?

> I think that it's better to keep things more or less the way we've

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.

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

> 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?

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.

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.

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.

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?

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.

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?

Something like a CRL seems to still be required.

     --dkg

---

From: Jon Callas <[email-masked]>
Date: Wed, 28 Aug 2019 00:29:04 -0700

> On Aug 27, 2019, at 3:43 PM, Daniel Kahn Gillmor <[email-masked]> wrote:
> 

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." 

> leakage concerns, it is trying to address the abuse concerns.  Maybe we

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

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

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

> universal view of "abuse", or might different people have different

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. 

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

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

> cryptographically verify the certification revocation signature.

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

> certification in the first place?  Is Alice allowed to slap a revocation

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.

> Mallory can hide Alice's revocation.  I don't think that's an acceptable

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.

> confident that she will learn of Alice's revocation, if it is created

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

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 28 Aug 2019 18:22:44 -0400

Hi Jon--

Thanks for the feedback!  I'm trying to distill it to concrete guidance
we can use to make OpenPGP certificate redistribution more robust…

On Wed 2019-08-28 00:29:04 -0700, Jon Callas wrote:
> 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.

I agree that we want people to be able to compose OpenPGP certificates.
It is definitely a feature of the format, but it's a tricky one, and one
that keystores have had difficulty in managing without opening
themselves to abuse.

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

This isn't sufficient, unfortunately, because what's abusive for one
keyserver might not be abusive for some of its clients, and vice versa :(

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

So this sounds like useful concrete guidance that we can offer in the
abuse-resistant keystores draft.  I'll include it in the next revision.
thanks!

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

Alice doesn't "own" her certification of Bob's certificate -- we're 

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

I start this from the assumption that the (ab)user has powerful,
flexible client-side tools, and their only limitation is that they don't
have access to (certain) secret keys.  This is Kerckchoff's principle,
basically.

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

But if the keystore allows the revocation to be vanished in any way on
its own terms, it has not solved the problem for the client that does
merge-based updates but already knows of Alice's certification?

Or, are you suggesting that a client of the keystore which knows of
Alice's certification, but receives Bob's certificate without it from
the keystore, should themselves *drop* Alice's certification just
because the keystore doesn't report it?  That would be a pretty radical
change to how most OpenPGP keystore clients work today.

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

these are straight up bugs. If you see them in any OpenPGP
implementation -- client or keystore or wherever -- please report them
and get them fixed.

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

No, that's not true in this situation.  We're talking here about how to
get control of the key back from Mallory, or how to stop Mallory from
decrypting messages already encrypted to the key, or anything like
that.  We're talking about how Alice can reliably publish her revocation
of her certification even in the face of Bob being impaired,
intransigent, or compromised.

> However, this is part of why we have designated revokers.

Designated Revokers need to be set up ahead of time.  If you've done
that, and your designated revoker isn't asleep at the switch, then all's
well.  but most people haven't, and it would be nice to handle that
case.

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

I'm looking for concrete guidance that we can offer to operators of
keystores and clients of keystores today.

Keystore operators have traditionally not wanted to be in the role of
certificate authority, or of designated revoker (i can confirm this as a
past and present keystore operator, but it's not just me).  They're
looking for a reliable set of guidelines they can follow to ensure that

 (a) the ecosystem is healthy,
 
 (b) clients with different trust models and trusted introducers can
     find what they need,

 (c) the keystore can operate efficiently in terms of bandwidth and
     computational resources, and 

 (d) the keystore operator themselves is at minimal technical and legal
     risk.

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

How does this help in redistributing Alice's certifications?  I am wary
about trying to "code a lot of policy" -- the devil is in the details
there, and i'd like to be clear about what those details are.  Do you
have something specific you're trying to propose here?

The CRL-like mechanism that launched this thread is concrete,
implementable, and has a set of functional properties that seem better
than the status quo (though i think it can be improved too).  If you've
got specific text that you want to propose to improve it, or a
counterproposal that makes it unnecessary, i'd be happy to see it.

Thanks for thinking this through here,

       --dkg

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 29 Aug 2019 12:07:01 +0000

Daniel Kahn Gillmor <[email-masked]> writes:

>I'm looking for concrete guidance that we can offer to operators of keystores
>and clients of keystores today.

Maybe we can look at X.509 for an example.  During the interminable X.509
standardisation process, there was an equally interminable debate about
whether to make revocations easy (the emergency handbrake model) or hard (the
DoS-resistance model).  The DoS resistance guys won out protocol-wise, and CAs
won out business-wise because it costs money to deal with revocations so
discouraging them as much as possible cuts back on expenses.

In the 20-25 years since then, there have, to the best of my knowledge, been
zero malicious revocations.  I counted them, twice.  There have however been
vast numbers of certs not revoked that should have been, or revoked far too
late to do any good, typically for malware-signing, phishing, or just
lost/password forgotten/eaten by the cat/whatever where there's no proof of
malicious use but they should still have been declared invalid for general
hygiene reasons.

So at least for X.509 the emergency-handbrake model should have been the one
to use but, typically for X.509, they went with the wrong option.  When a bus
is about to crash, you need to stop it promptly, not argue about who is and
isn't authorised to hit the brakes.

Peter.

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 29 Aug 2019 23:43:30 -0500

> pre-images in some contexts.

That's my understanding as well, but with the related property that a
single index will encompass all fingerprint-generating algorithms, which is
what I was focusing on.  It does not really get you the property that if
you have one fingerprint you can look up the entry for the object with that
fingerprint, though (IIUC), since the entry might only be in the index
under a different "name".

Sorry for not thinking it through more,

Ben

---

From: Jon Callas <[email-masked]>
Date: Fri, 30 Aug 2019 17:04:07 -0700

Thanks for the comments as well, and I'm really glad you're taking this task on. It's been one of my peeves for a long time. I know you've been dealing with it at least in part because the issues have been inflicted upon you, too.

I want to pull back and take a number of the discussion points in text paragraphs, too. I think we're mostly in violent agreement.

One way that I think about this is that the server is an actor in the interactions, and I'd encourage a server to have opinions and policies. We tend to look at the security actors as Alice and Bob, but the server is also an actor and should consider both Alice and Bob as potential adversaries.

There's two broad classes of abuse that we have to deal with. I'm going to call them syntactic abuse and semantic abuse. Syntactic abuse is something that is often relatively easy to discuss and solve. For example, if Alice puts a 1GB signature or revocation on Bob's key, we can solve that easily. Discussions we have had are pretty non-controversial and I like your suggestion about minimal revocations. 

There are other forms of syntactic abuse that's similar -- for example, if someone put a million certifications on a key, that would suck. The server could guard against with a policy like stripping certifications from a key that's not on the server. The obvious workaround for the abuser is to upload that million keys first. I still think that a policy (possibly per user?) of stripping certifications from keys not on that server is not a bad idea. I can imagine others, like not allowing Alice to submit certifications other than her own. Nonetheless, there's a lot of potential issues here and I agree with you that some of the things we discuss aren't sufficient, but I'll bet that a few (like syntactic parsing and size limits) are necessary.

One part of abuse protection is going to be to have a cleaner function that will do things like take the submitted certification and return a clean version of it. I'd include in that some hygiene functions like stripping expired certifications (except self-sigs), and so on.

Semantic abuse is different and much of that's going to be in the eye of the beholder. I think one might argue that something like many certifications as a form of spamming is actually semantic. Much of that's going to be in the eye of the beholder. In many cases, the only one who can tell us if Alice is being abusive to Bob is Bob.

You gave the use case of Alice revoking her certification of Bob's key because she believes he's suffered a key compromise. Fair enough, but what if she thinks that for some legitimate, but eccentric reason. Oh, let's suppose Bob says he keeps his passphrase in a password manager and Alice is horrified, and thus wants nothing more to do with Bob's key? 

Here's a case where I think that we're more or less in violent agreement on "ownership." I think it's Bob's key and if he wants to delete Alice's certification+revocation, fine. Let him, it's his key. The place where I think we agree on concept but perhaps not on the word "own" is her certification. Certainly, we shouldn't be seeing Alice's certification re-appear without its revocation. Whatever term we want to use to describe that is fine with me. As long as we are ending up with the idea that the revocation sticks to the certification and can't be removed, we're on the same page.

You noted that we're probably going to need to have a way to tombstone a certification. I agree. If Bob deletes Alice's certification, we don't want it to reappear. My hand wave back in 2440 days was the flag that says "let me manage this key, myself" which yes is a large hammer, but it works. If Bob's key is groomed the way Bob wants it, it's not abusive -- given that we agree that Bob owns his key. (There are people I know who disagree with this, but let's ignore them for now.)

If I were writing a server, I'd implement the tombstones with a non-exportable signature made by a key that the server itself owns. I'd write the tombstone details in a notation. This leaves dangling the issue of how it gets propagated, as you noted, and I'm willing to leave that as an exercise for the future. I'll state the problem though: Bob deletes Alice's certification from his key; how does Charlie find that out?

Let's rewind, though and come back to Alice's revocation. Let's consider the case where Alice really is trying to make Bob mad. Alice can even create a certification just to revoke it with a reason that's insulting. That's really just the certification-spamming abuse with frosting and sprinkles, but it's still an issue.

> looking for a reliable set of guidelines they can follow to ensure that

That's great, I agree completely. Key servers shouldn't (and likely can't) be CAs. Heck, if there's anything we know from X.509 it's that being a CA is hard. However, they can't just be a key store, if a store is a database with a web interface that allows anyone to put something into it.

A key server has to have policy that it runs. It has to solve a number of problems including abuse, but also including things like Bob being able to get rid of a key that they don't control. One of the oldest problems in the ecosystem is the new person who creates a key and then forgets their passphrase. No one yet has done the automated abuse of submitting keys for other people, but it's bound to happen, especially now that I mentioned it. Key servers need to run code to be a fair arbiter of cryptographic information.

	Jon