"Bitcoin Security Module": Adding hardware security for hot wallets

[DeathAndTaxes]

Bitcoinica didn't need to happen and yet it did twice.  Hot wallets are a necessity in some applications yet the nature of Bitcoin means any security breach now matter how rare puts the full value of the wallet at risk.  Since knowledge of the private key is control of the funds the only safe hot wallet is one where gaining access to the tx server doesn't give one the ability to access the private key.  This means keeping keys even from admins or super-admins.

I am building a hardware based solution around a programmable cryptographic processor.  The cost is in the hundreds of dollars but still significantly cheaper than a an off the shelf HSM.  Bitcoin presents some unique challenges for a HSM.  Simply keeping the key a secret until needed isn't sufficient.  The hardware module needs to sign transactions while never revealing the key. 

At this point the prototype can only sign a (2 output only) tx based on a single internally stored private key.  At this point the prototype wouldn't provide any real security.  While the attacker couldn't gain access to the private key he could just request an unlimited number of signed tx.  The full solution would be to allow programming the device with business rules which limit the type, value, and frequency of the transactions.

The hardware has both volatile and non-volatile storage so keys can either held in volatile memory only (and need to be reloaded loaded upon power cycle) or can stored in non-volatile encrypted storage to allow keys to survive power cycle.  An independent hardware timer allows the module to keep track of time which can't be spoofed by the attacker but will require secure timestamp to be provided at initialization (most likely from NTP server).

Constraints on the available memory prevent creating an entire bitcoin client so the module will need to rely on a host client for transaction setup, initialization, and connectivity to the bitcoin network.

Current capabilities:
* prevent extraction of a single private key once loaded
* sign dual output tx (where change is returned to same address)

Planned capabilities:
* limits on tx size and volume
* lock-down mode based on threat detection rules (client asking for tx which violate rules)
* delayed tx signing based on business rules (module returns tx encrypted w/ AES-256 which client will request decryption after "cooldown" time has elapsed)
* intrusion notification
* random write-erase-write cycle to ensure key destruction

[justusranvier]

I'm no cryptographer but I seem to remember that algorithms exist to split an encryption key such that N of M fragments must be used to form a valid signature.

Could such a system be used to create a separate verification system on a physically different computer (without requiring special hardware) so that even if the computer storing the hot wallet is compromised it can't generate transactions by itself?

[Stephen Gornick]

Planned capabilities:
* limits on tx size and volume

Not sure if this would by added as part of the business rule, or if included in the architecture but there will likely be transactions to a cold storage address which would need to bypass the restriction on tx size and volume.

Also, what would the connection for programming the unit be?  e.g., USB?

[mistfpga]

Good work,

I am doing a very similar thing, but using the armory client.  (we are also looking at a fpga option, for a proper hsm type effect.)

(still waiting for my edge...)

if there is anything i can do to help, I will, just give me a shout.

As I was typing this Stephen Gornick posted

Not sure if this would by added as part of the business rule, or if included in the architecture but there will likely be transactions to a cold storage address which would need to bypass the restriction on tx size and volume.

I have been thinking about just this problem - to me this is the biggest stumbling block.  my solution is to have all the rules predfined. then hash these rules, now you can enforce the rules on the non secure machine, you just pass the rules over the serial port and the box that recievs them hashes them, checked that against its _local_ db and if it is all good then allow the transactions.  if there is a mismatch someone is messing with you, so shred the keys and kernel panic.

cheers,

steve

[cypherdoc]

congratulations.  you guys are doing some badly needed work on security.

[sebastian]

Would suggest 2 modes instead:

1: Retailer/end user mode: The device will require a momentarly physical button to be held down for it to sign a outgoing tx. If a attempt is made to sign a tx without button held down, it will disconnect USB interface and beep each Xth second. (Xth second needs to be carefully selected so its not annoying, but its "hey someone is trying to steal your funds").
To reset, the user needs to disconnect the device and reconnect.
There should not be able to discern if the physical button is being pressed or not, from the USB interface, before its "too late", so a trojan cannot wait until the button is being pressed and "piggyback" that.
It will only sign one TX for each button press, for sending multiple TX, you would need to release the button and press again.

-----

2: Exchange/onlinewallet mode:
The device will keep a database of users, hashed password, their balance, and their receiving adress.
The device will NOT sign a TX that would cause a user's balance to go negative.
Along with a TX to it for sign, the requestor needs to supply a username/password of whoever's account to use.

The device also needs someway to verify incoming funds. So the device in some way needs to know the blockchain, or some other way to verify that a incoming funds is real, and then populate the user's balance, then automatically "sweep" this adress to the exchange/onlinewallet's main adress/hot wallet, then delete privkey and adress from user storage. Will also send out signed transactions for the host to just send out on the network. (sweep transactions)

It does not need to save the whole blockchain, the device would only need to save the 6 last blocks, because when it have seen a transaction and populated that user's balance with the money, the block is no longer needed for the device in question.

There also needs to be meta functions:
create account - creates account with 0 balance
delete account - deletes account if correct password is specifyed, but ONLY if the balance is exactly 0.
change password - changes password of a user.
update user balance - Can be used to deduct money from user, but not add.

The physical button will in this case function for password reset. While its held down, the device will accept any "old" password for changing password on a user (and not just the correct password). So basically, if a end user forgot his onlinewallet/exchange password, this would require manual intervention, where the site operator initiates a password reset, then physically are present at the HSM to hold down the button and then completes password reset, then gives the new password to the end user.

The physical button held down will also make the device accept any TX without any user, and this is when site operator collects fees from the main wallet.
The physical button also needs to be held down for it to register a "checkpoint" block, which will be required during initalization.
The physical button held down will also allow "update user balance" to add funds.


The security in this is: Lets say bitcoinica case.

Lets say bitcoinica consist of 180 users with 100 BTC in each wallet. The HSM device will then have a "hot wallet" (one address) of 18 000 BTC and 180 users inside.
A hacker that hacks into bitcoinica server, will not know any user's password because they are hashed at the site database. The hacker needs to crack these to get the unhashed password to authenticate to the HSM with. Lets say the hacker manages to crack 5 users.
The hacker will now use password for user 1. He now tries to get the HSM to sign a transaction for 18 000 BTC. But the device sees "the hot wallet contains 18 000 BTC but user 1 only have a share of these of 100 BTC" and will reject the transaction.
The hacker only have the choice of signing a sum of under 100 BTC.
So in this case, he would only be able to steal 500 BTC (5 users with 100 BTC in their account each)

For the hacker to be able to push larger transactions, he would need to crack a user that have depoisted a large sum at the exchange/onlinewallet service. And users with large BTC sums tend to have secure passwords = fail for the hacker.


So basically, the device would accept a 10 000 BTC transaction, ONLY if the user that is specifyed in the signing request, have 10 000 BTC in his account.




-----

Basically this would solve everything without delays for end users and without manual intervention at "correct" large transactions.
The "password" used to authenticate at the HSM for a specific end user can be anything, a encrypted string or whatever, even a expected "reply" from a security token or whatever.




NOTE: Dont misunderstand this now. With "balance", I DONT mean the wallet balance at the end user. I mean the balance the user have in a "virtual" account at the online exchange or online wallet service. This are NOT a actual bitcoin wallet balance, its just a stored-value of whatever a end user can spend at that site.

[DeathAndTaxes]

sebastian,

I am glad to get a conversation going and there is no one solution.

Hardware devices tend to have limited resources.  The hardware device I am using has very limited memory and storage (under 200KB combined).  It simply wouldn't be possible to store user data inside the module.  Currently it only works with a single private key.  Working with multiple keys may require storing it outside the database in encrypted format.

Also trying to limit tx based on user's balances has limited utility.  If we assume the attacker has complete control of the host they could simply record a fake deposit and then request a withdrawal.  I am glad you are thinking about it though.  We need lots of people thinking about it.

I am taking the approach that if the attacker doesn't have access to the private key he needs to play by the "rules" and those rules can be constructed to limit the amount of the loss (potentially to nothing if the attacker triggers a lockdown or generates tx which have a required waiting period before decryption).

[rjk]

The whole point is that the HSM is a single-purpose device. There is no point loading it down with extraneous functions, because they could be better performed by normal hardware in the usual manner. Additionally, giving the HSM a large set of features just means that many more things to hack and break. You want it to have a blockchain? That needs a network connection, which is not smart to have on such an HSM. Most HSM devices are connected via a serial port for a good reason: Harder to hack remotely.

[DeathAndTaxes]

Planned capabilities:
* limits on tx size and volume

Not sure if this would by added as part of the business rule, or if included in the architecture but there will likely be transactions to a cold storage address which would need to bypass the restriction on tx size and volume.

There are a couple of ways to do this and I am still thinking about how it is best handled.  

One method would be to have all deposited funds go directly to cold storage and then generate when you initialize the device it generates a hot address and the operator sends some of the funds to the hot wallet.  Once the rules are set there is no bypass or override.  

Another option would be to have a cold storage address loaded as part of the initialization parameters and unlimited funds can be transfered to the cold storage but any other address must follow "the rules".

A third oprtion which is more flexible but potentially less secure is to allow an override password (more likely a 128bit or 256 bit key) that would allow the operator to disable/modify the tx rules.  Even this is still more secure than a plaintext wallet as in normal operation the "override key" wouldn't be stored on the tx server.

Personally I think the second option is optimal but right now I am just trying to get the basics working.  The bad news is even send many is complex (possibly requiring swapping data in and out of the device) given the constraints on memory and storage.

Also, what would the connection for programming the unit be?  e.g., USB?

Either.   The interface will be transparent to the loading of the assembly and communicating with the device.

[sebastian]

DeathAndTaxes: Lets spin off of the idea and improve it then.

We could have encrypted storage outside of HSM in this way:
All accounts are stored OUTSIDE of HSM, but encrypted with a key ONLY the HSM knows. Lets call this encrypted chunk of data for a "blob". This "blob" are stored in the user's row at the site database.

Then each time a account needs to be used, its fed to the HSM and the HSM updates the account and returns the encrypted account blob.

BUT we need some way to verify we are not using a "old" encrypted blob with a "old" balance. I got a idea: Let each account have a n-bit ID. Each encrypted blob contains the ID and a small random value.
The random value is stored inside the encrypted blob along with ID.

Each time anything in the encrypted blob is updated, the new encrypted blob will have a new random value. (but same ID).
the HSM will NOT accept a encrypted blob containing a unmatching random value.

User's private keys and such can be stored in this blob too.

The random value and ID is stored in internal HSM memory. Lets say a 14 bit ID and a 18 bit Random.
14 bit ID will account for 16384 users.
Each user will "use up" 4 bytes
That will be a total of 64KB internal flash memory used.

And you would need 262 144 transactions on a SINGLE USER before random numbers start to repeat. And that would only allow a attacker to duplicate a balance ONCE. A simple cooldown between each command sent to HSM with lets say 1-2 seconds would slow down the attacker considerably.
Duplicating the balance would require this from attacker: Send a small transaction using blob1. Receive blob2 from HSM. Send blobOLD and see if the HSM accept it. Send a small transaction using blob2. Receive blob3 from HSM. Send blobOLD and see if accept. Send transaction using blob3 and receive blobN from HSM and so on and so on.

A cooldown of 2 seconds between each command would require 6 days work from a attacker before the attacker MAY succeed, and before 6 days, a attack would be guranteed noticed.



>>"If we assume the attacker has complete control of the host they could simply record a fake deposit and then request a withdrawal."
Nope.
The HSM should of course require you to feed it valid blocks. You feed it blocks as soon as you find it on the bitcoin network, and the device saves 6 blocks by hash in "flash" and saves the whole latest block in RAM while updating balances. After the host have indicated its done with feeding blobs, the block will be deleted from RAM.

The Host would need to keep track of which users to feed to the HSM for balance updating when it receives a payment block for one of it user's adresses.
So for it to INCREASE balance, it would need the attacker to actually depoist money into a user's account.

So the host does this when it sees a block paying lets say BitCoinUSER on Bitcoinia:
Host sends the block to HSM. HSM processes the block, and now it expects a blob to update.
The host now replies with the blob corresponding to BitCoinUSER.
HSM decrypts blob, increases balance and random value, reencrypts it, return to the host.
host saves this new blob in the database row for BitCoinUSER.

Host can indicate to HSM if the host has more blobs to feed, for example if transaction have multiple outputs pointing to a single user each.
Or if a block is totally unrelated to the site in question, the host can indicate like "0 blobs to feed".


So the encrypted blob (ONLY decryptable by HSM) would then contain:
Username - Hashed password - Balance - Receiving address - UserPrivate Key - UserID - Random Nonce

And the host database would then contain:
Username - Hashed password - Balance - Receiving address - (some other details) - Latest encrypted blob from HSM.

Note that the host database now contains the username, hashedpassword, balance, recv adress 2 times, one in plaintext format and one in encrypted format. The plaintext format is so the site can itself verify balance and other details before bothering the HSM. Of course the plaintext values is not sent to HSM and does not affect HSM in any way.

A depoist of for example USD --> BTC would then require manual intervention by site operator.
But BTC --> USD would then be direct.
This are also inline with site's policies, since a site WILL want to verify a USD depoist really hard before sending bitcoins, because a USD depoist may be chargebacked.


rjk: Of course the blocks is fed by the serial port, and not via the internet.



OVERRIDE IDEA:
You are talking about a 128bit/256bit key. Not needed at all.
Simply have a momentarly pushbutton on the HSM. This button needs to be physically held down while loading new "rules" or overriding rules.
A attacker who "pwned" a server online cannot reach the physical button and cannot bypass the HSM.


But the problem with "rules" is that a user owning a 1000 BTC account may not be able to use his account fully without a site operator having to confirm transactions.
We need some way to store/process indivual users in the system in some way, so a user owning 1 BTC will only be able to send 1 BTC, a user owning 1000 BTC will only be able to send 1000 BTC.

[galambo]

I think sebastian's diagram could work if the BSM was a small PC with something like a yubico HSM on it. If his cleartext message included an OTP to check with the HSM. What do you think?

[sebastian]

galambo: Or what about a raspberry Pi?
The Raspberry Pi could BE the HSM actually, and have a hardened OS on the SD card. Theres space on the board to mount a extra physical button that will affect one of the GPIO's that will make the HSM to bypass almost all security checks while its depressed.

like if (sha512($suppliedpassword) == $userhash || $GPIO16 == true) then

end if

The OS could be built by the bitcoin community and be freely downloadable as a image, that then can be dd'ed to a SD card. And SD card size then tells how many users it can store.

There is serial connections on the board, else a simple USB null modem serial cable (a cable with 2 USB males and a fat thing in the middle containing rs232 electronics) could be used to connect the raspberry to the host.
since the rs232 interface is well defined, there would be no possibility to "hack" the system.

[DeathAndTaxes]

sebastian you say the HSM can "know" when a user deposits but the only way it can natively "know" is if there is an entire blockchain and bitcoind and connectivity with multiple legit nodes all inside the the HSM.

If the bitcoind, blockchain, and bitcoin network connectivity is on the host you have to assume all of that is now under the control of the attacker and the HSM is simply being fed data which the attacker wants to see.

I encourage multiple different approaches but trying to put the entire tx server inside the hsm isn't really a hsm any more.  It is just a server and bitcoinica thought they had the server well secured.

[galambo]

galambo: Or what about a raspberry Pi?
The Raspberry Pi could BE the HSM actually, and have a hardened OS on the SD card. Theres space on the board to mount a extra physical button that will affect one of the GPIO's that will make the HSM to bypass almost all security checks while its depressed.

like if (sha512($suppliedpassword) == $userhash || $GPIO16 == true) then

end if

The OS could be built by the bitcoin community and be freely downloadable as a image, that then can be dd'ed to a SD card. And SD card size then tells how many users it can store.

There is serial connections on the board, else a simple USB null modem serial cable (a cable with 2 USB males and a fat thing in the middle containing rs232 electronics) could be used to connect the raspberry to the host.
since the rs232 interface is well defined, there would be no possibility to "hack" the system.

Well, I wouldn't trust myself to implement such a system on a raspbery pi for production use. I would review this document (http://static.yubico.com/var/uploads/pdfs/YubiHSM%20Manual%202011-09-14.pdf) for operation mode ideas if I was going to try to implement one myself. Additionally, I would like to review some other vendors products, but I doubt they will openly discuss their implementation.

[sebastian]

DAT: But as I said the site operator "initalizes" the HSM by helding the pushbutton and then feeding it with the 6 latest blocks.
After releasing pushbutton, the HSM will never accept a block which isn't "valid" according to the previous block hash and PoW.

So the hacker, despite having full control, cannot feed "false" blocks to the HSM since the block needs to be "tied" to the latest block.
Only way would be for attacker to redo the PoW, but that would take too long time.
Supressing any blocks would only be negative for the attacker, since a incoming balance would not be reflected on a user account and the user has access to less funds to steal.


Maybe it could store the userIDs to the 6 latest block temporarly in memory, and only updating randomvalue and returning blob upon receiving 6 confirmations?

So basically:
1: Host feeds blockA to HSM
2: Host feeds BlobA to HSM
3: Host feeds BlobB to HSM
4: HSM stores these userIDs along with how much the balance should be increased.
5: Host feeds blockB to HSM
6 ...*...
and so on
.....
.....
20: Host feeds blockG to HSM.
21: Host sends BlobA to HSM (again).
22: Host sends BlobB to HSM (again).
23: HSM returns updated BlobA to Host
24: HSM returns updated BlobB to Host


To "fool" the HSM, the attacker would need to compute 6 sequental fake blocks and send to HSM. Note that the HSM throws away the block once all required data is extracted, and only saves the 6 latest hashes, so the HSM would only need to store one single block in memory + 6 hashes in flash. Since the balance is stored in blobs, the HSM does NOT need the whole blockchain.

PoW of 6 blocks is really challenging for a attacker to create.

[DeathAndTaxes]

Well, I wouldn't trust myself to implement such a system on a raspbery pi for production use. I would review this document (http://static.yubico.com/var/uploads/pdfs/YubiHSM%20Manual%202011-09-14.pdf) for operation mode ideas if I was going to try to implement one myself. Additionally, I would like to review some other vendors products, but I doubt they will openly discuss their implementation.

The Yubico HSM is a classic example of how I said Bitcoin presents some unique challenges.  In most HSM applications you are simply protecting the private key.  The Yubico can protect a private key, it can even sign a tx but it has no concept of "what" it is signing.

So to take Bitcoinica as an example the attacker would be unable to steal the private key but it could ask the Yubico to sign this tx transfering 18K from Bitcoinica hot wallet to the attacker's address and the Yubico would happily do it.

[DeathAndTaxes]

sebastian,

That still requires HSM to be able to parse &validate blocks, find tx, match them against user database, validate tx, determined deposited amounts, and update user's profile.  I think you may be overestimating the computational power of these devices (well at least the ones which don't cost $80K).   My goal would be to get the cost <$500 installed that requires making the BSM logic as simple as possible.

Still I encourage you to start coding and experimenting. 

[galambo]

Well, I wouldn't trust myself to implement such a system on a raspbery pi for production use. I would review this document (http://static.yubico.com/var/uploads/pdfs/YubiHSM%20Manual%202011-09-14.pdf) for operation mode ideas if I was going to try to implement one myself. Additionally, I would like to review some other vendors products, but I doubt they will openly discuss their implementation.

The Yubico HSM is a classic example of how I said Bitcoin presents some unique challenges.  In most HSM applications you are simply protecting the private key.  The Yubico can protect a private key, it can even sign a tx but it has no concept of "what" it is signing.

So to take Bitcoinica as an example the attacker would be unable to steal the private key but it could ask the Yubico to sign this tx transfering 18K from Bitcoinica hot wallet to the attacker's address and the Yubico would happily do it.

I think the point of the hardware in this application is to verify that the internal servers are receiving their commands from the web server directly, before the transaction server does the transaction. I don't think the HSM can verify anything beyond that. The verification of accounts (ledger entry) is a separate verification. The verification that the user is authorized to initiate the transfer is a separate step of authentication.

[paraipan]

Well, I wouldn't trust myself to implement such a system on a raspbery pi for production use. I would review this document (http://static.yubico.com/var/uploads/pdfs/YubiHSM%20Manual%202011-09-14.pdf) for operation mode ideas if I was going to try to implement one myself. Additionally, I would like to review some other vendors products, but I doubt they will openly discuss their implementation.

The Yubico HSM is a classic example of how I said Bitcoin presents some unique challenges.  In most HSM applications you are simply protecting the private key.  The Yubico can protect a private key, it can even sign a tx but it has no concept of "what" it is signing.

So to take Bitcoinica as an example the attacker would be unable to steal the private key but it could ask the Yubico to sign this tx transfering 18K from Bitcoinica hot wallet to the attacker's address and the Yubico would happily do it.

I think robberies would be solved really easy if a bitcoin developer is willing to dedicate some time to it. Writing a patch that implements a set of custom rules in bitcoind that any merchant can configure when compiling the daemon could render hotwallet wallet hacks a thing of the past. Some rule examples: allowed coin amount per tx, e-mail warning of the wallet coins level.

I remind you that we already have private key protection implemented at the lowest level with the wallet encryption. Unlocking the wallet when needed is done by the online platform on the same rpc channel. The passwords used for connecting to rpc and for unlocking the wallet can be obfuscated within a compiled binary on the same server as the app.

Why use expensive and dedicated hardware when all that's needed is a little brainstorming ?

[galambo]

You could use each one of these authentication step(user, accounting, web server) to generate an (counter-based) OTP, then "glue" all of the OTPs together to make a private key to decrypt your keystore. This way you wouldn't even need HSM.

KeePass Password Safe Plugin "OtpKeyProv" does something like this.