While discussing this with someone else, this was brought to my attention: https://natmchugh.blogspot.com/2015/09/md5-collisions-in-ssh-keys.html from 2015, showing colliding 2048-bit public keys to the same MD5 hash. At least, enough that the ssh-keygen tool was happy to interpret it as a valid public key and provide the MD5 fingerprint of it. Happily converts it to PEM format and all that fun stuff. If it's algorithmically sound or if IOS's SSH service will accept or use it I have not explored, but so far it seems potentially usable as a seemingly valid public key. So from that perspective, #1 appears achievable. Now, of course, #2 is where it gets..... complicated. Deriving the private key for the new 2048-bit public key is a wee bit ... hard, we could say. But if we can generate a 1024 or 768 bit pubkey that collides, then this as an attack vector becomes a lot more feasible. Since IOS isn't checking key length/enforcing minimum key lengths (and indeed, is not even storing the length of the original public key that was hashed, which would cripple the potential feasibility of this attack) and allows key lengths down to 768-bit.... The trick there then becomes if a 768-bit public key would ever in the full range collide with the unknown length hashed pubkey you are trying to collide with. If you can generate a 768-bit pubkey that collides with the hash you are targeting, then it becomes a computationally "simple" exercise relatively speaking. In 2010, it took what was estimated to be 1500 years of CPU time of a single core of a 2.2GHz Opteron (a 2009 CPU) to crack a 768-bit key. https://eprint.iacr.org/2010/006 - Obviously, they had parallelized out the problem and it did not actually take that long. Actual real-time it took 6 months. Approximately about 1000 cores were used, I believe. CPU and such system bandwidth has greatly increased since then, at a massive rate. Throw in GPU compute, custom ASICs, etc as well for good fun. But as noted, key length increasing causes an exponential increase in difficulty. Of course, if the only collision is in 2048-space somehow rather safe barring quantum computing. That's a big if. 1024-bit likely is achievable with sufficient resources and time, more resources, less time. Increases your potential collision space, too. A low hanging fruit, or easy win so to speak, here from an IOS perspective would be a configurable minimum key size accepted by the SSH service, switching the hash algorithm, or as someone else pointed out, even just a unique per-device salt - or a combination of all of these to make an easy short-term fix without sizable code changes. The correct fix, of course, would be storing the entire public key and only doing an exact match for authorization... -----Original Message----- From: Tom Beecher via NANOG <nanog@lists.nanog.org> Sent: Sunday, August 31, 2025 5:19 PM To: Dan Mahoney <danm@prime.gushi.org> Cc: North American Network Operators Group <nanog@lists.nanog.org>; Tom Beecher <beecher@beecher.cc> Subject: Re: beware: being old sucks 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
_______________________________________________ NANOG mailing list https://lists.nanog.org/archives/list/nanog@lists.nanog.org/message/UADC46ZE...