|
Title: 2-of-3 Paper Wallets Post by: ben-abuya on January 29, 2013, 02:48:17 AM I've been playing around a lot with Armory as an offline wallet, and the one thing that would make me sleep better would be a 2-of-3 series of paper wallets. Right now you can only print a single wallet page, so if somebody breaks in to your house and gets it, they have all your coins. If Armory used something like ssss-split to print out three pages, where any two of them were needed, you'd be able to put them in three different places, making it very unlikely any thief would get to two of them. At the same time, you could lose one of three and still be able to reconstruct your wallet.
Does anybody else feel this would be a cool feature? Title: Re: 2-of-3 Paper Wallets Post by: Johnathan on January 29, 2013, 05:43:51 AM I've been playing around a lot with Armory as an offline wallet, and the one thing that would make me sleep better would be a 2-of-3 series of paper wallets. Right now you can only print a single wallet page, so if somebody breaks in to your house and gets it, they have all your coins. If Armory used something like ssss-split to print out three pages, where any two of them were needed, you'd be able to put them in three different places, making it very unlikely any thief would get to two of them. At the same time, you could lose one of three and still be able to reconstruct your wallet. +1Does anybody else feel this would be a cool feature? Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on January 29, 2013, 06:42:28 AM Request: This isn't exactly secret, but I didn't plan to release it yet. So don't go telling all your friends, yet... let people stumble on this thread on their own :) You're ridiculous! I was going to keep this a secret until I released the new wallets, but that may still be a while, and the feature is technically already done. If you hadn't specifically requested exactly what I just finished a few days ago, I was going to leave it to be part of mega-release with the new wallets :) However, it's not integrated into the GUI, because the current wallets use a ton of data to represent a wallet, and splitting them results in each part being even 2x bigger. The new wallets will use 160 bits instead of 512, making it a lot more "friendly" to apply this technique. However, if you don't mind that it will be a ridiculous amount of data and you have some patience with the command line, you can do this right now! (It's so fresh though, you have to switch to the "armoryd" branch which is where I've been doing my latest development) If you're into math, you might enjoy the description of how this works, at the bottom of this post. For now, here's some sample output from my unit-test: Quote from: UnitTestOutput Splitting secret into 3-of-5: secret=9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f Fragments: Fragment 1: [a272f36702ea5db5d89d9c41931faba0, ab273c91fef6de0d5cc3dc5e87712255] Fragment 2: [3b5090051d3684c2ca8aa241b353ae0e, 56cfeec3a5c2dc64c05c4649bcc851a2] Fragment 3: [49bc409989e5b8dbb9f3241bec05f5bc, 27e8cf636660f8819112fdc58d8f0352] Fragment 4: [46822a24fc0243e438779d28e29799e4, 312166ef08a03608a8083123445d44e7] Fragment 5: [630744fd7c3c59d632b93949901ea8be, b18f33873447825b8ab52f424e7caf28] Reconstructing secret from various subsets of fragments... The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f The reconstructed secret is: 9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f9f Splitting secret took: 0.00063 sec Reconstructing takes: 0.00290 sec The code that generated what is above is in unittest.py: Code: from armoryengine import * I'm not sure I can cram it into the GUI and subject users to typing in 1kB/fragment. That's a lot of data! I think I'll skip that for now, and just focus on finishing the new wallets and release it with that... Enjoy! The Math: It's a super-elegant solution (http://en.wikipedia.org/wiki/Secret_sharing#Shamir.27s_scheme): encode your secret into the coefficients of a polynomial, and then distribute points on that polynomial. If it's a first-degree polynomial (line), two points are needed to solve the coefficients (and thus recover the secret). If you want to require 3 points, use a second-degree poly (parabola). Use higher order if you want to require more pieces. The cooler part about this is that you have to use finite fields if you want any chance of this working with 256-bit numbers: pick a large prime number, N, and do all operations modulo N. This creates a cyclic group of size N. Things like division are simply A/B = A*(B^(N-1)). You can't do it with floats or doubles, because there's not enough precision to track all the significant digits in the variables and you'd die from the rounding errors. And the coolest part is how little code was required to implement all the finite-field matrix operations in python! There's nothing efficient about it, but it doesn't need to be efficient to be useful here. It is still usable up to 8-of-N secret splitting -- it takes a couple seconds to reconstruct, but who cares! Title: Re: 2-of-3 Paper Wallets Post by: Meni Rosenfeld on January 29, 2013, 06:58:03 AM @etotheipi: That's cool. Eventually though, multi-sig would be much cooler and safer than just secret-sharing a single private key.
Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on January 29, 2013, 06:59:36 AM @etotheipi: That's cool. Eventually though, multi-sig would be much cooler and safer than just secret-sharing a single private key. This is not a replacement for multi-sig. It is to provide an alternative, flexible way to create and store paper backups. Multi-factor auth wallets (linked wallets) are still coming... with the new wallet files... if I ever finish them... EDIT: I see what I wasn't clear about -- this is for paper backups, not multi-sig wallet chains. You will be able to print a single paper backup, or if you are in advanced/expert mode, you can choose M and N to print off an M-of-N paper backup. Then it would print off a single piece of paper that can be cut with scissors into N strips, requiring any combination of M strips in order to recover your secret (or check a box to print N separate pages). I just didn't want to do this with the current wallets, because each strip contains data that is 2x the size of the secret to be split, and the current paper backups already store 512 bits. Thus, if you split your paper backup into 3-of-5 like my example above, in order to recover the secret you'll be typing 3 kB into Armory by hand! That's a lot! Originally, I was just planning to wait for the new wallets which will only require backing up 160 bits, which is a lot better (and about the best I can do). Since someone explicitly asked about it just after I finished it, I decided to share that it's available already if you are willing to do some work. Title: Re: 2-of-3 Paper Wallets Post by: Meni Rosenfeld on January 29, 2013, 07:24:44 AM @etotheipi: That's cool. Eventually though, multi-sig would be much cooler and safer than just secret-sharing a single private key. This is not a replacement for multi-sig. It is to provide an alternative, flexible way to create and store paper backups. Multi-factor auth wallets (linked wallets) are still coming... with the new wallet files... if I ever finish them... EDIT: I see what I wasn't clear about -- this is for paper backups, not multi-sig wallet chains. Title: Re: 2-of-3 Paper Wallets Post by: ben-abuya on January 29, 2013, 02:34:43 PM You're ridiculous! I was going to keep this a secret until I released the new wallets, but that may still be a while, and the feature is technically already done. If you hadn't specifically requested exactly what I just finished a few days ago, I was going to leave it to be part of mega-release with the new wallets :) That's amazing! Actually, one of the reasons it would be great to have this in the GUI is that you can create a QR code for each sheet of paper. That way it doesn't matter as much how much data there is. Netbooks have built in cameras and can easily scan the codes. Meni, you're right about m-of-n transactions, they are certainly much more flexible and powerful. However, it's going to take a while for them to be properly implemented and managed by the Bitcoin community, and I see this as a great temporary solution. Btw, etotheipi, I had the pleasure of meeting you at the Bitcoin Summit in Philly -- we were on the panel together at the end. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on January 29, 2013, 07:06:07 PM I understood this. What I mean is that if you store your private key exclusively on paper, storing it with 2-of-3 secret sharing still leaves a vulnerability when the shares are imported and combined (mitigated by combining in an offline clean computer, but still). If you have a 2-of-3 multisig address, and store the keys for that on 3 distinct pieces of paper, you get more security. @Meni, I think you're getting stuck on the idea that I have in some way proposed this idea as a replacement for multi-sig wallets. This is not intended to replace multi-sig. I'm not comparing it to multi-sig. It's nothing to do with multi-sig, at all. 0% related. It's simply an alternative for backing up your regular single-sig wallet. Your single-sig paper-backup has all the security risks you describe, but it's still an important use-case that many users (and maybe even organizations) will use even when multi-sig is available. Multi-sig is completely unrelated to this, and is still my number one goal for the new wallets. Though, I guess you could technically create a 2-of-3 multi-sig wallet between multiple devices or parties, and each party could back up their own wallet using a M-of-N split-backup... sounds complicated. In fact, I might try to discourage fragmenting multi-sig-wallet backups because of it being complicated (but there's no reason it couldn't still be done)... Use-case 1: simple user wants to use Bitcoin, and wants to have it backed up, but doesn't want any one user to have control of it. He may create a 3-of-6 split-backup of his single-sig wallet, keep one, and give the others to five friends who don't know each other (and don't know who they'd even contact to find the other pieces). Use-case 2: These super-paranoid folks who think that someone at the bank will snoop in their safe-deposit box. Okay, so use two safe-deposit boxes at different banks, distributing 2-of-3 pieces (keep one, put the other two in two different banks). The likelihood of snooping is ridiculously low, but apparently still enough for the paranoids. However, that stupidly-low probability is squared when it's two unrelated banks so even most tin-foil hatters would be satisfied. Use-case 3: Simply hide a few pieces around your house. As ben-abuya said, finding a single one won't be sufficient, but in 10 years from now when you need it, you'll surely be able to remember at least 3 of the 10 places you split it :) (hell, hide one at your grandmother's house in one the 10,000 books she has on her bookshelves -- she doesn't even have to know or care that it's there) Title: Re: 2-of-3 Paper Wallets Post by: Meni Rosenfeld on January 29, 2013, 07:32:14 PM I understood this. What I mean is that if you store your private key exclusively on paper, storing it with 2-of-3 secret sharing still leaves a vulnerability when the shares are imported and combined (mitigated by combining in an offline clean computer, but still). If you have a 2-of-3 multisig address, and store the keys for that on 3 distinct pieces of paper, you get more security. @Meni, I think you're getting stuck on the idea that I have in some way proposed this idea as a replacement for multi-sig wallets. This is not intended to replace multi-sig. I'm not comparing it to multi-sig. It's nothing to do with multi-sig, at all. 0% related. It's simply an alternative for backing up your regular single-sig wallet. Your single-sig paper-backup has all the security risks you describe, but it's still an important use-case that many users (and maybe even organizations) will use even when multi-sig is available. Multi-sig is completely unrelated to this, and is still my number one goal for the new wallets. Though, I guess you could technically create a 2-of-3 multi-sig wallet between multiple devices or parties, and each party could back up their own wallet using a M-of-N split-backup... sounds complicated. In fact, I might try to discourage fragmenting multi-sig-wallet backups because of it being complicated (but there's no reason it couldn't still be done)... From the OP: Quote I've been playing around a lot with Armory as an offline wallet, and the one thing that would make me sleep better would be a 2-of-3 series of paper wallets. To sleep better, the OP wants to have 3 pieces of paper where any 2 of them are needed to access his funds.One way for this arrangement is to have a single-sig address where the private key is split into 2-of-3 secret-sharing pieces, and printing each piece on a different piece of paper. A second way for this arrangement is to have a 2-of-3 multisig address, and print each of the associated private keys on a different piece of paper. As you said, the first method is now available in Armory. That has its use cases (and is what the OP had in mind) and as I said, it's cool. The second method is not yet supported by Armory or the larger Bitcoin ecosystem. It is a more secure way to use 3 pieces of paper than the first method, and because of this, it will be even cooler when this method is available. That's all I'm saying. Of course there are many more use cases for multisig and all sorts of crazy combinations you can do. I am not implying one feature is supposed to be at the expense of the other. But using a 2-of-3 address for long-term bitcoin savings is the most important use case for multisig IMO, and I'm looking forward to its availability. Title: Re: 2-of-3 Paper Wallets Post by: deeplink on January 29, 2013, 07:41:09 PM It's nothing to do with multi-sig, at all. 0% related. I get that splitting the wallet and multi-sig are technically not the same, but isn't the end result exactly the same? For example, if I want to backup a wallet on paper in different locations, but each one of those prints alone shouldn't be able to spend my coins, I can do either of the following: 1) use your split-wallet approach and if I want to spend the coins, rebuild the wallet with x-of-y prints 2) use multi-sig and if I want to spend the coins, collect x-of-y printed signatures Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on January 29, 2013, 09:07:24 PM @ Meni,
Sorry, I didn't mean to get defensive. Just a misunderstanding. Really the important part of what I was saying was: "This feature has no effect on my intention to finish and promote multi-sig wallets and all their wonderful features/benefits, and I totally agree with you that a proper multi-signature solution is still needed." Perhaps I misunderstood the intention of the original post. I think the misunderstanding (and the answer to deeplink) is that what I posted about doesn't have anything to do with spending your coins. It's purely a backup thing so you can recover your single-signature wallet in 10 years when your offline computer finally bites the dust. This is a terrible idea for spending coins -- if you want to require 2-of-3 things every time you spend coins, don't use this. Use multi-sig wallets (which aren't available yet, but I'm working on it). Context: Right now Armory has a one-time-only paper-backup that will backup your single-sig wallet for ever. I recommend you use it and keep a copy in a safe-deposit box and you'll never lose your coins. You may not need it for 10 years, but then your HDD crashes and you can make one trip back to the bank to get it and recover your wallet. Some people, though, are concerned about the physical safety of their paper backup (bank employees snooping, someone breaking into your house and finding it). They would prefer that someone touching your paper backup doesn't get to clean you out instantly. For actually protecting your day-to-day purchases from theft, you can increase your security (over Bitcoin-Qt) by using (1) Offline wallets, or (2) Multi-sig wallets. Armory has #1 right now, and should have #2, soon. And this split-backup thing has nothing to do with that. Title: Re: 2-of-3 Paper Wallets Post by: Johnathan on January 30, 2013, 02:25:07 AM Thus, if you split your paper backup into 3-of-5 like my example above, in order to recover the secret you'll be typing 3 kB into Armory by hand! That's a lot! Originally, I was just planning to wait for the new wallets which will only require backing up 160 bits, which is a lot better (and about the best I can do). Actually, one of the reasons it would be great to have this in the GUI is that you can create a QR code for each sheet of paper. That way it doesn't matter as much how much data there is. Netbooks have built in cameras and can easily scan the codes. That is the plan, correct, to have a QR code for each split paper backup that could scanned in easily?With this feature you could keep a brain wallet by memorizing a passphrase but also backup the generated private key by splitting it N-ways among family, attorney, etc., in case of death, and put recombination instructions (and may one of the split QR codes) in your will. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on January 30, 2013, 06:32:22 AM It appears I reinvented a bitcoin wheel:
https://bitcointalk.org/index.php?topic=104086.0 I mean, it's a "standard" crypto trick, but it also looks like Vitalek created exactly the same thing 6 months. And I probably could've used his code. My solution uses a stupidly-inefficient version of matrix-inverse, but that's because it was ridiculously compact, and I thought 8-of-N would be overkill, anyway. He says his could support up to 15-of-N and wanted to go up to 255-of-N. Meh... That is the plan, correct, to have a QR code for each split paper backup that could scanned in easily? With this feature you could keep a brain wallet by memorizing a passphrase but also backup the generated private key by splitting it N-ways among family, attorney, etc., in case of death, and put recombination instructions (and may one of the split QR codes) in your will. Yes, there will be QR codes everywhere. But I don't have plans to implement a QR reader in Armory unless someone basically does it for me... it's annoying to type in paper-backup stuff, but it should be a once-every-3-years kinda thing for most users. I like the idea of putting one in your will (that's essentially giving it to an attorney, though, isn't it?). You could also have fun nesting these, if you weren't afraid of mind-blowing complexity -- split the secret into M-of-N, and then fragment some of the pieces further. It would allow you to create asymmetrically-important fragments, so that each piece really just represents some fraction of the secret, some pieces worth more than others. I guess you'd get the same thing from simply producing 100-of-N fragmenting, and distributing multiple pieces to each person/place. Then you can keep 10% in your bookshelf, 30% in a safe-deposit box, etc. That would be a ton of data, and QR codes probably wouldn't be very convenient either. This really isn't all that useful, just kinda fun to think about ... It's late, maybe I should sleep instead... Title: Re: 2-of-3 Paper Wallets Post by: ben-abuya on January 30, 2013, 08:07:59 PM Yes, there will be QR codes everywhere. But I don't have plans to implement a QR reader in Armory unless someone basically does it for me... it's annoying to type in paper-backup stuff, but it should be a once-every-3-years kinda thing for most users. It's true that that's the use case, however I believe there's one other important use case: testing the system in order to feel comfortable with the process. If someone puts their savings into their armory wallet and prints out three pieces of paper, the first thing they're going to want to do is try to restore the wallet from the pieces of paper. The QR code makes that much easier. To be fair, I did that test by typing in the words, and it wasn't that bad. It's also important to keep in mind the most likely failure mode. For instance, you could have a fantastic cryptographic system, an unhackable password, and a netbook that's completely isolated from the internet. And then the cable guy could slip a keylogger in your usb port, copy your encrypted wallet file, and come back a few days later to fix your router and take your password. That may be highly unlikely at this point, but infinitely more likely than somebody breaking a 160 bit password. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on February 23, 2013, 07:33:19 PM I've already described a similar use-case in one of the above posts, but I am considering doing this right now, so I thought it was appropriate to post here what I'm doing, and what the alternatives are. I want a simple offline computer to conduct trade, and I want to back it up...
A quick note: One of the benefits of Shamir's Secret Sharing is that if N pieces are needed to reconstruct the secret, having N-1 pieces is as good as having 0 pieces: you have nothing. Compare this to some scheme where by you simply split the private key into four 8-byte fragments... if you accumulate 3 of them, you only have to brute force 8 more bytes to get the fourth piece, which is completely feasible. With this scheme, the last piece could be any N-bit (x,y) pair on the finite field plan, and no one point is any more likely than the others. I emphasize this, because I don't want anyone reading to believe that somehow an attacker with 7 of 8 required pieces is a threat (outside of the fact that he has less remaining pieces to find than someone without any). Those seven pieces are 100% useless without an eighth one. It's one of the beauties of the SSS. So onto the use case: Right now, I have a wallet, backed up onto a single sheet of paper. That sheet of paper by itself allows anyone who finds it, to recover all the coins in my wallet. I have put a copy of this piece of paper in a safe-deposit box at the bank, for safe-keeping. If a fire at my house destroys everything, I can still get my coins back with a visit to the bank. Of course, the paranoids out there are concerned about bank employees snooping. I would say it's being too paranoid, but to some extent you can't be too paranoid with BTC, since all security failures are completely untraceable and unrecoverable. It would be impossible to prove that the employee did this. And declaring that life is unfair does not get me my coins back. Similarly, someone who breaks into my house finds one of my two sheets of paper will get all my coins. This is my point of comparison: the fragility of the single-backup system. You want to backup, but you don't want the vulnerabilities associated with it. I would propose a or 3-of-5 fragmented backup. You put 2 pieces in the safe-deposit box at the bank. You keep two at your house in different locations, as protection against losing one, and you give the 5th piece to a friend, family member, or your attorney (who should be good at keeping stuff). Make it 3-of-6 if you are extra concerned about your house burning down, and give one to another friend. A lot of things have to go wrong for this to fail. The 2 pieces at the bank are useless without a third one, so no problem with snooping bank employees. Someone breaking into your house, even if they find both pieces, will get nothing unless they also infiltrate the bank or break into your friend's house, too. If your house burns down (and somehow both pieces are completely destroyed), you still have a friend/lawyer with a copy which compliments the third available at the bank. If the banks disappears, you still have three pieces between you and your friend. And even if somehow these things happen, they will usually not happen at exactly the same time that your offline computer dies. Bank goes out of business? Well open your offline computer, decrypt your wallet, and print the two pieces again and put them in another bank. And why would we do this instead of multisig? Well, I don't want multisig. I am still a single person using an offline computer to operate my business, and it's quite simple to use single-sig offline transactions without any extra complexities (plus, you can only go up to M-of-3 using multi-sig). I just want a way to mitigate common side-channel compromises that are associated with my backups. Title: Re: 2-of-3 Paper Wallets Post by: deeplink on February 23, 2013, 07:59:49 PM Thanks for the explanation. This is exactly what I am waiting for to create the best fail-safe cold wallet backup. Also didn't know about the M-of-3 multisig restriction.
Talking of paranoia (I think it is legitimate when large sums of money are at stake) can you think of an easy way to validate if the backup is good? I mean 100% certainty. The only way to be really sure imo would be to restore the cold wallet from the backup and see if you can spend the BTC - very time-consuming if you are of the mental paranoid type and want to try all combinations of a Shamir's Secret Sharing 3-of-6 backup. Plus as far as I know that compromises some of the security of the cold wallet, because the public key is broadcasted to the network if you use an address for the first time. Is there another less time-consuming way possibly without the need to publish the public key to check if all backups are working? Title: Re: 2-of-3 Paper Wallets Post by: 13Charlie on February 25, 2013, 03:09:02 PM I like the idea of putting one in your will (that's essentially giving it to an attorney, though, isn't it?). You could also have fun nesting these, if you weren't afraid of mind-blowing complexity -- split the secret into M-of-N, and then fragment some of the pieces further. It would allow you to create asymmetrically-important fragments, so that each piece really just represents some fraction of the secret, some pieces worth more than others. This M-of-N system is a great feature and it will help many people, including myself sleep better at night. But . . . . Since the subject of super paranoid people has already come up here, If I were that paranoid person, I would prefer a backup system like X+ M-of-N. Where X is the piece that is in my will. I want to die before any of the pieces can be used. Is that something that could be possible with the current system that you're working on? As I typed that out, I answered my own question. I think it is possible, if you split it into enough pieces and keep > 51% of the pieces required to recover your wallet for the will. Example: Require 7-of-10 and put 4 pieces in your will. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on February 25, 2013, 04:50:51 PM I like the idea of putting one in your will (that's essentially giving it to an attorney, though, isn't it?). You could also have fun nesting these, if you weren't afraid of mind-blowing complexity -- split the secret into M-of-N, and then fragment some of the pieces further. It would allow you to create asymmetrically-important fragments, so that each piece really just represents some fraction of the secret, some pieces worth more than others. This M-of-N system is a great feature and it will help many people, including myself sleep better at night. But . . . . Since the subject of super paranoid people has already come up here, If I were that paranoid person, I would prefer a backup system like X+ M-of-N. Where X is the piece that is in my will. I want to die before any of the pieces can be used. Is that something that could be possible with the current system that you're working on? As I typed that out, I answered my own question. I think it is possible, if you split it into enough pieces and keep > 51% of those pieces to put in the will. Example: Require 7-of-10 and put 4 pieces in your will. The problem with this is that "putting it in your will" is essentially equivalent to "giving it to your attorney". Someone else has access to it in some capacity, since they obviously need to access it in the event that you die. Just like the bank employee snooping thing, it might be far-fetched, but some people are too paranoid. I think it makes sense that your will would contain a significant portion (say 2 of the 5 required pieces), making it considerably easier for your family to recover your funds once they see the will but not allowing your attorney full access to it if he "turns" on you. There's a lot of permutations, and I fear that this could be "too complicated" for many folks. I think I'll limit it to "require 2 or 3 fragments" below Expert usermode, and you can make any number of fragments. By the way, the algorithm that I have implemented uses deterministic fragment generation. i.e. You require any 3 pieces to reconstruct the wallet. You print out 5 such pieces. Now lets say you decide too much risk is involved in losing a couple of the pieces, so you can print out fragments #6 and #7 and know that they will compliment the other pieces. Or if one of your fragments is destroyed, you can reprint #2 and know it will be the same as before. As for peace of mind that the fragments will reconstruct properly... I'm not sure how to do that "right". I can show the user the result of recombining fragments (as I did in my first post in this thread, showing that I did the calculations and got the same answer, but that's not necessarily comforting to the user. They won't be satisfied until they manually enter each fragment into a fresh version of Armory that's never seen the wallet, and they get the correct answer. There's nothign I can really do about that. Title: Re: 2-of-3 Paper Wallets Post by: 13Charlie on February 26, 2013, 02:27:18 PM By the way, the algorithm that I have implemented uses deterministic fragment generation. i.e. You require any 3 pieces to reconstruct the wallet. You print out 5 such pieces. Now lets say you decide too much risk is involved in losing a couple of the pieces, so you can print out fragments #6 and #7 and know that they will compliment the other pieces. Or if one of your fragments is destroyed, you can reprint #2 and know it will be the same as before. That's awesome and offers tons of flexibility. I can't wait to play around with this feature. As for peace of mind that the fragments will reconstruct properly... I'm not sure how to do that "right". I can show the user the result of recombining fragments (as I did in my first post in this thread, showing that I did the calculations and got the same answer, but that's not necessarily comforting to the user. They won't be satisfied until they manually enter each fragment into a fresh version of Armory that's never seen the wallet, and they get the correct answer. There's nothign I can really do about that. Exactly, the only thing you can do is preach about practice! I didn't put any large amount in cold storage until I had reconstructed my wallet 3-4 times, I even did a fresh OS install and reconstructed again. Title: Re: 2-of-3 Paper Wallets Post by: dooglus on March 04, 2013, 06:04:28 AM the current paper backups already store 512 bits. Thus, if you split your paper backup into 3-of-5 like my example above, in order to recover the secret you'll be typing 3 kB into Armory by hand! 3 kB as in 3 kilobytes? I don't know what you use to encode the bits in a paper wallet but if you use base 64 you'll get 6 bits per byte, so should only have to type 171 characters from each of the backups, or 513 characters in total. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on March 04, 2013, 06:29:32 AM the current paper backups already store 512 bits. Thus, if you split your paper backup into 3-of-5 like my example above, in order to recover the secret you'll be typing 3 kB into Armory by hand! 3 kB as in 3 kilobytes? I don't know what you use to encode the bits in a paper wallet but if you use base 64 you'll get 6 bits per byte, so should only have to type 171 characters from each of the backups, or 513 characters in total. Wtf. You're right. I can't believe I confused myself with bits and bytes! But my point of reference was still correct: I know that typing a regular paper backup is "annoying", so typing 6 times as much would be more than "annoying." Granted, I use hex right now, and should probably use base 64 instead as you suggested. Though, part of the reason the paper backup uses a different alphabet than normal hex is so that it's easier to touch-type, since most people don't touch-type numbers very well. If anything, I'd probably switch to base-32, but then I'm not gaining much over hex... On a related note, can someone please find for me one of the few largest 512-bit prime numbers? My lookup table of primes stopped at 400 bits, and I haven't been able to find an appropriate one for 512. Having that would make it much more straightforward to fragment the current paper backups, rather than fragging the root key and chaincodes separately. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on March 05, 2013, 12:21:36 AM I've had quite a few people contact me, excited about the fragmented backup. It's essentially done under-the-hood already, and was going to go into the new wallets, but those are looking like they're going to be on the back-burner for a while. I'd like to provide the feature now, but I'm concerned about a few things:
As I said, I had hoped I could just finish the new wallets and get it all out there and make all the old wallet stuff, legacy. In order to balance all these different things, how would you (whoever wants this feature), feel about a halfway answer? I would create a "frag_wallet.py" script that would take a given Armory wallet, ask for your passphrase to unlock it, ask for M and N, and it would spit out N text files (of which you need M to reconstruct). Similarly, there would be a "unfrag_wallet.py" script, which you would dump M text files in that directory and it would create a new Armory wallet file for you, exactly as if you had restored from paper backup. The text files would contain everything that's needed, and each one could be loaded and printed separately, or copied to different devices. Also, there is so little source code for doing this, it looks like the entirety of the code needed could be printed on one or two sheets of paper. Granted, the script itself for reading and writing files, error checking, opening Armory wallets, is quite a bit longer -- but the raw code needed to reverse-engineer the calculations is small. But if users were concerned about not having the source code that generated the finite fields and how to reverse it, this could resolve any concerns (either way, it'll permanently be part of Armory code-base, but I know some people prefer that specific code to be backed up, too). So would people use it as a command-line utility? Even knowing that in a couple months there will be new wallets, with shorter seeds, with a native GUI interface? There's no reason this script would have to go away... I'd leave it in the "extras" directory and you'd always have access to it by downloading the repo, and it would serve as further example code. It would still be there and still work in 10 years from now. It would simply create an older Armory wallet that would have to be migrated to the new wallet format (which will have to be done with all older wallets, now, anyway). Thoughts? Title: Re: 2-of-3 Paper Wallets Post by: 13Charlie on March 05, 2013, 02:18:47 PM My 2 cents
Thanks for the options but . . . . I know that my current paper backups are safe and I don't plan on writing my last will and testament for a few decades. Take your time. Title: Re: 2-of-3 Paper Wallets Post by: ben-abuya on March 05, 2013, 10:11:03 PM My 2 cents Thanks for the options but . . . . I know that my current paper backups are safe and I don't plan on writing my last will and testament for a few decades. Take your time. +1 I think you should take your time and keep to your development goals. When I posted the feature ideas, they were just things I'd like to eventually see in the software, and I'm glad that you'd already been planning them all along. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on March 06, 2013, 05:46:22 AM Well, you guys were too slow and I just did it anyway. I also left out one critical reason: I really wanted this feature for myself! And I don't want to wait 2 months for it! I knew it would take me a day, and I'm sure someone would benefit from it, now. Also, it's not wasted effort -- it's more sample code for other users, and I got the fragment data structures ironed out which will be recycled when I implement it in the GUI.
I have tested the heck out of it, and successfully restored quite a few test wallets with it. Let me know what you think!
Checkout the armoryd branch, and the scripts are in the extras directory. Sorry, this only works if you can run python scripts (possible in Windows, but you have to install some stuff). Code: $ python frag_wallet.py ~/.armory/armory_2QQkCkdt_.wallet 3 5 Use the extras/frag_wallet.py script to break your paper backup in N files, and then you can immediately use the extras/unfrag_wallet.py script to execute the recovery process on 20 different subsets of M fragment files. Without the --test option, it will ask you for the appropriate encryption options, and then create an armory*.wallet file that can imported natively into Armory. Output of the fragging script Code: $ python frag_wallet.py ~/.armory/armory_2QQkCkdt_.wallet 3 5 Each file looks like the following: Code: Wallet ID: 2QQkCkdt Run the unfrag test: (it works without the --test flag, if you have more than M files) Code: $ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt --test Recover the wallet: Code: $ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt Exhaustive error catching and useful information Code: $ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt --testnet Code: $ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt --testnet Title: Re: 2-of-3 Paper Wallets Post by: ben-abuya on March 08, 2013, 10:18:01 PM Awesome, I'm gonna try this.
Well, you guys were too slow and I just did it anyway. I also left out one critical reason: I really wanted this feature for myself! And I don't want to wait 2 months for it! I knew it would take me a day, and I'm sure someone would benefit from it, now. Also, it's not wasted effort -- it's more sample code for other users, and I got the fragment data structures ironed out which will be recycled when I implement it in the GUI. Title: Re: 2-of-3 Paper Wallets Post by: nimda on March 09, 2013, 03:26:32 AM This is great.
Side note: I just spent several minutes trying to come up with a A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) scheme. The "DOH!" moment was when I realized that, since B ∧ C is useless, I might as well just set B = C and implement the scheme as K = A ⊕ B = A ⊕ C. No fancy geometry required! While practically useless, I'm still interested to know if a A ∧ (B ∨ C) scheme is possible where each piece is independent (gives no information about any other piece) and (B ∧ C) gives no information about K. Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on March 09, 2013, 03:31:10 AM This is great. Side note: I just spent several minutes trying to come up with a A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) scheme. The "DOH!" moment was when I realized that, since B ∧ C is useless, I might as well just set B = C and implement the scheme as K = A ⊕ B = A ⊕ C. No fancy geometry required! While practically useless, I'm still interested to know if a A ∧ (B ∨ C) scheme is possible where each piece is independent (gives no information about any other piece) and (B ∧ C) gives no information about K. I assume you're talking about trying to create "A or (B and C)" backups. My solution to this is quite simple: Create B and C. Backup copies of both B and C to wherever you were planning to backup A. Title: Re: 2-of-3 Paper Wallets Post by: nimda on March 09, 2013, 03:44:18 AM ... I assume you're talking about trying to create "A or (B and C)" backups Quote My solution to this is quite simple So's mine (K = A ⊕ B = A ⊕ C because B = C), unless yours implements the scheme at the bottom of my postQuote Create B and C. Backup copies of both B and C to wherever you were planning to backup A. This has the effect of making B and C essentially one key (I'll call it D), and your scheme reduces to A ∧ D, or 2-of-2. What's the point of having B and C be separate pieces if they're placed together?I intended A, B, and C to be separate, but it reduces to a 2-of-2 where there are 2 backups of one of the keys. The question (if it can be called that) at the bottom of my post above still stands. Perhaps use a trigonometric function like sine? If we implement it as A ⊕ sin(B) = A ⊕ sin(c), then having both b and c is still useless, and having b gives no information about c in a perfect world. (Again, it's useless to have b give no information about c, but still...) In a world with a maxInt, having b reduces the number of possibilities of c substantially, because there are only 2 possible c's for every 2π Title: Re: 2-of-3 Paper Wallets Post by: picobit on March 09, 2013, 08:07:30 AM The N-of-M scripts are a really good idea, and I will probably use them for my own use. However, it is a bit too complicated for my loved ones to do the restore. I know that will come soon to Armory, but in the mean time, what do you think of this "poor mans 2-of-3 paper backup":
1) Print two ordinary paper backups. Cut off the QR codes and destroy them. 2) Cut off the left 1/3 of one of the papers, and the right 1/3 of the other. 3) Store three envelopes in three places, each with 2/3 of the key. From any two envelopes, the entire sheet can be recovered. Clearly this lacks mathematical elegance, and gives no credit in the crypto community. :) Also, it leaks a significant amount of the key if just one part falls into the wrong hands. But with 256 bits in a key, that still leaves 85 bits for the average burglar to brute-force. And if there are both a root key and a chain key of 256 bits each I quess it will be more like 170 bits. Have I overlooked a problem with this method? Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on March 09, 2013, 03:57:15 PM The N-of-M scripts are a really good idea, and I will probably use them for my own use. However, it is a bit too complicated for my loved ones to do the restore. I know that will come soon to Armory, but in the mean time, what do you think of this "poor mans 2-of-3 paper backup": 1) Print two ordinary paper backups. Cut off the QR codes and destroy them. 2) Cut off the left 1/3 of one of the papers, and the right 1/3 of the other. 3) Store three envelopes in three places, each with 2/3 of the key. From any two envelopes, the entire sheet can be recovered. Clearly this lacks mathematical elegance, and gives no credit in the crypto community. :) Also, it leaks a significant amount of the key if just one part falls into the wrong hands. But with 256 bits in a key, that still leaves 85 bits for the average burglar to brute-force. And if there are both a root key and a chain key of 256 bits each I quess it will be more like 170 bits. Have I overlooked a problem with this method? That's wouldn't exhibit the awesome property I described about SSS giving no brute-force advantage to an attacker with less than M pieces. But there's four times as much data in the current backups than needed (theoretically), so even if you broke it into four pieces, each piece would still have sufficient entropy (128 bits each). However, you could really only use M-of-M backups... No arbitrary subsets. Title: Re: 2-of-3 Paper Wallets Post by: picobit on March 09, 2013, 04:37:23 PM However, you could really only use M-of-M backups... No arbitrary subsets. What I described was a 2-of-3 backup, since any two parts would reproduce the entire sheet with a bit of overlap. I agree it is inferior to the method you are implementing, but while lacking a GUI interface to restore that, assembling two pieces of paper is at least hard to get wrong.Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on March 09, 2013, 04:49:28 PM However, you could really only use M-of-M backups... No arbitrary subsets. What I described was a 2-of-3 backup, since any two parts would reproduce the entire sheet with a bit of overlap. I agree it is inferior to the method you are implementing, but while lacking a GUI interface to restore that, assembling two pieces of paper is at least hard to get wrong.Oh I get it... yeah, clever. My comment is still valid: it is "safe" since there's so much entropy in the current paper backup that even requiring brute-forcing any 1/4 of it is still prohibitive. So yeah, the terminal interface I produced is really a stop-gap, to make it available in some capacity until I get the new wallets implemented. However, you can feel good that it will remain supported, because I plan to be using it for a new-and-important wallet I'm creating :) Title: Re: 2-of-3 Paper Wallets Post by: DBordello on March 24, 2013, 06:21:26 PM Would it be possible to get the dependencies for these scripts included in the offline Ubuntu bundle?
Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on March 24, 2013, 10:24:58 PM Would it be possible to get the dependencies for these scripts included in the offline Ubuntu bundle? Yup! I actually just tried to use it myself on an offline computer and ran into this. I already adjusted the build script to distribute them with the dependencies needed to run them, I just have to do a new offline-bundle. Big new release coming soon. I'll make a new offline bundle just for that reason. Title: Re: 2-of-3 Paper Wallets Post by: DBordello on March 24, 2013, 11:45:18 PM I can't wait!
Excellent work. These scripts are what pushed me over the edge to switch to armory. Title: Re: 2-of-3 Paper Wallets Post by: DBordello on April 04, 2013, 08:59:43 PM Has there been any progress on updating the offline bundle to support these scripts?
Title: Re: 2-of-3 Paper Wallets Post by: etotheipi on April 04, 2013, 09:04:11 PM Has there been any progress on updating the offline bundle to support these scripts? Actually, I haven't because I wasn't ready to release yet. But Linux seems pretty stable. I might as well. I'll do it (and sign it) if you checkout the latest "managesatoshi" branch and test it online for me (in Linux). :) Title: Re: 2-of-3 Paper Wallets Post by: DBordello on April 04, 2013, 10:39:55 PM Deal
|