April 25, 2024

Archives for August 2004

Paper Trail Allows Venezuela Recount

On August 15, Venezuelans voted in a national referendum on whether to remove President Hugo Chavez. The (Chavez-run) government announced afterward that 58% had voted to keep Chavez in office. The opposition claimed fraud.

The election was held on electronic voting machines. Fortunately, the machines generated a voter-verified paper trail, so that there was some hope of recounting the ballots. Without a paper trail there could have been no recount, and Venezuelans would have had to take the result on faith, or reject it. With a paper trail, there is at least some evidence of how the votes were cast.

What evidence is there for fraud? The opposition says that the election results were inconsistent with exit polling, which they say went 58-42 in the other direction. That’s a big enough swing to raise eyebrows, but it’s hard to evaluate the accuracy of the exit polls based on the information available to me.

The opposition’s other claim is that the voting machines were programmed to cap the number of yes votes (i.e., anti-Chavez votes) recorded on each voting machine. In support of this, the opposition points to the data on machine-by-machine voting results, arguing that machines in the same polling place recorded the exact same number of yes votes too often, that is, more often than would have occurred by chance. That’s a claim that is amenable to statistical analysis. I’ll evaluate it in a future entry.

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.