Schneier on Security

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.

@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!

@memory: Some key qualifications to what I just said.

1) SSE2 Skein would be slower than the current 64-bit implementation of Skein, even for a parallelized Skein. That's because SSE2 tragically lacks a rotate instruction. That's not guaranteed to change w/the next gen of processors and their larger SIMD register sizes.

2) Larrabee and GPGPU are promising but unproven.

3) 5 cpb is a common-sense estimate; these future processors don't exist so I can't benchmark.

Still. Tree mode: interesting.

@will: Nothing of my own, but here are some links:

Intro:
http://tirania.org/blog/archive/2008/Nov-03.html -- Miguel de Icaza explains SIMD while talking about support for it in Mono

Reference:
http://msdn.microsoft.com/en-us/library/... -- Microsoft's reference on the SSE2 compiler intrinsics, which are what you'll actually use to code SSE in C++ -- I used this heavily when trying to code with SIMD
http://softpixel.com/~cwright/programming/simd/... -- concisely lists what instructions there are

Fun speculation on SIMD and the future:
http://en.wikipedia.org/wiki/... -- Intel's 256-bit successor to SSE2, also adopted by AMD
http://en.wikipedia.org/wiki/... -- first processor slated to implement AVX
http://en.wikipedia.org/wiki/Larrabee_(GPU) -- GPU promising many processor cores with 512-bit SIMD; might be vaporware
http://en.wikipedia.org/wiki/GPGPU -- general-purpose computing on (highly SIMD) GPUs
http://www.nvidia.com/object/cuda_home.html -- NVIDIA's site on GPGPU

Relevant Wikipedia articles:
http://en.wikipedia.org/wiki/...
http://en.wikipedia.org/wiki/SIMD
http://en.wikipedia.org/wiki/...

Some software using SSE2:
http://www.cryptopp.com/docs/ref551/... -- Wei Dai's implementation of Salsa20
http://cubehash.cr.yp.to/emmintrin.c -- djb's implementation of CubeHash

SHA-3 and SIMD:
http://www.di.ens.fr/~leurent/simd.html -- A SHA-3 candidate built to work well with SIMD instruction sets
http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/ -- JH is also meant to be SIMD-friendly
(Other SHA-3 candidates may also benefit -- BLAKE, being based on ChaCha, can probably be sped up. Honestly, I haven't thought through vectorizing them all.)

@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?... .

(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.

@moderator: I submitted a big old list of links for @will as a comment, and MT probably blocked it as spam. Since will asked and it's relevant (has to do with crypto performance, which is important to SHA-3), I'd love to see it unblocked. Or e-mail me and I'll put up a post on Blogger somewhere.