Making and Breaking HDCP Handshakes

Cadre writes "Ed Felten describes the handshaking routine used by HDCP and how if any 40 devices conspire together, they can break the security of the system."

Comments

American Hero.

[Whiney Mac Fanboy]

Ed Felten is a true American hero - he's:

* Convinced the Music Industry watermarking is unworkable (saving us from poor quality files)

* Testified against predatory monopolists as a witness for the US govt.

* Exposed holes in Sony's "fix" for XCP malware CDs (that turned out to be almost as dangerous as the original rootkit)

* Given us the memorable quote Given a choice between dancing pigs and security, users will pick dancing pigs every time.

(gleaned from wikipedia)

Also - anyone thinking the 40 'conspiring' devices makes it impractical to break HDCP/HDMI - think again. It just means 40 (or less) like minded hackers have to get together - not particularly hard to imagine these days.

I would do it

[eclectro]

But I don't have room for the forty big-screen TVs.

Re:I would do it

[gEvil (beta)]

That's okay. You can store them here at my place.

Re:Where did you get 40?

[Anonymous Coward]

From TFA:

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.

 
Four was an example for the article.

A little tougher than that...

[weetjerm]

His attack methodology is correct, but it will take more than 40 devices to break the system. The chances are very low that all 40 devices being linearly independent, and therefore each one offering non-duplicate information about the system. If you read the comments, he actually inadvertantly ran into this problem with his small example of 4 keys.

However, in writing this, I realize that I do not know how many keys you would need to present a good probability of solving the system of equations. Anyone want to run a simulation?

Re:A little tougher than that...

[Maljin Jolt]

Anyone want to run a simulation?

No funny simulation is needed, a math paper refered by TFA contains the info you want: 50 KSV's have probability 0.999, by the properties of linear algebra over Z/2exp56Z.

Why Reveal this Now?

[PingXao]

As a poster said at TFA, why did they reveal this attack so soon? It would have been much better to wait another few months until HDCP displays and video cards were shipping in larger numbers. That being said, who's comes up with these lame cryptosystems anyway? First CSS, which was a joke, now this, and you know the Advanced CSS will have holes in it big enough to drive a truck through. The bad news is that some day they will start hiring people who know what they're doing with cryptosystems and then we're all screwed.

Re:Why Reveal this Now?

[Anonymous Coward]

The bad news is that some day they will start hiring people who know what they're doing with cryptosystems and then we're all screwed.

Rather unlikely. The whole concept of DRM is bankrupt as a cryptographic concept because you are handing over the ciphertext, the plaintext and last but not least the key over to your adversary (usually called "consumer" or "hacker"). Sure you can try to make it hard for him to actually get them but you already handed them over and it just remains a question of time until they are recovered.
Meanwhile, a single break is a class break for at least all the content released up to the point of the break (even with "revokable" keys). Also, once a broke the system once, the content is freed forever and can be distributed at leisure (darknet hypothesis), which means even some small quality loss may be acceptable to the attacker since that loss would only occure once.

In short, DRM is a DReaM indeed.

'Old' news

[bas.westerbaan]

HDCP has been broken, and has been proved to be weak in 2001 twice. See http://apache.dataloss.nl/~fred/www.nunce.org/hdcp /hdcp111901.htm

No, it's 40, not 4

[Space cowboy]

In real life the devices have a vector of 40 secret numbers, he's using a vector of 4 to illustrate withour bogging down the reader.

The key is that with N variables (the number of different numbers in the vector), you need N equations to solve the set of equations for all of those variables - it's simple linear algebra.

When you purchase a licence, you get a bunch of 10000 keys for $16000, so S.O.Mebody could use this within an organisation to analyse the generation matrix, and actually produce 40 new keys and release them to the wild. No comeback.

Simon

In a related question...

[dpilot]

I was checking the Sunday advertising fliers this morning, and see that many of the new TVs are advertising HDMI as well as PC connections. Can someone please explain my limitations?

1: Can I hook up my current VGA or DVI to one of these, and display the content I can currently display?

2: Is the only limitation/constraint the new HD/BlueRay DVDs with "double-plus-good super-duper copy-protection, put there to protect me AND the children"?

3: Related to both, assume I have MythTV running with an HD capture card. (I don't yet, but plan to, before they become illegal. What's the latest status?) Can I run my captured content out through one of these new displays?

Re:In a related question...

[nsayer]

1. There are HDMI to DVI cables. The only question mark is the type of DVI your card uses. There are 3 types, depending on which sets of signals the jack has: DVI-A, DVI-D and DVI-I. HDMI is all digital, but its backwards compatible with DVI-D (DVI-I is a combination of both A and D - analog and digital). So unless your card is DVI-A, you should be able to use a DVI-to-HDMI cable to hook up your display. You will need to make separate arrangements for audio, however, since DVI (unlike HDMI) has no provisions for it.

This does presume that the card is able to put out a mode/timing that's compatible with the set, of course.

