7 ms·
NIST may not have you in mind
- planckscnst 14y agoIt seems strange that the author is complaining about AES speed. About a year ago, I benchmarked an IPsec setup between two cheap routers with an ARM9 processor that did not have any special crypto blocks in it. AES significanly outperformed the other algorithms I tried.
- tptacek 14y agoYou were almost certainly benchmarking an implementation of AES that relies on table lookups for speed; those table lookups create a side channel vulnerability, which was much of the point of this article.
- planckscnst 14y agoInteresting; it was what's in the Linux kernel.
- tptacek 14y agoPretty sure that's an S-box AES. The issue is that when implemented (a) in software (b) without reliance on large lookup tables --- ie, "securely" --- AES is significantly slower.
- dchest 14y agohttp://bench.cr.yp.to/results-stream.html http://bench.cr.yp.to/results-stream.html
- tptacek 14y agoThat's a table of stream ciphers benchmarked against AES, a block cipher, in CTR mode.
- dchest 14y agoYes. Apart from disk encryption, they are pretty much interchangeable (OP talked about IPSec).
- tptacek 14y agoAES is normally benchmarked against other block ciphers. It might not be fair to compare the performance of a native stream cipher to that of AES rigged up as a stream cipher with CTR.
- floody-berry 14y agoWhat makes the comparison unfair?
- tptacek 14y agoThe other ciphers are natively stream ciphers, and AES is a block cipher adapted via CTR mode to be a stream cipher.
- floody-berry 14y agoI'm still missing what makes it unfair. Are other modes of AES potentially faster? Does AES provide something that stream ciphers don't? Are Salsa20/Chacha20 unable to be compared to anything because they're native stream ciphers that look like a block cipher in CTR mode under the hood?
- tptacek 14y ago1. Yes. 2. Yes. 3. No.
- pbsd 14y agoKäsper and Schwabe's bitsliced AES [1] does not need very long streams to be fast. It processes 8 blocks simultaneously, not 128 (as a 'pure' bitsliced approach would), and therefore reaches peak performance at relatively small lengths, starting at 128 bytes. [1] http://cryptojedi.org/papers/aesbs-20090616.pdf http://cryptojedi.org/papers/aesbs-20090616.pdf
- agl 14y agoLooks like I haven't been keeping up to date even with my own colleagues' work! Thanks, I'll update the post.
- Nursie 14y agoIntel have specific instructions for GCM that mitigate some of this stuff I'm sure. I know this doesn't translate to 'NIST are keeping software implementations in mind', but when these things are available on a few processors that does make the software guy's job easier.
- el_cuadrado 14y ago> try Salsa20 rather than AES Salsa20 is a stream cipher, AES is a block cipher. It is like saying 'Try GCC rather than Windows 8'.
- tptacek 14y agoThat's more untrue that true. Most popular applications of AES could just as easily use CTR instead of CBC (I'm not particularly interested in litigating the conversion of applications that use ECB); many of those applications even have an option to do that. Most settings in which AES-CTR is acceptable admit to any other stream cipher. 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.
- askimto 14y agoThat's a stretch.
- dchest 14y agoIn addition to what others said, there's even fewer differences between them internally. 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".
- tptacek 14y agoFor those playing along at home, AES-GCM is AES in CTR mode plus a variant of Wegman-Carter MAC function to authenticate the data.
- dfc 14y agoI do not understand the jump from the NSA having a history of building systems from the chip up to reasoning by analogy that the same is true for NIST (The shared worldview link is 20 years old). I'm not disagreeing with the statement, I just do not see any support for the conclusion that NIST's is bad for the general public because unlike NIST's target customers we are not building custom chips. Can anyone shed any light?
- tptacek 14y agoNIST doesn't build systems. It standardizes technology for the US. NIST standardizes far more than just crypto algorithms, but in the crypto cases, NSA reviews potential standards before the standard is published, for suitability to DoD. It is entirely reasonable to propose that NSA pushes NIST towards standardizing crypto that NSA is in a better position to use than industry is.
- dfc 14y agoI was hoping you would respond, thanks tptacek. In light of your comment, is it reasonable to assume that NSA is going to supply the custom chips to the rest of the federal government? Given federal procurement standards it seems that the majority of federal IT departments rely on industry to provide hardware. Is it still reasonable to propose that NSA pushes NIST in a direction that serves NSA's interest at the cost of weakening other governmental agencies? What is the implementation deadline for federal use of SHA-3? Is it unreasonable to assume that the standards committee expects SHA-3 hardware implementation similar to AES-NI? 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 http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
- deleted 14y ago[deleted]
- uvdiv 14y ago8 random decimal digits takes ~26.6 bits. An ordered list of 10^6 of these takes 3.17 MiB. The information taken by the ordering is lg(10^6!) ~= 2.20 MiB. So as an unordered multiset, the information content is 0.96 MiB. It's possible, at least in information theory terms. But the answers here don't do it. LZMA does nothing here. (MiB = 2^20 bytes; Stirling's approximation => ln(n!) ~= n ln n - n) (edited for arithmetic error)
- blazingice 14y agoThis article focuses pretty heavily on the possibility of cache timing attacks against AES, and cites djb's original work along with Tromer/Osvik's publication in 2005. 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 http://cseweb.ucsd.edu/~kmowery/papers/aes-cache-timing.pdf
- tptacek 14y agoThis is very cool, thanks for posting. 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.
- Tobu 14y agoHardware will evolve. CPU's design constraints — programs with low parallelism and not much awareness of the memory hierarchy — have caused a bottleneck. SHA-3 will end up as yet another specialty instruction, with the actual programming done by the hardware vendor. For people who don't want to be dependent on that, I imagine GPUs provide a faster and more flexible alternative.
- dguido 14y agoI just checked and all of the computers and devices I own for work have AES hardware in them (Mac Mini, Macbook Air, iPhone). Maybe NIST thinks that, through standardization efforts, they can encourage more people to integrate such hardware over the long term? The amount of hardware support that AES has already is pretty substantial: https://en.wikipedia.org/wiki/AES_instruction_set 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.