Topic: Simple entropy questions (Read 2143 times)

From what I can tell, it also seems a bit like overkill (as I was saying above).  Nevertheless this discussion has been really interesting and helpful.  Thanks goatpig for the links and the writeups.  Good luck with your storage wallet pf!

The wording makes me feel a bit uncomfortable.

Let's make things clear. Armory is FOSS, the common sense implications are that you are using the software at your own risk and that you can't hold us devs accountable for snafus. You also didn't pay me for my consult on this matter so you can't hold me directly responsible if stuff goes stupid.

TLDR, I'm laying out my opinion, you figure out the rest for yourself.

That said, I think Armory gathers enough entropy to create root keys as is, and that the method you propose will not reduce entropy, and in fact increase it. I think the extra entropy is overkill in this particular case, and past 256 bits entropy, quality trumps quantity. But that's only my opinion and you should definitely go with what makes you comfortable.

Do with that what you may.

Okay, so this is my current plan:

• Perform the "6 screen divisions with 100 throws of a 6-sided die" method I described earlier.
• This will add 256 bits of entropy to Armory's existing 256 bits of entropy, providing me with at least 512 bits of entropy in the data that is fed into the HMAC256. So the end result will be at least 255 bits of entropy.

The reason I'm insisting on using the die like this is because I'm simply too scared to create entropy with the die only, not to mention modifying the Armory code. I could easily screw something up. But if I just use Armory as-is, at least I know I'm not screwing anything up since I'm just using the die alongside the official Armory. So I'm basically just adding the extra confidence of the physical die entropy into the confidence I already have for Armory.

Am I good to go? Do I have your blessings?

You could probably write a few thesis on entropy. Discussing it with the terms we are using is merely scrapping the surface of the underlying math. Simply put, the more entropy you feed a proper hash function, the more entropy your result will benefit of. However, due to the limitation of your final secret (here, 256bits), you should be more concerned about the quality of your entropy rather than quantity.


From the link:


I don't know where he gets the 0.6, I don't remember seeing that anywhere in FIPS 180-3, but then again I read that a long time ago so I can't tell whether the value is realistic or not, but for the sake of the argument, let's assume it is.

0.6 * 2^s is about 0.5 * 2^s.

0.5*2^s = (2^s)/2 = 2^(s-1).

So with with n = 256 and s >= 256, you will have at least 2^255 unique values from the hash-n of a value in the [0, 2^s] range.

Hmm. I looked into the code some more. It looks like I can just keep on appending entropy data. It could easily become gigabytes of entropy data. I guess the only limit is really the RAM on the machine. Then Armory takes the whole damn thing and takes a HMAC256 of it (using the hardcoded key "Armory Entropy").

So the question remains: In what way is information lost when going from potentially gigabytes of entropy data (if I throw the die gazillion times) down to the mere 256-bits of the HMAC256 hash?

For example, is there any mathematical/cryptographic theorem out there that says something like: "If you throw data that has more entropy than 256 bits into HMAC256, you will always get at least 256-bits of entropy. No less."

UPDATE:

The answer https://crypto.stackexchange.com/a/10405, if correct, sort of confirms that everything is good. If I throw petabytes of data with gigabits of entropy into HMAC256, I will end up with at least 255 bits of entropy. I'm not sure exactly where that "minus one" in (256 - 1 = 255) comes from though. Can an Armory developer confirm the validity of that answer on crypto.stackexchange?

Interesting.

So that I can understand better what's going on, are you able to tell me:

If we do "self.entropyAccum.append" of an integer (for example a cursor location) that has 16 bits of entropy and then later repeat the process again for another cursor location, do we now have an entropy of 32 bits?

In other words, did the first recording of the cursor location fill in this entropy bit sequence:

a1 a2 ... a16 (where each a can be either 0 or 1)

and the second recording of the cursor location fill in additional 16 bits:

a1 a2 ... a16 a17 a18 ... a32 ?

If my understanding in correct, is there a threshold at which it "wraps over"? For instance, after we have filled in 256 bits, will the next "self.entropyAccum.append" start over from bit zero, or will it continue past 256 bits? Is there any such a limit at all?

For example, in my above "screen dividing" example, is there a point at which I would actually stop making a difference in the entropy at some point (say, after throwing the die a million times)?

The mouse data in this particular code is a pair of integers (x, y) that define the position of the mouse relative to top left corner of the dialog the position is retrieved from. For a dialog of size (X, Y), the top left corner is (0, 0), the bottom right corner is (X, Y).

In this particular case, the dialog is created with a default size so it depends on the desktop resolution and the default system font size, which influences the size of the elements within that dialog (and thus how large Qt is going to create it). Assuming a desktop resolution of 800*600, I believe the dialog could get as small as 300 pixels wide and 150 high. This gives us x E [0, 150] and y E [0, 300], so an average of 16 bits for the pair in some pretty bad conditions.


Timestamps are in the plain old UNIX format, i.e. the amount of time that has passed since Jan 1st 1970. I believe the timestamp is in milliseconds in this case (I would have to double check). The more significant bits of the timestamp won't change at all during this operation, so only the bottom few really matter for consecutive throws. If you take [3-8] seconds per throw and key press that's about 12 bits of entropy per, but assuming I messed up and the timestamps are in seconds, then you are closer to 6~8 bits on the span of 100 throws.

I appreciate that some folks with some details knowledge of the maths have shown up to help educate us .   Entropy is information, information is represented in bits, I get this much.  The mapping from real world events into the amount of information they contain in bits isn't always as clear to me.  I wonder if you can show us how youfrom came up with the figures you gave: 16 bits from the mouse position, 8 from a timestamp.

Thanks!

Which is why the deck of cards is preferable.


There's about 16 bits of entropy in each mouse pos considering the average size of the dialog and that the position is relative to the dialog's top left corner and cannot exceed the bottom right corner. With the added timestamp, I'd say you get another 8 bits so that's ~24 bits per keystroke.

You're also forgetting about things like how a die may not have even weighting on all sides, thereby biasing every throw you make. So, to "guarantee" X amount of entropy for die throws isn't quite as simple as it looks at first glance.

Thanks for your input. It will help me lock down my final wallet creation method. (Most likely I'll end up trusting Armory.)

But I'm wondering, do you have the answer to the following question, for educational purposes? (Whether or not I apply its solution in practice is a different matter.)

Let's say I divide my screen real estate into 6 areas like so:

 -------------
 | 1 | 2 | 3 |
 -------------
 | 4 | 5 | 6 |
 -------------
 
And then, after entering the "Wallet creation wizard", I repeat these steps 100 times:

• Throw a 6-sided die.
• Place the mouse cursor into the corresponding screen area. For example, if 3 came up on the die, I move the mouse cursor into area 3 as shown in the diagram above.
• I enter some character into the "Wallet description" text field to make Armory record the mouse cursor location into the entropy.

The question is simply: Will this guarantee a 256-bit additional entropy from the die or not? And if not, how many extra die throws would be required?

I guess this is sort of a maths question. I don't know how to calculate it, because I don't know precisely how the cursor points map into raw entropy bytes, etc.

You are complicating things for no apparent reason. If you don't trust the software RNG, use a hardware one or dice/cards. Mixing them defeats the premise. You either trust the RNG or you don't. If you believe the software RNG is unsafe, why mix it with a safe source? Just use the safe source.

Nevertheless, you are also using the weirdest way possible to mix the entropy sources. Add a command line argument in armoryengine.py, something like --extranentropy. Pass in your external entropy as a hex string, load that into a SecureBinaryData object so that it is mlock'd then feed that through the extra entropy channel at wallet creation.

If that's too complicated, start some offline live instance of Linux, copy over Armory and the necessary packages (into the live ramdisk). Make sure no storage device (internal or external) are plugged for the good measure. Hardcode your extra entropy straight into the .py. Start Armory, create your wallet, write down the backup string, test it a couple times and shut down the machine. Voila.

Lastly, as picobit stated, it's easy to shoot yourself in the foot manipulating entropy on your own. Make sure you follow the dice roll/card deck instructions properly, and that you know what you are doing with the code. It's pretty easy to pass in an empty string for your entropy source.

I am not sure exactly how Armory collects entropy from the environment, but my guess is that it uses /dev/random for that purpose.  This means that you will NOT find lines in the source code tracking mouse movements, keyboard timings etc.  All those events are monitored by the operating system, and used to generate entropy that can then be accessed through /dev/random.  Possibly, Armory mixes that entropy with further random data it collects through other channels.

If you do not want to rely on system provided entropy, but want to generate it manually, then you can find threads in this forum on how to generate entropy by using dice (you need around 100 die rolls to generate 256 bits of entropy) or shuffling a deck of cards.  You can then manually generate an Armory paper backup from that data, and "restore" it in Armory.  You need to know what you are doing if you experiment with this, since getting it wrong may mean losing all your bitcoins.

Armory is already tracking the time too on every key press. I'm not sure about the millisecond accuracy and I'm not sure it modulos it with a prime though.

But I thought the whole point of the die was to get entropy from an outside non-digital source that couldn't have been tampered with. I have to agree it's for the extra paranoid. But since it's a one-time wallet that I hope to last me a few decades, maybe it's worth it.

An interesting investigation that you're carrying out.  I can't help feeling like you're going to extreme ends to get the dice involved.  Couldn't you just as easily and with equal or greater entropy take the unix time in milliseconds modulo some prime number alongside the mouse position coordinate everytime a user presses the keyboard?

Here's a thought experiment, what if you tell you user to roll a six sided die but then you just ignore the 1-6 he inputs and instead use the moment when he gives you input as the entropy source?  Wouldn't that equivalent or better to the information from the 6 sided die?

Okay, I think I figured something out in this area. To get a sense of what's going on, I added this statement at the bottom of the try block in the logEntropy function in ArmoryQt.py:


Running Armory ("python ArmoryQt.py") with this added and doing some basic experiments while looking at the Terminal in the background, I came to the following important conclusions:

• Do not rely on moving the mouse to gain entropy. Armory does not track mouse moves for adding entropy. It looks like etotheipi may have been wrong in this regard (unless Armory used to track mouse moves back then but no longer does).
• It does track mouse presses and releases, but only within certain areas of the "Wallet Creation Wizard" window. So I would not rely on this functionality because you may get unlucky and hit areas which do not respond to mouse press/release events.
• Keyboard presses within the text fields are reliable. So, if you type a character into the "Wallet description" text field say, that key press will be added to the entropy. But importantly, so will the mouse cursor location on the screen when you pressed that key.

---------------------------
End-users can ignore the above and just read the below instructions:
---------------------------

Accordingly, here are my new idiot-proof instructions on how to create an Armory wallet with next to bulletproof entropy:

• First, of course, click "Create Wallet" to enter the "Wallet Creation Wizard".
• Second, click into the "Wallet description" text field to give it focus.
• Step 1: Place your mouse cursor at a seemingly random location on your screen.
• Step 2: Roll a 6-sided die.
• Step 3: Press the outcome of the die roll into your keyboard in the "Wallet description" text field. For example, if the die showed the number 5, just type 5 into the "Wallet description" text field.
• Repeat steps 1-3 hundred times.
• Get rid of the stuff you typed into "Wallet description".
• Continue creating your wallet as usual.

Warning: I have only tested my instructions on Ubuntu 14.04 LTS.

What do you think? Do Armory developers and others approve of my solution? Is it sound?

Update: Oh no. I just noticed that it doesn't actually add the character keycode of the pressed key into the entropy. This renders the "die roll to keyboard" strategy useless. Armory developers: How would I go about adding the key press to the entropy as well?

Update 2: Hmm wait. This could actually still work, if I just divide my screen real estate into 6 parts and move my mouse into one of those 6 parts and press a key after every die roll. That could provide me with the entropy I want from the die. What do you think?

I think I understand your inquiry better now.  I'm not an armory dev (or even a user) so I can't say what command you might be able to use to see what armory is storing when you're typing numbers and letters and whatnot.  However, on the question is in principle about whether you can add entropy by rolling dice and then inputting the numbers, I'm pretty convinced that's just as good (or possibly better) than just slamming your fingers on the keyboard or scrolling your mouse around or whatever your normal armory instructions say to do.

In case it help satisfy your curiosity, I do know a command to print the entropy collected in /dev/random:


It basically looks like you're terminal emulator's worst nightmare as it tries to figure out how it might print the data that's being passed in.  Whatever encoding your terminal uses, it will try to decode the data and print it, but most of the time whatever data is being dropped in isn't printable, it looked like this in my terminal:


So that's what entropy "looks like". 

Let me put it this way:

What logging statement can I add to which line in which Python/C++ file to see on the Terminal (from which I typed "python ArmoryQt.py" to launch Armory) when Armory collects my keyboard/mouse input?

Better be safe than sorry. Also it's fun, and adds more to my understanding

So my questions still stand really, especially about adding entropy by throwing a die 100 times and typing the number (1,2,3,4,5, or 6) the keyboard (or tracing/drawing the numbers on the die with the mouse) while the "Wallet Creation Wizard" (step 1 or 2) is in the foreground. It would be nice if an Armory developer could confirm whether or not this would work.

I'm not sure why you're looking to add more entropy, is there some reason you have to suspect that what Armory's providing isn't enough?

With respect to entropy on linux there's also /dev/random that you can consult (https://en.wikipedia.org/wiki//dev/random).  If you want to roll dice that's certainly a way to generate true randomness, but it's also the slow way.

I guess I"m curious about your motivations here, if you're just trying to learn about randomness, or if you have some specific goal in mind with respect to Armory?

On the thread

https://bitcointalk.org/index.php?topic=673035.20

Armory developer etotheipi said this:


So is Armory really tracking and storing my mouse moves and keyboard presses while the "Wallet Creation Wizard" window is open? Does this mean I should prefer moving my mouse a lot and typing a lot on the keyboard for a few minutes when this window is open (in either Step 1 or Step 2 in the wizard)? Also, does this have to be done with Armory in the foreground? I'm on Ubuntu 14.04. (I'm guessing the OS won't send Armory those mouse and keyboard events unless it's in the foreground.)

That same thread also explains how to generate a new Armory wallet exclusively using 100 rolls of a 6-sided die. But my question is, how can I use die rolls to add entropy to the existing default Armory wallet generation? As opposed to relying exclusively on the die. The die could be biased after all. Update: Since Armory is tracking keyboard events in that wallet creation wizard window, would this method work?: 1) roll the die. 2) type the number on the die that comes up on my keyboard. 3) repeat 100 times. Once that is done, proceed with creating the wallet. What do you think?