3

We know that the "short" 32 bit OpenPGP key IDs can be easily brute-forced and the recommendation is to use the "long" 64 bit IDs or full 160 bit SHA1 fingerprint. However I am concerned that the "long" key IDs may also be brute-forceable in the not-so-distant future.

Given that a collision would generally be a precursor to a successful preimage attack, are there any known examples of a collision being found for a long key ID?

6

OpenPGP IDs are portions of the SHA-1 fingerprint, as defined in the standard. A short key ID is the last 32 bits, and the long key ID is the last 64 bits. A collision typically takes an average of 2n/2 operations, where n is the size of the hash in bits. Generating collisions for short IDs and long IDs is trivial, requiring an average of 216 and 232 operations, respectively. A collision in this case is defined as creating two differing hash inputs which have identical digests. It is actually even possible to collide the full SHA-1 fingerprint, as Google has shown. Colliding a full OpenPGP fingerprint requires nothing more than colliding a single SHA-1 hash. This is difficult, but possible with sufficient computing power.

Creating a preimage is different. Unlike a collision, a preimage attack requires creating an input that matches a specific hash digest. The attacker does not get to provide both inputs, only one, making it a much more difficult attack. Unlike a collision attack, a preimage attack requires a full 2n operations for a hash of size n. Because of this, creating a preimage for a short ID requires only 232 operations, which is downright trivial. Doing the same for a long ID requires 264 operations, which is not easy, but far from impossible. Doing the same with the full 160-bit fingerprint is simply impossible with current technology.

In summary:

+-------------+-----------+------------+
|             | Collision |  Preimage  |
+-------------+-----------+------------+
| Short ID    |  Trivial  |    Easy    |
+-------------+-----------+------------+
| Long ID     |   Easy    |    Hard    |
+-------------+-----------+------------+
| Fingerprint |   Hard    | Impossible |
+-------------+-----------+------------+
  • 2
    Generic collision of 160-bit SHA-1 is 2^80, but the Google+Stevens et al break is 2^63.1. However it requires substantial freedom in fairly large inputs (they use PDF files), and I'm not sure if that can be obtained for (otherwise valid) PGP keys. – dave_thompson_085 Nov 23 '18 at 8:12
  • 1
    @dave_thompson_085 Specifically, IIRC, they had the freedom to manipulate the data in a non-displayed JPG image within the PDF. – TripeHound Nov 23 '18 at 9:53
  • 1
    @TripeHound Remember that the OpenPGP standard can hold a lot of non-displayed data that is free to be modified. – forest Nov 24 '18 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.