AES is Broken!

That is the headline. What does it mean? Should you care?

What does it mean to say that a cryptographic algorithm is broken? Does it mean that the cost of recovering the clear-text without benefit of the key has suddenly fallen to zero? Well, that would qualify, but no, crypto does not fail that way. Does it mean that the cost has fallen to be equal to that of encrypting with the key. Clearly that would qualify, but no, it does not mean that either.

Well, how about the cost has fallen to be equal to the value of the data? How about the time required to recover the clear-text has fallen to less than the life of the data? Well, if either of those had happened, even I might agree that the algorithm was broken. However neither of those has happened either.

For a "standard" algorithm, one might claim an algorithm was broken if the cost of attack was lower than that claimed by the standard.

For example, for the Data Encryption Standard, the DES, the claim was that the cheapest attack was an exhaustive attack against the key, on average, half the time required to try all possible keys. By that standard, the DES is still not broken, low these thirty-five years later. It is true that using a bot farm, one can do a brute-force attack in days. However, for many applications, the life and value of the message are such that no one would spend even that much.

For RSA, the claim is that the cheapest attack is a function of the cost to find the factors of the product of two large primes. While finding the product of two primes is trivial, finding those two numbers knowing only the product is a problem that has challenged mathematicians for a long time.

The time required to try all the DES keys falls as the power of computers goes up but we always know what it is. Similarly, the time required to find the factors of the product of two large primes goes down as computers become more powerful. It might even get cheaper as mathematicians get smarter, but it is unlikely to drop suddenly.

AES is not a standard in the same sense as the DES or RSA. No claim is made for its strength. Rather it is a standard because an authority, NIST, says that it is. It's strength is what it is. We know that the most expensive attack is a brute force attack, but not only has no one ever asserted that there is not a cheaper attack, it has been demonstrated, at least mathematically that there are.. Said another way, by definition, one cannot ever say that it is broken. The best one can say, is "I can find a key this fast."

While some claim that ""Broken" in cryptography is the result of any attack that is faster than brute force"" that simply justifies the claim of the headline. It is not a definition that is meaningful in any sense that a laymen, or even a security professional can understand or use.

By one estimate, the time to brute force a 256 bit key is 5 x (10 )^51 years. What the authors of the paper claim is that they can do it in a mere (10)^51 years. While that may be an interesting improvement, certainly worthy of a paper, even a headline, it does not justify the use of the word "broken" in any practical sense, whatever the authors and headline writers might claim. These authors have simply established the new "standard" cost of attack for the AES.

This is a mathematical assertion that defies any other demonstration. Such an attack, begun at the big bang, would not have completed yet. We call that "strong enough" for security work.

I like cryptographers. Most are very nice people. However, like many such guilds, including security professionals, they have their own special jargon. I appreciate the fact that they do all of these heady calculations for me. However, their security advice is on a par with their medical and legal advice.

Creating a cipher that you yourself cannot break, is relatively easy. All the work is in learning enough about it to be able to predict how much work it would take a body of experts to break it. We call that effort "standardization."

Does all of this mean that our cryptography is "safe," that even nation states cannot read our encrypted data? Not. It has always been my assumption that nation states in general, and the US and Russia, in particular, can read any traffic that they wish.

I am reminded of three colleagues: Phil Zimmerman, who wrote PGP and called it "pretty good;" Adi Shamir, one of the authors of RSA, who wrote, "People do not break crypto, they bypass it;" and Brian Snow, who spent a career at NSA, and who said, "At NSA we spend as much resource on systems as on codes and ciphers."

Algorithms are the strong part of our systems, orders of magnitude stronger than we need them to be. People are the weak point and implementations are in the middle. While it might take the life of the universe to try all possible keys, one might brute force the eight character lock-word used to hide it in a day. Failing that, attackers might bug your systems, suborn your associates, or break your fingers, one after another..

Life would be wonderful it our security was determined by the height of our walls rather than by the guards at our gates, by the strongest link in our chain rather than the weakest. On the other hand, then we might not need security professionals or pay them the big bucks.

Tearing off the PCI/DSS Band-aid

More than a quarter of a century ago, while I was still at IBM, I had discussions with staff at Sears, then the nation’s flagship retailer, about their forthcoming credit card. I tried to convince them to take the opportunity to force the industry to replace mag-stripe cards with smart cards. They were Sears, they had the clout, they could make it happen. They didn't and the rest is history.

Now, the nation's new flagship retailers, Wal-Mart, Target, CVS, and McDonalds are making it happen. Sears and K-Mart will come along.

