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.

The panelists were:
William P. Crowell – former Deputy Director of the National Security Agency
Michael P. Jackson – Deputy Secretary, Department of Homeland Security
Jose A. Rodriguez, Jr. – former Director CIA, National Clandestine Service & CIA, DCI Counterterrorist Center

Overall, it was a very nicely arranged event on a brisk fall evening with about 100 CXO attendees; mostly large but some small government contractors and a few product companies like ScienceLogic that conduct business with military, intelligence and the public sector.

No surprise, given the financial crisis the economy is suffering from that the panelists said we also have a crisis coming on the Federal budget front. This will put enormous pressure on the way Administration thinks, and how and where to spend the $$.

Obama’s tone regarding the issues he will be confronting in the world during the election was encouraging. Make the world more non-partisan and take on the threats that we have in front of us head-on!

The panel was very upfront about current threats. William Crowell said,

“It is highly imprudent to believe that there will not be another 9-11. We have to fund and support the work to stop other attacks. We can only mitigate risk but we can’t eliminate risk. We have to try to absorb the sense of urgency and wake up every day looking at the intelligence screens as if 9-11 happened within the last couple of months.”

He added,

“They (the intelligence community) need the innovation, sense of commitment and urgency that comes from the private sector – a sense of mutual commitment to that mission.”

Predicted Priorities for investment for DHS:

1. Cyber attack as the top issue
2. Nuclear threats including dirty bomb
3. Chemical and biological attacks
4. Explosive attacks against critical infrastructure with maximum # of lives and or financial disruption / loss.
5. Large scale natural disasters – hurricane + earthquakes
6. Border penetration - identity management and border management issues

An Obama administration will spend dollars around these threat vectors. They will want to spend $$ to help state and local governments. Grants to state and local governments should significantly increase with the Obama administration, so think about how you will increase your focus on the state and local government spending initiatives.

Secure border investments – the panelists believe that the new administration will feel compelled to invest here. Michael P. Jackson bluntly said, “You have to make investments in border tools to get meaningful immigration reform.”

Panelists agreed that the 1^st year will be an intense period of scrutiny about fundamental directions. We can’t afford it all at DHS; it is dramatically under budgeted. At TSA/DOT and then at DHS, we spent about $4 Billion on technology investments since 9-11; those investments are now reaching the end of the original service life.

One gripe from the panel that I found humorous: “We don’t have a group of people who think like entrepreneurs.” It is insane how long things last when you buy things in the government. As an example, we are still replacing vacuum tubes in some of the very old FAA gear… this is well beyond what any reasonable person would think these initial investments should/would last.

Final Thoughts:
I actually think that the Obama Administration will be quite favorable to COTS software products, SaaS offerings, and creative financing initiatives from the private sector. The government just won’t have the capital budget to do everything it wants to accomplish. I would say if you look at how intelligently and aggressively Obama used technology to assist his campaign, the odds are good that this new breed of IT talent (which is already really comfortable with SaaS products, blogs, wiki’s, hosted/outsourced Cloud solutions… this team really understands the latest technology trends) will quickly work to bring these new IT paradigms to the Federal marketplace. Clearly the private sector can help the Government achieve more with lower capital budgets – beginning to provide services rather than transaction-based selling. Another clear idea is to think about leasing as a better way to work with the government which going forward will have increased budgets restrictions.

They will likely be in confrontation with members of Congress that won’t change fast enough, however the future of our nation’s ability to fight terror lies in becoming more efficient and effective. It requires the government be flexible enough to figure out what jobs and IT functions to outsource in a nimble and smart way. My prediction: this is great news for Service Providers. Overall the next 4 years should be great for our business as well as the Managed Service Provider/SaaS industry!

The analysts paired up today:
Antonio Piraino (Tier1 Research)
William Fellows (The 451 Group)

My usual disclaimers on live-blogging: doesn’t include everything covered (just what was most interesting to me) and had to paraphrase some answers because I simply cannot type that fast.

