Opened 7 years ago
Closed 6 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
branch-diff, diff-cov, branch-cov, buildbot |
Author: |
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 < 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 (2N)-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. 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 7 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 6 years ago by exarkun
- Branch set to branches/conch-without-getrandomnumber-4469
comment:3 Changed 6 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.
comment:4 Changed 6 years ago by itamar
- Keywords review removed
- Owner set to exarkun
- test_usesSuppliedRandomFunction was a wee bit too clever for me on first reading, but you can leave as is.
- docstring for _generateX has copy/paste issue - it mentions self.x.
- 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 6 years ago by exarkun
- 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.
- docstring for _generateX has copy/paste issue - it mentions self.x.
Fixed.
- 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 6 years ago by zooko
I also reviewed the branch and it looks correct to me.
comment:7 Changed 6 years ago by exarkun
Thank you zooko!
comment:8 Changed 6 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 6 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 6 years ago by exarkun
comment:11 Changed 6 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 6 years ago by <automation>
- Owner exarkun deleted
trac must be broken, or it would have noticed the branch on its own, created in r29379.