I wrote yesterday about the HDCP/HDMI technology that Hollywood wants to use to restrict the availability of very high-def TV content. Today I want to go under the hood, explaining how the key part of HDCP, the handshake, works. I’ll leave out some mathematical niceties to simplify the explanation; full details are in a 2001 paper by Crosby et al.

Suppose you connect an HDMI-compliant next-gen DVD player to an HDMI-compliant TV, and you try to play a disc. Before sending its highest-res digital video to the TV, the player will insist on doing an HDCP handshake. The purpose of the handshake is for the two devices to authenticate each other, that is, to verify that the other device is an authorized HDCP device, and to compute a secret key, known to both devices, that can be used to encrypt the video as it is passed across the HDMI cable.

Every new HDCP device is given two things: a secret vector, and an addition rule. The secret vector is a sequence of 40 secret numbers that the device is not supposed to reveal to anybody. The addition rule, which is not a secret, describes a way of adding up numbers selected from a vector. Both the secret vector and the addition rule are assigned by HDCP’s central authority. (I like to imagine that the central authority occupies an undersea command center worthy of Doctor Evil, but it’s probably just a nondescript office suite in Burbank.)

An example will help to make this clear. In the example, we’ll save space by pretending that the vectors have four secret numbers rather than forty, but the idea will be the same. Let’s say the central authority issues the following values:

Suppose Alice and Bob want to do a handshake. Here’s how it works. First, Alice and Bob send each other their addition rules. Then, Alice applies Bob’s addition rule to her vector. Bob’s addition rule is “[2]+[4]”, which means that Alice should take the second and fourth elements of her secret vector and add them together. Alice adds 19+7, and gets 26. In the same way, Bob applies Alice’s addition rule to his secret vector – he adds 13+13, and gets 26. (In real life, the numbers are much bigger – about 17 digits.)

There are two things to notice about this process. First, in order to do it, you need to know either Alice’s or Bob’s secret vector. This means that Alice and Bob are the only ones who will know the result. Second, Alice and Bob both got the same answer: 26. This wasn’t a coincidence. There’s a special mathematical recipe that the central authority uses in generating the secret vectors to ensure that the two parties to any legitimate handshake will always get the same answer.

Now both Alice and Bob have a secret value – a secret key – that only they know. They can use the key to authenticate each other, and to encrypt messages to each other.

This sounds pretty cool. But it has a very large problem: if any four devices conspire, they can break the security of the system.

To see how, let’s do an example. Suppose that Alice, Bob, Charlie, and Diane conspire, and that the conspiracy wants to figure out the secret vector of some innocent victim, Ed. Ed’s addition rule is “[1]+[4]”, and his secret vector is, of course, a secret.

The conspirators start out by saying that Ed’s secret vector is (x1, x2, x3, x4), where all of the x’s are unknown. They want to figure out the values of the x’s – then they’ll know Ed’s secret vector. Alice starts out by imagining a handshake with Ed. In this imaginary handshake, Ed will apply Alice’s addition rule ([1]+[2]) to his own secret vector, yielding x1+x2. Alice will apply Ed’s addition rule to her own secret vector, yielding 26+7, or 33. She knows that the two results will be equal, as in any handshake, which gives her the following equation:

x1 + x2 = 33

Bob, Charlie, and Diane each do the same thing, imagining a handshake with Ed, and computing Ed’s result (a sum of some of the x’s), and their own result (a definite number), then setting the two results equal to each other. This yields three more equations:

x2 + x4 = 18
x1 + x3 = 41
x2 + x3 = 24

That makes four equations in four unknowns. Whipping out their algebra textbooks, the conspiracy solves the four equations, to determine that

x1 = 25
x2 = 8
x3 = 16
x4 = 10

Now they know Ed’s secret vector, and can proceed to impersonate him at will. They can do this to any person (or device) they like. And of course Ed doesn’t have to be a real person. They can dream up an imaginary person (or device) and cook up a workable secret vector for it. In short, they can use this basic method to do absolutely anything that the central authority can do.

In the real system, where the secret vectors have forty entries, not four, it takes a conspiracy of about forty devices, with known private vectors, to break HDCP completely. But that is eminently doable, and it’s only a matter of time before someone does it. I’ll talk next time about the implications of that fact.

[Correction (April 15): I changed Diane’s secret vector and addition rule to fix an error in the conspiracy-of-four example. Thanks for Matt Mastracci for pointing out the problem.]