The PCI Council seems to suggest in today’s Assessor Update that extensive use of MD5 is a reason not to prohibit its use:

…the PCI DSS and PA-DSS do not explicitly prohibit the use of MD5, acknowledging the prevalence of MD5 as a cryptographic technology in the marketplace. Additionally, it may be possible to mitigate some of the risks associated with MD5 through the implementation of additional cryptographic controls or security measures. For example, the susceptibility of MD5 hashes to rainbow table lookups can potentially be mitigated through the proper use of strong, unique salts.

They then, of course, say it is up to the QSA or PA-QSA to assess the risk with their client.

They could have said they same thing about SSLv2.

Section 4.1 of the PCI DSS, until the end of 2008, was open to interpretation for SSL. However, the Assessor Update Nov08 clarified that use of SSLv2 for protection of sensitive information is prohibited.

…it is imperative that an ASV identify the use of SSL 2.0 to transmit cardholder data as a failure

The difference between the two probably comes down to two factors:

1. available options
2. ease of upgrade

SSLv2 was required only by browsers before 1997. Options for SSLv2 therefore have not only been around for a decade, but SSLv3 or later has been the default for applications since at least 2005. Despite possible workarounds, the advocated path was an upgrade.

Upgrading from SSLv2 is a trivial setting on servers. One reason often given by organizations to avoid change is the cost of development but there is none for SSL because a change was required from the start. Clients can automatically negotiate the upgrade. However, there still may be support calls due to error messages or warnings. This has been offset by servers configured to provide instructions or self-help to reduce support requests.

In comparison to SSL, MD5 has many available options (even though less obvious than SSL), so it passes the first criteria. It probably is said to be too difficult/costly to change because it was built into applications without any upgrade path for the hash function. Thus, the Council must really base their decision upon this second issue.

This makes for an interesting dilemma for an Assessor. The PCI Council is stepping away from the risk assessment themselves because they say they are “acknowledging the prevalence” of MD5 rather than any security or safety of the hash function.

I doubt most Assessors would use prevalence alone as a measure, whether or not it is “possible to mitigate some of the risks”. Some of the risks? An Assessor would probably say a more appropriate measure of risk, when asked to approve an increasingly vulnerable control like MD5, is the rise and prevalence of threats.

In 2007 Google was given a simple UI that matched md5 strings to prove a point that collisions were more common than we might have wanted to believe. Attacks up to this time were mostly theoretical.

Cheap and large storage continued to rapidly expand and hold massive rainbow tables for unsalted MD5. Two terabytes for just $100, for example, makes it hard to believe that rainbow tables could be outrun (e.g. expand the range of symbols for a hash) since table sizes simply increase at almost no cost.

In 2008 the theoretical attacks on MD5 became more real. A researcher claimed free MD5 attack software could run at 1.4 billion cycles per second. A race for the fastest MD5 crack engine heated up, using compute speed with simple code to crack hashes using a long salt. Last year saw a number of free attack tools that target salted MD5 and take advantage of ATI and nVidia multi-GPUs.

NVidia 8800gt, % applies to MD5

2 hashes: v0.23 = 302.9M/s, v0.24 = 311.3M/s
500.000 hashes: v0.23 = 295.6M/s, v0.24 = 302.5M/s

NVidia gtx465, % applies to SHA-1

2 hashes: v0.23 = 376.9M/s, v0.24 = 430.3M/s
500.000 hashes: v0.23 = 366.8M/s, v0.24 = 418.3M/s

The author of bcrypt adds some color to the evolution of threats against MD5

It’s important to note that salts are useless for preventing dictionary attacks or brute force attacks. You can use huge salts or many salts or hand-harvested, shade-grown, organic Himalayan pink salt. It doesn’t affect how fast an attacker can try a candidate password, given the hash and the salt from your database.

Salt or no, if you’re using a general-purpose hash function designed for speed you’re well and truly effed.

Thus, while the PCI Council advises Assessors to take a risk-based approach with clients, there in fact seem to be no countermeasures or compensating controls to make MD5 suitable for cardholder data protection. The best path in terms of “implementation of additional cryptographic controls” to meet the intent of PCI compliance is a move to a stronger hash function or to an encryption algorithm (e.g. do not list MD5 as a control that can protect cardholder data).

That is probably why Bruce Schneier put it so succinctly two years ago (December 31, 2008):

I’m not losing a whole lot of sleep because of these attacks. But — come on, people — no one should be using MD5 anymore.

US federal agencies suggested MD5 was not even worth using in 2004.

There are known MD5 collisions and weaknesses, and MD5 is not recognized by FIPS 140-2, Security Requirements for Cryptographic Modules. The NSRL data provides an MD5 to SHA-1 mapping to facilitate the migration away from MD5.

Then they migrated away from SHA-1 last year, because of threats.

[D]ue to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010.

Organizations that have not made their hash function easily modified/upgraded will only be in an even more difficult pickle when the Council finds the courage to finally ban MD5, or a specific breach is linked to the hash function. The latest guidance from the PCI Council, however, moves more risk into the hands of the Assessor at the same time it makes it much harder for Assessors to emphasize a prepared fallback position (e.g. SHA-256) for those who claim to be unable to move from MD5.

Prevalence in the marketplace could as easily have given the Council reason to push for change, just like with SSLv2. Instead they seem to call it a reason for pause.

Updated to add: Confusion may come from whether MD5 is allowable within other security processes. A TLS tunnel, for example, can protect MD5 hashes. This is like saying a TLS tunnel can protect ASCII-encoded data, however. Sensitive data (hashed or encoded, etc.) that requires a strong tunnel for its protection is therefore weak on its own; it would be imperative then to identify the use of MD5 to protect cardholder data as a failure.