Concerns regarding the authenticated key replacement mechanism

[teythoon]

I have grave concerns regarding the authenticated key replacement mechanism as proposed by HIP-1 and implemented in current hockeypuck versions. I believe it to be not complete, not functional, and dangerous.

First, because it uses OpenPGP's detached signature mechanism, it requires a signing-capable (sub)key. Therefore, the mechanism fails to protect OpenPGP certificates without signing-capable (sub)key. The solution is not complete.

Second, after a key has been replaced with a clean version, presumably to get rid of a flood of certifications, an attacker can simply re-add the certifications. The replacement mechanism does not assure sovereignty, only a momentarily relief. Therefore, the solution is not functional.

I haven't looked into how gossiping plays into that, but if gossiping uses the same policy as updates using hkp, then gossiping will also re-add any third party certifications.

Third, the pair of keytext and keysig are a capability to reset the copy of the certificate on the server to keytext. If a malicious party ever gets hold of such a pair, then they have the ability to remove updates from the certificate stored on the server. Undoing an update that extends the validity period of a certificate leads to an DoS because the certificate can no longer be used (e.g. for encryption). Undoing an update that revokes a key leads to a certificate being used even though it shouldn't, compromising authenticity and confidentiality. Therefore, I conclude that the mechanism is dangerous.

[cmars]

Thanks for the feedback, you raise some good points, and I'm open to other ideas about how to solve these issues.

I have grave concerns regarding the authenticated key replacement mechanism as proposed by HIP-1 and implemented in current hockeypuck versions. I believe it to be not complete, not functional, and dangerous.

First, because it uses OpenPGP's detached signature mechanism, it requires a signing-capable (sub)key. Therefore, the mechanism fails to protect OpenPGP certificates without signing-capable (sub)key. The solution is not complete.

This seems like an edge case. One can always create a signing subkey with the primary if needed, and sign a request. I think it's good practice to only certify subkeys with the primary, and sign stuff with subkeys that can be rotated.

Second, after a key has been replaced with a clean version, presumably to get rid of a flood of certifications, an attacker can simply re-add the certifications. The replacement mechanism does not assure sovereignty, only a momentarily relief. Therefore, the solution is not functional.

I haven't looked into how gossiping plays into that, but if gossiping uses the same policy as updates using hkp, then gossiping will also re-add any third party certifications.

This is in the unfortunate nature of the keyserver protocol. It's too liberal in what it accepts (depending on how it's configured!). A key may grow signatures to the point where it becomes a problem (like key spam). A keyserver operator may set a max limit on key size, but this then blocks future legitimate updates to a spammed key from being distributed. Key replacement allows a key owner to "force push" such updates to a keyserver, so that they can distribute the key material they want.

Third, the pair of keytext and keysig are a capability to reset the copy of the certificate on the server to keytext. If a malicious party ever gets hold of such a pair, then they have the ability to remove updates from the certificate stored on the server. Undoing an update that extends the validity period of a certificate leads to an DoS because the certificate can no longer be used (e.g. for encryption). Undoing an update that revokes a key leads to a certificate being used even though it shouldn't, compromising authenticity and confidentiality. Therefore, I conclude that the mechanism is dangerous.

This one is probably the most serious, and I'll likely soon address. It's a good point, there is a possible "replay attack" where someone could re-submit an old key reset request, erasing more recent signatures. This could be mitigated with a signed nonce -- but I think even a simple expiration time signed into the request would suffice.

[teythoon]

Thanks for the feedback, you raise some good points, and I'm open to other ideas about how to solve these issues.

Thanks for your prompt reply!

