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

[Melvin Carvalho]

On 1 April 2013 19:46, 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.
>
> > 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.
>

I've been doing a lot of work with bitcoin lately.

Bitcoin is essentially a ledger where you have an array of fingerprints
(160 bit hashes of a public key) and a value (number of coins in wallet).

Transactions involve signing transfers from one key to another, which also
creates new coins in the process, when the distributed ledger syncs up.

Unfortunately bitcoin only supports ECDSA and not RSA.  But I wonder if a
fingerprint of your GPG key could be used as the basis of a payment ledger?


>
> Regards,
>
>         --dkg
>
>
> _______________________________________________
> 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/20130603/fb5538b1/attachment-0001.html>