Subject: [Cfrg] Fingerprint schemes resistant to similar-fingerprint-mining?

From: Bryan Ford <[email-masked]>
Date: Thu, 7 Apr 2016 12:52:26 -0300

OpenPGP needs a replacement for its old SHA1-based key fingerprint scheme, and while the topic is under discussion on the openpgp list, I’d like to bring up a question and see if there’s any broader interest in CFRG.

OpenPGP key fingerprints especially - but also cryptographic key-fingerprints in general - get printed on business cards, displayed on websites, and get used for “eyeball-comparison” of public keys or certificates, etc.  But how many users in practice bother to verify more than the first few (and maybe last few) digits of a fingerprint?  

The problem: as others have pointed out, this leaves practically all “manual-comparison” uses of fingerprints open to “similar-fingerprint-mining” attacks.  For example, you want to impersonate me, so you invest some CPU time into creating many PGP (or other) public keys until you find one whose fingerprint looks similar to mine in the first and/or last digits.  It’s fairly easy with todays hardware ’s mine for quite a few fingerprint digits matching whatever you want.  Then you post the public key on openpgp key servers, or send someone else E-mail claiming it’s from me, and your victim thinks it really is from me because they “checked” its fingerprint against what’s on my business card or web site…  

Possible solution: design new fingerprinting schemes to allow the creator of a new key pair to invest some “mining” time/effort deliberately into the key creation, basically creating a key pair that embodies a self-certifying proof-of-work that its fingerprint reflects.  This key-creation effort then greatly increases the amount of effort an attacker would have to invest to mine for a key whose fingerprint is similar in more than a few digits.  For example, if I invest around 1 minute into creating my key-pair, a similarity attack should cost an attacker with similar hardware around 2^B *minutes* worth of CPU time to get B fingerprint bits to match mine, rather than requiring only 2^B public-key-generation-and-hash calculations.

I briefly sketched one possible approach yesterday in this message on the openpgp list: https://mailarchive.ietf.org/arch/msg/openpgp/w-WTcu-RL4SgXJw0K51FtWFqUJ0 <https://mailarchive.ietf.org/arch/msg/openpgp/w-WTcu-RL4SgXJw0K51FtWFqUJ0>  This approach builds on Argon2 and ideas previously suggested by Christian Huitema and Philip Hallam-Baker and others.  See that if you’re interested in the details.

But my main questions for the CFRG list are: (a) do people consider this a problem; (b) is it important enough to try to solve; and (c) is it strictly an “openpgp thing” or is it potentially of broader interest, since PGP isn’t the only crypto-based protocol that uses uses fingerprints (though it may be most widely-deployed one that relies heavily on fingerprints)?

Thanks
Bryan