January 19, 2025

Posts Comments

Serialized Posts

April 21, 2006 by

Lately I’ve found myself writing short series of posts on a single topic, as with the recent sequence of four posts on HDCP security. This is a departure from the traditional style of this blog, where posts were self-contained and the topic would typically change from day to day.

I typically plan out these post series in advance. For example, on HDCP I was pretty sure that there would be four posts, and what their topics would be. Sometimes the plan changes along the way, because writing the early posts, or reading the comments on them, advances my thinking on the topic. But generally I’ll stick pretty close to the plan.

You may wonder why I deliver this content as a series of short quasi-daily posts rather than delivering the whole discussion of (say) HDCP all at once. Part of the answer is that my schedule allows only a certain amount of blog-writing each day, and I would rather publish each piece sooner rather than waiting until it is all done. Another part of the answer is that I suspect there are advantages to letting you see the pieces one at a time and then seeing your comments before writing the next piece.

Filed Under: Uncategorized

HDCP: Why So Weak?

April 19, 2006 by

Today I want to wrap up (I think) the discussion on security weaknesses in HDCP, the encryption scheme used for sending very high-def video from a device like a next-gen DVD player to a TV monitor. I wrote previously (1, 2, 3) about how HDCP will inevitably fail – catastrophically – when somebody manages to recover the master secrets that are the source of all power in the system, and publishes those secrets on the Internet. I wrote, too, about how this problem could have been avoided by using standard cryptographic primitives rather than custom-designed ones.

It seems very likely that the people in charge of HDCP knew what they were doing, and made a deliberate choice to use the less-secure scheme rather than the more secure, standard one. (I don’t have definite proof that they knew about the security problems, but it’s pretty hard to believe that their engineers failed to notice it.) Why did they choose the weak system?

The academic paper on HDCP, by Crosby et al., says that HDCP’s designers were given a “budget” of 10,000 gates. (Gates are one of the basic building blocks from which digital chips are designed.) Crosby estimates that a more secure design would have required about 30,000 gates, to fix the vulnerability I discussed earlier and some smaller vulnerabilities. How much does it cost to add gates to a design? That depends – the high end of the cost range is around $100 per 10,000 gates, but the low end might be much lower.

There are really two questions here. (1) Why did they think it was worth paying for 10,000 extra gates to have the weak system, rather than no encryption at all? (2) Why did they think it wasn’t worth 20,000 gates to have a stronger system, rather than the weak system? Let’s consider these questions in order.

First: Why is the weak system worth spending 10,000 gates for? The answer doesn’t lie in platitudes about speedbumps or raising the bar – any technical bumps or bars will be obliterated when the master secrets are published. It’s worth noting, too, that the data stream they are protecting – uncompressed super high-def (1080i) video – blasts so much data so fast that there’s no affordable way for a would-be pirate to capture it, at least today. About all that can be done with such data streams today, at reasonable cost, is to display them, or to run them through simple format converter boxes. In future years, capturing the video stream will become a viable piracy strategy, but by then the master secrets will almost certainly have been published. So temporary piracy prevention doesn’t seem like a good explanation.

A much more plausible answer is that HDCP encryption exists only as a hook on which to hang lawsuits. For example, if somebody makes unlicensed displays or format converters, copyright owners could try to sue them under the DMCA for circumventing the encryption. (Also, converter box vendors who accepted HDCP’s license terms might sue vendors who didn’t accept those terms.) The price of enabling these lawsuits is to add the cost of 10,000 gates to every high-def TV or video source, and to add another way in which high-def video devices can be incompatible.

The second question is why they weren’t willing to spend an extra 20,000 gates to use a more secure crypto scheme. Doing so would have reduced, in the long run, some types of P2P infringement. They apparently felt this would not be a good investment, presumably because other infringment scenarios were more troublesome. Why spend money strengthening one link in a chain, when other links are already weaker?

The bottom line is clear. In HDCP, “security” technologies serve not to disable pirates but to enable lawsuits. When you buy an HDCP-enabled TV or player, you are paying for this – your device will cost more and do less.

Filed Under: Uncategorized Tagged With: ,

HDCP Could Have Been Better

April 17, 2006 by

I wrote Friday about weaknesses in the HDCP handshake protocol that is being used to set up encryption of very high-def TV content that is in transit from devices like next-gen DVD players to television monitors. This was not news to those who follow the area. The ideas in my post came from a 2001 paper by Crosby, Goldberg, Johnson, Song, and Wagner – all I did is abstract away some of the mathematical detail to simplify the explanation.

As far as I can tell, the publication of the Crosby paper, and the spread of the news about HDCP’s flaws, did not trigger any change in Hollywood’s plans for next-gen TV. They’re still relying upon HDCP, in the same way they seemed to be planning five years ago. As far as I can tell, HDCP’s vulnerability hasn’t changed anything – yet.

This is quite interesting, when we consider that the system as designed is almost certain to be completely broken. The security of the design relies entirely on the secrecy of 1600 special numbers (which form a 40-by-40 matrix), whose disclosure to the public would release the knowledge to build a device that could do absolutely everything that HDCP is supposed to prevent. It is well known how to extract these numbers – though it requires some technical effort – but once the numbers are published, HDCP’s security is shot forever. This is virtually certain to happen in the next few years.

