Dark Reading is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them.Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Perimeter

11/6/2008
06:15 PM
Robert Graham
Robert Graham
Commentary
50%
50%

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.

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

Comment  | 
Print  | 
More Insights
Comments
Threaded  |  Newest First  |  Oldest First
News
FluBot Malware's Rapid Spread May Soon Hit US Phones
Kelly Sheridan, Staff Editor, Dark Reading,  4/28/2021
Slideshows
7 Modern-Day Cybersecurity Realities
Steve Zurier, Contributing Writer,  4/30/2021
Commentary
How to Secure Employees' Home Wi-Fi Networks
Bert Kashyap, CEO and Co-Founder at SecureW2,  4/28/2021
Register for Dark Reading Newsletters
White Papers
Video
Cartoon Contest
Current Issue
2021 Top Enterprise IT Trends
We've identified the key trends that are poised to impact the IT landscape in 2021. Find out why they're important and how they will affect you today!
Flash Poll
How Enterprises are Developing Secure Applications
How Enterprises are Developing Secure Applications
Recent breaches of third-party apps are driving many organizations to think harder about the security of their off-the-shelf software as they continue to move left in secure software development practices.
Twitter Feed
Dark Reading - Bug Report
Bug Report
Enterprise Vulnerabilities
From DHS/US-CERT's National Vulnerability Database
CVE-2021-22675
PUBLISHED: 2021-05-07
The affected product is vulnerable to integer overflow while parsing malformed over-the-air firmware update files, which may allow an attacker to remotely execute code on SimpleLink Wi-Fi (MSP432E4 SDK: v4.20.00.12 and prior, CC32XX SDK v4.30.00.06 and prior, CC13X0 SDK versions prior to v4.10.03, C...
CVE-2021-22679
PUBLISHED: 2021-05-07
The affected product is vulnerable to an integer overflow while processing HTTP headers, which may allow an attacker to remotely execute code on the SimpleLink Wi-Fi (MSP432E4 SDK: v4.20.00.12 and prior, CC32XX SDK v4.30.00.06 and prior, CC13X0 SDK versions prior to v4.10.03, CC13X2 and CC26XX SDK v...
CVE-2020-14009
PUBLISHED: 2021-05-07
Proofpoint Enterprise Protection (PPS/PoD) before 8.17.0 contains a vulnerability that could allow an attacker to deliver an email message with a malicious attachment that bypasses scanning and file-blocking rules. The vulnerability exists because messages with certain crafted and malformed multipar...
CVE-2021-21984
PUBLISHED: 2021-05-07
VMware vRealize Business for Cloud 7.x prior to 7.6.0 contains a remote code execution vulnerability due to an unauthorised end point. A malicious actor with network access may exploit this issue causing unauthorised remote code execution on vRealize Business for Cloud Virtual Appliance.
CVE-2021-26122
PUBLISHED: 2021-05-07
LivingLogic XIST4C before 0.107.8 allows XSS via feedback.htm or feedback.wihtm.