Key fingerprints (not the DNS kind)

[Christian Weisgerber]

When you connect to a server for the first time, a fingerprint of
the server's public key is presented.  The idea is that if you
already know the fingerprint and it's a match, you can be confident
that you are talking to the server and not a man-in-the-middle.

People use this, e.g.:
http://www.openbsd.org/anoncvs.html

The typical fingerprint is just an MD5 hash over the public key.
Given how broken MD5 is, you have to wonder if a MitM can create a
new key with the same fingerprint.  I'm in particular concerned
about RSA keys, which are long and provide material to work with.
In fact, isn't this Lenstra/Wang/Weger's "Colliding X.509 Certificates"
attack from 2005?

Am I missing something?

There are three types of fingerprints that are shown to the user:

(1) MD5 in hex:

    2048 58:32:84:2f:e6:06:be:99:7e:1f:4e:49:c9:ac:04:e5 id_rsa.pub (RSA)

(2) MD5 as random art:

    +---[RSA 2048]----+
    |    ...          |
    |   o..           |
    |  . E.o .        |
    |  ..oo.*         |
    | . +..* S        |
    |  ..oo .         |
    |   =. +          |
    |  + .o .         |
    | ... .o          |
    +-----------------+
 
(3) SHA-1 as Bubble Babble:

    2048 xufok-vegum-ralym-tudob-zybyp-donyf-nifor-bocuc-behah-vilis-vexyx id_rsa.pub (RSA)

Bubble Babble fingerprints are only displayed by ssh-keygen -B,
which is of limited usefulness.  It looks like the sort of arcane
feature that could just be removed.

The other fingerprint formats should switch from MD5 to SHA-256 as
the underlying hash.  The devil is in the details.  How to display
a SHA-256 hash compactly?  Base64?  Truncate (eww, can o' worms)?
And how to manage the changeover from old to new fingerprints?

-- 
Christian "naddy" Weisgerber                          naddy at mips.inka.de