To be honest, my preferred outcome is for Hockeypuck to implement first-party attestations of third-party signatures (1pa3pc, see https://datatracker.ietf.org/doc/html/draft-ietf-openpgp-rfc4880bis-10.html#section-5.2.3.30). dkg, Vincent, and Werner put a lot of thought into it, and this is at least the second iteration of the spec. I think it is a more comprehensive solution, and it would be great to come together as a community of implementers and standardize our approach.

Once 1pa3pc is implemented in the OpenPGP library, the change to the keyserver is trivial because it only requires local reasoning about the certificate (see my patch to hagrid).

I understand that Hockeypuck uses gopenpgp. Maybe we can collaborate with ProtonMail to implement 1pa3pc. @twiss?

I have grave concerns regarding the authenticated key replacement mechanism as proposed by HIP-1 and implemented in current hockeypuck versions. I believe it to be not complete, not functional, and dangerous.

First, because it uses OpenPGP's detached signature mechanism, it requires a signing-capable (sub)key. Therefore, the mechanism fails to protect OpenPGP certificates without signing-capable (sub)key. The solution is not complete.

This seems like an edge case. One can always create a signing subkey with the primary if needed, and sign a request.

Are you saying that people with certificates that -for whatever reason- don't have a signing subkey should create a signing subkey for the benefit of using this API? That seems like an unfortunate workflow.

I think it's good practice to only certify subkeys with the primary, and sign stuff with subkeys that can be rotated.

I agree, but that does seem to be orthogonal to the problem of certificates that do not have a signing-capable (sub)key.

1pa3pc uses signatures created by the primary key, so that scheme supports certificates without signing-capable (sub)keys.

Second, after a key has been replaced with a clean version, presumably to get rid of a flood of certifications, an attacker can simply re-add the certifications. The replacement mechanism does not assure sovereignty, only a momentarily relief. Therefore, the solution is not functional.

I haven't looked into how gossiping plays into that, but if gossiping uses the same policy as updates using hkp, then gossiping will also re-add any third party certifications.

This is in the unfortunate nature of the keyserver protocol. It's too liberal in what it accepts (depending on how it's configured!). A key may grow signatures to the point where it becomes a problem (like key spam). A keyserver operator may set a max limit on key size, but this then blocks future legitimate updates to a spammed key from being distributed. Key replacement allows a key owner to "force push" such updates to a keyserver, so that they can distribute the key material they want.

1pa3pc circumvents this issue, by giving the certificate owner authority over which third-party attestations should be distributed. It does so using a cryptographic artifact that can be distributed with the certificate. Synchronizing keyservers can synchronize this artifact, and act according to the explicit wishes of the certificate holder. Doing so is really easy, because it only requires reasoning about the certificate in question.

In 1pa3pc, Bob's certification of Alice's (User id, primary key) pair is attached to Alice's cert as before, but Alice now creates a signature attesting to that certification. This signature includes a list of attested certifications identified by the certifications hash digest. Keyservers can now simply filter out any certification that is not in that list.

Third, the pair of keytext and keysig are a capability to reset the copy of the certificate on the server to keytext. If a malicious party ever gets hold of such a pair, then they have the ability to remove updates from the certificate stored on the server. Undoing an update that extends the validity period of a certificate leads to an DoS because the certificate can no longer be used (e.g. for encryption). Undoing an update that revokes a key leads to a certificate being used even though it shouldn't, compromising authenticity and confidentiality. Therefore, I conclude that the mechanism is dangerous.

This one is probably the most serious, and I'll likely soon address. It's a good point, there is a possible "replay attack" where someone could re-submit an old key reset request, erasing more recent signatures. This could be mitigated with a signed nonce -- but I think even a simple expiration time signed into the request would suffice.

While it is possible to improve this interface, the conceptual problem I see is that the signature does not encode intent. Making the intent explicit prevents signatures published in some other context to be be repurposed. One way to improve that is to encode that intent using a critical signature notation. However, tooling support for notations is unfortunately not great, I don't know if gopenpgp offers an interface for that.

I don't think that checking the signatures creation time and only using fresh ones addresses the problem, it only limits the window in which such a signature can be exploited.

On the other hand, 1pa3pc encodes intent.

It is important to fix this in a timely fashion, because I found that it can easily be exploited. I'm happy to provide more details in private (drop me a note, my address is justus@sequoia-pgp.org). This is me first stripping signatures off a certificate that I don't control, then deleting it from the server:

% sq keyserver --policy insecure --server hkp://localhost get F00583D361630E69DE5BDD9CC87CE52096C85999 | sq inspect --certifications
-: OpenPGP Certificate.

    Fingerprint: F00583D361630E69DE5BDD9CC87CE52096C85999
Public-key algo: EdDSA Edwards-curve Digital Signature Algorithm
Public-key size: 256 bits
  Creation time: 2021-01-04 09:23:07 UTC
Expiration time: 2023-01-04 09:23:07 UTC (creation time + P730D)
      Key flags: certification, signing

         Subkey: A20F6DC2B774D08F2F262DF2AB5A887DCC81FDF5
Public-key algo: EdDSA Edwards-curve Digital Signature Algorithm
Public-key size: 256 bits
  Creation time: 2021-01-04 09:23:07 UTC
Expiration time: 2023-01-04 09:23:07 UTC (creation time + P730D)
      Key flags: authentication

         Subkey: 1703D9376F7F6F16C528C0C9879C1A7A03A01953
Public-key algo: ECDH public key algorithm
Public-key size: 256 bits
  Creation time: 2021-01-04 09:23:07 UTC