Quick definition of Cloud Computing
WF: The cloud is a continuum of grid, virtualization and utility done right. It is about provisioning services instead of servers; flexible computing instead of fixed assets. Done right, the cloud abstracts users from the complexity of grid. Cloud computing is IT as a service. Cloud computing is the Third Way – not entirely in-house or outsourced, but an optimized hybridized version of both. In light of the Goldman Sachs report out resetting IT spending forecast from up 6% to down 1%, don’t underestimate the ability for enterprises to move from capex to opex by buying cloud computing instead of building it themselves.

The 451 Group conducted a survey on cloud computing in March, and then revisited it a month ago. Some interesting results:

• 84% have no plans to develop an internal cloud. 5% had no answer to this question. And for the 10% who did answer – the uses for a private/internal cloud were the same as those for a public cloud.
• Top 6 vendors they look to help them develop an internal cloud: Microsoft, IBM, Cisco, HP, Oracle, VMware

Is it all “upside” when it comes to cloud computing?

WF: Watch out for the Trojan horse, the red flag. What about the software needed to manage all this stuff? Any management software needs to take a holistic approach to solve the problem.

AP: Increased management requirements and capability – this is actually a great story for managed hosters who can hold your hand while getting you up into the cloud. Hosters alleviate the pain points, and this is why we’re going to see continued growth and focus in the managed hosting sector.

WF: I would argue that they’re too expensive. Look at Amazon – 10 cents a hit adds up.

AP: It’s almost impossible to do an apples-to-apples comparison between cloud providers. One reason is that they charge differently. I’d say that when you’re talking about the big cloud providers, you are right – that they are expensive over the long-term, but for use in the short-term, they can be optimal.

WF: The cloud is setting big expectations. Can IT deliver? It’s nice to talk about “shared resources for the greater good” but in any organization, you will still run into issues of power and control! Plus it’s still early days for resolution of regulatory issues and compliance around the cloud.

Final Thoughts

AP: Think of the opportunities of using cloud computing resources in the areas of testing and pre-production – short-term use/environment (quick up/quick down), inexpensive, opex not capex. We’re already seeing the cloud fostering much innovation.

WF: “It’s okay to fall in love with the term.” It is real but keep the expectations lower and realistic.

AP: I agree with you. The reality is that the cloud is driving a very fundamental underlying platform change. This is not just a term or something that will fall out of fashion. There’s a real need to build trust in the cloud and leveraging shared resources in this way – so use the cloud computing term cautiously; don’t abuse it and make the cloud seem like IT’s new toy.

No longer are OS vendors and other large infrastructure technology providers the main source of vulnerabilities. It’s the thousands of applications, produced by thousands of software vendors, that make up this huge 3rd wave. ISS reported that in 2007 that the top five sources of vulnerabilities: Microsoft, Apple, Oracle, IBM, and Cisco, had dropped to supplying us with only 13.6% of our vulnerabilities. 86.4% came from the other thousands of software vendors that supply our computers with a seemingly unending supply of vulnerabilities for attackers to exploit.

In a recent report Microsoft has congratulated itself on doing a good job securing Windows. And by all accounts they have done a good job. But then they state this:

“Unless software development practices change throughout the industry, any improvements in the security of Windows would be meaningless.”

Whoa. Millions of dollars spent on securing the most prevalent piece of software and it could be meaningless? Yes, it’s true. Since attackers typically only need one vulnerability, if it isn’t in the network, and it isn’t in the host configuration, and it isn’t in the OS, they will happily exploit a vulnerability in an application.

At every shift of exploit target the problem has gotten more difficult to solve. Networks had choke points and could be centrally managed. It took a while but eventually host configurations became centrally managed and automated tools could scan configurations. Although OSes were huge and complex beasts with 10’s of millions of lines of code, with enough effort, their vulnerabilities have been largely tamed as Microsoft’s Windows and the Linux kernel track record shows. This was a very substantial, over five year effort, which used some of the most talented security people anywhere.
But now what to do? Instead of a few OSes we now have thousands of applications with vulnerabilities. As Microsoft found out, the attackers don’t go away, they just move on to the next incrementally less juicy vulnerability. In the world of exploits that typically means the vulnerability with the next smallest target population.

