Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
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?
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 | +-------------+-----------+------------+
