Superconductor

Has PKI met its Waterloo?

Public key infrastructure (PKI) has found few uses outside national governments due the high costs caused by its high complexity. Has PKI met its Waterloo in these factors?

As Napoleon's defeated Grand Armée withdrew from the battlefield at Waterloo, its retreat was covered by units from the Old Guard, part of a small, elite unit under Napoleon's direct control. The soldiers in this unit were the best and bravest veterans from his previous battles and the most feared soldiers in Europe. In addition to being Napoleon's personal bodyguards, these units were his weapon of last resort, and they were rarely committed in battle.

Eventually the Old Guard's position became untenable, and the English General Charles Colville offered them a chance to surrender and avoid being inevitably destroyed by the vastly superior numbers of Wellington's victorious army. The French General Pierre Cambronne is said to have replied to Colville's request, "La Garde meurt, elle ne se rend pas!" - "The Guard dies, it does not surrender!" Cambronne later denied having said this, but that didn't stop the words from being inscribed on the statue of him that was eventually erected in his home town of Nantes, and they have become one of the legends that are commonly associated with the battle of Waterloo.

Despite its questionable authenticity, Cambronne's defiant reply may be good inspiration for a rallying cry that may be appropriate for supporters of public-key infrastructure (PKI) technology: "PKI dies, it does not surrender!" Except for the single use in implementing SSL, the use of encryption to identify servers and encrypt connections to them, PKI has proven to be extremely difficult to use and expensive to support, but its dedicated advocates insist on continuing its use to the bitter end. They even continue to support its use in the face of many newer technologies that are just as secure, more user-friendly and have a much lower total cost of ownership. PKI's proponents seem to never surrender.

PKI technology was a very innovative idea when it was first introduced. The digital certificates that PKI creates and manages provide the basis for authentication, digital signatures and encryption, all of which are very useful to have. Unfortunately, PKI also turned out to have many practical problems that its inventors didn't anticipate. These practical difficulties made it too difficult for the average user to use, which then resulted in very high support costs. So although it had an extremely promising start, it turned out to be unsuitable for most uses, the most notable exception being the use by government organizations.

Governments have an entirely different set of priorities than commercial enterprises: while businesses need to be profitable in order to survive in the long run, government organizations do not. Staying profitable is of utmost concern to businesses; spending their budgets and keeping people employed are among the highest priorities of most governments, and costs are relatively less important. So while most businesses found PKI to be unsuitable for widespread use, governments didn't find its high costs objectionable. This has led to almost all of the use of PKI being confined to governments and government contractors. And despite the high costs of doing it, governments have continued to move ahead with expensive PKI projects, with the American government alone having spent over $1 billion on the technology to date.

But while this has happened, many recent innovations have made it possible to provide the same benefits that PKI once promised, but at greatly reduced costs. Encrypted e-mail, for example, has recently become fairly popular due to heightened regulatory compliance concerns, so it has become much more widely deployed than it was just a few years ago. But if you look at the secure e-mail solutions that are commonly used today, you'll find that they're usually not based on PKI. Even if a solution does support PKI, that mode of operation is rarely used by customers. But while the use of newer technologies for encrypted e-mail has boomed, governments have continued to use PKI to provide this capability, perhaps attracted by its superior ability to help them spend their budgets and keep additional people employed.

Cost that is caused by unnecessary complexity may turn out to be the battle that PKI can't win when it's pitted against these newer technologies, so it may be somewhat appropriate to refer to it as "PKI's Waterloo." But because its supporters seem to have been inspired by Cambronne's legendary reply to Colville, it may be quite a while until we finally see them admit defeat.

On the other hand, Waterloo was the first time that Napoleon's Guards retreated without being ordered to do so. Perhaps supporters of PKI will suffer a similar change of heart, realize that their battle can't be won, and give governments a chance to realize the same cost savings that the commercial world has already experienced. We can only hope that this happens soon. Although it's often attributed to him, American senator Everett McKinley Dirkson never actually said, "A billion here, a billion there, and pretty soon you're talking real money," but it gives an idea of the savings that this might allow.

