How can PGP short key IDs be protected from collision attacks?
Source: Michael Cobb
A well-known PGP short key ID flaw has been discovered to be the cause of collision attacks on Linux developers. Expert Michael Cobb explains the flaw with short key IDs.
short IDs. The flaw can result in attackers creating fake ID keys, creating problems for the recipient of the encrypted files when they try to decrypt or authenticate messages. How does this flaw work, and why are short key IDs an issue?
A hash value or message digest for an email, document or file is created by generating a short digital fingerprint of the content using a cryptographic hash function -- a mathematical algorithm that maps data of an arbitrary size to a short, fixed-length value that uniquely identifies it. Hash values are widely used in many aspects of security, such as digital signatures and data integrity checks, so the hash functions used are carefully selected to ensure they have strong collision resistance -- two different inputs can't create the same hash value. A collision attack tries to find two distinct pieces of data that have the same hash value.
Users of PGP -- a cryptography tool for encrypting and digitally signing messages or files -- have a public key and private key, the public key often being published on a key server. As these keys are extremely long -- usually 1024 to 8096 bits -- a fingerprint or hash of the public key is used to label the key and make certain key management tasks easier and quicker, such authenticating keys belonging to other users or to certificate-issuing authorities. However, a fingerprint is 40 digits long when rendered as a hexadecimal number, and it's still too long for humans to easily use, so people and many applications just use the last eight digits of the fingerprint instead. This is called a short key ID -- a long ID is the last 16 digits of the fingerprint. Here's an example:
Fingerprint: 0D29 F56F 12BD BA07 7B37 15AB 851F 799A B4FF 1057
Long ID: 851F 799A B4FF 1057
Short ID: B4FF 1057
While modern cryptographic hash functions reduce the chances of finding two inputs that have the same hash value to practically zero, the chances the last eight digits of two hashes being the same are a lot higher. So high, in fact, that a number of spoofed PGP keys with the same short key ID have been found -- most notably that of Linus Torvalds, creator of the Linux kernel, and Greg Kroah-Hartman, the current Linux kernel maintainer.
The possibility of this type of collision attack being successful has been known for a few years. In 2011, Asheesh Laroia, a software engineer, effectively demonstrated such attacks are practical and the problem is also referenced in "RFC 4880: OpenPGP Message Format," section 3.3. -- "Implementations SHOULD NOT assume that Key IDs are unique." Despite this, using short key IDs is still common practice and poses a real threat, particularly when it comes to the integrity of file downloads, such as the Linux kernel.
So, while there is no flaw or vulnerability in PGP itself, using short key IDs is fundamentally insecure and very poor practice. Users shouldn't trust an ID shorter than the full fingerprint of a public PGP key for verification; the purpose of a key ID is to assist in searching for a key, not in validating it. Both users and software need to start showing and checking the full fingerprint, or at least the long ID. Collisions are still possible for long key IDs, but far less likely. Software developers should certainly write or rewrite their code to refer to the whole fingerprint, as cloud computing gives hackers a better chance of generating a collision attack for long key IDs. Fans of PGP who print their PGP key's short ID on the reverse of their business cards may want to add the first two blocks of their fingerprint to help others validate their key.
| }
|