Tuesday, August 12, 2008

MIT Students Use FPGAs to Hack Boston T

(edit 8/19) The judge has lifted the gag order today. (end edit)

/. points to an article about a court issuing a temporary restraining order to block a Defcon presentation by a group of MIT students that hacked the Boston T Charlie Card system. Not only can they print their own magnetic-striped cards with up to $655.36, but they can also crack the RFID cards using now-widely-known NXP MiFare vulnerabity and a "WarCart" they built (USENIX paper: Reverse-Engineering a Cryptographic RFID Tag). These students started this work for 6.857 taught by Ron Rivest. Two of them took 6.111 when I TA'ed: they attempted to build a CDMA Control Channel Traffic Analyzer for their final project. Maybe we should only allow projects that could end up getting us into lawsuits!

The Tech website has the presentation slides with all the legal documents too. The MBTA's strongest argument is based on the premise that it was unclear whether the MIT students were going to present any new vulnerabilities that were not already in the materials they had sent. Such materials could be a potential threat to public safety. The claim posits that Professor Rivest would not have given them an "A" for the project if their work was just magstripe printing and a repeat of the MiFare hack. It was pretty clear (to me) from the evidence that they were only presenting vulnerabilities in the CharlieCard system that they explained in their now-public disclosure to the MBTA as well as demonstrating how poorly accountable the actual security system is currently.

From a free-speech standpoint I think the temporary restraining order may have been appropriate to require the students to explain their project to the court in case they were going to present anything that could present a safety hazard to the subway system. As far as a non-expert Judge is concerned "someone is presenting novel vulnerabilities in the Boston Subway system" should be enough to merit the fullest caution of the court. However, as soon as it is clear to the Judge that the financial interests of the MBTA (and not public safety) are being weighed against the free-speech rights of the MIT students, the TRO should be lifted. The result of this case will probably be the same as the Dutch NXP Mifare case and an appeals court should lift the restraining order in favor of first amendment rights.

(Edit 8/14): Some of the terms of the TRO are ridiculous from a free-speech standpoint -- claim (2) would imply that security is a property established by judicial process. It's self-contradictory to include that in the request. Apparently the Judge denied a reasonable appeal from the EFF to add the terms "non-public" from the TRO. Apparently this Judge wants a higher court to clarify that first amendment rights outweigh the financial interests of the MBTA.

The Boston Herald reports that an MBTA board member Janice Loux is calling for a security audit and has lost confidence in the General Manager David Grabauskas . Here's a quote from Grabauskas that contradicts the courts action today to deny the appeal: “We just want to make very clear that we’re not interested in quashing anyone’s First Amendment rights,” Grabauskas said, declining to respond to Loux’s criticisms. “All we’re really asking is that the court bar the release of any nonpublic information that might adversely affect the CharlieCard’s security.”
(end edit)

That said, I think the students probably should have presented the CharlieCard vulnerability anyway since they were definitely not going to present anything that an expert couldn't figure out from the data that is out now -- and with so much more attention because of the injunction. Apparently the MBTA also isn't familiar with the Streisand effect. This aspect only highlights a common management problem and my new favorite aphorism:

Do not trust anyone over 30: they did not grow up with the Internet

Never hire someone for a security position unless they have a solid understanding of memetic diffusion in social networks.

As for the problem of finding qualified security consultants to audit the system, I think the students just volunteered to do it*: considering they have pictures in their presentation documenting how they committed various types of fraud it seems like a fitting punishment to make them fix Skynet. I guarantee that they are capable of building a more secure CharlieCard system on the cheap (like 1/100th of the $180M spent on this already). A short term software-only fix could probably achieve much higher security within weeks. The system should have a built-in RMS notice to encourage card swapping "to limit the amount of information Big Brother [Little Brother] can collect about T riders..." (RMS sends a message like this to the CSAIL list to setup card swapping sessions every so often).

