Split private keys

[Mike Hearn]

I think the right design is for a device that plugs in via USB, that provides a display and a button.

The device receives an encrypted/signed message containing a bit of text and a nonce. The text is displayed. The button simply sends the nonce back to the host in the clear (the confirmation).

If you want to send money to somebody via a BitBank, you go into the UI (or click a link that prefills the field) and enter:

1) The value
2) Optionally, a Bitcoin address (or public key)
3) An email address or domain name for the counterparty you're trying to pay, as in genjixs scheme

The BitBank (which we assume is secure) either challenges the counterparty to sign a nonce with the private key corresponding to the address/pubkey, to prove ownership. Or if no address was provided it just goes and retrieves one, eg via http.

The BitBank then encrypts/signs a message containing the friendly address, a browser plugin sends it on to the hardware which decrypts it. Note that the compromised host cannot see or change the message. It is displayed on the little LCD display and after checking it says what is expected, the user presses the button. The nonce is then sent back to the BitBank which uses it as confirmation of the transfer.

This is similar to but not the same as the smartcard based schemes used by regular banks. Actually hosting the wallet or private keys on a smartcard doesn't make much sense, because the vulnerability is still in the display/input systems. And typing an address into a bank style calculator also doesn't make any sense because a virus could rewrite the address to be one of its own.

So I claim to be able to safely transact on a machine rooted by an arbitrarily skilled/motivated opponent, you need all of: a secure remote wallet, a secure display/input system (lcd display+button), user readable addresses. This would actually be MORE secure than the best banking security available today, because even 2-factor signing of wire transfers can fail if you get the bank wire instructions via a compromised host (they could be rewritten to be somebody elses bank account without you noticing).

The technologies you need to create the little display+button device are all pretty cheap, so I'm sure this will happen at some point. On the software side what's needed is a transition to user-friendly addresses rather than hash160s, and a challenge or pubkey request protocol.

[ben-abuya]

Hmm, if we have the device with the screen and button, why do we need the BitBank? Since the only way to spend any coins from your account is to see the recipient address and amount on the device, and confirm with the button, what does the BitBank bring to the table?

I agree about the user friendly addresses. That might be a major hacking vector in the future because people aren't good at visually identifying those addresses. Something graphical would allow humans to leverage our brains' impressive image processing and pattern recognition capabilities. A strategy of running some 2d transform on the address and turning it into a colorful picture might be cool. Of course then hackers would try to find an address that produces a similar looking image, but maybe it's possible to make that hard. Another good approach is to add whitelisted addresses to the device as you make payments. You could also have trusted services that provide whitelists and text mappings to addresses, kind of like https domains.

[kjj]

Looks like the two approaches are completely different.

One doesn't require the user to have to buy/build any specialized hardware.  The other doesn't require the user to rely on an external service.

The bitcoin world is big enough for both approaches to make sense at different times or to different people.

And I must say that after looking into actually implementing ECDSA on tiny hardware, I'm really, really warming to Gavin's idea.

[ben-abuya]

Looks like the two approaches are completely different.

One doesn't require the user to have to buy/build any specialized hardware.  The other doesn't require the user to rely on an external service.

The bitcoin world is big enough for both approaches to make sense at different times or to different people.

And I must say that after looking into actually implementing ECDSA on tiny hardware, I'm really, really warming to Gavin's idea.

But there is no approach in which you only need an external service and no external device. If the root-kit has control of your computer, you can't trust anything on the computer, not even an https connection to a trusted server. How will you confirm the transaction? Or is the root-kit confirming it for you? Or are you confirming it, but to the wrong address?

I think the idea of an external device is a good one, since it's much easier to secure than your home computer. You don't have to implement ECDSA on tiny hardware, there are already smartcards available with this capability.

[kjj]

Looks like the two approaches are completely different.

One doesn't require the user to have to buy/build any specialized hardware.  The other doesn't require the user to rely on an external service.

The bitcoin world is big enough for both approaches to make sense at different times or to different people.

And I must say that after looking into actually implementing ECDSA on tiny hardware, I'm really, really warming to Gavin's idea.

But there is no approach in which you only need an external service and no external device. If the root-kit has control of your computer, you can't trust anything on the computer, not even an https connection to a trusted server. How will you confirm the transaction? Or is the root-kit confirming it for you? Or are you confirming it, but to the wrong address?