2. What you're probably talking about is the requirement that non HDCP-hardened outputs from HD players are supposed to be down-resed to 480p (or whatever). I don't know for certain, but I'm willing to bet that this is not an absolute requirement, but that there's a bit that the disk can set to require this behavior. Not all studios or titles will make the decision to flip that bit on on their content, and I'd certainly expect them not to bother until/unless the technology to take DVI-B and rip it to MPEG4 becomes widespread. Unlike macrovision on analog outputs, which largely went unnoticed with DVDs, this bit does threaten to have a real impact on folks, so I would expect a site to pop up relatively shortly with a list of disks "not to buy" unless you have HDCP. The industry might even respond with a standardized icon on the box whose meaning is "HDCP required for full resolution."

The other obvious restriction is that the HD media is itself encrypted, so when HD-DVD-ROM drives come out, you won't be able to read the data off of them (except in the context of an HD-DVD movie player app), at least not until it's reverse engineered and cracked like DVDs were.

3. I may be wrong, but I am unaware of any HD video capture cards. There are HD tuner cards/boxes out there that will do HDTV, but they're decoding the RF from a TV station and getting MPEG2 streams. That's not the same thing as ripping 1080i from a DVI connector and turning THAT into MPEG2. Even if that were possible, the original source (HDTV, HD-DVD, DVD, whatever) was probably compressed in the first place, so you'll be recompressing it, which will degrade the picture some (more).

Re:In a related question...

[frzndrag]

HDMI compliance is not required, you just need a DVI to HDMI is just a rework of the DVI cable to allow for easier consumer connections and include audio.
from http://www.ramelectronics.net/ "HDMI - Digital connection for Video and 8-channels of Digital Audio as well as device control features. Electronically better potential for supporting longer cable lengths than DVI for digital video.
Specification supports up to 12 bit Y-Pr-Pb video (rarely implemented on equipment) as opposed to 8 bit limit of DVI RGB."
I've used them before for other AV media conversion products and they make pretty good stuff.

also see the HDMI FAQ at http://www.hdmi.org/about/faq.asp
which states "Is HDMI backward-compatible with DVI (Digital Visual Interface)?
Yes, HDMI is fully backward-compatible with DVI using the CEA-861 profile for DTVs. HDMI DTVs will display video received from existing DVI-equipped products, and DVI-equipped TVs will display video from HDMI sources."

Re:Cool, but nor practical

[Anonymous Coward]

I find it exceedingly unlikely that 40 such companies will pay for a key vector, just to take the risk of getting sued out of existence.

According to the article, keys are being sold in quantities of 10000, which makes it sound like each physical device has its own unique key. If this is the case, then one not-quite-tamper-proof production run of some player will yield more than enough keys for the attack to be practical.

One thing I hate worse ...

[Midnight Thunder]

There is one thing I hate worse than this DRM (Draconian Rights Management) crap: region encoding. DRM only effects me if I want to make a backup or play a disk I bought with Linux. Now if I buy a disk in Europe and want to play it in Canada it is not doable, officially. Unofficially I have to get a DVD player with a backdoor, or a PC DVD player with the Firmware hacked or rip the DVD - all this for a DVD I bought legitimately!?

And then there is something that scares me: how unaware of this many people I speak to are, even some people working in IT!

Exactly. Ed's math is borked.

[goombah99]

I had exactly the same thought. 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.

One attack in many

[bhima]

Wow so many folks sort of missed the point here...

Felton's description of the weaknesses of DHCP handshakes is of only one potential attack. Combined with other attacks and it's entirely possible that a group effort could crank out new secret vectors faster than the M.A.F.I.A.A. could revoke known compromised ones.

For example: If more was known (than I know) about the encryption algorithm used (AKA "the hdcpRngCipher") work could be started on creating dense & smart Time-Memory Trade-Off tables. This is a non-trivial task involving tens of thousands of CPU hours... a perfect thing for a validating distributed computing application (oh. this. has. so. been. done. before).

Also a HDMI repeater or splitter isn't very far from being a sniffer... I think all it lacks is a little I2C to USB help. This, the tables above, & a HDCP device will net you all the vectors you need to employ Felton's attack. Once one set has been compromised and the methodology worked out it's just a matter of turning the crank to get more and potentially very, very quickly.

The utility of these attacks goes well beyond being able to view 1080p on a non DHCP device... one could render revocation useless be attacking high-end components sold by M.A.F.I.A.A. members (i.e. Sony). This eventually must lead hardware devices running out of un-revoked vectors and becoming inoperable... an untenable situation for the M.A.F.I.A.A.

Now, if such a concerted attack is organized on the hi-def media... I feel that we will be right where we are now... a reasonably astute person can watch any DVD wherever they want and they can retain a backup of that media in a format of their choosing.

Here's what will happen

[Omaze]

Someone will connect an oscilloscope to the wire(s) that connect(s) the devices and reverse engineer the communications signal. They will then construct a custom breadboard able to talk to any HDCP device while being able to impersonate a device with a programmable HDCP vector/rule. With a link (ethernet or serial) to any modern day PC they'll just brute force it.

It won't be difficult.