Google encrypts your Gmail - or does it ?

Lots of buzz around Google making your Gmail safer by making it easier to turn on encryption. Two things come to mind - firstly it's interesting how just by changing a simple default it's possible to increase overall security. Eliminating user clicks is critical in providing useable security - bravo Gmail team.

The second point is that simply securing the pipe between your computer and Gmail is not really enough to protect your most sensitive communication. Emails by definition travel all over the place, so if you really want to make sure you are protecting your email then you need to encrypt the email itself. No other way to do it. But of course the problem with email encryption solutions over the past 15 years has been that they are all too difficult to use - a few clicks too many for the ordinary user.

One easy to use approach that you may want to try is the Voltage Security Network, especially if you routinely send work documents home via gmail (or any other public email system) - take the free trial.

A rounding error?

A few days ago, I gave a talk, part of which discussed the data that supports the claim that encryption has historically been both hard and expensive, although newer technologies are definitely changing this. Some of the data that I used to support the claim that encryption has historically been expensive came from a report from the US Government Accountability Office (GAO) on the cost of PKI in the US federal government. One particular data point that I mentioned was how much that the US Department of Agriculture (USDA) had managed to spend per digital certificate.

According to the GAO report, the USDA has spent $6,887,473 for a total of only 147 certificates, for an average of about $46,853.56 per certificate. I rounded this down to only $46,000 in my talk.

Today, I realized that the amount that the rounding error in my estimate was actually fairly large. By rounding down $46,853.56 to only $46,000, I had created a rounding error of $853.56 per certificate, an amount that’s actually much greater than the total cost of certificates, even for government organizations.

The US federal agency that seems to have had the best experience with PKI is the Department of the Treasury. They’ve spent $3,200,454 for 122,450 certificates, for an average of only $26.14 per certificate. When I saw this, I contacted the manager of their PKI program, hoping to get some insight into how they managed to keep their costs so low, but he never replied to my inquiries. Their total costs are much less than the rounding error that I made when talking about the USDA’s costs, but it looks like I’ll never know how they managed to do this.

Theory of Cryptography Conference

The sixth Theory of Cryptography Conference will be held in San Francisco, California, USA , organized by Stanford University and sponsored by the International Association for Cryptologic Research (IACR). Papers presenting original research on foundational and theoretical aspects of cryptography are sought.

The Theory of Cryptography Conference deals with the paradigms, approaches, and techniques used to conceptualize natural cryptographic problems and provide algorithmic solutions to them. More specifically, the scope of the conference includes, but is not limited to the:

• Study of known paradigms, approaches, and techniques, directed towards their better understanding and utilization,
• Discovery of new paradigms, approaches and techniques that overcome limitations of the existing ones,
• Formulation and treatment of new cryptographic problems,
• Study of notions of security and relations among them,
• Modeling and analysis of cryptographic algorithms, and
• Study of the complexity assumptions used in cryptography.

The Theory of Cryptography Conference is dedicated to the dissemination of results within its scope. The conference aims to provide a meeting place for researchers and to be instrumental in shaping the identity of the theoretical cryptography community.

Program Committee:

Ivan Damgaard (University of Aarhus)
Stefan Dziembowski (University of Rome)
Marc Fischlin (Darmstadt University)
Matthew Franklin (UC Davis)
Jens Groth (University College London)
Thomas Holenstein (Microsoft Research)
Nicholas J. Hopper (University of Minnesota)
Yuval Ishai (Technion and UCLA)
Charanjit Jutla (IBM Watson)
Daniele Micciancio (UC San Diego)
Kobbi Nissim (Ben-Gurion)
Adriana M. Palacio (Bowdoin)
Rafael Pass (Cornell)
Manoj M Prabhakaran (Urbana-Champaign)
Omer Reingold (Weizmann, chair)
Yael Tauman Kalai (Microsoft Research)
Brent Waters (SRI International)
John Watrous (University of Waterloo)

Program Chair: Omer Reingold
General chair: Dan Boneh

