2-of-3 Paper Wallets

[etotheipi]

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.

[etotheipi]

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:

• It's a lot of data
• I am going to be reworking the backup system with the new wallets... I don't want to re-write it twice in order to support fragmented backups now, and then do it again later for the new wallets
• I don't want to end up with even more versions of backups that have to be supported in the restore-paper-backup dialog

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?

[13Charlie]

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.

[ben-abuya]

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.

[etotheipi]

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!

• Create M-of-N fragmented backup, for any value of N, and 2<=M<=8
• Works with any Armory *.wallet files, encrypted or not (will prompt for passphrase if encrypted)
• Creates N text files that can easily be opened and printed (sorry, no QR codes from terminal)
• Deterministic fragments means you can re-print lost fragments, or create more later (increase N)
• The git-commit version is put in the text file, in case you want to know exactly what version created it
• Error correction up to one character per line.  Identifies which file&line has 2+ errors that can't be corrected automatically.
• Use the "unfrag" script right after "fragging" to test recombining various subsets of fragment files (for your own peace of mind)
• Endless error checking to make sure you get it right, or know what you did wrong.

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
$ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt --test
$ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt

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

********************************************************************************
* Executing wallet-fragmenting script.  Split your Armory wallet 
* into N pieces, requiring any M to recover the wallet.
********************************************************************************

Found hash of current git commit: cf8ebe7cecf4bbd0457e8f984354aabb6e869e66
Here is the paper backup information for this wallet.

   Root Key:   hrfr dejf snwf rtun rtin dhri snor aihd wiut
               otjf osws teaa gjei ihoa ffaa fojn swng tusg
   Chaincode:  kwig jorj agtj ragt kwrn dnhf ojgw tkwg snti
               hdst aurh osfj ajhd nwra ogdd dsiw saff fwra

Will create 3-of-5 fragmentation of your paper backup.
Continue? [Y/n]: y
About to create the fragments.  Any other info/identifiers you would 
like to add to each of the fragment files?  Enter it on the next line: 
(Enter info or leave blank): This fragment belongs to forum user etotheipi     

Fragment 1: wallet_2QQkCkdt_frag1_need_3.txt
    ID: 0301 02d1 93af fa6f
    x1: aiow gnrr haaj hthf hsnf rskj tooi kjta ajuf
    x2: jgto kgir ekgs whod kdkr rwsr hase jdui irdh
    x3: rugh hoas sghk sowr esdj kgnw hihe jnri jehu
    x4: eagt fair gjan ifwd retd ewnd aofu gnur jdut
    y1: owrn sowu nfrw oeeo gggs ikkw feii ueja hwns
    y2: aogt osig wonk jkis fkur gfhk kowt gwdu tter
    y3: eats akge jeot rdug oeki frgd onia einn rddj
    y4: dkfj nsed tijj nfkn dkne nieu ittf gnrg gkhj

Fragment 2: wallet_2QQkCkdt_frag2_need_3.txt
    ID: 0302 02d1 93af fa6f
    x1: fadf gtko nwii gfwd nogk osak jodn tess dgdt
    x2: wris jthf kgdu jiwj jeho suii ugnw rewd rtoi

...

Fragment 5: wallet_2QQkCkdt_frag5_need_3.txt
    ID: 0305 02d1 93af fa6f
    x1: hfte nufh utis sseh aweu jkgw ugno iaow kdue
    x2: nkwo ndsw jief taar tfrg kejn knwg tfkt akuw
    x3: ofat fgui iwsk eofg toeo widn gwnh hauk knhg
    x4: ugut wfww rfon kdkg uddi rutn nefh ftid iorn
    y1: oerh rdie rnth dnda iaws ateg utaf drhh grnu
    y2: hrte iaoh khwa jrfa dfeh doej usit infh fjhj
    y3: uije nsga suod jiid sjau rhwh swsg rfgn gwud
    y4: nwnd eheo issg tdrw kdei fhoj joun iuit jirf

NOTE: If you rerun this fragment script on the same wallet
      with the same fragments-required value, M, then you will
      get the same fragments.  Use this to replace fragments,
      or using a higher N-value to produce more pieces (but you
      MUST use the same M value!)

Each file looks like the following:

Code:

Wallet ID:   2QQkCkdt
Create Date: 2013-Mar-06 12:29am
Git Commit:  cf8ebe7cecf4bbd0457e8f984354aabb6e869e66
This fragment belongs to forum user etotheipi

This Fragment:     #1
Fragments Needed:   3
Fragments Created:  5 (more fragments may have been created later)


