May 22, 2017

Archives for January 2007

Diebold Shows How to Make Your Own Voting Machine Key

By now it should be clear that Diebold’s AccuVote-TS electronic voting machines have lousy security. Our study last fall showed that malicious software running on the machines can invisibly alter votes, and that this software can be installed in under a minute by inserting a new memory card into the side of the machine. The last line of defense against such attacks is a cheap lock covering the memory card door. Our video shows that the lock can be picked in seconds, and, infamously, it can also be opened with a key that is widely sold for use in hotel minibars and jukeboxes.

(Some polling places cover the memory card with tamper evident seals, but these provide little real security. In practice, the seals are often ignored or accidentally broken. If broken seals are taken seriously and affected machines are taken offline for inspection, an attacker could launch a cheap denial-of-service attack by going around breaking the seals on election day.)

According to published reports, nearly all the machines deployed around the country use the exact same key. Up to this point we’ve been careful not to say precisely which key or show the particular pattern of the cuts. The shape of a key is like a password – it only provides security if you keep it secret from the bad guys. We’ve tried to keep the shape secret so as not to make an attacker’s job even marginally easier, and you would expect a security-conscious vendor to do the same.

Not Diebold. Ross Kinard of SploitCast wrote to me last month to point out that Diebold offers the key for sale on their web site. Of course, they won’t sell it to just anybody – only Diebold account holders can order it online. However, as Ross observed, Diebold’s online store shows a detailed photograph of the key.

Here is a copy of the page. The original showed the entire key, but we have blacked out the compromising part.

Could an attacker create a working key from the photograph? Ross decided to find out. Here’s what he did:

I bought three blank keys from Ace. Then a drill vise and three cabinet locks that used a different type of key from Lowes. I hoped that the spacing and depths on the cabinet locks’ keys would be similar to those on the voting machine key. With some files I had I then made three keys to look like the key in the picture.

Ross sent me his three homemade keys, and, amazingly, two of them can open the locks on the Diebold machine we used in our study!

This video shows one of Ross’s keys opening the lock on the memory card door:

Ross says he has tried repeatedly to bring this to Diebold’s attention over the past month. However, at the time of this posting, the image was still on their site.

Security experts advocate designing systems with “defense in depth,” multiple layers of barriers against attack. The Diebold electronic voting systems, unfortunately, seem to exhibit “weakness in depth.” If one mode of attack is blocked or simply too inconvenient, there always seems to be another waiting to be exposed.

[UPDATE (Jan. 25): As of this morning, the photo of the key is no longer on Diebold’s site.]

AACS: Modeling the Battle

[Posts in this series: 1, 2, 3, 4, 5, 6, 7.]

By this point in our series on AACS (the encryption scheme used in HD-DVD and Blu-ray) it should be clear that AACS creates a nontrivial strategic game between the AACS central authority (representing the movie studios) and the attackers who want to defeat AACS. Today I want to sketch a model of this game and talk about who is likely to win.

First, let’s talk about what each party is trying to achieve. The central authority wants to maximize movie studio revenue. More precisely, they’re concerned with the portion of revenue that is due to AACS protection. We’ll call this the Marginal Value of Protection (MVP): the revenue they would get if AACS were impossible to defeat, minus the revenue they would get if AACS had no effect at all. The authority’s goal is to maximize the fraction of MVP that the studios can capture.

In practice, MVP might be negative. AACS makes a disc less useful to honest consumers, thereby reducing consumer demand for discs, which hurts studio revenue. (For example: Alex and I can’t play our own HD-DVD discs on our computers, because the AACS rules don’t like our computers’ video cards. The only way for us to watch these discs on our equipment would be to defeat AACS. (Being researchers, we want to analyze the discs rather than watch them, but normal people would insist on watching.)) If this revenue reduction outweighs any revenue increase due to frustrating infringement, MVP will be negative. But of course if MVP is negative then a rational studio will release its discs without AACS encryption; so we will assume for analytic purposes that MVP is positive.

We’ll assume there is a single attacker, or equivalently that multiple attackers coordinate their actions. The attacker’s motive is tricky to model but we’ll assume for now that the attacker is directly opposed to the authority, so the attacker wants to minimize the fraction of MVP that the studios can capture.

We’ll assume the studios release discs at a constant rate, and that the MVP from a disc is highest when the disc is first released and then declines exponentially, with time constant L. (That is, MVP for a disc is proportional to exp(-(t-t0)/L), where t0 is the disc’s release date.) Most of the MVP from a disc will be generated in the first L days after its release.

We’ll assume that the attacker can compromise a new player device every C days on average. We’ll model this as a Poisson process, so that the likelihood of compromising a new device is the same every day, or equivalently the time between compromises is exponentially distributed with mean C.