Attackers have started with the common client applications that can be found on almost every machine: Acrobat, Flash, RealPlayer, Quicktime, popular antivirus software. And they will continue down the popularity slope until they get to application populations down in the thousands which is getting to fairly small software vendors. Attackers can do this because they can bundle many vulnerabilities together, exploiting the statistical fact that you must have some vulnerable software installed. Compromised web sites have been found attacking visitors with over ten client side exploits preying on multiple versions of vulnerable client software.

The solution to this problem is all software must be written securely, not just the software from the big guys. Small vendors think they aren’t a target just like home users used to think they weren’t a target. People thought, “Why would someone want to attack my home computer?” Then they realized they did home banking, or had a fast internet connection that could be used for DDoS attacks or sending spam. All software vendors need to get the same wakeup call. Attackers don’t want to find a vulnerability in your software to make you look bad. They want any vulnerability. If the population of your software is small they will just bundle your vulnerability together with others in an exploit pack. The days of the average software vendor not having to worry about application security are officially over.

Skein is our submission (myself and seven others: Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker). Here's the paper:

Executive Summary

Skein is a new family of cryptographic hash functions. Its design combines speed, security, simplicity, and a great deal of flexibility in a modular package that is easy to analyze.

Skein is fast. Skein-512 -- our primary proposal -- hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core -- almost twice as fast as SHA-512 and three times faster than SHA-256. An optional hash-tree mode speeds up parallelizable implementations even more. Skein is fast for short messages, too; Skein-512 hashes short messages in about 1000 clock cycles.

Skein is secure. Its conservative design is based on the Threefish block cipher. Our current best attack on Threefish-512 is on 25 of 72 rounds, for a safety factor of 2.9. For comparison, at a similar stage in the standardization process, the AES encryption algorithm had an attack on 6 of 10 rounds, for a safety factor of only 1.7. Additionally, Skein has a number of provably secure properties, greatly increasing confidence in the algorithm.

Skein is simple. Using only three primitive operations, the Skein compression function can be easily understood and remembered. The rest of the algorithm is a straightforward iteration of this function.

Skein is flexible. Skein is defined for three different internal state sizes -- 256 bits, 512 bits, and 1024 bits -- and any output size. This allows Skein to be a drop-in replacement for the entire SHA family of hash functions. A completely optional and extendable argument system makes Skein an efficient tool to use for a very large number of functions: a PRNG, a stream cipher, a key derivation function, authentication without the overhead of HMAC, and a personalization capability. All these features can be implemented with very low overhead. Together with the Threefish large-block cipher at Skein core, this design provides a full set of symmetric cryptographic primitives suitable for most modern applications.

Skein is efficient on a variety of platforms, both hardware and software. Skein-512 can be implemented in about 200 bytes of state. Small devices, such as 8-bit smart cards, can implement Skein-256 using about 100 bytes of memory. Larger devices can implement the larger versions of Skein to achieve faster speeds.

Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Here's source code, text vectors, and the like for Skein. Watch the Skein website for any updates -- new code, new results, new implementations, the proofs.

NIST's deadline is Friday. It seems as if everyone -- including many amateurs -- is working on a hash function, and I predict that NIST will receive at least 80 submissions. (Compare this to the 21 submissions NIST received -- five were rejected as not being complete -- for the AES competition in 1998.) I expect people to start posting their submissions over the weekend. (Ron Rivest already presented MD6 at Crypto in August.) Probably the best place to watch for new hash functions is here; I'll try to keep a listing of the submissions myself.

The selection process will take around four years. I've previously called this sort of thing a cryptographic demolition derby -- last one left standing wins -- but that's only half true. Certainly all the groups will spend the next couple of 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 of them; in this process, "best" is the enemy of "good." My advice is this: immediately sort them based on performance and features. Ask the cryptographic community to focus its attention on the top dozen, rather than spread its attention across all 80 -- although I also expect that most of the amateur submissions will be rejected by NIST for not being "complete and proper." Otherwise, people will break the easy ones and the better ones will go unanalyzed.