The following is a single fragment of your wallet.  Execute 
the reconstruction script with any 3 of these fragment files 
in the execution directory to recover your original wallet.
Each file can be reconstructed by manually typing the data 
into a text editor.  Only the following 9 lines (with prefixes)
are necessary in each file.  All other data can be omitted.

ID: 0301 02d1 93af fa6f
x1: aiow gnrr haaj hthf hsnf rskj tooi kjta ajuf
x2: jgto kgir ekgs whod kdkr rwsr hase jdui irdh
x3: rugh hoas sghk sowr esdj kgnw hihe jnri jehu
x4: eagt fair gjan ifwd retd ewnd aofu gnur jdut
y1: owrn sowu nfrw oeeo gggs ikkw feii ueja hwns
y2: aogt osig wonk jkis fkur gfhk kowt gwdu tter
y3: eats akge jeot rdug oeki frgd onia einn rddj
y4: dkfj nsed tijj nfkn dkne nieu ittf gnrg gkhj

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

********************************************************************************
* Restoring wallet from 3-of-N fragmented backup! 
********************************************************************************

Recovered paper backup: 2QQkCkdt

    hrfr dejf snwf rtun rtin dhri snor aihd wiut
    otjf osws teaa gjei ihoa ffaa fojn swng tusg
    kwig jorj agtj ragt kwrn dnhf ojgw tkwg snti
    hdst aurh osfj ajhd nwra ogdd dsiw saff fwra

Testing reconstruction on 20 subsets: 
   Using fragments (0,1,3)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (2,3,4)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (1,3,4)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (1,2,3)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (0,1,2)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (0,3,4)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (0,3,4)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (2,3,4)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   Using fragments (0,2,4)  Reconstructed (first line): hrfr dejf snwf rtun rtin dhri snor aihd wiut
   ...

Recover the wallet:

Code:

$ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt

********************************************************************************
* Restoring wallet from 3-of-N fragmented backup! 
********************************************************************************

Recovered paper backup: 2QQkCkdt

    hrfr dejf snwf rtun rtin dhri snor aihd wiut
    otjf osws teaa gjei ihoa ffaa fojn swng tusg
    kwig jorj agtj ragt kwrn dnhf ojgw tkwg snti
    hdst aurh osfj ajhd nwra ogdd dsiw saff fwra

You have supplied more pieces (5) than needed for reconstruction (3).
Are you trying to run the reconstruction test instead of actually 
recovering the wallet?  If so, wallet recovery will be skipped.  [Y/n] n

Proceeding with wallet recovery...

Would you like to encrypt the recovered wallet? [Y/n]: y
Choose an encryption passphrase:
   Passphrase: 
        Again: 
Set the key-stretching parameters:
   Seconds to compute (default 0.25): 2
   Max RAM used, in MB (default 32):  16
Creating new wallet...
Please wait while the address pool is being populated....
Created armory_2QQkCkdt_recovered.wallet

Exhaustive error catching and useful information

Code:

$ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt --testnet
ERROR: Some files are duplicates!
   wallet_2QQkCkdt_frag1_need_3.txt is 	 Fragment 1
   wallet_2QQkCkdt_frag2_need_3.txt is 	 Fragment 1
   wallet_2QQkCkdt_frag4_need_3.txt is 	 Fragment 4
Aborting

Code:

$ python unfrag_wallet.py wallet_2QQkCkdt_frag*.txt --testnet

********************************************************************************
* Restoring wallet from 3-of-N fragmented backup! 
********************************************************************************

(WARNING) armoryengine.py:1235 - ***Checksum error!  Attempting to fix...
(WARNING) armoryengine.py:1259 - Checksum fix failed
ERROR:  Uncorrectable error
        File:  wallet_2QQkCkdt_frag1_need_3.txt
        Line:  y2

[ben-abuya]

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.

[nimda]

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.

[etotheipi]

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.

[nimda]

...

I assume you're talking about trying to create "A or (B and C)"  backups

Yes. The logic symbols are just shorter (and are part of my AltGr layout).

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 post

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π

[picobit]

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?

[etotheipi]

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.

[picobit]

 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.

[etotheipi]

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

[DBordello]

Would it be possible to get the dependencies for these scripts included in the offline Ubuntu bundle?

[etotheipi]

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.

[DBordello]

I can't wait! 

Excellent work.  These scripts are what pushed me over the edge to switch to armory.

[DBordello]

Has there been any progress on updating the offline bundle to support these scripts?

[etotheipi]

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). 

[DBordello]

Deal