TCC Steering Committee Members: Mihir Bellare, Ivan Damgard,

Oded Goldreich (chair), Shafi Goldwasser, Johan Hastad, Russell Impagliazzo, Ueli Maurer, Silvio Micali, Moni Naor, and Tatsuaki Okamoto.

Proud sponsors include IBM, Microsoft and Voltage Security.

How big is 128 bits?

It should be fairly well known by now that the venerable DES encryption algorithm is obsolete. NIST made this official when they withdrew the DES standard on May 19, 2005. It’s probably less well known that NIST requires that all US government users move to something at least as strong as Triple-DES by 2010, but that’s what’s recommended to keep encryption secure against adversaries that have access to the bigger and faster computers that get released every year.

Triple-DES provides 112 bits of strength, which NIST says should be good through 2030. After that, US government users will need to use encryption that provides at least 128 bits of strength, like AES does. In the latest NIST guidance, it looks like 128-bits keys will be good essentially forever. Does this make sense, or should we just expect some additional guidance from NIST that increases the required key sizes even more?

From one point of view, it certainly seems like 128 bits of key is good for quite a while, perhaps even essentially forever. If you’re going to attack a symmetric algorithm, you’re probably going to have to do too many computations to do easily on a single computer. A network of many computers is a better idea. An even better idea is to do the computations in hardware instead of software. But even that’s not enough to recover a 128-bit key.

In July 1998, the DES Cracker, a special-purpose computer built by the EFF for only $250,000, managed to recover a 56-bit DES key in roughly 56 hours, and showed that an attacker with a fairly small amount of resources could defeat DES without too much trouble. The DES Cracker could test roughly 92 billion keys per second on 1,536 special-purpose chips. Given a plaintext-ciphertext pair, the overall machine could test all possible DES keys in a bit over 9 days, and you’d expect to find the key that decrypted the ciphertext in about half that time, or about 4 and a half days.

Let’s assume that we can make a special-purpose computer that can test keys one billion times faster than the DES Cracker, or roughly 92 quadrillion keys per second. Maybe Moore’s law and faster clock speeds can help us do this. Adding additional chips to our computer will also help.

Even with this huge increase in speed, such a hypothetical machine will still take roughly 100 billion years to recover a single 128-bit key. This doesn’t look too promising. So unless someone finds an incredibly severe weakness in AES, it looks like that assuming that a 128-bit key is good for essentially forever may be fairly reasonable.

Learn to play poker

Information security practitioners can learn a lot from the game of poker: it's a good example of the difference between dealing with uncertainty and dealing with risk. Information security is often described as dealing with the risks associated with information security systems, but a closer look shows that it really deals more with uncertainty, and one of the best ways to learn about dealing with uncertainty is to play poker.

Risk management deals with the average losses associated with unpredictable events. In particular, for a given event, we find the risk associated with it by multiplying the probability that the event happened by the loss that we will experience from the event. So an event that happens with a 1 percent chance that will cause $1 million of loss when it happens represents a risk of 1 percent of $1 million, or $10,000.

In the case of information security, however, we rarely know either the probabilities of security-related events or the loss that will accompany such events. If you are running a web server, for example, it's almost certain that it contains many exploitable vulnerabilities, some of which have not yet been discovered by security researchers. In the face of this almost-certain exposure, what are your chances of being exploited by a hacker due to one of these yet-undiscovered vulnerabilities? And if you are exploited, how do you quantify the damage that you suffer? If you send unencrypted e-mail, what are the chances of it being read by an adversary? If your e-mail is indeed read, how much damage will it actually cause?

Because it's difficult to accurately answer such questions for most information security systems, the unpredictable losses from using them is probably more accurately described as uncertainty than as risk, and most risk management methodologies don't work very well with them. This is similar to the situation where a one approach works well to develop strategies for a game like craps but an entirely different approach is needed to develop strategies for games like poker.

