November 22, 2024

Archives for 2004

Grokster Wins in Appeals Court

The 9th Circuit Court of Appeals ruled today that Grokster (along with other vendors of decentralized P2P systems) is not liable for the copyright infringement of its users. Today’s decision upholds a lower court decision, which had been appealed by a group of music and movie companies.

The Court largely accepted Grokster’s arguments, finding that although the vast majority of Grokster users are infringers, Grokster itself cannot be held liable for that infringement.

The Court found Grokster not liable for contributory infringement, because Grokster did not have the necessary knowledge of specific infringement. In light of the Supreme Court’s 1984 Sony Betamax decision, as elaborated in this appeals court’s Napster decision, the court first determined that Grokster’s software has substantial commercially significant uses other than infringment. As a result, contributory infringement would have required that Grokster have knowledge of specific acts of infringement, at a time when Grokster could take action to stop those acts. But Grokster simply distributes its product to consumers, and has no knowledge of how any particular customer uses the product later. If copyright owners tell Grokster about an act of infringement, after that act has already happened, that is not actionable knowledge because it is too late to stop the infringment.

The court also held Grokster not liable for vicarious infringement, because Grokster does not have the right and ability to control its customers’ infringing activity. Grokster has no practical way to kick users off the system or to police the system’s use. The court also ruled that Grokster cannot be required to redesign its software and force its customers to update to the redesigned version.

The money quote comes near the end of the opinion:

As to the issue at hand, the district court’s grant of partial summary judgment … is clearly dictated by applicable precedent. The Copyright Owners urge a re-examination of the law in light of what they believe to be proper public policy, expanding exponentially the reach of the doctrines of contributory and vicarious copyright infringement. Not only would such a renovation conflict with binding precedent, it would be unwise. Doubtless, taking that step would satisfy the Copyright Owners’ immediate economic aims. However, it would also alter general copyright law in profound ways with unknown ultimate consequences outside the present context.

Further, as we have observed, we live in a quicksilver technological environment with courts ill-suited to fix the flow of internet innovation. The introduction of new technology is always disruptive to old markets, and particularly to those copyright owners whose works are sold through well-established distribution mechanisms. Yet, history has shown that time and market forces often provide equilibrium in balancing interests, whether the new technology be a player piano, a copier, a tape recorder, a video recorder, a personal computer, a karaoke machine, or an MP3 player. Thus, it is prudent for courts to exercise caution before restructuring liability theories for the purpose of addressing specific market abuses, despite their apparent present magnitude.

Report from Crypto 2004

Here’s the summary of events from last night’s work-in-progress session at the Crypto conference. [See previous entries for backstory.] (I’ve reordered the sequence of presentations to simplify the explanation.)

Antoine Joux re-announced the /msg02554.html">collision he had found in SHA-0.

One of the Chinese authors (Wang, Feng, Lai, and Yu) reported a family of collisions in MD5 (fixing the previous bug in their analysis), and also reported that their method can efficiently (2^40 hash steps) find a collision in SHA-0. This speaker received a standing ovation, from at least part of the audience, at the end of her talk.

Eli Biham announced new results in cryptanalyzing SHA-1, including a collision in a reduced-round version of SHA-1. The full SHA-1 algorithm does 80 rounds of scrambling. At present, Biham and Chen can break versions of SHA-1 that use up to about 40 rounds, and they seem confident that their attacks can be extended to more rounds. This is a significant advance, but it’s well short of the dramatic full break that was rumored.

Where does this leave us? MD5 is fatally wounded; its use will be phased out. SHA-1 is still alive but the vultures are circling. A gradual transition away from SHA-1 will now start. The first stage will be a debate about alternatives, leading (I hope) to a consensus among practicing cryptographers about what the substitute will be.

SHA-1 Break Rumor Update

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.

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.