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. > > > 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
