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

[David Tomaschik]

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:
>>>
>>>   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.
>>
>
> 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.[29] Stevens developed
> this attack in a project called HashClash,[30] 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?
>
> https://products.butterflylabs.com/homepage/1500gh-bitcoin-miner.html
>
> *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 Tomaschik
OpenPGP: 0x5DEA789B
http://systemoverlord.com
david at systemoverlord.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20130401/4d1b5b32/attachment-0001.html>