Topic: Split private keys (Read 17309 times)

This method mame "publick key halving".

I would like to see if it is possible to resurrect this discussion to understand more about how split keys can be generated and used.

I have been working on a project called SEEDCARD - a bitcoin physical key card that is generated using partial private keys.

As i am not a coder, i have written a proposal that explains how the keys could be generated and used - heres a link to the website: https://seedcard.github.io/website/index.html and there you will find a link to the Code Brief page.

The ideas that were being discussed in this thread so many years ago have inspired me to search for a way to create something that was mentioned in the Satoshi's whitepaper. I believe that there could be a decentralised way to create wallets. These wallets could be used like cash to make off-chain transactions that solve the scaling problem.

Curious to see what happens!

This is the part I'm fixating on right now.  I assume this is done by Device 2 in order to obfuscate it's private key from Device 1.  Can someone provide an example of an equation that would do this?

EDIT: Gavin, I also assume you made a typo at the end of your sentence and meant Device 1's private key instead of public key.

You're obviously already beyond my skill level. I'm sorry, but I can't help more.  But I don't believe that this particular idea ever got much traction.

Yes, but my intent is different, so I just wanted to verify this specific part of the equation.  Can Computer A and Computer B generate a shared public key with their respective private keys, without compromising the shared private key?  Is the main security problem only when the shared private key actually needs to be used?

Um, no not quite.  What Gavin was talking about here is a form of two factor authentication, as applied to how the bitcoin system works.  Roughly what is being suggested is that one device is creating the transaction according to what it knows about the spender's wallet.dat file, less the private keys that go with the addresses that contain value; and the second device's job is simply to securely hold the private keys, and sign the transaction with the correct keys when presented with a verifiable transaction and proper authorizasion from a human being.  But the second device does not have access to the transaction inputs in the wallet.dat file, and therefore couldn't create a valid transaction on it's own.

Actually, that's not quite right.  What I've described above is a split wallet.dat system, which can be done now; but what Gavin is suggesting is the development of a new kind of address that, even if the second device is compromised and the private keys stolen, the funds cannot be moved without access to the first device.  Currently, a split wallet.dat system is employed by a couple of light android clients (such as Mycelium) to permit a server to hold the wallet.dat while the actual private keys are kept on the android phone.  When the user, from the android phone, initiates a transaction; the server creates the transaction and then sends it to the device for signing by the user's phone.  This protects the user's funds both from a hacker tricking the server into thinking that they are the user's phone and from similar server ended theft/fraud, but the user's funds are still at risk if the phone is stolen.  'Split addresses' would permit two factor transaction signing, requiring both access to the user's phone, and another of the user's devices; so that the attacker would require both devices to agree.  This may not be useful for most people, since if someone is mugged of their phone they are likely mugged of any devices that they possess at the time.  But the second device could be as simple as a bluetooth only device that must be within range of the cell phone, with a keypad to enter a code upon POS.  Or it could be the user's home pc, that can be set to remain open (within limits, say a max BTC per day rule) for a full day or week, so that if the user's phone is stolen, the amount at risk is limited to what can be taken before the home PC client can be stopped.  Either device could be backed up as well.

Bringing this back from the dead for something slightly related I am brain-storming.  If I understand this correctly, two separate devices can generate a ECDSA public key without ever knowing the full private key.  The security problem arises when one needs to actually utilize the private key, correct?

Sounds like he and I came to the same conclusions, he just beat me by a month or two.

I really need to start hanging out on IRC.

If I remember correctly, ArtForz is already working on a secure key storage and signing device. I'll see if I can find a chat log.

Found it: http://bitcoinstats.com/irc/bitcoin-dev/logs/2011/05/05/20#l485685

This is definitely a topic for lawyers, but you don't really have to transmit anything. Customer wants to pay $100 electric bill. His client generates an unsigned transaction and sends to vault service. Vault service partially signs transaction and sends back to client. Client has secure device complete the signature and client broadcasts fully signed transaction to the network. I guess the only thing the regulators could say here is that the service has the ability to block transactions, so it should be required to do so under AML regulations.

Another thing is there's no need to open this kind of service in the US. There's a much smaller degree of trust required than a regular bank, and it might be a lot harder for the US to strong-arm other countries into regulating this. I definitely wouldn't call it anything with the word "Bank" in it. In some countries it's even illegal to call a company a bank if it's not regulated as a bank.

Just as an example, some definitions in the Michigan Money Transmission Services Act:


Seems not to include bitcoin.


No selling or issuing of any payment instruments is done by the security service. It's possible you could mangle the meaning of "issuing payment instruments", but see below.


"transmission or payment of money" -- according to (b), bitcoin may not be defined as money, and therefore no payment instruments could ensue.

That's a BitBank more or less, and unfortunately I doubt you could avoid being regulated as a money services business because you'd still be a "money transmitter". You probably could avoid being regulated as a fully blown bank though.

Being regulates as a money transmitter means following AML regulations, basically, doing KYC in order to open an account and trying to report "suspicious transactions". There are some other rules in there as well.

Is this regarding the discussion about saving previous relevant transactions on the secure device? If so, it's a good point

As for the hardware design, I'm starting to think this is the wrong place to get into it. People can hack their own MP3 players and do cool DIY projects, but if we're talking about something that's intended for mainstream use I think you'd need to form a real company to get this moving.