Re:Here's what will happen

[tadmas]

Someone will connect an oscilloscope to the wire(s) that connect(s) the devices and reverse engineer the communications signal.

There is no need to do this -- the signal itself would have to be according to some kind of standard or else a brand X DVD player couldn't work with a brand Y television. Just look up the communications protocol.

With a link (ethernet or serial) to any modern day PC they'll just brute force it.

Riiiiight. The DVD's addition rule is [1]+[3] and the TV's is [6]+[17]. What's our secret key? It could be 24 (7+17 and 9+15) or 57 (17+40 and 56+1) or 29387 (12412+16975 and 19280+10107).... Each is equally likely, so yes you could brute force it, but if the actual keys are big enough, it would take a Really Long Time to do it. This is the idea behind just about all forms of modern encryption; they can be broken by brute force, but it takes so long it's not worth it.

Could this be broken on a modern PC? Assuming you could easily verify that you got the unencrypted form and the secret keys are 17 decimal digits, then on average it would take you 5e17 guesses to brute force it. If you assume checking 1,000,000 per second, that's 5e11 seconds > 15844 years. Don't hold your breath.

This is why the attack in TFA is useful. Instead of having to try billions of possible keys, you can algebraically figure out a secret vector, so then cracking the encryption is a simple elementary school addition problem. Solving a set of linear equations to get the secret vector can be done in slightly less than thousands of years.

It won't be difficult.

Yes, it will. That's just like saying "cracking RSA is super-easy because it's just finding the prime factors of a number!!!!!!!11!!1one" So, why can't anyone with a modern PC bring RSA to its knees? After all, when you publish your public key, you're also publishing your private key, too.... if someone can figure out the factors of your modulus. You can just brute force it -- it won't be difficult.

Re:Cool, but nor practical

[quentin_quayle]

Did the moderators Read The Fine Article before giving the parent points?

Felten in talking about "a conspiracy of about forty devices" is not saying that (defectors at) forty device makers have to reveal secret keys. What he's saying is that you just need to the 40 devices themselves, or rather (as post above pointed out) enough to get 40 different key sets (and some math and programming ability). Then the crack is done by analysing the bit streams between the devices (between player and display, or whatevre).

The expense is the cost of all those tvs and players. Bribing the device makers is a *different* kind of attack which Felten rules out as impractical.

IT'S NOT ABOUT PIRACY!

[nagora]

This stuff, just like region encoding, is about price-fixing. That's why the security is crap: its only purpose is to prevent the 99.99% of consumers who will never crack even a trivial encryption from recording a TV programme instead of going out and buying the HDDVD of the series later in the year. That keeps the price of those DVD's up and that's all this is about.

It used to be called "a cartel" and it used to be illegal.

TWW

Re:Region Coding vs. Fair Use

[ClamIAm]

Sorry, but in the age of global trade, nobody has a "right" to the type of region-controlling the media cartels do. In fact, this type of collusion is most likely illegal under lots of treaties and jurisdictions.

Apparently this is easy.

[mozu]

The solution is easy according to an anonymous physicist. I showed him the problem and it took him 2 min to do this. He laughed when I told him this is a multi-billion dollar cipher system.

If (no. of eqns.) >= (no. of variables), the equations are solvable.

Given

x1 + x2 = 33 - (1)
x2 + x4 = 18 - (2)
x1 + x3 = 41 - (3)
x2 + x3 = 24 - (4)

Rearrange (4)
--> x2 = 24 - x3

Sub (5) into (1)
x1 + ( 24 - x3 ) = 33
x1 - x3 = 33 - 24
x1 - x3 = 9


(6) + (3) --> 2(x1) + 0 = 9 + 41
2(x1) = 50
x1 = 25

Sub (7) into (1) --> 25 + x2 = 33
x2 = 8

Sub (8) into (2) 8 + x4 = 18
x4 = 10

Sub (8) into (4) 8 + x3 = 24
x3 = 16

Summary
-->
x1 = 25
x2 = 8
x3 = 16
x4 = 10

Apparently any 1st year maths student can do this. This is not the best method however and using a matrix to solve for lambda is the best way, so he says. By the way it took me about 2 hours brute forcing it by logical trial and error using pen and paper.

New business-model: Blackmail your competitor!

[tlk nnr]

The handshake algorithms allows a cool new business-strategy:

- get 40 secret vectors
- use these 40 vectors to recover the secret vector of a well-selling HD-DVD TV screen
- approach the vendor, and threaten to release the secret vector
- profit!: The vendor will have to pay, otherwise the TV screen will end up on the blacklist, and the owners won't be able to play HD-DVD's anymore.

Re:Cool, but nor practical

[ultranova]

Anyways, the whole purpose of buying HD media is for the HD. If it's then downscaled right back to just-slight-above DVD quality, I think people are going to be, pardon my French, pretty fucking pissed. Especially the early adopters who have the highest chance of getting screwed over.

Well, kicking down the front door of the central HDCP bureau and storming it with torches and pitchworks to get the master key is just another kind of brute force attack, no ?-)