So I will correct myself here a little bit, specifically this statement that I am wrong on : The actual public key is still stored and used for the auth process; it
can't work otherwise
Dan is correct here in that : - SSH_MSG_USERAUTH_REQUEST contains the pubkey in the blob. - Cisco appears to be just taking that pubkey, taking its MD5, and if that MD5 matches what it has in the config, it will then use that pubkey for the rest of the bits. With MD5 , generating a collision is solved. But for this to be exploitable, you would have to : 1. Generate a colliding result that is ALSO valid for the public key algorithm specified. 2. Generate a private half of the key that is also valid for the algorithm specified. #1 is perhaps theoretically possible, but without knowing the math I'd say almost impossible. #2 still being impossible is the bedrock principle that makes asymmetric crypto work. On Sun, Aug 31, 2025 at 2:12 PM Dan Mahoney <danm@prime.gushi.org> wrote:
On Aug 31, 2025, at 06:43, Tom Beecher <beecher@beecher.cc> wrote:
Dan-
This paragraph is important to unpack.
[snip] Close , but not quite. The fingerprints are used *to identify which public key to use* for the challenge/response.
The actual public key is still stored and used for the auth process; it can't work otherwise. Just because the CLI only shows you the fingerprints doesn't mean anything.
I do not believe that to be the case.
If it were, why does copying the same hash to a different router/switch cause it to let you in? (I tested this, and say as much.)
I call out RFC 4252 section 7 here for a reason, it specifies that what’s transmitted is referred to as a “binary blob”, which is later broken down into the components in 4253 Section 6.6. What’s transmitted for RSA keys is the modulus (i.e your semiprime) and e (your exponent), which is effectively the entire public key, less the comment field.
This other statement is important as well :
Those places could have then generated an ssh private key, having a public key with the same md5 hash. It would have been mathematically hard to do so, but this is a possible offline (massively-parallel) attack. Just sitting generating keys. They would not have to try those keys against your router to attempt auth.
Any circumstance where the public part of *different keypairs* hashed to the same thing would mean that keygen algorithm is instantly dead and no longer usable. Anywhere.
Correct. It hasn’t happened, yet. But there have been rashes of weak rng’s in openssl (decades ago) that led to poor key choices that were more factorable, and there are now lists of public-key-blacklists (which IOS devices don’t check).
(https://factorable.net/, https://wiki.debian.org/SSLkeys)
And because it needs to be an md5 hash of the product of two prime numbers, it’s not like one can just pad random binary data in there to affect the hash.
I say that much in the paper, but I call out what could have been done differently, as well:
* Vendor could have stored the whole key, and not just given you the illusion it was being stored. * Vendor could have placed limitations on allowable key length. * Vendor could have updated the signature alg. * Vendor could have advised the use of a key only for this purpose.
Is it likely that someone’s still using a weak key from that long ago? God I hope not, but we’re still using 8 inch floppies in our nuclear arsenal and still have ATMs running WIndows XP, so I wouldn’t be shocked if some key were buried in some provisioning system somewhere.
Algorithms move, and at one point, DES and even 3DES was considered unbreakable. Right now, it would seem that generating a deliberate key that matches a known hash isn’t possible (even with the md5 weaknesses), but in my heart, I believe a dedicated nation-state with a good cyberwarfare budget would try anyway. RSA key generation is really only about finding primes, and if one good thing came out of cryptocurrency, it was a better understanding of how easy it is to get into custom FPGAs and ASICs to do this stuff.
Anyway, my point was that in light of Randy’s recently posted vulnerabilites, that any key that you might have used for pubkey auth into *any* device here should probably be retired, and that if for some reason pubkey is part of your workflow, you should probably generate and use a key *only* for that purpose, and not your general purpose id_rsa.pub. At the very least, one should think about how this is different from every other system out there.
-Dan