[Posts in this series: 1, 2, 3, 4, 5, 6, 7.]
This is the third post in our discussion of AACS, the encryption scheme used for HD-DVD and Blu-Ray discs. Yesterday Ed explained how it is possible to reverse-engineer a player to learn its secret device keys. With the device keys, you can extract the title key for any disc that the device can play. Anybody with the same disc can use this title key to decrypt the movie.
We’ve already talked about two scenarios where this information could be used for widespread circumvention. One possibility is for the attacker to keep the device keys to himself and publish title keys for discs he has access to. This means anyone can decrypt those discs, but other discs remain secure.
Another option is for the attacker to publish the device keys outright. That would let anyone decrypt any available disc, but it would also tell the AACS central authority which device keys were compromised. Once the central authority knows which device keys to target, it can blacklist those device keys.
Blacklisting in AACS works like this: disc producers can change the way new discs are encrypted so that the blacklisted device keys cannot decrypt the new discs’ headers and therefore cannot extract title keys or decrypt the movies. Of course, blacklisted device keys can still decrypt all the older titles they could before, since the data on old discs doesn’t magically change, but they can’t decipher any new discs.
Blacklisting would be a PR and business disaster if it meant a lot of consumers had to throw away their fancy players as a result of a crack. That’s why AACS allows each individual player to be assigned its own unique set of device keys that can be uniquely blacklisted without adversely affecting other players.
(Some serious crypto wizardry is required to enable a huge number of distinct device keys with surgically precise blacklisting, while keeping device memories and disc headers manageably small.)
Can blacklisting be avoided? Here’s one way an attacker might try: He could keep his device keys secret and create a web site where people can upload header information from discs they want to decrypt. Then he would use his device keys to extract the title keys for those headers and post the title keys back to the site—a sophisticated attacker might automate this process. Cryptographers call this kind of site a decryption oracle.
As it turns out, the designers of AACS anticipated decryption oracles, so the system includes a way to track down and blacklist the device keys used to operate them. This process is called “traitor tracing,” and it works roughly like this: The central authority creates a phony disc header that can be decrypted by about half of the possible devices. (They just need the header, so there’s no need to press an actual disc.) They upload this to the oracle and see whether it can find the title key. The result lets the authority narrow down which devices the oracle’s keys might have come from. The authority repeats the process, creating a new header that will reduce the set of suspects by half again. With a few of these probes, the authority can home in on the oracle’s device keys.
(The full story is more complicated. The oracle might know keys from more than one device; it might try to trick the authority by pretending it can’t decrypt certain headers when it really can; it might try to detect the authority’s probing and change its behavior; and so on. Regardless, the authority can use a sequence of probes to devise a blacklist that will make new discs immune to decryption by the oracle, without affecting noncompromised players.)
The upshot is that if the attacker makes an oracle available to the public, the central authority can render the oracle useless for future discs. However, a clever attacker has another surprisingly effective strategy: limiting who can submit queries to his oracle. We’ll have more on that in tomorrow’s post.
I think most of the defenses have been covered in the comments, but I think there ought to be an article which summarizes them.
My favorite defense is to only allow the oracle to work on known good revocation trees.
As far as I can tell the list of revoked players is the same on all real disks and it will only change when a key is revoked, so you can create an up to date whitelist from your own source of legitimate disks with relatively little effort.
All disks that have a revocation tree that matches one in the whitelist gets decrypted as normal, all others get a pending error code telling the user that this key cannot yet be decrypted and that he should try again in a few days.
There should be relatively little churn in the hardware player part of the list, but as far I can tell the software players will get routinely banned and new updates pushed out, so maybe the scheme would have to ignore changes to software players.
I was wondering if a new player would be able to play some content that would have been published before it exists, since its DeviceID had not been treated ?
I imagine a ranking scheme, combined with delayed results could make probing more expensive. Require a login, and only publish results to users with a certain threshold of accurate key reports. Should also be helped by cross checking against other device keys.
It really seems like the same battle from the other end, ultimately if you allow access by untrusted sources you’re risking the data you wanted to hide.
“However, a clever attacker has another surprisingly effective strategy: limiting who can submit queries to his oracle.”
Of course this is going to happen. Where do you think The Scene get their goodies from? They don’t get it from someone who actually buys the product. They get it from people who work at video rental stores or places which have free access to those goodies. They don’t need some guy sending them a request to crack a disc that mommy bought them for their birthday.
“While I’m sure a lot of exceptionally clever (and well paid, I presume) people worked to create this system, is it an impossible problem to truly solve?”
Of course it is. It’s copy protection, aka “trying to put the genie back into the bottle”.
I see a problem here with the Revocation Authority’s attack on the Oracle. The problem is thus:
If the RA can conduct unlimited attacks against the Oracle, and get a valid pass/fail reply to each probe, then they can easily binary search down through billions of possible Device Keys (say 2^32 possible player DK’s) in a manageable number of attempts. However, at present there are only dozens of AACS protected discs out there. By the end of this year maybe a few hundred. In five years, a few thousand.
Since you have to supply a movie title with your header for decryption, it is easy to check this movie title against a list of valid titles. If you’ve already gotten the Title Key for this title, you don’t decrypt, but instead just send back the already decrypted Title Key. If they submit a proposed header from some movie not released with AACS, you simply ignore the request which removes their ability for multiple probes.
And in the third case where they submit a header with a valid title that you have not yet decrypted, you wait for a few dozen of the same headers to arrive, and decrypt the one that seems most valid (i.e. identically arrives from multiple, independent sources; or trusted sources that have sent you valid headers before). If there’s a question, well there’s always NetFlix to get the header yourself.
This would seem able to take a lot of the steam out of their ability to probe with multiple attacks to determine which DK is in use.
It does beg the question of just how many revoked keys does their system support before it becomes cumbersome to administer? Do additionally revoked keys change the header size. Increase it for each specifically revoked DK? Can this increased header size be detected as a probe attack? It might easily become possible to filter out attack headers with nothing more than comparing them to “normal” headers for movies being released at this point. It seems to me that the RA’s are assuming a somewhat dumb Oracle.
While I’m sure a lot of exceptionally clever (and well paid, I presume) people worked to create this system, is it an impossible problem to truly solve?
clearly the best attack is to try the hardest to compromise the most popular models of DVD players – get their keys blacklisted and wreak havoc among the customer base. All it will take is a couple of Congrescritters finding out that their players wont play the latest DVDs and there will be new allies on our side…
Paul,
I seem to remember the use of illegally modified Kazaa clients (violation of Copyright, violation of EULA) to corrupt the p2p network… not to mention a famous root-kit. These guys are perfectly happy to play on the blackhat side of the fence and when it comes to a legal challenge they usually win. It would take a large consumer backlash and public outcry to change this situation.
I’m also thinking that it is most likely illegal to even access a key-breaking oracle so they might set up a “stinging oracle” to encourage the users to do something to reveal their identity before giving them the keys (e.g. download “Oracle Client the Obvious Trojan” and you can crack any keys you like). My guess is that even if their stinging client was sending back a listing of all your files you would lose any legal challenge… simply because of who you would be fighting against and because so soon as you are branded with the accusation of “pirate” then your complaints about privacy aren’t going to get listened to. After six months data collection they start demanding payment, most of the people caught will roll over easily, a few will go to trial, spend years fighting and finally lose, everyone else will be scared away from oracles.
Unless I’m missing something, the only people submitting faked queries are going to be the authorities, so an oracle with a relatively small number of keys should be able to detect an attack almost immediately and act to derail it — if necessary, by shutting down and reappearing in a different guise after a decent interval.
The legal position for the revocation authority will also be rather more interesting than it already is for the RIAA, since they’ll have to forge addresses, circumvent content-protection methods and otherwise play on the black-hat side of the fence to get the information they want out of the oracle, with the avowed intent of rendering (more or less) worthless the property tens of thousands or perhaps million of some other company’s innocent customers. (I also wonder what the fine print of player warranties will say — if the device key is revoked during the warranty period, is the manufacturer on the hook for a replacement?)
Ralph Hartley: I believe you’re wrong, the device keys are per model; if we both own the same model of player (and hence the same device key) and I crack my player and thus cause the device keys for that model to be revoked, you’re SOL as far as new disks are concerned.
What Mitch is proposing makes the oracle vulnerable to (actual) key revocation, avoiding which is the oracle’s primary purpose per the post. Subsequently proposed stochastic approaches at cloaking keys will degrade oracle performance when keys are revoked (performance not in the sense of speed, but reliability of decryption).
It appears to be quite likely that in practice the oracle operators, esp. when multiple individuals collude, can “generate” (discover) new device keys at a rate faster than the key authority can discover and disable currently used keys.
Tim: Each unit is assigned a unique key. So revocation does not degrade a whole model.
Their model is much weaker. They assume the oracle has no memory at all, and no way to distinguish test queries from real ones.
The scheme in the paper is designed to extract the information needed to defeat a captured software decryption box. None of the defenses Devonavar suggests (which should also be treated as examples) are possible in that context, because the tracer they don’t need to identify the keys used, it just needs to find a query the box won’t answer (with high enough probability), but any legitimate player will.
I don’t know what the limits are for a remote oracle with memory and access to published disks (which can’t be test queries), but it is surely a much harder problem.
Alex: Just for clarification purposes, is each individual player unit assigned a unique key, or is each model of player assigned a unique key?
Devonavar: Sorry, I was only trying to provide a simple counterexample. Section 5 of the paper we cited in he post gives a more general tracing algorithm and proves that it succeeds under some pretty strong assumptions. (Though their model is weaker than the oracle model we discussed.) That might be a good place to start if you want to get into the gory details of tracing.
Alex: Your approach only works if the studios know ahead of time how the oracle handles multiple keys. I highly doubt that someone running an oracle will publish details of their “counter-revocation” algorithm.
Or, to modify Mitch’s example, why not use this algorithm:
If all keys can decrypt, then decrypt;
If not all keys can decrypt, then either decrypt or do not decrypt at random.
Do not allow multiple queries for a single key from the same IP address to prevent detecting which keys are compromised by scanning for discrepancies in the results (or find a way of always offering the same result to the same key).
And, for best results, have pool of five or six keys (as many as possible), and use only two or three keys chosen at random for each query. This approach would make it more or less impossible to use deductive reasoning to discover compromised keys, as the keys used would change from query to query. I suspect it would be vulnerable to large-scale statistical analysis, but the number of queries needed for each deductive iteration would be quite large, and could probably be stymied by disallowing multiple queries for the same title key from the same IP. Add in the fact that the studios will not know ahead of time what algorithm is used to obscure the keys used for decryption, and it shouldn’t be too difficult to keep the compromised keys secret.
Mitch: Good thinking, but the key revocation system is designed to handle oracles that have multiple compromised keys. See the paper linked above for more details.
Let’s say there are three device keys, and the oracle refuses to decrypt if any of them fails to decrypt the probe header, as in your example. I believe this will only slow down the tracing by a factor of 3, because the central authority can just knock out the keys one at a time.
In the first round of probing, they blacklist half the possible device keys, as before. (Let’s call the half they blacklist the left half and the rest the right half.) If the oracle won’t decrypt, the authority knows at least one cracked key must be in the left half. If it will decrypt, all the keys must be in the right half. As before, the authority can repeat this process to home in on one of the keys. Then, they can figure out the second key by constructing new probes that leave the first device key off of the blacklists…
If the Oracle has multiple device keys, chooses one at random for each decryption and makes the user pay for each decryption (CAPTCHA, Proof of Work, …), then it could take a long time to the central authority to revoke the keys.
Question for Ed and Alex:
Suppose I’ve compromised 2 or 3 or more players, and suppose my Oracle operates as follows: Given a disk header, it delivers the title key if and only if *all* of the keys in its possession can decrypt it. If not, it refuses to reveal the title key.
It seems that in most cases, a legitimate disk would work, while a “probe” with only 1/2 the keys (say) would have a 1/8 or smaller chance of decrypting. It probably becomes combinatorically impossible to use the probe to determine what the keys in my possession are.
Is this reasoning correct?
@Tel: Public and illegal (in the US) doesn’t mean the oracle can be taken down easily. For example, consider all the bittorrent trackers which are tracking copyrighted material.
Also, another source of device keys could be software players purchased online with stolen IDs. And don’t forget about software players purchased in shrinkwrap from retail software outlets, cash & carry like the hardware players.
Legal attacks against the oracle site would be easier — it can’t be both hidden and public at the same time and if running a key cracker is not illegal now (I think it is) then as soon as the MPAA find it a nuisance they would make it illegal.
As for pulling device keys out of your software, yes that is going to be easy to do (very easy) but most likely the software containing the unique device keys will be issued to each person through some sort of Internet registration system so that they will know the name and address of the person leaking the keys. Cautious people will not want the trouble they get for being named as a leaker… The only remaining source of keys will be consumer devices (pay cash, carry away the box) which are much harder to crack into; and of course, device keys stolen from virus-infected Microsoft systems then resold on the black market.
For Linux users who want their software to be legit, none of these are a viable option. I would argue that the only viable attack is an economic attack — get your entertainment elsewhere… search for independent artists and vote with your dollars.
So, suppose someone just uses the Oracle to crack every key for every reader, the way the MPAA plans to do their discovery thing, and then publishes all the known keys in public on the web so that the MPAA is forced to revoke them, and thereby all existing readers become completely useless for all new movies. Sure, that makes me think this key revocation “plan” is so well thought out.
It just takes one smart techie with a soldering iron and some hacked electronic gear to ‘plug in a key’ (pick one, there are many to choose from), capture the movie, write it to one non-DRM’ed disk image to share it far and wide, and it makes this whole game useless. Even embedding the key in the hardware is no assurance against a truly motivated (i.e. ticked-off) hacker. If you give the hackers both the key an the disk at the same time (yes, its necessary so it can be played) then the game is already over. Its just a matter of time. Solving a “social problem†with a “technical solution†is always doomed to failure.
I’m loving these easy-to-read quick(ish) blurbs about the AACS. Great job!
AndrewJ: Oops. I fixed the post to correct this. Thanks.
Correction to paragraph 7, about the oracle: Instead of “post the device keys back to the site” you probably mean “post the title keys back to the site”.
This is an excellent series, thanks!
Very interesting, thanks for the clear and concise explanation!
BTW, there’s some irony that Google Adwords is showing a Sony Blu-Ray ad above this. I would click it but I’m afraid it leads to a rootkit. 🙂