Are You Suffering from Bad Entropy?

February 8th, 2012 - Posted by: Calum MaCleod

When I arrived at work this morning, I found an email telling me that Malaysia may be suffering a case of bad entropy—or to put it more precisely, bad key entropy. “What does this mean?” I asked myself.

So off I went to a few familiar “fonts of all knowledge,” Google and Wikipedia, to discover what entropy is all about. According to one source I came across, entropy is a measure of disorder or unpredictability. In other words, my wife can exhibit extremely entropic behavior at times. If she were a crypto algorithm, high concentrations of entropy would be very good, but she’s not. In general, I haven’t got a clue what she’s thinking when she behaves entropically.

Another source expressed the common belief that entropy is a good measure of how many guesses it will take to correctly guess a single value generated by a given source—for example, the number of guesses it takes to correctly guess a single thought generated by my wife, which I have yet to determine. But Drs. David Malone and Wayne Sullivan from the Department of Mathematics at University College Dublin are convinced that this belief is not well founded and that its implied definition of entropy “may have arisen via the asymptotic equipartition property.” Ah yes—it’s amazing what you’ll see at the bottom of a pint of the black stuff!

But what do these ramblings have to do with anything, you might ask? The answer to this question brings us back to the email about Malaysia’s current malady.

The last few days have seen yet another certificate authority compromise—this time, the compromise of DigiCert Sdn. Bhd, Malaysia’s well-known trusted third party. But Malaysia’s trouble doesn’t end there. It appears that malware is using a stolen certificate that once belonged to the Malaysian Agricultural Research and Development Institute, known affectionately to locals as “MARDI.” It appears that MARDI has been involved in spreading some “digital compost.”

DigiCert Sdn. Bhd issued several certificates with weak keys, which is where the expression “bad key entropy” comes into play. For the purposes of this discussion, let’s define bad key entropy as anything that can make encryption keys easy to acquire. In the case of DigiCert Sdn. Bhd and MARDI, either the compromised encryption keys were improperly protected, and were consequently stolen, or were weak (easily predictable) enough for hackers to break by brute force—or both. In either case, a series of events took place that allowed outsiders to gain access to the private keys. As a result, browser manufacturers had to issue yet another update to their browsers—this time to take DigiCert Sdn. Bhd from their browsers’ lists of trusted publishers.

So Why Should You Care?

While it may seem that current events in Malaysia have little to do with you and your organization, they have a lot to do with you. Bad key entropy can happen to any company in any number of ways, and it frequently does. When bad key entropy happens, trouble will eventually follow. The four scenarios in the following paragraphs present some of the most common ways bad key entropy can develop in organizations like yours.

Bad Key Entropy Scenario 1

DigiCert Sdn. Bhd made the news for issuing keys based on 512-bit encryption. These keys are uncommonly weak and are therefore easy targets for brute-force attacks. The U.S. National Institute of Standards and Technology (NIST) recommends key lengths of 2048 bits and higher. The organization has considered 512-bit key lengths “depreciated” or unacceptable for several years, which means DigiCert must have issued very old keys.

While it’s unlikely that your organization still has 512-bit keys in its encryption deployment, it could well have 1024-bit keys. We’ve found that keys of this length are common, even though NIST has recommended that companies phase them out by the end of 2010. Although 1024-bit keys aren’t as easy to break as 512-bit keys, they are breakable. Every organization should check its certificate inventory and replace its 1024-bit keys immediately.

Finding keys that were generated with the MD5 encryption algorithm is as common as finding 1024-bit keys. In fact, it’s common for us to encounter encryption deployments wherein up to 40 percent of the certificate population uses MD5. You should know that the purpose of hashing algorithms is to hide keys. But if the algorithms are predictable—as MD5 is—hackers can easily discover the poorly hidden keys and use them to generate cryptographic tokens that appear to be authentic when they are actually illegitimate. Every organization should check its certificate inventory and immediately replace all keys that were generated with MD5.

Bad Key Entropy Scenario 2

No matter how strong your keys are—and let’s assume that you have now eliminated every last key that falls short of 2048-bits and are no longer using MD5—you still have to deal with the challenge of protecting your keys: Preventing brute-force attacks won’t help if you leave your backdoor wide open.

Many organizations require passwords to protect keystores. But we’ve noticed that system administrators tend to either not use keystore passwords, or use the same weak password to protect keystores on multiple systems. Additionally, we find that administrators often don’t bother to change keystore passwords—ever. Need I tell you that you should always password protect keystores? And if you really want to keep the keys within them safe, you should change the passwords each time you renew or replace corresponding certificates and private keys.

Bad Key Entropy Scenario 3

In many organizations, administrators use the same private key across multiple systems. They can do this for genuinely technical reasons, or simply out of laziness. Either way, you should know that every time you transfer private keys from one location to another, you dramatically increase the risk of a key compromise. Ideally, you should have a dual-control process to carry out such tasks.

Bad Key Entropy Scenario 4

The lack of clear policies, combined with the ability to enforce policies, frequently means that people are able to perform unauthorized actions—so audit logging is important for your certificates and, especially, private keys. Every organization should implement a solution that logs all certificate- and key-management operations, particularly when access to private keys is involved.

Each of these scenarios is equally significant for preventing bad key entropy. To verify this statement, simply ask yourself this question: Will it matter for me and my organization whether a breach results from some spotty teenager exploiting my 1024-bit keys, hashed with MD5, or from an administrator who happened to leave the backdoor open?

Of course it won’t matter. Either way, you will discover that bad key entropy is as costly and embarrassing for you as it was for Malaysia.