Subject: [openpgp] Fingerprint, Base32 or Base32C?

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 27 Apr 2015 14:10:05 -0400

I would like opinions on whether we should put a running checksum on
the fingerprint encoding or not.

The simplest encoding of a fingerprint is to take the BASE32 encoding,
truncate to the first n characters and group the result into sets of
five digits (according to the 7-2 rule).

Since each character encodes 5 bits and we have an 8 bit version ID,
we have 92 active bits in the following fingerprint:

xxxxx-xxxxx-xxxxx-xxxxx-xxxxx

The problem typing this sort of code in by hand is that it is a bit
error prone. If a mistake is made we don't know where.

For a modest increase in complexity, we can add a running checksum at
the cost of one bit per block.

Con: The above fingerprint with five chunks only gives 87 active bits
Con: While we can chain the checksums to give a pretty robust check on
the first block, we only have a small chance of detecting an error in
the last.

Pro: Easier for the user
Pro: Since it is easier, a six chunk block might be acceptable giving
111 active bits.

Coding Base32C is if anything a bit easier than Base32 since each 5
character chunk is now 24 active bits. We consume bits in increments
of 8 bytes.

If we want to make things really robust, we probably want to add in a
checksum character at the end, either in addition to per block
checksums or as an alternative:

xxxxx-xxxxx-xxxxx-xxxxx-xxxxx c

c = (Sum (x_i)) (mod 5)

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Mon, 27 Apr 2015 22:40:17 +0200

> the fingerprint encoding or not.
I'm a bit unsure about the use of this,... can you elaborate on the
benefits you think are reached with that?!

Isn't the FP already checksum enough by itself?
Adding another checksum over the fingerprint shouldn't give more
security, or does it (since if it would be so simple to forge similarly
looking FPs that the user may type in by accident we'd have completely
different problems)?

I guess adding a checksum over the fingerprint will just tempt people to
only verify that checksum.

Cheers,
Chris.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 27 Apr 2015 16:49:20 -0400

> only verify that checksum.

The idea is that when someone is typing in the fingerprint, the client
can perform a parity check to see if the fingerprint data is correct
as the user is typing rather than waiting to the end.

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Tue, 28 Apr 2015 00:20:13 +0200

> as the user is typing rather than waiting to the end.
Okay, I see...

Well I have no strong opinion against it, but as I've said before,... it
seems like "fingerprinting the fingerprint" and I guess it tempts people
to check even less carefully - on the other hand, you never can prevent
people from doing stupid things, so if someone really just compares the
checksum, then it's IMHO his fault, and not the existence of the
checksum.

Cheers,
Chris.

---

From: Tom Ritter <[email-masked]>
Date: Mon, 27 Apr 2015 21:46:41 -0500

> as the user is typing rather than waiting to the end.

This is getting pretty far into usability.  Which I don't think is
bad, but it's just a bunch of assumptions that weren't unpacked right
away, and ignores alternatives.

There are lots of ways to compare fingerprints, some of which will not
work in the situation at hand.  Goals of any fingerprint comparison
mechanism should be to reduce the level of effort required by the
user, and reduce the sharp edges of failure situations.

Some (most?) of the situations one will encounter:
a) Comparing two fingerprints that are on the same desktop computer
b) Comparing two fingerprints that are on the same mobile device
c) Comparing a fingerprint between a desktop and mobile (in either direction)
d) Comparing a fingerprint between a desktop and paper
e) Comparing a fingerprint between a mobile device and paper

(Technically, I really mean 'desktop' to mean 'any computer without a
webcam' and mobile device to mean 'any computer with a camera'.  So
replace 'mobile' with 'laptop' in many instances.)

I think QR codes are excellent comparison mechanisms.  Look at
situations (c) and (e).  Desktop (or paper) displays a QR code, Mobile
reads the QR code and says 'They match!'  What's a less user-effort
level and less error-prone mechanism?

For situation (a), I would say the answer should be 'copy-and-paste'.
I envision a key verification UI as saying (below the displayed QR
code) a text box with a label "Or paste the fingerprint beginnging
with WXYZ here:".  You paste it, if it matches, you're set.

For (b).... mobile copy and paste sucks. Fortunately, I'm struggling
to come up with a feasible situation where you have a verified
fingerprint in one mobile app and you need to get it to a second. It's
more likely you have a public key 'pointer' (something that would get
you a public key, like a url or fingerprint in an email signature) and
you want to use it to get (not verify) a key.

