Back to index

tor  0.2.3.19-rc
Defines | Functions
di_ops.h File Reference

Headers for di_ops.c. More...

#include "orconfig.h"
#include "torint.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines

#define tor_memneq(a, b, sz)   (!tor_memeq((a),(b),(sz)))
#define fast_memcmp(a, b, c)   (memcmp((a),(b),(c)))
 Alias for the platform's memcmp() function.
#define fast_memeq(a, b, c)   (0==memcmp((a),(b),(c)))
#define fast_memneq(a, b, c)   (0!=memcmp((a),(b),(c)))

Functions

int tor_memcmp (const void *a, const void *b, size_t sz)
 Timing-safe version of memcmp.
int tor_memeq (const void *a, const void *b, size_t sz)
 Timing-safe memory comparison.

Detailed Description

Headers for di_ops.c.

Definition in file di_ops.h.


Define Documentation

#define fast_memcmp (   a,
  b,
 
)    (memcmp((a),(b),(c)))

Alias for the platform's memcmp() function.

This function is not data-independent: we define this alias so that we can mark cases where we are deliberately using a data-dependent memcmp() implementation.

Definition at line 26 of file di_ops.h.

#define fast_memeq (   a,
  b,
 
)    (0==memcmp((a),(b),(c)))

Definition at line 27 of file di_ops.h.

#define fast_memneq (   a,
  b,
 
)    (0!=memcmp((a),(b),(c)))

Definition at line 28 of file di_ops.h.

#define tor_memneq (   a,
  b,
  sz 
)    (!tor_memeq((a),(b),(sz)))

Definition at line 19 of file di_ops.h.


Function Documentation

int tor_memcmp ( const void *  a,
const void *  b,
size_t  len 
)

Timing-safe version of memcmp.

As memcmp, compare the sz bytes at a with the sz bytes at b, and return less than 0 if the bytes at a lexically precede those at b, 0 if the byte ranges are equal, and greater than zero if the bytes at a lexically follow those at b.

This implementation differs from memcmp in that its timing behavior is not data-dependent: it should return in the same amount of time regardless of the contents of a and b.

Definition at line 24 of file di_ops.c.

{
  const uint8_t *x = a;
  const uint8_t *y = b;
  size_t i = len;
  int retval = 0;

  /* This loop goes from the end of the arrays to the start.  At the
   * start of every iteration, before we decrement i, we have set
   * "retval" equal to the result of memcmp(a+i,b+i,len-i).  During the
   * loop, we update retval by leaving it unchanged if x[i]==y[i] and
   * setting it to x[i]-y[i] if x[i]!= y[i].
   *
   * The following assumes we are on a system with two's-complement
   * arithmetic.  We check for this at configure-time with the check
   * that sets USING_TWOS_COMPLEMENT.  If we aren't two's complement, then
   * torint.h will stop compilation with an error.
   */
  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.  (To see this, note that if v1 ==
     * v2, then v1^v2 == equal_p == 0, so equal_p-1 == -1, which is the
     * same as ~0 on a two's-complement machine.  Then note that if
     * v1 != v2, then 0 < v1 ^ v2 < 256, so 0 <= equal_p - 1 < 255.)
     */
    --equal_p;

    equal_p >>= 8;
    /* Thanks to (sign-preserving) arithmetic shift, equal_p is now
     * equal to -(v1 == v2), which is exactly what we need below.
     * (Since we're assuming two's-complement arithmetic, -1 is the
     * same as ~0 (all bits set).)
     *
     * (The result of an arithmetic shift on a negative value is
     * actually implementation-defined in standard C.  So how do we
     * get away with assuming it?  Easy.  We check.) */
#if ((-60 >> 8) != -1)
#error "According to cpp, right-shift doesn't perform sign-extension."
#endif
#ifndef RSHIFT_DOES_SIGN_EXTEND
#error "According to configure, right-shift doesn't perform sign-extension."
#endif

    /* If v1 == v2, equal_p is ~0, so this will leave retval
     * unchanged; otherwise, equal_p is 0, so this will zero it. */
    retval &= equal_p;

    /* If v1 == v2, then this adds 0, and leaves retval unchanged.
     * Otherwise, we just zeroed retval, so this sets it to v1 - v2. */
    retval += (v1 - v2);

    /* There.  Now retval is equal to its previous value if v1 == v2, and
     * equal to v1 - v2 if v1 != v2. */
  }

  return retval;
}

Here is the caller graph for this function:

int tor_memeq ( const void *  a,
const void *  b,
size_t  sz 
)

Timing-safe memory comparison.

Return true if the sz bytes at a are the same as the sz bytes at b, and 0 otherwise.

This implementation differs from !memcmp(a,b,sz) in that its timing behavior is not data-dependent: it should return in the same amount of time regardless of the contents of a and b. It differs from !tor_memcmp(a,b,sz) by being faster.

Definition at line 96 of file di_ops.c.

{
  /* Treat a and b as byte ranges. */
  const uint8_t *ba = a, *bb = b;
  uint32_t any_difference = 0;
  while (sz--) {
    /* Set byte_diff to all of those bits that are different in *ba and *bb,
     * and advance both ba and bb. */
    const uint8_t byte_diff = *ba++ ^ *bb++;

    /* Set bits in any_difference if they are set in byte_diff. */
    any_difference |= byte_diff;
  }

  /* Now any_difference is 0 if there are no bits different between
   * a and b, and is nonzero if there are bits different between a
   * and b.  Now for paranoia's sake, let's convert it to 0 or 1.
   *
   * (If we say "!any_difference", the compiler might get smart enough
   * to optimize-out our data-independence stuff above.)
   *
   * To unpack:
   *
   * If any_difference == 0:
   *            any_difference - 1 == ~0
   *     (any_difference - 1) >> 8 == 0x00ffffff
   *     1 & ((any_difference - 1) >> 8) == 1
   *
   * If any_difference != 0:
   *            0 < any_difference < 256, so
   *            0 < any_difference - 1 < 255
   *            (any_difference - 1) >> 8 == 0
   *            1 & ((any_difference - 1) >> 8) == 0
   */

  return 1 & ((any_difference - 1) >> 8);
}