conch uses PyCrypto getRandomNumber()
|Reported by:||zooko||Owned by:|
(diff, github, buildbot, log)
conch uses PyCrypto's getRandomNumber() function. That function is documented in the latest versions of PyCrypto as being for internal use only:
This function is for internal use only and may be renamed or removed in the future.
In addition, getRandomNumber(numbits) doesn't return a random number >= 0 and < 2numbits, as you might expect, but instead it always sets the high bit, so it returns a random number >= 2numbits-1 and < 2numbits. This is not documented in older releases of PyCrypto but is documented in the current git head:
NOTE: Confusingly, this function does NOT return N random bits; It returns a random N-bit number, i.e. a random number between 2(N-1) and (2N)-1.
Since conch uses getRandomNumber() to generate Diffie-Hellman secret keys (here, here, here, and here), conch is therefore accidentally generating keys slightly weaker than intended. RFC 2631 says of Diffie-Hellman secret keys:
X9.42 requires that the private key x be in the interval [2, (q - 2)]. x should be randomly generated in this interval.
I don't know why it excludes q-2 as a valid value. conch currently has a non-zero but negligible chance of accidentally choosing q-2 as its secret key. Here is some untested code that probably generates the right sort of values without using PyCrypto:
import binascii def log_ceil(n, b): """ The smallest integer k such that b^k >= n. log_ceil(n, 2) is the number of bits needed to store any of n values, e.g. the number of bits needed to store any of 128 possible values is 7. """ p = 1 k = 0 while p < n: p *= b k += 1 return k def next_multiple(n, k): """ The smallest multiple of k which is >= n. Note that if n is 0 then the answer is 0. """ return div_ceil(n, k) * k def bytes_to_long(bytes): return int(binascii.hexlify(candidatebytes), 16) def secrandrange(rng, lowerbound, upperbound): interval = upperbound-lowerbound sizbits = log_ceil(interval, 2) sizbytes = next_multiple(sizbits, 8) while True: candidate = bytes_to_long(rng(sizbytes)) if candidate < interval: return candidate + lowerbound x = secrandrange(os.urandom, 2, q-1)
Change History (12)
comment:1 Changed 4 years ago by exarkun
- Component changed from core to conch
- Owner changed from glyph to z3p
- Priority changed from normal to high
comment:9 Changed 4 years ago by exarkun
- Resolution fixed deleted
- Status changed from closed to reopened
comment:11 Changed 4 years ago by exarkun
- Resolution set to fixed
- Status changed from reopened to closed