4 ms·
How is this good code? x |= MAC_computed[i] − MAC_computed[i]; Shouldn't one side or the other (of the minus operation) be MAC_received[i]?
by natch 17y ago
How is this good code?
x |= MAC_computed[i] − MAC_computed[i];
Shouldn't one side or the other (of the minus operation) be MAC_received[i]?
- cperciva 17y agoYes, that's a typo. Sorry. (Lesson learned: LaTex is not the best language to write code in.)
- natch 17y agoDO: Do what Bruce Eckel does, and have all code in a publication run through automated tests before releasing it. ;-). And... you're welcome?
- Robin_Message 17y agoAlso, x |= MAC received[i] − MAC computed[i]; Is making me twitchy, I mean I'm sure we're on two's complement machines and there is no C compiler in the world where those two could be unequal but still subtract to zero* , but still, how about one of x |= (MAC received[i] != MAC computed[i]); x |= (MAC received[i] ^ MAC computed[i]); Otherwise, Good stuff! * Possible break: If we have a separate sign bit, then we might have 0 and -0, which would subtract to give 0. Don't know of any machine/compiler that does that though.
- caf 17y agoYour != proposed change likely results in a branch, which is what we're trying to avoid. The ^ version is fine, but the original subtraction is too as long as they're unsigned.
- NateLawson 17y agoI wrote about this mistake before. Developers see a single-line RHS expression and think it evaluates without branching. http://rdist.root.org/2010/01/07/timing-independent-array-comparison/ http://rdist.root.org/2010/01/07/timing-independent-array-co...
- sparky 17y agoAre you sure? All architectures I am aware of have mechanisms to do this in a branchless way. On my machine: int main(int argc, char argv) { int x = 0; x |= (argc != 1); return x; } Relevant portion of assembly (no optimizations): cmpl $1, -20(%rbp) setne %al movzbl %al, %eax orl %eax, -4(%rbp) Most other architectures have one of: 1) condition codes that you can use to predicate an "or $r1, $r1, 1" (e.g., ARM) 2) compare instructions that put a 1 or a 0 in a result register, which can be directly ORed in. (e.g., MIPS) Of course, that code only works if you are either not writing in C89 or if your compiler and ISA conspire to always return exactly one from true boolean expressions. It is my understanding that the C89 standard only requires "nonzero," so you might need "a |= (b != c) ? 1 : 0;*" instead. YMMV depending on compiler and architecture, but the 2 or 3 platforms I tried without passing any opti flags were branchless. Test program:
- cperciva 17y agoI always use ^ when I write this code, but that made LaTex unhappy, so I switched to subtraction instead for the talk.
- yread 17y agoAnd why is the original way of not completing the for cycle for some keys wrong? Is the difference between checking the whole array and checking only lets say first byte measurable? Especially when considering that this would probably be done over a network?
- cperciva 17y agoYes, it is measurable. Remote timing attacks are scarily practical -- even a single cycle difference can be a problem, because an attacker can many many attempts and compute the average time in order to kill the noise.
- tptacek 17y agoThe current state of the art in remote measurement (which is in its infancy; the first papers to apply basic signal processing on measurement over IP networks are just coming out) suggest that the timeable thresholds are in the tens of microseconds over a WAN. But that doesn't matter, because over switched "local" networks (read: from one end of a data center to another), the thresholds are in nanoseconds; everything is timeable. Attackers will spend the $30 to get a machine in the same hosting center as you as soon as the other attacks get less trivial.
- mukyu 17y agoTiming attacks like this have been successfully used against a few gaming consoles.
- NateLawson 17y agoIn particular, a memcmp()-style timing attack was successful against the Xbox360 CPU. This is a multi-Ghz processor.