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.

Since the election, the newspapers and Internet have been flooded with unsolicited advice for President-elect Barack Obama. I'll go ahead and add mine.

[...]

And by "revamp," I mean "start over." Most security experts agree that the rigmarole we go through at the airport is mere security theater, designed not to make us safer, but to make us feel safer by making it increasingly inconvenient to fly. TSA's approach to security is too reactionary -- too set on preventing attacks and attempted attacks that have already happened. And please, whatever you do, resist the temptation to let TSA workers unionize. Security from terror attacks should be a federal jobs program. You need the authority to fire underperforming screeners quickly and effortlessly. Three game-changing possibilities to head up TSA: security guru Bruce Schneier, Cato Institute security and technology scholar Jim Harper, or Ohio State University's John Mueller.

Although I'd be happy to see either Jim or John with it.

I don't want it because it's too narrow. I think the right thing for the government to do is to give the TSA a lot less money. I'd rather they defend against the broad threat of terrorism than focus on the narrow threat of airplane terrorism, and I'd rather they defend against the myriad of threats that face our society than focus on the singular threat of terrorism. But the head of the TSA can't have those opinions; he has to take the money he's given and perform the specific function he's assigned to perform. Not very much fun, really.

But I'd be happy to advise whoever Obama choses to head the TSA.

The job of the nation's CTO would be more interesting, but I don't think I want it, either. (Have you seen the screening process?)

District Court Holds that Running Hash Values on Computer Is A Search: The case is United States v. Crist, 2008 WL 4682806 (M.D.Pa. October 22 2008) (Kane, C.J.). It's a child pornography case involving a warrantless search that raises a very interesting and important question of first impression: Is running a hash a Fourth Amendment search? (For background on what a "hash" is and why it matters, see here).

First, the facts. Crist is behind on his rent payments, and his landlord starts to evict him by hiring Sell to remove Crist's belongings and throw them away. Sell comes a cross Crist's computer, and he hands over the computer to his friend Hipple who he knows is looking for a computer. Hipple starts to look through the files, and he comes across child pornography: Hipple freaks out and calls the police. The police then conduct a warrantless forensic examination of the computer:

In the forensic examination, Agent Buckwash used the following procedure. First, Agent Buckwash created an "MD5 hash value" of Crist's hard drive. An MD5 hash value is a unique alphanumeric representation of the data, a sort of "fingerprint" or "digital DNA." When creating the hash value, Agent Buckwash used a "software write protect" in order to ensure that "nothing can be written to that hard drive." Supp. Tr. 88. Next, he ran a virus scan, during which he identified three relatively innocuous viruses. After that, he created an "image," or exact copy, of all the data on Crist's hard drive.

Agent Buckwash then opened up the image (not the actual hard drive) in a software program called EnCase, which is the principal tool in the analysis. He explained that EnCase does not access the hard drive in the traditional manner, i.e., through the computer's operating system. Rather, EnCase "reads the hard drive itself." Supp. Tr. 102. In other words, it reads every file-bit by bit, cluster by cluster-and creates a index of the files contained on the hard drive. EnCase can, therefore, bypass user-defined passwords, "break down complex file structures for examination," and recover "deleted" files as long as those files have not been written over. Supp. Tr. 102-03.

Once in EnCase, Agent Buckwash ran a "hash value and signature analysis on all of the files on the hard drive." Supp. Tr. 89. In doing so, he was able to "ingerprint" each file in the computer. Once he generated hash values of the files, he compared those hash values to the hash values of files that are known or suspected to contain child pornography. Agent Buckwash discovered five videos containing known child pornography. Attachment 5. He discovered 171 videos containing suspected child pornography.

One of the interesting questions here is whether the search that resulted was within the scope of Hipple's private search; different courts have approached this question differently. But for now the most interesting question is whether running the hash was a Fourth Amendment search. The Court concluded that it was, and that the evidence of child pornography discovered had to be suppressed:

The Government argues that no search occurred in running the EnCase program because the agents "didn't look at any files, they simply accessed the computer." 2d Supp. Tr. 16. The Court rejects this view and finds that the "running of hash values" is a search protected by the Fourth Amendment.

Computers are composed of many compartments, among them a "hard drive," which in turn is composed of many "platters," or disks. To derive the hash values of Crist's computer, the Government physically removed the hard drive from the computer, created a duplicate image of the hard drive without physically invading it, and applied the EnCase program to each compartment, disk, file, folder, and bit.2d Supp. Tr. 18-19. By subjecting the entire computer to a hash value analysis-every file, internet history, picture, and "buddy list" became available for Government review. Such examination constitutes a search.

