Re: MD5 is fast

[Saku Ytti via NANOG <nanog () lists nanog org>]

I think it would be prudent to pay attention to the application OP is
talking about.

OP is talking about:
   - password hashes, this can be argued to matter, there are terrific
slow hashes for this
   - validating ISIS LSP, this cannot be argued to matter, the
collision isn't valid ISIS LSP

All of this information is already on the thread.


On Mon, 8 Sept 2025 at 22:24, Owen DeLong via NANOG
<nanog () lists nanog org> wrote:
> 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/



-- 
  ++ytti
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/UXM2Y75H5I57FOVEJOPDCAZEEMQJHGLN/