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.]
Hi, you can also have bought HDCP compatible devices, and they don’t understand together because te HDMI cable is 15m and too long.
In this case of which I am concerned, you would be happy that somebody help you to solve this HDMI – HDCP problem !
Hi, not sure if this has been mentioned yet but there is a device or was, ( can’t find it for sale anymore ) from the jap/chinese scene, which takes one hdmi hdcp signal and recieves it handshakes and all as if it were a hdcp monitor/lcd. then sends out (hdmi) without hdcp. i assume the device imitates a lcd, with the same chipset, probably why they were advertised in australia for $500. i think it was called gameswitch i will look for link and post it.
Re: DMCA:
Can’t a couple of arguments be made that this doesn’t violate the DMCA or if it does.. we can’t we get an exception..where are my consumer protection attorneys?
`(B) a technological protection measure `effectively controls access to a work’ if the measure, in the ordinary course of its operation, requires the application of information, or a process or a treatment, with the authority of the copyright owner, to gain access to the work.
HDCP requires the consumer to BUY CERTAIN devices to the exclusion of others devices is this a process or treatment in effect it is a tying of copyrighted content to technological devices (antitrust anyone? But is it anticompetitive…certainly there is an argument that it indeed is anticompetitive…gives copyright holders a certain amount of control over the consumer electronics and PC markets)
Otherwise.. can argue to the copyright office for an exception.
After all, all I want to do is to be able to legitimately play blue-ray movies on my computer. I have no desire to infringe copyrights at all.
I wonder if anyone has made an over-broad argument in a DMCA case before..
I have a slightly less technical question. I’m looking to buy a new home theater set up in the coming year. I’ll be starting from scratch, and I’ll be going high(er)-end. Buying all HDCP compliant items WILL be an option for me, but I don’t want to buy anything that will “self destruct” if I try to play “unapproved” hi-def content. In other words, where I get my content from is my business, and I surely don’t feel that the industry has the right to sell me “crippleware” or “self destruct” products. As far as the home theater set up goes, I was looking at Samsung’s new 1080p/120hz LN-T4671, Samsung’s new BD-UP5000 BD/HD-DVD player, and a Denon reciever (either the 3808CI or the 4808CI). I’d mostly be playing “legally” purchased content on this set up. I am a videophile/audiophile, and I like to collect DVD’s, so switching to buying Blu-Ray/HD-DVD discs doesn’t bother me. I don’t watch TV, so there will be no TiVo or cable/satellite boxes in the equation. Purely BD/HD-DVD/DVD movies, and later a “media center” PC. What I AM concerned about is whether or not my components will “self-destruct” under the following possible circumstances:
A) I insert a bootleg copy of “premium content” media into my BD/HD player
B) When I get around to buying a new HD capable PC, I insert bootleg media into one of the drives, or download bootleg “premium content” and attempt to play it on my home theater
C) I create my own “premium content” on my new PC, said content obviously not being “approved” by the industry and thus not able to execute the “hand-shake”
So again, since I’m starting from scratch and planning to shell out some cash anyway, I don’t mind adopting the HDCP standard on all my devices, as long as it isn’t going to restrict what content I can view or at what resolution I can display it.
What should I do? Wait until the industry realizes they’re fighting a losing battle and buy the inevitable clean hardware when it comes out? Or will they ever become sane again? Might not the next gen DRM bullshit be worse? And what is going to happen with “premium content” on platforms other than Vista or Mac? Microsoft has now pissed me off… Right off of their list of customers…
How relaible are the hacks and work-arounds for this type of gear? I’m more than willing to “unlock” my devices if necessary, I just don’t want to put my multi-thousand dollar set up at risk with crappy modifications, or reduce its functionality by having to perform some rain-dance every time I want to play “ILLEGAL” content.
Thanks for the help guys! I’ve only been researching this for a few days.
Thanks, makes a lot of since but you will need more than algebra one knowledge to solve it. Maybe a good algebra two student using a matrix and row reduction could. Anyway thanks for the information it is what I initially thought.
For those who claim that capturing HDMI is not practical for the next 10 years… look at this product:
http://www.blackmagic-design.com/products/intensity/techspecs/
Hi there,
I have recently designed a model of this HDCP in both C and verilog.
Its not too hard, just time consuming.
I used the HDCP spec 1.3 here : http://www.digital-cp.com/home/HDCP_Specification%20Rev1_3.pdf
In the Appendix A at the back, the spec prints off 4 different key sets and does sample calculations to show how exactly values are calcualted.
Now my project is completed i am wondering about these “sample” key sets in the Appendix. Are they actual valid key sets? Could they be used to interface with a real receiver/trasnmitter chip? Surely not, they must be invalid somehow. If they were valid wouldnt that mean that all what’s been discussed here is null and void already? The keys have already been leaked!
I tried to interface my code with a real receiver and the Ri it gave back to me was different to the Ri that my C code calculated, which leads me to believe that these keys are actually invalid somehow.
But im not sure, it could be a bug in my code, but i think not as i’ve tested my code over a few different test cases and it seem ok.
Any idea’s?
Would digital-cp just publish a valid key set like that?
Thanks!
John
There is another alternative. Use a program similar to decss to decode the video on the disk itself. Transfer the file to another media format or even re-burn it to another dvd and enjoy. You can have HD formats in mpeg 4 files. Once you have it in that format you can do whatever you want with it. Basically what im saying is rather than crack it as it streams crack it as a file on the disk itself. By all means though go ahead and do what you are talking about.
Above all the cryptographic problems, conspiracy problems and other, why not waiting some weeks to see 41 numbers to be black listed. these code will be writen in the newest hddvd but will be fully operationnal for the hdDVD who are a little older. this mean if we are able to get these number on the hddvd (i think) it is posible to solve the conspiracy problems and get the numbers of our reader.
Just a few comments, to help correct some common misconceptions about HDCP:
HDCP devices are divided into “transmitters” and “receivers”. The secret vectors for these are not interchangeable, except for certain trivial corner cases. This is important because it alters the way the vector math works in some ways not foreshadowed by Mr. Felten’s original paper, and most of the discussion here (a very few people have tried to make the point, but most of the rest didn’t listen).
HDCP repeaters are both a “receiver” (on the upstream side) and a “transmitter” (on the downstream side). So a compliant repeater does contain two sets of secret vectors.
HDCP protects only the link itself… the wires and the silicon at both sides. It doesn’t protect the DVD, or signals inside the TV, or anything else.
Roger Says:
December 27th, 2006 at 12:20 pm
A number of people here have commented on the amount of storage required to store a complete uncompressed film if it could be captured after the HDMI encoding has been removed.
One thing to consider is that the signal is digital not analog so 100% clean and that the player is likely to support pause (with image) and single frame advance.
Roger – not entirely true – see this article for a more in depth explanation
http://forum.ecoustics.com/bbs/messages/34579/122868.html
A number of people here have commented on the amount of storage required to store a complete uncompressed film if it could be captured after the HDMI encoding has been removed.
One thing to consider is that the signal is digital not analog so 100% clean and that the player is likely to support pause (with image) and single frame advance.
The result is that you can just have a PC advance the film a frame at a time and capture just the frame. A single frame will allow high speed capture to memory rather than disk. Basic compression can then be used on the frame to reduce the amount of disk storage required. The result is a system that needs say 2 x 750GB disks and 4GB RAM so bringing the system build cost down.
To capture the audio you would just replay the film.
Roger
Why not make a special “Y” Cable Connect HDMI Output (HDCP Compliant) to indut HDMI Input (HDCP Compliant) and add a spy connector that is independant of the handshake channel and wired to be invisable to the others. Sure you would get a 3db loss. I would never do this because it would be illeagl.
This is so depressing. I was going to buy a widescreen HDTV for xmas…but I guess back-packing India it is!
I think that there is a general misunderstanding that the keys associated with HDCP reside on the DVD that you put into your player. For example: “To play HDCP discs, you need a HDCP drive and a HDCP monitor†and “The issue of why we need to break the space of 40 keys is that any time a key is known to be broken or exposed it can be revoked by all future DVDsâ€.
I am here to inform you that the copy protection does not reside on the DVD. DVDs are protected under CSS and, at times, other levels of copy protection, but not HDCP. HDCP is a protection between your HDCP TV and your HDCP DVD player, to protect the cable from some kind of pirate termite that wants to hack your signal and steal your video.
HDCP will prevent playing any disk, VHS, or other video input to that DVD player across the HDMI or DVI cable protected by HDMI. For example, the implementation of HDCP will prevent you from watching your family videos recorded by your cam-corder over the digital HDMI or DVI cable connection if your TV is not HDCP compliant. I believe this should be illegal.
I couldn’t care less if original, legal DVDs do not work on most computer monitors over their DVI input. I think it is ridiculous that someone can stop you from playing your family DVDs over your computer monitor off your DVD player, when it is perfectly capable of doing so, and so is your computer.
HDCP protection should be limited to companies who purchase such a protection for their own content. No one has the right to corrupt my own content or limit the use of my DVD player when it is playing unprotected content.
Now I have a doubt: If we break HDCP protection, do we still need a HDCP device (monitor and video card) to play the content? Because, since non-hdcp devices don’t have that “handshake”, we can never discover its codes (it don’t have any codes!!!).
Paul,
Since you NEED HDCP devices to play HDCP-protected content, I think it will not work if you simply REMOVE HDCP from the device firmware. Because, if you put a HDCP protected disc to play on a NON-HDCP device, it will simply NOT PLAY. To play HDCP discs, you need a HDCP drive and a HDCP monitor. So the only way is to BREAK the HDCP protection… and I think it will be easier on computers, using a software for that…
Guys,
Aren’t we going about this the wrong way?
Surely the simplest approach is to disabled the HDCP in the DVD player to start with.
I have update various DVD players over the years with ‘firmware’ DVD’s downloaded off the net in order to remove Regioning and Copy Protection code…. how long before some bright sparts provide us with updates for the next generation that removes HDCP.
Of course, if your silly enough to by Sony, this will never be a reality anyway!
Paul.
The whole point of the encryption was not to get rid of piracy. If they wanted that, they would have put some ungodly military-grade encryption through the cable rather than this wussy form of protection. They want the encryption there just so they have an excuse to sue people.
But what’s to stop a store 20ft across the border from America to Canada from selling a dongle to strip out the encryption? As soon as the scheme is cracked, and a mathematical model is made to emulate the central authority, what’s to stop a company outside the US from making a nice, cheap dongle? Better yet, since it sounds like a dongle such as that would be entirely digital, why not have that company “accidentaly” leak a set of plans that anyone could build with stuff from radioshack? I admit I know nothing of the construction of equipment such as this, but it just seems too easy.
I may be wrong, but it seems to me that it is possible to recover a key without having any compromised keys at all. The trick is that you know what the monitor is going to do with it. If I’m wrong, someone please explain why I am but this is just the first thing I thought of when I read the article and a bit of the spec.
For what I’m thinking of, let’s talk about Alice and Bob above. We’ll say that Bob is an imposter, and Alice is the key we’re trying to find out about.
Let’s say Alice and Bob above swap their addition rules. They then do their addition magic, and agree upon their shared secret key, the number 26. Since Bob is an imposter, he doesn’t know about the 26 though. Nonetheless, they’re ready to talk after the addition rule swap. The idea is that Bob will take some byte which I’ll call X, then encrypt it, then pass it to Alice. This is what Alice is expecting.
But – if Bob is on our side, he doesn’t have to encrypt X. He can simply pass the value of zero. Alice will receive the byte and say “Aha! This is Bob’s encrypted content. I’ll decrypt it by XORing it with 26 and pass it to the display.”
And since zero XORed with 26 is 26, Alice will broadcast her secret key to the device. Yes, I know that in the spec Alice will use 26 as an input to a pseudo-random number generator and use that, but since the pseudo random algorithm is known, for all intents and purposes she might as well be using the original 26.
Since Bob passed her the rule [2]+[4], we now know that Alice[2]+Alice[4] is 26. Repeat using different addition rules, and you can receive your independant set of linear equations rather simply.
Anyways it seems that way to me. It can’t be that easy, can it?
http://www.eetimes.com/story/OEG20010521S0035
ok i know nothing about all this stuff but the need to have 40 divices to “crack” HDCP is not completely clear to me.
The content on HD disks will be encrypted using HDCP. Otherwise you could just catch this data stream halfway somehow. The disc does not need to know the common secret number because it does not need to write or decrypt anything. However, the encrypted disc must pass the public vector so the apparatus can figure out the “common” encryption number needed to decrypt the HDCP encoded data stream from the disc.
So although there is no need to place the secrete number matrix on the CD the vector that needs to be past will be. Also if one would find out the secret “common” number which is used to encrypt the data stream you should have the public vector of the CD, (possibly) the public vector of the apparatus, secrete number of the apparatus and the (implied) secrete number of the CD.
So don’t you just need 40 encrypted Cd’s?
Once enough keys are stolen, it is possible to generate as many keys as you need from that set.
From the example, I generated a vector for a KSV of [3]+[4]
9,10,15,17
for the “HD is too much bandwidth OMG” people:
http://www.blackmagic-design.com/products/hd/
these are not expensive. no more than one would spend on a top end graphics card for playing doom3 or whatever.
so really anyone can do it with a moderately high end machine and some NLE software.
add to that a lo-fi HD format like HDV or what have you and it turns out you can fit quite a bit of video onto that rather ordinary computer. then there’s DV100, which is very high quality indeed and not too big to be useless.
also consider that pirates don’t care about quality, and neither (largely) do consumers. i’d gladly watch a DVD over an HD-DVD if it means i can actually watch it without fuss, and i’m sure the pirate DVD industry will keep going strong for years to come (consider how much “handycam-in-theatre” stuff there is out there. people still buy these and think they’re getting a bargain).
It would be much easier to just pull your flat pannel appart and capture the stream post decryption.
LCD screens are made by a handful of manufactures (mostly in China & the South Pacific). They all produce similar parts that are widely interchangable (though with sligthly different part numbers; if you know the right part number you can get replacement parts much cheaper).
These screens are then purchased in bulk by companies who build the interface boards (Apple & Dell for example).
To make a dongle you would just need a compliant monitor and a copy of the interface specs the screen uses. Pull the screen out and build a board that can capture the raw data post decryption.
Just a little social engineering is needed to get the specs, they aren’t trade secrets as their product is compatible with thier competitors.
Probably take 5 years for them to put the encryption into the actual screen and not the controller board.
If the private keys corresponding to 10 linear independent KSV’s are leaked, then the private key for any KSV in the subspace generated by those KSV’s can be forged. As there are at most 39 linearily independent KSV’s, if all of them have their private keys leaked, then *ANY* KSV can be forged, totally usurping the central authority.
However, if only a handful, 20 ksv’s are disclosed, then an attacker could forge a large number of KSV’s: any KSV in the 20-dimensional subspace. The only setback is that the spanned subspace may not be convenient for finding a well-formed KSV which must have exactly 20 1’s and 20 0’s. Once a well-formed KSV is found, the private key is forgible. (Finding a KSV could entail either brute force or using the Lenstra-Lenstra-Lovász lattice reduction (LLL) algorithm for a simpler repsentation of the spanned subspace.)
Remember the original goals of the defender: Assume a few keys will be leaked. If a single leaked key is widely used, then it can be easily blacklisted. The ability to forge a large number of keys makes this strategy useless.
Matt Mastracci, such a forged key for a display device would work for any transmitter, if the KSV’s were leaked by a display. If we had 30 transmitter KSV’s, then we could also forge an authentication — by emulating the transmitter’s side of the computation. In this case just transmitters within the subspace spanned by the leaked transmitter KSV’s would work. In HDCP, display keys are more valuable than transmitter keys.
rew:
> Now the mathematcial question I’m not sure about is: Suppose I have 40 private keys, but they are linearly dependent to 30. So now the question is: Would this mean that we can calculate all private keys belonging to this 30-bit subspace? Or would we not have enough information to do this?
Absolutely. That’s why it’s in their best interest to use as many bits as possible for each key.
Even if we don’t end up with 40 private keys, we might still end up with 30 or so that are independent over a given key subspace and crack “most” of the private key. The only problem is that those keys would only work with other devices within the same 30 bit subspace, AFAIK.
There is an obvious flaw in HDCP if the only goal you have is to get to the unencrypted stream and you have any one set of compromised keys and a non revoked receiver to handle the handshake for you.
Setting up a regular HDCP link between a valid transmitter and receiver will reveal enough information on the I2C bus for anyone with any valid keyset to calculate the link key (if the receiver can calculate the key, so can the listener) Since the listener never sends its key mask (and thus cannot be revoked), the transmitter will happily start sending data and the listener has the key…
i’m being a little slow on the math at the moment […] could you do anything neat with a really large set of addition rules but no secret vectors?
jig,
I guess I might be slow too: I’m still trudging my way through the proofs in the Crosby, et al. paper.
But as far as your question goes, once you have a set of KSVs which spans the submodule used by the key authority, then you have all the information necessary to generate any tuple in that submodule. (See footnote 1 on p.6 in the PDF).
Or, to try to answer your question more simply, once you have acquired a number of independent “addition rules”, then acquiring more “addition rules” does not increase the information you have available. Perhaps someone else can phrase that concept more elegantly than I…
sorry, i meant to say that i don’t think that there will be updateable blacklists for the hdcp keys, just the aacs keys.
i don’t believe that the hdcp keys are going to be updateable, just the aacs keys.
hdcp is not on all the time by default. it is triggered on by either the video being encrypted or by macrovision (i haven’t been able to determine which, if not both trigger). you can test yourself with a dvd and one of the scaling dvd players (supposedly required to use hdcp). take any retail dvd, strip macrovision and decrypt the vobs and then burn back and play. hdcp won’t trigger.
displays don’t decide and they don’t deny. they will respond to hdcp handshakes if queried, but they will accept any video, hdcp protected or not, and display it. this facilitates you making your own video and not having to pay licensing fees to aacs ltd and hdcp ltd just to get it to screens.
there is already a device that effectively strips the hdcp signal. i believe it came about because there needed to be a simple way to switch video inputs or double outputs (2 or more screens at once)… regardless, it’s a little box with hdcp responding ports on one side, and vanilla digital video on the other. i am almost positive that there is no point at which the video is analog somewhere in the black box.
i believe that to be vista capable, computer video cards will have to have the hdcp logic in the gpu somewhere. so there is no separate hdcp “chip” you can snoop (otherwise it really wouldn’t be that hard to build an hdcp-free daughter card).
i’m being a little slow on the math at the moment. i get the approach above, including the gotchyas talked about in the comments… but could you do anything neat with a really large set of addition rules but no secret vectors? each addition rule (paired with some other rule) limits your key space, further limited by the knowledge of the size of the key. the one thing that i’d hope a large group of people could do quickly in parallel (and probably legally) is get a bunch of addition rules from their own equipment.. and we’d only need display keys by the way. no-one should care what the transmiter keys are, frankly, we just want to emulate the display devices (displays don’t deny) to trick the transmitters into transmitting to a device that doesn’t play by the display device rules.
anyway, maybe i’m not quite imagining how many addition rules we’d need to limit the keyspace enough to make decent educated guesses… i’ll think about how many addition rules we’d need to figure out the dummy case above (2 digit numbers, 4 in each secret vector, sum 2 to get 3 digit number) to get an idea. or maybe a simpler system….
Another strange thing is the extensive list of signatories to the HDMI system. Perhaps the membership fee is peanuts, but I wonder if they really expect to prohibit any non-members from being able to manufacture devices with HDMI signals and connectors.
Can they really have international patents on a mere connector? Or do they just need a big litigation budget to achieve the same effect?
Aren’t there laws supposed to prevent a manufacturer from excluding interoperability?
Is this a pact made in hell? Hollwood gets to control the content, HDMI gets to control the hardware. Consumers get to pay, and choose the colour of the boxes, but control nothing, except perhaps the on/off switch.
If you get 40 independent keys, what you can do is you present a random KSV to the other end, and calculate the private key that belongs to that KSV on the fly.
If you build this into the HDCP-stripping-dongle, the dongle cannot be banned. Every time the link authenticates, the dongle will select a different KSV….
Now, sending a company that buys 10000 keys from the central authority some highly dependent KSVs is a good idea: If someone finds an easy way to steal the private keys from this one /type/ of device, you’ll have a highly dependent set of equations, leading to less leaked information.
Now the mathematcial question I’m not sure about is: Suppose I have 40 private keys, but they are linearly dependent to 30. So now the question is: Would this mean that we can calculate all private keys belonging to this 30-bit subspace? Or would we not have enough information to do this?
Still, the central authority could then try to ban this 30-bit subspace, banning the easy-to-open devices, as well as the dongles derived from them.
UniDyne,
The issue of why we need to break the space of 40 keys is that any time a key is known to be broken or exposed it can be revoked by all future DVDs. Since the key signature, the addition vector, is specific to a single device, they can selectively revoke the device. To be able to work arounf that you need to break a large enough subspace so that it’s impossible to revoke all of those keys. Ideally you break the whole 40 dimensional subspace then you can create a universally un revokable system. Game over.
To what end?
Why do we want to find the key to the source device anyway? We would already have a sample set of keys to launch our attack. We only need ONE AUTHENTIC KEY to authorize ourselves as a valid HDCP device and capture the stream or feed it to a non-HDCP device. If you need 40 keys to compromise a single key, what’s the point? YOU ALREADY HAVE KEYS!!! And the results of the key exchange aren’t broadcast over the wire anyway – only the addition rules that are needed to make your key return the same result.
The obvious problem would be key revocation. Okay. So what’s to stop us from figuring out how to generate mathematically valid keys? It’s only 40 bits and there is plenty of computing power out there…
I expect the blind spot has been caused precisely because the industry couldn’t (and still can’t) conceive of people wishing to distribute and view copyleft HD works.
DMCA doesn’t need to be integral with the work (I expect they checked this), it needs to protect against unauthorised operations on copyrighted works.
There would need to be some other EULA, e.g. “By purchasing this device you agree not to utilise its highest resolutions for anything except HDCP permitted works”.
We simply have to demonstrate that a customer of an HDMI device has a right to enjoy all its capabilities for copyleft works (or copyrighted works where the copyright owner has expressly forbidden any TPMs from preventing access or performance of the work at any fidelity).
Crosbie Fitch Says:
“It seems to me that to REALLY break HDCP you have to demonstrate that it is not protectable by the DMCA.”
That raises an interesting question. Doesn’t the DMCA presuppose that the technical measure being provided with protection against circumvention is in some way an integral part of the work being distributed?
Once the technical measure is independent of a work, what is the position with circumventing it for some other legitimate purpose.
Another question that needs answering. Supposing someone wants to distribute (their own) high-res movie without any copy protection at all applied. Will such a movie be able to be played through the digital connection on a system that comprises an HDCP device connected to a non-HDCP device.
It would be quite interesting to see how this actually pans out when put into production. They will have to know that the production costs, bad press, irritated customer, etc. will have to outweigh any perceived benefit they may be getting.
It costs a lot more to try to stop piracy than piracy actually costs itself.
It seems to me that to REALLY break HDCP you have to demonstrate that it is not protectable by the DMCA.
One way may be to create a DVD licensed with CC-SA and attempt to play it back on an HDMI TV.
Then someone has to prove that circumvention of HDCP is being performed in order to compromise copyright – which it obviously isn’t.
This then legitimises sale of HDCP circumvention devices.
One more thing occurs to me. There’s a glaring missing element to the HPCP specification. How do the movie makers know which addition vectors to ban? That is, if a pirat outfit manages to get ahold of just ONE single key set, they can use that to decode movies forever until the addition vector gets revoked. So there has to be some way for the movie vendors to inspect a pirated move and determine what key/addisiton vector was used to acquire it.
Thus it seems like they must have to also watermark the movie with the addition vector so they can discover this. However this a somewhat of a tricky task. Inthe watermarking method is known then possibly it can be erased too. The movies that are prirated will be compressed too so the watermark has to be robust under recompression.
Any one know the asnwer to this one?
If not then it may be this requires no math at all crack, just one key set.
oops I meant to say I assume it’s per device not per model.
Matt, thanks for the link to the paper.
I read the algorithmic sections carefully and skimmed the rest. I could not locate in it the place where it says there are 20 public keys and 20 private keys. (I do understand they have 20 one bits and 20 zero bits in the addition vectors)
But I do see now that addition vectors are supposed to be unique. I wonder if that’s unique per model or unique per device. If it’s per model then if they revoke an addition vector then they screw everyone with that same model. I wonder if that’s what they are contemplating. So I assume it’s per model.
So if we assume that it’s intolerable to ban large numbers of innocent devices, then here’s the strategy a hack can use. First we don’t need to achieve a perfect 40 bit subspace knowledge of the keys. We just need to be able to generate valid shared secrets for a large enought subspace that banning all of that subpace would pull in tens of thousands of innocent units–and I’m assumeing that revoking that many innocent players to snuff the pirates would be unacceptable.
To achieve that would require much less than 40 linearly independent keys. It would require knowledge of around 12. Which would be more easily achieved.
In any case, It seems to me that they can limit their exposure to a universal unbanable 40 bit keyspace crack by making sure no one manufacturer ever gets the full 40 bit key space. if they can assure that then it becomes a practical impossibility to get leaks from a sufficient number of vendors to get the required 40 linearly independent sets. I note that it would take a lot more than 40 vendors to conspire since many of them might find their addition vectors were linear combinations of other vendors. I’d expect that it would take about 50 vendors to assure a reasonable chance of getting 40 linearly independednt vectors.
Also as I have pointed out before they can assure that at least all future players are not cracked instantly by reserving some bits (or basis vectors) that are only dolled out in future years. But that’s simply a race that depends upon how fast leaks occur.
So I still stand by the practical difficulty of getting all 40 linearly independent basis vectors.
However as I just pointed out, the pirates can win if they can simply get a big enough subspace of the keys mapped so that revoking that entire subspace is unacceptable. That might require as little as 10 to 12 linearly independent addition masks. That sounds a lot more plausible to me than getting 40 to 50 manufactureres to conspire.
So I guess what I’m saying is that
1) The conspiracy required to span the 40 bit space is potentially much much larger than Ed’s article suggests.
2) But you don’t actually need to span the full space to reach a point where it would be untennable to revoke the all the pirated shared secrets.
finally, I’m really curious about how they compute the key sets. It’s kind of amazing that there’s sets of numbers that you can use that assure they sum to the same shared secret using all the different key and addition vector combinations. It’s a cute trick. What’s the math behind it?
Oh and one more thing. There’s two simplifications in Ed’s math that we have not discussed the importance of.
1) the shared secrets are not formed actually the sum of the keys but the modular sum. this means that standard linear algebra wont actually work to solve for the key values. I think there will be a large number of ambiguities inthe key values introduced by this that have not been considered in solving the equations.
2) While I argue above that it only may take solving for a subspace of 1o to 12 bits to win the game, I have not carefully considered what fractions of the subspace formed by taking 12 linearly independent addition vectors also meets the requirment of the addition vectors having 20 ones and 20 zeros. It might be quite small, in which case one needs to expand my minumum criteria.
Can the DMCA outlaw a device that contains a FPGA that is not programed to do anything (yet)? Then it would be a simple download from the web to purpose the device in anyway you desired. I guess at that point you (in the USA) would need to ponder the DMCA, but before the download such a device is technicaly generic and not relevant to the DMCA. If the device takes encrypted programs then only at the point where it programs it’s FPGA would the DMCA matter, because the user can’t tell what the program contains therefore they can’t know/prove for sure if it is against the DMCA. Once decrypted content data started to flow from the device the would be no question of if the DMCA could be relevant. This shifts the policing of the DMCA from controling hardware to controling end user behavior, which is impossible. Busting the true pirates who take the decrypted content and resell it will not change, but the principle of “fair use” looks safe enough to me. Time will tell, until the dust settles I’m not going to waste a cent on anything touched by this issue and I suspect that millions of other people will do the same.
Lets assume the company never re-uses an addition vector when it sells to two different people. […]
Next if they re-use keys […]
charlie,
See the HDCP Specification, Rev 1.1 [PDF] (via Wikipedia) on p.6:
Also note p.52:
Unless I’m misinterpreting, the specification apparently requires that KSVs are never reused.
Although, if you were actually saying that in operational practice, some vendor(s) may fail to follow the specification…
Question – I have the Dish Network HiDef package. I do not want to get the Dish Network VIP 622 DVR because it is a $300.00 lease … instead I want to buy a HiDef DVR and connect it to my VIP 222 HiDef receiver … I understand that due to DMCA I cannot do this and the HDCP handshake will FAIL … is this true and is it true that I cannot connect a 3RD party DVR to my HiDef receiver?
Karthik,
I do not have the faintest clue what you are trying to say. Perhaps you’re responding to a particular post? Or not? Either way, more English sentences interspersed among the mathematical sentences might help to get your point across more clearly.
Another weakness that lies outside the math and more in the realms of social structure: There are thousands of companies that might afford to buy codes for legitimate hardware.
Now, assume one of them does not play fair and has a version of the hardware in the back room that allows them to output unencrypted data and save it to the disc. Now they have a full version unprotected. They can go on and sell it to the real pirate industry, which will flood the markets with the pirated goods. The pirated version will be superior to the genuine one. What can the industry do now? There’s a leak in the system but they’ll never know who’s leaking.
Currently there’s leaks in the production stage already and I wouldn’t think it’s too far stretched to think that the “pirate industry” couldn’t afford mailing one disc to be processed somewhere. All it takes is one key, and no one will ever know what was the key used.
ccorn,
See the Crosbie, et al. paper at the top of page 5 (in the PDF). (Small) sigma is defined as a transformation from a (40-tuple of 56-bit elements) to a (56-bit element). The authors quickly note that sigma is a linear transformation.
Each “addition rule” or 40-bit “Key Selection Vector” (KSV) naturally corresponds to a particular 40-tuple of 56-bit elements. That is, the 40-bit KSV can be considered as a 40-tuple of single-bit elements, and a single bit has a natural, unambiguous representation in 56 bits.
(Small) sigma of every valid KSV is 20, which is a multiple of 4.
ok. … in response to the “raw signal is too big to store” crowd..
Currently there is no hardware cheap enough to do it.. but what’s to prevent some taiwanese firm putting together a small box which can compress it using a set of $50 dedicated compression/decompression chips and spitting it out a firewire 800 cable?
charlie strauss:
I think you need to read the HDCP spec to see how it works. The 20 of 40 bits that each player advertises are *public*, allowing us to know for certain what keys they are using.
Each any every one of those public keys that we can read from each and every HDCP device advertises exactly which 20 bits it is using. If we analyse a little over 30 devices and see that they use the same 30 bit indexes (the rest always being zero), we will likely be able to solve the linear equations to recover the secret keys.
It is very unlikely that they would be able to generate 10,000 keys for a single manufacturer while ensuring that they are linearly independent with every other single key in existance.
They probably chose 40 as a good number that trades off between storage space (you need one 56-bit key for each of those bits) and security. Adding extra bit doesn’t really buy you anything – if we were able to generate keys anywhere within the first 20 bits of a 1000, that’s still a huge keyspace for us to play in. They can’t just cancel the whole keyspace either – that would kill a lot of innocent devices. So, as you can see, it’s in their best interest to use as many bits as possible without saving any for the future.
Note that they won’t re-use addition vectors between two companies because blocking one device would then block some other device randomly somewhere in the world. I would put money on the fact that every addition vector is unique to a single device globally.
Here’s the spec – you should read up on it:
http://www.digital-cp.com/home/HDCPSpecificationRev1_1.pdf
This definitely strikes me a protection for the sake of protection, pirates will pirate the content, no doubt about it. But in the process X% of customers will scratch their heads and take TVs back to the shops complaining that “It just comes up ‘Not Supported’ when I put in my Terminator 4 Blu-Ray Disc.”.
In response to what can be done in hardware – the requirements are not trivial, but eminently do-able in standard FPGAs from a number of vendors. The stream rate probably forces the cable to be parallel (in some fashion) unless the cable is very short.
I have designed InfiniBand physical layer equipment (including the PCBs) and the cables for standard IB (2.5Gb/s per pair) are expensive [$50 each typically at moderate volumes with a minimum order quantity of 500], and for 4x do not exceed 10m [this is a physical issue for cables].
If HD wants to be a consumer item, that price has to go down. Given the requirements to make the cable, that means shorter cables or a relaxed signal spec.
Even if the stream were on a single pair, there are FPGAs available (such as the Xilinx Virtex Pro series) with IOs capable of over 3Gb/s, with typical prices of about $60 each in moderate quantities.
So how much would it cost to make a universal decoder? Probably less than $1k (much less) in moderate quantities (
With regard the blacklist updates, I’m picking each update will have a version number and the latest version will overwrite the previous. How long before we see otherwise blank dvds coming out with very late version numbers and an empty blacklist? If your key has been blacklisted, drop in a DVD, wait 30 seconds and you’re away. I guess the version numbers will be covered by the DVD encryption?
who cares about DMCA? I dont live in USA and even if we DID have a DMCA I would ignore it wholeheartedly.. I’m sick of being treated so badly by the industry, only reason I buy dvd’s is because they have been cracked. I am not skilled enough to take advantage of whats posted here but if I was, I would see it as my duty to crack it for the sake of evening the playingfield between the consumer and the industry just a bit because at the moment its tilted around 80 degrees in their favour.
Neo,
You are right that if they slowly enlarge the subspace that the mathematics of the crack become somewhat easier. But I don’t think the difficulty of the math was ever the limiting issue.
The big danger for the company is if some one were to make a universal decoder dongle that worked in perpetuity for all present an future devices. by slowly enlarging the sub space they could assure that any decoder dongle would not work on any future player only on the old one (unless it were reprogrammed). While that might not be a limit to many people it would limit the value of it to the general consumer and illegal inhibit dongle sales.
matt,
If they limit the key space to 30 basis vectors (initialially) then one is still confronted with a daunting problem. Any one manufacturer might only get a very small slice of the basis vectors. 15 basis vectors would be enough for 10,000 unique addition rules. But actually you might be able to make do with even less that that if you could re-use the same basis vector with different keys (not sure if the logic of the internal key generaiton algorithm would permit that).
Now lets take some big “If”s and see what happens. Lets assume the company never re-uses an addition vector when it sells to two different people. And let’s assume that it decides to use my hypothetical 30 bit sub space. and let’s assume they are stupid enough to tell us which 30 bits (or equivalently 30 basis vectors) they are using to generate all these keys.
Then we would still have to get 30 different manufacturers to leak to us their data sets in order to get all 30 basis vectors and responses. That’s a non-trivial task. A lot more than just getting 30 devices.
Now lets relax those assumptions. Maybe they don’t tell us the basis vectors, so we have to keep looking trying to span an unknonw number. e.g. suppose we had stolen codes from 20 companies. Are we done yet? we can now span some subspace but is it the full subspace we can maximally achieve or should we keep looking for more. we won’t know till we run into a device that we can’t hack.
Next if they re-use keys then it’s likely it will take a lot more than 30 leaked key/address sets to span the space since a lot of the leaks will be redundant.
And of course as I pointed out, they can keep enlarging the subspace each year so new devices can’t be hacked with an old decoder dongle.
But of course that won’t stop an old player from continuing to work with a old decoder dongle. So people will be able to decode the streams once they manage to crack one of the devices.
If I were the people designing this code I think I’d add one more layer on it. I’d have multiple addition rules per player and then I’d let the HD dvd select which addition rule to use. Initially all DVDs made in 2006 would only use rule 1. then as systems got hacked, newer DVDs would go to rule 2 which would include basis vectors beyond the original substace and thus confound the older dongles.
I’m a little surprised they limited this to a subspace of 40. Why not make it 400 or 4000, to give them more room to play this shifting the basis vector game?
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]
let’s take:
Alice: x1+x2 = 26 — 1
Charlie: x1+x3 = 22 — 2
Diane: x2+x3 = 10 — 3
from 1 and 3 (subtracting 3 from 1)
x1 – x3 = 16 — 4
x1 + x3 = 22 — 2 (adding the equations 4 and 2)
————————-
2×1 = 38 => x1 = 19
from 2, x3 = 22-x1 =3
from 3, x2= 10-x3 = 7
(or alternatively from 1) x2 = 26-x1 = 26-19=7
From this:
Bob: x2+x4 = 13
or: x4 = 13-x2 = 6
It is said that in a matrix of nxn coefficients, solving the matrix product:
AX = B (where A is the coeff matrix, X is a matrix consisting of: x1,x2,x3 and B is the RHS matrix)
can lead to an unique identifiable solution if and only if:
A-Inv B i.e. A-Inv exists, or Adjoint(A)/|A| exists or the determinant of A is not zero.
for that, it means that you can’t have redundant information of the variables…
example:
x1+x2 = 2 — 1
2 x1 + 2 x2 =4 — 2
which essentially means a lot of possible values for x1 and x2 because both equations are equivalent.
Also note this example:
x1+x2 = 2 — 1
x2+x3 = 6 — 2
x1-x3 = -4 — 3
i can write the third equation as: eq 1- eq2
Which means, i can solve this set of equations, but not with a unique solution. When i say not unique, i mean a set of another equations of the form:
x1 = k
x2 = 2-k
x3 = 4+k
which means, k can take many values, say: 0,1,2,3 …
and my vectors would be:
k=0 (0,2,4)
k=1 (1,1,5)
k=2 (2,0,6)
k=3 (3,-1,7)
if my third equation were: x1-x3 = 4, then notice that if i formed a fourth equation from 1 & 2, say:
x1-x3 = -4, it would become quite contradictory to what the equations were.
So, that’s not a set of solvable equations at all.
🙂
also, verifiable:
| 1 1 0 |
| 0 1 1 |
| 1 0 -1 |
has a determinant of 0. verify it. 🙂
I hope this only clears up the algebra part 🙂
About the storage need and bandwidth…
HD content, is only 125MB/s @ 1080i (1.25Gb/s), and 250MB/s @1080p (2.5Gb/s)
Nowadays hard drives handle easily 40MB/s sustained, and have 250GB or more.
If one uses 10 drives in parallel (RAID0), the 250MB/s is easily achieved. Now 250GB x 10 = 2.5TB, @250MB/s => 2h45m, more than enough to capture a whole movie.
Compression is not really an issue, a decent computer will handle the task in less than a week, just a few days. I have not done this part, but my pc is able to compress NTSC SDTV at about 24~25 fps using mplayer (duron 1.3G, linux), 80% of realtime. Given that HD is basically 10x more, one can get 1fps at least. A 1080i movie is 90m long ~= 162000 frames, compressing at 1fps ~= 45hours. Nothing to worry about.
The RAID0 array is an easy one, adaptec has some pretty ones with PCI-X and 8 SATA, an handle the bandwidth.
Of all these, maybe HD-SDI hardware is the complicated part, but a decent hardware engineer can use off the shelve chips to do it. National has some pretty serial HD-SDI -> parallel HD-SDI ones, plus some FPGA.
Note: B=bytes, b=bits
In the end, for a established pirate, or the wannabe one, these hardware is not an issue, is cheap $15000 or less. Pirates be delighted! For hobbists… well not easy, the one that don’t do the real harm, for them the system doesn’t work. Viva la DMCA!
Ivan
Wait a minute, that was idiotic. Ignore my last post.
The sample is unsolvable. Observe
x1 + x2 = 33 *2 ==> x2 + x4 = 66
x2 + x4 = 18
So 66 = 18? I have my doubts
ebfe: HDCP actually uses 20, not 2, items in the addition rule. This puts the total number of keys at 40 choose 20 = 137,846,528,820. This is still not that big a number, though, and keys can be generated at will.
Vorn
SteveR: HDCP has various anti-tamper requirements which would render that approach more complicated, but not impossible. One is that the same chip which decrypts must also decode, so there will be no convenient PCB track carrying the unencrypted information. That means even if you can intercept the analog HDTV signal, you still have to handle a DAC-ADC-reencode. Not ideal quality.
A place I see potential vulnerability is PC DVD players. Part of the AACS licence requires that software players authenticate display cards to ensure they support and use HDCP. I wonder if the drivers might be a potential area to exploit.
despite the bit-size of each value in the key vector:
if only two out of 40 values are summed up, there can only be 780 unique solutions at all within the whole hdcp system.
let’s think of a 4 value vector (x1,x2,x3,x4). The possible rules are:
x1 + x2 (==x2+x1)
x1 + x3 (==x3+x1)
x1 + x4 (== … )
x2 + x3
x2 + x4
x3 + x4
as you might already guessed the number of possible solutions is equal to (n-1)*n/2.
This is rather funny as only 780 out of a 2^56 possible values are used. Any device can trick any other device by a chance of 0,12%
FPGAs are large/fast/cheap enough to do the processing.
I’ve seen much more impressive video stuff done with FPGAs
in a friend’s garden shed. He’s good tho. I’m not going
to write the VHDL, legal or not.
brucee
I have two questions concerning apparent shortcomings in HDCP. I realize that neither of these questions deal specifically with cracking HDCP technology, but simply represent other less elelgant workarounds.
1. I assume the HDCP chip will reside on a monitor’s “motherboardâ€. I would further assume that the “motherboard†would have the equivalent of “video out†wires to feed the monitor’s pixels. What would stop someone from taking the monitor apart and simply “sampling†these wires to record the HD content?
2. Electrical equipment fails. That means spare parts and junked monitors. That implies the capability for anyone to obtain a supply of HDCP chips. I would further assume that HDCP chips acquired through junked monitors would be virtually free. As Ed posted “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.â€
Whoops! just realized my question is answered above!
What if they just don’t release all 40 keys. What happens if they just give out 30 of ’em?
Trickling the keys out over time would actually make their situation worse. Say they initially limit themselves to a 30-dimensional subspace. This will be easier to crack than the full 40. Later, every time they start using one more dimension, as soon as some hacker stumbles onto a device that won’t work, they know it uses one more key bit; and they know the previous subspace. It’s easy to extend the subspace by just one more dimension. It can probably be brute-forced; otherwise it takes just one of the “new” keys being leaked to someone who can generate the previous subspace.
charlie strauss:
The authority needs to hand out more bits than that because each key has exactly 20 bits! This means that you’d need at least 10 more to get a fairly decent sized set. Even if they only gave out keys with 30 bits, this would allow attackers to use *30* keys to determine a partial master key and generate all valid keys anywhere within that 30-bit keyspace (still fairly large).
My point is that by them restricting the keys they hand out, the problem actually gets easier. Let’s hope they do!
Carlos,
no this scheme fails for the reason I stated. All the central athurity has to do to stifle this attack is to never hand out to any one person of company a set of 40 linealy independent addition vectors. Then all of the math above fails.
It would therefore require a much larger conspiracy between multiple companies to find a set of addition vectors that spans the linearly independent basis set of 40.
By dribbling these out over time they can always assure that this years decoder dongle which can only decode the current known subspace of addition vectors will fail on next years device.
However once you got a decoder dongle working with specific player, you could use it with that particular player indefinitely. There just wont be any universal decoder dongle as claimed unless the central authority screws up and does hand out a linearly independent set that spans the entrire 40 element space.
A few clarifications:
1. HDCP is part of the extremally elaborate, though partially abandoned, CPSA framework. This also includes such technologies as CSS, HDCP, CPRM, CPPM and various other such abbreviations.
2. The main purpose of HDCP is *not* to prevent ordinary consumers copying. The expense of the equipment to capture a raw DVI stream is excessive. Its purpose is partially to prevent professional pirates, but mostly to prevent companies manufacturing equipment does does not respect content usage rules.
For example, HDCP ensures that noone will be able to make an HD-recorder capable of recording either content from purchased media or pay-per-view broadcasts. The licence for obtaining HDCP keys forbids such things.
In this way it is very similar to CSS. The purpose of which was not so much to prevent copying of discs (which can be done without breaking CSS, though only with access to professional equipment) as to ensure all DVD players obey the region restrictions and apply macrovision on the outputs.
3. CPSA suffers from one huge weakness – when one technology is broken, others are rendered pointless. For example, when CSS was broken, macrovision on outputs became usless for actually preventing piracy. It serves now only to cause problems for those with older TVs. In the same way, while a solution for HDCP would be nice, a solution for AACS would render much of the content protected by HDCP easily accessible anyway. With the exception of some broadcast content, much of which would become available on DVD later.
4. Should HDCP be broken, the first market would not be devices for piracy, but converters for using existing HDTV displays – particually computer monitors and projectors – to view future HDCP-required content. These would be illegal in the US, most of Europe, Japan, and some other areas.
5. Even should HDCP be broken completly tomorrow, it would not be abandoned. Too much is invested, and its purpose is legal rather than technological. Pirates would be able to operate just as easily without a way around HDCP as they with it – and even if it could be broken with five minutes of googling, the lawyers would still be poised to decend on any manufacturer who dared to make a mass-market HD-recorder without restrictions.
6. If individual keys are compromised, there is an elaborate revocation system. In the full design, blacklists are distributed via new media, new devices, the internet and broadcasts. Devices then exchange these lists each time they authenticate – if they have different versions, the newer replaces the older.
It is interesting to consider that if the message-signing system were ever to be broken (Highly unlikely, since this is conventional crypto, not DRM), it would be possible to make a viral update which either disables blacklisting by having an all-ones version number of blacklists all known devices. This would spread through all connected equipment. Give someone a DVD and it disables not only their DVD player, but their TV, recorder, cable or sat decoder… and when they take them to be repaired, the damage spreads to the technicians test equipment, and to the next device they test before they work out what happened.
But, this full system will probably not be implimented. This was also intended for DVD, but time and internal disagreements prevented it. Instead DVD uses the CSS revocation system, which is far less effective, if safer. In the same way is is likely that any production revocation mechanism for HDCP would be piggybacked off that used for AACS, rather than the ‘viral-update’ approach.
Encontrada debilidad en el algoritmo de cifrado para la Alta Definición…
El protocolo HDPC/HDMI se asegura de que todo contenido de alta definición que viaja por un cable lo haga cifrado. Para ello se efectúa un handshake previo que compromete las claves secretas usadas.
Visto en el blog de Enrique Dans [http://edans.blogs…
charlie:
If I understand this correctly, you can coerce an authorized device to perform actions allowing you to derive it’s key.
Having unused bits that later are required could, in fact, make any hack useless in a few years. Of course, doing so would make the authorized devices (whose keys you have) useless at the same time.
“People keep talking about the unencrypted stream being larger than the encrypted.”
Um… no. People keep talking (correctly) about the (encrypted or decrypted) HDMI stream being larger than the (encrypted or decrypted) content source (eg: HD-DVD).
HDMI streams uncompressed raw video, while HD-DVD stores MPEG video.
Breaking the encyption on the HDMI stream allows you to play the content on “unapproved” devices, but to record the stream, you would need to capture and re-encode a high data-rate video stream. Breaking the encryption on the HD-DVD disc gives you the “original” compressed/encoded MPEG.
I think this attack may fail. Or rather not be as immediately successful as imagined. Ironically, the fatal flaw is contained in the same algebra mistake made in the orginal post.
In order to prevent this attack from being done easily, the central authority could deliberately hand out linearly dependent addition vectors to any company that applies. For example, suppose a company applies for 10,000 keys. The central authority gives them 10,000 keys and 10,000 addition vectors. But the addition vectors are all crammed into the first 14 or 15 bits of the 40 bit addition vector. (that is bits 16 to 40 are zero). This would assure that the addition vectors are linearly dependent and the code cannot be cracked.
In effect the 10,000 keys are hobbled to representing no more than 15 independent keys, not the requisite 40 to crack this.
Thinking even more globally, the central authority could reserve say the last 10 bits of the addition vector, so that all devices manufactured from 2008 to 2010 never used the last 10 bits. then all devices manufactured from 2010 to 2012 always used the 31st bit but none of the last 9. Then in 2013-2014, all devices always use the 32nd bit but none of the last 8. and so on.
thus they can prevent anyone from collecting all 40 so far into the future that they can assure that any crack that works this year will fail on all new devices.
Of course, the hackers only need to stay on the ball and update their hacks as they can. But it’s going to take a very large consipiracy among multiple companies to collect large enough set of addition vectors to crack this.
Encryption is not compression. Though they are normally used hand and hand, they are not the same. People keep talking about the unencrypted stream being larger than the encrypted. You are talking compression. They are different. Not to say you don’t have a valid point, because the streams are sent compressed, but the two are mutually exclusive, in reality.
I’m not sure if this is part of the spec, but it is possible that revocation list updates could be included within content or media (e.g. on the blu-ray DVD you just rented). If this can be done I would assume it would be in the form of a digitally signed packet that is occasionally issued by the central authority
let the slashdotting begin…
I expect them not to ever send the generated key over the line. Since you can generate it at both sides, you only need the addition key of the other to generate it yourself. The other device will only ever send out its addition key, and that won’t change.
The point of the attack is that you can, given 40 known keysets and one addition key, generate its secret key set. If you can do that, you have got all the keysets in the world.
This is nice for displaying HDTV, yet you need a device that can handle the bandwidth. Does anybody know about any hardware-ish device (FPGA?) that can reach the required speeds?
Why not just keep throwing addition rules at the device?
BobPaul,
According to the Crosby, et al. paper (p.3), the dot product is hashed with a nonce before being put on the wire. It’s actually the result of the one-way hash that’s compared.
So, while I’m not saying that your attack wouldn’t work (not saying it would, either), the one-way hash function presents a complication.
@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…
🙂
“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.
@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..
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.
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
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 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.
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.
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.
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?
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.
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.
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.
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.
http://www.engadget.com/2005/07/21/the-clicker-hdcps-shiny-red-button/
Story about a device that strips HDCP.
So what is the objective of the HDCP system, other than to be awkward.
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.
How is my DVD player supposed to get new revocation lists? It doesn’t seem very practical to force such updates.
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.
Awesome article. I can’t wait to get to Princeton next year!
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)
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).
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?
And there is an error in the above post. that paper was published in 2001, not 1991.
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.
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.
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.
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.
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.
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!
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.
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.
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 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).
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.
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.
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?
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.
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?
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]
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.
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
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.
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.
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.