New Concept/Idea/Product: Secure Bitcoin Wallet SEEDS

[casascius]

EDIT March 2013: Since this thread has been revived from the dead, I thought I might point out that I have implemented something functionally similar to this proposal (but arguably better).  It is my BIP 38 encrypted paper wallet generator, implemented in Casascius Bitcoin Address Utility.  Basically, instead of generating "seeds", you pick a passphrase, the utility can be used to turn the passphrase into an intermediate code, which you send to somebody else and they can print wallets all day long, using the same utility, encrypted with your passphrase.  The person who has the intermediate code and prints the wallets has no way to know what the passphrase was or get the private keys to the addresses they print (short of brute forcing the passphrase from scratch).  This to me is so much more practical than the "seeds" idea I had earlier.  I currently have no intention of producing or selling the product I describe in this thread, as Casascius Bitcoin Address Utility is a free open-source download you can run and receive these benefits from today at no cost.

I have decided that I might like to sell a new product: sheets of SECURE WALLET SEEDS.

A "wallet seed" is a sticker that has a private key on it that I securely generated.  I sell you a sheet of them in the mail.  Each seed is only half of a Bitcoin account - you get the other half elsewhere.

Your seeds are used to create a paper wallet - somewhere else - like using a modified copy of Bitaddress.org (which I'm sure will happen soon if this idea is liked).

In a nutshell: you buy my sheet.  My sheet has a URL that leads to the public keys needed to incorporate the keys from my sheet into a brand new secure paper wallet.  You cut-&-paste the data from that URL into the paper wallet generator of your choice, and print a paper wallet.  Your paper wallet knows which sticker ID's to ask for, and there's spots on your sheet that match each sticker.

Your paper wallet is absolutely secure.  It is unusable without the private keys from my sticker sheet - so you are safe from someone who attacks your machine with a trojan or virus or keylogger.  It is safe from me, because I don't and can't ever have the part you generated.

So, you peel the keys off my sheet, and stick them onto the appropriate locations on your new paper wallet.  Voila, absolutely bulletproof paper wallet.

PROOF OF CONCEPT ---> https://www.casascius.com/seeds/25A999B7ECCAA441.pdf

for this to become commonplace, only a couple things would be needed:
1 - modification to BitAddress.org to accept pastes of the public key file.
2 - modification to MtGox's redeemer that allows it to accept a combination of TWO keys in order to do a redemption, as well as similar mods to the importprivkey patch.

[Revalin]

What advantage will this have over generating my own seeds?

[nmat]

What advantage will this have over generating my own seeds?

Just about to post that. It seems to me that a user that is knowledgeable enough to import these keys can also securely generate his own.

[casascius]

What advantage will this have over generating my own seeds?

It's an independent source.

If whatever you use to generate the seeds is also used to generate the final wallet, and they are both compromised by the same attacker, the seeds offer no benefit.  The whole point of the seeds is to securely generate addresses on a machine known to be compromised, or which is possibly compromised... but without giving the person who generates the seeds the ability to steal your money.

[Revalin]

How do you generate a public key without assembling a full copy of the private key in one place?

[gnar1ta$]

Is there a way to explain this for the crytologicaly impaired?

[casascius]

Yeah, there was another thread I had started (titled "Elliptic Curve Math Question") where the math was hashed out in depth.

Basically, it's possible for two parties to each create a key pair, and join them mathematically in such a way to make a third keypair, where the public half of that new keypair is easily calculated without sharing any private keys, but where the private key for that third keypair can only be calculated by someone who has both of the first two private keys.

So as long as the sources of the first two private keys can't collude to share them with each other, neither of those sources can get the private key to the third combined key.  That third public key is used to generate the address where you send your bitcoins.  Since you are the only person who has both private keys, only you can redeem the coins, despite them both coming from potentially untrusted sources.

You as the user get one key from me, and one from your (potentially compromised) computer.  I share just enough information to allow your computer to compute the combined bitcoin address (that's why there's a link to a text file full of numbers).  Coins sent to that address can only be redeemed if you have the private key I generated AND the one your computer generated.

A hacker who roots your computer is out of luck because he doesn't have my key...I mailed it to you.

I'm out of luck (as a supposed thief) because i have no way to get the key your computer generated.

You can generate your own seeds as long as you have a way of getting them that is completely independent from the wallet generator.  For example, if you generate seeds on your compromised computer and then make a paper wallet with them on the same computer (or another computer controlled by the same hacker), you are screwed because the same hacker can get both halves.  But if (for example) you could generate seeds on your smartphone, and have them mailed, faxed, or otherwise delivered to you with a method that doesn't involve your computer, then you're safe.

[gnar1ta$]

So the actual "bitcoin" private key needed to spend the coins can only be generated from the combination of the 2 "non-bitcoin" private keys. And the "bitcoin" public key used to generate the wallet address can be found by using the 2 "non-bitcoin" public keys - no private keys required. 

If that's correct, that's a great idea.

[mila]

how similar is it to deterministic wallet?
would the same seeds produce always the same keys?
or is there a limitation of how many keys one can grow and then the seed would be exhausted?
thanks and cheers!

[Meni Rosenfeld]

A hacker who roots your computer is out of luck because he doesn't have my key...I mailed it to you.

I'm out of luck (as a supposed thief) because i have no way to get the key your computer generated.

Unless, of course, you and the hacker are one. If people are to use this to store their life savings, you'd have quite an incentive to try to hack into your customer's computers.

So the actual "bitcoin" private key needed to spend the coins can only be generated from the combination of the 2 "non-bitcoin" private keys. And the "bitcoin" public key used to generate the wallet address can be found by using the 2 "non-bitcoin" public keys - no private keys required. 

That's basically it. The details were discussed here and there are two main approaches. One that is considered less secure (but IMO good enough for this application) is to have two private/public key pairs, each of them could be a valid Bitcoin pair in its own right, but they are not used as such - rather, a new private key can be obtained by combining the 2 private keys, and the corresponding public key can be found by combining the two public keys. The more secure version, which may be what casascius wants to do here, is to derive the private key from the 2 private keys, but to derive the corresponding public key from one private key and one public key.

how similar is it to deterministic wallet?
would the same seeds produce always the same keys?
or is there a limitation of how many keys one can grow and then the seed would be exhausted?
thanks and cheers!

As described in the OP each seed would be used for just one key. The idea can be extended to deriving multiple keys from one casascius seed.

[jav]

You as the user get one key from me, and one from your (potentially compromised) computer.  I share just enough information to allow your computer to compute the combined bitcoin address (that's why there's a link to a text file full of numbers).  Coins sent to that address can only be redeemed if you have the private key I generated AND the one your computer generated.

A hacker who roots your computer is out of luck because he doesn't have my key...I mailed it to you.

But: Wouldn't the hacker be in a position to simply display a different Bitcoin address? One which isn't at all connected to those two private keys, but instead a different one for which he has the private key. How would you notice if you don't have an independent and secure way of computing the Bitcoin address of the two private keys, which brings you back to the problem of operating on a compromised computer.

[pointbiz]

I'm interested and confused at the same time, so I'm going to try and consolidate what I believe are related ideas. Please understand any hesitation on my part is only because I have this idea in my mind about keeping bitaddress simple and easy to use.

Since there has been a discussion about how Bitcoin addresses can be safely generated as the point sum of two public keys, you ought to consider making Bitaddress.org support creation of such addresses.  This has generated a lot of interest, and would be a relatively simple change.

The result of making the change I propose, is that someone could paste in an EC point generated from somewhere else (e.g. smartphone) and the entire sheet of paper wallets would then have "half" private keys.  (they are still full length, but they are only half of what's needed to spend the funds).

The other "half" needed to redeem the funds would be the private key used to create that other EC point.  Basically, the paper wallet would be completely immune to a compromised machine or even a fake website, as long as the attacker didn't also control the independent source of that other EC point.

In brief:

1. Allow a user to paste in a public key (which is 65 bytes).  Detect typos by verifying that X and Y are on the curve.  Recall that a public key is an EC point.

2. You generate a Bitcoin address exactly the same way - but as you are computing the Bitcoin address - right after you generate the public key (pubkey = privkey * G), you do an EC point addition, adding in the public key you were just given. (so, pubkey = privkey * G + point)

3. You encode the private key in some way that indicates that it is only half of a private key.  This clues redeemers into the fact that some other key is needed. (I would like to propose that this be signalled by using something other than 0x80 as the version byte when doing the base58 encoding, perhaps something that makes the Base58 coded number start with '6' instead of '5').

EDIT: I recommend you use the version byte 0xA2 for this purpose.  Codes will start with a 6.

I will put a bounty on it.  One of my silver coins mailed to the address of your choice.

Bounty for a "Split Key" (working name) tab on bitaddress. The tab needs to accept a list of public keys (textarea) and the output needs to look like the paper wallet but also have a hollow square to place a QR code of another private key (the seed key). The split key paper wallet would show two private keys and one bitcoin address. However byte 0xA2 is used in place of byte 0x80 for both private keys, signifying that they need to be combined.

Could you provide me an updated "in brief". I believe the Elliptic Curve math question thread didnt have a clear conclusion for me... possibly cause I took a good number of days to get through the whole thing, but what I understood was point addition was rejected in favor of point multiplication.

You mentioned this to me in the PM "except when you compute the Bitcoin address, you use a new public key from the pasted file in place of the secp256k1 constant G". That corresponds to Meni Rosenfeld's understanding below as well. Can you point me to the post from the other thread which talks about that? Is that the point multiplication people were speaking of?

I understand the seed key could be provided by you Casascius but ideally there would also be functionality within this tab to generate Part A (seed) and Part B of the Split Key. Therefore, I could generate Part A at my friend Alice's house and use her printer and I could generate Part B at my friend Bob's house and use his printer. I haven't thought this through fully.

The use case of the final product is long term paper storage of bitcoins... correct? These aren't mediums of exchange like Casascius coins or printcoins?


Side note for v1.4 of bitaddress
- I will allow for a deterministic wallet to be created by entering a passphrase on the wallet details tab, instead of a private key. You will be prompted that your entered value is not a valid private key and asked if you want to use it as a passphrase to create a private key. It's just a SHA256 of the passphrase.
- I may update the wallet details tab to show QRCode of bitcoin address and WIF private key. I'm realizing QRCodes are just a great way to copy/paste from computer to mobile.
- I may update the wallet details tab to show the 65 byte public key. Since there's so much chatter about it lately
- I'm adding some FAQs to the Bulk Wallet tab. I'm going to use some text you posted about using Bulk Wallet to accept bitcoins on your website.


Once that's done then I can decide on my next TODO.

[casascius]

Will hit points one by one.

Elliptic curve math: The requirements have changed slightly since the time I posted them before.  We have switched to favoring multiplication rather than addition.  That's because there is a vulnerability with addition that doesn't exist with multiplication.  It's not a huge difference, but one notable difference is that the combined bitcoin address cannot be computed with two public keys alone: it requires one public and one private key.  So if Alice and Bob are trying to create a secure keypair together, Alice creates her keypair, sends the public side to Bob, and Bob calculates the combined bitcoin address from his new private key and Alice's public key.  Alice could compute the same address with her private key if Bob shares his public key with her.  In both cases they are substituting the other's public key in place of G when doing the multiply.  I believe the thread where this was discussed is the same Elliptic Curve Math Question thread you referred to, just at the end of it.

Your program could generate the seed: Yes, and in fact that might be preferable, and let's not worry about stickers.  Consider that we could say the best practice is to print part A at work, a library, or a friend's house, then copy, paste, and e-mail themselves the public key file, and then print part B at their own house, using the e-mailed file to ensure they match.  That will bring it within reach of many more people than me simply offering to sell stickers (few people will bother with that).

Example: You could have a "half wallet" tab.  The tab offers two buttons: create a half wallet (that's part A), or finish from a half-wallet you started before (part B).  If they click the first button, a batch of keys comes up, as well as a read-only textbox where they can copy out the public keys and e-mail to themselves.  If they click the second button, a textbox appears where they can paste it, and when they submit, the textbox disappears and part B comes out.  THe page would offer advice suggesting that half-wallets are a way to protect against rooted and hacked computers, saying that the keys are useless unless someone has both halves, therefore they should be generated on separate computers in separate places on separate networks, where the likelihood of a hacker being able to spy on both computers is reduced as much as possible.

Each bitcoin address on a half-wallet needs to show a "pair ID" so that the user knows they are matching the correct keys together.  But the pair ID shouldn't be confused for a bitcoin address.  I recommend that the pair ID be a ten character ID, computed as the second through eleventh characters of the Bitcoin address that would be generated from public key A.  Sheet B should be able to recompute the pair ID given the public keys that were pasted in.

Each box on half A would have a single QR code (for the private key), and the text: "This is a half-key.  Pair ID: abcde12345"

Each box on half B would have two QR codes, just like a BitAddress paper wallet, but also the text: "This is a half-key.  You need both halves to redeem funds.  The Pair ID of the other half you need is: abcde12345. "  Of course, one QR code is the Bitcoin address, and the other is the private key of half B.

Bounty: I'm still fair game for paying the silver coin as a bounty!

Purpose: These should be usable not just for long term storage, but anywhere a paper wallet would work.  The only difference is they are more tedious, but of course they are more secure.  These could be mediums of exchange like casascius coins, though I have my own generator for those (I use minikey due to space constraints).

QR codes: I definitely enjoy having the QR codes there.  I get regular use out of my USB Wasp-brand handheld scanner, for scanning bitcoins in and out of my system.  Paper wallet use is a breeze.

[Steve]

This idea is appealing, especially for savings.  However I have to agree with jav that if you computer actually is compromised, then it's still not safe to trust it the addresses it presents to you.  It would be a more difficult attack (since it involves the clandestine altering of your key/address software rather than just sniffing data) and since there would likely be fewer people using this technique, it may not be worth the effort for an attacker.

It still seems to me that the most prudent advice is to only generate private keys and their corresponding addresses on a computer that you completely trust and that has never been and never will be connected to a network of any kind.  Software and perhaps a device (that doesn't have any way to physically connect directly to a network) that makes the whole process easy would be a good idea.  A bootable CD that only writes a PDF file of the paper wallet (with passcode encrypted private keys as QR codes) might be a good solution for people.  The ISO file could be signed by various people that attest to its safety.

[pointbiz]

I totally understand this half wallet concept now (I like the term half wallet). I also like the term pair ID.

I've done a mock up based on the graphics from Osmosis. I think I'm getting excited about this...



Steps for do it yourself half wallets (which could be adapted for the sticker system).

• The part with the white background on the bottom left is printed during "Part A".
• You email yourself the Part A public keys, then go to another computer at a different location. You take the printed sheets from Part A with you.
• At the second location when doing "Part B" you feed the printer with the Part A sheets.
• You open your email at the second location and copy/paste the public keys from Part A into Part B.
• You then print the part with the nice background and check that the pair IDs match up.

[ripper234]

FYI, I uploaded this to the wiki a long time ago.

casascius, are you making these? Can I order one?

[casascius]

FYI, I uploaded this to the wiki a long time ago.

casascius, are you making these? Can I order one?

I'm not making anything of the sort, but since the time I wrote this, I have come up with BIP 38 and a utility that essentially does the exact same thing, only better.

Instead of generating a "seed", you pick a passphrase.  You use Casascius Bitcoin Utility to turn that into an "intermediate code" and send it to someone else.  Someone else can use that to produce BIP38-encrypted paper wallets that are encrypted with your passphrase but has no way to find out what the passphrase was or to figure out the key (short of brute forcing it).

[ripper234]

FYI, I uploaded this to the wiki a long time ago.

casascius, are you making these? Can I order one?

I'm not making anything of the sort, but since the time I wrote this, I have come up with BIP 38 and a utility that essentially does the exact same thing, only better.

Instead of generating a "seed", you pick a passphrase.  You use Casascius Bitcoin Utility to turn that into an "intermediate code" and send it to someone else.  Someone else can use that to produce BIP38-encrypted paper wallets that are encrypted with your passphrase but has no way to find out what the passphrase was or to figure out the key (short of brute forcing it).

Interesting.