Imagine starting a company that implements Gavin's idea. The company doesn't have ownership over your bitcoins, but helps regular people transact securely on a day-to-day basis. This company would bring in hardware engineers, talk to smart card manufacturers, and negotiate bulk pricing for them. To open an account, you'd ask for a couple of devices or smart cards to be sent to you in the mail. Eventually, you'd be able to buy them at Walmart and 7-eleven. Once you have your devices, you put one away in a safe deposit box and forget about it, and use the other one to do secure payments. The company could make a lot of money on a monthly or annual storage fee. Since the company has to know the bitcoin addresses it's securing, it could just look in the block chain to see how much you've got in them, and take a small cut.

It's cool because it's like opening a bank but without the regulatory bs, and you're not really responsible for everybody's money. Advanced users probably won't need the service at all, and the company can sell them the hardware to secure their coins themselves.

OK. For a lightweight client, check out BitCoinJ which implements this mode already. There's no need to duplicate work.

I've investigated smartcards before. Finding cards that can do ECDSA is difficult. Also, readers that have a display and pinpad can be quite expensive (reusing the ones banks issue isn't as easy as I'd hoped).

Ideally the smartcard reader device is smart enough to do internet connectivity (perhaps tunnelled through the host), because - again - Bitcoin addresses/pubkeys are opaque. You need assurance that the address you see is  owned by the counterparty you think it's owned by. We covered this before. Having a display isn't enough. The display needs to display something human readable. In my proposal, the BitBank provided another service beyond hosting keys: verifying that the public key in question was really owned by some human readable string like a business name or email address. In a pure card based design there's no such external trusted observer. Instead I suppose you could try to re-use the existing SSL PKI and have the reader understand how to verify a signature over a new pubkey using the organizational pubkey embedded into a SSL cert.

I think the right tradeoff is not to have the card sign the transactions (this requires a powerful and expensive card) but rather, have the card hold the keys and release them in the clear to a device that can provide the correct PIN. The device itself then takes an unsigned transaction created by the host, fills out the scriptSigs and hands the signed transaction back.

So there'd be three levels of trust: the untrusted host device knows your balance and can build transactions. The dedicated device signs them. The card holds the keys.

There would need to also be an ability to export an encrypted backup because people probably won't want to store all their value in a card that can easily break, be lost, be stolen, etc.

listening.

Yeah, those are very good points. The compromised computer can already know that the bitcoin addresses you're sending from belong to the same account and that they belong to you (if the computer has any additional information about you). This could be an issue, and should probably be addressed by any scheme that purports to be secure. The only added amount of data it could glean from you requesting previous transactions for bitcoin addresses is that it could infer that you own bitcoin addresses that you may not end up using in the send transactions.

I don't think this is correct.

• You have the following 4 items: the private key (A), the public key (B), its associated hash (C) and finally the associated bitcoin address (D), which is base58encode( hash (C) + checksum). (D) is only invented so that the hash (C) is human friendly.
• If you know (C), you can calculate (D) and vice-versa. But is it not possible to calculate the public key (B) from (C) or (D).
• Initially to receive coins, you reveal your bitcoin address (D).
• If you send coins to it, a standard transaction is made to (C) (Humans do not really need to read the raw blockchain). Output from it can be claimed if you can sign the transaction.

So up to the point where you only receive coins, you never have to reveal your public key (B).

But if you want to spend any of them, you will have to reveal your public key to everybody. Otherwise is it not possible for anyone to check to see if your signature is correct.
That is why 2 checks are made when you claim a transaction: first the supplied public key is checked that it hashes to (C) (so that you cannot claim the coins using another public key), and afterwards the signature is checked using the supplied public key.

In fact, revealing your public key shouldn't make things more insecure. But it was probably added as an extra security layer: once you have to reveal the public key (=to spend some coins), you can spend all coins of that bitcoin address and send the change to a new bitcoin address with unrevealed public key. To get to your bitcoins, one must first find a public key that hashes to your bitcoin address (quite impossible already) and then use that to find the associated private key (again at the moment quite impossible).

The only reason I can think of that you wouldn't want an untrusted client preparing the unsigned transaction for you is that you don't want to divulge any of your public keys that are holding money. But that means that if you receive money away from your trusted machine, you won't be able to spend that money. I think a combination makes sense. You can download a cache of your current transactions at home. When on the road, if these transactions can cover the bill, you don't need to divulge any public keys. Otherwise you have the choice of divulging public keys to the client to check for new incoming transactions until you can cover the bill.


Looking forward to it

I've been reading this topic with great interest, as I already proposed something similar a few months ago (a smartcard-like device to use as payment in stores instead of a full bitcoin client on some fancy smartphone).

I've been working on this idea and this is what I have in mind:

• a lightweight client (A);
• a smartcard device (B) with display and button(s);
• a GUI software (C).

It can support a variety of configurations like the secure storage of wallet keys (like the discussion in this topic) or paying at your favourite store, just to name two.
Still need to develop a lot (only part A partially done), but because of this discussion, I'll release the "lightweight" client very soon (still working out some final details, then it's ready for first release/test), so that perhaps other people can build on top of that.

Why a lightweight client ?
Everybody talks about "in the future people won't be using a full bitcoin client", and I agree with that: the full client is only useful for people actively supporting the p2p network (mining, big bitcoin user, ...). "Normal" people only need a (very) small part of the blockchain to be able to use bitcoins.
So the client I'm developping will connect to the bitcoin network (at the moment only to one node) to do only 1 thing: download the blockchain, inspect it and store only relevant data. In "private" or "extra-light" mode, it will only store open transactions of a (small) list of bitcoin addresses (=the few user's bitcoin addresses). In "store" or "light" mode, it will story all open transactions (to be used by a store/website that will accept payments in bitcoin, or some power-users wanting to have all relevant data of the blockchain).
It stores this data in a database (I choose MySql) so that any other program/script/web page can easily access this data. In extra-light mode, as only a few transactions need to be stored, a much easier storage (like plain text or CSV format) can be used (so it could be compiled for smartphone platforms more easily).

