COMSEC: August 2011 Archives


August 29, 2011

One of the "poster child" applications for research into privacy-preserving cryptography has been electronic tolling (i.e., for highways and bridges). Tolling is an attractive application for a number of reasons, including:
  • There are some really serious privacy implications to knowing where where your car is, or at least people think there are. (See for instance the IETF's Geographic Location Privacy WG).
  • The kinds of infrastructure that you would need (transponders, receivers at the toll plaza, etc.) to implement are already in place. You would of course need to upgrade them, but it's not like people would find it hard to understand "we're sending you a new E-ZPass transponder. Stick it to your windshield".
  • You can hide most of the complexity in the transponder, so it's not like the users need to know how to execute blind signatures or cut-and-choose protocols.
  • A lot of money changes hands.
Most importantly, the existing situation is stunningly bad, both from a privacy and a security perspective. To take an example, Fastrak transponders are simple RFID tags, so it's trivial to clone someone's transponder as well as to place your own Fastrak readers to track people at locations of your choice. It's clear you could do a lot better than this, even without getting into any fancy cryptography, and with some cleverness, you can do much better. There has been a huge amount of research on privacy-preserving tolling over the years, but the basic idea is always to ensure that people pay tolls when appropriate but also to avoid anyone—including the toll authority—from determining through the protocol when given cars passed a given location. How achievable this goal is depends on the model: it's pretty well understood how to do this when the toll plazas are in fixed locations; it's rather harder to do when you have large expanses of toll roads and you want people to pay by the mile.

Against this background, last Thursday's NYT Article on E-ZPass toll fraud makes sobering reading. Briefly, E-ZPass can operate in a "gateless" mode where you drive through the plaza but there's nothing to stop you if you don't pay. Instead, there are license plate cameras and so if someone doesn't pay you can send them a ticket in the mail. (Note that the transponders aren't that reliable, so in some cases you keep a record of which license plates are registered to have a transponder and just bill people with registered plates but whose transponders didn't register as if the transponder had worked.) In any case, according to this article roughly 2% of people don't pay and the enforcement procedures are proving to be quite problematic. The problem isn't identifying the offender, it's billing them:

The process for trying to catch toll cheats begins with a photograph, automatically taken at the toll plaza, that is used to identify the offending vehicle's license plate number. Using motor vehicle records, the Port Authority then tracks down the vehicle owner and sends a letter indicating that a toll and possibly a fine are due.


"That is one of the great untold secrets for any given agency," Neil Gray, the director of government affairs for the Washington-based International Bridge, Tunnel and Turnpike Association, said about toll cheats. "You'll probably spend more time and money chasing the toll than you will get for the toll."


Then it comes down to how much time and what resources states want to invest to chase down these funds. In Maine, officials are able to suspend the registration of vehicles with unpaid E-ZPass bills; in Delaware, drivers with outstanding toll violations cannot renew their registrations. Jennifer Cohan, director of Delaware's Division of Motor Vehicles, acknowledged that there were harsher measures that could be employed.

"We technically could arrest these folks," Ms. Cohan said, suggesting that it was possible to have a police officer at every toll booth. "But our law enforcement officers are extremely busy."

What lessons does this have for more complicated cryptographic tolling mechanisms? First, the fact that the rate at which non-subscribers go through the toll plaza without paying is so high and that it needs to be enforced with cameras sort of negates concerns about the privacy of the tolling system itself. It doesn't really help to have a privacy-preserving cryptographic tolling protocols if you need cameras everywhere to detect fraud. And since toll plazas tend to be placed at choke points like bridges, tunnels, etc., there's a lot of information leakage. There's been a fair amount of work on tolling that doesn't use fixed toll plazas (e.g., where you pay by mile of road driven) and then uses secret cameras for auditing (see, for instance, Meiklejohn, Mowery, Checkoway, and Shacham's The Phantom Tollbooth) in this year's USENIX Security), but it's not clear how useful these models are. First, you still need a fair amount of surveillance (and hence information leakage) in order to enforce compliance. Second, tolls get collected at choke points not only because it's easy but also because those are the limited resource you want to control access to, so just charging people for miles driven on a large number of roads isn't an adequate substitute. (And of course in the case where you want to charge people for all miles driven, it's easier to just install mileage meters and/or charge a gas tax scaled to your car's expected MPG).

Second, a level of fraud this high suggests that concerns about the technical security of the system are premature. If you have photographic proof of 2% of people passing through the toll plaza and just outright not paying and you can't even manage to punish them and/or collect money from them, then you've got bigger things to worry about than fancy technical attacks. So, for instance, Meiklejohn et al. describe an attack on previous systems in which drivers collude to discover the locations of secret cameras and use that to defraud the tolling authority. It's a clever attack but kind of pointless if it's easier to just not pay entirely and figure you won't get caught.

More generally, I think this represents an argument against a broad variety of privacy-preserving cryptographic mechanisms based on this style of "voluntary" compliance enforced by auditing and punishment. The argument for this strategy goes that it allows you to (mostly) preserve people's privacy because the vast majority of transactions go unexamined while ensuring compliance because people are afraid of being caught if they cheat. The first half of this argument is fine as long as you can design an auditing mechanism which itself isn't too invasive. However, it's the second half of the argument that seems really problematic: if the value to me of cheating is V and the chance of getting caught is α, then the punishment P must be ≥ V/α or I'd be better off cheating and taking the occasional punishment. If either P or &alpha is too small, then the system won't work. So, here we have an instance where this has actually been tried, and the state has the capacity to inflict quite high punishments (including putting you in jail), and it's not working very well.

Many of the settings that people talk about using privacy-preserving cryptography in (e.g., digital payments) have weaker enforcement mechanisms and much more ambiguous evidence of cheating. For instance, the transaction itself might not be that well tied to your real-world identity, making punishment difficult. Moreover, often these protocols are complicated and involve a lot of fancy cryptography, so even if you do get caught you can argue that it was an inadvertant error and so you shouldn't receive the whole punishment. If we can't even make this stuff work in the current simple setting, it seems pretty questionable that it will work in more complicated cases.