Armory's Random Number Generator (Is Armory Broken?)

[vernell]

I am looking at Armory's code to see how the wallet secret key is generated. This is what I saw so far:

PyBtcWallet -> SecureBinaryData -> (Crypto++) AutoSeededX917RNG -> ... bunch of code ... -> /dev/urandom

Now, I don't want to go into the discussion about /dev/random vs. /dev/urandom. The problem is that for bitcoin holding purposes, I actually don't trust /dev/random nor /dev/urandom. It might happen that their implementation in my kernel is silently broken (see Android's case). Or that my machine happens to be low on entropy just as I am about to create a wallet. Since Armory is all about deterministic wallets created with a single master key, it is super-important that this key is generated properly. Randomness in Armory is mission critical. Bad randomness could sweep cold storage coins behind my back.

I am proposing that Armory will use it's own random number generator. Preferably something similar to TrueCrypt's RNG (http://www.truecrypt.org/docs/random-number-generator#Y266). /dev/(u)random, time measurements and mouse movements will be continuously mixed into an entropy pool. Random numbers can then extracted from the pool. When creating a new wallet, Armory will mix mouse movements into the pool for at least 10 seconds before generating the master key. Even bitaddress does this.

I actually really like all the features in Armory - cold storage/offline transactions, deterministic wallets, N-out-of-M backups, etc. But it really saddens me to see its most critical security feature broken like this. I would love to use Armory for storing my coins. But the not-good-enough RNG makes me eery.

[Abdussamad]

AFAIK the android bug was because /dev/urandom or /dev/random was NOT being used.

[etotheipi]

Crypto++ pulls entropy from /dev/random or /dev/urandom, but that is not it's only source of entropy.  Their docs are pretty explicit that it uses multiple sources.  Plus, /dev/random actually is extremely reliable, but it's also a very scarce resource: it can't generate a lot of random numbers.

Look at the section on AutoSeededX917RNG:
http://www.codeproject.com/Articles/16982/Applied-Crypto-Pseudo-Random-Number-Generators

Specifically this table from that article:



For more information look up

FIPS PUB 171 Key Management Using ANSI X9.17

[vernell]

Crypto++ pulls entropy from /dev/random or /dev/urandom, but that is not it's only source of entropy.  Their docs are pretty explicit that it uses multiple sources.  Plus, /dev/random actually is extremely reliable, but it's also a very scarce resource: it can't generate a lot of random numbers.

Look at the section on AutoSeededX917RNG:
http://www.codeproject.com/Articles/16982/Applied-Crypto-Pseudo-Random-Number-Generators

Specifically this table from that article:
http://www.codeproject.com/KB/cpp/PRNG/image06.png


For more information look up

FIPS PUB 171 Key Management Using ANSI X9.17

I read the crypto++ code and read the docs. From what I saw, AutoSeededX917RNG is seeded from /dev/random or /dev/urandom and then it uses a block cipher (AES) to generate subsequent numbers. There is no other entropy source. Also the docs don't mention other entropy sources. Please point me to the place in the code if I am wrong.

Moreover, it looks like AutoSeededX917RNG is only seeded once, and Armory maintains only a single instance of it. That means that if I am creating multiple wallets in Armory without closing and restarting, all the wallets will be created from the same underlying 256 bits of entropy that were generated on startup. This looks like a problem to me, because I would expect that if I am creating 3 wallets Armory would use 768 bits of entropy and not only 256. Again please correct me if I am wrong.

Regarding /dev/random. I know how it is implemented in linux. I too *think* it is secure. But I am not sure. In principle it is possible that the entropy estimator might miss and overestimate. Or a bug could creep into the debiasing and whiting algorithms in future kernel versions. Such bugs have been known to lay dormant for years. The implications for Armory could be catastrophic. Not saying it is likely, just saying its possible. And I would not recommend the use of Armory on platforms where the quality of /dev/random is more questionable.

Also, note that Armory is meant to be used in offline systems. Such systems obviously have less entropy derived from packet timing. So all else being equal I would expect /dev/random to be slightly weaker when used on an offline computer. That means Armory needs to be even more careful when creating a cold wallet.

In the bottom line, I think Armory should follow TrueCrypt and bitaddress and use /dev/random but only in addition to other entropy sources. It can never hurt. Sure, I would rely on /dev/random to generate a session key for shopping on ebay. But relying solely on it to generate a long term deterministic bitcoin wallet makes my stomach ache.

[etotheipi]

I read the crypto++ code and read the docs. From what I saw, AutoSeededX917RNG is seeded from /dev/random or /dev/urandom and then it uses a block cipher (AES) to generate subsequent numbers. There is no other entropy source. Also the docs don't mention other entropy sources. Please point me to the place in the code if I am wrong.

Moreover, it looks like AutoSeededX917RNG is only seeded once, and Armory maintains only a single instance of it. That means that if I am creating multiple wallets in Armory without closing and restarting, all the wallets will be created from the same underlying 256 bits of entropy that were generated on startup. This looks like a problem to me, because I would expect that if I am creating 3 wallets Armory would use 768 bits of entropy and not only 256. Again please correct me if I am wrong.

Regarding /dev/random. I know how it is implemented in linux. I too *think* it is secure. But I am not sure. In principle it is possible that the entropy estimator might miss and overestimate. Or a bug could creep into the debiasing and whiting algorithms in future kernel versions. Such bugs have been known to lay dormant for years. The implications for Armory could be catastrophic. Not saying it is likely, just saying its possible. And I would not recommend the use of Armory on platforms where the quality of /dev/random is more questionable.

Also, note that Armory is meant to be used in offline systems. Such systems obviously have less entropy derived from packet timing. So all else being equal I would expect /dev/random to be slightly weaker when used on an offline computer. That means Armory needs to be even more careful when creating a cold wallet.

In the bottom line, I think Armory should follow TrueCrypt and bitaddress and use /dev/random but only in addition to other entropy sources. It can never hurt. Sure, I would rely on /dev/random to generate a session key for shopping on ebay. But relying solely on it to generate a long term deterministic bitcoin wallet makes my stomach ache.

Perhaps I misread their comments about it.  Perhaps the different sources I was thinking about were the list of things it does differently on each OS.

Bear in mind that creating the wallet seed only requires 32 bytes of real randomness.  Even an offline computer will have no problem with 32-bytes, and that's far in excess of the really-actually 16 bytes that is considered secure.  This isn't RSA where you have to do a search through a large number of random might-be-primes. 

I agree it wouldn't hurt to add extra entropy sources, but I think it's quite a stretch to call it insecure.  This is FIPS standard for generating random numbers for cryptographic purposes (but, I know you're talking about the seeding instead of the algorithm).  When we make an Android app, we absolutely will be supplementing the entropy sources since we have a plethora of entropy sources such as audio and video.  For now, I've been recommending that if people are paranoid, they can actually use dice or a deck of cards to do their own entropy.

[vernell]

I am not saying Armory isn't secure. I am saying the security of Armory == the security of the underlying /dev/random. Which is not terribly bad, but not terribly good either if you are paranoid as me.

Here is a possible attack on Armory. I sell you a laptop. I think you might install Armory on it. I subvert /dev/random to generate bad random numbers (an extreme way would be to point /dev/random to /dev/zero, but I would probably do something way less obvious). You get the laptop and install Armory (you even verify the signature after downloading!). You fund your wallet. I search through the much smaller key space and steal your funds. The laptop could have been offline the whole time. And it did not matter that Armory needed only 32 bytes. (Of course, if you reinstall the OS my attack would not work. I am counting that you won't).

FIPS assumes that you have a secure entropy source. What FIPS really does is specify algorithms that could stretch an original short random seed into a long stream of pseudo-randomness. But if the entropy source is not secure the assumption is invalidated and FIPS will be broken.

Is there a way to use my own entropy (cards, cubes) with Armory? I didn't see this feature.

[etotheipi]

SUBJECT:   Re: Armory's Random Number Generator (Is Armory Broken?)

...

I am not saying Armory isn't secure. I am saying the security of Armory == the security of the underlying /dev/random. Which is not terribly bad, but not terribly good either if you are paranoid as me.

You're suggesting Armory might be "broken" in your subject.  I'd appreciate if you'd change the top post subject if you don't actually believe that.  

Also, in your example of "If I sell you a laptop"... if you sell me a laptop for secure computing and I don't wipe the OS before I use it, there's always something you can do to compromise it.  Even if I fix the RNG thing as you recommend, there's plenty of other ways you can compromise a system if you have full root access to it for an unlimited amount of time.

Finally, I don't have a GUI method for inputting entropy directly into Armory.  It's not laziness, I'm avoiding users entering "99999999999999" for their entropy because they want a brainwallet and think no one would ever guess that.  So I have simply provided (in other posts) the way this can be done from the Linux shell very quickly, to make it clear it can be done but you accept the risks if you don't do it "right".

Example using a shuffled deck of cards:

Code:

>>> from armoryengine import *      # With version 0.90 and lower
>>> from armoryengine.ALL import *  # With version 0.91+
>>> entropy = hash256('Ad3s4s9c7hKhKd...')
>>> print makeSixteenBytesEasy(entropy[:16])
fntf euji uofg kkhf  ewfe keft uawj garh  twsu
>>> print makeSixteenBytesEasy(entropy[16:])
sdwe nift ijso dhgg  ghjf sigo tunw uteu  hafo

In Armory, go to "Restore Wallet" and restore a single-sheet backup.  Enter that:

fntf euji uofg kkhf  ewfe keft uawj garh  twsu
sdwe nift ijso dhgg  ghjf sigo tunw uteu  hafo

You can do everything as you did it before.  Including making a paper backup, which will just show those two lines.  Which of course should be backed up.

[DobZombie]

What if you encode a timestamp, then use that as another point of entropy?

[picobit]

I think OP has a valid point - I would be much more worried about an unknown bug in /dev/random being discovered, and allowing people to later brute-force Armory wallets en masse than I would be about malicious printers or USB-stick firmware virusses or some of the other in my opinion pretty unlikely attack vectors that are being addressed by Armory.  The attacker would not even need access to your machine!  What if I created an offline wallet on a Raspberry Pi and Raspbian is later discovered to have a flawed /dev/random?  Suddenly, all my funds will be gone.

I understand why you do not want to add an alternative source of entropy in the GUI, people will use it to generate bad Armory brain wallets.  But what about a source of supplementary entropy?  I can type in "correct horse battery staple" and it is SHA-256'ed and combined with /dev/random.  Even if my extra passphrase is lousy (as in my example), I am saved by /dev/random.  And if /dev/random is partially compromized, even a mediocre passphrase entropy-phrase may save the day, and a good long one certainly will.

Only risk: The user confuses this with the encryption passphrase - but maybe you can just use the encryption passphrase as the extra source of entropy for the seed generation, in addition to /dev/random.

[etotheipi]

Here's my thoughts:  if Crypto++ has a way to inject supplemental entropy, I'm all for doing that.  As picobit pointed out, it can't do any harm, it can only do good.  If that's the case, there's no reason I can't add various user-generated values to the entropy pool (such as the number of microseconds between mouse clicks, uninitialized RAM states, hashes of various system files like /var/log/Xorg.0.log,  etc).  A few of these together are probably even sufficient entropy alone.

My main concern was messing with crypto libraries, that have already been thoroughly reviewed and tested.  In my mind, digging into any of these things is very risky, and I'm not exactly qualified to do it. I risk unbalancing a solid RNG implementation.   But if there are channels built-in to insert extra entropy, I will act on your suggestion.

[etotheipi]

Goatpig figured out where you can inject additional entropy into the RNG in Crypto++.  I went to go inject entropy path from the GUI to the C++ PRNG and I stumbled on this:

https://github.com/etotheipi/BitcoinArmory/blob/master/armoryengine.py#L7636

Code:

          # TODO: We should find a source for injecting extra entropy
         #       At least, Crypto++ grabs from a few different sources, itself
         plainRootKey = SecureBinaryData().GenerateRandom(32)

That comment was probably written two years ago.  I guess I had thought about it before, but never took the time until now to look into it.  There is actually a AutoSeededX917RNG::IncorporateEntropy function that does exactly this.  There's a few other things that held up the 0.91-beta release, so there's room to get it into that release.

[picobit]

 There's a few other things that held up the 0.91-beta release, so there's room to get it into that release.

Interesting!  Once you have integrated that into a reasonable safe release I think I will make a new offline wallet (with the new Armory on the offline computer) and transfer everything - just to be safe against future attacks against undiscovered bugs in /dev/random.  Yes, I know it is paranoid...

[etotheipi]

https://github.com/etotheipi/BitcoinArmory/blob/0.91-dev/ArmoryQt.py#L796

Code:

       # The entropyAccum var has all the timestamps, down to the microsecond,
      # of every keypress and mouseclick made during the wallet creation
      # wizard.   Also logs mouse positions on every press, though it will
      # be constant while typing.  Either way, even if they change no text
      # and use a 5-char password, we will still pickup about 25 events. 
      # Then we throw in the [name,time,size] triplets of some volatile 
      # system directories, and the hash of a file in that directory that
      # is expected to have timestamps and system-dependent parameters.

That's in 0.91-dev and just merged into the testing branch.

[picobit]

Cool!  I think I will wait a bit before upgrading the offline machine and the offline wallet - after all, you have often been saying that it should be pretty safe to use a bleeding-edge online Armory as long as the offline one is a well-tested version, as that would catch any coin-losing bugs.

But great to see you have added this!

[jl2012]

If I simply don't trust any computer-generated random number, is it possible for me to use my own random number (e.g. by trowing dice) as deterministic wallet seed?

[etotheipi]

If I simply don't trust any computer-generated random number, is it possible for me to use my own random number (e.g. by trowing dice) as deterministic wallet seed?

See post #7 in this thread.

[jl2012]

If I simply don't trust any computer-generated random number, is it possible for me to use my own random number (e.g. by trowing dice) as deterministic wallet seed?

See post #7 in this thread.

Thanks, so this is a new function. I remember that I have asked the same question 2 year ago.

[etotheipi]

If I simply don't trust any computer-generated random number, is it possible for me to use my own random number (e.g. by trowing dice) as deterministic wallet seed?

See post #7 in this thread.

Thanks, so this is a new function. I remember that I have asked the same question 2 year ago.

Kind of.  The code is technically the same, I just pulled out the chunk that converts a seed into paper backup into a reusable function.  It's not much easier to access via command-line.  We actually used the technique with a deck of cards recently to generate some new wallets, and it turned out to be pretty darned easy if you were in linux.  You only needed to install the offline package into a live session, and then open a shell in the /usr/lib/armory directory.