Hash functions are the most commonly used cryptographic primitive, and the most poorly understood. You can think of them as fingerprint functions: They take an arbitrary long data stream and return a fixed length, and effectively unique, string. The security comes from the fact that while it's easy to generate the fingerprint from a file, it's infeasible to go the other way and generate a file given a fingerprint.

Originally created to make digital signatures more efficient, hashes are now used to secure the very fundamentals of our information infrastructure: in password logins, secure web connections, encryption key management, virus and malware scanning, and almost every cryptographic protocol in current use. Without cryptographic hash functions, the internet would simply not work. At the same time, there isn't a good theory of hash functions. Unlike encryption algorithms, there are no secret keys involved; this makes it harder to mathematically define exactly what hash functions are.

The National Institute of Standards and Technology, NIST, is holding a competition to replace the SHA family of hash functions. "SHA" stands for "Secure Hash Algorithm." It was developed by the NSA in 1993 to replace the commercial MD4 and MD5 algorithms, and has been updated several times since then. All the SHA algorithms are very similar, and have been increasingly under attack, so NIST wants to replace them.

The competition is important because, unlike other technological standards, committee design — balancing the interests of diverse constituents — isn't conducive to good security. Security is best when it's designed by expert teams and then subjected to public review. And cryptography is best when it's chosen by competition.

In 1997, NIST held a competition for a block cipher to replace DES. Fifteen candidates and three-and-a-half years later, Rijndael became the new Advanced Encryption Standard — AES. NIST is doing the same thing for what it's calling SHA-3 (not, for some unexplained reason, the Advanced Hash Standard or AHS).

The deadline was October 31, and NIST received 64 submissions. This isn't surprising — I predicted 80 — as most of the 15 AES submitters were professors, whose students at the time have become professors themselves, with their own students. (If NIST does a stream cipher competition in another ten years, they should expect about 256 submissions.) These submissions came from academia, from industry, and from hobbyists. CIO magazine recently interviewed one of the submitters, who is 15. Twenty-eight submissions have been made public by the submitters, and six of those have been broken.

NIST is going through all the submissions right now, making sure they are complete and proper. Their goal is to publish all accepted submissions by the end of November, in advance of the First Hash Function Candidate Conference, to be held in Belgium right after the Fast Software Encryption workshop in February.

The group expects to quickly make a first cut of algorithms — hopefully to about a dozen — and give the community a year of cryptanalysis before making a second cut in 2010. After another year of cryptanalysis, NIST will choose a winner in 2011. Expect a final standard by 2012.

My advice for software developers is to let the process run its course. While it's tempting to use the new cool algorithms in your designs, it's far too soon to trust any of them. This process is likely to result in all sorts of new research results in hash function security, and some real cryptanalytic surprises. Give the community a few years to figure out which ones are good and which aren't.

I've previously called this sort of thing a cryptographic demolition derby: The last one left standing wins. But that's only partially true. Certainly all the groups will spend the next few years trying to cryptanalyze each other, but in the end there will be a bunch of unbroken algorithms. NIST will select one based on performance and features.

NIST has stated that the goal of this process is not to choose the best standard but to choose a good standard. I think that's smart; in this process, the best is the enemy of the good. While there's no rush to choose a new standard — the SHA-2 algorithms will remain secure for the foreseeable future — we don't want to analyze the candidates forever.

Personally, I was part of a group of eight cryptographers that submitted Skein to the competition. A decade ago, writing Twofish and participating in the AES process was the most fun I had ever had in cryptography. These next few years promise to be even more fun.

---

Bruce Schneier is chief security technology officer of BT. His new book is Schneier on Security.

Errata: Version 1.1 of the paper, reference, and optimized code corrects an error in which the length of the configuration string was passed in as the size of the internal block (256 bits for Skein-256, 512 for Skein-512, and 1024 for Skein-1024), instead of a constant 256 bits for all three sizes. This error has no cryptographic significance, but affected the test vectors and the initialization values. The revised code also fixes a bug in the MAC mode key processing. This bug does not affect the NIST submission in any way.

NIST has received 64 submissions. (This article interviews one of the submitters, who is fifteen.) Of those, 28 are public and six have been broken. NIST is going through the submissions right now, making sure they are complete and proper. Their goal is to publish the accepted submissions by the end of the month, in advance of the Third Cryptographic Hash Workshop to be held in Belgium right after FSE in February. They expect to quickly make a first cut of algorithms -- hopefully to about a dozen -- and then give the community about a year of cryptanalysis before making a second cut in 2010.

Lastly, this is a really nice article on Skein.

These submissions make some accommodation 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.

That's exactly what we were trying to do.

Jeff Clark of Neoformist is one such artist blurring the boundaries between programming, verbal, and visual art. Using a scripted algorithm he generates portraits of famous people and animals using an algorithm that creates words in the colors and patterns needed to create the portrait. Some examples feature a shot of Barack Obama created with the words “Yes We Can” and Albert Einstein with the word “Genius.” Very cool– go take a look.