I think the idea of an external device is a good one, since it's much easier to secure than your home computer. You don't have to implement ECDSA on tiny hardware, there are already smartcards available with this capability.

You don't confirm the transaction.  What happens is that the service fails to confirm bogus transactions made in your name by your (pwn3d) computer.

[ben-abuya]

You don't confirm the transaction.  What happens is that the service fails to confirm bogus transactions made in your name by your (pwn3d) computer.

Ok, rereading Gavin I see that "give me a call on big transactions" is the external device. Also, the "something I get in the mail" is an external device. I'm not sure it's worth going through all this, risking small transactions, getting telephone calls, relying on a 3rd party site, when you could just plug that something you get in the mail into your usb port and be quite secure from the start. The usb device could even auto-sign small transactions (no need to press the button) and keep track of how many transactions are being sent every day and notify you if something is weird. Someone mentioned that you can hack a $20 mp3 player and install your own software. It's already got a display, input device and usb plug.

If you did want to implement Gavin's idea, bitcoin already supports multisigned transactions. You'd require 2 of 3 signatures. One on your computer, one kept by the service, and one in the thing you get in the mail. The partially signed transaction would have to be sent to the online service for the 2nd signature, and the service would forward it to the bitcoin network.

[kjj]

I'm not sure it's worth going through all this, risking small transactions, getting telephone calls, relying on a 3rd party site,

That's fine, no one is going to force you to.  But some people will find it useful.

Someone mentioned that you can hack a $20 mp3 player and install your own software. It's already got a display, input device and usb plug.

Any chance you could find that reference?  I would love to see it, but searching for "hackable mp3 player" doesn't turn up the sorts of things I'm looking for.

By the way, I am actively working on the hardware device route.  I know what capabilities it is going to need, and what the communication protocol is going to look like, but I haven't yet found a hardware platform that is both simple to develop on and capable of doing the crypto.

[shads]

The attacker will have to install some kind of keylogger or memory logger and then wait for the next time the user needs to decrypt the private component of the wallet to sign a transaction.  Plus, odds are decent the user may discover their infection in the interim before they ever decrypt their wallet.dat.

I know this is way OT but thinking along the same lines what about CydeWeys suggestion in conjunction with implementing a file access hook to wallet.dat?  Various alerting options (sms via webservice, email, dialog box etc..) warn user that a process other than their chosen bitcoin client is attempting to read the file.  Of course it would need a separate implementation per OS.  Since it would need to run as a service it could probably be a separate but complementary project but would be nice to include as an option in the default client package.

[ben-abuya]

That's fine, no one is going to force you to.  But some people will find it useful.

This is a design discussion, we're trying to evaluate what would work best for the average user, it's not about what I want to use. My question is why would people find this useful if they can get the same functionality from a device they'd need anyway?

Any chance you could find that reference?  I would love to see it, but searching for "hackable mp3 player" doesn't turn up the sorts of things I'm looking for.

Sure: http://forum.bitcoin.org/index.php?topic=17919.msg227691#msg227691

By the way, I am actively working on the hardware device route.  I know what capabilities it is going to need, and what the communication protocol is going to look like, but I haven't yet found a hardware platform that is both simple to develop on and capable of doing the crypto.

What about the cryptocards like this?

http://www.gemalto.com/products/top_javacard/download/TOP_DL_v2_Sept10.pdf

Not sure it has the exact curve bitcoin uses, but it's getting pretty close.

[kjj]

That's fine, no one is going to force you to.  But some people will find it useful.

This is a design discussion, we're trying to evaluate what would work best for the average user, it's not about what I want to use. My question is why would people find this useful if they can get the same functionality from a device they'd need anyway?

Any chance you could find that reference?  I would love to see it, but searching for "hackable mp3 player" doesn't turn up the sorts of things I'm looking for.

Sure: http://forum.bitcoin.org/index.php?topic=17919.msg227691#msg227691

By the way, I am actively working on the hardware device route.  I know what capabilities it is going to need, and what the communication protocol is going to look like, but I haven't yet found a hardware platform that is both simple to develop on and capable of doing the crypto.

What about the cryptocards like this?

http://www.gemalto.com/products/top_javacard/download/TOP_DL_v2_Sept10.pdf

Not sure it has the exact curve bitcoin uses, but it's getting pretty close.

But they don't need the hardware device if they use an online service.  These are competing options, not a decision that must be made once for all users at all times.

Thanks for the link.  I'll check those out.  Hopefully one will be suitable.

I may get stuck with a Java device just for price reasons, but I personally despise Java, so I'm looking for other choices.  This would totally work, but is a bit expensive, and probably FAR more capable than we need.

[shads]

I may get stuck with a Java device just for price reasons, but I personally despise Java

I was going to derail the thread by leaping to java's defense until I realized that my previous suggestion is completely impossible to implement in it.

[kjj]

Hmm.  Think I found my hardware.

Sansa Fuze - $50 on Amazon
ARM9 based system on a chip (similar to the hammer I linked earlier) - up to 250 MHz, with 320K RAM on chip.
8 MB SD RAM
Couple gigs of flash, and microSD socket for backups.
Has a method for unbricking.

[Mike Hearn]

The point of the BitBank is to hold your keys. Obviously - the whole point is that your computer is actively working against you. So the most it can be trusted to do is relay messages, but you have to assume they might get modified in transit.

Smartcards or ECDSA in hardware aren't necessary in the design I proposed (which would have to be implemented by a BitBank of course). You could use any signing/encryption algorithm.

[just_someguy]

I don't have a great solution for this but maybe just some food for thought:

Key protection is a hard subject that people have been trying to solve for a long time.
There are a ton of solutions that someone might choose based on their comfort and circumstance.
If you guys get hung up on key protection schemes you could make a full time job of implementing them and the core development might suffer. There are a couple of projects out there right now that would be more easily adaptable to cranking out a multitude of different key protection schemes. Bitcoinj comes to mind.

Encryption of the wallet was a huge advance. Solving the key logger issue, etc, seems to be beyond the scope of what you need to solve. Let the OS developers take care of that.

Perhaps instead just add the ability to more easily import transactions generated by other programs.
If you added the option to monitor a folder for txt files and relay transactions contained in it I think you would see a plethora of key protection software develop without having to worry about it becoming the bulk of the bitcoin developers' time.

As an added benefit the relaying installation could have no knowledge of what keys you possessed period, thus having the ability to completely remove key management responsibility from the core client. I can't think of a more secure mode to operate under... assuming the client validated transactions before relaying them.

[smartcardguy]

Looks like the two approaches are completely different.

One doesn't require the user to have to buy/build any specialized hardware.  The other doesn't require the user to rely on an external service.

The bitcoin world is big enough for both approaches to make sense at different times or to different people.

And I must say that after looking into actually implementing ECDSA on tiny hardware, I'm really, really warming to Gavin's idea.

On a related note I found a commercially available smart card that supports the ECC curve bit coin uses and I have ordered samples, it provides a PKCS11 implementation which should be hook able into OpenSSL via it's engine interface. Its not the cards I though I would go with originally but they will work

1st step will be to get crypto to happen on the token, then the idea of getting a on device display for transaction or some other similar solution

http://www.athena-scs.com/product.asp?pid=33

[Gavin Andresen]

RE: cryptocards instead of an online service:

Seems like we aught to be able to come up with a protocol that works over the web or that can talk to http://localhost:SOMEPORT to interact with an attached smart-card device (there'd be helper software running on localhost:SOMEPORT that spoke the protocol and relayed to the smart card).

I wanted to start this discussion to make sure we don't re-invent the wheel, and to think in advance about what changes to core bitcoin (if any) are needed to support this kinds of functionality.

[ByteCoin]

The particular issue I'm submitting for consideration in this post is the implementation of a new future-proof address type.

Terminology
An overseen transaction is one where the user requires the assent of one or more third parties to complete the transfer of bitcoin.
The third party is termed the overseer. The service they provide is oversight.
Bitcoins sent to the user which require an overseen transaction to spend are overseen coins. The address they are sent to is an overseen address. Note that sending coins to an overseen address does not require an overseen transaction.


Oversight Service
The user signs up to an oversight service with a certain policy and mechanism on approving spends. The oversight service might be implemented as a USB dongle with a display or a web page accessible by a browser or by a call centre accessible by phone.


