Why are key IDs typically the *last* digits of the key hash?

Question

With PGP for example, the "properties" of the following key are:

pub   rsa3072/2BD6571B 2022-06-03 [SC] [expires: 2024-06-02]
      6713B62DC36CE36403C724B1FFD641CF2BD6571B
uid         [ultimate] [email protected]
sub   rsa3072/10E0C323 2022-06-03 [E]

---

fingerprint   6713B62DC36CE36403C724B1FFD641CF2BD6571B
ID (long)                             FFD641CF2BD6571B
ID (short)                                    2BD6571B

I find this very counter-intuitive, as everything of the output of GPG is meant to be read from left to right - except for the hash. Taking the last digits of the hash makes it very hard to compare a long ID and a fingerprint, for example: one needs to read from right to left or try to spot the beginning of the ID within the fingerprint and then read starting from there.

Why is it that way?

The fingerprint is a cryptographic hash, so the first bytes should be just as unpredictable as the last bytes. Therefore, the first 4 (/8) bytes of it could be used as the key ID just as well, couldn't they?

I assume this to be some kind of endianness issue, but it still seems weird to me that some architecture peculiarity would justify such a confusing default in a case where clarity means security.

Answer 1

What you've mentioned, that the key ID is the last portion of the hash, is true of v4 OpenPGP keys. However, before that, there were v2 and v3 keys (which were functionally identical) which are always RSA keys. Their key ID is the last 64 bits of the RSA modulus, and is therefore always odd, since an RSA modulus is the product of two large primes. Using the first 64 bits of the RSA modulus would be bad because it is typically less random.

RSA was patented until 2000, and it was desirable to introduce a key format that didn't rely on patented algorithms. When v4 keys were introduced, they could support other algorithms, such as DSA and ElGamal, which are discrete logarithm algorithms and, unlike RSA, can securely share their large prime parameters. Thus, the key ID was specified to be the trailing portion of the SHA-1 hash. There's no good reason for using the trailing portion, but my guess is that it made programming easier since the same truncation code could be used as for v3 keys.

In the current OpenPGP refresh, there is a move away from key IDs altogether because they are too short to be unique, and encouraging users to use them means that users will often misidentify the key. Attackers have often targeted creating fake keys that have the same key ID and UIDs as well-known people like Linus Torvalds. Instead, the movement is toward using fingerprints, which in v5 keys will use SHA-256. Since SHA-256 is believed to be secure, it is expected to be functionally impossible to forge a key's fingerprint.