37

Is it safe to split a private key file and put it in different locations? I mean can somebody actually do anything with only a part of a key?

Steffen Ullrich
  • 184,332
  • 29
  • 363
  • 424
dblouis
  • 493
  • 4
  • 8
  • 4
    Isn't this trivially easy by just deriving two values which when xor'd together produce the key? You could theoretically extend this to any number of values required to be combined to produce the secret. Or am I missing something? – Sandy Chapman Aug 23 '17 at 20:49
  • 61
    This looks like an horcrux – IAmJulianAcosta Aug 23 '17 at 21:39
  • 2
    @SandyChapman Interesting idea! For each 1 in the key, flip a coin for whether the pieces get 1's or 0's; for each 0 in the key, flip a coin for which piece gets the 1. At first glance, seems ok because a 1 or 0 in the key does not lead to a bias in whether you get a 1 or 0 in the pieces, though I think it's impossible to scale that up to a "*k* of *n* pieces need to be present" that all the standard secret sharing algs have. – Mike Ounsworth Aug 23 '17 at 21:50
  • related https://security.stackexchange.com/questions/113597/how-should-i-store-a-physical-written-copy-of-my-password/113607#113607 – Richie Frame Aug 24 '17 at 00:20
  • 1
    If you mean just spreading data required to get the key across your drive, then the attacker instead of locating the key will have to locate the program, which assembles it, and this will immediately lead to stealing the key. So there's really no point in doing that. However, if you plan to use different measures of security for different parts (one part is in truecrypt vault, another on a sheet of paper in the wallet, etc), then of course it will reduce chances of a breach. – Serge Seredenko Aug 24 '17 at 00:34
  • XOR each byte of the private key with a byte of your choosing, then just remember that. – xvk3 Aug 24 '17 at 07:00
  • I was thinking putting each piece on a USB stick and hide them in different locations. But this is not good for another reason: if I cut the key in 5 parts for example, if one stick die, I cannot retrieve the key. I could put 4/5 of the key on each stick so that I can retrieve the key with only two of them, but then there is too much information on one stick and it's too easy too retrieve it, for what I understand. – dblouis Aug 24 '17 at 07:26
  • 1
    @L.DUPRÉBERTONI You _could_ do those things, as long as you're not pretending that you're getting any security from them. Seriously, find a tool that does Shamir's Secret Sharing and use that. It shouldn't be too hard to get set up. – Mike Ounsworth Aug 24 '17 at 12:23
  • [ssss](http://point-at-infinity.org/ssss/) seems really easy to use – dblouis Aug 24 '17 at 12:44
  • 1
    @WillV, unlike the Shamir secret share given in the accepted answer, your scheme falls apart under collusion. If I had a 10 byte key that I'd handed out to 10 of my friends, then any 9 of them could easily just try all 2^8 possibilities for the part of the key they're missing. The Shamir share is not vulnerable to this sort of thing. – ymbirtt Aug 24 '17 at 13:42
  • @ymbirtt Don't use a 10 byte key. All my method requires is the ability to remember a number between 0 and 255. The Shamir's Secret Sharing requies you to have friends. – xvk3 Aug 24 '17 at 13:50
  • @WillV, the 10 byte key was an example. The argument still holds up with a 1000-byte key and 999 colluding friends. The point is that, under your scheme, every share found by an attacker makes it easier for them to recover the result. The surprising property of a shamir share is that an attacker with any number of shares below the threshold has just as much information as an attacker with zero shares. The "friends" are also metaphorical - sharing a key by hiding it in multiple places has the same security properties as handing a share to a number of friends. – ymbirtt Aug 25 '17 at 07:37
  • @ymbirtt I understand your point. However, my initial comment was about securing a private key without sharing it with other people: in which case a single XOR is sufficient. If you do need to share a private key: generate multiple keys that need to be XOR'd together to reveal the private key. – xvk3 Aug 25 '17 at 09:00
  • @MikeOunsworth You have your bits inverted. – marcelm Aug 25 '17 at 15:00
  • As an aside, Applied Cryptography discusses this problem, and is well worth reading. – Charles Duffy Aug 25 '17 at 15:03

2 Answers2

54

Just splitting the file up will not have the desired effect (as A.Hersean explains in their answer).

I think what you're looking for is "Secret Sharing" algorithms, most notably Shamir's Secret Sharing algorithm (thanks @heinrich5991), where the secret is split up into N pieces and given to different people for safe-keeping. To reconstruct the secret, all N pieces (or in some variants, only k of the pieces) need to be brought together. The attacker gains no information unless they have all the pieces.

Although used in many applications, I don't believe it is available in openssl or CAPI. There are many robust open source implementations -- see this question, but you'll need to do some homework to decide if you trust the implementation to not be back-doored.

There is also the related concept of "Multi-party encryption"; where you encrypt the secret with multiple people's public keys, and then all of them need to participate in decrypting it. Here's a SO tread about it:

Encryption and decryption involving 3 parties

You can do a poor-man's version of this using only the RSA implementation you already have by chaining RSA encryption:

RSA(key1, RSA(key2, RSA(key3, secret) ) )

If you want 3 people to encrypt, but only 2 of them need to be present to decrypt, then you can store 3 versions of the ciphertext:

RSA(key1, RSA(key2, secret) )
RSA(key2, RSA(key3, secret) )
RSA(key1, RSA(key3, secret) )
Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • 1
    Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/64340/discussion-on-answer-by-mike-ounsworth-protecting-a-private-key-by-spreading-it). – Rory Alsop Aug 24 '17 at 07:56