Partly in response to these forward leaning merchants, Visa has announced that it will expand its Technology Innovation Program (TIP) program to the US. They will begin transitioning to EMV standard cards and infrastructure.

Some of you are aware that I have been very critical of the payment card industry for continuing to use the broken mag-stripe and PIN system. By doing so, they have put the necessary public trust and confidence in the retail payment system at risk. I am torn between "what took you so long" and "better late than never."

The EMV (EuroCard, MasterCard, and Visa) technology that Visa plans to use has been in use in the rest of the world for years. It uses a contact-less smart card, and optionally, a signature or PIN. It is already deployed in the US in some markets and the leading retailers already mentioned.

Here is an American Express EMV card that I have had for a couple of years. For reasons of backwards compatibility, it also has a mag-stripe. That is good because I can use it in EMV mode in only a limited number of places. Those places include McDonalds, CVS, Target, and Wal-Mart. it is bad because the vulnerabilities of mag-stripe and PIN will persist for years.

Many of the users of the EMV/POS readers deployed by these flagship merchants are foreign travelers to the US. These retailers have bitten the bullet but they cannot get all of the return on their investment until Americans carry EMV cards.

Therefore, these retailers have been a source of public pressure on the payment card industry to deploy this technology. Wal-Mart has been castigating the payment card issuers for more than a year now for "blocking" the use of this technology. Google Wal-Mart EMV and you can see for yourself.

Of course, "blocking" is stronger rhetoric than I am prepared to use. There is history here and business reasons why the issuers have not used EMV in the US. For example, the reason that Sears did not deploy smart cards was that the barrier to entry was too high; it was far cheaper to exploit the existing infrastructure than to replicate it.

While I understand those reasons, and to some degree am sympathetic, I have argued for some time that we cannot continue to rely on a broken technology for the security of our retail payment system. In the presence of cheaper counterfeiting technology, we have strengthened our currency, and even checks, to the point where cards are now the weak link in our system.

Notice that the merchants in this list are all nation wide chains that operate their own systems for authorizing payments. Part of the resistance in the US is rooted in the fact that most of our small and medium-sized merchants use third-party card service providers to accept card payments. These third-party providers enable them to accept any issuer;s card without having to have a separate agreement with and connection to that provider.

While it is an industry standard, EMV is also proprietary. The issuers share the exact workings, under contract and non-disclosure agreements, only within the industry. The important thing for you and I to know is that the card "signs" the transaction, without disclosing its own identity, the "credit card number," to the POS device. EMV resists skimmers and rogue or compromised POS devices. It resists replay attacks and card cloning attacks.

As with mag-stripe, in some, but not all, transactions, EMV will use PINs and signatures to resist the fraudulent use of lost or stolen cards. Because, the primary protection against the use of lost or stolen cards is disabling it after it is reported lost or stolen, PINs and signatures will not be required for all small value transactions.

For example, when I buy a Big Mac, I simply touch my card to the POS device and check the display and receipt to satisfy myself that I was charged the correct amount. No signature or PIN. If I use the same card to purchase an HDTV, I expect to enter a PIN or sign a transaction slip.

One interesting feature of EMV is that a card can be limited in the number of PIN-less transactions that it can do. An internal counter keeps track of the number of PIN-less transactions. The count is reset to zero for every PIN transaction. If the count reaches the threshold, the next transaction must involve, will prompt for, the PIN.

Because the POS device cannot capture the EMV card number, it is safe to enter a PIN into it. The PIN is only useful with the card or card number. I have long argued against "debit" card transactions where both the card number and the PIN appear in the clear at the point of sale. These are the source for many counterfeit cards.

While it is now relatively cheap to clone a mag-stripe card, knowing only the public number, this is not sufficient to clone an EMV card. Putting aside the fact that it is more expensive to write chips than stripes, cloning the EMV card requires knowledge of its secret token. It is secret for a reason, a security reason.

Another reason the issuers have resisted EMV in the US is that it does not solve the fraudulent "card not present" problem, those on-line transactions where the rogue has the card number but not the card. Most solutions to this problem involve a display and power, expensive, though not impossible, to put on a card.

Oh, I almost forgot about the PCI DSS, the Band-Aid that the issuers have been relying upon to hold their broken system together. Visa has announced that after October 1, 2012, merchants who have 75% or more of their transactions originating on EMV equipped terminals, will be exempt from compliance with DSS for any year for which that is so. This is a big incentive to those third-party card service providers, who have been one of the problems, for whom DSS compliance is so expensive. Their participation and cooperation in EMV is essential.

