[messaging] Useability of public-key fingerprints

[Trevor Perrin]

On Tue, Feb 11, 2014 at 3:32 PM, Tom Ritter <tom at ritter.vg> wrote:
>
> RE: Moxie and fingerprints are horrible. :) I agree-ish. I don't think
> they're crucial for everyone, but I think eventually there's going to
> be sharp edges that wind up poking through the abstraction. We've
> talked about persistence of keying material and the inability for an
> attacker to MITM you forever - but eventually you need to rekey
> because of device change.

Agreed that key continuity and key fingerprints complement each other.
 Continuity so your device remembers keys and you don't have to
repeatedly check them, and fingerprints for when you want to check a
new or changed key, or double-check an important key.

With trusted online directories we could make "fingerprint" checks
automatic.  But being able to manually check an important public key
against different sources (including printed / written / spoken) will
always have its uses, I think.


> Some of the places where I see fingerprints continuing to be useful
> far into the future:
>  - Business Cards. My key is at <this url> and the fingerprint is [field]
>  - You are handed a new device and {don't have access to your database
> of trusted fingerprints/need to accomplish work, quickly}. Your
> contact sends you a <OTR message/pgp-signed message/whatever>. Do you
> recognize this fingerprint?
>  - "Here, SSH into my server, I set you up an account." "Is <this> the
> SSH fingerprint?" "Uh.... yea I recognize that."

Interesting that your 2nd and 3rd cases involve recognizing a
fingerprint from long-term memory.  That's a hard use case for
fingerprints.  At most I'd expect a user to remember a few bytes,
which isn't a secure check.

The main use case I see is comparing two fingerprints, one on your
screen for your communication partner, and one you're checking against
(from a phone call, a slip of paper, a friend's screen, a webpage,
etc.)


> In different contexts vastly different options are preferential.
>  - If I have a business card two good options are having the PGP
> fingerprint on the bottom margin so I can hold it up to my screen, or
> having a QR code scan to a copy-pastable text snippet I can paste
> below the actual fingerprint
>  - Orally, a restricted subset of alphanumeric characters will make a
> good fingerpint. Read aloud the following two numbers: 0xBCCD388AEEA8
> and 0x196442F6392

I've been advocating base32 because it gets you a small string and
lends itself to "pseudowords" which I think are easier to read and
hold in short-term memory.

But you raise a good point that a more restricted alphabet might be
easier to verbalize, so there could be a tradeoff here.


> The THC tool that brute forces look-alikes, with the tricks you'd
> expect: it weighted fingerprints that matches better at the beginning
> and ending higher, it weighted '3' as somewhat close to to '8' but not
> as close as 'B', etc. Such a tool can be built for any field we come
> up with.

I think the THC "fuzzy fingerprint" tool isn't actually that
effective.  Here's its "high score" outputs (
https://www.thc.org/thc-ffp ):

  08:54:5d:27:f8:e9:47:4e:49:8a:87:7e:03:cc:98:73   (target)

  08:54:5d:27:a1:5b:82:39:f6:ba:79:df:67:6d:78:73   (14 hour run)

  08:54:56:2c:28:d6:87:89:5e:02:a6:fd:43:c9:d8:73   (109 day run)

  08:54:5d:39:d6:20:58:b3:f0:99:39:2d:7d:2c:98:73   (63 day run)


You'd need a lot more computation to fool anyone who's doing more than
a cursory check.

For example, the pseudo-word fingerprints have 25 base32 characters,
grouped as 6-4-5-4-6.  The current bitcoin hashrate is around 20
petahashes or 2^54 hashes/sec, so it would take ~30 seconds to match
the first and last groups, and ~1 year to match one of the 4-character
groups as well.

And all that effort is defeated (and detected!) if someone checks at
least 17 of the 25 characters.


> Besides Trevor's examples:
> Here are some already made:
>  - Identicons:
> http://haacked.com/archive/2007/01/22/Identicons_as_Visual_Fingerprints.aspx/
>  - Monsters: http://www.splitbrain.org/projects/monsterid
>  - Wavatars: http://www.shamusyoung.com/twentysidedtale/?p=1462
>  - Unicorns (really)
> http://meta.stackoverflow.com/questions/37328/my-godits-full-of-unicorns
> Here are some more ideas:
>  - A spirograph
>  - A color pattern, a gradient
>  - A floral pattern, or flannel, etc
>  - A geometric plot on a Cartesian graph
>  - A geometric plot on a globe (potentially limited to landmasses and
> ignoring oceans)

I agree with dkg's skepticism of visual fingerprints [1].  They're
less flexible than text which can be handwritten or verbalized.  I
don't know any studies showing they're effective.  And the main
argument seems to be that they make it easy to notice that unrelated
fingerprints are different.  But that's easy even with text!

The test should be:

 * Does the format resist false-accept errors even when an attacker
expends significant computational effort on a "fuzzy match"?  I don't
think we know the answer for visual fingerprints.

 * Does the format resist false-reject errors when the verifier is
comparing identical fingerprints with different color tones,
resolutions, aspect ratios, dirt or scratches, etc.  I'd worry that
uncertainty over which visual differences are insignificant could be a
source of confusion which text fingerprints don't have.


> Take a step back forward: let's say we magically have a geometric map
> plot that people recognized with pretty good confidence.  What would
> this get us? I keep imagining my OTR conversation having their
> map-fingerprint visible so I would get used to seeing it. And seeing
> their map-fingerprint in my mail client.  Are we gaining anything by
> getting a user to recognize their friend's fingerprint?
>
> I'm not sure I see a context where we are, honestly.

Yeah, I think trying to remember fingerprints and recognize them on
every conversation is the wrong way to get value out of fingerprints.
It makes more sense to just have them as an option for users to
perform infrequent checks (on new or changed keys, or to double-check
an important key), and then have software remember that key.


> RE: Pseudowords. Maaaaybe.  Just like THC's tool, I could create one
> that aims to produce similarly-looking pseudowords. And since the
> words are not words, I think people's pattern recognition will be
> tricked more easily than with an actual wordlist.  I think a usability
> study could be in order. ;)

Yeah, we need some studies here...


Trevor


[1] https://moderncrypto.org/mail-archive/messaging/2014/000013.html