On Fri, 6 May 2011 23:14:58 -0400
Nick Mathewson <nickm@xxxxxxxxxxxxx> wrote:
> Also, as I said on the bug, doing a memcmp in constant time is harder
> than doing eq/neq. I *think* that all of the cases where we care
> about memcmp returning a tristate -1/0/1 result, we don't need
> data-independence... but in case we *do* need one, we'll have to do
> some malarkey like
>
> int memcmp(const void *m1, const void *m2, size_t n)
> {
> /*XXX I don't know if this is even right; I haven't tested it at all */
> const uint8_t *b1 = m1, *b2 = m2;
> int retval = 0;
>
> while (n--) {
> const uint8_t v1 = b1[n], v2 = b2[n];
> int diff = (int)v1 - (int)v2;
> retval = (v1 == v2) * retval + diff;
> }
>
> return retval;
> }
>
> which frankly makes me sad. I bet there's a better way to go.
See attached. This one is also untested (and I didn't even put the
â#include <stdint.h>â in the file), but it *should* work.
My technique for calculating equal_p came from my uint32-based
crypto_verify function in my previous message, which was in turn based
partly on DJB's crypto_verify functions and partly on a disassembly of
what GCC compiled DJB's functions to on a Fedora 12 AMD64 box. But I
couldn't tell that the technique was correct, so this time I added
comments to it.
Robert Ransom
int tor_memcmp(const void *x_, const void *y_, size_t len) {
const uint8_t *x = x_;
const uint8_t *y = y_;
size_t i = len;
int retval = 0;
/* The following assumes we are on a system with two's-complement
* arithmetic. */
while (i--) {
int v1 = x_[i];
int v2 = y_[i];
int equal_p = v1 ^ v2;
/* The following sets bits 8 and above of equal_p to equal_p == 0,
and thus to v1 == v2. */
--equal_p;
equal_p >>= 8;
/* Now equal_p is equal to -(v1 == v2), which is exactly
* what we need below. */
/* If v1 == v2, leave retval unchanged; otherwise, zero it. */
retval &= equal_p;
/* If we just zeroed retval, set it to v1 - v2; otherwise, leave
* it unchanged. */
retval += (v1 - v2);
}
return retval;
}
Attachment:
signature.asc
Description: PGP signature
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev