Bending Skein Code

Few of the submissions to NIST's hash standard contest have been optimized for desktop/server processors. One, though, known as Skein, seems to have considered this. It is designed specifically to run well on Intel Core 2 processors -- without sacrificing speed on other processors or security.I write fast code. People ask me how I do it. I tell them:

"Do not try to bend the spoon; that's impossible. Instead, only try to realize the truth. There is no spoon. Then you'll see that it is not the spoon that bends. It is only yourself."

Computers have the ability to run many times faster than they do in practice. That is the because the problems they are trying to solve don't completely fit with the hardware -- they aren't "bent" to conform to hardware quirks.

A good example is crypto algorithms. Common crypto algorithms consist of logical operations that transmogrify bits within data. A modern computer processor, like the Intel Core 2, can execute three logic instructions per clock cycle (meaning a 3-GHz processor can do 9 billion logic operations per second).

Unfortunately, the logic a crypto algorithm wants to do doesn't quite fit on the processor. The older hash algorithm, SHA-1, is a good example. It only used about a quarter of the potential of the Core 2 processor. It can only do about 1.5 logic operations per clock, and each operation operates on 32 bits rather than the full 64-bit potential of the processor.

First standardized around 1993, SHA-1 is now considered weak. NIST, the U.S. National Institute of Standards and Technology, is holding a contest to create a successor. This is similar to the contest it held for the AES symmetric-encryption standard, but this one will come up with a new hash standard tentatively called "SHA-3."

Roughly 10 people/groups have submitted algorithms. These submissions make some accomodation to the Core 2 processor. They operate in "little-endian" mode (a quirk of the Intel-like processors that reads some bytes in reverse order). They also allow a large file to be broken into chunks to split the work across multiple processors.

However, virtually all of the contest submissions share the performance problem mentioned above. The logic they use won't optimally fit within the constraints of a Intel Core 2 processor. Most will perform as bad or worse than the existing SHA-1 algorithm.

One exception to this is Skein, created by several well-known cryptographers and noted pundit Bruce Schneier. It was designed specifically to exploit all three of the Core 2 execution units and to run at a full 64-bits. This gives it roughly four to 10 times the logic density of competing submissions.

This is what I meant by the Matrix quote above. They didn't bend the spoon; they bent the crypto algorithm. They moved the logic operations around in a way that wouldn't weaken the crypto, but would strengthen its speed on the Intel Core 2.

In their paper (PDF), the authors of Skein express surprise that a custom silicon ASIC implementation is not any faster than the software implementation. They shouldn't be surprised. Every time you can redefine a problem to run optimally in software, you will reach the same speeds you get with optimized ASIC hardware. The reason software has a reputation of being slow is because people don't redefine the original problem. This is the sort of thing I did with intrusion detection/prevention. I redefined how I did detection in order to optimize how fast it ran. (The trick, by the way, is to use state machines so that you don't have to reassemble at low layers of the stack, just reorder fragments.) This prejudice about software has long frusterated me. I saw customers test my solution, find it was faster, but STILL buy the ASIC product because "everyone knows hardware is faster."

By the way, logic density should be considered a security risk. Hacking tools like John the Ripper crack hashed passwords by guessing more than one password at a time. While you can only use a quarter of the CPU resources to hash a single password, you can hash four passwords simultaneously using all of the resources. This gives the hacker a four-to-one advantage. It's a small advantage in the grand scheme of things, to be sure, but an advantage worth considering nonetheless.

I look forward to playing with assembly language versions of the NIST submissions. I'm particularly interested in SSE instructions that use 128-bit registers. The Core 2 only executes two 128-bit instructions per clock vs. the three 64-bit instructions used in Skein, so SSE is unlikely to help Skein much. It might help other algorithms, though.

Robert Graham is CEO of Errata Security. Special to Dark Reading