Revoked Subkeys: Attacks and Mitigations?

[maxtaco]

(2nd time typing this up, the last time I unplugged my computer with my foot just before hitting submit)

@oconnor663 and @Sidnicious spent a few fun-packed hours talking about PGP subkey attacks and our sloppy-merge strategy in #531.

It turns out there is an attack here:

1. Alice pushes primary key A and subkey B
2. Alice makes a bunch of sigs.
3. Alice loses B to her foe (d'oh Alice)
4. Alice revokes B [the PGP way, not the sigchain way], authorizes new subkey C, and pushes new key to the server
5. The server recovers B, suppresses the revocation statement, and then forges arbitrary sigchain links for Alice.

There's really no combination of server/client hacks to ameliorate this problem. It's why we built the keybase sigchain the way we did. For now, let's go with the approach in #531, but in the future, we need to implement a better solution, which is:

When pushing new and updated PGP keys, the client should sign a sigchain statement with both the KID of the PGP key and also a SHA256 hash computed over the whole PGP key body, including all of the framing and header comments (no reason not to!). This hash should land in the sigchain, and the server is obligated to store and display the full PGP key that is the preimage. Clients should use this exact full PGP key for all links after this link that use this KID. For all (legacy) links that come previously, clients fallback to the sloppy-merge PGP key that they're currently using.

Here are the components needed for this fix:

• keybase-proofs updates:
  • add new field full_pgp_hash to applicable eldest, dualkey and sibkey chainlinks (Support for full-body PGP key signing proofs#23)
  • introduce new type of chainlink pgp_update, for just updating a PGP key (New chain link type for PGP key updates proofs#24)
• server-side updates:
  • changes to key uploading to compute this hash over the key and to store this key in a new column of the database. This is advisory but not useful (keybase/keybase#263).
  • changes to the key update path to post pgp_update links to the server on key upload (keybase/keybase#264)
• Go client updates:
  • change sigchain replay to download and hash all_bundles, and to use the exact key when specified by the sigchain, and the sloppy-merged key otherwise (Respect PGP full body hashes in key family reconstruction #545)
  • change proof generation to include this full_pgp_hash hash link for eldest, dualkey and sibkey signatures (Sign full PGP body hashes into PGP-related sigchain links #546).
  • upload a pgp_update chain link on pgp update (Upload a pgp_update chain link on PGP update. #547)
• libkeybase-js changes: change sigchain replay (Respect PGP body hashes signed into sigchain libkeybase-js#6)
• node-client: compute and post full_pgp_hash as necessary, on delegation or update (Sign full PGP body hashes into PGP-related sigchain links node-client#205)

[s4y]

I had a quick chat with @oconnor663 Friday evening, and we’re trying to figure out why we shouldn't store the PGP keys themselves in the sigchain.

The main argument against was to keep the sigchain small, but clients are going to need the full keys anyway to validate chain links. Any thoughts?

[oconnor663]

Just to clarify what Sidney said, I think @maxtaco was concerned about users uploading kajillion megabyte PGP keys and getting those stuck in the sigchain. But even without embedding the keys, users are still going to have to pay the performance penalty of fetching those keys. I think we might want a limit on the size of PGP keys either way, in which case there might not be downsides to just embedding PGP keys directly in the sigchain.

(In fact right now, users have to fetch large key bundles every time they hit lookup.json, whereas sigchain links are only fetched once and then cached. So in the chain would actually be better performance-wise. Though I imagine we could add some incremental mode to lookup.json too if it became an issue.)

[maxtaco]

Is there a disadvantage to storing just the hash? It seems like good
cleanliness to just store the hash.

On Monday, July 27, 2015, oconnor663 notifications@github.com wrote:

Just to clarify what Sidney said, I think @maxtaco
https://github.com/maxtaco was concerned about users uploading
kajillion megabyte PGP keys and getting those stuck in the sigchain. But
even without embedding the keys, users are still going to have to pay the
performance penalty of fetching those keys. I think we might want a limit
on the size of PGP keys either way, in which case there might not be
downsides to just embedding PGP keys directly in the sigchain.

(In fact right now, users have to fetch large key bundles every time they
hit lookup.json, whereas sigchain links are only fetched once and then
cached. So in the chain would actually be better performance-wise.
Though I imagine we could add some incremental mode to lookup.json too if
it became an issue.)

—
Reply to this email directly or view it on GitHub
#544 (comment).

[maxtaco]

I can concoct some cases in which I don't want to download the pgp keys but
I do want to verify the chain. I think we will regret it in the future if
we open the sigchain up to arbitrary bloating.

On Monday, July 27, 2015, Maxwell Krohn themax@gmail.com wrote:

Is there a disadvantage to storing just the hash? It seems like good
cleanliness to just store the hash.

On Monday, July 27, 2015, oconnor663 <notifications@github.com
javascript:_e(%7B%7D,'cvml','notifications@github.com');> wrote:

Just to clarify what Sidney said, I think @maxtaco
https://github.com/maxtaco was concerned about users uploading
kajillion megabyte PGP keys and getting those stuck in the sigchain. But
even without embedding the keys, users are still going to have to pay the
performance penalty of fetching those keys. I think we might want a limit
on the size of PGP keys either way, in which case there might not be
downsides to just embedding PGP keys directly in the sigchain.

(In fact right now, users have to fetch large key bundles every time they
hit lookup.json, whereas sigchain links are only fetched once and then
cached. So in the chain would actually be better performance-wise.
Though I imagine we could add some incremental mode to lookup.json too
if it became an issue.)

—
Reply to this email directly or view it on GitHub
#544 (comment).

[maxtaco]

Think about mobile etc. we will regret forcing 2Mb downloads. I also
prefer not to doctor people's keys. I think I feel pretty strongly here we
should embed the hash rather than the key.

Offline for a few hours

On Monday, July 27, 2015, Maxwell Krohn themax@gmail.com wrote:

I can concoct some cases in which I don't want to download the pgp keys
but I do want to verify the chain. I think we will regret it in the future
if we open the sigchain up to arbitrary bloating.

On Monday, July 27, 2015, Maxwell Krohn <themax@gmail.com
javascript:_e(%7B%7D,'cvml','themax@gmail.com');> wrote:

Is there a disadvantage to storing just the hash? It seems like good
cleanliness to just store the hash.

On Monday, July 27, 2015, oconnor663 notifications@github.com wrote:

Just to clarify what Sidney said, I think @maxtaco
https://github.com/maxtaco was concerned about users uploading
kajillion megabyte PGP keys and getting those stuck in the sigchain. But
even without embedding the keys, users are still going to have to pay the
performance penalty of fetching those keys. I think we might want a limit
on the size of PGP keys either way, in which case there might not be
downsides to just embedding PGP keys directly in the sigchain.

(In fact right now, users have to fetch large key bundles every time
they hit lookup.json, whereas sigchain links are only fetched once and
then cached. So in the chain would actually be better
performance-wise. Though I imagine we could add some incremental mode to
lookup.json too if it became an issue.)

—
Reply to this email directly or view it on GitHub
#544 (comment).

[s4y]

I assumed that clients need all of the keys to verify the chain. Is that wrong? Either way, I'll proceed with embedding hashes.

[maxtaco]

I can concoct a few scenarios in which not. One for sure is the case of
third party mirrors of the keybase merkle tree. They might never need to
verify signatures. Also in the go client we skip a lot of signature
verifications if we can. Ie that the tail of the chain is signed and don't
care as much about intermediate chain links. We can go back and forth on
whether this is a good idea but it is nice to have the option available
(and there to have optionality with regard to downloading Big PGP keys).
It feels like the level of indirection here might buy us valuable
flexibility in the future. Happy to discuss more in person tomorrow.
Thanks.

On Monday, July 27, 2015, Sidney San Martín notifications@github.com
wrote:

I assumed that clients need all of the keys to verify the chain. Is that
wrong? Either way, I'll proceed with embedding hashes.

—
Reply to this email directly or view it on GitHub
#544 (comment).

[oconnor663]

That makes a lot of sense to me. Hadn't thought about e.g. third party mirrors.

[s4y]

I think keybase/keybase-issues#1770 just exposed the current plan as inadequate.

1. What if a someone uploads a version of her PGP key that expires in one year, then lets a year pass? Right now, she can upload a renewed version of the key at any time. This won't be allowed with key versioning.
2. What if someone sends a revocation (or an extension) to the keyserver network and expects it to be honored by Keybase clients? Right now, we could theoretically give the Keybase server the ability to sync with keyservers and grab revocations and new signatures (which might extend or retract the key's expiration date). But key versioning forbids the addition of information to a key just like it forbids suppression.

I'm thinking that, when verifying a pgp_update link, clients should

1. strip revocations from the new key (in case the update revokes the signing key)
2. then, merge it into the chain's (unstripped) previous active key.

I haven't come up with a solution for issue two that doesn't give the server dangerous power. Example: let's say that the version of my key specified by my sigchain expires in a week. One night, in a drunken stupor, I re-sign it to never expire and upload it to a keyserver. The next morning, refreshed, I re-re-sign it to expire in a week once again.

(If the Keybase server is allowed to append to the key, it could maliciously serve the never-expiring version and suppress the second update.)

Thoughts? Did I miss any more problems with the current strategy?

[maxtaco]

As for (1), we can chose to ignore the expiration for this case. That feels like the right answer. Maybe Jack is right, maybe we should just be ignoring expiration times. I'm really coming around.

For (2), I'd say we ignore revocations too. We're designing our own system to handle both, maybe it's time to start abandoning the PGP system.

I think on upload, we should leave the key unmolested but just start ignoring things we don't like, as above.

[oconnor663]

Agreed with Max on (1). Ignoring expiration times entirely for this type of link would be the easiest thing. (Well, the easiest easiest thing would be ignoring expiration times for every link.) We could also specify that PGPUpdate links should be verified with the post-update key, if the signing KID is the same as the KID being updated. If we really cared about key expiration I would suggest the latter, but it sounds like we don't.

For (2), I think we have to tell people that their expectations are wrong, and that Keybase does not interact with public key servers. I'm not sure what you guys mean by ignoring revocations. Do you mean getting rid of the full_hash field? What problem would that be solving, other than (1)?

[s4y]

For (1), I agree if ignoring expiration times is simple. Otherwise, we already have code to merge versions of a PGP key so it would be easy to merge the existing and new version of a key when validating a pgp_update link.

@oconnor663, to clarify on (2): I think we're on the same page. From the point of view of someone who's used to PGP, we should pick up updates from keyservers. But, since that would let a malicious Keybase pick up updates selectively, we shouldn't do it.

By "ignoring revocations", I think Max just means stripping revocations from the new PGP key when using it to check the signature.