Wednesday, August 31, 2011

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.

No comments:

Post a Comment