Expiration time: 2023-01-04 09:23:07 UTC (creation time + P730D)
      Key flags: transport encryption, data-at-rest encryption

         UserID: Christoph Biedl <cbiedl@gnupg.com>
Alleged certifier: 84F3C63824DEE148F5D44C4763D47BB3B2579F7B
             Note: Certifications have NOT been verified!

% curl --data-urlencode keytext@cbiedl.pgp --data-urlencode keysig@cbiedl.sig http://localhost:11371/pks/replace
{"inserted":null,"updated":["eddsa263/f00583d361630e69de5bdd9cc87ce52096c85999"],"ignored":null}
% sq keyserver --policy insecure --server hkp://localhost get F00583D361630E69DE5BDD9CC87CE52096C85999 | sq inspect --certifications
-: OpenPGP Certificate.

    Fingerprint: F00583D361630E69DE5BDD9CC87CE52096C85999
Public-key algo: EdDSA Edwards-curve Digital Signature Algorithm
Public-key size: 256 bits
  Creation time: 2021-01-04 09:23:07 UTC
Expiration time: 2023-01-04 09:23:07 UTC (creation time + P730D)
      Key flags: certification, signing

         Subkey: A20F6DC2B774D08F2F262DF2AB5A887DCC81FDF5
Public-key algo: EdDSA Edwards-curve Digital Signature Algorithm
Public-key size: 256 bits
  Creation time: 2021-01-04 09:23:07 UTC
Expiration time: 2023-01-04 09:23:07 UTC (creation time + P730D)
      Key flags: authentication

         Subkey: 1703D9376F7F6F16C528C0C9879C1A7A03A01953
Public-key algo: ECDH public key algorithm
Public-key size: 256 bits
  Creation time: 2021-01-04 09:23:07 UTC
Expiration time: 2023-01-04 09:23:07 UTC (creation time + P730D)
      Key flags: transport encryption, data-at-rest encryption

         UserID: Christoph Biedl <cbiedl@gnupg.com>
% curl --data-urlencode keytext@cbiedl.pgp --data-urlencode keysig@cbiedl.sig http://localhost:11371/pks/delete
% sq keyserver --policy insecure --server hkp://localhost get F00583D361630E69DE5BDD9CC87CE52096C85999
Error: Failed to retrieve cert

Caused by:
    Key not found

[andrewgdotcom]

1pa3pc is a radical enough change that it will require a flag in the recon protocol, which will cause a hard fork of the network. While we probably don't have to worry about backwards compatibility with SKS, we should at least have a plan for the hockeypuck operators to co-ordinate any such change. I'd prefer to do this in a single hard fork on a predetermined date, along with the other changes mentioned in #135.

[dkg]

fwiw, i agree that 1pa3pc is a reasonable way forward for this kind of abuse-resistance.

I also agree with @andrewgdotcom that planning a hard fork in the network synchronization would be necessary once there is a quorum of functioning/syncing keyservers that are capable of distributing only sovereign certificates (using 1pa3pc to identify the 3rd party certifications that are accepted).

Having some general mechanism to plan for hard forks like this is also important, but if figuring out the general scheme for all future hard forks were to block such a transition for 1pa3pc, i'd suggest getting 1pa3pc done first, and using what we learn from that transition to try to inform a more generic future scheme for hard forks.

[andrewgdotcom]

For supporting 1pa3pc packets (or any new packet type), we do not need a hard fork. Presumably only a small number of keys will initially be using the new features, so we can allow sync to gracefully fail in those cases and catch up later as operators upgrade their software. We only need a hard fork when we drop large numbers of existing, nonconforming packets.

The technical mechanism for causing the hard fork exists - this would be the third hard fork of the recon protocol, although the first two (yminsky.dedup and yminsky.merge) are lost in the mists of prehistory. You set flags in the recon configuration, and the keyserver will refuse to sync with any keyserver not displaying the same set of flags. Of course, the flags must correspond to the actual current state of your dataset, otherwise you're wasting your time.

Where I think we might improve things technically is to use new flags as configuration parameters, to change both the input filters and the sync behaviour at runtime (AIUI the existing flags are treated as opaque by hockeypuck, as the hard forks predate it). This would allow operators to simply set the flag on flag day and restart, and let the software take care of the rest. Using a flag to enable or disable filters should be straightforward. Using a flag to alter recon is complex, as it would require parallel sets of ptrees etc to be generated and maintained during the lead-up to the hard fork. Otherwise, operators would have to upgrade the software, set the flag, and reingest from a dump to process the database through the updated filters - a process that takes several hours.

