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

[David Tomaschik]

On Mon, Apr 1, 2013 at 10:46 AM, Daniel Kahn Gillmor
<dkg at fifthhorseman.net>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:
>
>   https://tools.ietf.org/html/rfc4880#section-12.2
>
> A better place to discuss issues related to OpenPGP in general is the
> IETF's OpenPGP mailing list:
>
>  https://www.ietf.org/mailman/listinfo/openpgp
>
> 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
http://systemoverlord.com
david at systemoverlord.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20130401/aa8b9a7f/attachment.html>