[messaging] Useability of public-key fingerprints

[Robert Ransom]

On 1/29/14, Daniel Kahn Gillmor <dkg at fifthhorseman.net> wrote:
> On 01/30/2014 01:19 AM, Robert Ransom wrote:
>> The difference is that you can encrypt messages to a key offline, but
>> you need to be connected to the Internet (and to a working directory
>> server of some sort) in order to encrypt messages to a fingerprint.
>
> There is a hybrid approach to doing a handshake like this between two
> users in person, though, if both have computing devices with them.  You
> can use human-inspectable mechanisms like QR codes or acoustic coupling
> to transmit a fingerprint, and then use whatever (non-inspectable)
> higher-bandwidth channel exists between the two devices (802.11b, NFC,
> bluetooth) to transmit the full key/metadata, which each peer then
> verifies against the fingerprint.

If the parties can set up an interactive connection, you can use a
40-bit ephemeral password to authenticate the key.  It wouldn't even
require a PAKE protocol.


>> That's another of Ross Anderson's usability lessons: if you want the
>> user to check a fingerprint, make the user type it in and have the
>> software compare it.  (And in that case, it may as well be a key or
>> password of some sort, especially with ECC.)
>
> This is a really key insight, and i've found it to be a very useful
> workflow to have users enter data rather than asking them to sustain the
> effort to make a comparison.  Do you have a reference for Anderson on this?

Section IV (PDF pages 3 and 4) of
<https://www.cl.cam.ac.uk/~rja14/Papers/homeplug-soupspaper.pdf> is
one reference.

Almost everything he knows about security engineering is somewhere in
his book ‘Security Engineering’, which everyone involved in security
should read.


> I'm not convinced that users might just as well enter the full ECC key
> as a shorter fingerprint, though.  For an application that wants 112-bit
> cryptographic strength for this key exchange, users would have to
> transcribe at least a 224-bit ECC key, which is significantly more
> taxing (and error-prone) for most humans than transcribing a 112-bit
> fingerprint.

Maybe.

If you want to evaluate key sizes rationally, you need to decide two
things: (a) How many cryptographic operations can They perform in
order to attack the system?  (b) What is the maximum acceptable
probability that They will succeed in breaking any key used in the
system?

If They can perform 2^k operations, and you want a probability of 2^-b
that They will break any key in the system, you need at least b+k bits
in symmetric secrecy keys, and at least b+2*k bits in group-element
exponents and any hashes exposed to collision attacks.  (Secrecy keys
are only exposed to preimage search; group-element exponents are
exposed to search for collisions on the function (a, b) |-> a*B +
b*P.)

If your reason for wanting ‘112-bit security’ is that your attacker
can perform 2^80 operations and you want a maximum probability that
They will break *something* with their attack of 2^(-32), then a
32+2*80 = 192-bit EC group is enough.  With Edwards curves, the field
order for that must be at least 194-bit; 2^194 - 33 is not too bad,
and 2^198 - 17 may be better for implementations.  (I wouldn't even
consider 2^196 - 15.)

(Note that if you're not seriously size-constrained, I would strongly
recommend the less rational, but safer, easier, and faster rule of
thumb “256-bit symmetric keys everywhere; Curve25519 for everything
connected to the Internet; Curve3617 if you're willing to go to the
trouble of storing the key offline”.)

>  What happens if the user makes a mistake?  Are they locked
> out from communicating?

If the user typos an encryption public key, their message is just
plain gone.  If the user typos a symmetric secrecy key, it'll at worst
be a PITA to recover the data; if they're trying to decrypt a file,
they'll just try again.  If the user typos an authentication key,
they'll find out pretty quickly.

> If the goal is a usable tool, it's probably worth taking advantage of
> other mechanisms to bootstrap up from the smallest reasonable value we'd
> want people to transcribe, as long as the fingerprinting mechanism used
> is cryptographically strong.

Yes.


Robert Ransom