Our one use of tor_weak_random() is subtly wrong

In relay.c , we try to use tor_weak_random() to generate a 1/N random event using the pattern:

   if ((tor_weak_random() % N) == 0)

But that's subtly wrong. Many popular libcs' versions of random() use a linear congruential generator with a modulus that's a power of two, for which the low-order bits tend to have a much shorter period than the high-order bits. So we'd probably be better off with something more like:

  if (tor_weak_random() < TOR_RAND_MAX / N)

modulo rounding issues. Perhaps a tor_rand_int(long maxval) would be smarter still.

This isn't too big a problem, since if we're ever in a place where we can't tolerate not-too-random values, we shouldn't be using tor_weak_random(). Still, it's worth fixing.

changed milestone to %Tor: 0.2.4.x-final

added component::core tor/tor milestone::Tor: 0.2.4.x-final priority::low resolution::fixed status::closed tor-relay type::defect labels

Replying to nickm:

But that's subtly wrong. Many popular libcs' versions of random() use a linear congruential generator with a modulus that's a power of two, for which the low-order bits tend to have a much shorter period than the high-order bits.

It's actually total wrong, and not because random() implementations.

    int num_streams = 0;
    for (conn = first_conn; conn; conn = conn->next_stream) {
      num_streams++;
      if ((tor_weak_random() % num_streams)==0)
        chosen_stream = conn;

Every first checking of condition happens with num_streams = 1; Any (random) number % 1 == 0 As result chosen_stream = first_conn. always.

While you exams circuit_resume_edge_reading_helper, FYI:

for (conn=chosen_stream; conn; conn = conn->next_stream) {
  if (conn->_base.marked_for_close || conn->package_window <= 0)

will segfault if func called with first_conn == NULL. It likely remotely exploitable.

wrong code part quote. correct one:

  for (conn = first_conn; conn != chosen_stream; conn = conn->next_stream) {
    if (conn->_base.marked_for_close || conn->package_window <= 0)
      continue;

ok, no segfault happens actually. some flips during code reading occurred.

Yup. Note that the code isn't

    int num_streams = 0;
    for (conn = first_conn; conn; conn = conn->next_stream) {
      num_streams++;
      if ((tor_weak_random() % num_streams)==0) {
        chosen_stream = conn; break;
      }
    }  

Instead, it was:

    int num_streams = 0;
    for (conn = first_conn; conn; conn = conn->next_stream) {
      num_streams++;
      if ((tor_weak_random() % num_streams)==0)
        chosen_stream = conn;
      // no break here.
    }

So the first time through the loop, chosen_stream is always first_conn, but the second time through the loop, it becomes the second connection with P=1/2, and so on. I've tried to make this even more explicit in the comment.

And wrt the segfault, it can't happen because if first_conn is NULL, chosen_stream will be NULL. So in the first loop (The one after "FY:I") the loop condition will be false immediately, since conn will be set to NULL. And in the second loop (the one after "correct one:"), conn=first_conn will set conn to NULL, and conn!=chosen_stream will compare conn with NULL, so again the loop body is never executed.

Branch "bug7801" is my public repository. Please review.

Trac:
Status: new to needs_review

#if INT_MAX > TOR_RAND_MAX
#error tor_weak_random_range requires INT_MAX <= TOR_RAND_MAX
#endif

http://msdn.microsoft.com/en-us/library/2dfe3bzd.aspx

The constant RAND_MAX is the maximum value that can be returned by the rand function. RAND_MAX is defined as the value 0x7fff.

Wow, what a completely useless rand().

To be constructive: looks like it's time to drop in a LCG.

Trac:
Status: needs_review to needs_revision

Okay, just dropped in an LCG implementation for _WIN32.

Trac:
Status: needs_revision to needs_review

To be clear, it's not only windows limits RAND_MAX to so slow values. No guarantees to find RAND_MAX >= INT_MAX for all another platforms too. Only one guarantee that RAND_MAX is no less than 0x7fff.

Agreed, but I can't find any other platform we support that has that that limitation. If there is, they'll see an #error, and we can write LCG code for them too.

Hm. looks like it'll break on irix. Not sure if I care about irix.

Is there a valid reason to put this much effort into keeping a bad RNG in Tor instead of #define tor_weak_random() crypto_rand_int(INT_MAX + 1)?

#define tor_weak_random() crypto_rand_int(INT_MAX) would be faster, because crypto_rand_int does an abysmal job of handling values of max of the form ((1<<n) - 1).

#2210 (moved)

We used random() because we didn't want to drain cryptographic entropy for this, since it's not necessary.

Replying to cypherpunks:

#2210 (moved)

We used random() because we didn't want to drain cryptographic entropy for this, since it's not necessary.

I asked for a valid reason. You can't ‘drain entropy’ from OpenSSL's RNG.