5 ms·

It looks like at least libsodium implements constant-time array comparison in C. https://github.com/jedisct1/libsodium/blob/ae4add868124a32d4e54da10f9cd99240ae

by creata 6y ago

It looks like at least libsodium implements constant-time array comparison in C. https://github.com/jedisct1/libsodium/blob/ae4add868124a32d4e54da10f9cd99240aecc0aa/src/libsodium/sodium/utils.c#L179-L201 https://github.com/jedisct1/libsodium/blob/ae4add868124a32d4... Edit: I'm not disagreeing that C compilers are free to optimize stuff like this out; this comment is for people who (like me) thought that serious projects always used assembly for constant time operations.

Arnavion 6y ago
And indeed the XOR method is also how it's implemented in Rust. https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#226-244 https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#226-244 - the impl for [u8], where the per-element ct_eq is https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#259-272 https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#259-272 - the impl for u8
dfox 6y ago
Which is prime example as to how C does not consider timing to be observable behavior. What the code does is that it tries to specify the operation in sufficiently complex way that makes compiler give up on any optimizations.
- dvdkhlng 6y ago
  Note how this problem of "sufficient complexity" is an asymmetric problem between code author and compiler. A rather simple transformation implemented by the author to make the code constant-time may require NP-hard effort for the compiler to undo. (but then the compiler may still do other unrelated transformations that end up making the code non-constant time again)
Denvercoder9 6y ago
There's nothing that guarantees that's constant-time. It's just written in a way that's likely to be constant-time, and observed to be constant-time with current compilers, but there's no reason why a specification-compliant compiler couldn't make it variable-time tomorrow. You can do exactly the same in Rust. Rust isn't any help there, but it doesn't obstruct you either.
kroeckx 6y ago
We've had code in OpenSSL written in C that was constant time until a newer version of both gcc and clang recognized (mask & a | ~mask & b) as a conditional assign and could do things like turn it into a branch. Edit: It can turn "b = foo(); c = (mask & a | ~mask & b)" into "if (mask) c = a; else c = foo();"

by creata 6y ago

Arnavion 6y ago

And indeed the XOR method is also how it's implemented in Rust. https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#226-244 https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#226-244 - the impl for [u8], where the per-element ct_eq is https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#259-272 https://docs.rs/subtle/2.4.0/src/subtle/lib.rs.html#259-272 - the impl for u8

dfox 6y ago

Which is prime example as to how C does not consider timing to be observable behavior. What the code does is that it tries to specify the operation in sufficiently complex way that makes compiler give up on any optimizations.

dvdkhlng 6y ago
Note how this problem of "sufficient complexity" is an asymmetric problem between code author and compiler. A rather simple transformation implemented by the author to make the code constant-time may require NP-hard effort for the compiler to undo. (but then the compiler may still do other unrelated transformations that end up making the code non-constant time again)

Denvercoder9 6y ago

There's nothing that guarantees that's constant-time. It's just written in a way that's likely to be constant-time, and observed to be constant-time with current compilers, but there's no reason why a specification-compliant compiler couldn't make it variable-time tomorrow. You can do exactly the same in Rust. Rust isn't any help there, but it doesn't obstruct you either.

kroeckx 6y ago

We've had code in OpenSSL written in C that was constant time until a newer version of both gcc and clang recognized (mask & a | ~mask & b) as a conditional assign and could do things like turn it into a branch. Edit: It can turn "b = foo(); c = (mask & a | ~mask & b)" into "if (mask) c = a; else c = foo();"