1
$\begingroup$

I'm developing software that will use public key encryption as part of its user identification, verification and data ownership processes. Assume that I have the user experience side of things worked out and that what I propose will work well within the design of my application; the question I have here is purely about the security side of things.

Private key loss is an awful thing to bear, if it means total loss of access to your data. You can print it out and store it somewhere safely, or put in a USB key and put that in a safe, or whatever, but the average user is not going to do these things. They don't understand security, and they won't usually make the effort to cover their bases. Even if they do, they may forget where they saved or stored their key, or they may lose it for other reasons.

My question is as follows:

Assume there is a network of people who know each other closely enough that they can pick up the phone (or Skype, etc.) and have a voice conversation. Am I missing any glaring security problems with the following?

  1. On my local machine, my private key is divided into 3 parts. The key ABCDEFGHIJKL... becomes ADGJ..., BEHK..., and CFIL....
  2. I select 3 people in my network (preferably each selected from a distinct social group that doesn't really overlap with the others), and encrypt one of the pieces of my private key with their public key.
  3. I send each respective encrypted piece of my private key to the person whose public key I used to encrypt it, and it is stored in their local data store.

Catastrophe strikes! My private key is gone!

  1. I generate a new temporary key pair.
  2. I ask each of my 3 friends to decrypt their piece of my old private key and re-encrypt it using my temporary public key, then send the newly-encrypted version back to me.
  3. I decrypt each of the three pieces and rebuild my private key.

I now have access to my data.

The solution sounds convoluted, sure, but as I said earlier, I have a way to handle the UX for this in a reasonably frictionless way.

The only issue I can think of is that a friend may lose access to their own data and then I'll be out of luck, but to mitigate that as an issue, I'll hedge my bets and perform the same process with different groups of 3 people.

Other things:

  1. "3" is not set in stone, and can be adapted depending on the user's network size.
  2. A user could leverage a service that uses 2-factor authentication as a stand-in for one of their friends. e.g. I could store one of the pieces unencrypted (but obviously useless in isolation) in my 2-factor-secured GMail account.

Can you see any issues with my approach, and if so, what could I do to achieve the same result in a more cryptographically-secure way?

$\endgroup$
  • 1
    $\begingroup$ Don't split this way. Use proper secret sharing mechanisms (ie SSS or XOR-based). $\endgroup$ – SEJPM Apr 24 '17 at 16:11
  • $\begingroup$ Splitting your key by just splitting into partial strings (doesn't matter if it's every 3. symbol or consecutive symbols) is a terrible idea, because you hand out actual information about your key - to them and to everyone who compromises their system. I suggest looking into secret sharing schemes (e.g. Shamir's secret sharing), so that at least no one with less than 3 shares can't recover any information about the key. But still, the security of your key becomes dependent of the other parties keeping your key secure and not be malicious. And of course you need a stragety to change your key. $\endgroup$ – tylo Apr 24 '17 at 16:12
  • $\begingroup$ @tylo Thanks, I'll look that up. I assume you're saying it's less secure not from the perspective that the partial key is useful on its own, but that it can be used to reduce the brute force workload by 1/3? $\endgroup$ – Nathan Ridley Apr 24 '17 at 16:15
  • $\begingroup$ Actually there are attacks (IIRC) that can efficiently recover a full RSA private key given enough bits of the private key, I think the threshold was like 1/3 of the bits. $\endgroup$ – SEJPM Apr 24 '17 at 16:17
  • $\begingroup$ I've edited that part in the comment. With your idea brute force becomes an issue, with secret sharing not so much. But your security depends on their system not being compromised and key management/storage is a much more common security weakness than encryption being broken (if using proper implementations of current encryption systems) $\endgroup$ – tylo Apr 24 '17 at 16:19
4
$\begingroup$

Splitting your key by just splitting into partial strings (doesn't matter if it's every 3. symbol or consecutive symbols) is a terrible idea, because you hand out actual information about your key - to them and to everyone who compromises their system.

For RSA this is actually a real problem, because partial knowledge of the private key makes Coppersmith's attack possible. In the original attack the known bits had to be either the least or most significant bits, but the attack has been refined quite a bit. For example, Reconstructing RSA Private Keys from Random Key Bits by Heninger and Schacham (2009) just need a fraction of $0.27$ random bits of the private key and a small exponent. In that paper the related work section gives a good overview over previous works.

As a refinement for the splitting: I suggest looking into secret sharing schemes (e.g. Shamir's secret sharing), so that at least no one with less than 3 shares can't recover any information about the key. But still, the security of your key becomes dependent of the other parties keeping your key secure and not be malicious. And of course you need a stragety to change your key and update their shares. Reasons for this might be that you want to change the list of trusted persons, one of them lost all the date on their computer, etc.

In general, the dependency on their security is a practical issue: If you use proper implementaions of current state-of-the-art encryption schemes, it is much more likely that key management and storage contains a security weakness than the actual encryption.

Regarding the last part: If you worry about one friend loosing his data at the same time as you (roughly the same time, before you could redo the splitting process), secret sharing schemes can be set up so that you need $k$ out of $n$ shares to recover the key. And it doesn't matter which $k$ of those $n$ shares you use.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.