id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,branch,branch_author,launchpad_bug
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,,