Subject: Key fingerprints?

From: Mouse <[email-masked]>
Date: Sat, 1 Dec 2012 17:44:25 -0500 (EST)

I've got a couple of suggestions for ssh implementors.

SSH implementations - or at least a few of them - use key fingerprints
to summarize keys to users, such as in "no host key saved for this
host, here's the host key we got, accept it?" questions.

As far as I can tell, how this is done is not standardized.  4251
appears to consider it an implementation choice, with a mild suggestion
of SHA-1 hashes converted to hex.  It seems to me it is in everyone's
interest for fingerprints to be comparable between implementations,
which calls for some kind of standardization, even if only de facto.

When I was writing moussh I investigated this a ltitle bit and it
appeared to me that the only other implementation I had at ready hand
(some version of OpenSSH, probably) used MD5 hashes of the public-key
data blobs, converted to hex with : used as an octet separator, a la
01:23:45:67:....  Since I wanted hashes fingerprints to be compatible,
that's what I implemented.

Since then, I've added a more compact - and, I find, easier to compare
by eye - representation, the same data content as the hex style but
represented in base 85 using most of the printable ASCII characters;
moussh now prints both forms in most cases when it has occasion to
print key fingerprints.  I've also seen a two-dimensional "random art"
representation, but I know nothing about the details behind it.

On another note, MD5 is showing weaknesses.  So far, all I've actually
seen reported is collision failures, but I expect second-preimage
failures to show up before too much longer.  While there isn't a whole
lot of wiggle room in key data blobs to take advantage of second
preimages, there is some.  So, I'd like to use something stronger than
MD5, but I also don't want to disturb people by presenting fingeprints
that appear to disagree with other implementations' fingerprints for
the same keys.  This means at least some degree of coordination with
how other implementations compute and present fingerprints.

So, here's what I'd like to do.  To be useful, these need different
implementors to work together, which is why I'm writing here: to
suggest that we collaborate on these.

- I'd like to collect specifications for the various fingerprint
   formats in use, with an eye to publishing them in some form,
   preferably with test vectors.  I can do the collecting and
   collating, and, in a minimal form, the publishing (a text file up
   for FTP or HTTP fetch); if these are considered valuable enough,
   someone else might want to publish them in other way (such as,
   perhaps, an Informational RFC).

- I'd like to come to some kind of agreement for how to compute and
   represent fingerprints in a way that's a bit more future-friendly
   with respect to hash algorithms than just printing hashes in hex.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: [email-masked] (Niels Möller)
Date: Mon, 03 Dec 2012 09:47:55 +0100

>    perhaps, an Informational RFC).

GNU lsh displays openssh-style md5 fingerprints, and ssh.com-style
"bubble babble". E.g., lsh --sloppy www.lysator.liu.se shows

  Received unauthenticated key for host www.lysator.liu.se
  Key details:
  Bubble Babble: xemoc-kovyp-nehoz-zacod-mohek-hurep-hybag-hizog-fahob-dydug-sexix
  Fingerprint:   18:2a:ea:db:b5:1f:f2:83:fb:d0:24:45:f8:9a:fc:d6

There are no deep thoughts behind this, just an attempt to be compatible
with what others do.

>    with respect to hash algorithms than just printing hashes in hex.

I'm kind-of skeptic to displaying the fingerprint in some form
intuitively recognizable and rememberable by humans. So I think the
primary use case is for the user who actually have the expected
fingerprint written down and wants to compare it to what's displayed on
screen.

I totally agree it would be nice to standardize the fingerprints. I
think it would make sense to

1. Use a stronger hash function than md5, and if standardizing something
   new at this time I think it's prudent to also choose something
   stronger than sha1.

2. Consider carefully what length of the fingerprint really is needed,
   and if we think something shorter than 256 bits is good enough,
   truncate the output of sha256 or sha3-256 or whatever function is
   chosen.

3. Use some more compact and/or more readable alphabet than hex. I don't
   have an informed opinion on whether or not things like bubble-babble
   or the "random ascii-art" thing really helps users.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: Mouse <[email-masked]>
Date: Mon, 3 Dec 2012 11:20:28 -0500 (EST)

>>    formats in use, [...]
> "bubble babble".

This is just the sort of thing I was looking for; I'll have to see if I
can dig up a spec for bubble babble fingerprints.  At worst I suppose I
can try to work it out from the code; if it's a GNU program I'd be
shocked if source weren't available.

> intuitively recognizable and rememberable by humans.

Yes, I agree; any fingerprint with enough information to be worth
bothering with is probably beyond what most humans will be willing to
memorize.

> So I think the primary use case is for the user who actually have the
> expected fingerprint written down and wants to compare it to what's
> displayed on screen.

Or - to cite my own use case - has the correct fingerprint in one
window and wants to compare it with the fingerprint displayed by an ssh
client in another window.

> 1. Use a stronger hash function than md5, and if standardizing
>    something new at this time I think it's prudent to also choose
>    something stronger than sha1.

Agreed on both counts.

> 2. Consider carefully what length of the fingerprint really is
>    needed, and if we think something shorter than 256 bits is good
>    enough, truncate the output of sha256 or sha3-256 or whatever
>    function is chosen.

I'm actually tending towards using multiple algorithms, each truncated
(or folded) to a short length and then concatenated, with tweaks like
the ones HMAC uses to reduce the utility to an attacker of weaknesses.
After all, we're hashing relatively small data blobs here; extra
computation is not a very big deal.

> 3. Use some more compact and/or more readable alphabet than hex.

Definitely.

>    I don't have an informed opinion on whether or not things like
>    bubble-babble or the "random ascii-art" thing really helps users.

In general, neither do I.  But I have found that, in my own case, the
base-85 encoding is _much_ more usable than the openssh-style hex.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 03 Dec 2012 11:39:22 -0500

> base-85 encoding is _much_ more usable than the openssh-style hex.

I'd be careful about going too far with this.  Compactness is nice, but
so is the ability to read a fingerprint over the telephone.  I think
that at least means being case-insensitive, and probably also avoiding
some other characters (I'm assuming we are starting with printable
ASCII).

-- Jeff

---

From: Mouse <[email-masked]>
Date: Mon, 3 Dec 2012 13:29:18 -0500 (EST)

>> In general, neither do I.  But I have found that, in my own case,
>> the base-85 encoding is _much_ more usable than the openssh-style
>> hex.
> I'd be careful about going too far with this.  Compactness is nice,
> but so is the ability to read a fingerprint over the telephone.

Agreed.  Different fingerprint presentations for different purposes.
My base-85 presentation is fairly specifically optimized for visual
comparison; moussh prints both the hex:hex:hex form and the base-85
form because they are optimized for different use cases and the
software has no way to tell which is more appropriate at the moment.

> I think that at least means being case-insensitive, and probably also
> avoiding some other characters (I'm assuming we are starting with
> printable ASCII).

Maybe have a table of 16384 words and print it 14 bits at a time using
them?  That's language-specific, of course....

Optimizing for comparing by eye is very different from optimizing for
voice (eg) over the telephone, and I would expect it to be difficult to
satisfy both at once.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign

---

From: James Cloos <[email-masked]>
Date: Mon, 03 Dec 2012 17:11:37 -0500

>>>>> "M" == Mouse  <[email-masked]> writes:

M> I've also seen a two-dimensional "random art" representation, but I
M> know nothing about the details behind it.

Cf openssh's key.c : key_fingerprint_randomart().

 http://www.openbsd.org/cgi-bin/cvsweb/src/usr.bin/ssh/key.c?annotate=1.99

They also implemented bubble babble in key_fingerprint_bubblebabble().

GnuTLS uses that randomart implementation, too.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 1024D/ED7DAEA6

---

From: "denis bider \(Bitvise\)" <[email-masked]>
Date: Wed, 5 Dec 2012 11:36:04 -0600

How can we have this whole conversation without mentioning Bubble Babble?

http://wiki.yak.net/589/Bubble_Babble_Encoding.txt

This was originally designed by SSH, and has been implemented in Bitvise 
products since our first versions.

All our products show Bubble-Babble fingerprints. For example:

xubem-kiloc-getad-ponyh-sagyb-sunyp-zirog-ninif-ponak-pisob-luxex

This is Bubble-Babble for a 1024-bit DSA key.

denis

-----Original Message----- 
From: Mouse
Sent: Saturday, December 01, 2012 16:44
To: [email-masked]
Subject: Key fingerprints?

/~\ The ASCII   Mouse
\ / Ribbon Campaign