Re: [Sks-devel] Keyserver flooding attack: mitigation straw-man

[Yegor Timoshenko]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Bjarni, thanks for creating the MUA I'm using to write this
message!

> So if you find your key is being flooded or spammed (or you
> would for any other reason like to censor your own key), you
> sign an authorization statement with that key, and then issue a
> pull request against the shared git repository which adds your
> authorization and the key itself to the SKS-override tree. From
> that point onward, your key may still be poisoned in the raw
> SKS database, but you've prevented it from being served to the
> general public and you've prevented the people relying on your
> key from being harmed. The cost is, from that point on you will
> have to manually update your key using the above workflow
> instead of SKS.

Overall, this sounds like a MVP for protecting against current
attack results by policy. Specific workflow you've described does
work for long-term consequences.

However.

First off, there is the social problem of getting all peers
on-board with this workflow, which I will not get into.

Then, there is a number of massive denial-of-service
vulnerabilities in SKS gossip protocol: the simplest one is that
if attacker pushes >1 MB worth of unique OpenPGP packets for a
specific key separated onto 3 or more keyservers, merging process
will escalate traffic between keyservers to that comparable of a
distributed denial-of-service attack (this happens because of
timeouts and subsequent retries from each peer), while merging
itself seems to be an O(n^2) operation.

It is possible to partly mitigate this issue using bandaids, for
example, see:
https://gist.github.com/yegortimoshenko/781c880be8f1b8a91c9c23fa83a35d58

That said, it won't stop any attacker with computing power
comparable to that of PocketBeagle from destroying the whole SKS
network (disabling everyone who peers, that is), because they can
keep changing the keys (say, automatically) faster than anyone
can keep up. So, any bandaid would only work against accidental
or limited attacks. Also, mitigation requires applying a patch,
or at least, given an intricate enough patch, centralized
blacklist, in which case effective tradeoffs of the whole system
will be similar to those of centralized keyserver designs like
Hagrid (https://keys.openpgp.org).

Same concerns/limitations also apply to this flooding attack, or
poisoning attacks that abuse the fact that SKS accepts non-RFC
compliant packets: potential attacker might as well flood/poison
everyone's keys, because no known attack seems to require much in
terms of time or computing power.

I think the logical continuation of your idea is to convert SKS
dump to a Git repo and serve keys from there and accept any
modifications to it via pull requests from that point forward.
I'd guess that many SKS operators would switch to plain-text
database as source of truth, as a transparent forkable medium. It
does require human resources to keep up however, and quite likely
I underestimate the scale of things.

TLDR: This is an improvement, but it won't stop any malicious
attacker (i.e. anyone who wants to take down SKS, either by
flooding or poisoning all keys or by abusing denial-of-service
issues in gossip protocol).

-----BEGIN PGP SIGNATURE-----

iQGzBAEBCgAdFiEE2O6+NAvfE/J3pC6k+HLNsxw094UFAl0j2gYACgkQ+HLNsxw0
94XjtQv+LS0CUIGcypbK3mqTSZj63V9CvSOLB03817FYt5YsMFlBEqqO216vpZg2
2KB9BJ2O5AUj4+r93EncixIz+AlbSMb2PvCUxJTPSNp3zLaxfzZxKcmU4r3tNcJu
RKQAxjfTceDwp4VrH/HMu8qSG0KKn7o2cC1F35D7QPBOUZZxd4CQ2lBjLfsYa7yu
Ia1eu3aLugl4gGT/eHabtYdFFuPQWcpAg73RGVeTyFrmxHMtu5yl87+yORxbCLTh
9nbWXLlMT6KVZH4gqpONiks22a1f9ht2wWwv8CkLzT68rUx4LrDyjRCHZ6UVJhdD
DcCHMU9A3sspTIrkrc29Ga7VFCC/4sx2wntDJhW07CeaehmPEPEtB2kzaBRbAx9F
aeWkozAkSyLYSzxC4yYy7Y0QaskS2fy13SFgRpfkwdi4rlL0U5PVxnqCu5D4wYFu
/XzhkkvcIpLIRkjm6IKZaMpDBnleYK8erTj7A8o/s1IrzeWsLZNErvvBdtlqIVaC
HU/E91GZ
=1Ndp
-----END PGP SIGNATURE-----