The GUI software (C) will act as the interface between the smartcard and the client (A): it will manage the smartcard and will send unsigned transactions to the smartcard and signed transaction to the client. (C) could be a small program running on a PC/checkout desk at the local store where a customer can insert his smartcard into a reader to pay for some goods. But it could also be a webpage of an online store.

In a bigger store, the actual implementation could be: 1 server hosts the lightweight client (A) + database and at each checkout software (C) is installed and used to process payments (which will query the database on the server, and send transactions to (A)).

The smartcard (B) is the key part making everything secure: it has a fixed software on it (you can't hack into it and install some other software to read out the RAM containing the private keys) that can generate/load keypairs and sign a transaction sent to it (so it never needs to reveal the private keys when inserted into a unknown PC/terminal).
As said elsewhere, we cannot trust that what we actually see on the display of the checkout terminal/PC is that what is asked to sign, so it will have to have a display and one or more buttons to confirm/cancel the transaction (or loading of new keypairs, ...). This will also prevent abuse of the smartcard when the PC of a local user is infected.

I'll release the link to my website as soon as the lightweight client is ready for testing.

If the device does all of the wallet stuff itself, you can take it on the road.

I want this thing to be my wallet.  Not a glorified dongle that allows me access to the wallet stored on my PC.

Yes, the private keys are stored only on the secure device, but that wasn't my question. My question was, if the client can create the required unsigned transaction, which requires nothing more than knowledge of the public block chain, why does the secure device need any more data than just that unsigned transaction, which it then signs. Everything but the actual transaction signature is public knowledge, the only thing the device needs is the transaction itself, so that it can properly sign it. It does not need to know all other unrelated transactions that I've done in the past, and it has no way of knowing whether to trust them anyway.

Your real wallet is in the device.  The PC on your desk can keep a copy of the public keys so that it can show you your current balance as a convenience, but that's it.  When you want to pay, it sends the destination address and the amount, only.  The device then creates the transaction all by itself, using transaction records it already knows.


Encrypting the whole thing would certainly work, but it is probably overkill.  You can't just encrypt the data using the keys themselves, or you provide the attacker with a whole lot of known plaintext to degrade your key with.  Most encrypted streams exchange session keys and do a whole lot of crap behind the scenes, and we would have to do all of that ourselves, all to protect stuff that doesn't really need to be protected.

Simple hashing seems sufficient.  At least for now.  Eventually, sure, we'll probably want the serial communication to be encrypted.  But for the first step, I'd like to be able to debug the thing with a 'scope.

But if you're getting the unsigned transaction, that will include the proper inputs. I'm not sure why you'd need all the previous transactions. The idea is that we don't assume anybody is honest. The secure device makes sure we're never doing anything except sending the displayed amount to the displayed address. It's impossible to do anything else with that signed transaction no matter what you feed the secure device.


I'm probably missing something here. If we know the secure computer or device's public key and encrypt the whole JSON response with that key, what else do we have to worry about? In any case, all information being sent here is in the public block chain anyway so I'm not sure if there's a point encrypting it.

The secure device needs copies of all blocks involving keys that it contains, so that it can generate new transactions later.  It would use this request to ask for them.  As an aside, the secure device should only make this request upon a command from the user.  That way you can plug into your home box, which is probably honest, and update your information, but when you plug it into a retail POS, you don't give it the chance to give you bogus data.


Unless the tiny spec I read was missing something, there was no way in JSON to authenticate, that detail being left up to the layer below.  Since there is no layer below when using serial, either we make one, or we use digests to authenticate commands.

My first guess is that there is nothing in any of these commands or responses that needs to be kept secret, but a few things that we would like to have authenticated.

acceptPublicKey, balance calculations -- I like that!

getPublicKeyTransactions -- why do we need that?

getPaymentRequest, returnPaymentRequest -- yep these are exactly what's needed to enable use with secure devices. browsing through the code shows that the relevant code that has to be split out is all in a critical block. the signed transaction will have to be checked for viability once it's imported back into the client.

Another thing you'd want to be able to do is test the private key signing without actually doing a transaction.


Why do we need in-band authentication? Why not just encrypt the JSON with the secure device's public key? I think it's best to use established secure protocols like TLS if at all possible.

While I was driving today, I had some thoughts on what exactly was needed to get my hardware wallet project talking to the client.  Might work for other types of smartcards projects too.

I also had the bright idea of letting the client act as a stand in for a hardware wallet.

Step 1.  Add some new methods to the JSON RPC API.  I think I can get by with just 4, but I may have missed something.  acceptPublicKey tells a node to add a new public key and include it in balance calculations.  getPublicKeyTransactions tells a node to return all transactions involving a given public key.  getPaymentRequest tells the node to give it any pending payment requests.  returnPaymentRequest returns the signed transaction to the node.

Step 2.  Add UI/config file support for these calls.  A set of options to specify a remote JSON server to connect to as a client.  An option to tell the client NOT to generate keys.  A checkbox on the payment page to tell the node to queue up the amount/address pair for delivery to an external device in response to a getPaymentRequest RPC call.  A button to tell the client to ask the other server for transaction requests.  A dialog to display and request confirmation/deletion of queued requests.

At this point, you could have two computers running bitcoin.  One on your main box that has no keys and is unable to send any coins by itself, and a second box that does not connect to the network ever, but only talks RPC to the first box.  All keys are on the second box, so all payments must be relayed through the JSON RPC service from the first box to the second.

Since the second box is on the network too (or it wouldn't be able to talk to the first box), won't it get infested too?  Yup, and that brings up...

Step 3.  Implement JSON over serial.  Could be actual serial, could be serial over bluetooth, could be serial over USB, could be a terminal program on each box with the super paranoid user relaying commands back and forth by retyping them.  I think we would need to extend the JSON spec, since it doesn't seem to contain any provisions for in-band authentication, and we won't have access to the HTTP layer doing it for us.  I propose that each string be followed by a hash of the command + password.

Step 4.  Implement a security system that allows the developers (or the use, I suppose) to allow/disallow certain RPC to come in from or go out to certain interfaces.

Step 5.  Build hardware that talks this protocol over various forms of serial.

I think that this approach has a bunch of advantages.  First, it allows everyone with a junk box sitting around the ability to set up a secure offline wallet without needing any special hardware.  Second, it allows debugging to take place on computers which have excellent debugging tools, at least initially.  And when we get to the step where we are working with hardware, we will have a protocol to target that is known to work.

Ok, that's the missing piece. I think that's a pretty good option for Gavin's challenge. I'm not that familiar with Google or Facebook 2-factor authentication, but if people become comfortable using it via a mobile phone or smartphone and these cheap little devices become easily available, that would be a really nice system.

I still like the idea of a secure usb device that obviates the need for the online service. It's a tradeoff of trust of a 3rd party service against the responsibility of securing your physical keys.


I never really expected that of the scheme. Most people don't have incredibly sophisticated keylogging, memory-reading root-kits on their computers and teams of hackers standing by to analyze the data collected from them. As long as your money is safe I think that's pretty reasonable for the average joe.

You can just leverage Google or Facebook authentication if you want 2-factor on signin. That's a 2 hour job for any BitBank.

You're right that it doesn't solve the case of an attacker who just wants to observe your bank statements and doesn't care about stealing your coins. I don't think anyone has ever solved that one, without assuming the web access device is trusted.

How do you sign in to the online service? If you use a pass phrase there could be a keylogger. This doesn't sound like 2-factor authentication, because your device doesn't authenticate you. So it solves the trust problem (you know the transaction is legit), but a hacker could steal your identity and pretend he's you.

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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?


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


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.

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.

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


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.

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.

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.

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.

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.

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.

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.

This sounds a lot like threshold cryptography combined with distributed key generation.

There have been a few papers written on using RSA to achieve the same result, but I'm unaware of this being done with elliptic curves. However, I'm not a cryptographer.

As a sidenote, splitting a private key in this fashion could be used to construct a simple contract without needing a trusted third party. Two individuals could generate a split private key, and then sign a pure function that would perform some prearranged task; by signing the function, it would be tied to a bitcoin account and essentially act as a fund manager. Bitcoin miners could then run this pure function (passing into it the current block data as an argument) as part of the block chain verification process.

Here's a use case I'd like to work:

I tell Bitcoin running on my computer or cell phone to run transactions through a bitcoin security service-- maybe I give it a https:// URL for the service.

I tell the security service "auto-approve small-value transactions, but give me a call for any transactions above $X (or $XY per day)."

The security service sends me something in the mail that I keep safe, but that I can use to recover use of my bitcoins in case the security service goes out of business or disappears or I decide to stop paying for the service.

I get bitcoin addresses either from my bitcoin client (not trustworthy!) and/or from the security service that require both my computer and the security service to sign to spend.  And I have people send bitcoins (or I self-send my own bitcoins) to those addresses.

Spending coins is done as usual-- I type in an amount and an address.  Behind the scenes, magic happens, and if the transaction is greater than $X I get a phone call -- "Press 1 to confirm payment of $X bitcoins to bitcoin address blah, press 2 to cancel."

If I suddenly get random phone calls, I know my computer has been infected.

There are a number of possible solutions to this problem. The best solution from a technical point of view would involve an implementation of the paper I referred to earlier.

I gather that you are willing to make changes to the bitcoin client software to enable users to opt into some scheme whereby they are protected even if their computer is compromised.

If the computer running the bitcoin client is rootkitted then strictly, it's impossible to trust anything the computer displays or limit what it sends or ensure the security of any information you input. Practically, there are limits to the complexity of software which anyone is willing to develop for a rootkit and so some use of the computer may be possible.

Possible solutions are:

1) Facilitating the use of an offline secure computer to hold the private key and generate transactions. In this case the engineering effort goes towards implementing an efficient secure communication probably involving copying alphanumeric strings between the two computers. The user has to have another computer and be able securely to install the client.

2) Facilitating the use of a third-party website the approval of which (indicated by quoting an ECDS) would be required before transactions of the client could succeed. In this case, the unapproved transaction generated by the client is sent to the website, the website displays what the transaction would accomplish in some hard-to-spoof fashion and the user approves of the transaction via some hard-to-brute-force pre-arranged password or other such token. The website then signs and either passes the transaction back or sends the transaction onto the network itself. This is a solution which requires multisignatures to be enabled.

