How difficult is it to break the OpenPGP 40 character long fingerprint?

David Tomaschik david at
Mon Apr 1 22:50:43 CEST 2013

On Mon, Apr 1, 2013 at 10:46 AM, Daniel Kahn Gillmor
<dkg at>wrote:

> On 04/01/2013 12:24 PM, adrelanos wrote:
> > gpg uses only(?) 40 chars for the fingerprint.
> > (I mean the output of: gpg --fingerprint --keyid-format long.)
> this is a 160-bit SHA-1 digest of the public key material and the
> creation date, with a bit of boilerplate for formatting.  This is not
> gpg-specific, it is part of the OpenPGP specification:
> A better place to discuss issues related to OpenPGP in general is the
> IETF's OpenPGP mailing list:
> It is a good idea to review their archives for fingerprints and digest
> algorithms before posting, though.  Much of what you asked has been
> discussed in some detail on that list already.
> > How difficult, i.e. how much computing power and time is required to
> > create a key, which matches the very same fingerprint?
> This is called a second-preimage attack.  I am not aware of any
> published second-preimage attacks against SHA-1's 160-bit digest that
> bring the computation within tractable limits.  A theoretically perfect
> 160-bit-long digest algorithm would require ~2^160 operations to arrive
> at a particular digest.  SHA-1 is almost certainly not theoretically
> perfect against this sort of attack, but does not appear to be
> practically broken by anyone who is publishing about it.

Two points worth noting: not only do you need to find a 2nd preimage, but
you need to find one that is valid key material, which would make the
search even harder, and 2^160 is a lot of tries (assuming SHA-1 is
"perfect").  The fastest hashers for passwords for plain SHA1 are doing ~4
billion c/s, call it 2^32.  So we need 2^128 seconds.  Let's assume our
attacker has a *LOT* of money and brings 2^20 (about 1 million) machines to
the table to attack this key.  We're down to 2^108 seconds, or about 2^83
years (there are about 2^25 seconds in a year).  Of course, this ignores
Moore's law and new flaws in SHA-1.

Bad news: 2^83 years is sooner than the heat death of the universe.  Good
news: 2^83 years is long after the sun is expected to have enveloped and
destroyed the Earth during the death of the sun.

> > Isn't 40 chars a bit weak?
> the underlying material is 160 bits -- it does not need to be
> represented as 40 chars.  And if the digest algorithm was known to be
> weak (e.g. if it was a simple CRC), then even fingerprints 10 times as
> long would not be enough.
> However, for the purposes of key fingerprints in particular, SHA-1
> appears to be reasonable in the near term.
> > Are there plans to provide a longer fingerprint which in theory can't be
> > broken with computing power expected in for example 100(0) years?
> For future OpenPGP drafts, there has been some discussion about moving
> to a longer digest (on the IETF list i mentioned above).  Those
> decisions have not reached a consensus, from what i can tell.
> Predicting computing power or the state of mathematics itself 100 or
> 1000 years into the future seems like a dubious proposition.  Consider
> the state of mechanical computation and mathematics 100 or 1000 years
> ago.  Do you think that even a skilled mathematician at the time could
> have predicted where we are today?
> The longevity of any public key cryptosystem should probably be
> estimated in years or decades at the longest if you want any confidence
> in your answer.
> Regards,
>         --dkg

David Tomaschik
OpenPGP: 0x5DEA789B
david at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20130401/aa8b9a7f/attachment.html>

More information about the Gnupg-users mailing list