make_nonce is not random enough

[kylemacfarlane]

When doing bulk operations it is quite easy for requests to go out with the same timestamp. If I leave a bulk operation going at up to 60 requests a minute (often they all go out in the first 10s) then it will almost certainly use a duplicate timestamp/nonce pair within about 20 minutes.

I'd say that make_nonce needs to also take into account the current time in microseconds and maybe even the pid.

Using sleep() is my current method but I don't think it should be needed.

[mmalone]

Hrm. It's a birthday attack, so if I'm remembering my statistics correctly the point where we'd expect a collision is at a sample of size 1.25*sqrt(n) where n is the number of possible results from the random function. Since we're generating a base 10 number between 0 and 100,000,000 that would mean we'd expect a collision after 12,500 calls. I ran some tests and found that this is roughly accurate - after 1000 iterations I found that I got a collision after generating an average of 12,818 nonces. Of course this is statistics, so sometimes collisions happen earlier, sometimes later (my min was 383, max was 36,843). 12,500 requests per second from one token is a lot, but it's certainly not impossible... so I agree, we should fix this (or at least document it somewhere).

My suggestion is that we use a larger base, rather than a longer number. A 10 digit base-32 number would give us an expected collision after 41,900,000 or so nonces (keep in mind this is per second, per client), 9 digit would be around 7,000,000. I'd probably go with 10 digit base-32 or something close to that.

I threw my test code up on a gist if you have any other ideas: http://gist.github.com/378010

[oconnore]

OAuth 1.0 does not require the nonce to be an integer. Just use this (strips the ='s off the end so it doesn't need to be urlencoded)

def gen_nonce(length):
   """ Generates a random string of bytes, base64 encoded """
   if length < 1:
      return ''
   string=base64.b64encode(os.urandom(length),altchars=b'-_')
   b64len=4*floor(length,3)
   if length%3 == 1:
      b64len+=2
   elif length%3 == 2:
      b64len+=3
   return string[0:b64len].decode()

gen_nonce(32) gives you 256 random bits from the OS CRNG

[setharnold]

This has been assigned CVE-2013-4347. See http://www.openwall.com/lists/oss-security/2013/09/12/7

[joestump]

Switched this to use random.SystemRandom(). This should be fixed.

[jaitaiwan]

@joestump which commit?

[joestump]

That was also in 82dd2cd.