Ticket #4469 defect closed fixed

Opened 4 years ago

Last modified 4 years ago

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 (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)

Change History

1

Changed 4 years ago by exarkun

  • owner changed from glyph to z3p
  • priority changed from normal to high
  • component changed from core to conch

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.

3

Changed 4 years ago by exarkun

  • owner z3p deleted
  • keywords security, review added; security removed

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

 build results.

4

Changed 4 years ago by itamar

  • keywords security added; security, 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.

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

3. 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.

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.

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

Fixed.

3. 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.

6

Changed 4 years ago by zooko

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

7

Changed 4 years ago by exarkun

Thank you zooko!

8

Changed 4 years ago by exarkun

  • status changed from new to closed
  • resolution set to fixed

(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.

9

Changed 4 years ago by exarkun

  • status changed from closed to reopened
  • resolution fixed deleted

(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

10

Changed 4 years ago by exarkun

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

refs #4469

11

Changed 4 years ago by exarkun

  • status changed from reopened to closed
  • resolution set to fixed

(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.

12

Changed 3 years ago by <automation>

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