IN THE world of electronic commerce, you either have to be very trusting or very foolish. When you buy a holiday or CD online, how do you know the website you send your credit card details to won’t abuse it? And when you use a card to withdraw cash, how do you know someone hasn’t put a wiretap on the ATM machine in order to learn customers’ PINs or clone their cards?
In many cases, you can reassure yourself that your transactions are protected by encryption, mathematical tricks that make your information indecipherable to anybody who isn’t supposed to see it. Encryption is to data what a good, strong padlock is to a cash box: it’s supposed to be your strongest point of defence. It lets you take your data out in public without having to trust the rest of the world to keep their hands off.
It may come as a shock, then, to discover that the people who endorse encryption standards – the kind of things your bank’s website boasts about – are feeling anything but secure. At the end of February, the European Union’s flagship cryptography committee, NESSIE (New European Schemes for Signatures, Integrity and Encryption), issued a long-awaited list of approved encryption methods, the ones it considers reliable enough for everyday use. It recommended two top-of-the-line ciphers, known as 128-bit block ciphers: the Advanced Encryption Standard (AES) and a Japanese cipher called Camellia. But buried in the NESSIE report was a less-than-ringing vote of confidence: “Many NESSIE partners have significant concerns that the simple algebraic structure of the AES, and to a somewhat lesser extent Camellia, may lead to future breakthroughs in the analysis of these block ciphers.” In other words, no one is sure just how long they will remain secure.
Advertisement
That’s particularly galling for the US government’s National Institute of Standards and Technology (NIST) because, late in 2000, it certified AES as the approved encryption method for dealings between the US government and private contractors. This endorsement seemed to give AES a huge advantage in the market for encryption software, which millions of people use every day for e-commerce and for sending data over company intranets. Indeed, in October last year, Microsoft registered its own networking software that offers AES-based encryption. With the US government and Microsoft behind it, what could go wrong? A lot, apparently.
The alarm bells started ringing in August last year, less than two years after NIST formally selected AES. “AES may have been broken…or maybe not…there’s no need to panic. Yet. But there might be soon. Maybe.” With these words, Bruce Schneier, the editor of a widely read security newsletter called Crypto-Gram, eloquently captured the sense of confusion in the crypto world. The trigger was an announcement by a 31-year-old cryptographer working for Schlumberger-Sema, which makes electronic bank cards. Nicolas Courtois had unveiled a new “attack” on AES. Something, he said, that would make it easier for eavesdroppers to decipher an AES-encoded message.
Courtois, working with Josef Pieprzyk of Macquarie University in Sydney, Australia, had come up with a whole new kind of attack, one that AES simply wasn’t set up to deal with. The attack quickly became the subject of a heated and often bad-tempered debate, and for good reason. Although AES might survive Courtois and Pieprzyk’s new attack strategy, this new and unexpected line of assault could equally prove fatal. “All over the world people are working on this attack,” says cryptographer Lars Knudsen of the Technical University of Denmark. “It’s an indication that there might be something there.” AES, designed to last a century, could be dead within a decade.
Perhaps we shouldn’t be surprised. Creating provably secure yet usable ciphers has always been a problem. AES was itself the product of an ongoing controversy. Back in the 1970s, NIST (then known as the National Bureau of Standards) had seen the need for a single encryption method that could be used by government contractors. Rather than ask the secretive National Security Agency to develop this cipher, NIST set a precedent by soliciting proposals from private industry. IBM answered the call and developed the Digital Encryption Standard (DES).
Unlike the “public-key” systems that revolutionised the industry later that decade, DES is an old-fashioned “symmetric-key” cipher. This means that both the sender and recipient of a message use the same key for encryption and decryption, just as they did back in the days of Julius Caesar. But, of course, cryptography has progressed a great deal since the 1st century BC. While primitive ciphers (like the ones still found in the puzzle sections of newspapers and magazines) encrypt a message letter by letter, DES encrypted a message in blocks of 64 “bits” – zeroes and ones. Following the principles laid down by crypto-pioneer Claude Shannon, DES worked by combining “confusion” with “diffusion”. Confusion is the substitution of deceptive bits for some of the message bits, as in a classical cipher; diffusion is the spreading out of the deception among all 64 bits, for example by scrambling their order.
From the beginning, serious cryptographers argued that the secret keys (that is, the instructions on how to carry out, and reverse, the confusion and diffusion in DES) were not long enough. They were only 56 bits long, which meant that there were only 256 (roughly 72 million billion) possible keys. So an adversary could decipher a message by brute force, simply trying every key until the message popped out. In the 1970s this was still far beyond any computer’s capability, but by the 1990s it was not. The death knell for DES may have sounded in 1998, when a non-profit organisation based in San Francisco called the Electronic Frontier Foundation built a demonstration machine it called the DES Cracker that could decipher any DES-encoded message in a matter of days.
Even before this, security-conscious users had begun to adopt “Triple DES” as a patch, encrypting a message three times with three different keys. Triple DES is still more than secure enough for one-time use, but its short block length of 64 bits created another problem. If you encipher more than 232 (about 4 billion) blocks of data with the same key or set of keys, you are likely to encounter the same block twice, and information about the data will start to leak out. The longer the block length, the less likely this is to happen. “It isn’t like you can read everything,” says Bill Burr, the manager of the Security Technology Group at NIST, “but you find little bits and pieces you can start to read. If you think of someone encrypting a large, 200-gigabyte disc drive under a single key, there’s a good chance you can find out something about the contents.”
So in 1997, NIST announced a competition to develop the Advanced Encryption Standard, a cipher that would work on longer blocks of 128 bits and have flexible key lengths of 128, 192, or 256 bits, providing varying degrees of security as required. (It is worth noting that adding just one bit to the key length doubles the security, adding another doubles it again, and so on.) The prestige of designing a universal cipher that would be used for decades was irresistible to cryptographers, even though to enter the contest they had to agree not to assert any patent rights. “The winner of the competition was NIST,” says Knudsen, who designed a cipher called Serpent, one of the five finalists. “They had the world’s best cryptographers working three or four years for free.”
In 2000, NIST announced its winner. Rijndael, an algorithm designed by Belgian cryptographers Vincent Rijmen and Joan Daemen, became the AES. Mathematical purists cheered, because Rijndael was a very elegant cipher and it ran faster than any of the other finalists. Security experts, however, were a bit surprised. Although all five finalists had shown themselves to be secure against all known methods of attack, Rijndael was widely perceived as the one with the smallest margin of safety.
And now those doubts have proved well founded. Courtois and Pieprzyk are not claiming to have broken AES, in the sense that the DES Cracker had broken DES. A message, or even a roomful of hard discs, encrypted with AES is still completely immune to decryption. But they are claiming to have found a chink in its armour.
The implicit promise of AES is that an adversary would have to search through 2128 keys to find the one you used to encrypt your message – a stupendous, mind-boggling task. If your adversary combined all the computing power in the world, it would still take them trillions of years to decipher your message. But if Courtois and Pieprzyk are right, the adversary would only need to search through around 2100 keys. Still a stupendously large number, still a task that would take longer than the age of the universe, but, nevertheless, a lower level of security than AES’s implicit warranty. AES no longer does what it was meant to do, and so it lacks the longevity that NIST required. Faster computers, or further developments of the Courtois-Pieprzyk attack, could render it obsolete. “Cryptography needs to prevent not only present, but also any future attacks, even if they are unlikely to happen,” Courtois says. “That is why the current version of AES will probably be discarded.” He believes this process will be progressive, though. “It still has enough security to last for at least 5 to 10 years.”
The experts at NIST are not making such definite pronouncements, but they are keeping an eye on the situation. “Yes, it [AES] was intended to last for decades,” says Burr. “I think it probably will. But this adds an element of uncertainty.” NIST has more to lose than Europe’s NESSIE committee, because its selection process picked a single winner so that all of the US government’s hardware could have one type of security chip. “If – I stress the if – you assume that AES is broken, then you might have an object lesson in not putting all your eggs in one basket,” Burr concedes.
So how has Courtois wreaked such havoc? AES was designed to be resistant to two kinds of attack. The first, called differential cryptanalysis, basically works by bombarding the cipher with a huge number of almost identical texts. The cipher then throws them back at you, encrypted, and the differences between the encrypted texts can give you information about the way the cipher works. The second kind of attack, called linear cryptanalysis, uses the idea that the “confusion” part of the cipher can be roughly mimicked by another mathematical procedure that’s not so confusing – a so-called linear function.
Both the AES cipher and the proposed attack on it by Courtois and Pieprzyk rely on the mathematics of “finite fields”, alternative sets of mathematical rules suited to the binary notation of computers. The simplest of all finite fields has just two numbers in it: 0 and 1. You can think of them as symbolising “even” and “odd” numbers. So the rules for arithmetic in this field are just what you’d expect: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 (because odd + odd = even). And similarly for multiplication. The AES cipher uses a somewhat more complicated field, with 256 numbers that can be written as strings of eight bits (such as 00110101).
The principal vulnerability of AES, according to Courtois and Pieprzyk, lies in its “substitution box” or “S-box”. In the Shannon paradigm of confusion and diffusion, this is the confusion part of a cipher. AES takes a 128-bit string of digital text (in other words, 128 ones and zeroes), chops it into eight-bit pieces, and converts each piece into the number it symbolises in the finite field being used. Think of the original piece of data as x and the encrypted data as y. Using the rules of arithmetic specific to that field, the S-box computes y as the inverse of x (y = 1/x). Put another way, xy = 1. Then y is mixed with the output for the other 8-bit pieces – the diffusion – and the whole process is repeated 10 times. The process might be compared to chopping and mixing a cabbage to make coleslaw, except that every now and then the S-box steps in and randomly changes half of the pieces of cabbage to carrots (or vice versa).
But although they were trying to make their code resistant to the most widely used and dangerous types of attack, Courtois believes Rijmen and Daemen have unwittingly created an S-box whose computations follow a pattern. It’s like trying so hard to be unpredictable that you end up being completely predictable. That is because xy = 1 leads to other algebraic relationships. Multiplying both sides by x, for example, gives x2y = x. This looks like the same thing – but it’s not. When you start plugging in zeroes and ones, it brings about extra relations between bits of x and bits of y that were not apparent in the original equation, and not anticipated by the inventors of AES. This is the “simple algebraic structure” that the NESSIE consortium viewed with such concern. These relations enable you to predict bits of x, the original message, from bits of y, the encrypted message. And the more relations there are, the closer you can get to cracking the code.
There are so many of these relations in the S-box used for AES, Courtois says, that it reduces the security of the code. It would not be easy to crack: Courtois estimates that you’d have to solve 8000 equations involving 1600 different combinations of x and y. Nevertheless, it’s faster than trying to guess the secret key by trial and error.
While no one is disputing the existence of these extra relations, critics claim that Courtois and Pieprzyk are underestimating the time needed to solve those 8000 equations. They say it would actually take much longer. Rijmen, along with many industry pros, is unruffled. “There never has been a reason to worry,” he says.
But others are not so sure. Cryptographer Bill Millan, based at Queensland University of Technology in Brisbane, Australia, says he is not surprised that AES is vulnerable. “I think there are many more ways [to attack AES] than have been discussed in the literature.” Only time – and further research – will tell who’s right. “It’s hard to know what we should do except watch,” says Burr of NIST.
Schneier takes a more philosophical view. Although no one predicted the debate over AES, we shouldn’t be surprised that someone has come up with an attack that has to be taken seriously, he says. That’s how cryptography works these days. “The community develops a series of algorithms for which there are no known attacks, and then new attack tools come out of the blue and strike a few of them down,” he wrote in Crypto-Gram. “We all scramble, and then the cycle repeats.” What is important to recognise, Schneier says, is that there is no longer any way to be sure how safe a new cipher is. He believes we have entered an era of cryptanalysis where no one can verify whether attacks are likely to be serious or not. They have become so complex and computationally intensive, we do not have enough processing power to analyse them.
And so NIST, Microsoft and anyone else using AES is stuck with knowing nothing for certain about their best security tool. Perhaps AES can be relied upon for the rest of the century, as intended. On the other hand, it could be broken before the end of the decade. If AES gets in more serious trouble, NIST says it might turn to backups such as Camellia or Serpent. But they, too, are vulnerable to Courtois and Pieprzyk’s attack. The other solution might be to hold a new competition and start the whole lengthy process over again.
But Courtois isn’t about to apologise for opening this cryptographic can of worms. Sometimes people see his work as hacking – ruining everything for everyone. To him, it’s heroic. To design a cipher and break it, you need sophisticated mathematics and high standards of proof. “Hacking is like looking to see if the neighbour left the key under the mat, or if the window can be opened with a kitchen knife,” he says. “Our job is high-end cracking: to go beyond the current knowledge. To outsmart the whole world.”