Making and Breaking HDCP Handshakes
Friday April 14, 2006 by Ed FeltenI 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.]
April 14th, 2006 at 4:42 pm
[…] Link (via Boing Boing) […]
April 14th, 2006 at 5:41 pm
Oh man - this algorithm seems especially weak, considering the fact mentioned in the paper that you could purchase 10000 keys for US $16,000. All it would take would be a *single* inside man at one company to get a hold of 40 of the keys.
I’m tempted to whip up a Java applet to do some visualization.
Once that happened, it would be a matter of weeks before companies started putting out HDCP decryption adapters that fit on HDMI cables.
April 14th, 2006 at 5:50 pm
To save anyone having to scour the paper for information, the “addition rules” are 40-bit numbers with 20 one bits and 20 zero bits. The private keys are a vector of 40 56-bit numbers.
AFAICT, the secret keys are calculated by using the bit indexes within the addition rule number to add all the 56-bit numbers together to produce (I believe) a 61-bit key.
It would be interesting to see what stream encryption they use at that point - it’s possible that with such a small key size that it could be broken by simpler cryptographic techniques.
April 14th, 2006 at 6:03 pm
It seems like building a device which impersonates 40 different devices, using 40 keys, is pretty simple; But if I understand correctly, even thinking about it violates the DMCA. Which means that the only customers who will suffer from this scheme are U.S. customers. Just like region-free DVD players are commonplace around the world.
April 14th, 2006 at 6:33 pm
Wow. I flunked algebra and I understood this. One could seriously break the encryption in less than 30 minutes with a homebrew HDMI to Serial adapter and some simple C programming.
idjuts.
UnDMCA, before someone streins themselves to see a positive result.
-jX
April 14th, 2006 at 6:50 pm
Fallowing up from Matt Mastracci.
If one could crack the key on forty diffrent parrings of divices then you would have forty diffrent rules and keys. A 61 bit key is not all that short but given that these are media players where the user controls the media a known plan text attack could be employed. It looks like HDCP wont last long once in the whild.
April 14th, 2006 at 8:28 pm
BTW - is your test case solvable? I tried using a linear equation solver and it seems to be underconstrained…
The equations boil down to two equivalent pairs:
x1 + x2 = 33
x3 + x4 = 26
x2 + x4 = 18
x1 + x3 = 41
I can find a solution though if I make Diane’s addition key [2]+[3]
April 14th, 2006 at 8:49 pm
Why do we need more than one “conspirator”? I don’t care about finding my HDDVD player’s secret vector, I just care about decrypting the video it sends out. To do that, all I need is one valid secret vector + addition rule, so that my video recording device can pretend to be an HDMI-compliant display device.
I say HDDVD as a more practical example, since encrypting the output of a regular DVD player is just moronic. Is the DVD Forum actually dumb enough to mandate extra player encryption to try and protect an already cracked media format?
April 14th, 2006 at 9:02 pm
I don’t think it’s solvable the way it is. I tried the algebra myself and couldn’t get it (and I was an A student in Algebra I and II) and then googled for a 4 unknown calculator and found http://www.1728.com/unknwn4.htm and it couldn’t solve it.
April 14th, 2006 at 9:49 pm
Couldn’t you just hammer a device with thousands of “addition rules” and make it trivial to recover the secret vector for it?
How are these stored? Could you just peek at the EPROM and find the secret vector directly, given access to the hardware?
April 14th, 2006 at 10:45 pm
RyeBrye:
The problem is that the result of the addition rules aren’t presented to you - it’s hashed with a nonce that prevents this sort of attack.
April 14th, 2006 at 10:49 pm
Roy S:
You need more than one conspirator because they could just “ban” a single one and prevent existing players from exchanging keys with it. Fortunately, all we need are 40 raw secret keys, even if they have been revoked by every player on the planet.
Once we get those keys, we can do all sort of interesting attacks on existing devices, including cloning attacks on valid devices.
April 15th, 2006 at 1:07 am
The system of equations is not solvable as is as the four equations are not linearly independent (as Matt Mastracci noticed, adding equation 1 and 4 gives the same result as adding equations 2 and 3). That’s just due to an unfortunate choice of addition vectors, though (also noted by Matt).
April 15th, 2006 at 1:14 am
If you already know 40 keys for 40 devices, why would you need to get the key of some other device?
From what I understand, it is not so trivial to get a key from the HDCP authority. You will need to sign NDAs, to be a real company that manufactures HDCP monitors or players, and so on.
So I am afraid this attack isn’t as simple as it sounds.
April 15th, 2006 at 2:44 am
The simplicity of it isn’t the point. Hackers will manage to get keys from various devices (or else through leaks), but the HDCP specification allows for remote updates to the allowed keys of various HDCP devices. Thus any key that’s distributed across the net or in a fake product will be disallowed. However, this shows a way to crack any HDCP key, thus nullifying this protection.
April 15th, 2006 at 2:54 am
I just implemented a proof of concept HDCP “conspiracy” program in Java. You can download it from:
http://grack.com/downloads/misc/hdcp.zip
Basically, it has two modes. The first mode solves the “conspiracy” problem where you have a number of secret keys and you want to determine the secret key of another box given its private key. The second mode solves for the private system key that can be used to generate any key with no effort. This key is effectively a symmetric NxN matrix (40×40 for the real case).
It turns out to be trivially simple to use the linear solver to solve for the system key. From this system key, it’s trivially simple to solve for *any* private key in the system.
The code doesn’t have a GUI or anything, it’s just a bunch of unit tests that illustrate my proof of concept. It’s easiest to fire up eclipse at point it at the project - it should be all ready to go.
April 15th, 2006 at 7:00 am
As regards Radu’s comments, a holder of genuine keys would not have to dislose them in order for the system to collapse. All they would need to do is to create 40 relevant “bogus” keys, and leak those.
April 15th, 2006 at 7:46 am
[…] HDCP, by the way, will also be used in Sky’s upcoming HD satellite service. Making and Breaking HDCP Handshakes: […]
April 15th, 2006 at 9:25 am
Matt,
You’re right — I took a shortcut and didn’t verify that my four-way conspiracy’s equations weren’t redundant. Not all sets of four equations in four unknowns have a unique solution! I’m updating the post to fix this, per your suggestion.
April 15th, 2006 at 9:43 am
Anonymous:
That’s a good point. All it takes is one person with access to the keys to generate a bunch of keys that are valid but aren’t traceable.
Considering how many software and hardware companies there are, I’m guessing there’s at least one mole within one of them.
April 15th, 2006 at 12:04 pm
I wish you guys would have waited to publish this information until much later.
You should have waited until the industry has sold 100 million plus HDTV sets and the majority of people own one, then it would be too late/expensive to change their flawed design.
If you truly wanted to see HDCP fail, now is not the time to point out it’s inherent flaws.
Currently, there is not enough market penetration and they could possibly revise it right now and make it harder/impossible to crack later down the road.
I want to see HDCP go down in flames as it strips me of my fair use rights, you’ve just given them a guided tour of what needs fixing. Thanks.
April 15th, 2006 at 12:10 pm
As regards the post from “Fair Use rights”, the paper that exposed this problem was published in 1991, long before there were any industry agreements on what to do. And the fact that the system is easily crackable has been in an article in Wikipedia for ages.
Yet they have still gone ahead with it.
The industry have known about this for at least five years.
April 15th, 2006 at 12:31 pm
As a matter of interest, even if the uncompressed HD content streams unencrypted down the HDMI lead,how easy would it be to record it and somehow transform that back onto a disk?
And there is an error in the above post. that paper was published in 2001, not 1991.
April 15th, 2006 at 2:04 pm
Fair Use Rights: Basically, it’s the same as CSS for DVD. It took them a number of years to develop a flawed spec and now they’ve pushed it out to at least thousands of consumers. Changing it now would be prohibitively expensive (how many $16000 giant LCD screens, $500 HDCP-enabled cable boxes, etc. would they need to recall and retrofit?
Anonymous: if you wanted to decrypt the HDMI stream after-the-fact, you’d need to crack a key that changes every few frames, meaning you’d need to crack the session key, or brute force the key for each small set of frames.
April 15th, 2006 at 2:23 pm
As a matter of interest, even if the uncompressed HD content streams unencrypted down the HDMI lead,how easy would it be to record it and somehow transform that back onto a disk?
The unencryped form would be HD-SDI. Devices that can swallow this stream at full speed are currently only available in pro models, starting at about $25k for the JVC HD Encoder (MPEG 2).
April 15th, 2006 at 3:55 pm
HD-SDI… From an MPEG-2 source, to HD-SDI, to an MPEG2 result, which then would need to be put in MPEG4 if you are going to distribute it… Which means it goes from being somewhat lossy, to quite lossy.
So right now the best way to “crack” anything is to “crack” the disk itself. Good luck with that one.
(assuming my logic is correct, which is a big assumption)
April 15th, 2006 at 5:27 pm
[…] Freedom to Tinker » Blog Archive » Making and Breaking HDCP Handshakes Tags […]
April 15th, 2006 at 5:39 pm
Awesome article. I can’t wait to get to Princeton next year!
April 15th, 2006 at 6:10 pm
The main reason to crack the code is not so you can pirate HD-DVDs - it’s so that you can figure out how to play them on your non-HDCP-compliant widescreen TV, or from your non-HDCP-compliant computer. Of course, in order to do the latter, you really do need to crack the on-disk encryption. :’| And it would help to get the DMCA repealed, since it outlaws this particular application of fair use rights.
April 15th, 2006 at 6:20 pm
How is my DVD player supposed to get new revocation lists? It doesn’t seem very practical to force such updates.
April 15th, 2006 at 6:22 pm
Matt Mastracci Says:
“Fair Use Rights: Basically, it’s the same as CSS for DVD. It took them a number of years to develop a flawed spec and now they’ve pushed it out to at least thousands of consumers. Changing it now would be prohibitively expensive (how many $16000 giant LCD screens, $500 HDCP-enabled cable boxes, etc. would they need to recall and retrofit?”
Maybe that is what they meant when they spoke of Blu-Ray and HD DVD as being the second coming of the DVD.
April 15th, 2006 at 6:51 pm
So what is the objective of the HDCP system, other than to be awkward.
April 15th, 2006 at 6:56 pm
http://www.engadget.com/2005/07/21/the-clicker-hdcps-shiny-red-button/
Story about a device that strips HDCP.
April 15th, 2006 at 6:57 pm
Matt:
I’m not sure about the requirement that the matrix be symmetric. The matrix for the simple 4 X 4 example is indeed symmetric but I think that is a consequence of allowing any pair out of the 4 to do the handshake.
In the real case devices can be divided into 2 groups: transmitters (set top boxes, DVD players, etc.) and receivers (display devices). Any link would involve one transmitter and one receiver. In that case I don’t think the matrix needs to be symmetric — the transmitter’s secret key vector could be made by summing selected columns of the matrix and the receiver’s could be made by summing selected rows (or vice versa). The key would end up being the sum of the 400 cells that are defined by the intersection of the 20 selected columns and 20 selected rows. If this is the case then an asymmetric matrix would work.
Yes, some devices (repeaters, recorders) are both transmitters and receivers but a careful read of the spec for the handshake protocols for the repeater seems to imply 2 separate keys.
The above is just some speculation on my part — I could be wrong so feel free to correct me if you have any better information
Also note that the summation is mod 2^56 so the end result is still only 56 bits, not 61.
April 15th, 2006 at 8:13 pm
Hmm,
if the addition rules are represented by 40-bit vectors with precisely 20 bits each, then every combination of addition rules will always have an /even/ number of bits set (i. e. numbers added). That is, you can /never/ solve such a system.
I remember a similar scheme to be the basis for detecting all double-bit errors in error detection and correction circuits.
April 15th, 2006 at 8:20 pm
Uups, sorry. The “never solving” only holds for mod-2 arithmetics.
Therefore, I am not sure yet whether my above observation is relevant or not.
April 15th, 2006 at 8:24 pm
How is my DVD player supposed to get new revocation lists? It doesn’t seem very practical to force such updates.
They wouldn’t try to update current DVD players, what someone mentioned above about securing DVD’s once again refers to to companies updating DVD encryptions on the next gen players. (Making them effectively un-playable on older machines) I don’t think this will happen, it’s trivial.
April 15th, 2006 at 9:43 pm
HDCP protects data on the wire between the computer or video player, and the display or monitor. It is not used for protecting data on the disk. If HDCP is completely broken, the only way to exploit the crack would be to build or acquire a hardware device which sits on the wire and records or alters the data. By virtue of the DMCA, such devices would be illegal in the U.S., so it would not be legal to sell equipment there that recorded HD video using the crack. Building such equipment would probably be beyond the capabilities of the typical hobbyist.
If no encryption had been used on the wire, then the DMCA would not come into play and the content consortia would not be able to stop unauthorized recorders from being sold. From the DMCA perspective, the important thing is that encryption be used, not that it be strong. Since these attacks have been known for years but HDCP deployment has proceeded anyway, presumably the industry does not really care if HDCP gets broken. Copyright holders will still have the legal authority to stop HDCP-defeating equipment from being distributed. At least, this is the case in the U.S. Is there an analogous legal situation in Europe?
April 15th, 2006 at 9:54 pm
Anonymous says: So what is the objective of the HDCP system, other than to be awkward.
In combination with the DMCA it makes you a criminal for “breaking” the encryption.
April 15th, 2006 at 10:00 pm
People keep talking about the dmca as if it affects the whole world. It does not. For example, it has no legal recourse here in Canada. We freely use to decript directv. We are legally able to use anydvd to back-up our software. And do you believe that that technology doesn’t filter across the boarder from countries that are not ruled by the DMCA. The technology will flow across the boarder, and the USA will be better off for it.
April 15th, 2006 at 10:48 pm
I bought a 24 inch LCD, perfect for HDTV, but since the cable box dvi uses encryption, the monitor displays “encryption not supported”
This crap only makes devices not work, pisses me off that this stuff is even inlcuded. This crap does nothing for the consumer. You would buy a car if it said “only uses authorized tires and authorized gas”. The government wouldnt even allow that, but they will for your electronics. NO THANK YOU. Open standards and formats only.