3 ms·

Really interesting idea. I would be curious to see if this could be embedded into a proc macro in Rust, allowing one to do something like this: fn compare_

Really interesting idea. I would be curious to see if this could be embedded into a proc macro in Rust, allowing one to do something like this: fn compare_hashes(a: &[u8], b: &[u8]) -> bool { let size = a.len(); fact!{ for (uint64 i from 0 to size) { if (x[i] != y[i]) { return -1; } } return 0; } } It would get compiled into asm and inlined. I'm also wondering how this interacts with bounds checking, which would introduce branches. I tried searching the paper (sorry, no time to read the whole thing today) for 'bounds' but did not get a result. Semi-related. One (insufficient) option for dealing with timing leaks is to add a random delay. ie: `sleep_ms(rand(1,1000))`. The problem is that given N leaks an attacker can remove that noise. I have two questions here: 1. What is "N"? 2. Does that sleeping introduce any additional vulnerabilities? Basically, is this a "if you can afford that latency it won't hurt".

_nhynes 4y ago
Rust has some great constant time libs already, for instance `subtle` [0]. A `derive(ConstantTimeEq)` might get you most of the way, but a constant-timeifier would be great for wrapping whole algos where you might not want to think too hard about timing side channels. For your sleeping proposal, it sounds a little like differential privacy [1] where you can add some randomness to gain some privacy but spend some of the predetermined privacy budget. In that case, `N` depends on the (roughly) variance of the computation time, the noise amount, and your privacy budget. If you get it right, it has provable security properties. However, that doesn't work as well when the adversary has access to the machine and can observe the intermediate state (or side channel leaks thereof). [0]: https://github.com/dalek-cryptography/subtle https://github.com/dalek-cryptography/subtle [1]: https://blog.openmined.org/privacy-series-basics-definition/ https://blog.openmined.org/privacy-series-basics-definition/
jonhohle 4y ago
For comparisons, the normal “trick” is to & a failure flag for every character in the hashes so you’ll always compare the same number of characters. At the end, the failure flag is returned. This may cost more time in obvious failure cases, but eliminates timing oracles (assuming comparison and & operations require the same number of cycles regardless of the operands).
kqr 4y ago
If you add the same delay for the same input there's no statistical way to remove the noise because at that point it's no longer noise -- it's bias. That said, it's fairly easy to tell if a CPU spends time sleeping or doing actual work, so it depends on who is in control of the CPU.
- insanitybit 4y ago
  Oh, interest. So something like `sleep_ms(0, hash(input) % 1000)`
comex 4y ago
A better alternative is to sleep, not for a fixed time period after the end of the operation, but until a fixed amount of time after the start of the operation (assuming the operation never takes longer than that). That way, in theory, the total time taken is independent of any variability in the timing of the operation itself. But there’s still a high risk of some side channel letting the attacker tell when the program is working and when it’s sleeping.

_nhynes 4y ago

Rust has some great constant time libs already, for instance `subtle` [0]. A `derive(ConstantTimeEq)` might get you most of the way, but a constant-timeifier would be great for wrapping whole algos where you might not want to think too hard about timing side channels. For your sleeping proposal, it sounds a little like differential privacy [1] where you can add some randomness to gain some privacy but spend some of the predetermined privacy budget. In that case, `N` depends on the (roughly) variance of the computation time, the noise amount, and your privacy budget. If you get it right, it has provable security properties. However, that doesn't work as well when the adversary has access to the machine and can observe the intermediate state (or side channel leaks thereof). [0]: https://github.com/dalek-cryptography/subtle https://github.com/dalek-cryptography/subtle [1]: https://blog.openmined.org/privacy-series-basics-definition/ https://blog.openmined.org/privacy-series-basics-definition/

jonhohle 4y ago

For comparisons, the normal “trick” is to & a failure flag for every character in the hashes so you’ll always compare the same number of characters. At the end, the failure flag is returned. This may cost more time in obvious failure cases, but eliminates timing oracles (assuming comparison and & operations require the same number of cycles regardless of the operands).

kqr 4y ago

If you add the same delay for the same input there's no statistical way to remove the noise because at that point it's no longer noise -- it's bias. That said, it's fairly easy to tell if a CPU spends time sleeping or doing actual work, so it depends on who is in control of the CPU.

insanitybit 4y ago
Oh, interest. So something like `sleep_ms(0, hash(input) % 1000)`

comex 4y ago

A better alternative is to sleep, not for a fixed time period after the end of the operation, but until a fixed amount of time after the start of the operation (assuming the operation never takes longer than that). That way, in theory, the total time taken is independent of any variability in the timing of the operation itself. But there’s still a high risk of some side channel letting the attacker tell when the program is working and when it’s sleeping.