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.

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.

The good news is that due to the nature of this problem, it is extremely difficult to determine the vulnerability merely by analyzing the patches; a common technique malicious individuals use to figure out security weaknesses.

The typical response I heard was “what do you mean, it can’t be reverse engineered? I’ll just look at the diffs!”

In hindsight, after examining the BIND diffs (yes, I did it too) and discussing with colleagues, all most people saw was UDP source port randomization and a better PRNG for generating the transaction ID, the latter of which would appear to be related to Amit Klein’s cache poisoning attack from about a year ago.

What Rich was really saying is that you can reverse engineer the patch until you’re blue in the face, but that won’t reveal the specifics of the vulnerability.

Dan’s blog post this morning appeared to confirm that interpretation:

DJB was right. All those years ago, Dan J. Bernstein was right: Source Port Randomization should be standard on every name server in production use.

There is a fantastic quote that guides a lot of the work I do: Luck is the residue of design. Dan Bernstein is a notably lucky programmer, and that’s no accident. The professor lives and breathes systems engineering in a way that my hackish code aspires to one day experience. DJB got “lucky” here — he ended up defending himself against an attack he almost certainly never encountered.

Such is the mark of excellent design. Excellent design protects you against things you don’t have any information about. And so we are deploying this excellent design to provide no information.

To translate the fix strategy into a more familiar domain, imagine large chunks of Windows RPC went from Anonymous to Authenticated User only, or even all the way to Admin Only. Or wait, just remember Windows XPSP2 :) This is a sledgehammer, by design. It cuts off attack surface, without necessarily saying why. Astonishingly subtle bugs can be easily hidden, or even rendered irrelevant, by a suitably blunt fix.

Nate McFeters appears to think that Tom Ptacek has figured it out. I’m going to go out on a limb and say that Tom didn’t figure anything out yet but still wanted to write a pithy blog post. I think that if Tom had figured it out, he would have written it down privately and posted the SHA-1 hash, as is the trendy thing to do these days.

Speculation aside, the title of Tom’s blog entry, Dan Kaminsky could have made hundreds of thousands of dollars with this DNS flaw!, does make an important point — Dan didn’t sell the details to ZDI, he used his influence and reputation to coordinate a massive vendor patch effort. That’s an admirable move.

(FYI, for the impatient, click here.)

There are two ways to generate random numbers on computers: (1) use a software program called a Pseudorandom Number Generator (PRNG) or (2) use a hardware random number generator. A Pseudorandom Number Generator uses a seed value to generate a sequence of numbers that appear random. The problem is that the same seed generates the same random sequence. The hardware based RNG observes and samples some physical phenomenon which is random, such as cosmic rays, RF noise, etc. (aka Entropy).

RNGs are important in Information Security because they are used to generate encryption keys, salts, etc. Historically, attacking RNGs has proven effective, such as the defeat of Netscape’s HTTPS sessions.

Most operating systems utilize a hybrid approach, implementing a PseudoRandom Number Generator that has a seed that is regularly updated through the collection of random hardware events. This process is called Entropy Collection or Entropy Harvesting. For most applications, this approach should be completely sufficient. However, one of the key assumptions is that the operating system has been up and running long enough for the seed value itself to become hard to predict through the collection of Entropy. Also, many of the Entropy collecting events come from properties of hardware devices, such as the minor variations in hard drive rate of rotation. As such, there are a few circumstances where the OS RNG may not be good enough for strong cryptographic key generation:

• Live Boot CD ( The start state of the RNG may be predictable. )
• Virtualized Hosts ( OS may be dependent on simulated events for randomness. )

( Given the exploding popularity of virtualization, this is an area worthy of research. Stay tuned. )

Design of the Got Entropy Service

Many RNGs (such as the one included in Linux, as well as OpenSSL’s) allow the addition of entropy from outside sources. So I started looking to Entropy sources I could use to bolster the RNGs on my virtual hosts (and other uses…). While I was looking into this, it occurred to me that I had an unused TV tuner card, a PVR-350.

When a TV is tuned to a channel with no local station, the ’snow’ on the screen is RF noise (the same as the static between stations on AM radios). But, for reasons beyond our scope, you never use a direct physical observation as the RNG. You have to ‘de-skew and whiten’ the data prior to sampling it. Here is the process that I use:

