Re: MD5 is insecure

[brent saner via NANOG <nanog () lists nanog org>]

On Sun, Aug 31, 2025, 17:25 Tom Beecher <beecher () beecher cc> wrote:

> Which means if IOS does no pubkey packet length validation, you no longer
> > need to generate a keypair that has a pubkey that collides on MD5. You
> > just
> > need a blob that collides with that hash, and will *truncate* to a key you
> > control. Which is much easier to collide.
>
>
> To actually exploit this :
>
> Generating a collision isn't hard. But you'd have to generate a collision
> that was also valid to use in the key algorithm specified
> in SSH_MSG_USERAUTH_REQUEST.

Which is an undefined size, which isn't normally a problem, but keep that
in mind.

So now you actually need a preimage attack, and even for MD5 that's not
> feasible still.
>
> Even if you managed to pull that off, you STILL don't have valid private
> half of the keypair. And if you could do that you just broke all of modern
> cryptography so we have other problems. :)

Bob generates an RSA 4096 keypair, *KP1*. This keypair has public key *K1*.
On the wire, that pubkey component is sent like this in
*SSH_MSG_USERAUTH_REQUEST*:

# ( ... )
*0x00000007* (length: 7 bytes follow (or whatever length for the key type,
depending on if you're trying to auth with ssh-rsa, ssh-rsa2-sha256,
ssh-rsa2-sha512, etc.)
*0x7373682d727361* (string, "ssh-rsa". see above)
*0x00000003* (length: 3 bytes follow)
*0x010001* (RSA's *e*)
*0x00000201* (length: 513 bytes follow)
*0x......* (RSA's *n*)

Worth noting that this is the *same exact* format, encoded to base64, that
is the second column in your *~/.ssh/id_<type>.pub* file (e.g. in this
case, *~bob/.ssh/id_rsa.pub*).

IOS device *foo* has authorized a(ny) key with MD5 *C,* an MD5 checksum of
public key *K1*. As stated in the other thread, *foo* only bases authn on
if the *checksum* presented key matches *C*. *foo* does not store *K1* locally.
It does not use *C* to look up a local *K1*. The only course of action
forward, given that ...*interesting* design choice, then is to use the key
that the client presents - provided its checksum matches *C*. We agree on
that, yes?

Alice creates keypair *KP2*, with public key *K2*. Alice then pads junk to
*K2*'s *n* until she reaches collision in the wire-packed form with
*C,* creating
*Blob1*. Let's say Alice had to add 512 bytes to reach collision with *C*.

Alice now initiates an SSH connection with *foo*, and starts
*SSH_MSG_SERVICE_REQUEST*.
Alice sends *Blob1* to *foo* as part of *SSH_MSG_USERAUTH_REQUEST*:

# (...)
*0x00000007*
*0x7373682d727361*
*0x00000003*
*0x010001*
*0x00000401* (length: *1025* bytes follow instead of 513)
*0x......* (Alice's RSA's *n)*
*0x.... (junk data)*

*Foo* reads in that key and parses it.
While parsing, it already knows from KEX that it's RSA 4096. So let's say
the IOS version of sshd does something extremely stupid[0] and uses a fixed
length lookup table.
"Oh, it's RSA 4096. I need exactly 3 bytes bytes from the buffer for the
pubkey's *e* and 513 bytes for *n*. I can skip over the other unnecessary
bits and pieces in the buffer. Efficiency!!1[1]"

So it grabs....

3 bytes for *e*.

And it grabs...

513 bytes. For *n*.

Hey Tom, what would happen in that case?



[0] More stupid than authing based on key checksum, I mean, instead of
locally storing keys. And more stupid than using MD5 for that checksum. I'm
sure those are just flukes.
[1] "Efficiency", like you know. Not storing the entirety of a pubkey
locally, or using MD5 instead of a more expensive hashing algo.

>
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/GTPOZK25WZSH2HSF6VCBZJQAUP7G7BK2/