How difficult is it to break the OpenPGP 40 character long fingerprint?
david at systemoverlord.com
Tue Apr 2 01:32:45 CEST 2013
On Mon, Apr 1, 2013 at 3:38 PM, Melvin Carvalho <melvincarvalho at gmail.com>wrote:
> On 1 April 2013 22:50, David Tomaschik <david at systemoverlord.com> wrote:
>> 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:
>>> 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.
> From wiki:
> As of 2012, the most efficient attack against SHA-1 is considered to be
> the one by Marc Stevens with an estimated cost of $2.77M to break a single
> hash value by renting CPU power from cloud servers. Stevens developed
> this attack in a project called HashClash, implementing a differential
> path attack. On 8 November 2010, he claimed he had a fully working
> near-collision attack against full SHA-1 working with an estimated
> complexity equivalent to 257.5 SHA-1 compressions. He estimates this attack
> can be extended to a full collision with a complexity around 2^61.
> Given that ASICS these days are running at 1.5 terra hashes per second,
> 2^61 doesnt sound that much?
> *disclaimer* I may have totally got these sums wrong!
These numbers are for a collision attack: that is, find *any* 2 values that
have the same SHA-1 value. For OpenPGP purposes, we care about finding an
input that returns a preselected hash value (the fingerprint of another
key). That's a "preimage" attack, and I'm not aware of any preimage
attacks on SHA-1, so we're back to the 2^160 (or 2^159, since, on average,
you only need to try half the space) complexity.
david at systemoverlord.com
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Gnupg-users