[tahoe-lafs-trac-stream] [tahoe-lafs] #1924: NetBSD < 6.0 /dev/random appears to break RSA keygen in test suites

[tahoe-lafs]

#1924: NetBSD < 6.0 /dev/random appears to break RSA keygen in test suites
-------------------------------+------------------------------------
     Reporter:  midnightmagic  |      Owner:
         Type:  defect         |     Status:  new
     Priority:  major          |  Milestone:  undecided
    Component:  code           |    Version:  1.9.2
   Resolution:                 |   Keywords:  netbsd random cryptopp
Launchpad Bug:                 |
-------------------------------+------------------------------------

Old description:

> It *looks* as though the NetBSD /dev/random from earlier than 6.0 (prior
> to Thor's patch which overhauled it to supply unlimited amounts of random
> data) does not supply enough bytes to get Tahoe LAFS through the test
> phase *at all times*.
>
> If you turn off all sources of mixed entropy via NetBSD rndctl, and
> exhaust it continuously (cat /dev/random > /dev/null) it is possible to
> reproduce the issue semi-regularly.
>
> It manifests as failed RSA invertibility tests in the test suite.
>
> Running crypto++ test binary under the same conditions makes crypto++
> complain bitterly about how long it has to wait for random bytes to be
> supplied from /dev/random, but it does not technically fail: just
> complain about it.
>
> I believe it is this issue which is not being handled correctly.
>
> I have no direct evidence this is so.
>
> Updating to NetBSD >= Thor's /dev/random overhaul appears to correct the
> issue.

New description:

 It *looks* as though the NetBSD /dev/random from earlier than 6.0 (prior
 to Thor's patch which overhauled it to supply unlimited amounts of random
 data) does not supply enough bytes to get Tahoe LAFS through the test
 phase *at all times*.

 If you turn off all sources of mixed entropy via NetBSD rndctl, and
 exhaust it continuously (cat /dev/random > /dev/null) it is possible to
 reproduce the issue semi-regularly.

 It manifests as failed RSA invertibility tests in the test suite.

 Running crypto++ test binary under the same conditions makes crypto++
 complain bitterly about how long it has to wait for random bytes to be
 supplied from /dev/random, but it does not technically fail: just complain
 about it.

 I believe it is this issue which is not being handled correctly.

 I have no direct evidence this is so.

 Updating to NetBSD >= Thor's /dev/random overhaul appears to correct the
 issue.

--

Comment (by zooko):

 Just an update: this ticket is not getting much love from me because
 [https://tahoe-lafs.org/trac/pycryptopp/ticket/85 pycryptopp #85] makes it
 stop happening when pycryptopp compiles libcryptopp. However, [https
 ://tahoe-lafs.org/trac/pycryptopp/ticket/85 pycryptopp #85] presumably has
 no effect when the libcryptopp was compiled by something else and
 pycryptopp is just linking to it, so this bug could still affect a user in
 that case.

 Also, of course, this could actually be a bug in Crypto++, a bug in
 pycryptopp, a bug in gcc, a bug in a backdoor in the compiler that was
 used to compile the compiler that was used to compile gcc, etc. Until we
 know what this ''is'', we can never be sure of what it isn't.

 Okay, here comes a summary of what I know about this bug. The main theme
 is that it is probably a bug in NetBSD v5, but we're not 100% sure of
 that.

 The effect of the bug is that Crypto++'s internal consistency check on RSA
 multiplication fails, like this:

 {{{
 terminate called after throwing an instance of 'CryptoPP::Exception'
   what():  InvertibleRSAFunction: computational error during private key
 operation
 }}}

 Here's an example of that happening on midnightmagic's buildslave running
 NetBSD v5: https://tahoe-lafs.org/buildbot-
 pycryptopp/builders/MM%20netbsd5%20i386%20warp/builds/150/steps/bench/logs/stdio

 This is reproducible on midnightmagic's machine, but only when the
 "entropy pool" that feeds /dev/random is depleted. Now this part is insane
 and means we have entered and alternate dimension in which time and space
 are not as we know them. Because, pycryptopp never reads from /dev/random!
 It only reads from /dev/urandom. Nevertheless, midnightmagic confirms that
 when the entropy pool is full, this bug never (or almost never?)
 manifests, and when the entropy pool is depleted, this bug is very
 reproducible.

 midnightmagic: please confirm for the Nth time that I haven't
 misremembered the above.

 If the above is true, then it strongly suggests a bug in the kernel which,
 in the case that the entropy pool is depleted when you read from
 /dev/urandom, corrupts some memory or something. One thing that would be
 strange about that is why only this particular RSA internal consistency
 check ever suffers ill effects from this proposed corruption.

 Another explanation besides the "alternate dimension" explanation is that
 Russian blackhats are using midnightmagic's NetBSD 5 buildslave as a
 training ground for new recruits.

 It would be interesting to see if anyone else can reproduce this bug on
 ''their'' NetBSD 5 system.

 Okay, here's the next thing that I know about this bug: that I added more
 internal consistency checks to the code, and triggered midnightmagic's
 buildslave to run it, and what I found was that my new internal
 consistency checks passed (and they ran ''after'' the read from
 /dev/urandom), but then a few instructions later Crypto++'s original
 internal consistency check failed. Here, look at the code to see what I
 mean:

 Original version from Crypto++:

 http://sourceforge.net/p/cryptopp/code/433/tree/trunk/c5/rsa.cpp#l223

 Version with my added internal consistency checks:

 https://github.com/zooko/pycryptopp/blob/a7f5955a576734396a54f5c10497c84018022691
 /src-cryptopp/rsa.cpp#L224

 Okay, that's the summary.

 Suggested next-steps:

 Someone please try to reproduce this on a NetBSD v5 machine that is
 unlikely to be controlled by the same Russian blackhat trainees as
 midnightmagic's machine. The steps to reproduce are:

 {{{
 git clone https://github.com/tahoe-lafs/pycryptopp.git
 cd pycryptopp
 python setup.py build
 while [ 1 ] ; do
   python setup.py bench
 done
 }}}

-- 
Ticket URL: <https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1924#comment:23>
tahoe-lafs <https://tahoe-lafs.org>
secure decentralized storage