The chances of winning or losing in any situation are well known for the game of craps. This is because the outcome of the game is based entirely on the roll of the dice, and these have well-known probabilities. This means that the best strategy is easy to find and to follow. Further, these strategies are essentially unchanged from those that players used hundreds of years ago - the game has remained relatively unchanged from the time that it was played by twelfth-century soldiers in the Third Crusade or mentioned in The Canterbury Tales. You can't really win at craps - you'll lose money in the long run if you choose to play it. On the other hand, because the probabilities are well known, risk management methodologies work quite well in finding ways to minimize your losses.

In poker, on the other hand, while the probabilities of being dealt strong hands are well known, the unpredictable nature of opponents makes understanding these probabilities only a small part of a winning strategy. The best strategy for poker also changes over time as opponents also adopt new strategies to counter existing strategies. Because of this, a book on poker written in the 1960s may describe very different strategies than one written in the 1990s, yet both books can describe what might have worked well at the time.

In poker, the actions of opponents can also make a big difference in a winning strategy from moment to moment. If you are holding a moderately-strong poker hand and your opponent makes a large bet, for example, you may decide that your hand is too weak to win, and that further betting is futile. The fact that your opponent may just be bluffing makes such decisions even more difficult.

In this light, the connection between poker and information security is not hard to make. In both cases, participants need to make decisions in the face of uncertain or even inaccurate information. In the case of poker, the uncertainty is caused by the other players, and because it's in the interest of the other players to adopt a strategy that keeps a high level of uncertainty in the game, it's unlikely that this element of the game will ever go away.

Information security, on the other hand, deals with reducing the chances of undesirable uncertain outcomes, but both the ever-changing nature of both the information security market and the strategies of attackers make it likely that it will always be impossible to develop a winning strategy that stays useful for long. So even the best security policy and the soundest security architecture will become obsolete fairly soon.

On the other hand, winning poker players have shown that it's indeed possible to develop winning strategies in such a dynamic environment, so it shouldn't be surprising that it's also possible to successfully address the challenges of information security. Perhaps information security practitioners should use the game of poker as a training ground for decisions that they face on the job. After all, although you'll always lose at craps, winning at poker is definitely possible.

An alternative to PKI

By now, everyone has probably heard that encryption can be difficult and expensive. It may deserve this reputation. “Why Johnny Can’t Encrypt” and “Why Johnny Still Can’t Encrypt” showed that users have problems with using some public-key systems. Usability has gotten much better, and if these studies were done today with most successful e-mail encryption products, the results would probably be much more encouraging. On the other hand, there are still complexities that seem to make some public-key technologies unnecessarily complicated. You could see at this year’s RSA show.

The RSA Data Security Conference is one of the biggest gatherings of information security professionals in the industry and it's where new products are often announced for the first time. This year's show took place April 7-11 in San Francisco, and featured some interesting products and services. Some of these, however, should have made attendees raise an eyebrow or scratch their head as they pondered exactly why such new things were even needed. In particular, more than one vendor was demonstrating a path validation service for digital certificates. That's right - they expect to be able to charge for this service and make money. If you're one of those few remaining people who believe that using certificates is feasible for more than SSL, this might be enough to make you change your mind.

Digital certificates provide the basis for useful things like authentication, digital signatures and encryption, but the public-key infrastructure (PKI) that's needed to create and manage them has a nasty reputation for being too difficult for users to actually use and for being extremely expensive to support. The fact that people feel that there's a viable business in handling certificate processing seems to indicate that the technology is also getting far too complicated to be useful.

Because the thorough verification of an identity that's done when certificates are created can be expensive, it's typically not done very often, so that a certificate is typically valid for quite a while. A one-year or more lifetime for a certificate is typical. But because they're valid for so long, you don't know that a certificate is still valid when you go to use it. The corresponding private key could have been compromised. Or the user's identity could have changed. Because the identities in certificates are based on X.500 names that include organizational structure, changing departments in an organization can also make the identity in a certificate invalid. Or the user could just no longer be part of the organization that issued the certificate.

