[Cryptography] [FORGED] Re: DDoS'ing PGP keys

[Stephan Neuhaus]

On 7/7/19 4:44 AM, Peter Gutmann wrote:
> John Levine <johnl at iecc.com> writes:
> 
>> GPG croaks when it tries to process the key.
> 
> Without looking at the code, I'm guessing it'll be something like an n^2
> algorithm used to process keys.  Many years ago I encountered some (not PGP)
> key-processing code and fed it a largeish key collection.  Based on the fact
> that the entire system ground to a halt, I asked the developers whether they
> were perhaps using an n^2 algorithm to do the processing.  The following day I
> got the rather sheepish answer that it wasn't n^2, it was n^3.

Waaaaay back when, I too noticed the dismally slow performance of PGP's 
key listing and management code. The way I remember it, it went:

for (each key in the keyfile, sequentially) {
   for (each signature on the key) {
     for (each key in the keyfile, sequentially) {
       if (id on key matches id on signature) {
         check signature
       }
     }
   }
}

So, not n^3 for PGP, but at least n^2.  I have no idea whether this kind 
of code is still in effect today, but I doubt it. Surely the entire 
codebase has been overhauled by now? Please?

Fun,

Stephan