Archives for April 2006

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.

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.