[Freedombox-discuss] identicons are not strong crypto [was: Re: Tap-to-share PGP key exchange]

Michael Rogers m-- at gmx.com
Mon Oct 3 18:35:37 UTC 2011


On 03/10/11 18:13, The Doctor wrote:
> Sort of like this?
> 
> http://www.thc.org/papers/ffp.html
> 
> I am surprised that no one has brought up bubble-babble fingerprints
> yet (https://secure.wikimedia.org/wikipedia/en/wiki/Bubble_Babble) or
> a randomart depiction
> (http://superuser.com/questions/22535/what-is-randomart-produced-by-ssh-keygen).

Thanks for the interesting links!

It seems to me that if an attacker knows what method a person verifying
a key will use (hex digits, identicons, bubble babble, randomart, etc),
the attacker will *eventually* be able to create a key that passes a
first-glance verification. The question is, how difficult can we make
the attacker's job?

To take an extreme example, most people are able to distinguish between
(at least) tens of thousands of faces and recognise (at least) dozens of
familiar faces. That's far better than we can do with random phrases or
ASCII blobs, so let's imagine we had a key verification system based on
faces.

In this imaginary system, every key would be digested down to, say, 160
bits of fingerprint, which would be used to set the parameters of a
face-drawing algorithm: the eye width, nose length, mouth angle and all
those other things that make a face unique. The system would be capable
of producing 2^160 faces.

Now let's assume, optimistically, that an average person can distinguish
between a million faces - roughly 2^20. That's far smaller than the
number of faces the system can produce. So if an attacker wanted to find
a first-glance match for a given key, the attacker would only need to
create 2^20 keys on average before finding a match, rather than 2^160.
To put it another way, the security level of the verification system
would only be 20 bits.

So what can we do to make the attacker's job harder? Two possibilities
come to mind.

The first is a technique borrowed from password-based encryption: we
make it hard to calculate the fingerprint of a key. For example, we
define the fingerprint as hash(f(hash(key)) rather than hash(key), where
f is a hard-to-calculate function such as scrypt [1] or PBKDF2 [2].
Ordinary users don't need to calculate very many fingerprints, so the
impact on them is small, but an attacker searching for a matching key
has to calculate a lot of fingerprints, so the impact on the attacker is
large.

The second possibility is a technique borrowed from salted hashing: we
make the fingerprint dependent on the verifier, so that a given user
always sees the same fingerprint for a given key, but different users
see different fingerprints for a given key. For example, we define the
fingerprint as hash(hash(key)|x) rather than hash(key), where x is a
per-user secret value. Without knowing my secret value x, an attacker
can't tell whether two keys have matching fingerprints from my point of
view.

Both possibilities have downsides, of course: the first introduces extra
CPU load and the second makes it impossible for two users to compare
fingerprints out-of-band, since they'll always see different
fingerprints for a given key. But I hope they serve to stimulate some
better ideas. :-)

Cheers,
Michael

[1] http://www.bsdcan.org/2009/schedule/events/147.en.html
[2] https://tools.ietf.org/rfc/rfc2898.txt



More information about the Freedombox-discuss mailing list