I think this is generally a correct result: See my article Searches and Seizures in a Digital World, 119 Harv. L. Rev. 531 (2005), for the details. Still, given the lack of analysis here it's somewhat hard to know what to make of the decision. Which stage was the search — the creating the duplicate? The running of the hash? It's not really clear. I don't think it matters very much to this case, because the agent who got the positive hit on the hashes didn't then get a warrant. Instead, he immediately switched over to the EnCase "gallery view" function to see the images, which seems to be to be undoudtedly a search. Still, it's a really interesting question.

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.

No doubt you are aware of the out-of-band security bulletin issued by the Microsoft Security Response Center today, and like all security vulnerabilities, this is a vulnerability we can learn from and, if necessary, can use to shape future versions of the Security Development Lifecycle (SDL).

Before I get into some of the details, it's important to understand that the SDL is designed as a multi-pronged security process to help systemically reduce security vulnerabilities. In theory, if one facet of the SDL process fails to prevent or catch a bug, then some other facet should prevent or catch the bug. The SDL also mandates the use of security defenses, because we know full well that the SDL process will never catch all security bugs. As we have said many times, the goal of the SDL is to "Reduce vulnerabilities, and reduce the severity of what's missed."

In this post, I want to focus on the SDL-required code analysis, code review, fuzzing and compiler and operating system defenses and how they fared.

Code Analysis and Review

I want to start by analyzing the code to understand why we did not find this bug through manual code review nor through the use of our static analysis tools. First, the code in question is reasonably complex code to canonicalize path names; for example, strip out ‘..' characters and such to arrive at the simplest possible directory name. The bug is a stack-based buffer overflow inside a loop; finding buffer overruns in loops, especially complex loops, is difficult to detect with a high degree of probability without producing many false positives. At a later date I will publish more of the source code for the function.

The loop inside the function walks along an incoming string to determine if a character in the path might be a dot, dot-dot, slash or backslash and if it is then applies canonicalization algorithms.

The irony of the bug is it occurs while calling a bounded function call:

_tcscpy_s(previousLastSlash, pBufferEnd - previousLastSlash, ptr + 2);

This function is a macro that expands to wcscpy_s(dest, len, source); technically, the bug is not in the call to wcscpy_s, but it's in the way the arguments are calculated. As I alluded to, all three arguments are highly dynamic and constantly updated within the while() loop. There is a great deal of pointer arithmetic in this loop. Without going into all the gory attack details, given a specific path, and after the while() loop has been passed through a few times, the pointer, previousLastSlash, gets clobbered.

In my opinion, hand reviewing this code and successfully finding this bug would require a great deal of skill and luck. So what about tools?  It's very difficult to design an algorithm which can analyze C or C++ code for these sorts of errors.  The possible variable states grows very, very quickly.  It's even more difficult to take such algorithms and scale them to non-trivial code bases. This is made more complex as the function accepts a highly variable argument, it's not like the argument is the value 1, 2 or 3! Our present toolset does not catch this bug.

Ok, now I'm really going out on a limb with this next section.

Over the last year or so I've noticed that the security vulnerabilities across Microsoft, but most noticeably in Windows have become bugs of a class I call "onesey - twosies" in other words, one-off bugs. There is a good side and a bad side to this. First the good news; I think perhaps we have removed a good number of the low-hanging security vulnerabilities from many of our products, especially the newer code. The bad news is, we'll continue to have vulnerabilities because you cannot train a developer to hunt for unique bugs, and creating tools to find such bugs is also hard to do without incurring an incredible volume of false positives. With all that said, I will add detail about one-off bugs to our internal education; I think it's important to make people aware that even with great tools and great security-savvy engineers, there are still bugs that are very hard to find.

Fuzz Testing

I'll be blunt; our fuzz tests did not catch this and they should have. So we are going back to our fuzzing algorithms and libraries to update them accordingly. For what it's worth, we constantly update our fuzz testing heuristics and rules, so this bug is not unique.

Defenses

If you want the full details of the defenses, and how they come into play on Windows Vista and Windows Server 2008, I urge you to read teh SVRD team's in-depth analysis once it is posted.

