Re: MD5 is slow

[Matthew Petach via NANOG <nanog () lists nanog org>]

On Tue, Sep 9, 2025 at 1:10 AM Vasilenko Eduard via NANOG <
nanog () lists nanog org> wrote:

> The problem is smaller: the attacker needs to predict only the password;
> some packets are predictable for 100%.
> The password is the thing that you put at the end of a command: "ip ospf
> message-digest-key 1 md5 c1$c0"
> How long could the password be? 10-12 letters are considered to be a good
> password (if upper case, lower case, special letters, numbers), but people
> typically use just words (only 100k words are typically well-known).
> Then some APTs have billions of typical passwords in the database
> (prioritized for probability). They could just try them all on a good GPU.
> It is needed for hash to be slow. Hence, for example, SHA-2 consists of
> "And, Xor, Or, Rot, Shr, Add (mod 2^32)" in 64 or 80 rounds! (for every
> block of 512bits).
> Hence, a few milliseconds twice per every hop for a rather small control
> plane message.
>
> It is strange for me that nobody cares about this latency.
> Eduard


Eduard,

I think the reason that it seems to you "that nobody cares about this
latency" is that you seem to
be focusing on a different latency from what everyone else thinks about
when worrying about latency.
Initially, you seemed to be concerned about a completely incorrect 5ms per
MD5 hash number,
which multiple people pointed out was completely wrong.  The idea that hash
functions need to
be "slow" to prevent brute force attacks is a leftover from the idea that
password comparisons
would be slowed down after a certain number of tries to slow the rate of
brute force password
attacks.  But that's not a function of the hash itself, that's a function
of the programs calling the
hashing function inserting extra latency.  The hash calculation itself is
breathtakingly fast.
If we do a quick web search and look at the top few results from the past
18 months, people
report that relatively modern CPUs can do about 43 million MD5 hashes per
second per core.
That would mean a given MD5 hash is taking about 23 nanoseconds
(0.00000002325581395348 seconds)
Even if every LSP update is MD5 hashed separately, sequentially on a single
CPU core, that still means
flooding 1000 LSP updates is going to add 23 microseconds of latency to
your routing convergence.
Flooding 1000 LSPs sequentially through 50 nodes in a large network?
You've finally hit 1ms of added
time to your overall convergence due to the MD5 lookups *throughout the
entire network*
Compared to the rest of the flooding process timers and SPF calculation,
that latency is negligible.

Additionally, that's pretty much the worst-case scenario, when you've had
such a massive change
to the network that you have 1,000 LSPs that all need to be updated and
flooded out at once.
In most cases, you've got orders of magnitude fewer updates going on, so
your MD5 latency
is going to add fractions of a microsecond to the convergence time.

Comparing that to the speed of light across town, and you quickly realize
that the MD5
calculation is a fraction of the time it takes to send that LSP from here
to the router on
the other side of the city, let alone a router on the other side of the
country.  When most
people talk about latency, that's the latency that really starts to matter.

Worrying about the speed of the MD5 calculation when it comes to trying to
speed up convergence on a modern router with a modern multi-core CPU is
like worrying about the wind resistance from the dirt on the hairs on the
back of
the flea that's biting the tip of the ear on the dog while it has its head
sticking out
the passenger window of the car on a warm sunny day while zipping down the
highway.   (The car that is, not the flea).
If you want to reduce your gas consumption, you pull the dog inside and
roll up the
window.  You don't swerve all over the road trying to brush the dirt off
the hairs on
the back of the flea.

If you're worried about IGP convergence times, there's much bigger
contributors
to the overall convergence time that are much better targets to go after.

Thanks!

Matt





> -----Original Message-----
> From: Jay Acuna <mysidia () gmail com>
> Sent: Monday, September 8, 2025 22:26
> To: North American Network Operators Group <nanog () lists nanog org>
> Cc: Saku Ytti <saku () ytti fi>; Dan Collins <dcollinsn () gmail com>;
> Vasilenko Eduard <vasilenko.eduard () huawei com>
> Subject: Re: MD5 is slow
>
> On Mon, Sep 8, 2025 at 3:00 AM Vasilenko Eduard via NANOG <
> nanog () lists nanog org> wrote:
>
> > 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  only
> the password is not known, but could be tested from the dictionary).
>
> They do not require high latency.  0.1ms per call is still just fine.
> And the concept of brute force a hashing algorithm should resist involves
> many orders of magnitude more possibilities than contained in a password.
>
> Put it this way:  MD5 has a block size of 512 bit.
> The MD5 algorithm has not failed in its security purpose for a hashing
> algorithm: If one is able to reverse an input by directly trying every
> possible input that contains a number of unpredictable bits 447 or less.
> Exactly the same way as it's not a MD5 problem if you have a 1-byte
> password, and someone tried all 255 possibilities.
>
> You really need a bare minimum of least a block of input; if not more to
> properly use
> MD5 and similar secure hashing algorithms. Predictable bits also don't
> help against guessing, so you should consider this as 512 bits of entropy
> on the input or more to safely use a hashing procedure calculated on
> 512-bit blocks.
> I also read MD5 input shorter than 512 must be padded congruent to 448
> modulo 512.
>
> SHA-2 is similar. You need more bits than a typical password would contain.
>
> Standard secure hashing algorithms are not designed to save you in case
> your input contains fewer random bits.
>
> You have the option of using a key-stretching algorithm instead of a
> straight hash. PBKDF2, as mentioned before.  Multiple rounds of hashing
> chained in a certain manner can cause delays for brute force guessing.
>
> A dictionary word contains about 4-bits worth of entropy.  If the 512 bits
> are not filled, the input is to be padded with bits in front of your
> password, which are predictable, so they don't count.  That is far from
> enough unpredictable bits to directly use MD5.
>
> From a randomized password; you get approximately 6 to 7 bits worth of
> entropy per character, so a good password length input for MD5 would be at
> about 85 random characters.
>
> --
> -JA
> _______________________________________________
> NANOG mailing list
>
> https://lists.nanog.org/archives/list/nanog () lists nanog org/message/4LFVVQ7VGFM76EPKKFRSEAAXHKBGCREV/
_______________________________________________
NANOG mailing list 
https://lists.nanog.org/archives/list/nanog () lists nanog org/message/DR7WAK3JYO2XKYYW2WTY6JC5HYP2D2KA/