Re: MD5 is fast

[Owen DeLong via NANOG <nanog () lists nanog org>]

Except, it’s not 340282366920938463463 seconds to go, it’s ≤ 340282366920938463463 seconds to go.

That’s the worst case number if the attacker gets his brute force on the last possible attempt.

In reality, one should assume that most brute force attacks will succeed in roughly 1/2 that time, and if any 
intelligence can be applied to further reduce the search space, frequently, the time can be further reduced, often to 
between 1/8 and 1/32 of the original total number of hashes, sometimes even more.

So if we’re actually talking about 1/2 of 1/32 of your original number, it’s still 5316911983139663491.609375 seconds 
which is roughly 61538333138190.5496714 days or approximately 168482773821.19247001 years, so yeah, still reasonably 
safe, but a lot of people don’t consider these factors when thinking about hash safety, so it is important to bring 
them up.

Owen

> On Sep 8, 2025, at 11:29, nanog--- via NANOG <nanog () lists nanog org> wrote:
>
> The hash doesn't need to be slow if there are enough numbers to check. If you have to calculate 
> 340282366920938463463374607431768211456 hashes, it doesn't matter if each one takes a nanosecond and the bad guy has 
> 1 billion computers, because that's still 340282366920938463463 seconds to go.
>
> On 8/09/25 09:59, Vasilenko Eduard via NANOG wrote:
> > Hi Ytti,
> > Hi Dan,
> > Your comments on the performance are very important.
> > I still believe that any Hash must be slow enough, because if it were fast, then the attacker could take a big GPU 
> > and brute force it
> > (The routing message is very predictable; only the password is not known, but could be tested from the dictionary).
> > But what is slow? us or ms?
> > In support of the latter, look to https://www.ijcna.org/Manuscripts/IJCNA-2020-O-01.pdf.
> > It is hundreds of cycles per byte.
> > Acceleration helps, but not much (around 3x) https://github.com/minio/sha256-simd/blob/master/README.md.
> > A few milliseconds per every hop is expensive.
> > Eduard
> > -----Original Message-----
> > From: Saku Ytti <saku () ytti fi>
> > Sent: Friday, September 5, 2025 18:55
> > To: North American Network Operators Group <nanog () lists nanog org>
> > Cc: Vasilenko Eduard <vasilenko.eduard () huawei com>
> > Subject: Re: MD5 is slow
> >
> > On Fri, 5 Sept 2025 at 10:22, Vasilenko Eduard via NANOG <nanog () lists nanog org> wrote:
> >
> > > Any hash MUST be slow (by design) to withstand brute force. In the network device case, it is about 5ms for SHA-2 
> > > (of course, dependent on the control plane processor).
> > Out of curiosity, how did you arrive at 5ms?  I don't think it is important, but it is interesting to me.
> >
> > I'm more arriving at around 1us on core from <10years ago (w/ SHA instruction set) or 10us on older core per ISIS 
> > LSA.
> >
> > But we can't still include even this 1us or 10us to the convergence budget, because NOS almost always has most of 
> > the cores doing nothing, due to poor design and no commercial pressure to improve. So if this would actually matter, 
> > you could at the first point when receiving LSA call sha_validate on another core with access to a shared pointer to 
> > boolean sha_valid=false, which this other core sets to true, upon validating SHA. Then the original core which is 
> > guaranteed to do work exceeding 1us or 10us for that LSA will continue its work, and finally check that sha_valid is 
> > true, if not reject the work it did, making the integrity validation free provided it takes less time to validate 
> > the integrity than it takes to calculate the topology.
> >
> > --
> >   ++ytti
> > _______________________________________________
> > NANOG mailing list
> > https://lists.nanog.org/archives/list/nanog () lists nanog org/message/VV7SJROWHEFBEBXPSCJCXHVRZ2VFX7TX/
> _______________________________________________
> NANOG mailing list https://lists.nanog.org/archives/list/nanog () lists nanog 
> org/message/KPVZV7RZFU36PXWXCIGACF7OHU7CRUK6/

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