Tonight is the “rump session” at the Crypto conference, where researchers can give informal short presentations on up-to-the-minute results.

Biham and Chen have a presentation scheduled, entitled “New Results on SHA-0 and SHA-1”. If there’s an SHA-1 collision announced, they’ll probably be the ones to do it.

Antoine Joux will present his SHA-0 collision. Also the authors of the slightly flawed paper claiming an MD5 collision have a presentation; it seems likely they’ll announce that they’ve fixed their bug and have a collision in MD5.

Each group has been given fifteen minutes, which is a significant departure from the normal five minutes allocated for rump session talks.

The session is tonight; I’ll give you an update as soon as I hear what happened. It will be webcast at 7PM Pacific time, tonight.

I wish I could be there, but I’m on the wrong coast. Anybody who is at Crypto is invited to post updates in the comments section of this post.

Following up on yesterday’s discussion about new attacks on cryptographic hashfunctions, Eric Rescorla points to a new paper from Chinese computer scientists, which claims to have found a collision in MD5. MD5 is a cousin of the SHA-1 function discussed yesterday; MD5 is believed to be the weaker of the two.

The paper is odd, in that it includes two values that it claims have the same MD5 value, but it doesn’t explain how the claimed collision was generated. And it turns out that the authors made an error, so that the two values don’t in fact generate the same MD5 value. Eric and the commenters on his site did some clever detective work to determine that the two published values generate a collision for a slightly different function, which Eric dubbed MD5′. MD5′ is very similar to MD5 so it seems very likely that the new attack can be extended to the real MD5.

There’s a rumor circulating at the Crypto conference, which is being held this week in Santa Barbara, that somebody is about to announce a partial break of the SHA-1 cryptographic hashfunction. If true, this will have a big impact, as I’ll describe below. And if it’s not true, it will have helped me trick you into learning a little bit about cryptography. So read on….

SHA-1 is the most popular cryptographic hashfunction (CHF). A CHF is a mathematical operation which, roughly speaking, takes a pile of data and computes a fixed size “digest” of that data. To be cryptographically sound, a CHF should have two main properties. (1) Given a digest, it must be essentially impossible to figure out what data generated that digest. (2) It must be essentially impossible to find find a “collision”, that is, to find two different data values that have the same digest.

CHFs are used all over the place. They’re used in most popular cryptographic protocols, including the ones used to secure email and secure web connections. They appear in digital signature protocols that are used in e-commerce applications. Since SHA-1 is the most popular CHF, and the other popular ones are weaker cousins of SHA-1, a break of SHA-1 would be pretty troublesome. For example, it would cast doubt on digital signatures, since it might allow an adversary to cut somebody’s signature off one document and paste it (undetectably) onto another document.

At the Crypto conference, Biham and Chen have a paper showing how to find near-collisions in SHA-0, a slightly less secure variant of SHA-1. On Thursday, Antoine Joux announced an actual /msg02554.html">collision for SHA-0. And now the rumor is that somebody has extended Joux’s method to find a collision in SHA-1. If true, this would mean that the SHA-1 function, which is widely used, does not have the cryptographic properties that it is supposed to have.

The finding of a single collision in SHA-1 would not, by itself, cause much trouble, since one arbitrary collision won’t do an attacker much good in practice. But history tells us that such discoveries are usually followed by a series of bigger discoveries that widen the breach, to the point that the broken primitive becomes unusable. A collision in SHA-1 would cast doubt over the future viability of any system that relies on SHA-1; and as I’ve explained, that’s a lot of systems. If SHA-1 is completely broken, the result would be significant confusion, reengineering of many systems, and incompatibility between new (patched) systems and old.

We’ll probably know within a few days whether the rumor of the finding a collision in SHA-1 is correct.

Lots of people are telling airport-security stories these days. Thus far I have refrained from doing so, even though I travel a lot, because I think the TSA security screeners generally do a good job. But last week I saw something so dumb that I just have to share it.

I’m in the security-checkpoint line at Boston’s Logan airport. In front of me is an All-American family of five, Mom, Dad, and three young children, obviously headed somewhere hot and sunny. They have the usual assortment of backpacks and carry-on bags.