1. Collect about 3 minutes of video ( about 130 MB data ).
2. Using a random key and IV, encrypt the data ( using openssl & AES-128-CBC ).
3. Discard the first 32k of the file.
4. Use each of the following 32k blocks as samples.
5. Compress each sample with SHA-256.
6. Discard the last block.

• Steps 2 and 3 remove any patterns, such as MPEG file formatting, from the data.
• Steps 4 and 5 generate a 32-byte random value ( 1024 to 1 compression in the hash ).

Check it out at http://gotentropy.artofinfosec.com

Can an Attacker Broadcast a Signal to Undermine This?

Such an attacker could not remove RF noise from the received signal. Our eyes and brains are good at filtering out the noise in the TV video, but there is a lot of it. Part of the noise comes from the atmospheric background RF, but there are also flaws (noise) in the tuner’s radio and analog-to-digital capture circuitry.

I think this is a pretty strong RNG, and I have provided an interface for pulling just the values.

Also, I have written a script ( getEntropy.sh ) that will pull Entropy from the service and seed it into /dev/random on Linux.

Results from ENT

Here are results, from a sample run of the Got Entropy, analyzed by ENT ( A Pseudorandom Number Sequence Test Program provided by John Walker of www.fourmilab.ch - Thanks, John! ).

• Entropy = 7.999987 bits per byte
• Optimum compression would reduce the size of this 13366112 byte file by 0 percent.
• Chi square distribution for 13366112 samples is 233.85, and randomly would exceed this value 82.48 percent of the time.
• Arithmetic mean value of data bytes is 127.4767 (127.5 = random).
• Monte Carlo value for Pi is 3.143054786 (error = 0.05 percent).
• Serial correlation coefficient is -0.000078 (totally uncorrelated = 0.0).

Resources for the Curious…

• Wikipedia - Pseudo-random Number Generator
• Wikipedia - Hardware Random Number Generator
• NIST - Random Numbers Page
• Netscape RNG Attack
• van Heusden Video Rand

Cheers, Erik

Art of Information Security would love your feedback !

Got Entropy ?

One of the phrases I often hear during vision and strategy planning meetings at Microsoft is "What is the crawl, walk, run?" We use this phrase to differentiate the initial activities that will get us quickly moving toward our larger goals and then supplement them with other activities that may require longer preparation or planning. As I help non-Microsoft companies implement SDL into their development lifecycles, this "crawl" phase toward full adoption of SDL is very important. Usually some person in an organization picks up on the principles of SDL and is ready to roll them out immediately. However, that person usually is faced with competing interests that complicate full adoption: the team is mid-stream in development, short on budget, or management wants to see clear evidence before investing in the changes to support full SDL adoption.

Since we usually focus on how to roll out the full Lifecycle, I want to take a shot at defining what it means to start “crawling” toward SDL. One very important note before I start. What I describe below is not Microsoft’s SDL process. It matches some of the tools and principles, but does not encompass the holistic application security solution provided by SDL.

In my mind, to start crawling toward SDL, you need to execute on some of the core principles. They obviously need to be low-cost and effective. So, I want to summarize these into three components.

1.       Detailed awareness of your architecture and its attack surface.

2.       Tools that will perform security analysis on your application.

3.       Results that show how the analysis resulted in improved security.

The good news is that you can attain these components with tools that are already available. The one consistent minimum requirement is that your code compiles/builds within Visual Studio 2005 SP1. The SP1 piece of this is important because some of the important defenses I discuss below were first made available in that version. Let’s look at some of the tools you can use to get “crawling” toward SDL today:

Detailed awareness of your architecture and its attack surface

Threat Modeling

Even if you are past the design phase, assign someone to do a retrospective model (perhaps as part of a pre-release review). This will likely give you a better understanding of your overall architecture and uncover holes in places you may have inadvertently overlooked.

Tools that will perform security analysis on your application

This is probably one of the most often discussed topics around SDL, so I’ll spend some time providing more detail. Let’s break this down into how it impacts differing parts of your team or organization: developers, testers, and operation.

Developers

You should start by strengthening your compiler defenses. Depending on whether you are writing native or managed code, these will differ.

For C and C++ code:

Strengthen your compiler defenses

·         Use the latest compiler and linker because important defenses are added by the tools

·         If using Visual C++,  use Visual Studio 2005 SP1 or later

·         Compile with appropriate compiler flags

