November 21, 2024

Posts Comments

Archives for April 2010

India's Electronic Voting Machines Have Security Problems

April 29, 2010 by

A team led by Hari Prasad, Alex Halderman, and Rop Gonggrijp released today a technical paper detailing serious security problems with the electronic voting machines (EVMs) used in India.

The independent Electoral Commission of India, which is generally well respected, has dealt poorly with previous questions about EVM security. The chair of the Electoral Commission has called the machines “infallible” and “perfect” and has rejected any suggestion that security improvements are even possible. I hope the new study will cause the EC to take a more realistic approach to EVM security.

The researchers got their hands on a real Indian EVM which they were able to examine and analyze. They were unable to extract the software running in the machine (because that would have required rendering the machine unusable for elections, which they had agreed not to do) so their analysis focused on the hardware. They were able to identify several attacks that manipulated the hardware, either by replacing components or by clamping something on to a chip on the motherboard to modify votes. They implemented demonstration attacks, actually building proof-of-concept substitute hardware and vote-manipulation devices.

Perhaps the most interesting aspect of India’s EVMs is how simple they are. Simplicity is a virtue in security as in engineering generally, and researchers (including me) who have studied US voting machines have advocated simplifying their design. India’s EVMs show that while simplicity is good, it’s not enough. Unless there is some way to audit or verify the votes, even a simple system is subject to manipulation.

If you’re interested in the details, please read the team’s paper.

The ball is now in the Election Commission’s court. Let’s hope that they take steps to address the EVM problems, to give the citizens of the world’s largest democracy the transparent and accurate elections they deserve.

Filed Under: Other Topics, Privacy & Security Tagged With: , ,

The Gizmodo Warrant: Searching Journalists in the Terabyte Age

April 27, 2010 by

Last Friday night, police officers in California used a warrant to search the home of Jason Chen, the Gizmodo blogger who wrote about the iPhone prototype found in a Redwood City bar. Orin Kerr has written an interesting post assessing the legality of the search. I wanted to touch on an important issue he didn’t discuss: Whether the search the police are conducting is unconstitutionally overbroad.

Orin discusses two laws that specifically shield journalists from being the target of a search, the California Reporter’s Shield Law, found jointly at California Penal Code 1524(g) and California Evidence Code 1070, and the federal Privacy Protection Act (PPA), 42 U.S.C. 2000aa. Both laws were written to limit the impact of Zurcher v. Stanford Daily, a U.S. Supreme Court case authorizing the use of a warrant to search a newspaper’s offices. The Supreme Court decided Zurcher in 1978, and Congress enacted the PPA in 1980 (and amended it in unrelated ways in 1996). I’m not sure when the California law was enacted, but I bet it’s of similar vintage. In other words, all of the rules that govern police searches of news offices were created in the age of typewriters, desks, filing cabinets, and stacks of paper.

Now, flash forward thirty years. The police who searched Jason Chen’s home seized the following: A macbook, HP server, two Dell desktop computers, iPad, ThinkPad, two MacBook Pros, IOmega NAS, three external hard drives, and three flash drives. They also seized other storage-containing devices, including two digital cameras and two smart phones. If Jason Chen’s computing habits are anything like mine, the police likely seized many terabytes of disk space, storing hundreds of thousands (millions?) of files, containing information stretching back years. And they took all of this information to investigate an alleged crime (the sale of the iPhone prototype) that could not have happened more than 37 days before the search (the iPhone was found on March 18th), which they learned about from a blog post published four days before the search.

I’m deeply concerned about overbreadth as the police begin to search through these terabytes of information. The police now possess, intermingled with the evidence of the alleged crime they are investigating, hundreds of thousands of documents belonging to a journalist/blogger that are utterly irrelevant to their investigation. Jason Chen has been blogging for Gizmodo since 2006, and he’s probably written hundreds of stories. The police likely have thousands of email messages revealing confidential sources, detailing meetings, and trading comments with editors, and thousands of other documents bearing notes from interviews, drafts of articles, and other sensitive information. Because of Chen’s beat, some of these documents probably reveal secrets of great economic and business value in the Silicon Valley. Under traditional, outmoded Fourth Amendment rules, the police can read every single document they possess, so long as they intend only to look for evidence of the crime, and under the “plain view rule,” they can use any evidence they find of other, unrelated crimes in court against Chen or anyone else.

If the California state courts share my concerns about overbreadth, they should consider embracing the very sensible rules for search warrants for computer hard drives (in any case, not just those involving journalists) adopted last year by the Ninth Circuit in United States v. Comprehensive Drug Testing. To paraphrase, in cases involving the search and seizure of computers, the Ninth Circuit requires five things: (1) the government must waive the plain view rule, meaning they must agree not to use evidence of crimes other than the one under investigation that led to the warrant; (2) the government must wall off the forensic experts who search the hard drive from the investigating the case; (3) the government must explain the “actual risks of destruction of information” they would face if they weren’t allowed to seize entire computers; (4) the government must use a search protocol to designate what information they can give to the investigating agents; and (5) the government must destroy or return non-responsive data.

These rules are especially needed when the target of a police search is a journalist (in fact, they may not go far enough). And these rules may be required under Zurcher. In justifying the search of the newspaper’s offices in Zurcher, the Supreme Court agreed that when the Fourth Amendment’s search and seizure rules collide with First Amendment values, like freedom of the press, the “Fourth Amendment must be applied with ‘scrupulous exactitude.'” The court went on to explain why ordinary search warrants for news offices (remember, back in the age of paper files) meet this heightened standard:

There is no reason to believe, for example, that magistrates cannot guard against searches of the type, scope, and intrusiveness that would actually interfere with the timely publication of a newspaper. Nor, if the requirements of specificity and reasonableness are properly applied, policed, and observed, will there be any occasion or opportunity for officers to rummage at large in newspaper files or to intrude into or to deter normal editorial and publication decisions.

When the California state courts combine this thirty-year-old statement of the law with the modern realities of terabyte storage devices, they should hold that the Fourth Amendment requires magistrate judges to play an integral and active role in the administration of the search of Jason Chen’s computers and other storage devices. At the very least, the courts should forbid the police from looking at any file timestamped before March 18, 2010, and in addition, they should force the police to comply with the Comprehensive Drug Testing rules. In the terabyte age, these rules are necessary at a minimum to prevent the police from interfering with a free press.

Filed Under: Uncategorized Tagged With: , ,

Needle-in-a-Haystack Problems, and P vs. NP

April 27, 2010 by

Last week I wrote about needle-in-a-haystack problems, in which it’s hard to find the solution but if somebody tells you the solution it’s easy to verify. A commenter asked whether such problems are related to the P vs. NP problem, which is the most important unsolved problem in theoretical computer science. It turns out that they are related, and that needle-in-a-haystack problems are a nice framework for explaining the P vs. NP problem, which few non-experts seem to understand.

Stated simply, the P vs. NP problem asks whether needle-in-a-haystack computational problems can exist. To understand what this means, we need to take a short detour into computer science theoryland. It’s perfectly safe, but stay close to the group so you don’t wander off into a finite field…. Okay, let’s meet P and NP.

P is the set of problems that can be solved efficiently. The precise theoretical definition of “efficient” is a bit subtle: we define the “size” of a problem to be the number of characters needed to write down the problem; and we say a solution method is efficient if, when the problem is large, the method can finish in a length of time that is less than the problem size raised to some power.

For example, suppose we are given two N-digit numbers, A and B, and a 2N-digit number C, and we’re asked whether A times B equals C. It requires 4N characters to write down the problem, one character for each digit in each of the numbers. We can solve the problem by multiplying A and B, using the multiplication method we learned in school, and then comparing the result to C. The multiplication will take us roughly N-squared steps, and the comparison is faster than that. So the solution time will grow roughly as N-squared, and if N is large this is less than the third power of the problem size (i.e., less than 4N raised to the third power). Therefore multiplication is in P, which matches our intuition that we know how to multiply efficiently.

Here’s another example, the “traveling salesperson problem” (TSP): given a list of cities, a table showing the airfare between each pair of cities, and a total travel budget, is there an itinerary that visits every city on the list and returns to where it started, without exceeding the total travel budget? One way to solve this problem is to try out all of the possible itineraries, and see if there’s one that is cheap enough. That works, but it is not efficient, because its running time grows faster than any fixed power of the problem size. No efficient algorithm for the TSP is known. There might be one, but if there is one we haven’t discovered it yet. So we don’t know if the TSP is in P.

You might have guessed by now that P stands for “polynomial”, as in “solvable in polynomial time”. That is indeed the origin of the name P. And you might go on to guess that NP stands for “not polynomial” — but that would be wrong. If you must know, NP stands for “nondeterministic polynomial”. I won’t bother explaining what “nondeterministic” means here, because that has confused generations of students. Instead, let’s use an alternative, but equivalent, definition of NP.

NP is the set of problems having yes/no answers, for which, whenever the correct answer is “yes”, there is some “hint” that allows us to verify the “yes” answer efficiently. Think about the TSP: if somebody tells you a cheap itinerary, you can verify efficiently that that itinerary visits all of the cities, ends where it started, and costs less than the travel budget. So the TSP is in NP.

Multiplication is in NP as well. Given any hint (“booga booga”, say) we can verify that A times B equals C, by simply ignoring the hint, and then multiplying and comparing as above. By a similar argument, any problem in P must also be in NP.

You can see now how this connects with needles and haystacks. If a problem is in NP but not in P, it’s like a needle-in-a-haystack problem: we can verify the answer efficiently if we’re given a hint, but without a hint we can’t find the answer efficiently. So asking whether needle-in-a-haystack problems exist is exactly the same as asking whether P is different from NP.

Are P and NP different? We don’t know. Consider the Traveling Salesperson Problem. We know it’s in NP, because we can verify the answer efficiently given a hint, but we don’t know if it’s in P. We don’t know if the TSP can be solved efficiently — we haven’t found an efficient solution yet but we can’t rule out the possibility that somebody will discover one tomorrow. A lot of people have tried really hard for a long time to find an efficient solution, so most experts tend to assume that no efficient solution is possible — but the experts have been wrong before.

If, on the other hand, P and NP turn out to be equal, the consequences would be huge. For example, much of cryptography would collapse. Decrypting a message is supposed to be a needle-in-a-haystack problem—easy if you have a hint (i.e., the secret decryption key) but hard otherwise.

It’s annoying, to say the least, that such a basic question about information remains unanswered. For decades theorists have been trying to scale the P vs. NP mountain from various directions,without success. The rest of us have gotten accustomed to assuming that needle-in-a-haystack problems exist, and hoping for the best.

Filed Under: Uncategorized

Needle-in-a-Haystack Problems

April 23, 2010 by

Sometimes the same idea comes flying at you from several directions at once, and you start seeing that idea everywhere. This has been happening to me lately with needle-in-a-haystack problems, a concept that is useful but often goes unrecognized.

A needle-in-a-haystack problem is a problem where the right answer is very difficult to determine in advance, but it’s easy to recognize the right answer if someone points it out to you. Faced with a big haystack, it’s hard to find the needle; but if someone tells you where the needle is, it’s easy to verify that they’re right.

This idea came up in a class discussion of Beth Noveck’s Wiki-Government paper. We were talking about how government can use crowdsourcing to learn from outside experts, and somebody pointed out that crowdsourcing can work well for needle-in-a-haystack problems. If somebody in the crowd knows the answer, they can announce it, and other participants in the discussion will recognize that the proposed answer is correct. This is the basis for the open-source maxim that “given enough eyes, all bugs are shallow”. It’s also the theory underlying the Peer to Patent project, in which distributed experts tried to find the best prior art document that would invalidate a patent application.

The idea came up again in a discussion of online passwords. A highly secure system doesn’t remember your password, because an attacker who managed to observe the stored password could impersonate you. But if the system doesn’t store your password, how can it verify that the password you enter is correct?

The answer is that the system can create a needle-in-a-haystack problem to which your password is the only right answer. By remembering this problem rather than your password, the system will be able to recognize your password when it sees it, but an attacker who learns what the problem is will have great difficulty determining your password. There are standard cryptographic tricks for generating this kind of needle-in-a-haystack problem.

The idea came up a third time when I read a paper with the eye-catching title “Why Most Published Research Findings Are False“. The paper explains why the vast majority of research findings in a field might be false, even if the researchers do everything right; and it suggests that this is the case for some areas of medical research.

To see how this might happen, imagine a needle-in-a-haystack problem that has one right answer and a million wrong answers. Suppose that our procedure for verifying the right answer when we see it is not flawless but instead is wrong 0.01% of the time. Now if we examine all of the 1,000,000 wrong answers, we will incorrectly classify 100 of them (0.01% of 1,000,000) as correct. In total, we’ll find 101 “correct” answers, only one of which is actually correct. The vast majority of “correct” answers — more than 99% of them — will be wrong.

Any research field that is looking for needles in haystacks will tend to suffer from this problem, especially if it relies on statistical studies, which by definition can never yield absolute 100% confidence.

Which brings us back to crowdsourcing. If we’re not perfect at recognizing proposed answers as correct — and no human process is perfect — then a crowdsourcing approach to needle-in-a-haystack problems could well yield wrong answers most of the time.

How can we avoid this trap? There are only two ways out: reduce the size of the haystack, or improve our procedure for evaluating candidate answer. Here crowdsourcing could be helpful. If we’re lucky, vigorous discussion within the crowd will help to smoke out the false positives. It’s not just access to experts that helps, but dialog among the experts.

Filed Under: Uncategorized

Release Government Data, Early and Often

April 22, 2010 by

One of the key axioms of modern open government is that all public data should be published online in a raw but usable form. Usability in this case is aimed at software programmers. By making government datasets more usable, programmers are more likely to innovate in the civic sphere and build technologies, using the raw data, to enhance the relationships among citizens and with government.

The open government community has provided plenty of valuable guidance about what usability means for programmers. We proclaim that all datasets need to be: published in a format that is reasonably structured and machine-processable; well-documented; downloadable in bulk; authenticated using cryptographic digital signatures; version-controlled; permanent and citable; and the list goes on and on. These are all worthy principles to be sure, and all government datasets should strive to meet them.

But you’ll be hard-pressed to find any government datasets that exist with all of these principles pre-satisfied. While some are in better shape than others, most datasets would make programmers cringe. Data often only exist as informal working sets in proprietary Excel spreadsheets. Sometimes they are in structured databases, but schemas are undocumented, field values are ambiguous, and the semantics are only understood by the employee who created them. Datasets have errors and biases that are known but never explicitly corrected.

For a civil servant who is a data caretaker looking over the laundry list of publishing principles, there’s frequently a huge quality chasm between the dataset she owns and how people are asking to see it released. To her, publishing this data adequately just seems like a lot of extra work. The more attractive alternative is to put off the data publishing—it’s not in her job description or evaluations anyway—and move on to other work instead.

How can this chasm be bridged? A widely-adopted philosophy in software development and entrepreneurship would serve open government data well: release early and release often. And listen to your customers.

In the software development world, a working version of the product is pushed out as soon as possible even with known imperfections—an “alpha” release—so it can be subject to real use by early adopters. Early adopters can provide helpful feedback about what works, what’s broken, and what new features would be most useful to them. The software developers then iterate quickly. They incorporate the suggested fixes and features into their code and release an updated version of the product to their users. The virtuous cycle then starts again. Under this philosophy, software developers can be efficient about how to best improve their code where it matters, and users get software that works better and has more features they desire.

The “release early, release often” philosophy should be applied to government data. For the initial release, data caretakers should take the path of least resistance to get data out the door. This means publishing datasets in whatever format is most convenient, along with as much documentation as can reasonably be mustered. Documentation is especially important with an “alpha” dataset—proper warnings about its problems, instabilities and inductive limitations must be prominently displayed. (Of course, the usual privacy and legal caveats should also be applied.) Sometimes, the “alpha” release will be “good enough” for programmers to start their work, and this will minimize any superfluous work done by caretakers. This is the virtue of “release early.”

In other cases, programmers will need assistance using the dataset and will notice problem spots with the initial release. The dataset might be confusing, contain errors or be difficult to work with. A tight feedback mechanism allows the programmer to get help quickly and continue to innovate, while the data caretaker can fix problems based on real use cases and add clarifying metadata into an updated version of the dataset. Data quality and usability increases for those working with the dataset, both in and outside of government. That’s the virtue of “release often.”

And here is the big opportunity for government: no platform currently exists to engage the prime audience for government data—software programmers. Without a tight feedback mechanism, the virtuous cycle of mutual benefit cannot exist. Government is missing its best opportunity to improve data quality by neglecting useful feedback from programmers who are actually tinkering with the datasets. Society is losing out on potentially game-changing civic innovations, which otherwise would have been built if data were more usable and the uncertainty of failure reduced.

A terrific start in turning the corner would be for government to adopt an issue-tracking system for its datasets. As a public venue, it would help ensure that data caretakers are prompt in addressing developer concerns. It would also allow caretakers to organize feedback in a formal way. Such platforms are commonplace in any successful software development venture. The same needs to be true for government data in order to drive rapid quality improvements and increase developer engagement.

Filed Under: Uncategorized Tagged With: , ,