Request for comments: Developing guide for very high-security bitcoin storage

[jhogan]

Secure cold storage of bitcoins is difficult, and near-impossible for an amateur.  We are solving this problem and would like community feedback on our approach.

We attempted to follow the consensus advice for creating secure bitcoin storage - setting up multi-sig paper wallets using air-gapped computers. To our surprise, this common advice was difficult to follow. There were a confusing variety of tools to choose from at each step, most of which weren’t built around this use case.

We were also surprised to discover there were no good tutorials for navigating this process, despite Bitcoin being several years old.  This should not be a gap in the Bitcoin ecosystem in 2016!

We are solving this problem by creating an open source, step-by-step guide that removes all confusion from the process of creating secure cold storage.

As a first step, we’ve written a design document detailing the technical decisions we have made so far. This is not the step-by-step guide, but a summary that we have put together for more efficient critique. Please give us your most severe criticism.

The link is below. Please leave comments here or in the document itself.
https://docs.google.com/document/d/1sYK1aFubfQqj5B_5r0K4piNfYtQrSYqOU70A78DA1xs/edit#

[1714932133]

1714932133

[1714932133]

1714932133

[1714932133]

1714932133

[1714932133]

1714932133

[1714932133]

1714932133

[bitsec731]

- Read the document, it's good for average users, but it is not the ultimate security. What if the USB stick has hidden malware on it? Can you trust the USB manufacturer? Certainly not.

- I agree on the Hardware wallets. The USB port is a joke. Atleast they should be able to have an option to send data over a QR code through an old 2$ webcam, instead of must plug into a PC. You can then dispose of the webcam after using it, if you are paranoid.


I am more interested in the dice approach. Can't you technically overcome the dice bias by having more throws (add more entropy)?

Instead of generating a 160 bit number, what if you generate an 600 bit number, wouldn't that overcome the bias? I am interested if cryptographic experts would have an answer to that. Thank you.

[ArcCsch]

- I agree on the Hardware wallets. The USB port is a joke. Atleast they should be able to have an option to send data over a QR code through an old 2$ webcam, instead of must plug into a PC. You can then dispose of the webcam after using it, if you are paranoid.

Hardware wallets are supposed to not send any private keys through the USB, and only sign things when the accept button is physically pressed, the hardware is designed to create an "air gap" between the chip and the plug. The private keys never leave the wallet.

I am more interested in the dice approach. Can't you technically overcome the dice bias by having more throws (add more entropy)?

https://commons.wikimedia.org/wiki/File:Binary_entropy_plot.svg
This links to a graph of entropy generated by coin flips as a function of the probabilities of the outcomes (bias), note that since the maximum in the graph is smooth, the loss in entropy generated by a slightly biased coin depends quadratically on the bias (a coin with bias ~0.001 should have entropy loss ~0.000001).
I assume a similar relationship holds for dice, but the 5-dimentional bias space is quite hard to visualize, 36 dice rolls (~93 bits) are just about enough for secure BIP38 encryption (use at least 50 for algorithms without key stretching).

[bitsec731]

Hardware wallets are supposed to not send any private keys through the USB, and only sign things when the accept button is physically pressed, the hardware is designed to create an "air gap" between the chip and the plug. The private keys never leave the wallet.

That may or may not be true. I don't think anyone securely inspected their chips for bugs or backdoors.

But that is not what I was referring too, I was referring to power analysis attack. Since the wallet is powered through the USB port, it would be trivial to mount such an attack and decode the private keys by averaging it over many use cases, and then send out the private key through some covert channel. And since you are forced to be connected to the internet while using them, I would not call an internet connected PC secure.

https://en.wikipedia.org/wiki/Power_analysis

This links to a graph of entropy generated by coin flips as a function of the probabilities of the outcomes (bias), note that since the maximum in the graph is smooth, the loss in entropy generated by a slightly biased coin depends quadratically on the bias (a coin with bias ~0.001 should have entropy loss ~0.000001).
I assume a similar relationship holds for dice, but the 5-dimentional bias space is quite hard to visualize, 36 dice rolls (~93 bits) are just about enough for secure BIP38 encryption (use at least 50 for algorithms without key stretching).

Interesting, so are you saying that even a bad dice can generate random numbers, it's just that it loses entropy value.

How can you estimate the entropy of a dice? Assuming that it's not optimal. (2.5849625007)

[achow101]

I have left several comments on the document.

That may or may not be true. I don't think anyone securely inspected their chips for bugs or backdoors.

Even if the chips allowed something to leak through USB, there still needs to be firmware that controls the chip so that it does do that. IIRC the firmware to most hardware wallets is open source and publicly available (it is for Trezor at least).

But that is not what I was referring too, I was referring to power analysis attack. Since the wallet is powered through the USB port, it would be trivial to mount such an attack and decode the private keys by averaging it over many use cases, and then send out the private key through some covert channel. And since you are forced to be connected to the internet while using them, I would not call an internet connected PC secure.

https://en.wikipedia.org/wiki/Power_analysis

Power analysis attacks have been done before on Trezors: https://jochen-hoenicke.de/trezor-power-analysis/. However these can be relatively easily fixed with firmware changes.

[AGD]

I will read it later, but thumbs up for OPs first post/topic already. Well done.

[ArcCsch]

I was referring to power analysis attack.

The easiest way to eliminate power analysis is by using a capacitor and a resistor inside the wallet:

(1) Connect capacitor to USB to charge.
(2) Disconnect capacitor from USB.
(3) Connect capacitor to chip for some amount of computation.
(4) Disconnect capacitor from chip before it can possibly run out.
(5) Connect capacitor to resistor to drain all excess energy.
(6) Disconnect capacitor from resistor and loop back to step (1).

This prevents the computer from monitoring power use.

[TierNolan]

Instead of generating a 160 bit number, what if you generate an 600 bit number, wouldn't that overcome the bias? I am interested if cryptographic experts would have an answer to that.

You wouldn't need 600 bits, unless the die is very biased.

The entropy is equal to -sum(p(n) * log2(p(n)). 

Basically, the sum of the log of the probability of each state weighted by the probability of each state.

A fair coin would have 2 states with p = 0.5.

That gives

sum(0.5 * log2(0.5)) = -[0.5 * (-1) + 0.5 * (-1)] = 1 bit

An unfair coin with 60% chance of heads gives

[0.4 * log2(0.4) + 0.6 * log2(0.6)] = -[0.4 * (-1.32) + 0.6 * (-0.737)] = 0.971 bits

This means that a 60% coin gives you 97% of the entropy of a fair coin.

A fair dice gives you 2.584962501 bits worth of entropy. 

A dice with a 20% chance of a 1 and a 16% chance for the others gives.

[0.2 * log2(0.2) + 5 * 0.16 * log2(0.16)] = 2.57947 bits

That is pretty large loading and still barely effects the entropy.

A die with a 50% chance of a 6 and 10% of the others gives

[0.5 * log2(0.5) + 5 * 0.1 * log2(0.1)] = 2.16 bits

If you rolled one dice for every 2 bits you want, then you would have to be using very low quality dice not to get the entropy you require.

If the result of 80 dice rolls was run though a hash function, the output would have at least 160 bits of entropy and likely close to 206 bits.

[bitsec731]

Even if the chips allowed something to leak through USB, there still needs to be firmware that controls the chip so that it does do that. IIRC the firmware to most hardware wallets is open source and publicly available (it is for Trezor at least).

Is it all open source though? That is the big question, because usually there are always bits and blobs that control certain aspects of a chip that are closed source by design, and often they can't be reprogrammed at all, not by the vendor, but by the patents and other design secrets of the chip designer.

There are no open source processors currently for PC, that are feasible to use for general use, for example.

Instead of generating a 160 bit number, what if you generate an 600 bit number, wouldn't that overcome the bias? I am interested if cryptographic experts would have an answer to that.

You wouldn't need 600 bits, unless the die is very biased.

The entropy is equal to -sum(p(n) * log2(p(n)). 

Basically, the sum of the log of the probability of each state weighted by the probability of each state.

A fair coin would have 2 states with p = 0.5.

That gives

sum(0.5 * log2(0.5)) = -[0.5 * (-1) + 0.5 * (-1)] = 1 bit

An unfair coin with 60% chance of heads gives

[0.4 * log2(0.4) + 0.6 * log2(0.6)] = -[0.4 * (-1.32) + 0.6 * (-0.737)] = 0.971 bits

This means that a 60% coin gives you 97% of the entropy of a fair coin.

A fair dice gives you 2.584962501 bits worth of entropy. 

A dice with a 20% chance of a 1 and a 16% chance for the others gives.

[0.2 * log2(0.2) + 5 * 0.16 * log2(0.16)] = 2.57947 bits

That is pretty large loading and still barely effects the entropy.

A die with a 50% chance of a 6 and 10% of the others gives

[0.5 * log2(0.5) + 5 * 0.1 * log2(0.1)] = 2.16 bits

If you rolled one dice for every 2 bits you want, then you would have to be using very low quality dice not to get the entropy you require.

If the result of 80 dice rolls was run though a hash function, the output would have at least 160 bits of entropy and likely close to 206 bits.

Thank you. My crypto skills are not that good, that is not my area of expertise.

Can you reference this formula that you have used?

[achow101]

Is it all open source though? That is the big question, because usually there are always bits and blobs that control certain aspects of a chip that are closed source by design, and often they can't be reprogrammed at all, not by the vendor, but by the patents and other design secrets of the chip designer.

Take a look at the code yourself: https://github.com/trezor/trezor-mcu

You can compile from source and flash it to your device, so everything that is there is what is part of the Trezor firmware.

[jhogan]

- Read the document, it's good for average users, but it is not the ultimate security. What if the USB stick has hidden malware on it? Can you trust the USB manufacturer? Certainly not.

Thanks for your comments.  Can you propose a more secure alternative?  I'm curious if you have something in mind.  Keep in mind the computer in question needs to get the key generation software on it somehow, and we certainly don't want to accomplish that by connecting it to a network.

I have left several comments on the document.

I saw that, thank you!  It will take us some time to review all comments, but look forward to doing so.

Even if the chips allowed something to leak through USB, there still needs to be firmware that controls the chip so that it does do that. IIRC the firmware to most hardware wallets is open source and publicly available (it is for Trezor at least).

Having everything open source definitely helps, but open source can have important vulnerabilities too (e.g. Heartbleed).  And side channel attacks, like the power analysis attack you linked.  Perhaps that can be fixed, but what other undiscovered vulnerabilities might be out there?  That USB connection just creates an incremental risk any way you look at it. 

[gmaxwell]

You should evaluate if your software decisions are consistent with best practices for selecting cryptographic software (see a talk I gave on the subject (third section) at https://youtu.be/Gs9lJTRZCDc?t=2240); or if you're taking potentially dangerous code that you found on the internet because its superficial feature set sounded good.

[buwaytress]

I was referring to power analysis attack.

The easiest way to eliminate power analysis is by using a capacitor and a resistor inside the wallet:

(1) Connect capacitor to USB to charge.
(2) Disconnect capacitor from USB.
(3) Connect capacitor to chip for some amount of computation.
(4) Disconnect capacitor from chip before it can possibly run out.
(5) Connect capacitor to resistor to drain all excess energy.
(6) Disconnect capacitor from resistor and loop back to step (1).

This prevents the computer from monitoring power use.

Good starting point to foil power analysis attacks but couldn't it be designed in such a way that it is built-in or automated, part of security trigger?

I think we must remember that this guide is designed for newbies - any recommendation must put this consideration at foremost thought.

[ArcCsch]

snip

Good starting point to foil power analysis attacks but couldn't it be designed in such a way that it is built-in or automated, part of security trigger?

I think we must remember that this guide is designed for newbies - any recommendation must put this consideration at foremost thought.

Oh, this was targeted at developers of hardware wallets to give the hardware itself security against power analysis.
Other security possibilities are to enclose the chip in a thick case of a highly conductive metal to stop electromagnetic waves, add an ultrasonic noise source, much more powerful than the legitimate chip to foil acoustic cryptanalysis, and add a small TRNG to continually seed the PRNG.
Also, does the Trezor show the transaction in full before it is signed?
It most certainly should.
Also, it should be hard to confirm by accident (pin should be entered.)

[TierNolan]

Can you reference this formula that you have used?

It's a pretty standard formula.  You can get it from the information theory entropy article on wikipedia.

[bitsec731]

Is it all open source though? That is the big question, because usually there are always bits and blobs that control certain aspects of a chip that are closed source by design, and often they can't be reprogrammed at all, not by the vendor, but by the patents and other design secrets of the chip designer.

Take a look at the code yourself: https://github.com/trezor/trezor-mcu

You can compile from source and flash it to your device, so everything that is there is what is part of the Trezor firmware.

But the ARM processor is not open sourced.

TREZOR is using a 120 MHz embedded ARM processor (Cortex M3 to be precise) with a custom developed system.

Most of this stuff is patented. If the processor is not open, it doesnt matter that the rest of the code is.

https://en.wikipedia.org/wiki/ARM_architecture

Thanks for your comments.  Can you propose a more secure alternative?  I'm curious if you have something in mind.  Keep in mind the computer in question needs to get the key generation software on it somehow, and we certainly don't want to accomplish that by connecting it to a network.

I could but I think it would be an overkill. Certainly as you have said for holdings of 100,000-500,000$ I would say that this guide is ok. If a person has more than that, he might go for a full manual key creation because certainly no digital machine can be trusted 100%. And there are other attack vectors too.

I would rate the guide 7/10, it's still orders of magnitude better than what the average bitcoin user has, and a thief would always start with the low hanging fruits.

Having everything open source definitely helps, but open source can have important vulnerabilities too (e.g. Heartbleed).  And side channel attacks, like the power analysis attack you linked.  Perhaps that can be fixed, but what other undiscovered vulnerabilities might be out there?  That USB connection just creates an incremental risk any way you look at it. 

When it comes to side-channel attacks, there are hundreds of possible attack vectors, and it's nearly impossible to defend against all. People should start with the most vulnerable ones, and defend against those first.

People should also build their own threat models, and see what kind of defense they need or don't. Not everyone has a lot of coins, and for smaller holdings, some of this stuff could be an overkill.

[Cubic Earth]

The guide seems reasonable, and nice to see some work being put into this.

Here is my method for secure cold storage:

1) Start with clean, offline computer, with wireless capability disabled

2) Load a few different wallets and pieces of address generating software onto the computer

3) I used Bitaddress.org as my key generator. Crappy java-script RNG? No problem. Did I check the sigs? Nope. I let it generate a key pair, and use that as the starting point.