·         Compile clean at the highest possible warning level

·         Compile with –GS to detect stack-based buffer overruns

·         Link with appropriate linker flags: /NXCompat to get NX defenses, /DynamicBase to get ASLR,  and /SafeSEH to get exception handler protections

Do not use banned APIs in new code

·         Use #include “banned.h” header file to find banned C/C++ functions in your code quickly. This header file is included in the companion disk in the Security Development Lifecycle book.

·         Compile regularly with /W4 and fix all C4996 (banned C Runtime function) warnings

For all Languages:

Strengthen your compiler defenses

·         Use the latest compiler, linker and libraries because defenses are added by the tools and code

o   If using C#, use  C# v2.0 or later and if using VB.Net use 8.0 or later

·         Use .NET Framework 2.0 or later

·         Do not use weak crypto in new code

o   Use only AES, RSA and SHA-256 (or better)

·         Prevent XSS vulnerabilities by using filtering and escaping libraries around all Web output

·         Secure your SQL script by only using prepared SQL statements - no string concatenation or string replacement

Run these tools habitually

·         PREfast (in Visual Studio 2005, use the /analyze compiler option) – a static analysis tool that identifies defects in C/C++ programs and enables you to perform quick desktop error detection on small code bases

·         FxCop – an application that analyzes managed code assemblies (code that targets the .NET Framework common language runtime) and reports information about the assemblies

·         Application Verifier (AppVerif) – detect and help debug memory corruptions, critical security vulnerabilities, and limited user account privilege issues.

Testers

James Whittaker has covered testing in the SDL on this blog in the past. In a “crawl” scenario, you need to keep it simple while maximizing the value of output. I would recommend focusing on fuzz testing. This is likely something you will need to invest some time creating.  Scott Lambert’s article on Fuzz Testing at Microsoft and the Triage Process provides some good guidance on how to think through what type(s) of fuzzing to exercise against your application.

If you choose to expand beyond fuzz testing, I would point you back to James’ article on the broader topic of Testing in SDL. You may come to the conclusion that expanded security testing  may come later in your “walk” or “run” phases, but I would take some time to think through testing even while “crawling” to ensure you are getting broad enough coverage for your application. James’ article highlights the three-pronged approach to security testing we use at Microsoft. You should use these three approaches to ensure your own fuzz testing is comprehensive.

1.       Attacks against the application’s environment.

2.       Direct attacks against the application itself.

3.       Indirect attacks against the application’s functionality.

Results that show how the analysis resulted in improved security

Response planning

Protecting your customers is the entire reason for focusing energy on application security.  If there are holes in your code that you don’t uncover, someone else will. It is absolutely critical that you are prepared to respond rapidly and protect your customers. It is equally important that you construct your  response plan to serve as a front-line barometer for detecting the resilience of your security design  and what pieces of your applications security should be proactively bolstered to  address externally reported vulnerabilities.  The knowledge you harvest from these security incidents (typically through root cause analysis) is the primary way to improve your code and security tooling for the future.  Do everything you can to learn lessons from the vulnerabilities others find. If you don’t have a response plan in place, you need to get one in place as soon as possible. If you don’t know where to start, take a look at how our own Microsoft Security Response Center does it and fit to your scale or pick up the Security Development Lifecycle book and dig into the four-step process outlined.

The four steps of the emergency response process:

1.       Watch

2.       Alert and Mobilize

3.       Assess and Stabilize

4.       Resolve

Bugs, Bugs, Bugs

Gathering evidence that clearly shows your work has improved the security of your application is always a challenge. Trying to keep it lightweight adds to that challenge. The most effective way to create traceable and practical evidence without a lot of overhead is detailed management of security issues in your bug database.  The key here is that your bug database is configurable and able to be queried in a variety of ways to pull out this data. From the time you set out to implement this plan, be strict in tracking every discovery from threat modeling, the mitigations to those threats, and every bug you expose in tool analysis. This library of security bugs will give you an easy way to go back and gather evidence that shows the quantity of issues you discovered, the mitigations you used, and the impact the changes had on your application.

I have provided a fairly detailed view of these components. As I indicated, many of these defenses are available for you in Visual Studio 2005 SP1 or various linked resources above. If you are unsure whether you are taking advantage of all available defenses in your development tools, take the time to check.

