Click here to Skip to main content
Click here to Skip to main content

Good Bye MD5

, 20 Sep 2005
Rate this:
Please Sign up or sign in to vote.
The cracking of MD5 is making it useless?

Introduction

A complementary article, showing how to exploit this is here.

There is a Crisis in Hashland. Latest results on Cryptology are opening the debate about the security of cryptographic one way hash functions.

I suggested in another article that:

Don't store the user password on your database. No matter how many security measures you take, there is not a perfect security system. Use a hash method for the passwords, like SHA1, or MD5.

SHA1 and MD5 aren't secure anymore, because of projects like passcracking, we can't trust these hash functions for one way encryption.

In fact, experts suggest that:

"Given the number of practical attacks on MD5, it may be time to move
to a Federal Information Processing Standards (FIPS) approved hash
algorithm, such as SHA-256, or SHA-512. Note that vulnerabilities have
recently been found in SHA-1, however, and NIST is already planning to
phase it out by 2010." (Quoted from cn.bbs.comp.security.)

Update - here are some reactions to these issues:

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. (Source)

To understand the consequences, this article first explains what one way hash functions are, shows one of their common uses on password storage, and shows the nature of the current attacks and their consequences, and also suggests other alternative hash functions stronger at the present time.

One Way Hash Functions

The following definitions are taken from Bruce Schneier's Book: Applied Cryptography Second Edition:

A one-way hash function, H(M), operates on an arbitrary-length pre-image message, M. It returns a fixed-length hash value, h.

h = H(M), where h is of length m

Many functions can take an arbitrary-length input and return an output of fixed length, but one-way hash functions have additional characteristics that make them one-way [1065]:

Given M, it is easy to compute h.
Given h, it is hard to compute M such that H(M)= h.
Given M, it is hard to find another message, M’, such that H(M) = H(M’).
....

In some applications, one-wayness is insufficient; we need an additional requirement called collision-resistance.

It is hard to find two random messages, M and M’, such that H(M) = H(M’).

Hashing Function Used for Password Storing

The definition mentioned before, lead to the development of secure password storage.

The use of one way hashing function is the following algorithm:

  1. For password storage, request input plain_password from user , then apply a oneway hash function H on plain_password and store it. In code, stored_password = H(plain_password)
  2. For password checking, request probe_password from user, apply H on it, and compare with stored_ password, i.e. check ::= H(probe_password) == stored_password.

This schema is good as long as H is a good and strong hashing function.

Today, MD5 is under heavy attack, the reason is that it is used on the GNU implementation of the POSIX function Crypt. In fact, on this Web site, you can find a lot of collisions for this function.

Other papers about the MD5 attacks can be found here.

Other Security Side Effects

In recent works, three investigators: Lenstra, Wang and Weger, showed that it is feasible to build colliding electronic X.509 certificates, using the MD5 collision techniques developed by Wang. You can read their paper here.

This work violates the basic trust principles underlying PKI (Public Key Infrastructure).

Moreover, Chinese investigators have shown an attack to other Hash function: SHA-1. (Read about it here).

Some others side effects are mentioned in the paper "MD5 To Be Considered Harmful Someday".

For example, digital signatures like RSA, DSA/ElGamel, and Elliptical Curve never hash the data directly, but rather a hash of the data, often the choice is MD5. Also consider DRM (Digital Right Management) implementations using MD5. All these protection signatures and checksums are at risk because of these findings.

If you read the paper, you can learn that it is possible to add a payload to the data, or alter the data without being noticed.

Other example is shown in the paper, Practical Attacks on Digital Signatures Using MD5 Message Digest.

A Proof of Concept

In this article, I wrote about how to implement the attack in Microsoft.NET.

Finding Collisions for MD5

The typical way of collision search is to use a brute-force algorithm: given a hash value h, for a plain message m, written in an alphabet A, then h = MD5(m), so in brute force collision search, we try every possible combination in alphabet A we find a m' message such as MD5(m') = h. m' can be equal to or not equal to m.

The Rainbow Crack uses precalculated tables for intermediate steps on the process, this can accelerate the cracking process. For example, a password of up to 14 characters, of this charset: "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()-_+=" can be cracked in a few minutes.

Better One Way Hash Functions

Some people suggest to use more complicated applications of MD5, for example, use stored_password = crypt(plain_password + salt), where the key is a fixed one or the user id, or some other fixed value. This schema is not stronger, and can be shown to have several flaws to this approach.

Other alternatives are:

  • Use a key based hash function
  • Combine algorithms
  • Use other functions

The first one relays on a key, that can be stolen. Combining algorithms is better, but probably only results in more CPU usage than real protection.

Alternatives Functions

To use other hash functions can be a solution, but what criteria is used to choose a good one?

