Penetration Testing mailing list archives
RE: Insecure Hash Algorithms (MD5) and NTLMv2
From: "Miguel Dilaj" <Miguel.Dilaj () nccgroup com>
Date: Tue, 1 Nov 2005 09:57:35 -0000
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 -------------------------------------------------------------------------------
Current thread:
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Thierry Zoller (Nov 01)
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Daniel Miessler (Nov 01)
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Steve Friedl (Nov 03)
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Daniel Miessler (Nov 04)
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Steve Friedl (Nov 03)
- RE: Insecure Hash Algorithms (MD5) and NTLMv2 Ben Nagy (Nov 03)
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Thor (Hammer of God) (Nov 04)
- <Possible follow-ups>
- RE: Insecure Hash Algorithms (MD5) and NTLMv2 Miguel Dilaj (Nov 01)
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Jack Lloyd (Nov 03)
- Re: Insecure Hash Algorithms (MD5) and NTLMv2 Daniel Miessler (Nov 01)