There are other solutions, none of them easy or nice.

It would be helpful if you could come up with some use-cases for the private key splitting. What ideally would you like the user experience to be? What degree of deviation and increased complexity from the normal transaction process do you imagine will be tolerable? Is this solution intended to be suitable for crypto-ignorant non technical users of bitcoin?

ByteCoin

The Ironkey also does RSA, it can be thought of as several devices in one, flash, smart card reader, smart card, all off a single USB bus.

The scenario we discuss here though doesn't require the flash component though it is of course interesting for other reasons.

As for the trusted input problem there are a few solutions, it depends on how deep you want to go to solve it.

To protect against user mode key l loggers in windows you can use the session 0 ui to collect the pin, only kernel malware would get past that.

You could use a secure PED (hard to do in a decentralized system)

You can use graphical pins, random layout (kind of like captchas)

There are a ton, first step IMHO is getting the keys off the host

Me too, and this is a likely attack in my opinion.

To protect against this attack one needs the keys to be in a crypto processor of some sort, and the ability to do some flavor of trusted pin presentment.

Though this would mitigate the risks significantly we would also want to have a recovery story in the event of token loss and theft.

Thanks, I'm a bit obsessed with that idea


I just checked the code again and I'm pretty sure it is a threshold scheme. nSigsCount is the threshold and nKeysCount is the total number of keys. Yes, it would have to be used by the sender of the coins to you. So, either you send yourself transactions like this, or you ask the person paying you to do a transaction like that. This could be as simple as giving them a different version of the bitcoin address that has a few type bits in it and a bunch of concatenated public keys. It would look like a regular address, just longer. You wouldn't even have to specify you want a special transaction, it would be implicit in the address.


