3 ms·

a += b; d ^= a; d <<<= 16; c += d; b ^= c; b <<<= 12; a += b; d ^= a; d <<<= 8; c += d; b ^= c; b <<<= 7; I'm curious: could a C compiler

by zeveb 10y ago

a += b; d ^= a; d <<<= 16; c += d; b ^= c; b <<<= 12; a += b; d ^= a; d <<<= 8; c += d; b ^= c; b <<<= 7; I'm curious: could a C compiler look at the quarter-round function above and determine that a+b (or the other terms) might overflow a 32-bit integer, and thus invoke undefined behaviour to eliminate the loop entirely?

cesarb 10y ago
In C, unsigned overflow is defined as wrapping, and all these numbers are unsigned. It's signed overflow that's undefined in C.
- Gibbon1 10y ago
  'Safe for for now' Notable I think the NaCl crypto library implements a compare as follows uint32_t diff_bits = 0; diff_bits |= x[0] ^ y[0]; ... diff_bits |= x[31] ^ y[31]; return (1 & ((diff_bits - 1) >> 8)) - 1; This because memcmp() leaks timing information. And implementing it with a for loop also leaks. Longer term worry is the optimizer will figure the above out as well.
  - nullc 10y ago
    > 'Safe for for now' No, unconditionally safe. The C standard exactly defines unsigned overflow while specifically leaving signed overflow undefined. (Pedantically timing is always a crapshoot in C, a compiler only need produce the same results as the abstract machine. It could freely take all your secret data and modulate it into the timing and be conforming. -- but considering that intel/amd won't make timing promises about the instructions themselves...)
  - loup-vaillant 10y ago
    > And implementing it with a for loop also leaks. Assuming you're talking about this for loop: for (int i = 0; i < 32; i++) // safe branch diff_bits |= x[i] ^ y[i]; then no, it doesn't leak, because the result of the resulting conditional branch doesn't depend on a secret. The only reason NaCl unrolls that loop is because neeed moar speeed. If you were talking about the early return straightforward for loop: for (int i = 0; i < 32; i++) // safe branch if (x[i] != y[i]) // timing leak... return -1; // ...magnified Then yeah, it leaks. > Longer term worry is the optimizer will figure the above out as well. It may, but even compiler implementers realise the value of constant time code. Replacing this code with an early return doesn't just require very sophisticated optimisations, it never happens outside of a crypto library. There is little incentive for compiler writers to do this.
    - Gibbon1 10y ago
      Problem is the optimizer is totally free to implement the 'safe' code snippet using an 'unsafe' early return. According to the standard that would be completely legal.
      - loup-vaillant 10y ago
        Correct. It can. I was just explaining why I think it won't anyway.
      - wolf550e 10y ago
        A compiler that did this optimization would immediately introduce a pragma guaranteed to result in constant time memcmp from some blessed source pattern. Maintainers of crypto libraries inspect the assembly when upgrading their compilers, test with many compilers and document the versions of compilers they support.
Veedrac 10y ago
Even if it were undefined behaviour, it would still only be conditionally undefined. A compiler can only eliminate a code path that unconditionally results in undefined behaviour.
jcranmer 10y ago
Even if the numbers were signed (unsigned overflow is well-defined), being able to eliminate the loop would require knowing that overflow MUST occur, not that it MAY occur.

by zeveb 10y ago

cesarb 10y ago

In C, unsigned overflow is defined as wrapping, and all these numbers are unsigned. It's signed overflow that's undefined in C.

Gibbon1 10y ago
'Safe for for now' Notable I think the NaCl crypto library implements a compare as follows uint32_t diff_bits = 0; diff_bits |= x[0] ^ y[0]; ... diff_bits |= x[31] ^ y[31]; return (1 & ((diff_bits - 1) >> 8)) - 1; This because memcmp() leaks timing information. And implementing it with a for loop also leaks. Longer term worry is the optimizer will figure the above out as well.
- nullc 10y ago
  > 'Safe for for now' No, unconditionally safe. The C standard exactly defines unsigned overflow while specifically leaving signed overflow undefined. (Pedantically timing is always a crapshoot in C, a compiler only need produce the same results as the abstract machine. It could freely take all your secret data and modulate it into the timing and be conforming. -- but considering that intel/amd won't make timing promises about the instructions themselves...)
- loup-vaillant 10y ago
  > And implementing it with a for loop also leaks. Assuming you're talking about this for loop: for (int i = 0; i < 32; i++) // safe branch diff_bits |= x[i] ^ y[i]; then no, it doesn't leak, because the result of the resulting conditional branch doesn't depend on a secret. The only reason NaCl unrolls that loop is because neeed moar speeed. If you were talking about the early return straightforward for loop: for (int i = 0; i < 32; i++) // safe branch if (x[i] != y[i]) // timing leak... return -1; // ...magnified Then yeah, it leaks. > Longer term worry is the optimizer will figure the above out as well. It may, but even compiler implementers realise the value of constant time code. Replacing this code with an early return doesn't just require very sophisticated optimisations, it never happens outside of a crypto library. There is little incentive for compiler writers to do this.
  - Gibbon1 10y ago
    Problem is the optimizer is totally free to implement the 'safe' code snippet using an 'unsafe' early return. According to the standard that would be completely legal.
    - loup-vaillant 10y ago
      Correct. It can. I was just explaining why I think it won't anyway.
    - wolf550e 10y ago
      A compiler that did this optimization would immediately introduce a pragma guaranteed to result in constant time memcmp from some blessed source pattern. Maintainers of crypto libraries inspect the assembly when upgrading their compilers, test with many compilers and document the versions of compilers they support.

Veedrac 10y ago

Even if it were undefined behaviour, it would still only be conditionally undefined. A compiler can only eliminate a code path that unconditionally results in undefined behaviour.

jcranmer 10y ago

Even if the numbers were signed (unsigned overflow is well-defined), being able to eliminate the loop would require knowing that overflow MUST occur, not that it MAY occur.