On 1 April 2013 22:50, David Tomaschik <da...@systemoverlord.com> wrote:
> On Mon, Apr 1, 2013 at 10:46 AM, Daniel Kahn Gillmor < > d...@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 > da...@systemoverlord.com > > _______________________________________________ > Gnupg-users mailing list > Gnupg-users@gnupg.org > http://lists.gnupg.org/mailman/listinfo/gnupg-users > >
_______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