The answer is simple, use hash functions with a bigger domain of results. For example, MD5 generates a 128 bits value, so the space of possible resulting values is 2128 in size. By simple logic, if your hash function has an output domain of a size bigger than that, then it's a good alternative.

All the followings functions have stronger implementations than MD5.

  • WHIRPOOL, generates a 512 bits output
  • RIPEMD, uses 160, 128 or 320 bits output
  • SHA-2, generates 256, 512 bits output

SHA-2 is available on crypto API, and Microsoft.NET, so I suggest you to use it. The SHA-2 is a group of functions, in Microsoft.NET you have the followings classes:

  • System.Security.Cryptography.SHA256Managed
  • System.Security.Cryptography.SHA384Managed
  • System.Security.Cryptography.SHA512Managed

Change Log

  • September 7th, 2005: Added some quotes from Chinese security groups, and more links on papers about the MD5 collisions. Also a section about other effects on DRM and checksums is included. Some grammar corrections.
  • September 8th, 2005: Some title changes, to be more precise about cryptology terminologies. Some typos corrected.
  • September 9th, 2005: Added list of SHA-2 algorithms available on Microsoft.NET 1.1.
  • September 14th, 2005: Added link to proof of concept article

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

ediazc
Web Developer
Chile Chile
Eduardo Diaz
personal blog

Comments and Discussions

 
GeneralBeating a dead horse... more like decimating it with a nuke... PinmemberPenGunAssassin12-Nov-08 5:04 
GeneralC also the new 'Pumpkin Hash' (MD6) Pinmemberalphons10-Sep-08 23:26 
GeneralMd5 is cracked! PinmemberWeiHua zhang7-Sep-08 3:11 
GeneralEven 23bit Binary-Salted MD5 is puppychow ! [modified] Pinmembergarychapman24-May-07 6:48 
Salting does NOT improve MD5.
Salting does NOT protect against brute forcing other than to add 32bits of searchspace.
Salting ONLY disrupts users of Rainbow tables by making storage size and access times prohibitive.
 
But rainbow tables are NOT ALWAYS faster than brute-forcing! Thats a myth!
 

Anyone that thinks that a 32bit binary-salted MD5 cannot be cracked in short order has probably made a simple mistake. They've evaluated the algorithm based upon processor cycles required per processing round and accounting for register width. IE, they are calculating the crack in 'Von Neumann' time.
 

MD5 is simple - just ADDs RORs and XORs - No MULs or DIVs
 
How fast can you fixed-ROR, saaay, 128 bits. Think about it...
 
Well, the answer is... no time at all. Its free! Sure, a Von Neumann processor has to chug through it piece by piece according to register width, and loses cycles in the fetching, register loading, the ROR itself and then the writeback...
But how about in terms of LEDs and Switches. Well, you wire the LEDs up to the switches and all 128 bits are RORed according to your fixed wiring. How does that apply to your CPU? It doesn't - But it does apply to FPGAs.
 
A single MD5 pipeline in a 2mm high programmable logic chip can handle 64 MD5 hashes AT THE SAME TIME (Thats one in each of the 64 bounded stages), spends no gate time on fetch and writeback, spends no gate time on the RORs or ABCD shuffles. The only thing it spends time on is the ADDs and XORs... and well, hardly even the XORs.
 

The ADDs
 
With carry lookahead the adds are way faster than a PC, and the latter stages can be shared as the adds are redundant and can be compressed into a single ADD. Not only this but the ADD is a constant ADD too. So, the final stages can be shared across multiple MD5 chains using a multiplex.
 
The XORs
 
Well, if you're familiar with your gates you can figure out that nBit XOR takes only one gate delay, for any value of n that fits on the chip. How fast is that? Well, faster than your CPU can begin to prepare a XOR... An FPGA can perform a few thousand bits of XOR simultaneously... before a PC can even fill the first register in preparation.
 

So, the result? A chip as large as 2cm square and a coupla mil high makes a high-end PC look like a chump. And if you farm the job across a cluster of these chips then you can sit the equivalent of a 100,000xPC supercluster on one corner of your desk... and it will power from a single 13A outlet. Silently too!
 
The great thing is, these will crack UNsalteds faster than you can look them up in a rainbow table... yet they are bruteforcing! No storage at all! And salteds? Well... feed in 200 salted hashes and you can have the result the same week - for binary salted hashes... and definately under an hour for non-binary salts of < one block width.
 

And where do you get these FPGA's? Well, safe disposal points are great for free low-mid range FPGAs. When companies change their STBs this is a perfect time to pull a hundred FPGAs and, if you ain't into etching your own boards, you can either have them made up at a budget PCB outlet using a batch process to group snapoff boards for lower costs - or... if your needs ain't so great you can dead-bug them while glued upside down to a sheet of MDF or Ply.
 
