Re: MD5 is insecure

[Tom Beecher via NANOG <nanog () lists nanog org>]

Brent-

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?

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*.

The key blob is *encoded* , not hashed. base64(x) can never equal
base64(y), and therefore cannot collide.

*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?

Even if we assert you got this far, AND that everything happens this way :

y = md5_hash(KP1)

x = The data you 'injected' into the key blob that is KP2.

If md5_hash(x) = y , then yes you have tricked the device into using KP2.

HOWEVER, finding x such that md5_hash(x) = y is a preimage attack.

And as has been stated, preimage against MD5 is still not computationally
feasible.


On Sun, Aug 31, 2025 at 6:40 PM brent saner <brent.saner () gmail com> wrote:

> 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/VQCQSU5VAA5VXGB7WGXX3OPCGL576UTP/