Whenever the attacker has a compromised device, he has the option of using that device to nullify the MVP from any set of existing discs. (He does this by ripping and redistributing the discs’ content or the keys needed to decrypt that content.) But once the attacker uses a compromised device this way, the authority gets the ability to blacklist that compromised device so that the attacker cannot use it to nullify MVP from any future discs.

Okay, we’ve written down the rules of the game. The next step – I’ll spare you the gory details – is to translate the rules into equations and solve the equations to find the optimal strategy for each side and the outcome of the game, that is, the fraction of MVP the studios will get, assuming both sides play optimally. The result will depend on two parameters: L, the commercial lifetime of a disc, and C, the time between player compromises.

It turns out that the attacker’s best strategy is to withhold any newly discovered compromise until a “release window” of size R has passed since the last time the authority blacklisted a player. (R depends in a complicated way on L and C.) Once the release window has passed, the attacker will use the compromise aggressively and the authority will then blacklist the compromised player, which essentially starts the game over. The studio collects revenue during the release window, and sometimes beyond the release window when the attacker gets unlucky and takes a long time to find another compromise.

The fraction of MVP collected by the studio turns out to be approximately C/(C+L). When C is much smaller than L, the studio loses most of the MVP, because the attacker compromises players frequently so the attacker will nullify a disc’s MVP early in the disc’s commercial lifetime. But when C is much bigger than L, a disc will be able to collect most of its MVP before the attacker can find a compromise.

To predict the game’s outcome, then, we need to know the ratio of C (the time needed to compromise a player) to L (the commercial lifetime of a disc). Unfortunately we don’t have good data to estimate C and L. My guess, though, is that C will be considerably less than L in the long run. I’d expect C to be measured in weeks and L in months. If that’s right, it’s bad news for AACS.

AACS: Sequence Keys and Tracing

[Posts in this series: 1, 2, 3, 4, 5, 6, 7.]

This is the sixth post in our series on AACS, the encryption scheme used for HD-DVD and Blu-Ray discs.

It’s time to introduce another part of AACS: the Sequence Key mechanism. Throughout our AACS discussion, we have done our best to simplify things so readers could follow our logic without having to digest the entire technical specification. At this point, continuing the discussion requires some background about Sequence Keys.

We wrote previously about the AACS traitor tracing algorithm, which the AACS central authority can use (under some circumstances) to figure out which device keys have leaked. The Sequence Key mechanism gives the authority further help in figuring out which devices are compromised.

Sequence keys don’t seem to matter as of yet. Discs are not required to use sequence keys, and indeed we have yet to see a disc that uses them. We would be interested to hear of any current HD-DVD discs that use them. (Your disc uses sequence keys if it contains the file “AACS/SKB.AACS”.)

The sequence key mechanism uses two tricks. First, it assigns each player device a unique (or nearly unique) set of sequence keys. Discs that use the mechanism contain a special header that a player can decode, using the player’s sequence keys, to get a group of six decryption keys called the variant volume keys. Things are set up so that different players, presented with the same disc, will often end up with different variant volume keys.

The second trick is to take a few snippets of the movie, and put those snippets on the disc several times, encrypted under different variant keys. The movie publisher might create eight slightly different variants of the snippet, and encrypt each variant under a different key. Every player will know one of the eight variant keys, so it will be able to decrypt one of the variants – but different players will decrypt different variants.

The effect of this is that the movie will look slightly different, depending on which player was used to decrypt it. If a ripped copy of a movie is redistributed, the central authority can look at which variant of each snippet is in the rip, and can then identify which player device did the ripping. Each snippet lets it narrow down the number of suspected players by roughly a factor of eight (assuming roughly one-eighth of the players get each variant of that snippet). Given multiple snippets, they can divide by eight for each snippet, rapidly narrowing down the suspects to a few players, or even just one.

Having identified a specific player, the authority can then blacklist its keys, as we described in previous posts, so the player will be unable to decrypt or play any new discs. (It will still be able to access existing discs.)

The BackupHDDVD tool, as it is today, cannot cope with discs that use the Sequence Key mechanism – it uses only the per-disc volume keys and does not have or use any sequence keys. It wouldn’t be hard to modify BackupHDDVD so that it also downloaded and used the variant keys for a disc, allowing it to access discs that use the Sequence Key mechanism. This would require reverse engineers to extract and publish more keys (probably the so-called Volume Variant Unique Keys, along with the associated Variant Data) but that probably isn’t a fundamental impediment.

Doing this would allow the central authority to look at the newly added keys and figure out which player they were extracted from. (Actually things get interesting if the attackers get Variant Keys from many different players and then combine them cleverly to try to avoid being identified; there’s a whole theory considering how well such attacks will work.)

In the end, none of this affects our basic analysis much. Our modeling of the interaction between attackers and the central authority already assumes that the central authority will be able to identify a compromised player, whenever that player is used to capture a significant number of keys. Sequence keys make the mechanism more complicated but they don’t make AACS much more effective, if the attackers are smart.