Bug#788783: openssh-client: uses MD5 for key fingerprints
"brian m. carlson" <sandals@crustytoothpaste.net> writes:
> > The remaining possibility is that the adversary has managed to come up
> > with a new public key (and matching private key) with the same
> > fingerprint as the target key, which was generated by an honest party.
> > But that's finding a second preimage, and it's /way/ harder than finding
> > collisions.
>
> Yes, it is finding a second preimage in the general case.
Right...
> However, it's possible to exploit collisions to find a very similar
> key to the legitimate user's—one which may be trivially weak, say with
> a 20-bit prime as a factor—but which nevertheless works with RSA.
I'd be interested if you could explain how. A reference to the
published literature will be fine. I'll accept references to papers on
the IACR ePrint server or arXiv.
> e is almost always a trivially small value, so any prime where that e
> works is sufficient. The goal is to impersonate. Who cares if it's
> with an insecure key?
I don't think this is the hard bit. The hard part is coming up with
anything at all, regardless of how meaningless it might be, whose MD5
hash is the same as that of the challenge public key.
> Since a collision costs approximately $0.65 to generate, one could try
> the attack repeatedly until a suitable n is found.
This is great, only collisions won't help you (much).
The best technique I can think of uses Kelsey and Schneier's expandable
messages, which uses collisions in the underlying compression function
to obtain a second preimage for the hash of a /very long/ original
message. Because the original message is very long, there are lots of
likely distinct chaining values obtained while hashing it. So the
strategy is to look for collisions between these and intermediate values
for your second-preimage message, so effectively you're searching for
second preimages at the compression-function level, and get to count all
of the applications of the compression function used to compute the hash
of the challenge message towards your attack. But all of this still
requires about 2^{128} compression-function applications total.
There's a slight problem. You can't just stick the appropriate suffix
of the target message onto the end of your second-preimage prefix,
because there's a length in the final block. This is where the
expandable messages come in, and this is where MD5's lack of collision
resistance becomes significant: you look for a lot of collisions between
message fragments of different lengths[1], so you can stitch them
together to pad out the prefix to whatever length you need for the final
block to come out right.
[1] I'm not actually /sure/ how easy this is with MD5, but I'll assume
that it's trivial for the sake of argument.
-- [mdw]
Reply to: