Title: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on March 06, 2013, 05:36:29 PM Background: "Fragmenting" your wallet backup was going to be a feature in Armory's new wallets, but other priorities have come up and I can't finish the new wallets yet. But I still wanted to make this feature available since the math was fully implemented. Rather than complicate the GUI with more backup options that will have to change once again when I finally do finish the new wallets, I decided to make a command-line utility.
Re-post of this message (https://bitcointalk.org/index.php?topic=139625.msg1588963#msg1588963). Reposting because I figured this was in demand by a wider audience, and there's plenty of folks in the D&TD forum that don't mind using command-line tools (though, this is the only command-line-required function of Armory). The "correctness" of the utility should be self-evident. The output of the "fragging" script is N files in the execution directory. The input to the "unfragging" script is to have M+ files in the execution directory. And the unfragging script has a built in "test" so you can see it work correctly on multiple subsets of fragments. And it puts the git-commit version in the output so you know exactly what version created it (though, it will forever be in the master branch now, and I don't expect it to change). Features:
Also, there is a completely dependency-less script "sss.py", which contains everything needed to restore these fragments. If you have python installed, you can run that script in isolation (default python installation, without installing Armory). The reason for making it, is it's easy to print off for the ultra-paranoid that think that the git-repo won't be available in the future for some reason. The script doesn't do the unfragging for you, but it has everything you need in a couple hundred lines of code and could be printed out on one or two sheets of paper. Use Cases: To be used with regular Armory wallets.
This still assumes a single-sig wallet, and that there is probably an offline computer with an encrypted version of it, accessible by you. The problem is that it needs to be backed up, and you don't want your backups to become the weakest point in the vulnerability chain. "Linked wallets" with multi-sig/multi-device is still in the works, and this is not a replacement for that. This is simply an alternative to backing up your wallet if you're concerned about physical security. The scripts are in the extras directory. They have been pushed to the master branch. Sorry, this only works if you can run python scripts (possible in Windows, but you have to install all the python packages listed here for windows (http://bitcoinarmory.com/building-armory-from-source/), and copy the .pyd file from the installation directory). Usage: 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: [ANN] "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on March 06, 2013, 05:37:49 PM By the way, TierNolan's comment below simply suggested an optimization to my current implementation of Shamir's Secret Sharing. There is nothing wrong with this implementation (accuracy-wise), it's just that the fragments could have been represented with about 1/2 the amount of data.
Given that this is a temporary solution (for the next few months), I will not complicate it by changing the format or calculations. I did this mainly for myself and wanted others to have access to it. These wallets will be deprecated in a couple months, anyway so I will focus on getting the new features implemented instead (though the code for recombining these fragments will remain in the repo forever). Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: TierNolan on March 06, 2013, 07:15:17 PM It looks like you store the x and the y coords for each fragment.
My understanding is that you don't need to make x complex. You can just store (1, y1), (2, y2), (3, y3) .... (n, yn) That would cut down the number of letters in half. You still can't calculate the y intercept without m points. You could just store it as x<hex of y coord> With base 64, you could have 64 fragments with a single character for x. Also, you can process each byte of the secret independently. There is no need to do large numbers. If you use 257 as the prime, then you can use ints for all your maths. The disadvantage is that sometimes you get 256 as the byte. With hex encoding, that could be written as G0. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on March 06, 2013, 07:21:25 PM That's a good point about arbitrary-ness of the x-coord. I forget why I had originally decided that X needed to be randomly selected. It probably wasn't a very good reason, other than my brain thought of that idea first and never went back and reconsidered it.
On the upside, it could be super-simple to upgrade the script without bothering any one -- the line prefixes are there for a reason. Update the script to use "x:" for new backups, and the new unfrag script will simply read the hex repr of x and expand to 32-bytes if it's there or use x1-x4 if that's there. As for the integer math, it almost seemed like there was no reason not to do it this way, since python has native huge-integer-handling. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: TierNolan on March 06, 2013, 07:24:31 PM That's a good point about arbitrary-ness of the x-coord. I forget why I had originally decided that X needed to be randomly selected. It probably wasn't a very good reason, other than my brain thought of that idea first and never went back and reconsidered it. On the upside, it could be super-simple to upgrade the script without bothering any one -- the line prefixes are there for a reason. Update the script to use "x:" for new backups, and the new unfrag script will simply read the hex repr of x and expand to 32-bytes if it's there or use x1-x4 if that's there. Sounds reasonable. Having random x values doesn't do any harm (unless you pick 0, but that is essentially impossible). Quote As for the integer math, it almost seemed like there was no reason not to do it this way, since python has native huge-integer-handling. It would be faster, but the script is probably instant already. The disadvantage is that the number of shares is limited to the prime value, so with a prime of 257, you can only have 256 shares. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on March 06, 2013, 07:36:19 PM Sounds reasonable. Having random x values doesn't do any harm (unless you pick 0, but that is essentially impossible). Actually, the secret is stored in the highest-order coefficient of the polynomial. So in the case of M=2, the secret is the slope of the line. Then it doesn't matter which points you pick. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: Roy Badami on April 03, 2013, 11:11:41 PM Excellent work. I've just started using Armory and I will certainly be setting up n-of-m soon.
My one criticism is that frag_wallet.py seems to insist on saving all the fragments in the current directory, immediately and without explicit prompting - which is the moral equivalent of writing the private keys to disk. Yes, with appropriate care (full disk encryption, secure erase, etc) this can be mitigated - but it's providing a gun for people to shoot themselves in the foot. If I'm going to go to all this trouble in the first place then I'd much rather save each fragment directly onto its own individual USB stick (which I'd store alongside the corresponding hand-transcribed paper copy of its contents). My FDE is there to protect me from mistakes, such as unencrypted keys getting written to swap, etc. But my aim is never to deliberately write keys to hard disk in the first place. If the unfrag_wallet.py script was similarly modified, then I could still do a test unfrag from my stack of USB sticks, with the unencrypted keys unlikely to ever hit disk. I'm sure I can easily modify the python scripts to do that when I get round to setting up n-of-m backups, but just my 2 bitcents. roy Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on April 03, 2013, 11:19:40 PM Excellent work. I've just started using Armory and I will certainly be setting up n-of-m soon. My one criticism is that frag_wallet.py seems to insist on saving all the fragments in the current directory, immediately and without explicit prompting - which is the moral equivalent of writing the private keys to disk. Yes, with appropriate care (full disk encryption, secure erase, etc) this can be mitigated - but it's providing a gun for people to shoot themselves in the foot. If I'm going to go to all this trouble in the first place then I'd much rather save each fragment directly onto its own individual USB stick (which I'd store alongside the corresponding hand-transcribed paper copy of its contents). My FDE is there to protect me from mistakes, such as unencrypted keys getting written to swap, etc. But my aim is never to deliberately write keys to hard disk in the first place. If the unfrag_wallet.py script was similarly modified, then I could still do a test unfrag from my stack of USB sticks, with the unencrypted keys unlikely to ever hit disk. I'm sure I can easily modify the python scripts to do that when I get round to setting up n-of-m backups, but just my 2 bitcents. roy It's a good observation. I made the same observation myself, when I actually applied it. The problem is, there's only so much I can do with a command line script. This was intended to be a stop-gap measure until I get the new wallets integrated. I will come up with a way to avoid writing them to disk. What I will probably do in the future, with all backup types, is have them print/save encrypted, and you are given a 15-character encryption key to write down and keep with it. It could be disabled, but it would offer a way to print/save the data without worrying about the device onto which the backup goes. Thanks for the feedback. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: Roy Badami on April 03, 2013, 11:26:15 PM It's a good observation. I made the same observation myself, when I actually applied it. The problem is, there's only so much I can do with a command line script. This was intended to be a stop-gap measure until I get the new wallets integrated. I will come up with a way to avoid writing them to disk. What I will probably do in the future, with all backup types, is have them print/save encrypted, and you are given a 15-character encryption key to write down and keep with it. It could be disabled, but it would offer a way to print/save the data without worrying about the device onto which the backup goes. Thanks for the feedback. Actually, what I'll probably do - on further thought - is simply run the script with the current directory being in a ramfs filesystem :-) But I don't know if things are quite as straightforward for Windows users - and it would be good to make it hard for people to shoot themselves in the foot. ETA: although I fully realise this is a stop-gap - and a very welcome one too! Thank you again! Incidentally, do you document any guidelines for setting up an offline system? If you don't already I'd suggest you should recommend FDE as a mitigation for private keys getting written to swap - particularly on Windows which AIUI doesn't have a fully reliable mechanism for locking pages in RAM. roy Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on April 03, 2013, 11:32:18 PM It's a good observation. I made the same observation myself, when I actually applied it. The problem is, there's only so much I can do with a command line script. This was intended to be a stop-gap measure until I get the new wallets integrated. I will come up with a way to avoid writing them to disk. What I will probably do in the future, with all backup types, is have them print/save encrypted, and you are given a 15-character encryption key to write down and keep with it. It could be disabled, but it would offer a way to print/save the data without worrying about the device onto which the backup goes. Thanks for the feedback. Actually, what I'll probably do - on further thought - is simply run the script with the current directory being in a ramfs filesystem :-) But I don't know if things are quite as straightforward for Windows users - and it would be good to make it hard for people to shoot themselves in the foot. Incidentally, do you document any guidelines for setting up an offline system? If you don't already I'd suggest you should recommend FDE as a mitigation for private keys getting written to swap - particularly on Windows which AIUI doesn't have a fully reliable mechanism for locking pages in RAM. roy No, the best I've got is a tutorial (https://bitcoinarmory.com/using-offline-wallets-in-armory/) for after the system is setup. I'm actually working on a kind of "Best Practices" guide. FDE is part of it. If you don't have FDE, the thing to do is use FAT32 partitions so that you can effectively shred files. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: Roy Badami on April 03, 2013, 11:38:37 PM No, the best I've got is a tutorial (https://bitcoinarmory.com/using-offline-wallets-in-armory/) for after the system is setup. I'm actually working on a kind of "Best Practices" guide. FDE is part of it. If you don't have FDE, the thing to do is use FAT32 partitions so that you can effectively shred files. Interesting comment. I was always under the impression that NTFS did data journalling, which of course makes secure deletion problematic (particularly given a very large default journal size). But all the references I can find now suggest NTFS only does metadata journalling, at least by default. Did this change at some point, do you know? Or is there some other reason why secure deletion isn't possible under NTFS that I'm missing? Also, if you have the RAM for it, you might want to consider not having a swap partition/pagefile. roy Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on April 03, 2013, 11:41:43 PM No, the best I've got is a tutorial (https://bitcoinarmory.com/using-offline-wallets-in-armory/) for after the system is setup. I'm actually working on a kind of "Best Practices" guide. FDE is part of it. If you don't have FDE, the thing to do is use FAT32 partitions so that you can effectively shred files. Interesting comment. I was always under the impression that NTFS did data journalling, which of course makes secure deletion problematic (particularly given a very large default journal size). But all the references I can find now suggest NTFS only does metadata journalling, at least by default. Did this change at some point, do you know? Or is there some other reason why secure deletion isn't possible under NTFS that I'm missing? Also, if you have the RAM for it, you might want to consider not having a swap partition/pagefile. For simplicity, users can use the alternate Ubuntu install CD, which has an option for encrypted LVM, and includes encrypting swap. It encrypts everything but the /boot partition. As for NTFS journaling, I actually have no idea. I don't want to gamble on it. But I do know that FAT32 will have the desired behavior. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: jmw74 on April 04, 2013, 02:17:25 AM Glad to see this.
As someone who couldn't see any satisfactory solutions for a cold wallet, Shamir's scheme was a godsend. I am really kind of surprised this isn't standard everywhere. There's really no downside, as far as I can tell. Having a 2/3 sharing scheme is superior in every way to having 2 copies of your wallet. If people are storing just a single copy of their wallet, I think that's insane unless it's a small amount. Even encrypting the wallet doesn't help, because then the password essentially becomes the wallet and you are left with the same problem you started with. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: Roy Badami on April 04, 2013, 08:08:39 PM For simplicity, users can use the alternate Ubuntu install CD, which has an option for encrypted LVM, and includes encrypting swap. It encrypts everything but the /boot partition. Exactly what I used to install my offline machine :-)Quote As for NTFS journaling, I actually have no idea. I don't want to gamble on it. But I do know that FAT32 will have the desired behavior. As does ext3/ext4 with data=ordered, of course, but I assume we were talking about Windows - at least, I assume you're not advocating the use of FAT32 on Linux systems :-Proy Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: etotheipi on April 04, 2013, 08:47:10 PM For simplicity, users can use the alternate Ubuntu install CD, which has an option for encrypted LVM, and includes encrypting swap. It encrypts everything but the /boot partition. Exactly what I used to install my offline machine :-)Quote As for NTFS journaling, I actually have no idea. I don't want to gamble on it. But I do know that FAT32 will have the desired behavior. As does ext3/ext4 with data=ordered, of course, but I assume we were talking about Windows - at least, I assume you're not advocating the use of FAT32 on Linux systems :-PWell you can't use FAT32 as your OS drive in Linux, but you can still use FAT32 partitions in Linux. If you can't use full-disk-encryption, at least you could put your wallet on a FAT32 partition and shred the hell out of any files that are put there. As you mentioned, the SSS splitting does have that problem right now. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: jmw74 on April 26, 2013, 01:57:58 PM For those who are interested, I added this same functionality to bitaddress.org. All I did is pull in the secrets.js library and hook it into the existing bitaddress.org UI.
Source is here https://github.com/weissjeffm/bitaddress.org Demo is here http://weissjeffm.github.io/bitaddress.org/bitaddress.org.html This will split whatever private key you give it. You will have to decide on your own what to do with the shares - print them out, etc. Personally, I'm going to stamp them on sheet metal. The reason I implemented this is other implementations of shamir's don't know what a bitcoin base58 key is, they treat it like any other string. The shares produced end up being way longer than they need to be. When I get some time, I'm going to hook in the QR-code generation so that you can print them to paper and not have to type in 100 or more characters to re-assemble the key. Note: I cannot say whether this is bulletproof in the crypto sense, I'm only using existing libraries. And you shouldn't be trusting code from a stranger without looking at it yourself, to verify the secrets are not copied off anywhere. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: Dabs on October 07, 2013, 07:56:26 AM @jmw74
Hi, can you do this split key thing with compressed keys? The ones where private keys begin with L and K, instead of 5. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: jmw74 on October 16, 2013, 03:01:35 PM @jmw74 Hi, can you do this split key thing with compressed keys? The ones where private keys begin with L and K, instead of 5. @Dabs, the interface I wrote doesn't deal with compressed keys, but it would be easy to implement. It just uses the secrets.js library which is capable of splitting and recombining any secret, not just bitcoin keys. Title: Re: [ANN] M-of-N "Fragmented Backups" now in Armory (command-line only) Post by: QuantumQrack on November 02, 2013, 07:50:28 AM For those who are interested, I added this same functionality to bitaddress.org. All I did is pull in the secrets.js library and hook it into the existing bitaddress.org UI. Source is here https://github.com/weissjeffm/bitaddress.org Demo is here http://weissjeffm.github.io/bitaddress.org/bitaddress.org.html This will split whatever private key you give it. You will have to decide on your own what to do with the shares - print them out, etc. Personally, I'm going to stamp them on sheet metal. The reason I implemented this is other implementations of shamir's don't know what a bitcoin base58 key is, they treat it like any other string. The shares produced end up being way longer than they need to be. When I get some time, I'm going to hook in the QR-code generation so that you can print them to paper and not have to type in 100 or more characters to re-assemble the key. Note: I cannot say whether this is bulletproof in the crypto sense, I'm only using existing libraries. And you shouldn't be trusting code from a stranger without looking at it yourself, to verify the secrets are not copied off anywhere. Wouldn't it be better to make this so that it works with the various ssss implementations out there instead of your specific implementation? Appreciate your work, but this kind of thing needs to be standardized. i.e. I tried recombining two shares to gain the secret on another website..and it didn't work. It only works via yours. |