Validating a certificate can be done by a call to an on-line certificate status protocol (OCSP) server, for example. You make an on-line call to an OCSP server and it tells you whether or not the certificate that you want to use is valid or not. More advanced protocols like the server-based certificate validation protocol (SCVP) can even answer more complicated questions, perhaps even determining if a certificate was valid when it was used instead of just determining if it's currently valid. This is a tricky problem, and solving it requires being able to reconstruct the state of a certificate at times in the past.

Another difficult problem is caused by the complicated architectures that users of PKI are trying to implement. In particular, the bridged architectures in which every root certificate authority (CA) cross-certifies with a central bridge CA, makes it very difficult to trace a path up to a trusted root certificate. You can think of trust relationships between CAs as defining a directed graph, and deciding whether or not to trust a particular certificate requires determining whether or not a path in this directed graph exists between a certain set of points on the graph. This is a problem that can be hard to solve, so using certificates that come from more complex architectures can be tricky. So tricky that it's apparently now better to rely on someone else to solve it that to do it yourself. That's what the products at this year's RSA show seem to tell us.

So with cutting-edge PKI technology, users need to make at least a few calls to servers. They might need to retrieve a certificate from an LDAP directory. Once they have a certificate, they need to check it’s validity by making another OCSP or SCVP call. And now it looks like a third call may be needed because it’s getting complicated to find a path from a user’s certificate to a trusted root CA. With all of these calls to servers going on, it makes you wonder if it wouldn’t just be simpler to make a single call to a server that asks for a symmetric key. That sounds like an alternative that’s better than what the state-of-the-art in PKI offers.

Switching Mobile Devices

Last June, along with many BlackBerry addicts I rushed out and bought the brand new BlackBerry Curve. This was a beautiful smartphone - memory slot, video and music playback, push email and a nice camera with flash and GPS - plus it did email too. About 28 days later I went out and bought the new Apple iPhone and with one swipe of my credit card turned my back on the BlackBerry - handing it casually to a friend who needed a new phone.

Well, today I got a call from my friend, informing me that having switched from a corporate BES plan to a personal BIS plan, his phone was now receiving personal emails from my (supposedly defunct) BIS account which I had set up to forward to my BlackBerry - and had forgotten to switch off when I switched devices.

Just goes to show that you can never be too careful with your personal data - much as I would like to blame my cellular carrier, it really was my fault for not being aware of how BIS was spraying my personal emails into the ether. So if you are moving devices or carriers or even ISPs be careful and make sure you are not leaving behind a trail of personal emails for innocent passersby to stumble upon.

- Wasim

Aberdeen releases PCI Data Security Standard Compliance Survey Results

Aberdeen released a new survey report that details how companies are attempting to become PCI compliant. You can download a copy of it here.

This report provides insights into the year-over-year progress that Best-in-Class organizations have been made in achieving, and sustaining, compliance with the Payment Card Industry (PCI) Data Security Standard (DSS). Public disclosures of security breaches involving consumer cardholder data continue to be a threat to consumer confidence in payment cards, and a growing source of financial risk for the payment card industry. The payment card industry has made steady progress in establishing a common set of security standards, evangelizing best practices, and encouraging adoption. Aberdeen's research shows that Best-in-Class organizations have indeed achieved superior protection of cardholder data through compliance with PCI DSS, and even Laggards have made encouraging gains in the last year.

The most interesting thing about the report is the comparisons of companies who have thought through a pro-active compliance program, established goals, evaluated technology solutions and started to implement them; and those that are still researching their options (laggards).

Five Compelling Facts from the Research:

1. On average Best-in-Class companies are achieving 22% better performance at addressing the 12 high-level PCI DSS security requirements, compared to other respondents.
2. Best-in-Class companies took 29% less time to achieve PCI compliance than all other respondents.
3. Best-in-Class companies spent 9% less to achieve PCI compliance than all other respondents.
4. Best-in-Class companies are spending 56% less to sustain PCI compliance than all other respondents.
5. Between 40-50% of Best-in-Class companies have reduced the number of failed audits and the number of data security incidents over the last 12 months.