Schneier on Security

Randall • July 24, 2009 5:56 PM

Re: CubeHash, djb mentioned something about CubeHash8/32 at the end of his slides at one of the conferences, right? He’s allowed to tweak the algorithm until September 15, so he might make it a more realistic competitor by lowering the insane safety factor.

I’ll repeat my earnest wish to see a tree mode of Skein as the default. The next generation of Intel processors will have 256-bit SIMD, meaning four Threefish encryptions at once, per core. Ain’t nothin’ to sneeze at.

Randall • July 24, 2009 10:47 PM

@memory: with a SIMD instruction set like SSE2, you don’t deal with multiple processors. One processor performs an identical task on multiple chunks of data in parallel: “XOR these four words onto these four” or “add these four words to these four.” It’s used in the real world: in the Crypto++ implementation of Salsa20, for instance, and in some SHA-3 candidates including CubeHash and SIMD.

I sent the Skein team some code implementing Skein in SSE2 that does two Threefish encryptions at once and throws one away; it takes about 20 cpb. (That’s much slower than their best 64-bit implementation (6 cpb), but faster than other 32-bit implementations, which is why it’s useful. (Also, I owe the Skein team some cleanup on that code…))

If my code weren’t throwing the results of one encryption away, it would be getting 10 cpb on 32-bit machines. You could exploit that speed in a tree hash or when, say, using Threefish to encrypt in counter mode. If you scale that up to 256-bit SIMD in Intel’s next-gen processors and do four encryptions at once, then you’d be getting 5 cpb. On the other hand, those processors might have other improvements that make the non-SIMD implementation of Skein faster.

GPUs go way beyond 256-bit SIMD. Intel’s Larrabee GPU (due next year? vaporware?) is supposed to have 512-bit SIMD in each core — eight encryptions at once — and existing GPUs can execute the exact same code on many sets of registers at once really efficiently.

I wouldn’t assume that GPGPU or far-future multicore speedups are all hogwash — people will continue to want to process data more quickly and clock rates aren’t going to keep on doubling forever, so we’ll eventually figure out how to make that kind of parallel computation more practical. But SIMD is something that you can use now. (Parallel ASIC implementations are also a short-term practical win.) If nothing else, it’s an easy way to nearly double Skein’s speed under 32-bit OSes!

Randall • July 26, 2009 11:04 PM

@dongs: Looks like rotations are only there for the 128-bit registers — see the “Shift/rotate…” bullet point at http://forums.amd.com/devblog/blogpost.cfm?catid=208&threadid=112934 .

(Would be awesome if there were rotates on 256-bit regs, though. If you see something more specific than that post, would love to hear.)

Still, the current SSE2 Skein/CubeHash spend a lot of time rotating, so 128-bit registers with rotates may be faster than 256-bit registers without.