It is my hope that some of you can use this scaled back entry into the principles of SDL to get moving toward improved security assurance. In the non-Microsoft SDL engagements I have been involved in, we have seen these steps effectively establish a baseline architectural understanding of your application security and identify critical weaknesses while providing solid evidence to support the decision to “run” forward into full SDL adoption.

[I want to thank Michael Howard for providing some of the key data for the Developer pieces in this article.]

We interrupt our regular schedule of blog postings to offer this special post for “Super Tuesday” given the subject matter. Hope you enjoy…

This year is a presidential election year in the United States. Selecting a new president is perhaps the ultimate example of the importance of having a trustworthy election process. There have been some well chronicled examples of elections with extremely close results, where the winner’s margin of victory was perhaps smaller than the election system’s margin of error. The term “Hanging Chads,” from the 2000 U.S Presidential election, is now part of the American vocabulary, and locally here in Washington State our last gubernatorial election in 2004 required 3 recounts with the final winner being determined by a margin of only 129 votes, or 0.0045% of the popular vote.

The populace demands confidence that, even in close elections, the election result accurately reflects the voters’ intent. In theory, such precision can be improved by using computers and technology.

However, it seems that every recent election season brings stories in the media about security concerns regarding voting machine (and their software) security. A recent New York Times article provides a good overview of voting machine security concerns; and academic studies on voting systems last year in California, Connecticut, Florida, and Ohio  provide some interesting insights about security concerns and vulnerabilities in voting systems from several vendors.

These analyses are fascinating to us, because they offer an opportunity to see how a set of experts look at products other than ours.  Applied security researchers often analyze our products, and often share their processes and tools with us, but it’s rare to see a top-to-bottom product review released.  In California, there was both white and black box testing done by different teams, and we’ve studied these reports to see the perceptions of development practices from other vendors and results of a different type of review process.

Something my colleagues and I find very interesting is that many of the vulnerabilities noted in these reports could have been prevented by following the requirements in Microsoft’s Security Development Lifecycle. The studies performed in California (prepared at UC Berkeley but created by teams of academics from across the United States) included detailed source code analysis. I’ll select out a few examples from those studies and describe them here. (Note: I’m deliberately picking a few examples from each vendor assessed in the study. I am not attempting to criticize any specific vendor, but rather am trying to illustrate examples of areas where application of the SDL could help contribute towards society’s need for trustworthy computing in a very visible and important application.)

Let’s start with the Source Code Review of the Sequoia Voting System. Two examples from the executive summary are interesting:

“Cryptography. …Many cryptographic functions are implemented incorrectly, based on weak algorithms with known flaws, or used in an ineffective or insecure manner. Of particular concern is the fact that virtually all cryptographic key material is permanently hardcoded in the system (and is apparently identical in all Sequoia hardware shipped to different jurisdictions)…

Software Engineering. …The software suffers from numerous programming errors, many of which have a high potential to introduce or exacerbate security weaknesses. These include buffer overflows, format string vulnerabilities, and type mismatch errors….”

A deeper reading of the cryptographic concerns (page 29 in report) notes concerns (amongst others) over the use of a flawed implementation of the SHA hash algorithm and use of the Data Encryption Standard (DES) algorithm. The SDL has specific policies outlining appropriate selection of cryptographic algorithms.  For example, DES is prohibited except for backwards compatibility. SDL also requires that applications use operating system cryptographic functions and libraries. The cryptography team in the operating systems group is supported by world-class cryptographers who carefully scrutinize the implementation of crypto algorithms, and additionally these operating system functions are formally reviewed and certified by the National Institute of Standards and Technology (NIST) Cryptographic Module Validation Program (CMVP) who validates cryptographic modules meet Federal Information Processing Standards (FIPS). Most application developers are not cryptographers and hence are unlikely to encode crypto algorithms correctly. The SDL requires the use of standard crypto functions and outlines requirements on algorithm selection, key length and key management.

Moving to the software engineering concerns; while several common coding and design concerns are noted (e.g. input validation) I want to select one with a bit more subtlety: running code from USB sticks (page 37 in report). From the report, it appears the code present on the USB sticks is used to program a component (HAAT) of their client (WinEDS) to prepare for a specific election.  The valid concern noted by the study is that USB sticks used by WinEDS to configure the HAAT are implicitly trusted to have appropriate authorization to program the voting devices for an election, and that a formal authorization framework didn’t appear to be present. The implication being (as stated in the report): “If such a stick is used in a HAAT that has been compromised by an attacker, or an attacker can provide a maliciously modified USB stick in place of a legitimate one, the attacker could surreptitiously take complete control over the WinEDS client”. Basically, this is a potential “rootkit” for election systems. A threat model, a fundamental design requirement of the SDL, could help uncover such design issues and illustrate the need for mitigations.

