3 ms·
That's one of the most amazing side channel hacks I've ever heard of Thanks! The Osvik-Shamir-Tromer attack on AES via hyperthreading (the same shared-cache i
by cperciva 17y ago
That's one of the most amazing side channel hacks I've ever heard of
Thanks! The Osvik-Shamir-Tromer attack on AES via hyperthreading (the same shared-cache issue, just a different target) was pretty neat too, although I must say that I find my attack on RSA to be more aesthetically pleasing thanks to its ability to steal a key by observing just a single cryptographic operation.
- jacquesm 17y agoNot to put too fine a point on it, but I'm really completely floored by taking this from the general idea of a resource monitoring attack to actually figuring out how to retrieve the contents of the cache and working out which bits map on to which bits in the key. Did you ever get it to a practical level where you were able to retrieve a complete key on a live system in a substantially reduced time ? How much knowledge would you have to have about the process being monitored (in most cases I assume you would not have the luxury of knowing in advance that someone was going to run a key generator, so I assume that you'd have to be monitoring all the time, but then you have to pick the cryptographic activity out of the background of all activity by all processes) ? (what I got from the article is that you basically stopped at the point where you retrieved a significant number of bits, but that leaves as guess as to how long it would take to recover the remainder, through brute force or otherwise, obviously every retrieved bit weakens the number of bit substantially, in other words, how practical is this attack ?). Has intel done something againt this kind of attack on the i7, from the references I take it that you did this work before the i7 was released ? Have you heard of this attack being used in the wild ? edit: re-reading the paper, more questions :) Do the people that write cryptography code spend time making sure that the code will generate as little opportunity to do this by ensuring that the length of the codepaths and the memory footprints of '1' bit operations in keys is the same as it is during the processing of '0' bits in keys ?
- cperciva 17y agoDid you ever get it to a practical level where you were able to retrieve a complete key on a live system in a substantially reduced time ? I retrieved enough key bits to make the rest easily computable, yes. How much knowledge would you have to have about the process being monitored ? Cryptographically speaking? None. Operationally speaking, if you don't know what program is running (or more importantly, what cryptographic library is being used) it may take you a few hours of "eyeballing" the timings before you see something which looks like a modular exponentiation -- but once you find it, you should be able to extract key bits (if the cryptographic code is vulnerable, that is). you retrieved a significant number of bits, but that leaves as guess as to how long it would take to recover the remainder Recovering the remaining bits is just a problem of modular algebra -- computationally speaking it's trivial. Has intel done something againt this kind of attack on the i7 I don't know. I've asked, but they don't want to talk to me. Have you heard of this attack being used in the wild ? Not exactly... but I've heard reports of certain government agencies suddenly getting very interested in how to defend against this sort of attack, so I suspect that some spooks are aware of this attack being used.
- jacquesm 17y agoDo you plan on verifying if this vulnerability is still present in nehalem/i7 ? What about multi-core and level 2 cache monitoring, is that also feasible or do you get too much noise ?
- cperciva 17y agoDo you plan on verifying if this vulnerability is still present in nehalem/i7 ? If I have the time and opportunity, probably. Right now I don't have an i7 processor or the time to spend on it. What about multi-core and level 2 cache monitoring, is that also feasible or do you get too much noise ? Every L2 cache I've seen so far leaks data too slowly to be useful as a cryptographic side channel (at least for attacks like mine).
- jacquesm 17y agoThanks for all your answers, if you ever get around to this and need access to an i7 let me know.
- NateLawson 17y agoAll respect to Colin, especially for his nice visualization of the cache behavior for RSA. However, I think the Tromer paper has more detail on multiple approaches to measuring cache behavior. It also pertains to AES, so you can compare side channel analysis of symmetric algorithms vs. public key. http://people.csail.mit.edu/tromer/papers/cache.pdf http://people.csail.mit.edu/tromer/papers/cache.pdf A lot of approaches can work without "eyeballing" the timings. The Aciicmez paper on BTB predictor side channels shows how you can retrieve the key in a single trace. It shows the interesting result that randomness, such as blinding, has no effect because it only helps when you're trying to compare multiple traces! (They take multiple traces, but then use a heuristic to throw out those that have too much jitter from other system behavior and then only analyze the one best trace.) http://eprint.iacr.org/2006/351 http://eprint.iacr.org/2006/351 http://eprint.iacr.org/2006/482 http://eprint.iacr.org/2006/482 http://eprint.iacr.org/2007/039 http://eprint.iacr.org/2007/039 http://eprint.iacr.org/2007/336 http://eprint.iacr.org/2007/336 This discussion is timely since I've written an article comparing the various side channel attack approaches for IEEE Magazine's Dec 2009 issue. It should be available online soon.