When they get through the metal detector, they’re told that Mom and Dad had been pre-designated for the more intensive search, where they wand-scan you and go through your bags. This search is a classic example of what Bruce Schneier calls Security Theater, since it looks impressive but doesn’t do much good. The reason it doesn’t do much good is that it’s easy to tell in advance whether you’re going to be searched. At one major airport, for example, the check-in agent writes a large red “S” on your boarding pass if you’re designated for this search; you don’t have to be a rocket scientist to know what this means. So only clueless bad guys will be searched, and groups of bad guys will be able to transfer any contraband into the bags of group members who won’t be searched, with plenty of time after the security checkpoint to redistribute it as desired.

But back to my story. Mom and Dad have been designated for search, and the kids have not. So the security screener points to the family’s pile of bags and asks which of the bags belong to Mom and Dad, because those are the ones that he is going to search. That’s right: he asks the suspected bad guys (and they must be suspected, otherwise why search them) which of their bags they would like to have searched. Mom is stunned, wondering if the screener can possibly be asking what she thinks he’s asking. I can see her scheming, wondering whether to answer honestly and have some stranger paw through her purse, or to point instead to little Johnny’s bag of toys.

Eventually she answers, probably honestly, and the screener makes a great show of diligence in his search. Security theater, indeed.

Yesterday the USENIX Conference featured a debate between Dan Geer and Scott Charney about whether operating-system monoculture is a threat to computer security. (Dan Geer is a prominent security expert who co-wrote last year’s CCIA report on the monoculture program, and was famously fired by @Stake for doing so. Scott Charney was previously a cybercrime prosecutor, and is now Microsoft’s Chief Security Strategist.)

Geer went first, making his case for the dangers of monoculture. He relied heavily on an analogy to biology, arguing that just as genetic diversity helps a population resist predators and epidemics, diversity in operating systems would help the population of computers resist security attacks. The bio metaphor has some power, but I thought Geer relied on it too heavily, and that he would have been better off talking more about computers.

Charney went second, and he made two main arguments. First, he said that we already have more diversity than most people think, even within the world of Windows. Second, he said that the remedy that Geer suggests – adding a modest level of additional diversity, say adopting two major PC operating systems with a 50/50 market share split – would do little good. The bad guys would just learn how to carry out cross-platform attacks; or perhaps they wouldn’t even bother with that, since an attack can take the whole network offline without penetrating a large fraction of machines. (For example, the Slammer attack caused great dislocation despite affecting less than 0.2% of machines on the net.) The bottom line, Charney said, is that increasing diversity would be very expensive but would provide little benefit.

A Q&A session followed, in which the principals clarified their positions but no major points were scored. Closing statements recapped the main arguments.

The moderator, Avi Rubin, polled the audience both before and after the debate, asking how many people agreed with each party’s position. For this pupose, Avi asked both Geer and Charney to state their positions in a single sentence. Geer’s position was that monoculture is a danger to security. Charney’s position was that the remedy suggested by Geer and his allies would do little if anything to make us more secure.

Pre-debate, most people raised their hands to agree with Geer, and only a few hands went up for Charney. Post-debate, Geer got fewer hands than before and Charney got more; but Geer still had a very clear majority.

I would attribute the shift in views to two factors. First, though Geer is very eloquent for a computer scientist, Charney, as an ex-prosecutor, is more skilled at this kind of formalized debate. Second, the audience was more familiar with Geer’s arguments beforehand, while some may have been hearing Charney’s arguments for the first time; so Charney’s arguments had more impact.

Although I learned some things from the debate, my overall position didn’t change. I raised my hand for both propositions, both pre- and post-debate. Geer is right that monoculture raises security dangers. Charney is also right that the critics of monoculture don’t offer compelling remedies.

This is not to say that the current level of concentration in the OS market is optimal from a security standpoint. There is no doubt that we would be more secure if our systems were more diverse. The most important step toward diversity would be to ensure true competition in software markets. Consumers have an incentive to switch to less-prevalent technologies in order to avoid being attacked. (See, e.g., Paul Boutin’s endorsement in Slate of the Mozilla Firefox browser.) In a properly functioning market, I suspect that the diversity problem would take care of itself.

(See also my previous discussion of the monoculture issue.)