Not if the rootkit has a keylogger in it. Also, it's better if the attacker doesn't get the encrypted wallet, because then the problem is reduced to how good your pass phrase is.

An encrypted wallet could protect a user completely compromised by a root-kit trojan.  I don't see how cutting and pasting an encrypted wallet over to a service (dropbox) or device (android phone) is any different than splitting keys.

The dead man's switch is a nice idea. 

Regarding script.cpp, I just checked if the opcode is there and not the logic. It looked to me that this is not a threshold scheme but a "you must present two signatures" scheme - so that's why I wrote about "increasing risk of loss". Moreover, wouldn't it also have to be used by the sender of the coins?!

Right, so by definition they don't have their wallet on the computer. IronKey has built in AES encryption. Imagine a smartcard or usb drive that had built in ECDSA encryption. The device could generate and store private keys and sign bitcoin transactions, but would be designed to never allow access to the private keys. The client just sends the unsigned transaction to the device and gets back the signed transaction.

This still has an weakness though. A rootkit could send the drive a transaction for your entire balance and have it sign it. So you need a screen on the drive that shows the amount and recipient address, and a physical confirm button.

The risk profile I care about is:

User's computer is completely compromised by a root-kit trojan, but they don't know it.

However, the user has access to some other device or service that they have setup in advance to be a "second line of defense" to prevent their entire wallet from being stolen.

I agree regarding risk profiles.

I known the iron key guys, it's a good product and the team they have is good but it's expensive and doesn't support ECC or at least it did not last year and I highly doubt it supports the curve bitcoin uses.

I think it would be possible to get the interesting scenarios to work on a cheap 10 device, initial probably being around 40 due to volume issues, the form factor doesn't need to be a card there are lots of USB dongles.

It really depends on how much money you're talking about. Split keys and dead man's switch don't really make sense for a few hundred bucks worth. But if you have $100,000 in bitcoin, do you really want to bet it all on one smartcard? We need to come up with different approaches for different risk profiles. Certainly, making it really simple to securely store $500 is very important.

I think a device like IronKey but with the ability to sign a bitcoin transaction would be great for this. It could be a smartcard too, but not everybody has a smartcard reader these days. I'm looking forward to bitcoin keyboards with a built-in smartcard reader. They could have a hardware override so that the keyboard stops sending input to the computer and is only used for unlocking the smartcard.

I have worked on systems that utilize key splitting in the past, though not with ECC.

I like key splitting but thought it might be worthwhile to play devils advocate and see where it takes us.

Usability of these systems are typically poor (complex and failure prone) but the nature of the systems that use this approach it's not been a problem, for Bitcoin I think it can be.

If the goal is to protect the key from compromise we might want to enumerate the threats we hope to mitigate, for example if it's the Trojan cases then the code that can steal one key could likely steal all keys.

Process and privlige separation helps address the key compromise cases, this can be done in a few ways for a software only solution you can imagine an authenticated service and a LPC or maybe one where crypto happens on a phone vs on the pc.

Another more common design pattern would be to move crypto to a smart card and have cards clone the crypto to a backup card to deal with the loss issue.

Well script.cpp is the core. It's completely integrated into bitcoin, it's just not in the default GUI. Before putting it into the GUI I'd add support to the RPC. I don't understand why this increases the risk of loss. If you only need 2 out of 5 keys, you can lose three of them and still be able to access your account. You can even do 1 out of 5 if you're worried about that and less worried about theft.


Well there's always a tradeoff between loss and theft. If you're worried about loss but not theft you'd want 1 out of n where n is big. If you're worried about theft and not loss you'd want n out of n. You're usually worried about both so you compromise and choose m out of n  somewhere in the middle.

I think a complimentary technique is to use a dead man's switch, so that in the case of loss Bitcoin will transfer your funds to another account after say 30 days. This is also already built into bitcoin scripting. That way you can focus less on loss and more about theft in your crypto protocol.

Thank you for pointing this out. I checked this in the code. With the exception of script.cpp and script.h it is not used. Especially, it si not part of the GUI.

Guess we should make it available ASAP.

Still it is only part of the solution. It increases the risc of loss. Now you should not lose TWO things. Before that, you whould not lose ONE thing.


Ok. Then replace "secure device" in my sentence by "usb drives/smartcards/whatever".

There is a thing which holds your key. This thing gets broken - you lose your money. You copy this thing - you increase your risc of having it stolen and you have to redo the copy every time you generate new keys.

The solution I am contemplating takes care of BOTH aspects.

You cannot be compromised so easily, because you need more than one device to access your money.

You do not increase your risk of loss, because you "things" are replaceable.

