Bitcoin Forum
March 29, 2024, 09:30:03 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 [2] 3 4 »  All
  Print  
Author Topic: Hardware Bitcoin wallet - a minimal Bitcoin wallet for embedded devices  (Read 44603 times)
someone42 (OP)
Member
**
Offline Offline

Activity: 78
Merit: 10

Chris Chua


View Profile
May 03, 2012, 04:17:55 PM
 #21

Isn't this overkill? I mean, writing an encrypted copy of the seed on a USB key doesn't sound dangerous. And it's much easier and less error prone for the user than manually copying it from what's displayed.
Writing to a USB key would require the wallet be capable of being a USB host, as opposed to merely being a USB device. Being a USB host requires far more processing resources than being a USB device. IMO, it just isn't worth the extra complexity and cost. An easier alternative to manually writing down the seed would be to take pictures of the display.
I guess that it would increase complexity, but do you think it's feasible to implement "hidden volumes" like Truecrypt does, in order to have plausible deniability against this kind of attack (works as long as the attacker doesn't know for sure how much you've got)?
Hidden wallets are a feature I plan to add. I intentionally made the "format storage" command write random data everywhere (instead of all 00s) for this reason.



I had a couple of comments on your protocol:
+ You do not specify the character encodings you are using. For the bitcoin addresses and public keys ASCII will be fine but for the wallet names I would use UTF8 to make it internationalisable (depends if you can display it I guess)
Good point. Currently, the wallet doesn't ever display or parse the wallet name (the wallet name is just there for the convenience of the host), so adding this feature requires no additional code.
+ You have some powerful commands (format, change encryption key) that an attacker can use with no constraints on their use. For instance, a point of sale device that you only want to send sign requests can format your device. Or they can change the encryption password and hold your BTC to ransom.  Perhaps you need a 'hardware protect' physical switch to stop this - maybe you have this already.
Just like with transaction signing, all powerful commands require approval from the user. I haven't done this with the "change encryption key" command yet because I'm still figuring out how to deal with ransom attacks.

One major problem I've identified with the hardware Bitcoin wallet is that since its input user interface consists solely of two pushbuttons, there's no way to get a wallet password into it. Currently, the host is supposed to provide an encryption key derived from a password, and this is bad because:
1. The user must type the password using the host's keyboard and the host may have a keylogger.
2. The host may have an advanced trojan which covertly mixes a "ransom key" into the encryption key, lets you load BTC into a wallet, then holds those BTC for ransom.

How can these flaws be dealt with? Here are the ideas I've come up with:
  • Keep things the way they are. Rely on the assumption that even if an attacker has your wallet password, they probably won't have physical access to your hardware Bitcoin wallet, so they still can't do anything nasty. Rely on wallet backups to mitigate ransom attacks.
  • Change the protocol so that the wallet password is sent in cleartext over the serial port. Then, the wallet has the opportunity (when setting or changing the wallet password) to display the password, allowing the user to detect if a "ransom key" has been inserted.
  • Add a USB port to the hardware Bitcoin wallet and allow the user to plug a USB keyboard into the wallet and directly enter the wallet password.
I like the last option the most, but it does involve additional cost (+0.20 to 0.40 USD for quantity = 1000) and complexity*. Also, since the key derivation function is evaluated on the hardware Bitcoin wallet, it can't be as strong, since the microcontroller on the device will be orders of magnitude less powerful than a modern CPU or GPU.

Can anyone think of a better way to deal with ransom attacks?



I am hardware-phobic but very impressed. Do you wantto makethis device tamper proof? Like erase memory when you detect that someone is trying to open the case?
It would be nice to have tamper proof features and there are microcontrollers out there which have such features. But the semiconductor manufacturers all seem to require the signing of an NDA (that goes against my goal of openness) and probably won't bother talking to me unless I commit to an order of at least 10,000 units. I figure it's not such a big deal: Bitcoins are transferrable. If your wallet is compromised or stolen, you create a new one and use a wallet backup to transfer everything to the new wallet.



That would require the device to recognize the signature. A standard like what's done for HTTPS could be created, with the device trusting a priori a set of CA root certificates, and people signing their URI's with a signed cert. But this set of root certs would need to evolve once in a while. The only way to "safely" update such set of trusted CA is by signing the update with a manufacturer's private key, which the device always trust. That only works as long as the manufacturer doesn't lose control to this key.

Difficult to implement, with some level of danger still, but yeah, a possibility, and certainly much better than nothing.
I don't know whether merchants would like to adhere to this protocol though. It would probably make their life easier if the same certificate they use for HTTPS could be used for this, at least they don't have to pay two different CA's.
It may be possible to verify signed Bitcoin addresses on a hardware Bitcoin wallet, as long as the signatures are generated using ECDSA (and preferably using the curve secp256k1). Most of the code needed to verify a signature is already implemented, because signature verification is similar to signature generation. Also, ECDSA public keys are only 64 bytes each, so there will probably be enough spare space to fit a couple in a firmware binary. Nevertheless, I don't think I'll implement this feature in the near future.

*There's a bit of a cheat I can use here. As I mentioned above, being a USB host is difficult. But most (maybe all?) USB keyboards are also PS/2 keyboards: those USB-to-PS/2 dongles they come with simply re-route the USB pins to PS/2 pins. The keyboard uses some electrical checks to determine whether it is plugged into an actual USB port or a USB-to-PS/2 dongle. Thus it's possible to trick a USB keyboard into using the PS/2 interface, and the PS/2 interface is much easier to work with than the USB interface.
1711704603
Hero Member
*
Offline Offline

Posts: 1711704603

View Profile Personal Message (Offline)

Ignore
1711704603
Reply with quote  #2

1711704603
Report to moderator
Even if you use Bitcoin through Tor, the way transactions are handled by the network makes anonymity difficult to achieve. Do not expect your transactions to be anonymous unless you really know what you're doing.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1711704603
Hero Member
*
Offline Offline

Posts: 1711704603

View Profile Personal Message (Offline)

Ignore
1711704603
Reply with quote  #2

1711704603
Report to moderator
1711704603
Hero Member
*
Offline Offline

Posts: 1711704603

View Profile Personal Message (Offline)

Ignore
1711704603
Reply with quote  #2

1711704603
Report to moderator
1711704603
Hero Member
*
Offline Offline

Posts: 1711704603

View Profile Personal Message (Offline)

Ignore
1711704603
Reply with quote  #2

1711704603
Report to moderator
marcus_of_augustus
Legendary
*
Offline Offline

Activity: 3920
Merit: 2347


Eadem mutata resurgo


View Profile
May 03, 2012, 09:53:26 PM
 #22

Interesting.

How small are you thinking a final version maybe? As small as a USB stick with 2-line display?

I think for btc savings (large amounts) having just a small, network-isolated, piece of hardware that does nothing else but store keys and sign transactions is a very promising concept.

Xenland
Legendary
*
Offline Offline

Activity: 980
Merit: 1003


I'm not just any shaman, I'm a Sha256man


View Profile
May 04, 2012, 05:49:43 AM
 #23

Interesting.

How small are you thinking a final version maybe? As small as a USB stick with 2-line display?

I think for btc savings (large amounts) having just a small, network-isolated, piece of hardware that does nothing else but store keys and sign transactions is a very promising concept.
Sounds like iron key needs to be Contacted Smiley
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500



View Profile
May 04, 2012, 08:23:44 AM
 #24

How can these flaws be dealt with? Here are the ideas I've come up with:
  • Keep things the way they are. Rely on the assumption that even if an attacker has your wallet password, they probably won't have physical access to your hardware Bitcoin wallet, so they still can't do anything nasty. Rely on wallet backups to mitigate ransom attacks.
  • Change the protocol so that the wallet password is sent in cleartext over the serial port. Then, the wallet has the opportunity (when setting or changing the wallet password) to display the password, allowing the user to detect if a "ransom key" has been inserted.
  • Add a USB port to the hardware Bitcoin wallet and allow the user to plug a USB keyboard into the wallet and directly enter the wallet password.
I like the last option the most, but it does involve additional cost (+0.20 to 0.40 USD for quantity = 1000) and complexity*. Also, since the key derivation function is evaluated on the hardware Bitcoin wallet, it can't be as strong, since the microcontroller on the device will be orders of magnitude less powerful than a modern CPU or GPU.

Can anyone think of a better way to deal with ransom attacks?

*There's a bit of a cheat I can use here. As I mentioned above, being a USB host is difficult. But most (maybe all?) USB keyboards are also PS/2 keyboards: those USB-to-PS/2 dongles they come with simply re-route the USB pins to PS/2 pins. The keyboard uses some electrical checks to determine whether it is plugged into an actual USB port or a USB-to-PS/2 dongle. Thus it's possible to trick a USB keyboard into using the PS/2 interface, and the PS/2 interface is much easier to work with than the USB interface.

Seriously, 0,40USD is nothing. Even if it ads more than 1USD per unit, it's still nothing. Just use USB, it's the current standard, people wouldn't need adapters, you could use the same USB port to connect to the device that will provide the transactions to be signed, and maybe one day you could make it capable of writing the encrypted seed out for backup purposes. Wink

I agree that keeping low cost is important to boost adoption, but don't get too radical on that. Usability is also an important criterion. This device would mostly be used by those which have a sensible amount of BTCs to protect anyway, so I believe they can afford a few dollars more for a decent thing. Those who don't have much coins, don't have much too lose in using desktop wallets anyway.
jim618
Legendary
*
Offline Offline

Activity: 1708
Merit: 1066



View Profile WWW
May 04, 2012, 09:19:34 AM
 #25

@someone42
You should give your device and protocol a name.

That way client software can advertise itself as supporting 'YourName' devices.
Also people can then clone your hardware and advertise their devices as 'YourName' compatible.

MultiBit HD   Lightweight desktop client.                    Bitcoin Solutions Ltd   Bespoke software. Consultancy.
jim618
Legendary
*
Offline Offline

Activity: 1708
Merit: 1066



View Profile WWW
May 04, 2012, 02:39:41 PM
Last edit: May 04, 2012, 05:17:37 PM by jim618
 #26

These combined USB drives with LCD make for an interesting form factor:


No buttons though.

Edit: link http://www.usbflash.co.uk/usb-flash-drives/plastic-usb-drives/flash-drive-lcd.html

One of the things on our 'possible' things to do with MultiBit is to make a MultiBitPortable where the wallet and software are all on a USB device. With a combination hardware wallet + USB drive you could :

+ plug in your USB drive / hardware wallet combo and start up your client software, the executable for which is on the USB drive.
+ when it needs to do a spend, it talks via serial/USB to the hardware device to get you to approve it with a button press on the device and the hardware device signs it.
+ client software then transmits the tx.

Both Electrum and MultiBit can run from small USB drives quite happily.

Just exploring the possibilities.

MultiBit HD   Lightweight desktop client.                    Bitcoin Solutions Ltd   Bespoke software. Consultancy.
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500



View Profile
May 04, 2012, 04:06:03 PM
 #27

It seems you forgot to add a link, jim...
MatthewLM
Legendary
*
Offline Offline

Activity: 1190
Merit: 1004


View Profile
May 04, 2012, 06:24:41 PM
 #28

I'm looking through the code. I guess the ECDSA and bignum algorithms were implemented more or less from scratch? I might use some of you algorithms for the C library I'm making. I was looking at other libraries including OpenSSL which is what the C++ client uses but none easily allow me to include only the specific parts I need into my library.

I found this:

Code:
  * All computation functions have been written in a way so that their
  * execution time is independent of the data they are processing. However,
  * the compiler may use optimisations which destroy this property; inspection
  * of the generated assembly code is the only way to check. The advantage of
  * data-independent timing is that implementations of cryptography based on
  * this code should be more timing attack resistant. The main disadvantage is
  * that the code is relatively inefficient.

Does this matter for the purposes of this device? And what about using bitcoin on a PC?

For a time-based attack an attacker would need to determine the start and end times of an operation. For signing transactions on a PC I don't see how time information could leak out to an attacker. From what I can tell the attacker would need some sort of access to the computer itself, in which case wallets are vulnerable anyway. So would the algorithms need to be secured against this type of attack when using bitcoin?

Perhaps using a random sleep period when signing transactions would protect against the attack and may allow for better optimisation. I found this but it isn't too keen on the random time delays: http://www.cryptography.com/public/pdf/TimingAttacks.pdf The blind signature technique wouldn't be applicable (unless I don't know something). Does anyone have any thoughts on this?
whiskers75
Hero Member
*****
Offline Offline

Activity: 658
Merit: 502


Doesn't use these forums that often.


View Profile
May 04, 2012, 07:45:00 PM
 #29

Nice idea!
To solve the password dilemma,
Why not use the LCD as the password display and
Ask the user to type the password BACKWARDS...

Elastic.pw Elastic - The Decentralized Supercomputer
ELASTIC ANNOUNCEMENT THREAD | ELASTIC SLACK | ELASTIC FORUM
pc
Sr. Member
****
Offline Offline

Activity: 253
Merit: 250


View Profile
May 04, 2012, 08:06:57 PM
 #30

Definitely an interesting concept.

But before using any sort of embedded device to generate keys, I'd want some confidence in its random number generator. (I haven't looked at the hardware or code, and I don't have the expertise to evaluate its randomness even if I did.) But the research using EFF SSL data that indicates a lot of SSL certificates in the wild use bad random number generators, probably generated on embedded devices, makes me really hesitant to use an embedded device to generate my bitcoin keys without a lot of scrutiny.
Peter Todd
Legendary
*
Offline Offline

Activity: 1120
Merit: 1147


View Profile
May 05, 2012, 04:40:37 PM
 #31

For a time-based attack an attacker would need to determine the start and end times of an operation. For signing transactions on a PC I don't see how time information could leak out to an attacker. From what I can tell the attacker would need some sort of access to the computer itself, in which case wallets are vulnerable anyway. So would the algorithms need to be secured against this type of attack when using bitcoin?

Perhaps using a random sleep period when signing transactions would protect against the attack and may allow for better optimisation. I found this but it isn't too keen on the random time delays: http://www.cryptography.com/public/pdf/TimingAttacks.pdf The blind signature technique wouldn't be applicable (unless I don't know something). Does anyone have any thoughts on this?

The problem with random sleep periods is that you can still determine the underlying time taken through simple statistical averaging in many circumstances. Possible a better solution would be to start a timer at the beginning of any cryptographic operation, and then once the operation finishes wait until a fixed maximum-time has elapsed. That way every operation takes the same amount of time. Adding a further random delay on top of this fixed delay wouldn't be a bad idea either, to help mask any residual leakage. (for instance, suppose that the time measurement turns out to be flawed, and there is still a remainder which it does not detect)

If the attacker can also determine what the power consumption of your hardware wallet you have to hide that as well. Unfortunately in the case of a USB-powered wallet this is actually a realistic attack as some motherboards can measure how much power a USB device is actually consuming. To protect against this, the "makeup" time period should do something cpu-intensive as well, perhaps an additional, randomly chosen, cryptographic operation. (don't pick the same operation, with the same keys, in case there turns out to be a key-dependent power consumption)

Finally, at the hardware level you can choose a power supply with a fixed current consumption on the input. A zener diode and resistor voltage regulator, operated correctly, has a nearly zero change in input current for a change in output current and you can do even better with something more sophisticated.

For the OP: I'm an electronics designer and I'd be interested in working further on the hardware design.

MatthewLM
Legendary
*
Offline Offline

Activity: 1190
Merit: 1004


View Profile
May 05, 2012, 04:51:27 PM
 #32

Thanks retep. I was thinking the same thing: Instead of a random delay, you could profile the algorithms to estimate the longest time and add a delay up until this time each time the algorithms are run. An additional random delay would be good also. As for the power problem, wouldn't it be best to focus on the hardware to mask this? With the algorithms there may be detectable power variations for the actual different operations computed right?
EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500



View Profile
May 05, 2012, 06:10:11 PM
 #33

But before using any sort of embedded device to generate keys, I'd want some confidence in its random number generator.

Good point to remember.
As suggested here, the device could have an embedded AM antenna and use the background noise as entropy source.
Peter Todd
Legendary
*
Offline Offline

Activity: 1120
Merit: 1147


View Profile
May 05, 2012, 07:57:36 PM
 #34

Thanks retep. I was thinking the same thing: Instead of a random delay, you could profile the algorithms to estimate the longest time and add a delay up until this time each time the algorithms are run. An additional random delay would be good also. As for the power problem, wouldn't it be best to focus on the hardware to mask this? With the algorithms there may be detectable power variations for the actual different operations computed right?

It depends on who the attacker is. If you assume they have access to your computer, as is the case with a virus, you're job is a lot easier and hardware or software solutions to keep the power draw constant are fine. However, if you are trying to defeat an attacker who has the actual device, then a hardware solution is trivial to attack by just taking the device apart. At that point though, there are a *lot* of possible attacks which this design can't prevent anyway.

I'd argue for fixing the problem in software first, and then once you've done that, determine if a cheap hardware fix is possible too. Having said that, a USB powered device with this fix is pretty easy to make as USB provides +5V and most uC's will run on 3.3V. If one of the easy-to-use FTDI FT-X chips is used for the uC<->USB communication we have no issue as well, as those chips have 3.3V-tolerant IO. The only issue left is the LCD screen, most of them run off of 5V. Still, simple level translation isn't hard and won't add much cost.

BTW, for the non-electrical engineers out there, this is how the zener-regulator works, and why it makes the current constant:



Vs represents the 5V supplied by the computer over USB, and R2 representing your uC. DZ is the zener. In operation, the effective value of R2 changes as the uC draws different amounts of current. At what extreme, R2 might be nearly infinite if the uC is in sleep mode, at the other extreme, the most current the uC can draw will look like an R2 of a few dozen ohms. What we want is for the current being drawn out of Vs to be fixed, regardless of the value of R2.

The zener diode has a property called breakdown where if the voltage applied to it in the reverse direction increases over a certain threshhold, it starts conducting current exponentially. Suppose we pick a 3.3V zener, and R2 is an open circuit. (the uC is off) If the zener is not conducting any current, the voltage across it will rise, and as the voltage reaches 3.3V, it will start conducting current again. This means we can pick the value of R1 assuming a given amount of current flows through it. Lets assume 30mA: R1=(Vs-Vz)/I=(5V-3.3V)/30mA=73Ohms. Now the zener is happily allowing 30mA of current to flow through it, which causes 30mA of current to flow through R1, and there is a voltage drop across R1 of 2.2V, just enough that 3.3V is across the zener.

Now lets suppose the uC starts doing a cryptographic operation. It's now consuming 20mA of current computing a bitcoin transaction. If the zener continues to draw 30mA of current, the total would be 50mA, and the voltage drop across R1 would be (20mA+50mA)*73Ohms=3.65V. However, 5V-3.65V=1.35Volts, way less than the 3.3V breakdown of the zener. Instead what happens is as the uC draws more current, the zener draws less, so the total current between the two stays the same. Now we have the zener drawing 10mA and the uC drawing 20mA.

An external observer, such as a wallet-stealing virus that can ask the computer for how much power the USB port is drawing, now has no idea how much power the uC is drawing no matter what it's doing. The disadvantage of course being that the power consumed is constant, even when the wallet isn't doing anything. Still, 150mW isn't a lot of power.


Of course, the above example is a bit hand-wavey, what actually happens is more subtle. A zener's current-to-voltage relationship is actually an exponential relationship, in the form I=k(V-Vth)^n with k and n being device-specific coefficients. Effectively, the total current drawn is *not* actually constant, it's just that the change in current draw is small.

Lets assume that the computer we're using has the ability to measure the current draw on an individual USB port with a precision (not accuracy!) of 0.1%, and the range of that measurement is one standard USB load, 100mA. 100mA * 0.1%=0.1mA, so if we keep our *change* in current draw to less than half of that, we can guarantee that there will be no detectable change in the current measured. We'll assume that uC draws 25mA fully on, or a change in uC current from off to on of 25mA. In the small signal model a zener looks like a resistor, so our circuit is now:



R1 is the 73Ohms we calculated earlier, and Rz is the impedance of the zener. (also known as the zener differential resistance) Our load now looks like a current source, and the input voltage disappears. What we want is for IR1 to be less than 0.05mA for I=25mA. So, I=IR1+IRz -> I=IR1+V/Rz Now what's V? Simply I*(R1*Rz)/(R1+Rz), so I=IR1+I(R1*Rz)/((R1+Rz)Rz) -> Rz=I*R1/(I-IR1) - R1=0.146Ohms

See, that's the catch, seemingly OK zeners can't meet this spec. For instance all of the BZX84 series zeners have maximum impedance of greater than 10Ohms, even if they look OK otherwise. Unfortunately, it looks like zeners that meet our requirements don't actually exist; the minimum zener impedance on digikey for a 3.3V zener is 3Ohms, and that spec only applies if you are drawing 380mA.

So lets go back to a software/hardware solution. Suppose we can get the change in current down to 0.25mA by clever software that carefully uses the same amount of power no matter what the cryptographic engine is doing. The above equation now gives us 18Ohms at the maximum, and as it turns out the $0.20 225mW MMBZ5226BLT1G is almost suitable at 28Ohms. (measured at 20mA) Solving for IR1 we get 0.18mA maximum, IE, this is the maximum change in current allowed before the host could detect it. So go work on the software some more!

Now what happens if the zener fails? Specifically, suppose the zener's impedance rises, such that the change in current through R1 increases. The only way we would know is if the voltage across R1 increases, so basically the uC now has to monitor the change in it's own voltage supply as it begins a cryptographic operation. That change would be equal to V=I(R1*Rz)/(R1+Rz)=3.4mV, tiny! Fortunately 10bit ADC's are quite common, so 3.3V/1024=3.22mV - we probably can't detect a subtle failure, but anything major is detectable. Such a design doesn't even have to be all that expensive if you use the other side of the R1 resistor as your Vref, which is OK because we only care about the difference between the too. Total implementation would be 4 0.1% resistors, $0.20 in volume.


Ugly 'eh? What looked so simple, just isn't. I gotta admit, I wasn't expecting a combined hardware/software implementation to be mandatory myself.

Peter Todd
Legendary
*
Offline Offline

Activity: 1120
Merit: 1147


View Profile
May 06, 2012, 01:29:24 AM
 #35

Good point to remember.
As suggested here, the device could have an embedded AM antenna and use the background noise as entropy source.

Regardless of how you collect your random data you should be also saving the state of the random number generator so you can restore it on the next power up. Currently the getRandom256() function collects new random bytes from the hardware generator, hashes them with sha256, and then returns that result. It really needs to operate with a persistent entropy pool to protect against a HWRNG failure. FWIW I just created an un-tested patch that implements this. See https://github.com/retep/hardware-bitcoin-wallet/compare/persistent-pool-prng

EhVedadoOAnonimato
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500



View Profile
May 06, 2012, 02:56:47 PM
 #36

Wow, sorry but you're talking Greek to me, retep.
What's the point in storing previously used random numbers? What's a HWRNG failure? I suppose the acronym means HardWare Random Number Generator, but still don't understand what you mean.
someone42 (OP)
Member
**
Offline Offline

Activity: 78
Merit: 10

Chris Chua


View Profile
May 06, 2012, 03:58:15 PM
 #37

How small are you thinking a final version maybe? As small as a USB stick with 2-line display?
I won't really know until I choose a display and layout a PCB, but I estimate a final version will have a size of about 1.5x the length/width/height of a typical USB stick.


I'm looking through the code. I guess the ECDSA and bignum algorithms were implemented more or less from scratch? I might use some of you algorithms for the C library I'm making. I was looking at other libraries including OpenSSL which is what the C++ client uses but none easily allow me to include only the specific parts I need into my library.
If you do choose to use the code, keep in mind that:
  • bigMultiplyVariableSizeNoModulo() is horribly slow. If you are going to hand-optimise or reimplement one function, choose this.
  • The "constant execution time" property of the algorithms may not carry over to a contemporary CPU because of caches and branch prediction. I don't have to worry about caching/branch prediction because none of the microcontrollers I'm looking at have these features.



The problem with random sleep periods is that you can still determine the underlying time taken through simple statistical averaging in many circumstances. Possible a better solution would be to start a timer at the beginning of any cryptographic operation, and then once the operation finishes wait until a fixed maximum-time has elapsed. That way every operation takes the same amount of time. Adding a further random delay on top of this fixed delay wouldn't be a bad idea either, to help mask any residual leakage. (for instance, suppose that the time measurement turns out to be flawed, and there is still a remainder which it does not detect)

If the attacker can also determine what the power consumption of your hardware wallet you have to hide that as well. Unfortunately in the case of a USB-powered wallet this is actually a realistic attack as some motherboards can measure how much power a USB device is actually consuming. To protect against this, the "makeup" time period should do something cpu-intensive as well, perhaps an additional, randomly chosen, cryptographic operation. (don't pick the same operation, with the same keys, in case there turns out to be a key-dependent power consumption)

Finally, at the hardware level you can choose a power supply with a fixed current consumption on the input. A zener diode and resistor voltage regulator, operated correctly, has a nearly zero change in input current for a change in output current and you can do even better with something more sophisticated.

For the OP: I'm an electronics designer and I'd be interested in working further on the hardware design.
The way my current implementation achieves constant time operation is to insert dummy operations instead of using branches. I believe this is like the "wait until maximum-time, while doing something cpu-intensive" approach, except that the waiting is interleaved instead of happening all at the end. However, it has the advantage that program flow is independent of secret data, so it also hides most (but not all) of the power consumption signature.

I had previously assumed that power analysis using a computer motherboard wouldn't be feasible for a hardware Bitcoin wallet. I assumed this because usually fast ADCs (at least the clock rate of the microcontroller) are required to do power analysis, and I doubt motherboards have 48 Msps ADCs in them. However, your comments have prompted me to question this. A point multiplication operation involves 256 point addition and point doubling operations which take place over some time (0.5 s to 4 s depending on the speed/power of the microcontroller). Sampling over each point addition/doubling would only require a < 1 ksps ADC and could possibly reveal information about secret data. Although I still think a power analysis virus is a bit exotic, it would be prudent to design some power analysis countermeasures into a hardware Bitcoin wallet.

About the hardware design: yes, I'd really appreciate help. Software mistakes can be fixed with a commit; hardware mistakes can require expensive redesign or rework.

See, that's the catch, seemingly OK zeners can't meet this spec. For instance all of the BZX84 series zeners have maximum impedance of greater than 10Ohms, even if they look OK otherwise. Unfortunately, it looks like zeners that meet our requirements don't actually exist; the minimum zener impedance on digikey for a 3.3V zener is 3Ohms, and that spec only applies if you are drawing 380mA.

So lets go back to a software/hardware solution. Suppose we can get the change in current down to 0.25mA by clever software that carefully uses the same amount of power no matter what the cryptographic engine is doing. The above equation now gives us 18Ohms at the maximum, and as it turns out the $0.20 225mW MMBZ5226BLT1G is almost suitable at 28Ohms. (measured at 20mA) Solving for IR1 we get 0.18mA maximum, IE, this is the maximum change in current allowed before the host could detect it. So go work on the software some more!

Now what happens if the zener fails? Specifically, suppose the zener's impedance rises, such that the change in current through R1 increases. The only way we would know is if the voltage across R1 increases, so basically the uC now has to monitor the change in it's own voltage supply as it begins a cryptographic operation. That change would be equal to V=I(R1*Rz)/(R1+Rz)=3.4mV, tiny! Fortunately 10bit ADC's are quite common, so 3.3V/1024=3.22mV - we probably can't detect a subtle failure, but anything major is detectable. Such a design doesn't even have to be all that expensive if you use the other side of the R1 resistor as your Vref, which is OK because we only care about the difference between the too. Total implementation would be 4 0.1% resistors, $0.20 in volume.


Ugly 'eh? What looked so simple, just isn't. I gotta admit, I wasn't expecting a combined hardware/software implementation to be mandatory myself.
Yeah, using simulation of a simple zener regulator circuit, I couldn't get better than a factor of ~3 reduction in power consumption signature.

I think a mostly software solution is possible. A relatively large (compared to what's possible on a smartcard) amount of passive filtering can be used to mask high-frequency power consumption signatures (with a cutoff in the 10s of kHz).

Say, for example, an addition: x + y requires i + d_i milliamp of current over one clock cycle, but the addition of ~x + ~y requires i - d_i milliamp of current over one clock cycle. As long as every necessary addition x + y is paired with a dummy addition ~x + ~y, total current consumption is always i milliamp of current over two clock cycles. Since the core clock of microcontrollers is in the Mhz range, the cycle-to-cycle variations in power consumption are not visible to an attacker; thanks to the filtering, only power consumption over hundreds of cycles is visible. The challenge is then to "pair" every necessary operation with a dummy operation that quickly compensates for the power comsumption of the necessary operation.



Seriously, 0,40USD is nothing. Even if it ads more than 1USD per unit, it's still nothing. Just use USB, it's the current standard, people wouldn't need adapters, you could use the same USB port to connect to the device that will provide the transactions to be signed, and maybe one day you could make it capable of writing the encrypted seed out for backup purposes. Wink
After seeing this: https://instruct1.cit.cornell.edu/courses/ee476/FinalProjects/s2007/blh36_cdl28_dct23/blh36_cdl28_dct23/index.html, I believe it is possible to bit-bang a USB host interface. So I will probably include a USB port on the wallet, for you to plug a USB keyboard into.
someone42 (OP)
Member
**
Offline Offline

Activity: 78
Merit: 10

Chris Chua


View Profile
May 06, 2012, 04:59:18 PM
 #38

Regardless of how you collect your random data you should be also saving the state of the random number generator so you can restore it on the next power up. Currently the getRandom256() function collects new random bytes from the hardware generator, hashes them with sha256, and then returns that result. It really needs to operate with a persistent entropy pool to protect against a HWRNG failure. FWIW I just created an un-tested patch that implements this. See https://github.com/retep/hardware-bitcoin-wallet/compare/persistent-pool-prng
If I understand your patch correctly, you are adding a persistent (across power cycles) entropy pool so that in the event of an undetected HWRNG failure, getRandom256() will degrade gracefully instead of immediately giving crappy random numbers.

This is a good idea, but you're using the encrypted read/write functions to do save/restore the pool state. I understand this is to ensure that the pool state is secret. But it is a problem because the encryption key the encrypted read/write functions use depends on which wallet is loaded. In some cases (eg. formatting non-volatile storage), random numbers are required when a wallet isn't even loaded (i.e. no encryption key is set).

The most general and secure fix I could think of for this is to define a "global" wallet encryption key, which exists solely to encrypt the pool state and its checksum. Actually, now that I think about it, the global wallet encryption key can also be used to encrypt the wallet names/versions. But this will require some significant changes elsewhere in the codebase. I will fully incorporate your suggestions, but only after I add support for multiple wallets.
Peter Todd
Legendary
*
Offline Offline

Activity: 1120
Merit: 1147


View Profile
May 07, 2012, 02:03:07 AM
 #39

If I understand your patch correctly, you are adding a persistent (across power cycles) entropy pool so that in the event of an undetected HWRNG failure, getRandom256() will degrade gracefully instead of immediately giving crappy random numbers.

Exactly.

This is a good idea, but you're using the encrypted read/write functions to do save/restore the pool state. I understand this is to ensure that the pool state is secret. But it is a problem because the encryption key the encrypted read/write functions use depends on which wallet is loaded. In some cases (eg. formatting non-volatile storage), random numbers are required when a wallet isn't even loaded (i.e. no encryption key is set).

The most general and secure fix I could think of for this is to define a "global" wallet encryption key, which exists solely to encrypt the pool state and its checksum. Actually, now that I think about it, the global wallet encryption key can also be used to encrypt the wallet names/versions. But this will require some significant changes elsewhere in the codebase. I will fully incorporate your suggestions, but only after I add support for multiple wallets.

Ah, I see what you mean. That said, in the interm it's probably acceptable to simply store the random seed unencrypted. An attacker who gets hardware access to read it can only use that knowledge to find out what the random values will be in the future; past values are protected by the one-way property of SHA256. Any attacker who gains such access can do far worse things.

That said I should add some documentation to my patch making this clear, as well as think through this issue carefully.

Also, in general we should write a clear statement as to what types of attacks we're trying to prevent in the first place.

Peter Todd
Legendary
*
Offline Offline

Activity: 1120
Merit: 1147


View Profile
May 07, 2012, 02:45:41 AM
Last edit: May 07, 2012, 03:08:28 AM by retep
 #40

The way my current implementation achieves constant time operation is to insert dummy operations instead of using branches. I believe this is like the "wait until maximum-time, while doing something cpu-intensive" approach, except that the waiting is interleaved instead of happening all at the end. However, it has the advantage that program flow is independent of secret data, so it also hides most (but not all) of the power consumption signature.

That's a good technique. Have you tried to measure the actual current consumption vs. time yet?

I had previously assumed that power analysis using a computer motherboard wouldn't be feasible for a hardware Bitcoin wallet. I assumed this because usually fast ADCs (at least the clock rate of the microcontroller) are required to do power analysis, and I doubt motherboards have 48 Msps ADCs in them. However, your comments have prompted me to question this. A point multiplication operation involves 256 point addition and point doubling operations which take place over some time (0.5 s to 4 s depending on the speed/power of the microcontroller). Sampling over each point addition/doubling would only require a < 1 ksps ADC and could possibly reveal information about secret data. Although I still think a power analysis virus is a bit exotic, it would be prudent to design some power analysis countermeasures into a hardware Bitcoin wallet.

It also occurred to me that another possible avenue of attack would be for the virus to record audio from the computer's line-in port. On most computers a lot of power-supply noise gets into the audio subsystem, and yet at the same time the ADCs connected to it are fast and precise.

About the hardware design: yes, I'd really appreciate help. Software mistakes can be fixed with a commit; hardware mistakes can require expensive redesign or rework.

Sure thing. What hardware experience do you currently have? I would be interested in starting a set of specs and then schematics.

For licensing the TAPR Open Hardware License looks reasonable: http://www.tapr.org/ohl.html - out of respect for my employer, I do want to make it clear I'm not trying to make any money out of this project. At the same time, my employer is also quite clear that I own the IP to things I develop unrelated to my job.

Yeah, using simulation of a simple zener regulator circuit, I couldn't get better than a factor of ~3 reduction in power consumption signature.

I think a mostly software solution is possible. A relatively large (compared to what's possible on a smartcard) amount of passive filtering can be used to mask high-frequency power consumption signatures (with a cutoff in the 10s of kHz).

Yeah, fix thing where it's easy, software, first, and then fix it where it's hard.

Using the system sound card as our threat model, we really have to filter out, well, practically everything. Even the high frequency stuff needs to be filtered as we can't predict what non-linearities exist in the system that would downconvert, say, 1MHz to 5KHz. That said, ferrites are cheap, and as you say, we've got a lot more room for stuff like that than on a smartcard. We'll have to come up with a plausible attack in detail to figure out just how many dB of reduction is required; unlike the projects I normally work on cost is a factor. Smiley

Of course, if cost is a problem, this can be a differentiation thing as well. Sell one version with "pretty-damn-good" security that leaves out the filtering and another "god-damn-bankvault" version that puts in back in.

The bankvault version can have all sorts of fun paranoia. For instance, if you have a sealed box, the best way to protect against it being opened is to put a light sensor and a light, in the box and trigger the alarm if the light level changes.

Say, for example, an addition: x + y requires i + d_i milliamp of current over one clock cycle, but the addition of ~x + ~y requires i - d_i milliamp of current over one clock cycle. As long as every necessary addition x + y is paired with a dummy addition ~x + ~y, total current consumption is always i milliamp of current over two clock cycles. Since the core clock of microcontrollers is in the Mhz range, the cycle-to-cycle variations in power consumption are not visible to an attacker; thanks to the filtering, only power consumption over hundreds of cycles is visible. The challenge is then to "pair" every necessary operation with a dummy operation that quickly compensates for the power comsumption of the necessary operation.

Yup. Pretty standard techniques, although we'll have to be careful to actually verify that the techniques really do work.

After seeing this: https://instruct1.cit.cornell.edu/courses/ee476/FinalProjects/s2007/blh36_cdl28_dct23/blh36_cdl28_dct23/index.html, I believe it is possible to bit-bang a USB host interface. So I will probably include a USB port on the wallet, for you to plug a USB keyboard into.

Nice! A keyboard is going to be a very slick interface, although do consider leaving a backup option for laptop users.

Incidentally, a keyboard makes possible a mode of operation that I think some users might like: brainwallet. The idea here is that you don't store the private key on the device at all. Rather each time you want to make a transaction, you connect the device up to a secure computer, type in your passphrase, have the device turn that into the wallet seed privkey, and then it tells the computer the public key portion of the seed. When you're done, the device forgets the privkey.

Now if the device falls into wrong hands, it can't even be used to show that you made transactions at all with that wallet, let alone steal coins from the wallet.

Pages: « 1 [2] 3 4 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!