Constant-time comparison function
wiml opened this issue · 5 comments
In addition to the other not-strictly-cryptographic utilities Cryptokit provides (xor_bytes, wipe, etc.) it would be nice if it provided a function to compare bytestrings / Cstructs for equality in constant time.
Hey, thanks for taking a crack at this! I think the function in PR #14 isn't quite constant-time (see my comment there).
I'm not entirely sure how to best write a constant time comparison in OCaml. The usual technique in C is something along these lines:
for(i = 0; i < length; i ++) {
differences = differences | (a[i] ^ b[i])
}
if (differences != 0x00) return false; else return true;This works because there are no data-dependent branches at all (the logic is done by the ^ (bitwise XOR) and | (bitwise OR) operators which are constant time on all hardware that I know of). Presumably the same technique could be used in a fold/accumulate style. But it's hard to know if the OCaml compiler will truly compile it to code without data-dependent branches.
An alternative is that some operating systems do provide a constant time compare in their system libraries (often, but not always, called timingsafe_bcmp()); using that function when it's available might provide a stronger guarantee that a potential super-smart compiler in the future won't break the constant-time behavior. Since that function has different names on different platforms it would require some build-time changes for cryptokit to test for it and use it.
It could just call the C function from OCaml too. cryptokit already implements a lot of in C. I'll take a look at it during the weekend. I did see your comment on the PR too, BTW.
Thank you for catching that up.
Apologies I left this report open for so long. What gave me pause is that there are so many functions in Cryptokit that are (definitely or very likely) not constant-time, hence I was unsure that adding constant-time comparisons would increase security -- and would not give a false sense of security.
On the other hand, the implementation of constant-time comparisons is not difficult: the or-of-xors algorithm you outline should work equally well in OCaml, see #14 for sample code.
Makes a lot of sense.
It may also make sense to inform the users that no functions have constant-time guarantee, and possibly flag the functions that should, that way someone may appear and try to fix it.
I'll update my changes based on your algorithm and resubmit the pull request.
README.md already mentions:
Like all ciphers in this library, the RSA implementation is *not* protected against timing attacks.
Maybe this warning should be more prominent. At any rate, I'm closing this PR since commit 7fd5a8c implements constant-time comparison functions.