Changes between Initial Version and Version 23 of Ticket #1924

Timestamp:

2013-07-17T16:41:53Z (11 years ago)

Author:

zooko

Comment:

Just an update: this ticket is not getting much love from me because ​pycryptopp #85 makes it stop happening when pycryptopp compiles libcryptopp. However, ​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