Opened 5 years ago

Closed 4 years ago

#4469 defect closed fixed (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
(diff, github, buildbot, log)
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.
"""

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 < 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 5 years ago by exarkun

  • Component changed from core to conch
  • Owner changed from glyph to z3p
  • Priority changed from normal to high

comment:2 Changed 4 years ago by exarkun

  • Branch set to branches/conch-without-getrandomnumber-4469

trac must be broken, or it would have noticed the branch on its own, created in r29379.

comment:3 Changed 4 years ago by exarkun

  • Keywords review added
  • Owner z3p deleted

Straw man proposal in the branch. Please tell me why it's wrong to do it this way.

build results.

comment:4 Changed 4 years ago by itamar

  • Keywords review removed
  • Owner set to exarkun
  1. test_usesSuppliedRandomFunction was a wee bit too clever for me on first reading, but you can leave as is.
  1. docstring for _generateX has copy/paste issue - it mentions self.x.
  1. Do you want to fix test_filetransfer.py's use of /dev/urandom (expanding this ticket slightly to "conch uses bad random generators", or do you feel that'd be out of scope for this ticket?

Other than that, looks good.

comment:5 Changed 4 years ago by exarkun

  1. test_usesSuppliedRandomFunction was a wee bit too clever for me on first reading, but you can leave as is.

He he. Sorry about that. I did add a comment to try to help, at least.

  1. docstring for _generateX has copy/paste issue - it mentions self.x.

Fixed.

  1. Do you want to fix test_filetransfer.py's use of /dev/urandom

Urgh. I thought it might be okay at first, but then I realized I don't know why it's even using random bytes there. I want to think about the code a little bit before changing it, so maybe I won't try changing it for this ticket.

comment:6 Changed 4 years ago by zooko

I also reviewed the branch and it looks correct to me.

comment:7 Changed 4 years ago by exarkun

Thank you zooko!

comment:8 Changed 4 years ago by exarkun

  • Resolution set to fixed
  • Status changed from new to closed

(In [29690]) Merge conch-without-getrandomnumber-4469

Author: exarkun
Reviewer: itamar, zooko
Fixes: #4469

Replace Conch's use of Crypto.Util.getRandomNumber with a
custom getRandomNumber function which behaves more appropriately
for the use. PyCrypto's version generated numbers in a reduced
range. Additionally, ensure that the generated private key x
does not fall outside the range allowed by X9.42.

comment:9 Changed 4 years ago by exarkun

  • Resolution fixed deleted
  • Status changed from closed to reopened

(In [29691]) Revert r29690 - test suite regression

This revision introduced test failures on the without-modules configuration:

===============================================================================
[ERROR]: twisted.conch.test.test_transport.RandomNumberTestCase.test_excludesLarge

Traceback (most recent call last):
  File "/var/lib/buildbot/twisted/py2.5-without-modules/Twisted/twisted/conch/test/test_transport.py", line 1961, in test_excludesLarge
    transport._generateX(random, 8),
exceptions.AttributeError: class transport has no attribute "_generateX"
===============================================================================

etc

Reopens #4469

comment:10 Changed 4 years ago by exarkun

(In [29692]) Skip if a dependency is missing

refs #4469

comment:11 Changed 4 years ago by exarkun

  • Resolution set to fixed
  • Status changed from reopened to closed

(In [29693]) Merge conch-without-getrandomnumber-4469

Author: exarkun
Reviewer: itamar, zooko
Fixes: #4469

Replace Conch's use of Crypto.Util.getRandomNumber with a
custom getRandomNumber function which behaves more appropriately
for the use. PyCrypto's version generated numbers in a reduced
range. Additionally, ensure that the generated private key x
does not fall outside the range allowed by X9.42.

(Unre-reviewed) re-merge fixes tests so they skip if a Conch
dependency is missing.

comment:12 Changed 4 years ago by <automation>

  • Owner exarkun deleted
Note: See TracTickets for help on using tickets.