A big focus of the SDL is to define and require defenses because we have no allusions about finding or preventing all security vulnerabilities by attempting to get the code right all the time, because no-one can do that. No one.  See my comment above about one-off bugs!

Let's look at each SDL mandated requirement and how they fared in light of this vulnerability.

-GS

The -GS story is not so simple. A lot of code is executed before a cookie check is made and the attacker can control the overflow because the overflow starts at an offset before the stack buffer, rather than at the stack buffer itself. So the attacker can overwrite other frames on the call stack, corresponding to functions that return before a cookie check is made. That's a long way of saying that -GS was not meant to prevent this type of scenarios.

ASLR and NX

The code fully complies with the SDL, and is linked with /DYNAMICBASE and /NXCOMPAT on Windows Vista and Windows Server 2008. There are great defenses when used together, and reduce the chance of a successful attack substantially. Also, the stack offset is randomized too, making a deterministic attack even more unlikely.

Service Restart Policy

By default the affected service is marked to restart only twice after a crash on Windows Vista and Windows Server 2008, which means the attacker has only two attempts to get the attack right. Prior to Windows Vista, the attacker has unlimited attempts because the service restarts indefinitely.

Authentication

Thanks to mandatory integrity control (MIC) settings (which comes courtesy of UAC) the networking endpoint that leads to the vulnerable code requires authentication on Windows Vista and Windows Server 2008 by default. Prior to Windows Vista, the end point is always anonymous, so anyone can attack it, so long as the attacker can traverse the firewall. This is a great example of SDL's focus on attack surface reduction; requiring authentication means the number of attackers that can access the entry point is dramatically reduced.

Firewall

We enabled the firewall by default in Windows XP SP2 and later, this was a direct learning from the Blaster worm. By default, ports 139 and 445 are not opened to the Internet on Windows XP SP2, Windows Vista and Windows Server 2008.

Summary

The $64,000 question we ask ourselves when we issue any bulletin is "did SDL fail?" and the answer in this case is categorically "No!" No because as I said earlier the goal of the SDL is "Reduce vulnerabilities, and reduce the severity of what you miss." Windows Vista and Windows Server 2008 customers are protected by the defenses in the operating system that have been crafted in part by the SDL. The development team who built the affected component compiled and linked with the appropriate settings as described in "Windows Vista ISV Security" and Writing Secure Code for Windows Vista so that their service is protected by the operating system.

The team did not poke holes through the firewall unnecessarily, in accordance with the SDL.

The team reduced their attack surface, in accordance with the SDL, by requiring authenticated connections rather than anonymous connections by default.

We know that the SDL-mandated -GS has very strict heuristics so some functions are not protected by a stack cookie, but in this case, there is no buffer on the stack, so there will be no cookie. We know this. There are no plans to remedy this in the short term.

Fuzzing missed the bug, so we will update our fuzz testing heuristics, but we continually update our fuzzing heuristics anyway.

In short, based on what we know right now, Windows Vista and Windows Server 2008 customers are protected because of the SDL-mandated defenses in the operating system, and because the development team adhered to the letter of the SDL to take advantage of those defenses.

Chalk one up for Windows Vista and later and the SDL!

As usual, questions and comments are very welcome.

This requirement was put in place to prevent use of certain older C runtime functions that lead to buffer overrun flaws and have been deprecated. In the Security Development Lifecycle book, an entire chapter is dedicated to the topic of banned function calls. In the book, we also provide a copy of the banned.h header file on the companion CD. This header file allows you to locate any banned functions in your code.

On MSDN, we have document the SDL list of Banned Function Calls, but the header file has not been publicly available outside the SDL book until now. Today, we are providing the banned.h header on the Microsoft Download Center.

Find the banned.h header here

By including this header file, then using #include “banned.h”; you will be able to locate any banned functions in your code. The full list of banned APIs is also included in the header file.

Alternately, if you are using the compiler in Visual Studio 2005 or later, you have a built-in way to check for these banned functions. To catch banned C runtime functions, you can compile with /W4 and then triage all C4996 warnings. In code reviews, you should always remove any code that disables the C4996 warnings - e.g.: #pragma warning(disable:4996). This is one simple way to ensure your code is released without banned functions.

Sanitizing your code to remove potentially insecure APIs is a vital protection. Whether you include the banned.h header file or leverage the /W4-C4996 warnings in the Visual Studio 2005 compiler, you now have two ways to check your code and meet another SDL requirement in your development phase.