4 ms·

memcmp compares two blocks of memory byte-by-byte. If the first two bytes don't match, the function can return early, otherwise it has to check the next byte. B

by pipeep 12y ago

memcmp compares two blocks of memory byte-by-byte. If the first two bytes don't match, the function can return early, otherwise it has to check the next byte. By measuring the execution times for all 256 possible bytes, one should be able to guess the first byte. Repeat this for the length of the memory being compared, and you should be able to essentially read the entire block of memory you're being compared against. These attacks are usually done over a fast connection (maybe buy a machine in the same datacenter as your target), and through lots of measurements averaged together and measured for statistical significance. We don't know where this function is used, so this might actually be a non-issue. We need someone more familiar with OpenSSL to comment.

solarexplorer 12y ago
What kind of connection is fast enough to detect the difference of a single loop iteration inside memcmp()? I get that this is type of attack is possible if you share the same machine with the attacker. But over the network? Are there any credible sources for this?
- deleted 12y ago
  [deleted]
- gsnedders 12y ago
  You don't need fast — you need predictable latency, that's all. Once you have predictable latency, you can work out compute time. And latency can become predictable through a large number of samples. Brumley and Boneh's 2003 paper ("Remote timing attacks are practical") on this is the typical reference: http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf
  - solarexplorer 12y ago
    My point is that to receive a single packet, you have an external interrupt, you go through the device driver, the ip stack, etc. And in all that you are looking for a difference of a single cycle. That won't work. Even with a zero latency network. There is just too much code involved. You can measure differences of thousands or maybe even hundreds of cycles, but not single cycles. That's below the noise level of a modern computer.
    - nitrogen 12y ago
      Noise can be filtered out by averaging many samples.
    - gsnedders 12y ago
      Go read the paper. They show (through doing it!) that it's practical.
- CanSpice 12y ago
  You probably want to read this: http://codahale.com/a-lesson-in-timing-attacks/ http://codahale.com/a-lesson-in-timing-attacks/ Particularly the section titled "You can’t possibly measure that, can you?"
  - solarexplorer 12y ago
    Thanks for the link. They claim that they can measure differences as small as 100ns, which is pretty impressive. A single iteration in memcmp is still a lot faster: about 1ns. I have a hard time to see how there is a realistic remote attack in this case.
- dragonwriter 12y ago
  > What kind of connection is fast enough to detect the difference of a single loop iteration inside memcmp()? Any, really, if you hit it with enough copies of each potential input so that you can get enough results to separate the timing difference from the noise. Though the faster, the more samples you can do per unit time, and the closer in network topology, the less sources of variability in latency that make it take more samples you'll have. At least, that's my understanding.
  - tptacek 12y ago
    No, there's a threshold below which you can't effectively distinguish noise from signal even with many samples; theoretically, you can try to overcome this problem with more samples, but there are practical limits, and often actual constraints on the number of samples you can collect and the window of time you have to collect them. Read Crosby and Wallach's "Opportunities and Limits" paper; the shorthand result of the paper is that across Ethernet you have a window of 100ns, and across an IP network something closer to 30us. The memcmp distinguisher is well below the IP network threshold.

by pipeep 12y ago

solarexplorer 12y ago

What kind of connection is fast enough to detect the difference of a single loop iteration inside memcmp()? I get that this is type of attack is possible if you share the same machine with the attacker. But over the network? Are there any credible sources for this?

deleted 12y ago
[deleted]
gsnedders 12y ago
You don't need fast — you need predictable latency, that's all. Once you have predictable latency, you can work out compute time. And latency can become predictable through a large number of samples. Brumley and Boneh's 2003 paper ("Remote timing attacks are practical") on this is the typical reference: http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf
- solarexplorer 12y ago
  My point is that to receive a single packet, you have an external interrupt, you go through the device driver, the ip stack, etc. And in all that you are looking for a difference of a single cycle. That won't work. Even with a zero latency network. There is just too much code involved. You can measure differences of thousands or maybe even hundreds of cycles, but not single cycles. That's below the noise level of a modern computer.
  - nitrogen 12y ago
    Noise can be filtered out by averaging many samples.
  - gsnedders 12y ago
    Go read the paper. They show (through doing it!) that it's practical.
CanSpice 12y ago
You probably want to read this: http://codahale.com/a-lesson-in-timing-attacks/ http://codahale.com/a-lesson-in-timing-attacks/ Particularly the section titled "You can’t possibly measure that, can you?"
- solarexplorer 12y ago
  Thanks for the link. They claim that they can measure differences as small as 100ns, which is pretty impressive. A single iteration in memcmp is still a lot faster: about 1ns. I have a hard time to see how there is a realistic remote attack in this case.
dragonwriter 12y ago
> What kind of connection is fast enough to detect the difference of a single loop iteration inside memcmp()? Any, really, if you hit it with enough copies of each potential input so that you can get enough results to separate the timing difference from the noise. Though the faster, the more samples you can do per unit time, and the closer in network topology, the less sources of variability in latency that make it take more samples you'll have. At least, that's my understanding.
- tptacek 12y ago
  No, there's a threshold below which you can't effectively distinguish noise from signal even with many samples; theoretically, you can try to overcome this problem with more samples, but there are practical limits, and often actual constraints on the number of samples you can collect and the window of time you have to collect them. Read Crosby and Wallach's "Opportunities and Limits" paper; the shorthand result of the paper is that across Ethernet you have a window of 100ns, and across an IP network something closer to 30us. The memcmp distinguisher is well below the IP network threshold.