There’s a good chance that the HDCP people knew beforehand that this would be the case. If they used a good due diligence process on the HDCP algorithm, they would almost certainly have discovered these weaknesses. But even if they didn’t know from the very beginning, they found out in 2001.

There’s no doubt that they could have done better. Instead of using the flawed homebrew algorithm they chose, the HDCP designers could have avoided this security problem by using a well-known algorithm known as offline Diffie-Hellman.

Recall from Friday that each HDCP device has a private value and a public value. When two devices – call them A and B – handshake, they send each other their public values. Then A combines its private value with B’s public value, and vice versa. The result of that computation is a secret key, which is guaranteed to be the same for both participants.

In HDCP as designed, the recipe for combining public and private values involves only addition. And because is uses only addition, a would-be attacker (like the conspiracy I discussed on Friday) can set up a series of N equations in N unknowns, and those equations involve only addition – not multiplication, division, or other mathematical operators. Because the equations are this simple (“linear” in math-speak), you can solve them by standard methods, assuming you have enough equations.

The offline Diffie-Hellman algorithm, which I mentioned above, combines the public and private values in a particularly nasty non-linear fashion, to prevent the equation-solving attack. (For more detail on how Diffie-Hellman works, see the entry in Wikipedia.) An adversary can set up equations, but as far as we know there is no practical way to solve them.

The Crosby paper suggests an explanation for the use of a homebrew algorithm: the HDCP design requirements said that the entire design had to implementable in hardware with no more than 10,000 logic gates. (Logic gates are one of the simplest building blocks used to design digital circuitry. In 2001, a state-of-the-art microprocessor chip would have contained tens of millions of gates.)

Indeed, the structure of the homebrew algorithm they used is so similar to that of offline Diffie-Hellman (with simpler mathematical structures replacing the more secure ones used by offline D-H) that it seems likely that the designers knew what they really wanted but couldn’t figure out how to fit it within the 10,000-gate budget they were given – so they settled for a less secure design.

The alternative, of course, would have been to increase the gate budget in order to allow a more secure design. Why didn’t that happen? I’ll discuss some possible reasons next time.

Filed Under: Uncategorized Tagged With: ,

Making and Breaking HDCP Handshakes

April 14, 2006 by

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

Filed Under: Uncategorized Tagged With: , ,

HDMI and Output Control

April 13, 2006 by

Tim Lee at Tech Liberation Front points out an interesting aspect of the new MovieBeam device – it offers its highest-resolution output only to video displays that use the HDMI format.

(MovieBeam is a $200 box you buy that lets you buy 24-hour access to recent movies. There is a rotating menu of movies. Currently video content is trickled out to MovieBeam boxes via unused broadcast bandwidth rented from PBS stations. Eventually they’ll use the Internet to distribute movies to the devices.)

This is a common tactic these days – transmitting the highest-res content only via HDMI. And it seems like a mistake for Hollywood to insist on this. The biggest problem is that some HDTVs have HDMI inputs and some don’t, and most consumers don’t know the difference. Do you know whether your TV has an HDMI input? If you do, you either (a) don’t have a high-def TV, or (b) are a serious video geek.

Consider a (hypothetical) consumer, Fred, who bought an early high-def set because he wanted to watch movies. Fred buys MovieBeam, or a next-gen DVD player, only to discover that his TV can’t display the movies he wants in full definition, because his TV doesn’t do HDMI.

Fred will be especially angry to learn that his MovieBeam box or high-def DVD player is perfectly capable of sending content at higher definition to the inputs that his TV does have, but because of a bunch of legal mumbo-jumbo that Hollywood insists upon, his set-top box deliberately down-rezzes the video before sending it to his TV. Just imagine what Fred will think when he sees news stories about how pirated content is available in portable, high-def formats that will work with his TV.

The official story is that HDMI is a security measure, designed to stop infringers. It’s been known for years that HDMI has serious security flaws; even Wikipedia discusses them. HDMI’s security woes make a pretty interesting story, which I’ll explore over several posts. First I’ll talk about what HDMI is trying to do. Then I’ll go under the hood and talk about how the critical part of HDMI works and its well-known security flaws. (This part is already in the academic literature; I’ll give a more accessible description.) Finally, I’ll get to what is probably the most interesting part: what the history of HDMI security tells us about the industry’s goals and practices.

Officially, the security portion of HDMI is known as High-bandwidth Digital Content Protection, or HDCP. The core of this security design is the HDCP handshake, which takes place whenever two devices communicate over an HDMI cable. The handshake has two goals. First, it lets each device confirm that the other device is an authorized HDCP device. Second, it lets the two devices agree on a secret encryption key which only those two devices know. Subsequent communication over the cable is encrypted using that key, so that eavesdroppers can’t get their hands on any content that is distributed.

In theory, this is supposed to stop would-be infringers. If an infringer tries to plug an authorized video source (like a MovieBeam box) into a device that can capture and redistribute video content, this won’t work, because the capture device won’t be able to do the handshake – the authorized video source will recognize that it is unauthorized and so will refuse to sent it content. Alternatively, if an infringer tries to capture content off the wire, between an authorized source and an authorized TV set, this will be foiled by encryption. That’s the theory at least. The practice is quite different, as I’ll describe next time.

Filed Under: Uncategorized Tagged With: ,