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

 

Recommended Reading:

Comment  | 
Print  | 
More Insights
Comments
Threaded  |  Newest First  |  Oldest First
COVID-19: Latest Security News & Commentary
Dark Reading Staff 7/6/2020
Ripple20 Threatens Increasingly Connected Medical Devices
Kelly Sheridan, Staff Editor, Dark Reading,  6/30/2020
DDoS Attacks Jump 542% from Q4 2019 to Q1 2020
Dark Reading Staff 6/30/2020
Register for Dark Reading Newsletters
White Papers
Video
Cartoon
Current Issue
How Cybersecurity Incident Response Programs Work (and Why Some Don't)
This Tech Digest takes a look at the vital role cybersecurity incident response (IR) plays in managing cyber-risk within organizations. Download the Tech Digest today to find out how well-planned IR programs can detect intrusions, contain breaches, and help an organization restore normal operations.
Flash Poll
The Threat from the Internetand What Your Organization Can Do About It
The Threat from the Internetand What Your Organization Can Do About It
This report describes some of the latest attacks and threats emanating from the Internet, as well as advice and tips on how your organization can mitigate those threats before they affect your business. Download it today!
Twitter Feed
Dark Reading - Bug Report
Bug Report
Enterprise Vulnerabilities
From DHS/US-CERT's National Vulnerability Database
CVE-2020-15570
PUBLISHED: 2020-07-06
The parse_report() function in whoopsie.c in Whoopsie through 0.2.69 mishandles memory allocation failures, which allows an attacker to cause a denial of service via a malformed crash file.
CVE-2020-15569
PUBLISHED: 2020-07-06
PlayerGeneric.cpp in MilkyTracker through 1.02.00 has a use-after-free in the PlayerGeneric destructor.
CVE-2020-7690
PUBLISHED: 2020-07-06
It's possible to inject JavaScript code via the html method.
CVE-2020-7691
PUBLISHED: 2020-07-06
It's possible to use <<script>script> in order to go over the filtering regex.
CVE-2020-15562
PUBLISHED: 2020-07-06
An issue was discovered in Roundcube Webmail before 1.2.11, 1.3.x before 1.3.14, and 1.4.x before 1.4.7. It allows XSS via a crafted HTML e-mail message, as demonstrated by a JavaScript payload in the xmlns (aka XML namespace) attribute of a HEAD element when an SVG element exists.