Some have suggested that merchants will resist replacing their POS devices. Probably true but "resist" only means that they will take their time. McDonalds did not replace their terminals, only added the EMV reader to the top. Check it out, but unless you know that you are looking for a red semicircle at the top of the device, you might miss it. The expense was not so much in this part as in installing it.

While we think of them as capital equipment, POS devices are actually consumables with a life measured in months to years. One can buy the latest feature-rich model, with built in WiFi or cellular communication, for hundreds of dollars. Most merchants buy their POS device from the card service provider who will be motivated to see them upgrade.

I wish I could tell you that everyone is going to love this technology as much as I do but I cannot. In fact, you can expect to hear all kinds of slurs about its security. After all, anything built by man can be broken by man.

For example, two weeks ago, at Black Hat, an NVP (We do not mention the names of NVPs; it feeds their narcissism.) was quoted as saying, "We think an EMV skimmer poses a serious threat, due to ease of installation, and is very difficult to detect." (Sic) First, a skimmer would be a tool, not a threat. Second, it might be easy to build and conceal, but the issue is getting the card to cough up its secret token. There is no command to ask it to do that. A cryptographer will tell you that one could simply ask it to authenticate a lot of transactions, a few million might do it, and then solve for the secret. A security person will tell you that "that will take a long time." it will take so long that it is not practical, much less efficient.

When you read these "expert remarks," remember two things. First, this is a mature technology, used and tested around the world. It is new only to the US market. Second, however vulnerable it may be, it is orders of magnitude stronger than the broken technology which it replaces.

Getting from our current system to EMV will not be without problems. Experience in Europe suggests that many problems will be related to the transition, in general, and backward compatibility to mag-stripe, in particular. Anticipating and mitigating these problems will not be easy but that is why we are called professionals and are paid the big bucks.

Mission Impossible

During my last years at IBM, Wjm Van Eck, A Dutch engineering student, published his paper about reading computer screens using TV receiving equipment. The press loved it. There were TV shows on the BBC demonstrating reading screens at a show and reading a document on a word processor screen from the Scotland Yard parking lot.

Van Eck's experiment was based in part on the following:

• All electronic equipment leaks
  
• CRTs are very noisy and leak a lot
  
• The screens of the day were character only
• The signal that they leaked mimicked that of broadcast TV

On his student budget, Van Eck simply cobbled together antennas, amplifiers, and receivers and displayed the signals on a standard TV screen.

I decided to see if I could replicate Van Eck’s results. I purchased from him a replica of his experimental rig. I gave it to two engineers, one senior and one junior, in the Raleigh lab, next to the plant that manufactured 3270 terminals. They assured me that it would be a piece of cake to reproduce the experiment.

It proved to be somewhat more difficult than they anticipated. On one trip to the lab, they did manage to show me a screen that lit up like their target. At a distance of two meters, it was clear that the image on the destination screen was related to the one on the target, but the content was less than readable. As often happens with engineers, these two lost interest in the effort after they were satisfied that, given enough time and resources, they could replicate the results but long before they had actually done so.

In the more general case, in estimating the cost of attack, engineers often discount the value of their own special knowledge and skills. They think, “Everyone knows (or can do) that.” They also tend to think that if an attack is feasible, it will be used. They tend to discount the difference between feasible and practical, effective and efficient.

These are the kind of esoteric attacks from which the drama in Mission Impossible is crafted. In fact, rather than fiction, one can expect an attack to be used only if it is efficient. The set of cases in the world in which such an attack is both suitable for the intended application and environment and cheaper than all alternatives is vanishingly small.

The leakage of information via electromagnetic signals is a vulnerability without a threat, a non-problem. Not all vulnerabilities are problems, not all problems are the same size.In the generation since van Eck published his paper and the press raised the alarm, such attacks have not ranked with our other security problems, not on our radar. The vulnerability is lower now than then and the cost of attack higher.

Today, while the attack equipment may be more efficient, the cost of such an attack is still higher. Screens are now bit-mapped graphics, not character. They are low-power, quiet, LCD displays, not noisy CRTs. Their emanations do not mimic broadcast TV signals. While they still leak, all electronic equipment does, they are much quieter than those of a generation ago.

One lesson that you should take away is that unless your applications are very sensitive, your adversary a nation state, and the rest of your security so good that this is your weak link, spend your scarce security resources elsewhere. Remember that "Mission Impossible" style attacks are undertaken only against those targets that are very sensitive and that have very good security.

Another lesson is that one should not take security advice from vulnerability pimps or the popular press. Rather, one should rely upon one's colleagues, professionals who are paid the big bucks.