NIST may not have you in mind
imperialviolet.org
imperialviolet.org
Last week at CCSW, we published a paper[1] detailing our attempts to bring these attacks to bear against Chromium.
In short, we don't see AES cache timing attacks as possible on more recent processors, and especially so once you factor in the sheer size of modern architected code.
[1] http://cseweb.ucsd.edu/~kmowery/papers/aes-cache-timing.pdf
DJB's attacks were from a remote attacker's vantage point. But your paper also takes on Osvik and Tromer, who used "spy processes" to continuously probe local caches to create traces that could be analyzed for key information. I know your paper mentions branch prediction and says you don't have results for it, but what's your take on whether Aciicmez's BTB attack is going to remain viable?
I thought the BTB attack was the cleverest and most disquieting of the bunch, in that it suggested that we don't even know enough about the x86-64 microarchitecture to predict what side channel vulnerabilities we might have in software AES.
Regarding the paper itself: the most provocative claim it makes is that we're trending towards "complete mitigation" of cache side channel attacks. You give two reasons: AES-NI and multicore systems.
The AES-NI argument seems compelling but a little obvious, in the same sense as one could have argued that peripherals that offloaded AES would also blunt attacks against software AES. AES-NI blurs the line between software and hardware AES, but it's still a hardware implementation.
Another argumentative point that could be made here is, AES-NI mitigates cache-timing attacks against systems that use AES. It doesn't do much good if you can't use AES, since the most popular block ciphers that compete with AES are also implemented with table lookups.
I found the multicore argument a lot less compelling, since it relied in part on the notion that attackers wouldn't easily be able to predict the cache behavior of their target multicore systems. It seems to me that the most likely environment in which cache timing attacks are going to be a factor on the Internet is shared hosting environments, in which attackers with the sophistication to time AES are easily going to be able to get a bead on exactly what hardware and software they're aiming at. Most users of AES are also using off-the-shelf hardware and software.
I do agree with you that x86-64 is extremely complicated, and that new attacks might crop up due to some future optimization.
As for the paper:
Yeah, AES-NI is sort of the final hammer against AES cache timing attacks, since it doesn't use the cache at all, but I felt that a paper on AES cache timing would be remiss without mentioning it :)
There are two parts to the multicore argument: the first is that it complicates things massively, and the second is that it can be a complete mitigation if used properly.
First is the complication bit, and that's just saying that the attacker must understand almost everything about the multicore implementation, including multilevel cache behavior and (possibly non-deterministic?) replacement strategy. I'm willing to believe that, were this the only hurdle, a dedicated attacker could still succeed. I was looking at a single core machine, so I didn't have to deal with the complexity here.
For the complete mitigation, you need to rely on platform support for core pinning. If you're allowed to say "I want to do encryption now, give me my own core for 400ms", then, since the 4KiB T-tables fit into your core's L2, attacker threads on other cores just can't examine them during use. This complicates the VM hosting model and might be a decent DOS attack, but it does completely stop cache probing attacks.
Finally, as you said, my work can really only apply to AES on the x86 on the desktop. Change one of these variables (such as AES to ElGamal or RSA or Blowfish), and side channel attacks might still exist. Such is the problem with negative results :)
If you're an HN'er reading along at home, Aciicmez' BTB timing paper (you should just be able to Google that) is very very very cool. They not only realized that you could theoretically watch the caches used by the branch predictor to build a trace from which you could recover RSA keys, but also came up with a very simple way to profile those branch predictor caches; that is, they designed a "spy process" like Osvik and Tromer did for memory caches that targeted the BTB instead.
Can anyone shed any light?
On a related note AES is the NIST standard for protecting sensitive but unclassified information:
"Applicability. This standard may be used by Federal departments and agencies when an agency determines that sensitive (unclassified) information (as defined in P. L. 100-235) requires cryptographic protection.
Other FIPS-approved cryptographic algorithms may be used in addition to, or in lieu of, this standard. Federal agencies or departments that use cryptographic devices for protecting classified information can use those devices for protecting sensitive (unclassified) information in lieu of this standard." [1]
I have always assumed that this scope limitation within FIPS197 meant that NSA, DoD, Secret Army of Northen VA, etc had a different standard/requirements (NSA Suite A&B) for classified (and up) information. Is this the case? If so why would NSA have so much skin in the game if they were not restricted to FIPS197 requirements?
[1] http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
While they exert a disproportionate amount of guidance to other agencies, that is generally orthogonal to their primary motivations.
You can certainly make a case that NSA pushes NIST towards making guidelines for things that they favor, but I don't seriously believe that's at the expense of weakening other agencies (at least not as a goal).
As to classified and up information, the NSA can't get enough ECC, and many of the Suite B implementations of other standards are just a version of the standard that works (and is "certified") to use Elliptical Curve Cryptography (like TPM Suite B, which we work on).
Could NSA's hardware centric recommendations be motivated by an interest in leveraging economies of scale (due to the size of federal IT procurement) and purchasing COTS hardware that was optimized for AES?
But I am claiming that there's a hardware orientated bias in the major recommendations that I see NIST making in the crypto space. I'm taking a flying guess at the reason, and perhaps I should simply have skipped any speculation. But the seeming bias is still worth highlighting I think.
The amount of hardware support that AES has already is pretty substantial: https://en.wikipedia.org/wiki/AES_instruction_set
I'd rather not suppose there's something insidious going on here, just that maybe NIST is taking a longer-term view than racing to put AES and SHA3 in everything yesterday.
Salsa20 is a stream cipher, AES is a block cipher.
It is like saying 'Try GCC rather than Windows 8'.
Even most message-based crypto --- applications where the designers can predict the size of most encrypted messages --- are well served by CTR, or by a native stream cipher.
So, while there are fundamental differences between Salsa20 and AES, for bulk encryption purposes those differences come nowhere close to the difference between GCC and Windows 8. It's really more of a "GCC vs. LLVM" kind of difference.
Salsa20 <stream cipher> is not a "traditional" stream cipher -- basically it's Salsa20 <hash function> (not collision resistant) in counter mode. The hash function itself is implemented as permutation with final addition of input words to make it irreversible. With this permutation you can build a block cipher, and by the way that's what SHA-3 finalist BLAKE does by introducing addition of key words during rounds (except it's built on a variant of Salsa20 called ChaCha20).
(I'm not saying that you should build your own block cipher from Salsa20, of course :)
The original sentence, though, is:
try Salsa20 rather than AES and Poly1305 rather than GCM.
AES-GCM is also not a "block cipher".