Ticket #4469 defect closed fixed
conch uses PyCrypto getRandomNumber()
| Reported by: | zooko | Owned by: | |
|---|---|---|---|
| Priority: | high | Milestone: | |
| Component: | conch | Keywords: | security |
| Cc: | zooko, zooko@… | Branch: | branches/conch-without-getrandomnumber-4469 |
| Author: | Launchpad Bug: |
Description
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 (2**N)-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)