Schneier on Security

Susi • December 12, 2008 11:03 PM

Bruce, I need to point out some code implementation issues for the x86 CPUs before the SHA3 contest is over.

Have you ever considered using SSE2+ integer instructions to further speed up the hashing? I mean, all those different suggested hashing algorithms have at least one reference implementation in C and almost all ones have one in assembly which both are used for benchmarking them. But the assembly code mostly uses only general purpose instructions – I neither have looked into every paper nor do I know the conditions of the contest in detail – but i guess that SIMD assembly code would be at least faster and maybe even simpler than the general purpose assembly code.

Basically, on a 64bit x86 CPU, you may use 14 to 15 out of 16 general purpose registers each being 64bit wide in your hashing routine. With all the current SSE… SIMD instructions, you have 16 out 16 general purpose registers each being 128bit wide. This means you can do at least (in theory) twice the stuff in parallel (especially since there is a double 64bit SIMD add instruction in the later SIMD instructions). Also, this may allow you to keep more of the internal state in registers, requiring less use of state (and less state) variables, fastening it up and rendering it more easy to implement (also, the SSE instructions are really easy to use).

There are similar SIMD instructions in the MMX/MMX+ instruction family, which would especially speed up the hashing codes for older 32bit x86 CPUs, because else you could only use 6 to 7 out of 8 general purpose registers each being 32bit wide. You can use 8 out of 8 MMX registers each being 64bit wide, which is better than using only the 32bit general purpose registers, but not as good as using the 16 128bit SSE registers in the 64bit CPUs.

Most x86 32bit implementations will actually run on a real 64bit CPU in the (32bit) compatibility mode. Those 64bit CPUs in compatibility mode and some later 32bit only CPUs actually also have SSE integer instructions (SSE2 onwards), but only 8 128bit registers.

One downer for all the 3 SIMD implementations is that you will need to use 2 SHIFTS and 1 OR to perform 1 ROTATE.

Now we conclude, that for every hashing algorithm to have an optimal implementation for each CPU, we need at least 3 different SIMD assembly implementation (pre 80686 excluded). This seems like a lot of work, but I guess it’s worth a try. I think someone should tell this the other candidates and the committee/jury too.

About Skein:

Finally, I must admit that I like Skein quiet a lot for its ovewrall concept with the configuration space at the beginning, encouraging people to use their own variations and more seeds to the hash. I also like the combination of add and xor separated with a rotation. I think it gives a good mixture for a primitive, difficult to trace back, which I had the joy to personally do some basic experiments on, about 2 years ago.

One thing I am a little sceptical about is whether the total lack of sboxes provides enough diffusion for the non-linearity. Also, I think the fact that Skein had not had any external cryptoanalysis as of yet should be emphasized, rendering the 25 out of 72 rounds attack more insignificant. I believe that Skein should have more external cryptoanalisys, do you know of any group other than you working on it Bruce?

p.s. I also totally like the EDON-R algorithm, due to it being based upon super cool quasigroups (good description included) with a general building rule for arbitrary sizes, and all that without sboxes too!