I have a few servers and machines that I regularly login to, so I was wondering if it was possible to secure them using a version of Shamir's Secret Sharing.

I thought if I could split my private key into a number of pieces, then distribute those pieces among each of the computers I use each day as well as a USB stick. This way I could move the USB stick from computer to computer, and each time I plug the USB stick into a new machine the number of pieces of key present would be enough to reconstitute the private SSH key.

Forgive me if this isn't making much sense, I may have completely misunderstood how this system works!

Is this possible, and can anybody help me get started with this problem?


Edit: For clarification, my thinking was that it should only be possible to administer my remote servers from the two machines in my house. The private key would be split up into a number of parts with each of the two machines in my house having a section of the key, I would also place a section of the key on an SD card.

That way, when the SD card is plugged into either of the machines the threshold is reached and the private key can be reassembled and used. However, I think I've misunderstood this secret sharing and its usefulness in this situation.

Thanks again!

  • I'm not sure what you're benefiting from doing something like that. SSS would be better at doing something like sharing a secret with 10 of your friends, and requiring that 5 of them get together in order to be able to retrieve the secret key. – JZeolla Jan 24 '14 at 20:28
  • You may also be interested in github.com/cloudtools/ssh-cert-authority , a certificate authority for ssh that can require several people to approve a request. – Xiong Chiamiov Feb 19 '16 at 0:04

Shamir's Secret Sharing is a nice algorithm to split a secret value into several pieces, and allow recovery with a threshold; meaning that you split (for instance) the secret into ten shares, such that any three shares are sufficient to rebuild the secret.

This calls for two comments:

  • The algorithm's main advantage is its threshold mechanism; it does not make much sense if all shares are needed to rebuild the secret. In the described scenario, with SSH keys, it is unclear what this threshold mechanism would mean. There is a scenario where you want something like that (I have seen it deployed in production; see below) but it involves several key owners.

  • Though the shares are separated, the rebuilding process must occur, by necessity, on a single machine which obtains, at some point, the secret itself. In particular, if you do the reassembly on a machine which is evil (i.e. which is under the control of an attacker through some subreptitious malware), then the attacker learns the SSH private key, and you lose.

The scenario where the threshold mechanism with SSH makes sense is the following: there is a very sensitive server somewhere (a Certification Authority), which must never be administered by a single administrator without any witness. However, the server is remote, and some remote administration must still take place. So the idea is to have a special private key, authorized for root login (the public key is in /root/.ssh/authorized_keys). The corresponding private key should be accessible only on a machine which is assumed safe (a machine dedicated for the task and kept safe through normal mechanism -- in that case, a Linux system with sane sysadmin procedures). When remote administration must take place, a quorum of key owner collaborate, enter their "shares" on the machine, and thus unlock the private key. They keep the sysadmin under eye control for the whole duration of the administration procedure.

In that scenario, a secret sharing scheme would make sense. However, the "shares" are big numerical values, which must be stored on physical devices, not in human brains; this was inconvenient. Moreover, usual SSH client software does not allow for plugging arbitrary secret sharing systems (not easily at least). So the practical solution was the following: the private key was stored several times, each time protected by a password split into two halves; each human knew only one half. If there are n share owners, then the private key must be password-encrypted n(n-1)/2 times (so with n = 5, this means 10 copies of the private key, each encrypted with a combination of two password halves). When remote administration must take place, two key owners select the corresponding encrypted private key file; each owner types his password half, and the connection occurs.

The system works in practice. It does not scale well (with n key owners and a quorum of t, it requires O(nt) encrypted files, for all combinations), but for small values it is perfectly workable.

  • Slight side question (sorry for hijacking this a little) - is this similar to the concept of Lagrange polynomials, whereby given n-1 points on the curve (where n is the number of terms in the polynomial) you can calculate another target point? – Polynomial Jan 24 '14 at 22:14
  • 1
    Shamir's Secret Sharing is defined with Lagrange's polynomials, precisely: there is a unique polynomial of degree at most t-1 which goes through t given points, and it is rebuilt as a linear combinations of Lagrange's polynomials. When the secret is shared, a random polynomial P of degree at most t-1 is generated, such that P(0) is the secret. Then user i receives share P(i). Any t shares are enough to rebuild P and recompute P(0). – Tom Leek Jan 24 '14 at 23:39
  • Excellent, thanks. I figured Lagrange polynomials might be involved in some way, though I didn't expect it to be so direct. – Polynomial Jan 25 '14 at 0:12
  • Excellent answer, thanks for clearing that up. My thinking was that it would only be possible to administer my remote servers from two machines, each having a different section of the private key. I then have an SD card which contains another section of the private key, and when this card is plugged into either of the machines the threshold is reached and the whole private key can be recovered. – robotsandcake Jan 25 '14 at 13:23

You can use gfshare for this: http://manpages.ubuntu.com/manpages/bionic/man7/gfshare.7.html

If you have N computer and 1 USB stick, you would create a 2-of-(N+1) sharing scheme meaning that you would get 7 N+1 splits, and you only need 2 to recreate the SSH key.

gfsplit -n 2 -m 7 .ssh/id_rsa

Then you would copy one different per computer / stick.

To use it, you would do

gfcombine id_rsa.1 id_rsa.2

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.