And for (d), you have that awkward "Hold the card up to the screen and
try and compare them by shifting your eyes up and down".  Typing *may*
be less error-prone. If it had a running checksum it probably would
be. But asking users to type things in feels like it would be really
jarring in a user's workflow.

-tom

---

From: Derek Atkins <[email-masked]>
Date: Tue, 28 Apr 2015 10:14:11 -0400

> as the user is typing rather than waiting to the end.

Why would someone type in a fingerprint?  Could you give me a use-case
for that?

The only use case I've ever seen is that you copy-and-paste it onto your
business card (or presentation, or other printed/distributed material),
and then the verifier performs a visual match later between the printed
material and their verification screen.

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 28 Apr 2015 11:12:49 -0400

> material and their verification screen.

Well, I would flip it round then and say, why would a user ever
interact with a fingerprint other than on a business card?

There are many other cases where devices will be exchanging
fingerprints under the covers. But I don't expect the user to ever see
those. If we meet at IETF and bump iPhones then I don't expect to see
a fingerprint unless I open up an 'advanced' tab.

Same for email. Lets imagine this email had a header that said:

Fingerprint: ufi:xxxx-xxxx-xxxx-xxxx-xxxx-xxxx; holder=[email-masked]

Your email client could collect that automatically and take it as
probable cause to suspect that the specified fingerprint might be
associated with [email-masked].

Now as stated, that would not be proof but we can add in mechanisms
that would enable a challenge-response verification to be performed
automatically and transparently. that is slightly more complex than it
sounds because we have to avoid getting fooled by mailing lists, etc.
But at this point any mailing list that isn't giving the correct SMTP
headers is likely being spam filtered away anyhow.

But for these applications we can use a 256 or even 512 bit
fingerprint and it isn't necessary to base32 encode it either unless
we think it might get translated to a little-fingerprint at some
point.

Same goes for QR codes. There really is no need for the QR code to be
based on the base32 encoding, it can be calculated from the binary or
base64.

When it comes down to it, business cards and legal documents are the
only places I expect the base32 fingerprint to be seen.

That said, I am really on the fence on Base32C. Another way to skin
the same cat would be to have an interactive protocol with whatever
service uses fingerprints as index terms. With a population of a
million keys (2^20) a fingerprint should start to become unique after
the fourth letter is typed. So the service could easily construct a
'did you mean' concordance.

---

From: Derek Atkins <[email-masked]>
Date: Tue, 28 Apr 2015 11:31:38 -0400

> interact with a fingerprint other than on a business card?

I've seen them on business cards, web sites (not sure why I'd believe
that), and printed on Letter paper at keysigning parties.  But my
question remains unanswered: When would someone ever need to *TYPE* in a
fingerprint?

The only time that I think a fingerprint would need its own checksum is
if users are actually keying a fingerprint in for some reason.  I don't
see any use case where this would ever happen.

> a fingerprint unless I open up an 'advanced' tab.

Sure, and in these cases you can just use the binary fingerprint
directly.  Or better yet, exchange the full keys/certificates.

[snip]
> only places I expect the base32 fingerprint to be seen.

*nods*  -- and need to be visually inspected/compared.

> 'did you mean' concordance.

Interesting concept..  But again, why would you be typing it in?  What's
the use case here?  The only use-cases I've seen are where the user
visually verifies that the printed fingerprint == the computed
fingerprint.

-derek

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 28 Apr 2015 11:58:33 -0400

> visually verifies that the printed fingerprint == the computed

Look, my concern here is purely that I don't want to have to redo the
code I write this week because someone proposes this as an addition
later on.

I think we have established that it is not worth doing.

If people are reading in a business card why not do OCR on their phone?

So we are looking at 95% of the uses of fingerprints being to provide
a visual verification of a fingerprint being displayed to them. That
looks good to me.

We can even (modulo the possibility of ridiculous patent claims)
consider a step further and have an image based Base2^20 display of
the same data.

Lets say we get an open source image library with 2^20 visibly
distinct entries. We number the entries and form a Merkle tree over
them. This gives us an alphabet where we can check every character
against the root hash of the Merkle tree. We then prepend the Merkle
tree chain to each gliph making it verifiable against the root
fingerprint.

