12

I have a private key and I want to store a paper version of it. I would like to split it in 2 equal parts (first 32 numbers and last 32 numbers) and store them in 2 different locations. Let's assume I'm 100% sure no one can access both parts, but it's possible that someone can steal one of them.

How much am I compromised?

To explain the question: I understand the attacker needs to guess only 32 hexadecimal numbers instead of 64 to complete the private key. Is that so much easier than guessing 64? Does this seriously undermine the security of my account? And is there something I'm missing that makes it even easier than guessing the remaining 32 numbers (ex: given the first 32 numbers only a possible subset of all remaining 32 numbers is possible due to some constraint)?

AnotherUser
  • 223
  • 2
  • 8

2 Answers2

14

For a numbers of 64 hexadecimal digits, there are 16 ^ 64 = 115792089237316195423570985008687907853269984665640564039457584007913129639936 possibilities.

For a numbers of 32 hexadecimal digits, there are 16 ^ 32 = 340282366920938463463374607431768211456 possibilities.

If someone has half your private key, your security has been reduced by a factor of 340282366920938463463374607431768211456. That's a large factor, but the amount of possibilities they would need to check to brute-force your wallet is still giant. They probably still wouldn't be able to break in.

However, to prevent any loss of security if one piece is compromised I would recommend a different scheme, for example:

Generate another random 64-digit hexadecimal number, different from your private key. XOR this new number together with your private key. Now, store the new random number and the result of the XOR operation in the two different locations.

To retrieve your private key, you would need both of the pieces and XOR them together. This way, your security is not compromised at all if someone has some but not all of the pieces.

You can use this same scheme with any number of pieces.

Just be sure you do it right :-)

Jesbus
  • 10,478
  • 6
  • 35
  • 62
  • I was about to answer and propose to xor as you did. So I confirm xoring is the best way to go. To add security you can also add some random in your private key by adding some random numbers in it at known places before xoring. Remember the places somewhere else and then you'll have a 3 part protection. Random, xor result and positions. Store each part multiple times in different places. Never store 2 parts in the same place. Then remember the places where you stored them... – Nicolas Massart Nov 01 '17 at 12:41
  • Ty for the answer and the additional suggestion of using XOR. Do you have any similar solution for passphrases where we use ascii chars? (example: bip44 valid passphrases, where number and length of words may differ) – AnotherUser Nov 01 '17 at 13:07
  • You can xor anything even ASCII. Everything is bits after all. You can have a look at this website: http://xor.pw – Nicolas Massart Nov 01 '17 at 14:03
  • @AnotherUser also to have constant length simply add spaces or zeros. I guess that's what they do in the site I linked. Try to xor an ASCII like "hello" with an hex like 123456789 which is longer and then xor this result with 123456789 again and it will give your hello back. – Nicolas Massart Nov 01 '17 at 14:06
  • 1
    the problem with this approach is that apply XOR on ascii chars usually results in non standard chars output – AnotherUser Nov 01 '17 at 14:11
  • 3
    If you want to generalize this into "hide X pieces and only need to recover X-N to recover the key," you could look into Shamir's Secret Sharing (and software that performs it). This would allow you to lose a few of the papers, at the cost of slightly more work recovering it. – thirtythreeforty Nov 01 '17 at 15:03
  • @NicolasMassart You might as well keep it simple and just do a second XOR. It's just as secure (otherwise it's just security through obscurity.) – corsiKa Nov 01 '17 at 18:47
  • @corsiKa the goal is to add "another piece to know" but yes you can do another xor it will add another piece to the puzzle. – Nicolas Massart Nov 01 '17 at 18:53
  • @AnotherUser Encoding it to Base32 would be a good second step after the XOR if legibility is a concern. Crockford's Base32 scheme is one that I am considering myself for this purpose. – BlueBuddy Nov 01 '17 at 21:17
8

How much am I compromised?

More than the simple analysis would suggest.

The private key is used as an ECDSA key. It turns out that, for a private key with n bits unknown, it's possible to recover the entire key in 2**(n/2) time.

With n=256 (that is, you don't know any of the bits initially), this is 2**128, which is generally assumed to be too difficult for anyone.

However, if you give the attacker half of the key (and so have n=128), well, this means that recovering the rest of the key is 2**64 time; this is certainly nontrivial (and so you wouldn't have to worry about anyone solving that on their laptop), however this would be practical for large, well funded adversaries.

Hence, I would certainly go with Jesse's suggestion of doing an xor rather than a simple concatenation; that way, the attacker learns nothing from one piece of the secret.

Jesbus
  • 10,478
  • 6
  • 35
  • 62
poncho
  • 181
  • 2
  • Does the attacker have to know which bits are unknown? For instance, if I have 01 from a 4-bit key, do I have to consider 01xx, 0x1x, 0xx1, x01x, x0x1, and xx01 separately, or does the 2**(n/2)-time algorithm account for unknown position? – chepner Nov 01 '17 at 18:15
  • @chepner: the 2**(n/2) algorithms (at least, the ones I know about) do assume you know the positions of the known bits. Also, I feel I should highlight that those algorithms don't work against general keys (e.g. AES keys); it's because it's specifically an ECDSA key that makes it possible (and the attacker can use some relations that occur because the underlying EC curve forms a group) – poncho Nov 01 '17 at 19:21