|Not this cipher.|
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?
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 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.
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.