Overseen Addresses
The user needs to distribute a new overseen address to receive bitcoins and/or to send his existing bitcoins to. The scriptPubKey for transactions sending to an overseen address must require the users signature (like a normal transaction) and the overseer signature.
This is a non-standard transaction which potentially needs to contain two hash160s of information - one for the user's key and one for the overseer's key. It's troublesome to type in such a lot of information and to come up with a new address format for every new type of non-standard transaction.


Out numbers - a new address type
We observe however that it's very easy for the standard client to create a new transaction by copying the scriptPubKey of an existing transaction. So instead of sending to an address like 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa  which contains the hash160 of the credited public key we could send to scriptPubkey 0 as seen in the block chain. I'm going to refer to this as "out 0".

Address 1PSSGeFHDnKNxiEyFrD1wcEaHr9hrQDDWc would be out 170 as it's the coinbase transaction for block 170. The coinbase transaction for block 171 would be out 172 as block block 170 contains the first ever transaction,  sending 10BTC to 1Q2TWHE3GMdB6BZKafqwxXtWAWgFt5Jvm3 which is then out 171.

The onus for creating the first non-standard transaction and getting it into the block chain can therefore be shifted onto the oversight service.
When the user signs up, the oversight service creates a non-standard transaction crediting a tiny amount of bitcoin to the overseen address and gets it into the block chain. After a suitable number of confirmations the overseer works out the what position that address has in the block chain and passes that "out-number" (typo-protected, see below) to the user. The bitcoins required for the small transaction could have been transferred by the user to the oversight service on subscription as part of the fee for the service.  


Paying to overseen addresses - or to generic out-numbers
We modify the standard client so that when the user types an out number into the "Pay to:" box, the client looks up the relevant scriptPubKey and fills in the fields accordingly. So if a user types "o170" the client finds out that the scriptPubKey is just a simple transaction to address 1PSSGeFHDnKNxiEyFrD1wcEaHr9hrQDDWc and fills it in. If the user types the out number for an overseen transaction then the client looks up the scriptPubKey and recognizes the transaction type. It redraws the Send Coins window to include a box for the overseer address and it populates the "Pay to:" and "Overseen by:" with the destination address and overseer address respectively.

New schemes involving non-standard transactions will be seen to be useful and will be invented and implemented in future. The above solution is completely future-proof as the client software doesn't even need to understand the scriptPubKey in order to create a transaction sending coins to it. If the standard bitcoin client software and UI is altered to allow transactions to out-numbers then users of that software can send money to overseen addresses even if the bitcoin client does not understand overseen transactions. The client should allow the user to send bitcoins to an out-number for which the client does not understand the scriptPubKey after a suitable warning such as "This version of the bitcoin software cannot inform you how coins sent to this address will be disposed".


Preventing bitcoin transfers going astray with out-numbers
There is an issue with preventing the mistyping of an out-number because it's very likely that adjacent numbers will be valid out-numbers and also many transpositions of adjacent characters will also yield valid out-numbers. I suggest that the hash160 of the scriptPubKey base-52 encoded into "a-zA-Z" be appended to the displayed out-number. A typo-protected out-number would therefore look like "o170XcaYfWuomDEsiFqnaXDVxqHHTxMe". The user would not have to distribute, store or remember all the alphabetic part of the out-number as the client would look up the relevant scriptPubKey, hash it and fill it in. So for the above example "o170X" would provide approximately a 98% chance of typo detection, "o170Xc" would provide approximately a 99.9996% chance of typo detection and "o170XcaYfW" would reduce the chance of an undetected typo to about one in about twenty billion. Anyone distributing their out-number to receive payments could decide how long their protected outnumber was going to be up to a max of the number + about 28 characters.

The exact format of protected out-numbers is thrown open for discussion. There must be no confusion between the current address system and protected out-numbers. Out numbers are "numbers" by analogy with bank account numbers and to avoid commerically embarassing issues whereby inappropriate words are spelled out (cf. the issues with rude words in CAPTCHAs). The alphabetical "check" portion can be engineered to be free of inappropriate words.

