Not sure if this has come up for discussion here before. https://www.vice.com/en_us/article/8xzj45/someone-is-spamming-and-breaking-a-core-component-of-pgps-ecosystem Udhay _______________________________________________ The cryptography mailing list cryptography@metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography

In article <CABrRNSX8P_81cd2cFoKW7H-OYRv0Kbd3HCMX_eQrRCUooqRK0w@mail.gmail.com> you write: >-=-=-=-=-=- >-=-=-=-=-=- > >Not sure if this has come up for discussion here before. > >https://www.vice.com/en_us/article/8xzj45/someone-is-spamming-and-breaking-a-core-component-of-pgps-ecosystem As I understand it, the attack simply involves adding thousands of junk signatures to a key and uploading it to an SKS server. GPG croaks when it tries to process the key. I can understand why that might have been a problem in 1990 when a megabyte was a lot of memory, but now that the minimal increment is a gigabyte, it suggests unfortunate things about GPG's testing and code quality. There's apparently a separate issue that the SKS software is 15 year old abandonware written in boutique language OCaml, and there's nobody around (including the original author) with the time and skill to change it to defend against the junk signatures. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography

John Levine <johnl@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. Peter. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography

On 7/7/19 4:44 AM, Peter Gutmann wrote: > John Levine <johnl@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 _______________________________________________ The cryptography mailing list cryptography@metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography