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

[The Doctor]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 10/03/2011 02:35 PM, Michael Rogers wrote:

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

Chernoff faces?

https://secure.wikimedia.org/wikipedia/en/wiki/Chernoff_face

Critique: http://eagereyes.org/VisCrit/ChernoffFaces.html

Implementation in Java: http://people.cs.uchicago.edu/~wiseman/chernoff/

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

The question there would be, what kind of CPU power would be necessary
to brute-force enough Chernoff faces to come up with a
close-enough-for-government-work face that spoofs the user?

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

My question answered.  Thank you.

> Both possibilities have downsides, of course: the first introduces
> extra CPU load and the second makes it impossible for two users to
> compare

On a plug server running Freedombox, this could be problematic.  Or,
it might be slow only at first install (like generating SSH host keys).

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

I do as well.

- -- 

The Doctor [412/724/301/703]

PGP: 0x807B17C1 / 7960 1CDC 85C9 0B63 8D9F  DD89 3BD8 FF2B 807B 17C1
WWW: https://drwho.virtadpt.net/

Who are you?

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk6LPysACgkQO9j/K4B7F8EpjwCgveUY1WWQ457/UACWj1TIzlfH
2ykAoK/ETmmgbqhgQPwPDfHXyLEq5L2m
=VrhI
-----END PGP SIGNATURE-----