With the suggest form of secret sharing you get both advantages for one price. 

See here: https://en.bitcoin.it/wiki/Contracts (CHECKMULTISIGVERIFY)


Agreed, just have to make sure that key renewal really is a lot more convenient.


The secure device holds no data, it's just used to generate keys and write them to the usb drives/smarcards/whatever. It's also used to sign transactions based on the keys on the usb drives/smartcards. If it gets lost, stolen or broken, you just get a new one.

I think this article http://www.paulgraham.com/softwarepatents.html gives good reasoning on why it is safe for us (and pretty much everyone) to ignore patents:

I am trying to work that out right now.

The idea is, that the account holder also has access to a majority of devices holding the shares. So, the account holder would press the "redistribute secret" button on all the devices he has access to, and the devices would generate and distribute new shares using a suitable protocol. Those devices which are not present at that moment, would not get their new share, and their old share would, from that moment on, be useless.

It is probably easier (but less secure) to have a single trusted device redistribute the secret.

To my knowledge there are no open source tools which do that. So it would be a matter of implementing and having it subjected to peer and community reviewing. The good part is, that it does not affect Bitcoin at all and would be a seperate piece of software, using the RPC API of bitcoin.


Is this multiple signature feature for m of n or is it rather for 2 of 2. What I saw in the code was rather a 2 of 2 kind of scheme - and I did nto check if it is really turned on or just in the code but disabled.

Getting the coins to a new address with keys is certainly possible and fun for the freak, for the John Doe user it is a no-go. Just compare: This new fine leather wallet is secure. You just have to move your coins into a different one every other day!


I agreed with that until yesterday. 

Imagine you lose the secure device. Or drop it. Or your cat pees on it. Your son runs his bike over it. There goes the access to all your bitcoins.   

I agree that the threshold scheme is important. How would proactive sharing work in the context of bitcoin? Who decides that shares are renewed? It will be interesting to see if there are established open source tools that give us threshold, proactive sharing and verifiability. However, proactive sharing and verifiability are slightly less important with Bitcoin. I understand that Bitcoin already supports an m of n scheme for signatures. Any individual key can easily be verified in the usual way and a renewal can be accomplished by getting keys together and transferring to a new address with new keys. The cryptographic version sounds more elegant, though.

I don't know if pluggable pc's are the best solution. I wouldn't want the keys being read on any machine that was connected to the net. I think the best safe solution is to create an unsigned transaction on your regular computer, write it to a usb drive, sign it on a secure device that has no connectivity but can show the amount sent and address sent to, and then send it via the regular computer. The secure device would also not have any persistent storage. Keys would be stored on additional usb drives.

Gavin, I looked at the papers Bytecoin cited, to see if it is worth effort implementing this.

Especially the first paper is very intersting. I agree that it should be possible to adapt the two zero knowledge proof parts from the Paillier crypto system (for which the paper gives a solution) to elliptic. Moreover, it probably involves quite a bit of thinking and implementing; it's not really as straight forward as it may seem.

Therefore, I spent a few hours analyzing the situation. I think that splitting private keys in the form you describe in your first post is the right direction but not really what we want. Let me first outline some problems I see with your approach and then provide an amendment to your thoughts.

Risk of loss: Suppose, we lose one of the two devices. Then we have lost our money, since we no longer can form the requested signature. Thus, while we gain more security against attackers, the burden on backup gets higher: We now have to backup two devices and we should do this after every generation of new keys. Lose your laptop, drop you mobile on the floor: Your money is gone. Two devices - double risk.

Burden of key-splitting: Every time we generate a new key, the two devices must synchronize, for the scheme to work. So: When generating a new bitcoin address, I need a new PAIR of private keys, which requires an activity on both devices. If you only have one device with you on generation time, you have got bad luck.

Usability: Looks like I always have to have both devices on me when using Bitcoin. Sometimes I will not. So I might end up having some small cash on some addresses which are only on one device. Or the other. And only the addresses with the big money are secured by secret splitting. Which may lead to user confusion and a hassle when trying to get the devices synchronized.

Mobility: Right now, BTC is a desktop application. It will become a mobile application. Fine. So will i need two mobile devices in that scheme, when I am having my beer in bitcoin bar? One could be a mobile phone. And the second? Smartcard? USB token? Second phone? How useful are two devices for a mobile solution?


Currently, I see two ways out of most problems: A cryptographical one (using a different crypto scheme) and an operational one.

Cryptographical idea: We do not want private key splitting, we want more. We want a threshold scheme with proactive sharing (and, if possible, verifiability). This means:

Threshold: We split keys not into two but into a larger number. For example: Five. (Desktop PC at work, desktop PC at home, mobile phone, smart card, USB token). We impose a threshold. For example: Two devices together can produce a valid signature. This solves the backup issue. Lose one device, you still have four left. I think, this threshold concept if a major improvement of the backup situation.

We have to modify the life-cycle of the keys, of course, to solve the other issues mentioned above. No small pools any longer, but 1.000 keys or more which are generated at the beginning. So we do not have to distribute fresh key shares so often.

Proactive sharing comes into the game, when we lose one of the devices. In this case, we want to disable the keys as fast as possible (before the attacker manages to steal a second of our devices). Proactive secret sharing allows us to redistribute the shares in such a manner, that compromised shares lose their value for the attacker.

Verifiability comes into the game, when one of devices is not lost but compromised or defective. It allows the other sharing participants to check if a sharing participant lies about his share (but, of course, without learning anything about the share).

For elliptic crypto and DSA, there exist threshold based signature schemes. I am currently researching, if there are proactive schemes (I assume, yes) or verifiable schemes (I do not know).