Sending overseen coins from an untrustworthy computer
Users subscribed to an oversight service are possibly using rootkitted computers and must be running an oversight-enabled version of bitcoin to spend overseen coins. if all the coins in the users wallet are overseen then when the user presses send, the computer can't send a complete transaction as it does not have access to the overseer's key and can't generate the overseer's signature. (Except by using the "disappearing overseer recovery pack" mentioned by Gavin).

One possibility is that incompletely signed transactions be allowed to propagate across the bitcoin p2p network like a normal transaction. The overseers would see all the incomplete transactions which they could sign to complete and after checking with their policies and/or phoning the users etc they sign the transactions and send the complete transactions out across the network to be included in blocks. In this instance, the behaviour of the incompletely signed transaction is similar to a transaction with a nLockTime in the future.

Another possibility is that the bitcoin client has been informed of the IP address of the oversight service that they are using, so the client sends the incompletely signed transaction direct to the overseer who, after suitable checks, signs it and distributes it or sends it back etc..

In the case that the overseer is a USB key, the incompletely signed transaction is sent to the USB device. It checks the transaction and displays the amount and the address to be credited to the user on its own display so that the user can check them. If the user approves then the USB key signs the transaction and sends the completed transaction back to the computer to send to the bitcoin p2p network. It seems likely that some extra USB-key-specific software needs to be installed on the computer to handle the communication between the bitcoin client and the USB key.


General Considerations
I think the system should not prefer any particular oversight service to any other. Anyone should be able to provide oversight service if they follow the protocol and any user should be able to subscribe to any oversight service.

The system should be able to be extensible to facilitate coins overseen by multiple overseers in which case the system should be able to facilitate situations in which both overseers are required to sign, and situations in which only one is required to sign.

If the overseer is a USB key, care has to be taken so that the bitcoin client does not have to concern itself with the details of transacting with the USB device.

In order to facilitate oversight services, bitcoind should be changed to enable the sending of transactions with explicit custom scriptPubKeys, possibly specified as a hexadecimal string encoding of the scriptPubKey contents.

ByteCoin

[Mike Hearn]

The out index is a neat idea, but if you aren't a full node (and most users won't run such nodes on their computers in future) it requires you to trust the connected node. That's an assumption Bitcoin tries hard to avoid.

There's no point having an overseer service without layering a naming service on top of Bitcoin. Addresses are opaque, and you probably get them via email, a web page, IM .... ie, via the compromised machine. It's not safe to use raw Bitcoin addresses obtained via an untrusted intermediary. For this reason the overseer must be given a human friendly name and the thing you verify (with secure hardware) must present that name to you, in such a way that the friendly name is always linked to the underlying Bitcoin address in an untouchable manner.

I'd suggest we start by re-examining the patch from genjix to support sending to named addresses. I don't think it's worth worrying about the details of how exactly keys are secured until there's a framework in place to handle address switcharoos.

[ben-abuya]

There's no point having an overseer service without layering a naming service on top of Bitcoin. Addresses are opaque, and you probably get them via email, a web page, IM .... ie, via the compromised machine. It's not safe to use raw Bitcoin addresses obtained via an untrusted intermediary. For this reason the overseer must be given a human friendly name and the thing you verify (with secure hardware) must present that name to you, in such a way that the friendly name is always linked to the underlying Bitcoin address in an untouchable manner.

I'd suggest we start by re-examining the patch from genjix to support sending to named addresses. I don't think it's worth worrying about the details of how exactly keys are secured until there's a framework in place to handle address switcharoos.

I agree with this. It's not as fun as trying to defend against root-kits, but probably way more significant for the average user. That said, I still don't get why people are saying you can just have a service without a secure device. Mike, your solution included a device with a screen and a button didn't it? Or are you referring to another solution you posted somewhere else? Gavin's plan called for something you'd get in the mail in case the service went out of business. The only way you can pass on the hardware device is either to trust your computer or to completely trust the online service. To me, completely trusting an online service with all your bitcoins kind of goes against what bitcoin is all about.

I also really like the idea of different kinds of bitcoin addresses. We're going to need this stuff for multi-signing and more advanced scripting.

[Mike Hearn]

You always need a second factor. Phone calls can work but I don't think they would be very convenient. Glancing at an attached device and pressing a button only takes a few seconds, assuming you have the device with you.

Note that unlike smart cards, these devices would not be customized per user. If yours is at home, you could just as easily use your friends.