Hacker News Reader

Comment by creata | Hacker News Reader

It looks like at least libsodium implements constant-time array comparison in C.

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.

View on HN

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.

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();"

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 - 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 - the impl for u8

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.

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)

Reply on news.ycombinator.com