39

A private or secret key is not meant to be cut. For example, if someone get hold of half of a symmetric key of 128 bits, the strength of the key would not be divided per 2, but it would be reduced by 18446744073709551616 (= 2⁶⁴). The remaining part of the key could be broken very fast. The same holds for asymmetric key (used by CAs), but the math is more complex.

So do not do it. This will increase the complexity of your solution while reducing its security, because you would have at least two places to secure instead of just one.

A. Hersean
  • 10,046
  • 3
  • 28
  • 42
  • 30
    "Put all of your eggs in one basket- then WATCH THAT BASKET." – J Kimball Aug 23 '17 at 13:49
  • 5
    However, if I generate 128 bits of high-quality randomness, and call it "A", another 128 "B", etc. I can then calculate K xor A xor B xor C = D and give A, B, C, and D to four different people. K can be reconstructed by xoring together the four "parts", none of which is literally a part of the key. Any 1, 2, or 3 "parts" is completely useless. – Monty Harder Aug 23 '17 at 21:50
  • @A.Hersean: The link you offer for XOR sharing being flawed simply says that the random parts have to be _really_ random. That same requirement surely applies to the random upper coefficients used in Shamir sharing, so why is one scheme flawed and the other is not? – hmakholm left over Monica Aug 24 '17 at 13:37
  • 1
    I misread a comment in the link I provided. What I wanted to say is that If an attacker gets a plaintext, its corresponding encrypted text, and all but one key, the attacker can find the remaining secret key. This is an impracticable attack scenario, but it show that the trivial (XOR) algorithm is weaker than those mentioned in Mike's answer. – A. Hersean Aug 24 '17 at 13:46
  • Are you certain your projection to asymmetric ciphers is even correct? While I'll readily agree that knowing half of a 128-bit symmetric key makes brute-forcing feasible (still, having compromised half a key is way better than having compromised the complete key!). Now, brute-forcing half an asymmetric key which is usually around, or upwards of 256 bits is still impossible. On the other hand, how would I do a non-brute-force attack on e.g. multiplying points on an elliptic curve if I do not know the point? It's not like knowing half of a point helps an awful lot, or is it? – Damon Aug 24 '17 at 13:53
  • 2
    @Damon For RSA, it depends of the encoding of the key and which part of the key you get. For ECC I cannot answer you, but that would make a good question for [crypto.SE](https://crypto.stackexchange.com/). – A. Hersean Aug 24 '17 at 14:00
  • I'm sure this is easily answered, but I'm a rookie here. If someone were brute-forcing half a key, how would they know they succeeded? Isn't the idea that there are still ~2^64 inputs which would produce the "top" half of the key? I don't see how reproducing half a hash gives the attacker much information, but I'm sure I'm misunderstanding something. – Lord Farquaad Aug 24 '17 at 21:19