--- Date: Sun, 15 Sep 2002 16:47:45 -0500 From: Bruce Schneier <schneierat_private> Subject: CRYPTO-GRAM, September 15, 2002 CRYPTO-GRAM September 15, 2002 by Bruce Schneier Founder and CTO Counterpane Internet Security, Inc. schneierat_private <http://www.counterpane.com> [...] AES News AES may have been broken. Serpent, too. Or maybe not. In either case, there's no need to panic. Yet. But there might be soon. Maybe. Some of the confusion stems from different definitions of "attack." To a cryptographer, an attack is anything that breaks the algorithm faster than brute force, even if it is completely impractical. To an engineer, an attack is something that is practical, or at least might be practical in a few years. An attack that breaks AES to a cryptographer might not to an engineer. The rest of the confusion stems from not being sure the attack actually works. Let's start from the beginning. A few months ago, Courtois and Pieprzyk posted a paper outlining a new attack against Rijndael (AES) and Serpent. The authors used words like "optimistic evaluation" and "might be able to break" to soften their claims, but the paper described a better-than-brute-force attack against Serpent, and possibly one against Rijndael as well. Basically, the attack works by trying to express the entire algorithm as multivariate quadratic polynomials, and then using an innovative technique to treat the terms of those polynomials as individual variables. This gives you a system of linear equations in a quadratically large number of variables, which you have to solve. There are a bunch of minimization techniques, and several other clever tricks you can use to make the solution easier. (This is a gross oversimplification of the paper; read it for more detail.) The attack depends much more critically on the complexity of the nonlinear components than on the number of rounds. Ciphers with small S-boxes and simple structures are particularly vulnerable. Serpent has small S-boxes and a simple structure. AES has larger S-boxes, but a very simple algebraic description. (Twofish has small S-boxes, too, but a more complex nonlinear structure. No one has implemented the attack against Twofish, but I'm not willing to stand up and declare the cipher immune.) These are amazing results. Previously, the best attacks worked by breaking simplified variants of AES using very impractical attack models (e.g., requiring immense amounts of chosen plaintext). This paper claimed to break the entire algorithm, and with only one or two known plaintexts. Moreover, the first cipher broken was Serpent: the cipher universally considered to be the safest, most conservative choice. There was some buzz about the paper in the academic community, but it quickly died down. I believe the problem was that the paper was dense and hard to understand. The attack technique, something called XSL, was brand new. (It's based on another technique, called XL, presented at Eurocrypt 2000.) And the results were so startling -- an attack against Serpent! -- that they were just discounted. Meanwhile, Fuller and Millan released a paper showing that AES's 8x8-bit S-box is really an 8x1-bit S-box. There's really only one piece of nonlinearity going on in the cipher; everything else is linear. Another paper came from Filiol. He claimed to have detected some biases in the Boolean functions of AES, which could possibly be used to break AES. But there are just too few details in the paper to make sense of this claim yet. At Crypto 2002, Murply and Robshaw published a surprising result, allowing all of AES to be expressed in a single field. They postulated a cipher called BES that treats each AES byte as an 8-byte vector. BES operates on blocks of 128 bytes; for a special subset of the plaintexts and keys, BES is isomorphic to AES. This representation has several nice properties that may make it easier to cryptanalyze. Most interestingly, the BES representation gives the XSL method a much more concise representation, and therefor sparser and simpler equations that are easier to solve. Moreover, there are intermediate versions of BES -- 2-byte vectors, 4-byte vectors, etc. -- decreasing in complexity as you head towards BES-8. These representations identified a bunch more quadratic equations that apply to AES and BES. When you throw them into the XSL mix, Courtois and Pieprzyk's attack now has a 2^100 complexity, as opposed to the wiffly waffly 2^200-or-so complexity claimed earlier. So, here's the current scorecard. Courtois and Pieprzyk claim a 2^100-ish attack against AES. They claim a 2^200-ish attack against Serpent. This is an enormously big deal. Assuming that it's real. We are in the era of completely theoretical cryptanalysis. Cipher key lengths have gotten so long that attacks simply can't be implemented; their complexity is just too great. But implementation is critical; some attacks have hidden problems when you try them out, and other attacks are more efficient than predicted. You can try the attack on simplified versions of the cipher -- fewer rounds, smaller block size -- but you can never be sure the attack scales as predicted. Differential cryptanalysis was developed this way; the attack was demonstrated on simpler variants of DES and then extrapolated to the full DES. (I don't believe that the attack has ever been implemented on the full DES.) Many of the attacks we use to break algorithms -- linear, boomerang, slide, mod n, etc. -- are more often mathematical arguments than computer demonstrations. I don't believe that we will learn in our lifetimes whether the 2^100 attack on AES really works or not. And we need a lot more analysis and testing of the general XSL technique, on weaker algorithms and simplified variants of real algorithms. So we're in a quandary. We might have an amazing new cryptanalytic technique, but we don't know if there's an error in the analysis, and there's no way to test the technique empirically. We have to wait until others go over the same work. And to be sure, we have to wait until someone improves the attack to a practical point before we know if the algorithm was broken to begin with. In any case, there's no cause for alarm yet. These attacks can be no more implemented in the field than they can be tested in a lab. No AES (or Serpent) traffic can be decrypted using these techniques. No communications are at risk. No products need to be recalled. There's so much security margin in these ciphers that the attacks are irrelevant. But there is call for worry. If the attack really works, it can only get better. My fear is that we could see optimizations of the XSL attack breaking AES with a 2^80-ish complexity, in which case things starts to get dicey about ten years from now. That's the problem with theoretical cryptanalysis: we learn whether or not an attack works at the same time we learn whether or not we're at risk. The work is fascinating. During the AES process, everyone agreed that Rijndael was the risky choice, Serpent was the conservative choice, and Twofish was in the middle. To have Serpent be the first to fall (albeit marginally), and to have Rijndael fall so far so quickly, is something no one predicted. But it's how cryptography works. 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. We all scramble, and then the cycle repeats. We're starting to see the new attack tools that work against some of the AES finalists. It's an open question as to how long the tools will remain theoretical. But many cryptographers who previously felt good about AES are having second thoughts. Summary of recent AES results: <http://www.cryptosystem.net/aes/> Preliminary version of the Courtois and Pieprzyk paper (final to be presented at Asiacrypt 2002): <http://eprint.iacr.org/2002/044/> Fuller and Millan Paper : <http://eprint.iacr.org/2002/111/> Filiol paper: <http://eprint.iacr.org/2002/099/> Murphy and Robshaw paper: <http://www.isg.rhul.ac.uk/~mrobshaw/aes-crypto.pdf> Rijndael analysis by the Twofish team from May 2000: <http://www.counterpane.com/rijndael.html> One effect of theoretical cryptanalysis is inconsistent standards for papers. Courtois and Pieprzyk submitted their paper to Crypto 2002, as did Murphy and Robshaw. For some reason, the latter was accepted and the former wasn't. In any case, the Courtois and Pieprzyk paper will appear at Asiacrypt later this year. [...] ------------------------------------------------------------------------- POLITECH -- Declan McCullagh's politics and technology mailing list You may redistribute this message freely if you include this notice. To subscribe to Politech: http://www.politechbot.com/info/subscribe.html This message is archived at http://www.politechbot.com/ Declan McCullagh's photographs are at http://www.mccullagh.org/ ------------------------------------------------------------------------- Like Politech? Make a donation here: http://www.politechbot.com/donate/ Recent CNET News.com articles: http://news.search.com/search?q=declan CNET Radio 9:40 am ET weekdays: http://cnet.com/broadband/0-7227152.html -------------------------------------------------------------------------
This archive was generated by hypermail 2b30 : Mon Sep 16 2002 - 00:38:34 PDT