In the paper, we propose a simple solution: take-down companies should share their raw, unverified feeds of phishing URLs with their competitors. Each company can examine the raw feed, pick out the websites impersonating their clients, and focus on removing these sites.

Since we presented our findings to the Anti-Phishing Working Group eCrime Researchers Summit, we have received considerable feedback from take-down companies. Take-down companies attending the APWG meeting understood that sharing would help speed up response times, but expressed reservations at sharing their feeds unless they were duly compensated. Eric Olsen of Cyveillance (another company offering take-down services) has written a comprehensive rebuttal of our recommendations. He argues that competition between take-down companies drives investment in efforts to detect more websites. Mandated sharing of phishing URL feeds, in his view, would undermine these detection efforts and cause take-down companies such as Cyveillance to exit the business.

I do have some sympathy for the objections raised by the take-down companies. As we state in the paper, free-riding (where one company relies on another to invest in detection so they don’t have to) is a concern for any sharing regime. Academic research studying other areas of information security (e.g., here and here), however, has shown that free-riding is unlikely to be so rampant as to drive all the best take-down companies out of offering service, as Mr. Olsen suggests.

While we can quibble over the extent of the threat from free free-riding, it should not detract from the conclusions we draw over the need for greater sharing. In our view, it would be unwise and irresponsible to accept the current status quo of keeping phishing URL feeds completely private. After all, competition without sharing has approximately doubled the lifetimes of phishing websites! The solution, then, is to devise a sharing mechanism that gives take-down companies the incentive to keep detecting more phishing URLs.

Here is our stab at devising a suitable sharing mechanism. We propose the creation of a members-only sharing club with compensation for net contributors paid for by net receivers. Take-down companies submit real-time copies of their entire feeds to a trusted third party (for the sake of argument, let’s assume that the APWG takes on this role). The APWG collates the individual feeds, marks the source of each submission (i.e., which take-down company) along with a timestamp. The APWG makes the amalgamated feed available immediately to all members. The members pick out phishing URLs impersonating their own clients, while ignoring the rest. Crucially, the expensive task of verifying phishing URLs and initiating take-down continues to be performed by the take-down company.

Periodically, the combined feed is audited to determine the reciprocity of contributions. Take-down companies provide a list of their clients to the auditor. The auditor then computes the number of phishing websites impersonating each take-down company’s clients that are missed by the takedown company but identified by others. The auditor also tallies the time difference for phishing websites that are identified by others first.

For example, suppose bank A1 has hired take-down company A to remove phishing sites on its behalf, and bank B1 has hired take-down company B. Suppose 500 phishing sites impersonate A1, and that A identifies 400 while B identifies an additional 100 sites missed by A. Likewise, suppose another 500 phishing sites impersonate bank B1, and that B identifies 300 while A identifies an additional 200 sites missed by B. B has received a net of 100 useful phishing sites more from A than B has given to A. Consequently, B should pay A a previously-agreed ‘finder’s fee’ for identifying these extra 100 websites.

The ‘finder’s fee’ provides additional incentive for take-down companies to invest in better phishing website detection. Designed properly, such a sharing club can overcome the potential for free-riding that companies such as Cyveillance fret about, while increasing sharing to shorten phishing website lifetimes.

Some subtleties must be mentioned, however. If the finder’s fee is big enough, some companies may be tempted to cheat to minimize their payout. For instance, underperforming take-down companies could claim to have independently discovered missing data from their feed shortly after collecting it from the shared feed. This can be mitigated by adding a credible threat of detection — inserting a few dubious fake phishing URLs that only appear in the shared feed. If the company claims to have ‘independently’ rediscovered these URLs, then they will be caught cheating. Another issue is that the auditing system does incur some overhead, which could be avoided if sharing was made unconditional.

To sum up, we recognize that many take-down companies will be reticent to share. However, we feel that sharing is too important to the goal of tackling phishing to brush aside because of a few inevitable complications. For the good of protecting consumers, the anti-phishing industry should learn to co-operate!