First we assume a circular CD

Over at Freedom to Tinker, Alex Halderman and his adviser Ed Felten have been causing headaches for SunnComm, the makers of broken technology designed to prevent the copying of music CD’s. Alex is the Princeton graduate student who enjoyed worldwide media attention two years ago, when he showed that SunnComm’s “MediaMax” anti-copying software could be disabled by holding down the “Shift” key while inserting a CD into your computer. Alex’s paper about this was downloaded over a hundred thousand times, and caused SunnComm’s stock to lose $10,000,000 in a week. By comparison, my paper Quantum Lower Bound for Recursive Fourier Sampling has (I think) been downloaded at least twice, and would have driven Recursive Fourier Sampling In 2o(h) Queries Incorporated out of business, had it existed.

Now Alex and Ed are reporting that SunnComm has continued to “innovate.” It seems that the latest version of MediaMax, which is included with several Sony/BMG music CD’s,

  1. secretly installs itself even before you accept the End User License Agreement,
  2. remains installed even if you decline the agreement, and
  3. secretly “phones home” to SunnComm with information about your activities, despite assurances to the contrary.

Alex and I met in seventh grade at Newtown Junior High School. I had just transferred from a parochial school, and was so low in the social hierarchy that, when kids beat me up, I was grateful for the attention. My one consolation was that, out of all the kids in the school, I — and I alone — knew that dx3/dx=3x2 and that t’=t/√(1-(v/c)2). Most importantly, I alone knew how to program in GW-BASIC.

So you can imagine the existential shock when I heard there was another kid in seventh grade who was already writing Windows applications and marketing them as shareware. Clearly I had to meet this guy, see if he was for real. After I found out that he was — and repaired the gaping holes in my ego — Alex and I became best friends. We remain so twelve years later.

Even in junior high, Alex was obsessed with security issues: his bestselling program, if I remember correctly, was an encryption utility. At the same time, he was obviously a “white hat.” Rather than getting himself into trouble by hacking the school computers, he’d simply make the teachers utterly reliant on his expertise, then ask them for administrator privileges.

One day in the cafeteria, Alex excitedly brought me a book he was reading, which described a bizarre-sounding encryption system called “RSA.” Supposedly, with this system you could send someone secret messages without ever having met them to agree on a key.

“But that’s obviously impossible,” I explained. I was proud that, for once, I could use my superior mathematical knowledge to set Alex straight.

Eventually Alex and I both ended up in academic computer science, albeit on opposite sides of it. Perhaps the difference between us is best summarized as follows. For Alex, the impossibility of making digital information copy-proof is a central truth of our age: something to be explained, and then re-explained, to judges, reporters, and businesspeople, in amicus curiae briefs and interviews on NPR. For me, it follows from the fact that the set of n-bit strings constitutes an orthogonal basis for Hilbert space.

