RE: Insecure Hash Algorithms (MD5) and NTLMv2

["Miguel Dilaj" <Miguel.Dilaj () nccgroup com>]

Hi Daniel,

I fully agree with you.
The whole buzz about MD5 being "weak" has been grossly misunderstood and
exagerated by the media.
Generating arbitrary malware that produces the same hash (MD5 or any
other) it's still very difficult, and has nothing to do with cracking
password hashes. I know some byte chains for MD5 have already being
produced, don't throw the links at me ;-)

The time required either to generate a table or to parse it will be
slightly longer if the hash has more bits, more space will be required
for the tables, but that's pretty much it. We can't even start to
compare that with the "real bruteforcing" time.

Another interesting point is that the media has presented this as
"MD5=bad, otherhash=good".

In theory ALL hashing algorithms are clearly flawed by collisions. Every
single one of them, and the reason is of mathematical nature.

Let's suppose an encryption (not hashing) algorithm, that produces
output of a size related to the input (for example, 32 bits of plain
text produce 32 bits or more of cypher text, so the relation is 1:1[+]).

        PT1 => CT1
        PT2 => CT2
        PT3 => CT3
        ... etc ...
        PTn => CTn

We have an infinite universe of plain texts, but we also have an
infinite universe of cypher texts.

Now let's see a hashing algorithm. Allow me to take MD5 as the first
example.
MD5, by definition, produces hashes from
0x00000000000000000000000000000000 to 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
That means a huuuuge number of different hashes, but it has a problem:
IT'S NOT INFINITE.
And, to paraphrase late Dr. Carl Sagan in his book Cosmos:
"0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF is not even close to the idea of
infinite" ;-)

That produces the following scenario:

        PT1 => H1
        PT2 => H2
        PT3 => H3
        ... etc ...
        PTn => H2
        ... etc ...
        PTn' => H1
        ... etc ...
        PTn'' => H2
        ... etc ...

So plain texts will produce the same hash, and not only some of them.
There will be AN INFINITE number of plain texts producing any of the
hashes. That's a consequence of the universe of plain texts being
infinite and the universe of hashes being finite.

Exactly the same criteria will apply to ANY hashing algorithm, the only
difference is that the universe of hashes can be bigger (if the hash has
more bits), but it's still not even close to infinite. The result will
be the same: infinite collisions, and an infinite number of plain texts
producing the same hash.

Of course, the difficulty in finding mathematical shortcuts allowing to
find two colliding plaintexts (or more!) is very very high... And a task
for the mathematicians out there, not me, I've to write some reports and
drink my coffee ;-)

IMHO Microsoft has jumped on the horse created by the media, and use
that as propaganda "this is bad, so we are dropping it for the good of
our beloved customers". Happily for them, 99.99% of their customers
don't understand the issue, so Microsoft ends looking like a bunch of
nice guys.

As a side comment on you mentioning salting with user@domain, I would
like to mention something related to the cached credentials, in which
the userID is the salt.
Salting is good because it increases the number of possible hashes.
But if you know the salt you can completely disregard its effect by
including it in the equation from the very beginning.

[Even if you don't know it for sure, in certain scenarios knowing that
the salt is a simple one still helps. I vaguely remember a discussion
ages ago (Netscreen passwords??) in which the salt was 2 lowercase
characters, so anything from aa to zz could have been included, for a
total of 676 combinations]. <- don't quote me on that ;-)

Back to cached credentials:
1) how many people out there rename the Administrator account?
2) WHAT is used to salt the hash for the Administrator? ;-)

In that scenario, a modified rtgen can be produced, to create rainbow
tables pre-salted with "Administrator". The tables will be totally
useless for other user accounts, or if the Administrator account has
been renamed, but my guess is that it can still be useful in more than
50% of the cases (and I'm being conservative...)

Cheers,

Miguel



-----Original Message-----
From: Daniel Miessler [mailto:daniel () dmiessler com] 
Sent: 30 October 2005 10:08
To: Craig Wright
Cc: pen-test () securityfocus com
Subject: Insecure Hash Algorithms (MD5) and NTLMv2


On Sep 22, 2005, at 11:52 PM, Craig Wright wrote:

> First the quote from the MSFT program manager
>
> "Microsoft is banning certain cryptographic functions from new 
> computer code, citing increasingly sophisticated attacks that make 
> them less secure, according to a company executive. The Redmond, 
> Wash., software company instituted a new policy for all developers 
> that bans functions using the DES, MD4, MD5 and, in some cases, the 
> SHA1 encryption algorithm, which is becoming "creaky at the edges," 
> said Michael Howard, senior security program manager at the company, 
> Howard said."

Just because MD5 has become "relatively" weak in recent months doesn't
mean that it's trivial to create/find collisions using it.  
Or, to put it another way, since NTLMv2 does in fact use a much larger
set of inputs, the fact that MD5 has become weaker simply isn't an
issue.

Here's why: the practical issue concerning collisions in weak hashing
algorithms has to do with modified/maliciously-generated content hashing
to the same thing as legitimate content does. This threat has nothing to
do with the difficulty of brute forcing hashes in the vein of the
rainbowcrack project, since the entire premise for that project is
trying all inputs.

Another way of looking at this is almost like a salting process; if
user@domain is part of every input then you can't just test $input, you
have to test $input for every $user@domain combination. As such, the
solution *IS* significantly stronger despite its use of MD5.

Or, at least this is how I currently understand things. Feel free to
correct me if I'm wrong.

--
Daniel R. Miessler
M: daniel () dmiessler com
W: http://dmiessler.com
G: 0x316BC712



***********************************************************************************************************

DISCLAIMER:                                                                                                
This e-mail contains proprietary information, some or all of which may be legally privileged.              
It is for the intended recipient only. If an addressing or transmission error has misdirected this e-mail, please 
notify the author by replying to this e-mail. If you are not the intended recipient you may not use,
disclose, distribute, copy, print or rely on this e-mail.   
                                               
***********************************************************************************************************


------------------------------------------------------------------------------
Audit your website security with Acunetix Web Vulnerability Scanner:

Hackers are concentrating their efforts on attacking applications on your
website. Up to 75% of cyber attacks are launched on shopping carts, forms,
login pages, dynamic content etc. Firewalls, SSL and locked-down servers are
futile against web application hacking. Check your website for vulnerabilities
to SQL injection, Cross site scripting and other web attacks before hackers do!
Download Trial at:

http://www.securityfocus.com/sponsor/pen-test_050831
-------------------------------------------------------------------------------