In our last class lecture of the semester, we discussed current news stories that involved security and computer technology. We spent quite a bit of time talking about a side-channel attack on RSA keys that was in the news recently thanks to an interview one of the creator’s of the attack gave to Le Monde (as reported by New Scientist). Here’s a draft of the paper describing the attack that has been submitted for publication.
The crux of the attack is that a spy process and the RSA process access a shared resource in the form of the branch target address cache. Depending on whether a bit of the RSA key is a 1 or a 0 it will make a different number of branches through the exponentiation logic. The spy process makes enough different branches to just fill up the branch target cache. Depending on whether the current bit that is being used to perform the exponentation is a 1 or a 0, the RSA process will make a different number of branchs and thus evict a different number of the spy processes branches. Then the spy process simply notes the time it took to execute its branches and note that a longer time means more branch target misses and can then deduce whether the RSA process was working with a 0 or a 1.
It all seems fine in theory. But of course for this to work with the amazing accuracy noted in the news articles (508 of 512 bits revealed in one encryption or decryption operation), your environment must be very controlled. The spy process needs to have a very good idea of when to start. If other processes are very active at the same time, then the timing results will be off. Though the attacker could still get valuable information. He would need to run multiple times to get the noise averaged out.
One of the students in class actually saw a demonstration of this attack over the summer. He said that the scenario was being played as the owner of the system running the spy process against a music or video service being run on his machine, the DRM scenario. This assumption was also brought up by Bruce Schneier’s comments on the attack. Scneier’s analysis brings up very good points about the futility of protecting your data (the media company’s data in this case) on an untrusted host (Joe-bob’s computer). If you own both the data and the device, you only have to protect yourself from the “outside”. If you own the data and trust the device, like the scenario of putting your valuables in a safe deposit box in a bank, this is also reasonable. But if you try to give your data to someone you don’t fully trust to “use” for a while you have problems. In the physical world, this is ameliorated by things like deposits and contractual law. But in cyperspace, the ability to trivally make identical copies breaks that physical analogy.
The paper talks of the attack more as a virus, an uninvited program (or maybe that was just my bias reading it). I think this is a more realistic scenario. In the DRM case where the attacker owns the device, it seems like there are more direct ways to get at the data. Sean Smith talks about directly accessing memory of the target process to pull out the information of interest as a means to avoid DRM protections implemented by the Trusted Platform Module (TPM). It would require a tech savvy person to do, but for a commoditized service like movies or videos, it only takes one take savvy person to figure it out and write a utility, and then it is available to the masses. If folks hack Tivo and XBoxes, someone will hack widely used protected music and video services.