Sep 1, 2025 Current Resources

RE: beware: being old sucks

nanog mailing list archives

From: Gary Sparkes via NANOG <nanog () lists nanog org>
Date: Sun, 31 Aug 2025 22:02:54 +0000

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/UADC46ZETJWV2UVWIHNYUY6775W3ULE4/
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/5NSM4RUFI3SBHELZCGUHIWOFNPGL77C6/

Current thread:

beware: being old sucks Randy Bush via NANOG (Aug 21)
- Message not available
  - Re: beware: being old sucks Randy Bush via NANOG (Aug 30)
    - Re: beware: being old sucks Dan Mahoney via NANOG (Aug 31)
    - Re: beware: being old sucks borg--- via NANOG (Aug 31)
    - Re: beware: being old sucks Tom Beecher via NANOG (Aug 31)
    - Re: beware: being old sucks Dan Mahoney via NANOG (Aug 31)
    - Re: beware: being old sucks brent saner via NANOG (Aug 31)
    - Re: beware: being old sucks Seth David Schoen via NANOG (Aug 31)
  - Re: beware: being old sucks Tom Beecher via NANOG (Aug 31)
  - RE: beware: being old sucks Gary Sparkes via NANOG (Aug 31)
  - Re: preimage and collision attacks nanog--- via NANOG (Aug 31)
Re: beware: being old sucks nanog--- via NANOG (Aug 31)
Re: beware: being old sucks Liudvikas Bukys via NANOG (Aug 31)
Re: beware: being old sucks Tom Beecher via NANOG (Aug 31)
Re: MD5 is insecure nanog--- via NANOG (Aug 31)
Re: MD5 is insecure Dan Mahoney via NANOG (Aug 31)
Re: MD5 is insecure Pedro Prado via NANOG (Aug 31)
Re: MD5 is insecure Krassimir Tzvetanov via NANOG (Aug 31)
Re: MD5 is insecure brent saner via NANOG (Aug 31)
Re: MD5 is insecure Tom Beecher via NANOG (Aug 31)