Blind Key Rotation not properly supported

[kaniini]

Background

Blind Key Rotation is a proposed mitigation for the inability to revoke JSON-LD Linked Data Signatures. It is based on the fact that AP implementations are supposed to refetch an actor's keys in the event that a signature fails to validate and recheck the signature.

Mastodon should implement Blind Key Rotation on Delete activities by sending the Delete activity signed by the original key and then generating a new keypair afterward, but that should be split into a different bug.

Expected behaviour

Mastodon should accept a blind key rotation from a remote user. This is necessary for situations where an instance is reinstalled anyway.

Actual behaviour

Mastodon does not accept blind key rotations. In order to get Mastodon to accept the new keys, the instance or user must be entirely suspended and unsuspended in order to delete the old key data.

Steps to reproduce the problem

1. Change an actor's keys.
2. Send messages to Mastodon.
3. Messages are not accepted due to invalid signature.

Specifications

Mastodon 2.6.5 on testodon.dereferenced.org.

[kaniini]

Based on whenever this gets fixed in Mastodon we intend to roll it out in Pleroma after a few development cycles. Right now this issue is blocking our efforts to improve future deniability by rotating keys.

[Gargron]

A couple things:

• If key validation fails and the last webfinger query was at least 1 day ago, the actor is re-resolved and a new key is fetched. This is exactly to help in situations where the instance is reinstalled.
• Mastodon supports an Update activity on the actor which is signed with the old key but contains a new key. This is part of Mastodon's own tootctl accounts rotate utility.

[kaniini]

Signed updates are good for regular rotations but blind updates are better for deniability, one of the key things to remember in a deniability situation is that you don't want a cryptographic relationship between the keys.

As for refreshing keys I guess an improvement would be to tighten the TTL.

[ClearlyClaire]

We should definitely reduce the TTL (or remove it altogether, we may not need to do the expensive round-trip related to full account update if it's only to fetch the key).

I wouldn't advocate changing keys after each Delete issued, that's going to cause a lot of key re-fetching and race conditions (Delete with old key processed after key change, etc.), I would propose doing that in a daily job instead. This could still cause race conditions if something is sent around the key change, but it limits risks.

On a related note, we only use LDS to forward replies and Delete activities, other implementations may use them for other things, but I can't see any convincing use case. We do sign way more stuff than needed for that purpose (we basically sign everything). I think we should only LDS-sign Delete and Create for public and unlisted toots, and nothing else.

EDIT: There is another thing that may need changing. Indeed, Mastodon currently assumes that if an account's key change, it's because it's lost its data, and it proceeds to re-follow them.

[ClearlyClaire]

Nevermind, there is a use for LDS for pretty much all public activities: relays.

[ClearlyClaire]

@kaniini I fail to see how signing the Update with the old key would make deniability more of a problem. If you can pretend that a signed message was fake because the old key wasn't yours, you can have the same argument about it signing your new key.

Sending such an Update would help with current Mastodon implementation since it would bypass the 1 day limit, but it wouldn't help with race conditions, though. Only a proper rollover would, and that is more likely to compromise deniability (and also, be more difficult to implement. I wonder which implementations handle the case where an author has multiple signing keys)

EDIT: Sending an Update with the old key would also let Mastodon know that the database hasn't been lost, and avoid trying to re-follow members of that instance (that's already its current behavior)

[kaniini]

@ThibG actually it is a serious problem because it creates a cryptographic relationship between the two keys. a forensic analyst will have a lot of fun with that.

Also relays do NOT need LDS, if you relay metadata about the posts instead, as the Pleroma implementation does (edit: which works just fine with Mastodon).

[kaniini]

I think we should only LDS-sign Delete and Create for public and unlisted toots, and nothing else.

This would be a significant improvement but rotating keys at some point after a Delete would still be a best practice.

[kaniini]

Regarding determining if an instance lost data or not, we could probably signal somehow in the actor object that it isn't brand new. I'm not sure what the semantics would be, but it seems possible to me.

[ClearlyClaire]

Relays don't need LDS, but not using LDS means every participant will have to fetch each relayed object to validate it, doesn't it? That would be highly inefficient. Le 30 décembre 2018 15:31:02 GMT+01:00, William Pitcock <notifications@github.com> a écrit :

…

@ThibG actually it is a serious problem because it creates a cryptographic relationship between the two keys. a forensic analyst will have a lot of fun with that. Also relays do NOT need LDS, if you relay metadata about the posts instead, as the Pleroma implementation does. -- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #9658 (comment)

[ClearlyClaire]

@ThibG actually it is a serious problem because it creates a cryptographic relationship between the two keys. a forensic analyst will have a lot of fun with that.

I am sorry, but I still can't understand how signing the Update with the old key can be a problem.

I think we should only LDS-sign Delete and Create for public and unlisted toots, and nothing else.

This would be a significant improvement but rotating keys at some point after a Delete would still be a best practice.

I improved the situation a bit (#9659), but yup, I agree we should rotate keys (I'm still trying to figure out how to avoid race conditions though).

[kaniini]

I am sorry, but I still can't understand how signing the Update with the old key can be a problem.

The Update contains the new key material, which means the old key is signing the new key material. This creates a cryptographic relationship between both keys which negatively impacts deniability.

You are looking at this from simply invalidating signatures on objects, that's an important part of it, but a forensic analyst can say in court something like: "well, key A signed an Update message containing key B, so everything signed by key A is from the same person who possesses key B." At that point the digital signatures from key A are accepted as digital evidence against you. Not good for an activist, and activists are largely the people who look toward fediverse technologies.

[ClearlyClaire]

But your defense relies on claiming that key A is not yours, right? In that scenario, key A could also have signed the Update, because anyone could sign anyone's Update with their own key. I'm not sure how that's more damning evidence than the signature on the message itself.
(Now if key B would have signed key A, that would be something else…)

[kaniini]

key A signing key B is still pretty damning. the point is to avoid any cryptographic relationship between the keys.

[ClearlyClaire]

I'm still not convinced by the benefits of blind key rotation over a standard rollout (if we assume that anybody listening to Update activities can listen to the incriminating Create activities as well—which wasn't the case before #9659).

#9667 is an attempt to drop the potential 1 day delay before accepting a blind key rotation, it doesn't address the refollow stuff nor possible race conditions, though.

As for avoiding race conditions, @kaniini proposed an interesting strategy: postponing the key change to when the account has been idle for one hour. I'm not too sure how we could do that with sidekiq, but that's a very sensible way to avoid those issues.

The account refollow stuff is still an open question. Should we drop that behavior altogether? Issue re-follows anyway? Something else entirely?

[Gargron]

Keys are comparatively large pieces of text and constantly updating every user's row in the accounts table sounds like a very, very bad idea to me.

[ClearlyClaire]

I'm not sure what part of the scheme you're opposing to exactly. If everyone would implement it as hinted there, this would be at most one change per account per hour, and much less in practice (only if the account deleted a toot, and only after 1h of subsequent inactivity). If you're worried about the fetching part, it's already possible to flood an instance with proper Update activities changing the key each time.