Topic: Idea for Highly Secure Paper Wallet - Using Split Keys (Read 4999 times)

The split keys described here are useful where you (the user) may be one of the attackers. In the traditional banking system, it is typical for institutional checking accounts to have 4 or more signing authorities, where at least 2 are required to authorize a transaction. Using the rules outlined in this thread, it is possible to build an electronic "checkbook" such that 2 of 4 keyholders are required to sign a Bitcoin transaction. The outputs would go to the payee and the next "check" in the checkbook. That is to say, each "check" would be single use (and sequentially numbered to facilitate that).

My concept assumes that this description is correct:

In my example, I want to set up a Bitcoin checkbook such that 2 of 4 signers are required to authorize a transaction. For each 'check­', each person will generate a new, unique private key: that I will designate A, B, C, D. BB code does not support nested formatting, and I want to write in English rather the pseudo-code. That is why I am making it clear here that A, B, C, D are different for each check.

For each check (of which an arbitrary number can be generated ahead of time):

• Generate a UNIQUE sequence number (stored in 'check')
• Each person generates a random, private key on their own machines (A, B. C, D)
• Each person computes their Public key: For example person 1 would; A*G = A'
  
• Each person shares their public key with every other person.
• Each pair of people generate a joint key:

   Person 1 Pairs with person 2: A*B'=(A*B)*G
    Person 1 Pairs with person 3: A*C'=(A*C)*G
    Person 1 Pairs with person 4: A*D'=(A*D)*G
    Person 2 Pairs with person 3: B*C'=(B*C)*G
    Person 2 Pairs with person 4: B*D'=(B*D)*G
    Person 3 Pairs with person 4: C*D'=(C*D)*G

• Each pair of people now sends their newly computed public key to every person not in their group..
• Each person encrypts their private key with the public key of every group for which they are not a member.
  
• Each of the results from the previous step are stored in the 'check'.
• The group generates a combined public key:

   Person 3 multiplies their private key with the public key of the first group: C*(A*B)*G=(A*B*C)*G
    Person 3 passes the result to person 4.
    Person 4 multiplies their private key with the previous result: D*(A*B*C)*G=(A*B*C*D)*G
    That result is stored in the 'check'
Edit: as a basic sanity check, Persons 1, 2 may want to do the same thing with the Person 3, 4 joint key. (and compare results)

To spend a 'check'

• A pair of people share their private keys
• They use their combined private key to decrypt the individual private keys encrypted with the combined public key
  
• They typically generate a transaction with two outputs:

   1. To the recipient of the payment
    2. To the next 'check' in the 'checkbook' (randomizing the order may be wise, but may not do much if this output is always larger).

Notes:

• Any participant can through malice or error hold all the funds ransom. I stopped trying to think of a work-around when I realized this applies to the two-person case as well. The parties should reasonably trust each other.
• If I am not mistaken, the data storage requirements grow factorially with the number of participants. Strictly for small groups.
  
• If you want to add or remove a signing authority, a new 'checkbook' must be generated. You would then spend the old 'checkbook' to the new one.
• Because of the complexity and lack of fail-safes, I recommend testing any implementations on testnet first.

Thanks for that. I was hoping you would make that tab useful for more than just the vanity pool idea. I think there's a number of interesting things split keys could be used for.

To generate a split key there is a new feature (v2.1) in the Vanity Wallet on bitaddress.org
It requires using two computers that are not compromised by the same hacker. For example using your computer at HOME and one at WORK.

Save the bitaddress.org HTML (get it from github) and check the SHA1 hash.

Open your saved bitaddress on your HOME computer and go to the Vanity Wallet tab. Click generate on Step 1. Print the page. We will call this key pair A (which consists of public key A and private key A). Copy and paste public key A into an email and send it to yourself at WORK.

Open your saved bitaddress on your WORK computer and go to the Vanity Wallet tab. Click generate on Step 1. Print the page. We will call this key pair B. Copy and paste public key B into an input box for Step 2. Then get public key A from the email you sent above and paste it into the other input box for Step 2.

