Tuesday, October 9, 2012

So you want to use an alternative cipher...

Not this cipher.
Once in a while I run into discussions that hinge on the following dubious proposition: that AES is bad and we need to replace it. These discussions always make me leery, since they begin with facts not in evidence, and rarely inspire any confidence that the solution is going to be any better than the 'problem'.

In fact, this whole point of view is so rarified that I've debated whether to even write this post, since my opinion is that AES is the last place your system is going to break down -- and you should be focusing your attention on fixing all the other broken things first.

Moreover, the simple advice on AES mirrors the ancient wisdom about IBM: nobody ever got fired for choosing it. Not only is AES is the NIST standard (certified in FIPS 140 and NSA's Suite B), but there are hundreds of solid implementations to choose from. If that's not enough for you, many processors now support AES operations natively, meaning that your application can now offload most of the work to hardware without the help of an expensive co-processor.

So why not just stick with AES? People who have these discussions generally give a variety of reasons, some of which are more valid than others. First, there's what I call the 'slight paranoia' viewpoint, which holds that AES has been around for a long time and could (soon/someday) fail. In just the last few years we've seen a few impractical attacks on the construction, which could be beginning of a trend. Or maybe not.

The second (less paranoid) objection is that AES is somewhat troublesome to implement in software. To make it run fast you have to expand the key and pre-compute a series of tables -- all of which increases key setup time and potentially makes you vulnerable to cache timing attacks. Good implementations take this into account, but even the best ones aren't perfect. And in a few cases your performance constraints are so tight that AES just isn't fast enough.

Now I'm not saying that any of these (except possibly for the last reason) are good reasons to ditch AES. In fact, ditching AES would be the opposite of my recommendation. But let's say that you've already made the decision to explore more recent, modern alternatives. What are they? Should you trust them? And most importantly: what will they buy you?

Salsa20

Based on an informal (and totally unscientific poll), the consensus among advanced AES-switchers is that Salsa20 has a lot going for it. This is mostly due to Salsa20's performance characteristics, but also because people are growing increasingly confident in its security.

Now, just for the record, Salsa20 is a stream cipher, while AES is a block cipher. This distinction is important: stream ciphers produce a string of pseudo-random output bits which are XORed with the message to be encrypted. Block ciphers can be configured to do the same thing (e.g., by running them in CTR or OFB mode), but they can also process plaintext blocks in other ways.

One important difference -- and a reason implementers have historically preferred block ciphers -- is that many block cipher modes allow you to randomly access just a portion of an encrypted message, without wasting time decrypting the whole thing. A second advantage is that block ciphers can be used to construct both encryption and message authentication (MACs), which makes them a wonderful building block for constructing authenticated encryption modes.

Salsa20 takes care of the first issue by providing a means to randomly access any block of the generated keystream. Each invocation of the Salsa20 keystream generator takes a key, a nonce (serving as an IV), and a block position in the stream. It then outputs the 512-bit block corresponding to that position. This makes it easy to, for example, seek to the last block of a multi-gigabyte file.

It's also possible to use Salsa20 in an authenticated encryption mode -- but it's not trivial. And to do this the cipher must be composed with a polynomial-based MAC like Dan Bernstein's poly1305. I won't lie and say that this usage is standardized and well-defined -- certainly not in the way that, say, EAX or GCM modes are with AES.

On the positive side, Salsa20 is fast in software. The key setup time is negligible and it has one of the lowest cycles-per-byte counts of any reputable ciphers. Current figures show Salsa20/12 to be 2-3x as fast as a heavily optimized AES-CTR, and maybe even faster for the implementation that you would actually use (of course, hardware implementations of AES could make up for a lot of this advantage).

The basic limitation a cipher like Salsa20 is the same as with any non-standard cipher -- no matter how good the design, you're using an alternative. Alternatives don't get the same attention that standards do. To its credit, Salsa20 has received a decent amount of academic cryptanalysis, most of it positive, but still nothing compared to AES.

Threefish

Threefish is another recent contribution to the 'alternative ciphers' canon, and hails from Schneier, Ferguson, Lucks, Whiting, Bellare, Kohno, Callas, and Walker. (With a list of authors this long, how could it not be excellent?)

Threefish's distinction is that it's one of a relatively small number of ciphers that recently passed through  (most of) a NIST competition. The dubious aspect is that the competition wasn't a competition for designing a cipher. Rather, Threefish was submitted as a building block for the SHA3 candidate Skein, which made it to the final round of the competition but was ultimately passed over in favor of Keccak.

Threefish is a wide-block cipher that can be configured to operate on 256, 512 or 1024-bit blocks. Right off the bat this seems useful for applications like disk encryption, where ciphers are typically used to encrypt large blocks of material (sometimes in 'wide block cipher modes' like CMC or EME). But it seems like a nice choice for security and performance reasons.

While Threefish has seen some cryptanalysis, this is still relatively limited (a few major results). None of these results are 'successful', which is noteworthy and confidence-inspiring. But even with this work, it's hard to say where the cipher stands in relation to AES.

The AES could-have-beens: Twofish, Serpent, etc.

AES seems like it's always been AES, so it's easy to forget that just a few years ago it was called Rijndael and there were four other finalists that could just as easily have taken the title. Those finalists all received a lot of cryptanalytic attention, and none of them went away when AES was selected.

The two ciphers I occasionally run into are Bruce Schneier's Twofish and Anderson/Biham/Knudsen's Serpent. Both have decent performance in software, and both have stood up relatively well to cryptanalysis. On the flipside, neither of the two ciphers has received very much in the way of analysis since the AES competition ended (Twofish's most recent significant result was in 2000).

Any of these ciphers could be a worthy alternative to AES if you were desperate, but I wouldn't go out of my way to use one.

In conclusion

I realize none of the above actually tells you which AES alternative to use, and that's mostly because I don't want to legitimize the question. Unless your adversary is the NSA or you have some serious performance constraints that AES can't satisfy, my recommendation is to stick with AES -- it's the one standard cipher that nobody gets fired for using.

But if you are in the latter category (meaning, you have performance constraints) I'm pretty impressed by Salsa20/12's performance in software, provided you have a good strategy for providing authentication. Even better, while Salsa20 is not standardized by NIST, standardization efforts are ongoing in the eCRYPT eStream project. The result could be increasing adoption of this cipher.

If your concern is with the security of AES, I have less advice to give you. The beautiful thing about AES is that it's so widely studied and used that we'll almost certainly have plenty of notice should the cipher really start to fail. That is, provided the people attacking it are doing so in the public, academic literature. (If your enemy is the NSA I'm just not sure what to tell you. Just run.)

That still leaves a class of folks who worry about encrypting things for the long-haul. For these folks the best I can propose is to securely combine AES with another well-studied cipher like Salsa20, Threefish or one of the AES finalists. This will cost you -- and there's no guarantee that both ciphers will stand over the long term. But the probability of two significant breaks seems lower than the probability of one.

8 comments:

  1. nice post, can you please advice on the best practice in combining two different Encryption algorithms, for example, should we use two different keys for each algorithm? should they both Block ciphers or stream ciphers?...etc

    ReplyDelete
    Replies
    1. With synchronous stream ciphers(including block-ciphers in CTR mode) it's relatively simple: Use independent keys and xor the key-stream.

      Tahoe-LAFS will use such a construction with AES-CTR and Salsa20.

      But it's quite unlikely that symmetric encryption is the weakest point of your system. So for most applications I recommend not encrypting several times.

      Delete
  2. See this older post: http://blog.cryptographyengineering.com/2012/02/multiple-encryption.html

    The quick summary is that it's complicated. However, if you pick two independent keys and encrypt in a cascade (meaning encrypt with one cipher in a secure mode of operation, then encrypt with the other in a secure mode) the result will be (semantically) secure if one of the two encryption modes is.

    There are exceptions to this result when it comes to chosen ciphertext attacks, but the solutions to that problem require you to greatly increase the ciphertext size. I would generally advise you not to be that paranoid.

    ReplyDelete
  3. The problem is NSA is the adversary to us *all*. AT&T anyone? And if you think they are only targeting a handful of people, you've got another think coming. See William Binney and his outing of the program.

    It's also why they are so paranoid of Huawei -- they know they have employed the same "backdooring" tricks they accuse Huawei of doing. It takes one to know one.

    So if you need to do anything really sensitive, your best move is to not do it on the Internet (or any other electronic form) at all. Using a carrier pigeon would be more secure.

    This is why I think the field of computer crypto is essentially good only as an academic exercise. It is all but worthless in practice unless you control all the hardware and software down to the last transistor and line of code. Fat chance of that ever happening (unless you are the NSA, of course). This is why they only approved AES for classified material in NSA approved systems. In other words, they want full control of the hardware and software implementation. This way they can ensure there are no backdoors or side-channels, as there obviously are in consumer grade variants and implementations.

    ReplyDelete
  4. This sentence is not clear to me:
    "To make it run fast you have to expand the key into a series of tables -- which increases key setup time and potentially makes you vulnerable to cache timing attacks"
    The tables aren't just to speed up sboxes and mixcolumn operations (thus not key related) ?

    ReplyDelete
    Replies
    1. There are several tables in AES. The sentence cited speaks about the result of the key schedule, i.e. all of the round keys. You'll want to do this only once, not for each block separately. But I don't really see any cache timing attack possibilities here, as the access pattern to the round keys is completely predictable.

      Delete
  5. What about using Keccak in its authenticated-encryption mode (i.e. using the duplex construction, not the sponge one)?

    ReplyDelete
    Replies
    1. Until most CPUs have specialized Keccak instructions it'll probably be slower than other encryption algorithms.

      Delete