21 ms·

An acquaintance of mine implemented a solution to this problem: it's an implementation of AES that used no tables and no branches; it used the shuffle instructi

An acquaintance of mine implemented a solution to this problem: it's an implementation of AES that used no tables and no branches; it used the shuffle instruction (pshufb) in a very creative way combined with a different interpretation of the AES algorithm to make it possible. It should be invulnerable to (at least standard) timing and cache attacks. For bonus points, it was also far faster than most standard implementations. Link to the paper: http://mikehamburg.com/papers/vector_aes/vector_aes.pdf http://mikehamburg.com/papers/vector_aes/vector_aes.pdf

tptacek 17y ago
All mainstream modern crypto libraries are hardened in one way or another against timing attacks (Nate Lawson can probably be counted on to jump in here and correct us on this), but to my mind the bigger concern is that we simply don't know what trails our code is leaving inside the processor. Processor microarchitecture is vast, undocumented, complicated, and intricate.
- jacquesm 17y ago
  Essentially you'd have to audit the entire cpu design to be sure that you didn't leave any fat fingerprints all over the place. Any flip-flop that had changed state in a recoverable way would be a potential security leak. Good luck getting that kind of access to a cpu design though, and even better luck trying to figure out all the angles of attack, miss one and someone else has a vector, silicon is hard to change after the fact. What is interesting here to me about this whole subject is that it has apparently long ago gone from 'theoretical' to 'practical', and you'd be hard pressed to prove that you didn't lose a key or two (or all of them) to an attacker sophisticated enough to do his snooping and then disappear quietly. After all, any hack or hacker that you read about or hear about wasn't as good as they could have been, the ones you never hear about are the ones to worry about. For me this whole idea of having someone plant a piece of software on a machine that I own without me detecting it was a prime reason in choosing not to do my own card processing (even though in the dark ages I wrote 'webpay', which later became the foundation for a major IPSP). I realized that by simply having a page hosted that accepts credit cards on a https connection I would basically be putting up an open 'hack me' invite.
  - tptacek 17y ago
    You want to google "Remote Timing Attacks Are Practical", which is the landmark paper in this subfield and also the one crypto people use to scare their children around campfires with. What you're really observing is the flip side of the "covert channel problem", which has been a well-known Hard Problem driving systems research since the '70s (it's part of Saltzer/Schroeder). Systems security people generally concede that the covert channel problem is impractical to solve in theory, and have resigned themselves to occasional fire drills as theory becomes practice.
    - jacquesm 17y ago
      Maybe I'm thinking about this too simply, but wouldn't fugding the timing on any cryptographic operation in a random fashion make it (much) harder to deduce the keys ?
      - tptacek 17y ago
        No. This is basic signal processing. Increase the noise, and all you do is increase the number of measurements needed to recover the signal. This is a really common misconception about defeating timing attacks. A more pernicious problem is that many of these microarch side channel attacks don't rely on direct timing of crypto code, so much as on microarch artifacts. (For what it's worth, the specifics beyond this get to a place where I'm out of my depth and Colin and Nate are still in theirs.)
        jacquesm 17y ago
        Right, I get that, increase the noise by a factor of two and you'd need more samples, increasing the chance of detection but ultimately not making the problem much harder. But every factor of two that you make it harder is effectively one bit extra on the key that you're trying to find right ? Assuming that's true (going out on a limb here) the more you are willing to waste time the harder it will get for an attacker to recover the keys, so ultimately it is a measure of efficiency vs security. As for micro architecture, I don't know much about that other than reading up on the 68K when it came out and how it functioned at the block level, but one way to side-step that issue completely if you want to write bullet proof crypto code (if that is even possible) would be to write it for a controller on a separate plug in card (pci, possibly usb) that would be permitted to allow exactly one crypto operation per fixed interval of time to be performed. That way you could effectively 'hide' the key and all its side-effects from view from both local and remote attackers. It would then take at a minimum physical access to the card to monitor its buses in order to recover they keys.
- NateLawson 17y ago
  There are some newer countermeasures but openssl doesn't implement any of them. http://eprint.iacr.org/2007/282 http://eprint.iacr.org/2007/282 I just took a quick look at 0.9.8h and this is still the case. The C code (aes_core.c) is the standard "alg-fst" version. The asm code in the subdirectory is faster but has no masking. In short, if you want timing attack resistance, you can't just expect it in standard libraries.
NateLawson 17y ago
That's a nice paper. Bitsliced implementations, for those who don't know, use sequential instructions to perform parallel computation. They compute the logic function for the S-boxes instead of a lookup table. Here's Biham's original paper on bitsliced DES. I think it's a good intro to this approach. http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1997/CS/CS0891 http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?...

tptacek 17y ago

All mainstream modern crypto libraries are hardened in one way or another against timing attacks (Nate Lawson can probably be counted on to jump in here and correct us on this), but to my mind the bigger concern is that we simply don't know what trails our code is leaving inside the processor. Processor microarchitecture is vast, undocumented, complicated, and intricate.

jacquesm 17y ago
Essentially you'd have to audit the entire cpu design to be sure that you didn't leave any fat fingerprints all over the place. Any flip-flop that had changed state in a recoverable way would be a potential security leak. Good luck getting that kind of access to a cpu design though, and even better luck trying to figure out all the angles of attack, miss one and someone else has a vector, silicon is hard to change after the fact. What is interesting here to me about this whole subject is that it has apparently long ago gone from 'theoretical' to 'practical', and you'd be hard pressed to prove that you didn't lose a key or two (or all of them) to an attacker sophisticated enough to do his snooping and then disappear quietly. After all, any hack or hacker that you read about or hear about wasn't as good as they could have been, the ones you never hear about are the ones to worry about. For me this whole idea of having someone plant a piece of software on a machine that I own without me detecting it was a prime reason in choosing not to do my own card processing (even though in the dark ages I wrote 'webpay', which later became the foundation for a major IPSP). I realized that by simply having a page hosted that accepts credit cards on a https connection I would basically be putting up an open 'hack me' invite.
- tptacek 17y ago
  You want to google "Remote Timing Attacks Are Practical", which is the landmark paper in this subfield and also the one crypto people use to scare their children around campfires with. What you're really observing is the flip side of the "covert channel problem", which has been a well-known Hard Problem driving systems research since the '70s (it's part of Saltzer/Schroeder). Systems security people generally concede that the covert channel problem is impractical to solve in theory, and have resigned themselves to occasional fire drills as theory becomes practice.
  - jacquesm 17y ago
    Maybe I'm thinking about this too simply, but wouldn't fugding the timing on any cryptographic operation in a random fashion make it (much) harder to deduce the keys ?
    - tptacek 17y ago
      No. This is basic signal processing. Increase the noise, and all you do is increase the number of measurements needed to recover the signal. This is a really common misconception about defeating timing attacks. A more pernicious problem is that many of these microarch side channel attacks don't rely on direct timing of crypto code, so much as on microarch artifacts. (For what it's worth, the specifics beyond this get to a place where I'm out of my depth and Colin and Nate are still in theirs.)
      - jacquesm 17y ago
        Right, I get that, increase the noise by a factor of two and you'd need more samples, increasing the chance of detection but ultimately not making the problem much harder. But every factor of two that you make it harder is effectively one bit extra on the key that you're trying to find right ? Assuming that's true (going out on a limb here) the more you are willing to waste time the harder it will get for an attacker to recover the keys, so ultimately it is a measure of efficiency vs security. As for micro architecture, I don't know much about that other than reading up on the 68K when it came out and how it functioned at the block level, but one way to side-step that issue completely if you want to write bullet proof crypto code (if that is even possible) would be to write it for a controller on a separate plug in card (pci, possibly usb) that would be permitted to allow exactly one crypto operation per fixed interval of time to be performed. That way you could effectively 'hide' the key and all its side-effects from view from both local and remote attackers. It would then take at a minimum physical access to the card to monitor its buses in order to recover they keys.
NateLawson 17y ago
There are some newer countermeasures but openssl doesn't implement any of them. http://eprint.iacr.org/2007/282 http://eprint.iacr.org/2007/282 I just took a quick look at 0.9.8h and this is still the case. The C code (aes_core.c) is the standard "alg-fst" version. The asm code in the subdirectory is faster but has no masking. In short, if you want timing attack resistance, you can't just expect it in standard libraries.

NateLawson 17y ago

That's a nice paper. Bitsliced implementations, for those who don't know, use sequential instructions to perform parallel computation. They compute the logic function for the S-boxes instead of a lookup table. Here's Biham's original paper on bitsliced DES. I think it's a good intro to this approach. http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1997/CS/CS0891 http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?...