[Infowarrior] - Making and Breaking HDCP Handshakes

[Richard Forno]

Making and Breaking HDCP Handshakes
Friday April 14, 2006 by Ed Felten
http://www.freedom-to-tinker.com/?p=1005

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:
    secret vector     addition rule
Alice     (26, 19, 12, 7)     [1]+[2]
Bob     (13, 13, 22, 5)     [2]+[4]
Charlie     (22, 16, 5, 19)     [1]+[3]
Diane     (10, 21, 11, ,14)     [2]+[3]

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.]