3 ms·

> Especially for security-critical operations, it is often a good idea to disassemble the relevant sections of the binary and ensure that things are handled app

by zrm 7y ago

> Especially for security-critical operations, it is often a good idea to disassemble the relevant sections of the binary and ensure that things are handled appropriately. The problem there being that a) all code is security-critical if the compiler elides a bounds check or turns it into a buffer overrun or just crashes and allows for DoS, and b) that requires you to inspect the code generated by every compiler that will be used to compile the code, which for published source code could be any compiler in the world, including ones that don't exist yet.

jancsika 7y ago
Wouldn't WASM help here? One could choose a popular dev target like Ubuntu LTS and seek to comprehend the relevant optimization behavior for a popular compiler like GCC. Now part b above is reduced to a single environment to generate a binary for all archs where WASM will run.
marcosdumay 7y ago
If a compiler issues code that elides a bound check or crashes for good source, it is broken. If a compiler optimizes your constant time algorithm into a completely equivalent one with varying time, it did nothing wrong, except on security-critical code.
- zrm 7y ago
  Suppose you have a function that looks like this: void f(int a[], size_t len) { size_t i=0; while(1) { int val = a[i++]; if(i > len) break; do_something(val); } } You would expect for this code to call do_something() for the first len values in a[], which will be the result on a lot of compilers. But suppose the true length of a[] is exactly equal to len, and the compiler is aware of that. Then when i is greater than or equal to len, reading a[i] is undefined behavior. That means that either the bounds check is always false and can be elided, or it isn't false which means there is undefined behavior that allows the compiler to do anything it wants, and maybe what it wants is to elide the bounds check as an optimization. So it does and the compiled code will keep executing do_something() on every value in memory after a[]. The code is wrong, but not in a way which is intuitively obvious, and not in way that compilers had historically taken advantage of to such deleterious effect. And you can't figure that out by looking at the compiler output for a compiler that doesn't take that optimization.
  - marcosdumay 7y ago
    The code is wrong, and the compiler has no correct option to use. Whatever it decides to do is ok. This is completely different from the program: int f (char* a, size_t len_a, char* b, size_t len_b) { size_t i = 0; int eq = 1; while (i < len_a && i < len_b) { if (a[i] != b[i]) eq = 0; i++; } return eq && i == len_a && i == len_b; } If you pass two strings that differ on the first character, do you expect it to run through all the characters or return at the first? Both will have exactly the same result, and compilers know how to convert one into the other. If you use code that returns early on a function that verifies user password hashes on a web site, you'll just leak all of your users passwords.
    - zrm 7y ago
      The first function is wrong because it leaves the compiler the discretion to do something dangerous. But isn't that the same problem as the second function? The compiler has much more discretion in the first case, all the way to nasal demons and flying monkeys, but that's little consolation when the discretion it does have in the second case is to do exactly the thing that makes the function insecure. "Whatever it decides to do is ok," but some of the things it can decide to do will leak your password hashes. Throw in Spectre and it's a huge mess, because it's not just the password hashing function leaking the password hashes, it's anything with an exploitable bounds check that can reach the memory where they're stored.

by zrm 7y ago

jancsika 7y ago

Wouldn't WASM help here? One could choose a popular dev target like Ubuntu LTS and seek to comprehend the relevant optimization behavior for a popular compiler like GCC. Now part b above is reduced to a single environment to generate a binary for all archs where WASM will run.

marcosdumay 7y ago

If a compiler issues code that elides a bound check or crashes for good source, it is broken. If a compiler optimizes your constant time algorithm into a completely equivalent one with varying time, it did nothing wrong, except on security-critical code.

zrm 7y ago
Suppose you have a function that looks like this: void f(int a[], size_t len) { size_t i=0; while(1) { int val = a[i++]; if(i > len) break; do_something(val); } } You would expect for this code to call do_something() for the first len values in a[], which will be the result on a lot of compilers. But suppose the true length of a[] is exactly equal to len, and the compiler is aware of that. Then when i is greater than or equal to len, reading a[i] is undefined behavior. That means that either the bounds check is always false and can be elided, or it isn't false which means there is undefined behavior that allows the compiler to do anything it wants, and maybe what it wants is to elide the bounds check as an optimization. So it does and the compiled code will keep executing do_something() on every value in memory after a[]. The code is wrong, but not in a way which is intuitively obvious, and not in way that compilers had historically taken advantage of to such deleterious effect. And you can't figure that out by looking at the compiler output for a compiler that doesn't take that optimization.
- marcosdumay 7y ago
  The code is wrong, and the compiler has no correct option to use. Whatever it decides to do is ok. This is completely different from the program: int f (char* a, size_t len_a, char* b, size_t len_b) { size_t i = 0; int eq = 1; while (i < len_a && i < len_b) { if (a[i] != b[i]) eq = 0; i++; } return eq && i == len_a && i == len_b; } If you pass two strings that differ on the first character, do you expect it to run through all the characters or return at the first? Both will have exactly the same result, and compilers know how to convert one into the other. If you use code that returns early on a function that verifies user password hashes on a web site, you'll just leak all of your users passwords.
  - zrm 7y ago
    The first function is wrong because it leaves the compiler the discretion to do something dangerous. But isn't that the same problem as the second function? The compiler has much more discretion in the first case, all the way to nasal demons and flying monkeys, but that's little consolation when the discretion it does have in the second case is to do exactly the thing that makes the function insecure. "Whatever it decides to do is ok," but some of the things it can decide to do will leak your password hashes. Throw in Spectre and it's a huge mess, because it's not just the password hashing function leaking the password hashes, it's anything with an exploitable bounds check that can reach the memory where they're stored.