This concept should work without touching anything on Bitcoin crypto - we only add a wallet client.

Organizational idea: We do not split at the wallet private key level, but at the level of the user.

Our wallet is handled by a secure and trustworthy organization or node. We tell that organization or node using secret splitting schemes as outlined above, when they are supposed to use the wallet keys on our behalf. The node might be a pluggable PC such as openplug.org running out of my home (with a backup of the keys stored somewhere). The activating devices then are a smartcard to be put into any card reader and a mobile phone. These two devices would not have to use Bitcoin elliptic crypto but just ANY existing key sharing scheme (which is much easier to do). Again, Bitcoin client does not have to be modified.

The advantage here is: When I lose one of the devices, I do not lose my bitcoins. Not only the attacker has no advantage, I have no damage in case of a loss. It is easy to get a new mobile and place it in synch with the second device and the trusted node.

Those who do not want to buy a pluggable PC can delegate this to an authority they trust. (I admit, this is not completely satisfactory. So, rather, have your own pluggable PC).



Would be great to get a bit of feedback on these thoughts.

Thanx.

Very interesting paper.

And the method is patented or patent pending  http://www.freepatentsonline.com/20030059041.pdf

Zero-knowledge proofs... ummm....

Nice to know it can be done securely. I'll leave it to the professionals to actually do it.

I have found an article Two-Party Generation of DSA Signatures by Philip D. Mackenzie and Michael K. Reiter which looks very promising.

At first glance, adapting the scheme to ECDSA should not be troublesome but implementing it is likely to involve a substantial amount of work. It is, however, vastly simpler than trying to do it using a generic MPC scheme.

This should be exactly what you need Gavin.

Everyone else should note that implementing this would not involve any changes to the Bitcoin system.

It's also worth reading Secure Distributed Key Generation for Discrete-Log Based Cryptosystems by Rosario Gennaro, Stanis law Jarecki , Hugo Krawczyk and Tal Rabin

ByteCoin

RE: pulling the wallet private key encryption ASAP:  Agreed 100%

I wanted to start discussing split keys now because if we need a new standard transaction type then it is best to do that in stages-- let clients relay, and miners include in blocks, the new transaction type.  Then once most of the network will accept the new transactions, people can actually start USING them.

Two-factor authentication on multiple devices is fine for down the line, but we really need a good solution to encrypt the private components of our ECDSA keypairs right now.  I would implement that PULL as soon as possible (with appropriate modifications) and then move onto additional changes.  Hashing the private keys with a good algorithm will make the standard attack vector of "look for a wallet.dat, send it home" much harder.  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.

As an anecdote, I consider myself a pretty savvy PC user.  Still, back when I was using Windows as a primary OS, I did get a virus once from a shady torrent.  Within a day I immediately realized things were off and completely re-formatted my PC.  Now, pretending that Bitcoin existed back then, encryption of the private key component would've been the difference between me losing all of my bitcoins and not.

Paypal used to (dont know if they still do) give out a free RSA fob with each new account. I think they later started charging for them but the price was miniscal. WoW I believe uses the same system.

Because sending to a multiple-signature-required address requires a new standard transaction type, a new type of bitcoin address, and a protocol for Device 1 <-> Device 2 communication. More code means more possibility of bugs, so I was hoping there is a simpler solution.

And as I said in the original post, I wanted to start discussion:If the answer is "multiple signatures" then so be it.

Yes, it will have a display.  I guess I didn't mention that, but it is absolutely essential.

It can either show the address, and ask for an amount.  Or it can show the address and amount, and ask for a Yes/No.

How will you ensure, that the 2.00 BTC which the hostile terminal shows you are about to pay isn't 450.00 BTC. Ie: How do you plan to deal with the hostile display issue? Will your device have its own screen?

I've been thinking about wallet security too.  I think a second device is a good idea, but I see it working in a different way.

I see a portable dedicated device with very limited communications ability.  Just a serial port will do, which probably means serial over USB or serial over bluetooth.  It will also have a SD card socket for wallet backups.

The device will generate the key pairs, and store them.  The private key never leaves the device, except on the SD card backup, which could be encrypted.

I think it only needs 3 hooks into the PC client software.

1) It needs to be able to push public keys to the client.
2) It needs to be able to ask for (and receive) balance updates from the client.
3) It needs to be able to accept an address from the client, and generate a complete transaction to that address using an amount entered on a keypad.  (Or possibly accept an address and amount, then only ask for confirmation.)

I think this could help with the retail problem too; no reason why you couldn't plug it into a potentially hostile terminal.

I'm thinking Arduino.  It should already have all of the crypto libraries necessary, plus hookups for serial, USB, BT, and SD cards.  Probably going to order some hardware this week to get started.

Since you aren't a cryptographer, why not just implement transactions with multiple signatures?

FYI: I posted this here on the forums because I see the mailing list as being for nuts-and-bolts "lets talk about exactly how to get XYZ done."

And I see these forums as a better place for brainstorming and pie-in-the-sky maybe-it-will-work-maybe-it-won't discussions.

Also, equations don't look pretty in plain-text emails.

Agree, that one should not change crypto light-heartedly. 

I understood the original suggestion as an additional option and possibility to be offered, just for testing.

Moreover: In my contribution yesterday late at night I demonstrated how the two devices can do a joint signature with both of their keys. However, I did a short security review and found a flaw in the scheme. My suggestion requires a communication from device 2 to device 1 and then another communication from device 1 to device 2. The second communication must be trusted otherwise the private key of device two can be compromised. Since Gavins idea was to split trust between two devices, this does not work:

Device 2 sends $d_2^{-1}z$ to device 1. This is secure, since $z$ is random. Device 1 generates $k^{-1}(d_2^{-1} z+d_1 r)$
 and sends to device 2. Device 2 then multiplies by $d_2$ and publishes the result.

Therefore anyone who is able to snoop into the second inter-device communication is able to reconstruct $d_2$. So the obvious attack vector is to compromise device 1 and the job then is done.


Why? Personally, I prefer it to be discussed in the forum, where there is better access, where there is generally better visability of the topic and more contribution by others and more transparency of the process.

Maybe better to discuss this on the mailing list?

Anything that involves significant changes to the crypto seems like a bad idea. Even if the equations are sound, it will be harder to convince others of the systems soundness.

Two-sig transactions are far easier to implement and prove correct. Given that the requisite mobile support doesn't exist yet, concerns about upgrade time don't seem like a big deal to me.

(subscribing, and doubtful about injecting cryptonovelties strait into Bitcoin)

If you allow two communications between the devices, couldn't it be done as follows:

Device 2 calculates d^-1₂z and sends this to Device 1.

Device 1 then calculates k^-1(d^-1₂z + d₁r) and sends to Device 2.

Device 2 multiplies by d₂ and has the result.

Generally i think the practice by people in the long run will have to involve a checking and a savings wallet, where best practice should be leaving no more than 500$ worth in the checking wallet.
That way, a wallet with more usability can be held, for mobile devices, "simple" password security and such. On the other side, due to the nature of bitcoin, a secure savings wallet should be promoted, using physically external security features such as a mobile auth app or a smartcard.
Once the development for such a second tier of defense is there, usage of such should be heavily promoted by bitcoin.org, after all users need to be protected from their own stupidity.

I presume it's also not acceptable for device 1 to be able to figure out device 2's part of the private key after viewing the completed signature.

I've looked into this already for a very similar application and initially I was hopeful too.

k is a random number provided by the first signer with the intention of preventing the recovery of the private key d by simple algebra. The second signer would need to incorporate their own random number into the "k" portion of the equation in order to prevent the first signer from deducing their d_B by analogous manipulation. However there doesn't seem to be a way of making a signature that behaves like ECDSA without revealing secret information.

Now it's Hal's chance to shine by showing how it's done!

You can probably create a multiparty signature but it would have to be verified by a different algorithm to the standard ECDSA and hence would be entering worryingly novel crypto territory. The benefit over multiparty signatures implemented in the script would be small.

I don't know much about secure multiparty computation but there may be a solution down that avenue but it would be a bit like using a sledgehammer to crack a nut.

ByteCoin

Gavin, not being a coder I might be treading way out of my depth here, but why go to all that length and deal with potential disastrous interactions between whatever happens in the mobile device and whatever happens on desktop (problem, bluetooth ? ), the results of which will amount to unhappy users and blame and whatnot, and not, say, implement HSM/smartcard support?

While I understand that the question of "dedicated hardware cryptographic devices vs. smartphones" is at least tangential to your post, methinks it is worthwhile to suggest that the developers look into the issue of whether capabilities of modern smartcard/HSMs are relevant to the goals of protecting wallets and can be used to implement a decent solution - IIRC there are "open source" smartcard solutions and affordable usb HSMs, and they aren't murderously expensive, and something tells me that it is not unlikely that dedicated cryptographic devices will offer more straightforward ways of securing wallet material than the (seemingly?   ) exotic approach you have outlined.

Anyone who has >2 000$ worth of coins in his wallet should be able to buy a motherloving smart card reader with the card, or a token, whatever class of hardware security devices you, the developers, will find easier/more practical to support.

So I've been thinking a lot about wallet security; Matt's password patch is a good first step, but maybe we can at least build in some infrastructure for a better solution.

We really need a solution where transactions are generated on one device and then verified on a second device, so malware must compromise both devices (e.g. computer and mobile phone, or web wallet and mobile phone) to steal coins.

gmaxwell from IRC thinks it can be done without multiple signatures (just with the standard transaction we have now), and staring at the ECDSA math on this wikipedia page I think he's right.  I believe he was inspired by ByteCoin's observation that you can create a vanity public key generating service that is secure-- the service can generate the public key but not know the private key.

I'm mostly writing this to convince myself it could work and to give ByteCoin and Hal and gmaxwell and anybody else who knows a whole lot more crypto than me a chance to poke holes in it. And then point me to a FIPS standard that has it all figured out already...

So:  generating an ECDSA keypair means choosing a private key d_A, then calculating the public key Q_A = d_AG (where G is a fixed point on the elliptic curve).

The key generation can be split; have device 1 choose d_A1 and device 2 choose d_A2.  Device 1 then sends Q_A1 to Device 2, and it can calculate Q_A1d_A2 = Q_A1*A2.  Or in english, Device 1 finds a public key on the curve.  Then Device 2 uses its part of the private key to do a bunch more elliptic curve multiplies to find the composite public key without ever knowing Device 1's public key.

So great, neither Device 1 or 2 needs to ever have both parts of the private key on them to generate the shared public key.

Now lets say Device 1 wants to spend a TxOut that is one of these split keys.  The key bit of the signature generation algorithm (see the Wikipedia page: http://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Signature_generation_algorithm ) is:
...
4. Calculate s = k^-1(z+rd_A)(mod n)
...
That can be rewritten as:

Calculate s = k^-1(z+rd_A1d_A2)(mod n)

And now I'm stuck.  Can that equation be refactored so that Device 1 can compute part of the signature, send its partial result to Device 2, and have Device 2 complete the signature (without Device 2 being able to figure out 1's part of the private key?)?