We can now have a collection of untrusted servers that serve up this
set of glyphs. At 4KB on disk per 120x120 pixel glyph, that is only
4GB.

So if Alice is using a 125 bit fingerprint (Work factor 2^117), her
Base64 fingerprint is:

aaaaa-bbbbb-ccccc-ddddd-eeeee

The equivalent Base2-20 fingerprint would be a sequence of images and
have a work factor of (2^112)

[z]-[z]-[z]-[z]-[z]-[z]

Anyone know where we might scrounge a million images? WikiSource perhaps?

It would probably behoove us to check them in some fashion but this
could be crowdsourced.

The idea of using images as an alphabet has ample prior art going back
to ancient Egypt.

---

From: Alessandro Barenghi <[email-masked]>
Date: Tue, 28 Apr 2015 16:13:33 +0000

> The idea of using images as an alphabet has ample prior art going back

In this case, wouldn't it be viable, while keeping a text representation
of the fingerprint, to employ a diceware-password-like approach to
represent the fingerprint?

With a reasonable english dictionary you get ~15 bits per word, which
gets you up to a reasonable margin rather fast (~8 words) and is easier
to inspect and compare visually.

The possible downsides of this approach are:
-- The need of storing a standardized dictionary
-- The possible mess with internationalization (although employing one
dictionary per language and adapting the client to read/print
fingerprints in a selectable language may get around this)

Cheers

Alessandro

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Tue, 28 Apr 2015 18:15:09 +0200

On Tue, 2015-04-28 at 11:12 -0400, Phillip Hallam-Baker wrote: 
> fingerprints under the covers.

And most of the time they should probably work with the keys themselves,
than using the fingerprint.

> But I don't expect the user to ever see

I'd generally refuse to design the next version of OpenPGP targeted
around use cases which inherently have very questionable security.
Especially smartphones are not really trustworthy for doing secure
crpyto,... so you need more reason than "it would be nice for
Apple/Android/Smartphone/JavaScript based E2E crypto/etc." in order to
convince me.

> associated with [email-masked].

And what's the use/benefit of this? The sender of an email is already
identified by it's From: header, an in order to trust that it needs to
match a properly signed UID on the key.
Works already fine?!

Further, this shouldn't be part of an OpenPGP standard,... we're not
defining mail.

It's ok if we define a fingerprint format, perhaps even URI schemas, but
that's it.

> headers is likely being spam filtered away anyhow.

What kind of challenge response? I.e. what should it prove? 

> based on the base32 encoding, it can be calculated from the binary or

I don't think we should define too much fingerprint formats, especially
the "short" are always kinda dangerous... it's like with the key IDs,..
people use it in insecure ways.
I'm also highly sceptical towards any formats that are not human
readable (e.g. QR).

> only places I expect the base32 fingerprint to be seen.

?? Every piece of software which deals with the keys and shows their FPs
for verification?

> That said, I am really on the fence on Base32C.

Does it have any big advantages over plain BASE32?

Cheers,
Chris

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Tue, 28 Apr 2015 18:57:45 +0200

> code I write this week because someone proposes this as an addition

I guess we're just at the start of the next standard,... writing code
now and assuming (and/or demanding) things to be stable is probably a
bad idea.

Cheers.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 28 Apr 2015 13:01:02 -0400

> represent the fingerprint?

Interesting idea. Oddly enough, I have an intern who is already
working on something very similar.

> to inspect and compare visually.

32768 words is very do-able. Hunspell English has 621,180 by the
looks. Not quite a million but it is quite likely we could get there
with affixation rules, plurals, etc.

First thing is probably to parse the flat file and then throw out
words that are too short, too long or too similar and see what is
left.

> fingerprints in a selectable language may get around this)

There would have to be different languages for different locales,
naturally. But in general, I think the pictures plus the words would
be fine.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 28 Apr 2015 13:04:05 -0400

> now and assuming (and/or demanding) things to be stable is probably a

My concern is that when a nincompoop decided to release code
implementing the <img> tag in HTML he gave the community less than 16
hours to review before he had made it a fait accompli. As a result the
<img> tag still does not handle displays with resolutions other than
75dpi consistently twenty years later.

Once code ships it is very hard to put the toothpaste back in the tube.

---

From: Bill Frantz <[email-masked]>
Date: Tue, 28 Apr 2015 10:14:37 -0700