For semantic purposes, I would suggest two new flags, let's call them packet-whitelist (#135) and attested-only (#136) for now. I would expect the former to be easier to implement, and so be rolled out first, as it only requires a change to the input filters and not support for novel packets. Without significant technical advances in the meantime, they will both involve reingesting data, which is why I suggested batching them together to minimise disruption.

I think the timeline for the attested-only hard fork should be driven by rollout of client support and corresponding documentation. For Hagrid, it makes sense to move straight away, because they didn't serve third party sigs at all before. For Hockeypuck to drop non-attested sigs will be a significant change in behaviour, and if users don't have the client software available to make attestations it will be very disruptive.

[Valodim]

Right, that last part is really the difficult bit here: client support for 1pa3pc isn't there yet. However, I believe in terms of chicken-and-egg bootstrapping, keyservers are in a much better position to make the first move, since it's just implementation of a relatively straightforward spec, no ux involved.

I believe sq only has a "certify all" interface right now, and pgpy is only support on the library level. @dkg also brought this up with gnupg and suggested an interface, which was initially well received but lowered in priority when HIP-1 (is that the name for this feature?) was announced.

There's been a bit of discussion on 1pa3pc here as well as HIP-1, I wonder @cmars what's your take on this?

[andrewgdotcom]

I believe in terms of chicken-and-egg bootstrapping, keyservers are in a much better position to make the first move, since it's just implementation of a relatively straightforward spec, no ux involved.

I see resolving this as a three-step process:

1. synchronising keyservers support 1pa3pc (minor update)
2. client rollout, user education etc.
3. synchronising keyservers enforce 1pa3pc (hard fork)

Hagrid is different, having never implemented legacy third-party signature support. :-)

[Valodim]

While I agree that sounds reasonable on paper, I'm not sure how effective step 2 can actually be performed and hence what the timeline of such a process could be. Educating users of an upcoming requirement like this is extremely difficult even in the best of conditions. And for OpenPGP in particular, the developer community isn't really connected to its users, and doesn't exactly have a great track record of educating users about new features via application UI (save some exceptions, like GPGTools for macOS).

[andrewgdotcom]

And for OpenPGP in particular, the developer community isn't really connected to its users, and doesn't exactly have a great track record of educating users about new features via application UI

So maybe this should be tackled first? Perhaps industry journalism is a better way to spread awareness in such a fragmented ecosystem?

[andrewgdotcom]

Please have a look at https://github.com/hockeypuck/hockeypuck/wiki/HIP-3:-Timestamp-aware-merge-strategy for an alternative approach.

[andrewgdotcom]

Having recently assisted a user through the HIP-1 key deletion process, I have come across some further issues:

1. It is impossible in principle to delete a revoked key via HIP-1, because the signature over the deletion request will not validate. For similar reasons, an expired key would have to be un-expired in advance of deletion, which is not an acceptable requirement.
2. Submitting a deletion request to a load-balanced cluster will only (currently) delete it from one node in that cluster. Operators would need to implement a custom deletion/replacement request handler in their reverse proxies for them to work as intended.
3. The only reason that sync does not immediately un-delete a deleted key using a copy from its peers is because hockeypuck fails to properly update the PTree, so recon does not initiate its recovery [1]. If however the deleted key were to be updated elsewhere (e.g. by a third-party certification) then the modified key will sync as normal, and undo the deletion. One way to fix this would be to add the fingerprint to the blacklist on deletion, however such dynamic updates would require blacklists to be stored in the database, rather than in the config file.
4. The unimplemented portion of HIP-1 (deletion request propagation) is ineffective - if even one keyserver in the network did not support deletion, or if a race condition were to occur between deletion propagation and recon, then the deleted key would not be reliably purged from the network.

[1] I view this as a bug (#227), but in order not to render the deletion process completely ineffective I propose that it not be fixed until an alternative deletion method is implemented.

[andrewgdotcom]

It is impossible in principle to delete a revoked key via HIP-1, because the signature over the deletion request will not validate. For similar reasons, an expired key would have to be un-expired in advance of deletion, which is not an acceptable requirement.

I've unexpectedly run into the second half of the above in #151, because ProtonMail/go-crypto added an automatic test for key expiry when verifying a detached sig, and the replace.asc test key expired at the end of 2022 - which means that the ci tests have been working for the last five months even though they probably shouldn't have. We could gracefully handle the key expiry error to maintain the current behaviour, but it still doesn't solve the other issues.

[andrewgdotcom]

I'm planning to address this in 2.2.0 by implementing a hard fork as described above.