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.]
Front page posts
[...] Link (via Boing Boing) [...]
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.
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.
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.
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
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.
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]
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?
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.
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?
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.
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.
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).
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.
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.
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 (40x40 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.
I put up a page with some basic info to describe how to use the code:
http://www.grack.com/programming/misc/HDCPConspiracyAttack.html
I also changed the download URL to:
http://www.grack.com/downloads/misc/hdcp/hdcp.zip
Sorry for spamming in your comments, Ed!
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.
[...] HDCP, by the way, will also be used in Sky’s upcoming HD satellite service. Making and Breaking HDCP Handshakes: [...]
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.
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.
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.
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.
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.
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.
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).
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)
[...] Freedom to Tinker » Blog Archive » Making and Breaking HDCP Handshakes Tags [...]
Awesome article. I can't wait to get to Princeton next year!
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.
How is my DVD player supposed to get new revocation lists? It doesn't seem very practical to force such updates.
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.
So what is the objective of the HDCP system, other than to be awkward.
http://www.engadget.com/2005/07/21/the-clicker-hdcps-shiny-red-button/
Story about a device that strips HDCP.
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.
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.
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.
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.
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?
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.
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.
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.
phil: I read the spec afterwards and noticed the same thing - it's all done modulo 2^56. Thankfully, this guy:
http://osiris.978.org/~brianr/crypto-research/hdcp/irwin.html
has determined that the conspiracy attack will get you most of the way there, even with solving linear equations. I haven't look too far into it, but on the surface it appears to make the problem only trivially harder. It might make determining the key generator matrix much harder, however.
That's a good point re: different transmit/receive keys. I was basing my assumption on the fact that each device would be able to authenticate with any other device. My guess would be (if this is actually the case) that the two sets of keys would use a single asymmetric matrix (generating the keys the same way as before) but distribute keys from two intersecting key spaces.
I think that people think that breaking HDCP will lead to lots of piracy.
Sorry - it won't. HDCP is not the encyption that holds "the goods". It's weak, but it's only job is to encypt UNCOMPRESSED video.
Uncompressed HD video is HUGE. An HDMI stream can reach 5GB a second! (That's giga Bytes not mega bits - huge).
Currently we lack affordable storage to even STORE a 2 hour movie in raw HDMI format. Although eventually that will get cheaper.
Even AFTER storing all that raw footage, somebody will have to recompress that back into a useful format (MPEG2 or H.264 etc) so that it can be played on modern video player. All of this is totally unpractical for years to come (like 5-7 years). Even when it is practical, it won't be as easy as ripping a DVD is today. It will be slow and time consuming, something consumers won't do (although pirate will, although they will probably have easier ways to get a good quality signal).
The REAL encryption to beat is the new Blu-ray, HD-DVD encrpytion : AACS. Although AACS DOES ALLOW for limited copying. (Copy a HD-DVD to a hard-drive). Although the copying has to be done by a "AACS" approved device, and the media owner can refuse you the right to copy it if they want. (Think Windows Vista!).
I think the idea is that if AACS allows for a limited amount of consumer copying that it might help disuade people from hacking the system, or at least discourage people from using hacked AACS systems (since some official AACS systems will allow backups and copying content from disks to media players, etc). Apple already proved that people will tolerate DRM as long as they can play the music when and where they want to.
Sony as ALREADY ANNOUNCED that the 1st generation Blu-ray players will NOT REQUIRE HDCP to get a 1080i signal! (Although HDMI is the only way to get 1080p!). Although they MAY start enforcing the requirement on future equipment. I expect the HD-DVD guys to follow suite. Which sort of is tacit agreement that HDCP is not worth the effort. Maybe in 5 years when people start using the HDCP "hole" to grab video they start enforcing the requirement, but I sort of doubt it.
YOu can read all the market speak at :http://www.aacsla.com/home
Why not just keep throwing addition rules at the device?
I could say "My addition rule is 1+2 and I'd know x1+x2=?" then the device I'm trying to hack would respond "You're a fake!" but would I care? Hells no. I'd just have it say "My rule is 1+3" and repeat through "1+40" Then all I'd need is on involving another variable pair I don't have yet (ex 2+40) and I'd have enough to solve the equation. I could even have my device drop the line voltage in-between tests to fake like I unplugged from the connector and plugged a new device in that might be legit.
[...] Making and Breaking HDCP Handshakes [...]
@BobPaul
I suspect those nubers would be very big, so brute forcing them would take a lot of time.
One other thing, the device might have some protection and not initiate any other dialogue with your device for 1 second, which would make brute forcing impractical.
I wonder though, how do they match the addition rules and secret keys so that their pairs are always equal..
"I wonder though, how do they match the addition rules and secret keys so that their pairs are always equal."
Maybe they have generated 40 keys by hard slogging and trial and error, and then solved simultaneous linear equations in order to create others.
@Radu:
Even if *I* can only try once a second, other people around the world with the same device as me can try once a second against the same target...
:-)
[...] This is an interesting blog entry regarding the security of HDMI. For those of you that don’t have the time to keep up latest in hardware copy protection schemes (i.e. you have a life), HDMI is the technology that Hollywood is insisting on being used to protect the next generation of Hi-Def content. HDMI is the reason that Blu-Ray was late to the market place and is also the reason why people are having issues regarding certain high end computer graphics cards. [...]