13 Responses to “First we assume a circular CD”

  1. Janos Simon Says:

    The problem is that there IS a way of making information copy-proof: it only requires that you do not own and control your computer.

    Not so long ago the Ceasescu dictatorship in Rumania had a great idea to make sure information was copy-proof: ownership of typewriters was controlled by the state. If you were a suspicious element, you could not have access to a typewriter.
    (Of course there were no xerox machines…)

    The entertainment industry, and some in the software business are trying to emulate this paradigm. It is possible to control copying if the “copy” instruction not controlled by the user. For the moment this is not done overtly: DRMs try to sneakily install viruses that try to control I/O or send a record of possibly relevant I/O to their Big Dataminig Brother, that tries to find copyright violators. Serious color printers sneakily identify themselves in every printed document. Software calls its creator with details of how it is being used.

    Most of these measures can be defeated — except that many countermeasures are ilegal by US law.

    So, unfortunately, preventing copying is possible — in spite of any Hilbert space theorems–as long as a mix of user agreements and “anti-piracy” laws prevent you from using your computer and your brain.

    Which is why Felten & co are great.

  2. Scott Says:

    Janos: Thanks! Of course you’re right about “interactive” media like software. For music, on the other hand, if you can get it through your eardrum, then presumably you can also get it into a recording device.

  3. Anonymous Says:

    How were you able to know Calculus in the 7th grade?

    I was fortunately able to take a class in BASIC programming on Apple I or II computers in the 6th grade. The instructor was really good and was completely able to relay the concept of an algorithm to an 11 year old. I still remember his lecture. He asked us to tell him how to toggle the light switch by making him turn and walk and move his arms. We also got to play space invaders.

  4. Scott Says:

    Anonymous: The summer between 6th and 7th grades, my brother had a babysitter who’d taken calculus in college. She gave me her textbook, and I read as much of it as I could.

    A few years before that, I’d invented a new field called “graph analysis,” which I was sure would revolutionize the world. Given a sequence of numbers, the idea was to find the “rate of change,” “rate of change of the rate of change,” etc. by taking successive differences between entries, like so:

    6 4 7 8 1
    -2 3 1 -7
    5 -2 -8
    -7 -6

    You could also reverse that operation by taking cumulative sums. It was a big disappointment to learn that Newton and Leibniz had already done this for continuous functions, which is the nontrivial part! πŸ™‚

    Anyway, you’re lucky to have had a good programming instructor as a kid. That class sounds awesome.

  5. Anonymous Says:

    Ah…well I would not have been able to understand the calculus even if I had access to the book since I didn’t even know about algebra in the 7th grade.

    I wonder how often do kids reinvent things? When I was a child it seemed obvious to me that if you tried to “look at” or measure elementary particles that you would change their position/momentum simply by interacting with them. I remember my disappointment when I found out that Heisenberg had already discovered the Uncertainty Principle! πŸ™‚

  6. Scott Says:

    “I wonder how often do kids reinvent things?”

    My guess: far more often than most people think! The best researcher would be someone with the knowledge, confidence, and intellectual honesty that come from decades of experience, but the brain of an 11-year-old.

    PS. Of course, Heisenberg’s principle deals with the product of uncertainties of a pair of noncommuting observables, not with the disturbance to any one of them caused by measurement. πŸ™‚

  7. Luca Says:

    Erdos had this story of how he “independently discovered” negative numbers when he was four.

  8. Eldar Says:

    To set the record straight, the new DRM software is by First4Internet, not SunnComm. It’s crown jewel “feature” is a generic rootkit (read that “trojan”) that makes your system unable to see or delete certain files on the disk. In the spirit of free commerce there seems to be already 3rd party malware that taps this crippling of your system. A bit little and too late, Sony is now making steps to contain the damage, as this one has the potential to be the one that backfires at them.

    One more thing for the irony – there are allegations that the DRM software has copyright violations in its own code, as it incoporates pieces of Free Software projects whose license does not allow this mode of distribution.

    By the way, I should state that I am not in the inner loop myself – the above is from what I read over the net.

  9. Scott Says:

    Eldar: First4Internet and SunnComm both have new DRM software, with different “innovations.” The First4Internet one does seem worse security-wise. But the SunnComm one is easier to explain, and funnier! πŸ™‚

  10. Anonymous Says:

    Can you tell us a bit more about the implication made in this statement:

    “For me, it follows from the fact that the set of n-bit strings constitutes an orthogonal basis for Hilbert space.”

    This is yet another instance where I know ever single word (and jargons) in a sentence but I don’t know what the sentence actually means. πŸ˜›

  11. Scott Says:

    Anonymous: The “no-cloning theorem” says that there’s no way to copy an unknown quantum state (i.e. if you try to duplicate the state, you’ll destroy its quantum coherence). Indeed, a pure quantum state can be copied if, and only if, it belongs to a known orthogonal basis. Fortunately, the set of n-bit strings (or in other words, computational basis states) constitutes just such a basis.

    All of that was just a fancy, highfalutin’ way of saying that classical information (being classical) can be copied!

  12. Greg Kuperberg Says:

    It partly depends on what you mean by a classical state. An indefinite classical state cannot be copied any more than a quantum state can.

    Part of the point is that in quantum theory, all states are indefinite. Pure states are the most definite, but they are still indefinite.

  13. Shtetl-Optimized » Blog Archive » How to rig an election Says:

    […] My friend Alex Halderman is now after bigger fish than copy-”protected” music CD’s. Watch this video, in which he, Ed Felten, and Ariel Feldman demonstrate how to rig a Diebold voting machine (and also watch Alex show off his lock-picking skills). Reading the group’s paper, one becomes painfully aware of a yawning cultural divide between nerds and the rest of the world. Within the nerd universe, that voting machines need to have a verifiable paper trail, that they need to be open to inspection by researchers, etc., are points so obvious as to be scarcely worth stating. If a company (Diebold) refuses to take these most trivial of precautions, then even without a demonstration of the sort Alex et al. provide, the presumption must be that their machines are insecure. Now Alex et al. are trying to take what’s obvious to nerds into a universe — local election boards, the courts, etc. — that operates by entirely different rules. Within this other universe, the burden is not on Diebold to prove its voting machines are secure; it’s on Alex et al. to prove they’re insecure. And even if they do prove they’re insecure — well, if it weren’t for those pesky researchers telling the bad guys how to cheat, what would we have to worry about? […]