On 4/28/15 at 10:01 AM, [email-masked] (Phillip 

>with affixation rules, plurals, etc.

Do remember that, as languages go, English has a rather large 
vocabulary. I don't know of any languages where 32K is a 
problem, but when over 100K or so, there is a problem. Also, 
even in English, we may want to limit the words to common words 
with different pronunciations, avoiding the there, their, 
they're problem.

While this group probably won't pick the word list, we do need 
to keep it relatively small.

Cheers - Bill

--------------------------------------------------------------
Bill Frantz        | There are now so many exceptions to the
408-356-8506       | Fourth Amendment that it operates only by
www.pwpconsult.com | accident.  -  William Hugh Murray

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 28 Apr 2015 13:20:30 -0400

32K words is much easier to check visually. And such a word list would
probably compress to 150KB which can be embedded in devices easily
enough.

"Before we begin our banquet, I would like to say a few words. And
here they are: Nitwit! Blubber! Oddment! Tweak! Thank you."

On Tue, Apr 28, 2015 at 1:14 PM, Bill Frantz <[email-masked]> wrote:
> On 4/28/15 at 10:01 AM, [email-masked] (Phillip Hallam-Baker) wrote:
>
> Do remember that, as languages go, English has a rather large vocabulary. I
> don't know of any languages where 32K is a problem, but when over 100K or
> so, there is a problem. Also, even in English, we may want to limit the
> words to common words with different pronunciations, avoiding the there,
> their, they're problem.
>
> While this group probably won't pick the word list, we do need to keep it
> relatively small.
>
> Cheers - Bill
>

---

From: "Derek Atkins" <[email-masked]>
Date: Tue, 28 Apr 2015 13:27:05 -0400

Reminds me of the usability portion of Neil Haller's (et al) S/KEY system.
 It used a dictionary of 2048 words, choosing 6 to encode a 64-bit number.

-derek

On Tue, April 28, 2015 1:20 pm, Phillip Hallam-Baker wrote:
>> vocabulary. I
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

---

From: "Neal H. Walfield" <[email-masked]>
Date: Wed, 29 Apr 2015 12:08:59 +0200

At Tue, 28 Apr 2015 16:13:33 +0000,
> to inspect and compare visually.

I wonder if less if not more.

If you look at the diceware list, it has "easy to remember words" like
"aaaa", "abner" and "adair".  And, this list is just 7776 words long.
These are not only hard for a native speaker to memorize, but also for
those who speak english as a second language.

If we are going to make a new word list, I would recommend using
something based on the voice of america simply word list.  This
includes 1500 simple words, which all english speakers with basic
proficiency are familiar with.

Alternatively, there is the PGP Biometric word list [1], which aren't
as simple, but are phonetically distinct.

[1] https://en.wikipedia.org/wiki/Biometric_word_list

Neal

---

From: Derek Atkins <[email-masked]>
Date: Wed, 29 Apr 2015 10:07:08 -0400

> Once code ships it is very hard to put the toothpaste back in the tube.

I think you'll get more than 16 hours to study things here.  So let's
not be more melodramatic than usual, please.

Indeed, you've had many more that that so far and still haven't provided
a use case for someone to actually need to type in a fingerprint such
that a checksum would be useful.  All I've received is
"but.. but.. someone COULD come up with one" or this example of the HTML
img tag, neither of which is useful to anyone to decide to add
(apparently needless) complexity when we're trying to reduce complexity.

-derek

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 29 Apr 2015 10:19:25 -0400

> not be more melodramatic than usual, please.

My point was, I don't want to be the next nincompoop.

> (apparently needless) complexity when we're trying to reduce complexity.

Yes, I conceded that already. I think it is pretty clear that if
anyone wants to resurrect Base32C they have to show a really good use
case that can't be addressed by an autocomplete/autocorrect service.

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Wed, 29 Apr 2015 16:27:17 +0200

> My point was, I don't want to be the next nincompoop.
Then the best thing is probably to wait a bit and not start implementing
(and "selling") things before the real discussions have even started.

Actually, I think that (often quite stupid) "activism" than can be seen
in many areas of crypto recently (e.g. "web based E2E crypto"  which
some groups/companies try to sell .... I mean WTF!??!)... are quite
concerning.
If I'd be the NSA and would want to sustainably weaken crypt... that's
just how I'd do it. 

Cheers,
Chris.