If you use the JTAG boundary register cells as your interface for setting up the job then you're looking at a 4-wire interface regardless of the boundary size or even whether the array is using mixed devices.
 
Now thats a hackers take on MD5 bruteforcing. And if you think that MD5 with a 32bit salted hash is safe then you're probably a C/ASM coder looking at the world through Von Neumanns glasses - go learn Verilog/VHDL and grab yourself a copy of either Altera Quartus Webpack (free) or XilinX Foundation ISE (Free version) and start simulating designs without the hardware. Honestly, you'll scare yourself straight. Some things really are far faster than ASM ; )
 
CPU cycles has NEVER been an effective way to ascertain cryptographic duration.
 

BTW, forget governments and corporations. A limited pre-production of ASIC based crackers can fit 32 MD5 pipelines on a single chip even with a cheaper coarse process. It costs less to do a run of 60,000 of these than it takes to pay a fully popped Crays electricity bill for a year... and they would definately make my FPGA cluster look like a snail. There is apparently one stacked on 16x16 frames in a tower in a London dockside which can crack bins of 32bit bin-salted MD5 faster in a forever cycling bruteforce... Cracking salted hashes with that is kinda like throwing logs in a woodchipper. I wouldn't be overly surprised if theres a couple of equally effective SHA1 crackers floating around.
 
Think a million pounds is a lot of money? Well... for me it is, but for corporates it is lunch money. But me? Well, I can still give salted MD5 a good run for its money.
 

So, use *AT LEAST* SHA1 if thats the only alternative offered! Seriously! Forget MD5+SALT completely... its the only way to stay safe from kids with too much time on their hands. The MD5 algorithm runs way to fast for its own good and thats something that was recognised very early on - long before the emergence of rainbow tables clouded the issue. The latest SHA1 issues are nothing in comparison.
 
-G
GeneralMD5 - Alive and Kicking PinsussJames Pullicino16-Sep-05 4:59 
GeneralRe: MD5 - Alive and Kicking Pinmemberediazc16-Sep-05 5:07 
GeneralRe: MD5 - Alive and Kicking PinmemberPuddin Tame24-Jul-11 20:06 
Generali need two files with different content and same md5 Pinmembernnnnnnn13-Sep-05 1:57 
GeneralRe: i need two files with different content and same md5 Pinmemberediazc15-Sep-05 4:19 
GeneralSHA2 in .NET Framework PinmemberDimitar Kolev8-Sep-05 1:39 
GeneralRe: SHA2 in .NET Framework Pinmemberediazc8-Sep-05 3:50 
GeneralThe issue with MD5 Pinmemberediazc6-Sep-05 17:12 
GeneralMD5 is ok Pinmemberjorgeleo696-Sep-05 8:08 
GeneralRe: MD5 is ok Pinmemberediazc6-Sep-05 17:32 
GeneralRe: MD5 is ok Pinmemberjorgeleo697-Sep-05 4:09 
GeneralRe: MD5 is ok Pinmemberediazc7-Sep-05 5:25 
GeneralRe: finding a collision will take a while Pinmemberazonenberg28-May-09 14:52 
GeneralRe: MD5 is ok PinmemberJoeDevil11-May-06 7:23 
GeneralRe: MD5 is ok Pinmembergarychapman24-May-07 10:30 
QuestionRSA implementation PinmemberT1TAN29-Aug-05 21:45 
AnswerRe: RSA implementation Pinmemberediazc30-Aug-05 9:35 
GeneralRe: RSA implementation PinmemberT1TAN30-Aug-05 21:28 
GeneralRe: RSA implementation PinmemberBoris505z11-Sep-05 22:48 
GeneralSHA-256... PinmemberAlexander M.23-Aug-05 14:54 
GeneralRe: SHA-256... Pinmembertsurutsuru1-Sep-05 8:13 
GeneralPlain MD5 wasn't considered safe for quite some time! Pinmembermav.northwind23-Aug-05 8:17 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! Pinmemberediazc23-Aug-05 9:04 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! Pinmemberwkempf23-Aug-05 11:20 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! Pinmemberediazc23-Aug-05 11:32 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! Pinmembersimonpersson30-Aug-05 12:50 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! Pinmemberediazc30-Aug-05 13:13 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! PinmemberJaime Olivares6-Sep-05 13:50 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! Pinmembergarychapman24-May-07 11:28 
GeneralRe: Plain MD5 wasn't considered safe for quite some time! Pinmembergarychapman24-May-07 10:48 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140721.1 | Last Updated 20 Sep 2005
Article Copyright 2005 by ediazc
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid