November 29, 2024

Acoustic Snooping on Typed Information

Li Zhuang, Feng Zhou, and Doug Tygar have an interesting new paper showing that if you have an audio recording of somebody typing on an ordinary computer keyboard for fifteen minutes or so, you can figure out everything they typed. The idea is that different keys tend to make slightly different sounds, and although you don’t know in advance which keys make which sounds, you can use machine learning to figure that out, assuming that the person is mostly typing English text. (Presumably it would work for other languages too.)

Asonov and Agrawal had a similar result previously, but they had to assume (unrealistically) that you started out with a recording of the person typing a known training text on the target keyboard. The new method eliminates that requirement, and so appears to be viable in practice.

The algorithm works in three basic stages. First, it isolates the sound of each individual keystroke. Second, it takes all of the recorded keystrokes and puts them into about fifty categories, where the keystrokes within each category sound very similar. Third, it uses fancy machine learning methods to recover the sequence of characters typed, under the assumption that the sequence has the statistical characteristics of English text.

The third stage is the hardest one. You start out with the keystrokes put into categories, so that the sequence of keystrokes has been reduced a sequence of category-identifiers – something like this:

35, 12, 8, 14, 17, 35, 6, 44, …

(This means that the first keystroke is in category 35, the second is in category 12, and so on. Remember that keystrokes in the same category sound alike.) At this point you assume that each key on the keyboard usually (but not always) generates a particular category, but you don’t know which key generates which category. Sometimes two keys will tend to generate the same category, so that you can’t tell them apart except by context. And some keystrokes generate a category that doesn’t seem to match the character in the original text, because the key happened to sound different that time, or because the categorization algorithm isn’t perfect, or because the typist made a mistake and typed a garbbge charaacter.

The only advantage you have is that English text has persistent regularities. For example, the two-letter sequence “th” is much more common that “rq”, and the word “the” is much more common than “xprld”. This turns out to be enough for modern machine learning methods to do the job, despite the difficulties I described in the previous paragraph. The recovered text gets about 95% of the characters right, and about 90% of the words. It’s quite readable.

[Exercise for geeky readers: Assume that there is a one-to-one mapping between characters and categories, and that each character in the (unknown) input text is translated infallibly into the corresponding category. Assume also that the input is typical English text. Given the output category-sequence, how would you recover the input text? About how long would the input have to be to make this feasible?]

If the user typed a password, that can be recovered too. Although passwords don’t have the same statistical properties as ordinary text (unless they’re chosen badly), this doesn’t pose a problem as long as the password-typing is accompanied by enough English-typing. The algorithm doesn’t always recover the exact password, but it can come up with a short list of possible passwords, and the real password is almost always on this list.

This is yet another reminder of how much computer security depends on controlling physical access to the computer. We’ve always known that anybody who can open up a computer and work on it with tools can control what it does. Results like this new one show that getting close to a machine with sensors (such as microphones, cameras, power monitors) may compromise the machine’s secrecy.

There are even some preliminary results showing that computers make slightly different noises depending on what computations they are doing, and that it might be possible to recover encryption keys if you have an audio recording of the computer doing decryption operations.

I think I’ll go shut my office door now.

Aussie Judge Tweaks Kazaa Design

A judge in Australia has found Kazaa and associated parties liable for indirect copyright infringement, and has tentatively imposed a partial remedy that requires Kazaa to institute keyword-based filtering.

The liability finding is based on a conclusion that Kazaa improperly “authorized” infringement. This is roughly equivalent to a finding of indirect (i.e. contributory or vicarious) infringement under U.S. law. I’m not an expert in Australian law, so on this point I’ll refer you to Kim Weatherall’s recap.

As a remedy, the Kazaa parties will have to pay the 90% of the copyright owners’ trial expenses, and will have to pay damages for infringement, in an amount to be determined by future proceedings. (According to Kim Weatherall, Australian law does not allow the copyright owners to reap automatic statutory damages as in the U.S. Instead, they must prove actual damages, although the damages are boosted somehow for infringements that are “flagrant”.)

More interestingly, the judge has ordered Kazaa to change the design of their product, by incorporating keyword-based filtering. Kazaa allows users to search for files corresponding to certain artist names and song titles. The required change would disallow search terms containing certain forbidden patterns.

Designing such a filter is much harder than it sounds, because there are so many artist names and song names. These two namespaces are so crowded that a great many common names given to non-infringing recordings are likely to contain forbidden patterns.

The judge’s order uses the example of the band Powderfinger. Presumably the modified version of Kazaa would ban searches with “Powderfinger” as part of the artist name. This is all well and good when the artist name is so distinctive. But what if the artist name is a character string that occurs frequently in names, such as “beck”, “smiths”, or “x”? (All are names of artists with copyrighted recordings.) Surely there will be false positives.

It’s even worse for song names. You would have to ban simple words and phrases, like “Birthday”, “Crazy”, “Morning”, “Sailing”, and “Los Angeles”, to name just a few. (All are titles of copyrighted recordings.)

The judge’s order asks the parties to agree on the details of how a filter will work. If they can’t agree on the details, the judge will decide. Given the enormous number of artist and song names, and the crowded namespace, there are a great many details to decide, balancing over- and under-inclusiveness. It’s hard to see how the parties can agree on all of the details, or how the judge can impose a detailed design. The only hope is to appoint some kind of independent arbiter to make these decisions.

Ultimately, I think the tradeoff between over- and under-inclusiveness will prove too difficult – the filters will either fail to block many infringing files, or will block many non-infringing files, or both.

This is the same kind of filtering that Judge Patel ordered Napster to use, after she found Napster liable for indirect infringement. It didn’t work for Napster. Users just changed the spelling of artist and song names, adopting standard misspellings (e.g., “Metallica” changed to “Metalica” or “MetalIGNOREica” or the Pig Latin “Itallicamay”), or encoding the titles somehow. Napster updated its filters to compansate, but was always one step behind. And Napster’s job was easier, because the filtering was done on Napster’s own computers. Kazaa will have to try to download updates to users’ computers every time it changes its filters.

To the judge’s credit, he acknowledges that filtering will be imprecise and might even fail miserably. So he orders only that Kazaa must use filtering, but not that the filtering must succeed in stopping infringement. As long as Kazaa makes its best effort to make the agreed-upon (or ordered) filtering scheme work, it will have have satisfied the order, even if infringement goes on.

Kim Weatherall calls the judge’s decision “brave”, because it wades into technical design and imposes a remedy that requires an ongoing engagement between the parties, two things that courts normally try to avoid. I’m not optimistic about this remedy – it will impose costs on both sides and won’t do much to stop infringement. But at least the judge didn’t just order Kazaa to stop all infringement, an order with which no general-purpose communication technology could ever hope to comply.

In the end, the redesign may be moot, as the prospect of financial damages may kill Kazaa before the redesign must occur. Kazaa is probably dying anyway, as users switch to newer services. From now on, the purpose of Kazaa, in the words of the classic poster, may be to serve as a warning to others.

Back in the Saddle

Hi, all. I’m back from a lovely vacation, which included a stint camping in Sequoia / King’s Canyon National Park, beyond the reach of Internet technology. In transit, I walked right by Jack Valenti in the LA airport. He looked as healthy as ever, and more relaxed than in his MPAA days.

Blogging will resume tomorrow, once I’ve dug out sufficiently from the backlog. In the meantime, I recommend reading Kim Weatherall’s summary of the Australian judge’s decision in the Kazaa case.

Recommended Reading: The Success of Open Source

It’s easy to construct arguments that open source software can’t succeed. Why would people work for free to make something that they could get paid for? Who will do the dirty work? Who will do tech support? How can customers trust a “vendor” that is so diffuse and loosely organized?

And yet, open source has had some important successes. Apache dominates the market for web server software. Linux and its kin are serious players in the server operating system market. Linux is even a factor in the desktop OS market. How can this be reconciled with what we know about economics and sociology?

Many articles and books have been written about this puzzle. To my mind, Steven Weber’s book “The Success of Open Source” is the best. Weber explores the open source puzzle systematically, breaking it down into interesting subquestions and exploring answers. One of the book’s virtues is that it doesn’t claim to have complete answers; but it does present and dissect partial answers and hints. This is a book that could merit a full book club discussion, if people are interested.

Recommended Reading: Crime-Facilitating Speech

Eugene Volokh has an interesting new paper about Crime-Facilitating Speech (abridged version): “speech [that] provides information that makes it easier to commit crimes, torts, or other harms”. He argues convincingly that many free-speech cases pertain to crime-facilitating speech. Somebody wants to prevent speech because it may facilitate crime, but others argue that the speech has beneficial effects too. When should such speech be allowed?

The paper is a long and detailed discussion of this issues, with many examples. In the end, he asserts that crime-facilitating speech should be allowed except where (a) “the speech is said to a few people who the speaker knows are likely to use it to commit a crime or to escape punishment”, (b) the speech “has virtually no noncriminal uses”, (c) “the speech facilitates extraordinarily serious harms, such as nuclear or biological attacks”. But don’t just read the end – if you have time it’s well worth the effort to understand how he got there.

What struck me is how many of the examples relate to computer security or copyright enforcement. Many security researchers feel that the applied side of the field has become a legal minefield. Papers like this illustrate how that happened. The paper’s recommendations, if followed, would go a long way toward making legitimate research and publication safer.