id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,branch,branch_author
4469,conch uses PyCrypto getRandomNumber(),zooko,,"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.
""""""
http://gitweb.pycrypto.org/?p=crypto/pycrypto-2.x.git;a=blob;f=lib/Crypto/Util/number.py;h=4bff7f0fc1cb51deb625ff3202d1c82a81e0af65;hb=HEAD#l61
In addition, {{{getRandomNumber(numbits)}}} doesn't return a random number >= 0 and < 2^numbits^, as you might expect, but instead it always sets the high bit, so it returns a random number >= 2^numbits-1^ and < 2^numbits^. 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 ([source:trunk/twisted/conch/ssh/transport.py@28979#L738 here], [source:trunk/twisted/conch/ssh/transport.py@28979#L806 here], [source:trunk/twisted/conch/ssh/transport.py@28979#L915 here], and [source:trunk/twisted/conch/ssh/transport.py@28979#L961 here]), conch is therefore accidentally generating keys slightly weaker than intended. [http://tools.ietf.org/html/rfc2631 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)
}}}",defect,closed,high,,conch,fixed,security,zooko zooko@…,branches/conch-without-getrandomnumber-4469,