Now, let’s turn to the Source Code Review of the Hart InterCivic Voting System. I’ll try to keep my commentary balanced by selecting two examples here as well:

From the executive summary:

“Unsecured network interfaces … Voters can connect to unsecured network links in a polling place to subvert eSlates, as well as to eavesdrop on cast votes and to inject new votes. Poll workers can connect to JBCs or eScans over the management interfaces and perform back-office functions such as modifying the device software. The impact of this is that a malicious voter could potentially take over one or more eSlates in a precinct and a malicious poll worker could potentially take over all the devices in a precinct. …

Failure to protect ballot secrecy Hart’s system fails to adequately protect ballot secrecy...”

The concerns about unsecured network interfaces are discussed in the context of authentication and least privilege (pages 24-25). While that is certainly a reasonable perspective, with the SDL we take a broader view and require all teams to threat model the attack surface of the software being developed. Attack surface is the enumeration of all possible entry points that an attacker could use to compromise software (code listening to network interfaces, code that accepts data from external sources, etc). The SDL requires development teams to both minimize attack surface in the software they are building and to consider attacks from each entry point on the attack surface to ensure that mitigations are present. It would appear that these examples show that the development teams didn’t adopt such a systematic approach, or failed to think about mitigations of each possible attack if they did.

Ballot secrecy is an example where security and privacy concerns intersect. Many people confuse security and privacy, and both are fundamental to trust. Privacy addresses a wide variety of concerns about many types of data (such as Personally Identifiable Data (PII), ballot data, etc.), how it’s handled (gathered, transmitted, stored, and disposed of) and what rights and expectations different stakeholders may have regarding that data. (Tina Knutson gave a great overview on these issues in a previous blog posting “Privacy is not just about data security“). Security provides the mechanisms, policies, and practices to enforce privacy requirements. Given the intertwined nature of these issues, both are addressed in the SDL.

The concerns about vote storage (section 6.8, page 58 of report) review some classic challenges in software security and privacy with weak random number generation. Randomization is important here since it controls how votes are stored in memory, and weak randomization enables someone to reverse engineer how individual voters voted by examining the aggregate tally of votes (which can be found on the Mobile Ballot Boxes “MBB”) in conjunction with the audit log. The MBB has mitigations in place to protect integrity (tampering) of votes, but doesn’t appear to protect against information disclosure. The SDL cryptographic policies also cover correct random number generation. The challenge of fully considering all ways in which data can be reverse engineered, contextualized (order of log entries providing information that can be linked to individuals’ choices), and correlated with other data sources is a growing challenge. In the SDL privacy policies, we call attention to these issues, but it’s still a challenge.

Next, let’s look at the Source Code Review of the Diebold Voting System. Again, I’ll pick two subjects.

“Vulnerability to malicious software: The Diebold software contains vulnerabilities that could allow an attacker to install malicious software on voting machines or on the election management system…

Vulnerability to malicious insiders: The Diebold system lacks adequate controls to ensure that county workers with access to the GEMS central election management system do not exceed their authority….”

Let’s look at the “Malicious Software” first: While there’s a lot of discussion of general concerns with viruses and malicious payloads, I’d like to drill down on a specific case noted in section 4.2.3 (page 29). The typical concerns around string handling in C/C++ and buffer overflows are mentioned. What is interesting is that in many places this system uses the Microsoft Foundation Classes (MFC) CString class to help mitigate such concerns. The problem noted is that this practice is not consistently followed, and in fact there is a case of one specific function making calls to both CString *and* a standard C string library, in the same function. So here it appears the engineering team had the right idea by trying to remove calls to potentially risky C string library functions (just as required in SDL), but they just weren’t able to consistently and completely apply it.

Regarding the executive summary concern about malicious insiders, I’m inclined to attribute it to what’s described in section 4.3 on page 30: “No formal threat model or security plan” and “No formal security training”. Both of these are pivotal elements in the SDL. Several comments are offered to the effect that “security measures that are in place appeared to be ad hoc”, and “When new developers arrive at the company, they do not receive any kind of security training”. We’ve blogged here in the past about the importance of both areas, so I won’t repeat that again. (See Adam’s Threat Modeling series and Dave’s “Security Education v. Security Training” posts respectively for more info).

Is the SDL enough to ensure trustworthy voting systems?

When I offered this blog post for the review of my colleagues, it generated some very interesting discussion. Some of my colleagues were worried that I would misrepresent the SDL as a panacea for creating perfectly trustworthy voting systems. Let me be clear: this is absolutely NOT the case. While the SDL could help mitigate repeating many of the problems identified in these studies, it’s worth noting that election systems have a number of unusual and unique requirements. For example, voters cannot review their voting records as they would their banking records to ensure that no fraud has been committed – since the ability to do so would typically enable vote-selling and coercion.  Alternate techniques are therefore required to allow voters to verify that their votes have been properly counted. Such requirements force the adoption of “extraordinary” techniques that go beyond those of secure software engineering.  Furthermore, the expectations of society on the trustworthiness of voting systems are much greater as compared to other types of software (for example: the latest XBOX game title). I’ll further explore differences in how different people think about “degrees of trustworthiness” (aka “assurance” or “robustness”) in a future posting.

Summary

Let me wrap by saying this, building secure software is difficult. Prior to the advent of Trustworthy Computing and the Security Development Lifecycle here at Microsoft, I’d bet that many of the issues noted in these reports would have applied to earlier Microsoft products too. Some might think I’m throwing stones while living in a glass house, but that is not my intent. While Microsoft products are not vulnerability free, we continue to systematically analyze the sources of vulnerabilities in our software. We continue to modify our engineering practices and tools to better identify potential vulnerabilities and mitigate them before software is released. With increasing awareness and concerns over the trustworthiness of computers in general, the entire industry needs to improve. Given the importance of how we choose to organize ourselves as a society and elect representatives to govern us, voting systems are a great place to step up both in the context of the computing industry, and to better serve society.

I believe many of the issues found in these voting systems would not have entered the system if the SDL was used to design and build the voting systems.

Since the SVN repository remained intact, we can’t go back and examine the backdoor in detail. However, we do have a newsgroup posting that sheds a little light on the situation:

> What diff do you see between the compromised version and
> the one that is there now? I see only a comment diff in one file.

it was a small block of code that checks for a $_SERVER var. If that var was present, it would redefine SM_PATH. Under normal circumstances, this would never be executed, but we have since learned how to make it execute.

In PHP, $_SERVER is an array populated by the web server that contains information such as headers, paths, and script locations. This includes some user-supplied input such as the URL query string and the HTTP headers. SM_PATH is the filesystem path where SquirrelMail is configured to be run from. So once an attacker controls SM_PATH, it’s likely that a subsequent call to include() can be exploited to fetch and execute PHP code from a remote server. This is a typical example of a Remote File Include vulnerability.

Note that the attacker backdoored the 1.5.1 distribution as well, with the same type of vulnerability but at a different location in the codebase.

I think what’s most interesting to me about this is that so many open source projects still rely on MD5 hashes for integrity checking. The minute the Xiaoyun Wang paper on MD5 collisions was released, every security practitioner in the world considered MD5 unsafe from that point forward. Even though practical attacks had not yet been formulated, the writing was on the wall. Unfortunately, the rest of the world either didn’t notice or didn’t care.

Cryptographers have since developed increasingly sophisticated attacks stemming from Wang’s original work. Recently, researchers in the Netherlands demonstrated two examples of chosen-prefix attacks which would make it possible for an attacker to take two tarballs (one original, one backdoored) and append a series of bytes to each that result in both files having the same MD5 hash. This proves beyond a shadow of a doubt that MD5 is not an effective method for verifying software integrity. There was hardly any doubt that this attack would surface eventually, so why is MD5 still in such widespread usage?

Cryptographic weaknesses aside, a lot of people completely miss the mark with hashes. MD5 or SHA-1 (or any hash function) are not very effective if the only way a user can verify them is on the same website where the download is hosted. If the download point is compromised, chances are the attacker can modify the hashes printed on the website too. Even when it’s done correctly, hashes only help identify when the distribution point is compromised. It does nothing to protect against source code compromise or vulnerabilities in the development tool chain.