Select Add and click Calculate Vanity Wallet. You will now have a secure Bitcoin address for saving.

When you later go to combine the private keys on one computer to get your coins out of savings then spend the whole balance (aka sweep) and don't use that same address anymore for savings. Consider it compromised.

You are describing how to generate a secure paper wallet on two compromised machines (that are not compromised by the same attacker).

May I ask what is the original purpose for that? If it was for the one paper wallet savings account that you occasionally withdraw from then, in order to sign the withdrawal transaction (which in your proposal is not a multisig), you are still faced with the problem of at least securely booting into a minimal OS (which you could then have used to the generate the paper wallet in the first place). Do I assume rightly that the purpose is to generate many split key paper wallets that you load up with small amounts, so when you come to use one of them then you empty it completely and never reload it?

I want to remark that even assuming that you can boot securely into a minimal OS (which I think you didn't want to assume) there is still a use of your proposed split key paper wallets as savings wallets. Because you can distribute the paper wallet into several locations and design it so that you need simultaneous access to N of these locations to be able to withdraw. Simply taking scissors and cutting a single key into N snippets would not work for N>2 because the key snippets would become too small and be brute-forceable.
  

On my vanitycoin.com website (which is not yet public) I generate the key pair in the browser from a user-id/pwd ("login key") and send the public key to my server. I generate whatever addresses you submit (1-1000 qty, w/ prefixes) and send the partial keys back to the browser. Then when you select "view results" it recombines the "login key" with each vanity key to give you the final key/address in various list formats for saving, eg. html,csv,sql,json. I've tested that all fully and it works well.

(My server code is all Python and the client JQuery / AJAX data handling. I should throw up a beta version but I need to sort out the IP + SSL stuff as it's too expensive on Amazon.)

There seems to be many possibilities and I haven't fully explored what things can be done along this lines but I'm pretty sure some pretty useful scenarios can be figured out.

I read in another thread that the same public key can be used to generate more than one private key using key addition.

This would allow for an advanced "split keys" commands section on the bitaddress paper wallet tab for the user to enter a public key. Then all paper wallets generated would output the summed bitcoin address and the partial private key. Therefore, I could conveniently create 1 key pair on my mobile phone (and backup to the cloud) and email the public key to my laptop and generate a secure paper wallet (printing two copies so one can be stored in a safety deposit box) based on that public key.

An alternate version of what I described above would use a brain wallet to generate the public key that would be added to the keys generated by the split key paper wallet. This essentially provides for paper wallet encryption WITHOUT AES!

Yes, that's right but also I was thinking of making a web site based off your code that makes it dead simple, and well explained, step-by-step, to do split keys. I even registered paperwallet.info for this purpose but I haven't got around to anything yet.

My main objective would be to re-arrange things to be simple for noobs and a bit more aesthetically pleasing. I'm still working out what to do. Not just creating a wallet but monitoring balance and doing spends too. So it's a paper wallet that has online functionality by taking a paper bill out of your wallet etc.

n1bor's modification to bitaddress.org was mentioned here is the link:
https://raw.github.com/n1bor/bitaddress.org/vanitytab/bitaddress.org.html

I believe it could be used for this Split Key purpose. The tab could possibly change some terminology such that it would be useful for Vanity (Pool) Wallet purposes and Split Key purposes. The missing feature is adding two public keys to get the bitcoin address without bringing the two private keys together in one place first (not a concern for a Vanity Wallet).

Cool, thanks.

The math works out fine for any number of keys, but the amount of exchanging of information between devices gets annoying:

Private key is A
Public key of A is A'
Public generator point of the Bitcoin elliptic curve is G.

Device 1:  Creates private key A.  Computes public key which is  A*G = A'
Device 2:  Creates private key B.  Computes public key which is  B*G = B'
Device 3:  Creates private key C.  Computes public key which is  C*G = C'

Ultimately, the combined private key will be A*B*C, and the public key will be (A*B*C)*G.   However, in order to do this, Device 3 needs to give device 2 its public key (C' = C*G).  Then Device 2 can produce B*(C*G)=(B*C)*G.  Then you transfer that to device 1 which can then produce A*(B*C)*G = (A*B*C)*G.   No one device has seen any private keys other than its own (so far).  Send coins to the address associated with that public key.

In order to create the private key, you just collect A, B and C onto the same computer and multiply to get (A*B*C).  Import that into a wallet and sign.  If you want to play with this, I recommend downloading Armory and run it in offline mode (because you won't actually use it for your wallet), then go to "Tools->ECDSA Calculator". 

It could probably be used like that too. I don't think people have given much attention to partial keys yet. It was worked out as part of wanting to use vanitygen without exposing the keys. And as far as my reading on the forum not much else has been done with it. It's a bit complicated for users and the combine functionality isn't in many clients so that's likely why. A simple wrapper has to be built around it so people can use it without running cmd line tools.

I'm a bit curious as well if multiple partials could be used in a similar way. Let's say the result of the first addition was a input key to a second addition such that three keys were needed. I haven't tried it but it seems likely to work.

edit: Just tried it and it does work.  So N-way keys could be created as well. And I just realized this is probably the basis for deterministic wallets. 

paper wallet is the subject. nice idea's but people are still thinking that they need third party services and outsiders.. paper is all you need... oh and a pen. maybe a safety deposit box.

if its not on your computer (restore it) or never been given to any web service.. the only people that can take it. know where u live.

I have been playing with this all day. Very cool.

Question: Why hasn't anyone used this for Escrow? I bet there has to be a page on this somewhere

Example:
* Seller goes to Escrow-BTC.com and signs a message from address 1EwMryEWqFLrfyyK6gTz3HUwgmLsVTFuQr (proves he knows the private key, not on-line wallet)
* Escrow-BTC.com then generates a vanity address with that public key and sends Buyer a PrivkeyPart: 5KiThyF8KKXm51jRT99Yckn63hGXFsBjniQNdYqyqDvhSHvQmEB
* This produces a vanity address: 1ZZZZKnrZRAmCgfVtjpgzZc1f9SkfndF5, which buyer sends funds to.
* At this point, no one knows the Private Key to 1ZZZZKnrZRAmCgfVtjpgzZc1f9SkfndF5
* Seller has delivered package, buyer can release his PrivkeyPart to seller. Buyer can only not deliver funds out of spite.
* Seller combines his private key with buyer's PrivkeyPart:


And viola! The seller has access to funds.

No, you don't understand. If I did anything at all it would be exactly like bitaddress,org where the html file can be saved and used offline any time, and completely open source and verifiable by anyone.

The point is that each private key generated would only exist and be printed from one system.

But one key is not enough to actually spend coins.

So a hacker would have to compromise two distinct and preferably unrelated systems in order to obtain a working spendable key.

The only thing someone uploads to the second system is the public key from the first system. The public also does not allow spending coins in any way.

The only reason to have it as a web site is to make it easy to distribute and use (it can have help text saying what to do) but it need not be online and connected when generating a key, in the same way that bitaddress.org doesn't need to be.

your talking about making a website that takes some ones private key and then gives them some split up version of it.

why need a website.. just give people the sourcecode to do it themselves if you think its a great idea. its not complicated script and does not need web hosting to allow people to use your idea of extra security.

i think those that want the caution of needing a paper wallet wont put their private keys into someone elses website.

its much easier for a website to be compromised then some ones own PC would be, especially if they recovered it back to factory settings to avoid trojans etc first.

but the low tech method of printing out or even....
hand writing the code is even easier. saves ink and any 'print queue' trojans.(if u aint already restored PC)

the simple as pie method is trust no one but urself. if ur computer is compromised.. restore it.. no need for third party services websites.

the other idea about using the ECDSA calculator.. is other the top of noobs heads. and still requiring third party stuff..

PAPER WALLET .. again PAPER WALLET.. has no need to store on 2 computers.. thats a digital wallet your talking about.

just keep it on paper. laminate it cut it in half so the long code is in 2 pieces and useless on its own. and store in a separate location, in PAPER form

I don't understand what you are asking:  if your system holding your wallet is compromised already, your wallet is toast.  Get a system that will never touch the internet again, wipe it and put a clean version of whatever OS you want on it.  Install Bitcoin software (insert Armory plug here), and manually copy down the private keys and addresses (in Armory, it is "Backup Individual Keys").  There's your paper wallet.  If you want to "watch" it, produce a watching-only wallet.

In the absence of any good multi-sig solutions, you can do "manual" multi-sig using Armory's built-in ECDSA calculator.  It requires some mathematical prowess, but everything you need to know is on the forums.  The gist is:  create two private keys on two separate computers that have never touched the internet.  Copy/print the private keys on separate pieces of paper and store them away safely.  Copy/print the public keys and exchange them.  Now one computer has PrivA & PubB, and the other one has PubA & PrivB.   Both systems can use this to create a public key that is associated with a private key that is only recoverable when both original private keys are on the same computer. 

You can use this address for collecting money.  Use it for savings.  But it will be a bitch to move:  you'll have to transfer the private key from one computer to another.  Then plug them into the ECDSA calculator to get the master private key.  Create a new wallet and import that private key.  Then sign the transaction and take to an online computer to broadcast.

I don't actually recommend this because it's not simple by any means, but if you are that hardcore it can be done.  That's actually why I made the ECDSA calculator, for devs, and hardcore users like (and for myself to check ECDSA math when debugging stuff).  But it sounds like you're looking for something like this.

Sorry, you still have no clue what I'm even talking about.

compromised system??

lol maybe next time u should include the first part of my quote.. restore/recover system to factory settings.

but if u easily get a compromised system then ofcourse ur also gonna be deluded to trust typing your private key into some script kiddies website so they can do magical things to your private key.

simple fact about paper wallet is.. keep it on paper dont give it out to third party websites. and dont obtain it from third party websites either.

a paper wallet is just that. a paper wallet. anyone saying they are solving paper security by designing a website. has no idea what paper wallets are all about.

make it from ur own CLEAN system print it out and the only thing u have to worry about is someone in your real world life reading it. so cutting it in half and putting it in 2 locations will reduce that from happening.

Not exactly. The second key is not valid alone (it would be rejected) and the address created with it does not work on either key alone. But the address does work when you combine (using suitable EC math) the first key and the second key to make a final "real key". But you would only do that at the time you want to spend your balance.

I guess you could put a balance on the first key if you chose and it would be theoretically less secure since it's on your possibly compromised system. My intention wasn't to monitor the systems using honeypot keys. You could do that entirely independently with other keys if you wanted. But of course it may tell you nothing as a hacker may just wait until he sees a significant balance on the address.

---
If you wanted to test this out for yourself you would do the following, using the vanitygen programs (because at this time they are the only ones I know that do the partial key math, although there is a patched bitaddress.org around now that does key combining).

Sys #1 Run,
keyconv -G
Save the private key on usb #1. Save the public key on usb #2

Sys #2 Insert usb #2 and run,
vanitygen 1 -P

The private key and address would be saved on usb#2 now.
But if you want to test it then run,

keyconv -c

And it will output your "real key" and address should be same as above.

In real life I think I would lean towards using paper since moving usb keys between systems has the potential to carry an infection also.

If I understand correctly, you will have 2 private keys (5J... and 5H... for example) combined to make a 3rd private key (5K...).

Could you send 0.10 BTC to the first address (5J...) and 0.10 to the 2nd (5H...) but send 100 btc to the 3rd (5K...)

Set up to be notified when one of the first 2 addresses are drained, this lets you know you have been compromised on 1 system.