4) I modify the private key by hand! I make about 7 changes, including deletions, additions, and substitutions. I also add a short word to make visual confirmation easy. I just make sure the key ends up being the same length as it started out.

5) I import the modified private key into several other wallets, and confirm that every generated address is the same.

6) I archive private keys as appropriate, via encrypted thumb drives and paper backups which I cut (with scissors) into fragments and distributed.

7) The addresses I isolate and make available to online machines.


The nice part about this method is, between modifying the private keys by hand, and cross referencing address generation among different pieces of software, the opportunity for malicious software to compromise funds is severely limited.

[AGD]

I think, the endpoint of security for Bitcoin is still the computer hardware part. It is no problem to use dice to create a secure entropy and paper as a storing medium (which burns pretty good and can be confiscated - which is something that a cold storage shouldn't have), but Bitcoin is still relying on closed source computers. Sure, regular people could build a open source power supply from scratch, but creating a open source processer is pratically impossible, so everyone who stores Bitcoins, will have to trust a few big electronic part manufacturers, that they are not storing your freshly created offline keys anywhere. So the Bitcoin system is not 100% trustless at all.

Check https://en.wikipedia.org/wiki/List_of_open-source_hardware_projects

Even using open source hardware doesn't protect you from chip manufacturers etc, so we still have to trust alot.
Also as long as the internet is something, that a few people can simply shut down, we have to trust a lot, that they don't.
You might still have your Bitcoins in your wallet then, but you will not be able to send them to another wallet - not even your own one.

[vapourminer]

The guide seems reasonable, and nice to see some work being put into this.

Here is my method for secure cold storage:

4) I modify the private key by hand! I make about 7 changes, including deletions, additions, and substitutions. I also add a short word to make visual confirmation easy. I just make sure the key ends up being the same length as it started out.

i especially like the part i bolded. word could be a hint as to what that key/addy is for, contains, whatever.

more work but more potential usefulness.

[shorena]

The guide seems reasonable, and nice to see some work being put into this.

Here is my method for secure cold storage:

4) I modify the private key by hand! I make about 7 changes, including deletions, additions, and substitutions. I also add a short word to make visual confirmation easy. I just make sure the key ends up being the same length as it started out.

i especially like the part i bolded. word could be a hint as to what that key/addy is for, contains, whatever.

more work but more potential usefulness.

Also a potential side channel, its probably not much, but a key with a word in it is easier to guess than a key thats entirely random. If you dont trust the crappy java prng, just use the one the OS provides.