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

[Melvin Carvalho]

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!


>
>
>>
>> > 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
>
> _______________________________________________
> Gnupg-users mailing list
> Gnupg-users at gnupg.org
> http://lists.gnupg.org/mailman/listinfo/gnupg-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20130402/bf6c47eb/attachment.html>