The sky is falling! Trip Chowdhry, the analyst with Global Equities Research who claimed Red Hat was ‘rubbish and the entire LAMP stack is potty, too’ published some eye-opening predictions, predominantly negative, about tech business in Silicon Valley. Now Chowdhry claims that “almost every VC funded open-source company is struggling and will run out of money within the next six months.” (Probably not the most unbiased guy about open source) Matt Asay argues that organizations in general are struggling, but open-source companies are not that high on the list. (But are they high on the VC “axe” list??) He notes Alfresco, Pentaho and JasperSoft are some of the players with ‘millions in the bank and growing revenue.’ Asay also says Chowdhry has a responsibility to do real due diligence and not create myths. Take that, Chicken Little! (img from Disney-Clipart)

We’re not as far behind as we thought we were. Google presented the results of a study they conducted about how IPv6- capable “ordinary users” are at the RIPE meeting in Dubai a few weeks ago. Turns out Apple Macs drive IPv6 penetration in the US. Fifty-two percent of all IPv6 users in the U.S. own a Mac and use 6to4 (creating IPv6 addresses from an IPv4 address and tunneling packets) – making the US fifth in the list of countries using IPv6. Russia and France took first and second place with .76 and .65 percent IPv6-enabled traffic . The US is at .45 percent. Worldwide, 0.238 percent of Google users’ systems are IPv6-enabled and prefer to use IPv6 over IPv4.

Obama’s win = Google’s win? Apparently Google CEO Eric Schmidt and President-Elect Obama are very good buddies and “this terrifies Microsoft”. Now competitors are more on guard against Google’s growing empire and popularity. Although Schmidt was mentioned as a possible candidate for the country’s new national CTO position, he said he would not accept the post if asked. I guess that’s one less thing Microsoft has to worry about.

The problem is that (Chris’ analysis is) completely impractical. I’ll take a recent, and fairly typical situation as an example. I was taking issue with the manner in which remote access was being provisioned for a third party vendor to connect to a system hosted by one of our European business units. To cut a long story short, it was not only a breach of policy but highly insecure. I wanted the access to be disconnected, the business unit director wanted my risk assessment. And he didn’t want to wait for it.

To quote Chris Hayes, spending time on working out the expected effectiveness of controls, over a given timeframe, as measured against a baseline level of force was not going to pacify an angry Italian fearful that my decision was going to cost him money. He wanted my explanation of the risk and more importantly, what I was going to offer as a solution to keep his business functioning

As Chris is someone who actually does this for a living in a large company, and this is typical of his actual day job, I really find Stuart’s “impractical” comment to be, um, misinformed.

Also, I think Stuart mistakes the purpose of a risk analysis.  The purpose of the risk analysis is not to force someone to be “secure”, but to provide knowledge for decision making.  Using it as a “hammer” to knock in the nail of your personal risk tolerance impairs efficiency and in the long run retards “security” as it creates political resentment.  Seriously, who cares if something might violate policy or not in a pre-implementation discussion?  Policies are not stone tablets handed down from on high, they are state-in-time codification of the data owners risk tolerance.  This risk tolerance changes sometimes, and that’s OK.

To that extent, I appreciate (and I’m sure Chris does, as well) that risk analysis does not create rationality in the data owner.  Someone who sees you as a speedbump on the route to progress they may not be ready to appreciate your point of view even if it is stated in the most rational manner possible.   But it’s worth noting (and Stuart’s example is indicative of this point) that risk analysis does not create rationality in the analyst, either.  If one is being so “security minded” as to ignore the risk tolerance of the business owner - we’re bound to get a reaction similar to that Stuart encountered.  In fact, a practical risk analysis like Chris performed on his blog, done in 30 minutes, should identify the critical point of disagreement between Stuart and the data owner (again, Stuart doesn’t own the data, the agitated Italian does).

But let’s stay rational and open to alternatives to what Chris offers.  Stuart states his approach to risk analysis as:

When I need to document a risk assessment I use a very simple form: list the threats, state the level of vulnerability, list the associated operational costs and potential revenue hits. High, medium, or low risk? Describe the controls and options. Write up who needs to do what, and how much of their time it’s going to take. Job done.

At first glance, I don’t think what Chris has done is any less efficient, and it provides greater insight (using Frequency and Capability instead of just ‘listing the threats’).  But what is key here is that Chris’ approach is consistent and defensible.  Less generous risk geeks and CSO’s I know would have no little difficulty with Stuart’s approach.  But to particularly answer Stuart’s main objection (impracticality) I would offer that with practice, Chris’ work is probably quicker and easier than Stuart’s described process as it eliminates much of the ambiguity an immature risk analysis creates - reducing the need for further discussion and arguments with data owners (regardless of disposition or nationality).

Finally the irony of Stuart’s post is that the reason he had this confrontation may in fact be because he was incapable of bringing a salient model for risk to the table, one that identified the factors that create risk and developed a defensible belief statement concerning risk.   We’ll never know if one would have helped him in this isolated instance, but I can tell you that in organizations like Chris’, good risk models and strong risk anlayses create operational efficiencies, reduce costs, and streamlines intra-departmental communications.

Also, check out the Securabit podcast I was a part of.