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 _______________________________________________ Freedombox-discuss mailing list [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/freedombox-discuss
