How difficult is it to break the OpenPGP 40 character long fingerprint?
melvincarvalho at gmail.com
Tue Apr 2 00:38:41 CEST 2013
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.
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!
>> > 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.
> David Tomaschik
> OpenPGP: 0x5DEA789B
> david at systemoverlord.com
> Gnupg-users mailing list
> Gnupg-users at gnupg.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Gnupg-users