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.

Steps are now being taken, rather faster since Dan Kaminsky came up with a really effective DNS poisoning attack, to secure DNS by using DNSSEC.

The basic idea of DNSSEC is that when you get an answer from the DNS it will be signed by someone you trust. At some point the “trust anchor” for the system will be “.” the DNS root, but for the moment there’s just a handful of “trust anchors” one level down from that. One such anchor is the “.se” country code domain for Sweden. Additionally, Brazil (.br), Puerto Rico (.pr), and Bulgaria (.bg) have signed their zones, but that’s about it for today.

So, wishing to get some experience with the brave new world of DNSSEC, I decided that Sweden was the “in” place to be, and to purchase “cloudba.se” and roll out my first DNSSEC signed domain.

The purchase wasn’t as easy as it might have been — when you buy a domain, Sweden insists that people provide their identity numbers (albeit they have absolutely no way of checking if you’re telling the truth) — or if a company they want a VAT or registration number (which are checkable, albeit I suspect they didn’t bother). I also found that they don’t like spaces in the VAT number — which held things up for a while!

However, eventually they sent me a PGP signed email to tell me I was now the proud owner of “cloudba.se”. Unfortunately, this email wasn’t in RFC3156 PGP/MIME format (or any other format that my usually pretty capable email client understood).

The email was signed with key 0xF440EE9B which was reassuring because the .se registry gives the fingerprint for this key on their website here. Rather less reassuringly footnote (*) next to the fingerprint says “.SE signature for outgoing e-mail. (**) June 1 through August 31.” (the (**) is for a second level of footnote, which is absent — and of course it is now September).

They also enable you to fetch the key through a link on this page to their “PGP nyckel-ID” at http://subkeys.pgp.net.

Unfortunately, fetching the key shows that the signature on the email is invalid.

Since the email seems to have originated in the Windows world, but was signed on a Linux box (giving it a mixture of 0D 0A and 0A line endings), then pushed through a three year old copy of MIME-tools I suppose the failure isn’t too surprising. But strictly the invalid signature means that I shouldn’t trust the email’s contents at all — because the contents have definitely been tampered with since the signature was applied.

Since the point of the email was to get me to login for the first time to the registry website and set my password to control the domain, this is a little unfortunate.

Even if the signature had been correct, then should I trust the PGP key?

Well it is pointed to from the registry website which is a Good Thing. However, they do themselves no favours by referencing a version on the public key servers. I checked who had signed the key (which is an alternative way of trusting its provenance — since the email had arrived to a non-DNSSEC secured domain). Turned out there was no-one I knew, and of 4 individual signatures, 2 were from expired keys. The other signature was the IIS root key — which sounds promising. That has 8 signatures, once again not people I know — but only 1 from a non-expired key, so perhaps I can get to know some of the other 7?

Of course, anyone can sign a key on a public key server, so perhaps it makes sense for .se to suggest that people fetch a key with as many signatures as possible — there’s more chance of it being signed by someone they know. Anyway, I have now added my own signature, using an email address at my nice shiny new domain. However, it is possible that I may not have increased the level of trust

In the case of phishing, it is relatively clear. The developers believe the PKI book. The PKI people believe in the efficacy of digital signatures to prove stuff. The cryptographers believe in the perfection of mathematics, and the security world believes in the completeness of their own learning. They are all wrong, but only at the large level of generalisations, not at the detailed level of particular claims. Any one of the claims, in isolation can be shown to be true. But, generalising these brittle claims to be solid building blocks is a completely different question. Few of the claims are strong enough to partake in a general model without severe support; the general model of secure browsing is the best evidence of how it is secure in name only.

How then is it built? By accident or by design, a series of claims meet together in a holy ring of righteous architecture. Each of the proponents claim loudly that their part is strong, but the ring has no strength. Eventually, one of the claims in the links is broken. For phishing, the browsers never did have the potential to show authenticity; not only did they not have the security strength to do it (c.f., Skype v. CSRF), they didn't even do it in practice (recall the lost padlock?), and their recent efforts to show authenticity (c.f. colour debate) reveal how far they are from understanding even the goal, let alone the implementation. Once that link was broken, and money was made, all the others revealed their weaknesses, as crooks systematically worked to breach the lot.

If we look at the wider financial collapse, now underscored by the nationalisation of the worlds biggest financiers of mortgages ($ 5.3 trillion.... or is it $ 5.4 ?), we see the same pattern. The bankers believed in their product. The originators believed in their origination, the securitizers believed in their free market and accurate price, and the holders believed in the assets. The CDO, the subprime, the other 100 special names, each was a contract. Each was clear in and of itself. But, when placed end-to-end, in a line, with a bunch of other agreements, the claims that were good in isolation were not strong enough to participate in the super-claim made of the overall edifice.
The financial system was built like a bridge; each piece rested on the previous one. And then, the clever architects bent the bridge around ... and around again, until the first piece met the last. The elegant keystone of finance was to finally lift up the first one to rest on the last.

Thus, the banks themselves invested their capital in their own product.