The MIT students have a great slide in their presentation: "Why Brute Force with an FPGA? ... Because it's Fast!" I think it's probably better to make this pitch at the High Performance on Wall Street conference over Defcon. From their slides it seems like they created an FPGA-accelerated 48-bit RFID key cracker using a Python script to generate Verilog. Now they, like h1kari from Pico Computing, are giving presentations to other hackers about the merits of FPGA-accelerated cracking (video of h1kari demoing FPGA accelerated WEP cracking). I remember an all nighter at the Las Vegas airport after Defcon in '06 discussing the state of FPGA programming tools with h1kari... that conference made me realize that the existence of vendor-neutral open-source FPGA tools would be the catalyst to change the perception that FPGAs are difficult to program. It seems like reconfigurable computing has multiple fathers and a whole slew of iconoclastic sons trying desperately to get on FBI watch-lists. The FBI probably doesn't suck at this FPGA-accelerated cracking stuff either, but they find more use for FPGAs in their data-warehouses as I'm sure my readers won't confirm.

To understand how the RFID hack was performed, you should read the Nohl paper from UVA which describes how the physical circuitry of a Mifare Classic RFID was reverse engineered. I think the technology used to determine the digital logic on the chips is more interesting than the rest of the paper about the RFID security. Once they determined the cipher for the Mifare cards, they implemented a naive brute force cracker in 64 Virtex-5 LX50 FPGAs that takes 50 minutes. Then they also reveal a weakness in the random number generator that allows them to essentially eliminate the randomness. They also describe a method of generating codebooks to substantially accelerate the crack.

From the slides of their presentation, I believe the MIT students transformed the naive brute-force multivariate quadratic (MQ) cipher cracking problem to a more efficiently implemented SAT problem (which would certainly merit an "A" for the work). FPGAs are perfect for brute-forcing SAT and there are probably 1,000 papers on this topic since it is possibly the most obvious target for FPGA acceleration. From the slides, it seems like the students replicate their cores with a Python script and probably do not contribute anything interesting to accelerating SAT except a novel way to profit from it.

From the comments on this year-old hackaday thread about converting HDTV boards into crypto-crackers, FPGA-accelerated cracking seems to be a good way to get people excited about FPGA technology. It also seems the problem of explaining "what is an FPGA" is still a hurdle to widespread adoption. This is where I say that an FPGA is a hardware spreadsheet, and we call it "Accelerated Computing" to proliferate our favorite meme to replace any other nerd-word you might put in front of "Computing." I also built a spreadsheet to hack the 48-bit RFID keys; it took less than 10 minutes to design and compile to Verilog, but I'm actually afraid to post it now! Here's the anatomy of a massively parallel brute-force cracker: each row tests a unique range of keys and iterates through them until it finds a match, columns of the sheet are "start-key" "end-key" "current-key" "next-key" "hashed-output" and "satisfies target." Super-clever implementers will propagate constants to optimize the hashing function based on the (start, end) range for each row.

Coming Soon: A collection of "Threads Considered Harmful" articles about the dangers of programming in parallel control flow style and the merits of dataflow design for easy-to-grok parallelism.

* The second-most important thing I learned at MIT was that things aren't done because you haven't done them. The most important thing I extracted from MIT was an observation about the effectiveness of people at completing a task that Arlow and I made while running house-cleanups in our fraternity. This observation was extremely apparent as a lab assistant watching students learn to develop FPGA applications in teams. We learned that the metric for a person's effectiveness is the product of their motivation and skill. With rare exception the overall effectiveness of grouping people working tightly together is the product of their individual contributions. Skill can exist anywhere in the complex plane. This model explains things like Microsoft, Google, Congress, and many other organizations down to the T. Imaginary skill leads to "security systems" meaning something different with the quotes. Motivated negative skill leads to War (and WarXing my EZ-Pass for profit).


Anonymous said...

Nice post!

looking forward to see that spreadsheet, or something alike

Lahma said...

I know this is a super old article, but I just came upon it today. My cousin is at MIT, and I am always so impressed by the practical, innovative projects that take place. I'm mesmerized by the increasing PMK/s provided by my multiple GPUs, so I'm sure I would be dazzled by a modern FPGA made specifically for bruteforcing. Very interesting project! I am curious as to what field you ventured into... but I probably won't get an answer to that ;)