November 28, 2024

MD5 Collision Nearly Found

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.

SHA-1 Break Rumored

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.

DVD Jon Strikes Again

Jon Johansen, known widely as “DVD Jon” for his work on DVD decryption utilities, has released a tool that lets anyone stream music to the Apple Airport Express.

The Airport Express is a slick little gizmo that plugs into any electrical outlet, and can receive content wirelessly and output it on standard connectors to a printer, stereo speakers, audio components, or network. But Apple designed the Airport Express so that it would only accept audio content that was encrypted with a certain encryption key.

It appears that DVD Jon reverse engineered Apple’s encryption mechanism to learn the encryption key. Now he has published the key, along with software code for a tool that streams music to the Apple device.

It will be interesting to see the reaction to this. As far as I can see, copyright isn’t an issue here, since the new software tool only allows people to play music they already have, and the law does not grant copyright owners the exclusive right to control private playing of music.

Perhaps Apple would have preferred that this had not occurred. But I don’t see any compelling reason to give that preference the force of law, or to give it moral standing over the conflicting preferences of others. Apple would have preferred not to face competition in the sending-music-to-Airport-Express-devices business. But now they will face competition, which may be bad news for Apple but will be good news for everybody else.

[Entry corrected, 3:45 PM. The original version used misleading terminology to describe the encryption key. This is now fixed. Thanks to Adam Shostack for pointing out my error.]

MS To Offer Crippled Windows in Asia

Microsoft plans to offer a reduced-functionality version of Windows XP to customers in a few Asian countries, according to an AP story by Alisa Tang. The “XP Starter Edition” software will lack support for high-res graphic (beyond 800×600), home networking and printer sharing, and other features. It will also be able to run at most three application programs at a time. It will sell for a much lower price than standard WinXP. The software is reportedly meant as an alternative to Linux, and to infringing copies of full WinXP.

This seems like a mistake on Microsoft’s part. Compared to Linux, the crippled version will cost more and do less. When selling the full version of WinXP, Microsoft has at least a plausible argument that you get more by paying more. That argument won’t fly for the crippled version.

Worse yet, customers will know that Microsoft could have given them the full version at the same cost. The decision to offer a deliberately deficient version, but only to its customers in developing countries, will reinforce Microsoft’s image as an imperialist.

I can’t see any upside to this move. Can you?

FCC Tome on Net Wiretapping

The FCC has released its Notice of Proposed Rulemaking (NPRM) on Internet wiretapping. (Backstory here.) The NPRM outlines a set of rules that the FCC is likely to issue, requiring certain online service providers to facilitate (properly authorized) government wiretapping of their customers. The document is a dense 100 pages, and it touches on issues from protocol design to administrative law to network economics, so no one reader or analyst can hope to understand it whole. Below is my initial reaction to reading it.

I’ll start by noting that the FCC isn’t working with a clean slate but must adopt the framework established by the CALEA statute. Some FCC critics (not including me) would prefer a world in which the government could never wiretap anybody for any reason; but that’s not the FCC’s decision to make. The question before the FCC is how to apply the CALEA statute to new Net services, not what the optimal wiretapping policy would be.

One important question is whether the FCC has the authority to issue the rules it is considering. Even some of the FCC commissioners express doubt on this point. This question is outside my expertise, so I’ll defer to people like Susan Crawford (who also has doubts about the FCC’s authority).

Instead, I’ll ask whether the FCC’s proposals are good policy, if we take as given the value judgments expressed in the CALEA statute, which I read as these three: (1) Properly authorized wiretapping is an important law enforcement and national security tool. (2) If necessary, communications providers should accept modest costs to enable lawful wiretapping. (3) In designing networks, wiretappability should be a consideration, but it can be overridden by other important design factors. (Again: I’m not taking a position here for or against these three statements; I’m only asserting that they reflect the views of Congress, as expressed in CALEA.)

The FCC’s first proposal is to require broadband ISPs to be ready to provide law enforcement with the packet-level traffic of any of the ISPs’ customers. I read this rule as requiring ISPs to make their best effort to turn over the raw packets as actually sent and received by the customer, and not as requiring ISPs to interpret, classify, or decode the traffic. This seems like a reasonable rule, in light of CALEA. Capturing the necessary packet-streams won’t be overly expensive for ISPs and doesn’t seem to require redesign of ISPs’ networks; and law enforcement can analyze the packet stream as necessary by using standard tools.

The second, and harder, question answered by the FCC is whether to require VoIP (i.e., voice service over the Internet) to be wiretappable. The FCC tries to take a middle ground on this issue, requiring only “managed” VoIP services to be tappable. The definition of “managed” is a little fuzzy, but it seems to apply only to services that meet all three of these criteria: (1) they look to the consumer like a kind of telephone-like service; (2) they allow calls to people with old-fashioned phones; and (3) they involve the provider’s equipment in each call (i.e., involvement in the call itself, not just as a sort of directory service). VoIP services that are “managed” in this sense would be required to facilitate wiretapping. Other services, like voice-enabled instant messaging, are not managed and so would not have to facilitate wiretapping.

The FCC’s proposed rule looks to me like a reasonable attempt to apply the goals of CALEA to VoIP technology. Managed services are precisely those that are best situated to capture the kind of information needed for wiretapping; and network designs that are inherently unwiretappable would seem to qualify as unmanaged. Two caveats apply, though. First, the NPRM’s definition of “managed” isn’t completely clear, so the definition I gave above may not be the one the FCC meant. Second, as any close reading of the NPRM will demonstrate, the actual application of a CALEA regime to these technology would involve lots of detailed decisions and determinations by the FCC and others, and the details could be bungled. (Indeed, given the sheer number of details, and their complexity, some nonzero amount of bungling seems inevitable.)

There’s much, much more in the NPRM, but I’ve gone on long enough, so I’ll stop for now. My overall impression is that this is a document that will get criticism from both directions. Law enforcement will think it doesn’t do enough; and some technologists will think it meddles too much in their affairs. Contrary to the cliche, criticism from both sides often doesn’t mean you’re doing a good job. But this may be one of those cases where the cliche is right. Overall, I think the FCC has done a pretty good job of applying the semi-contradictory goals of CALEA in a new arena.