Shamir's Password Store

20 Mar 2021
Progress: Concept

Passwords are a terrible technology for logging-in to websites, and I hope that one day they can be done away with. For now though, the best tactic is to generate random passwords and use a password manager.

A password manager uses one master password, which you remember, to decrypt or release the individual passwords for each service you're signed up to. These individual "passwords" can be long, randomly generated strings.

Third party services are not good enough

A lot of people use a third party password manager service, such as LastPass. The idea of having all your precious passwords stored on someone else's server might be offputting, but the defence is that even if the database were stolen, decrypting people's passwords would not be viable.

The argument goes like this: the password-hashing algorithm is designed to be computationally intensive. By hashing the password repeatedly, this can be extended so that it takes maybe several seconds for the algorithm to run. As computers get faster, more rounds of hashing can be added to the requirement. As a result, it may take a few seconds to correctly verify the master password (a minor inconvenience) but to brute-force guess the password would take years.

All well and good, and many people use this service without worrying. However, there's a subtle point that's been missed here. A rogue employee could potentially steal your master password. It's true that even the employees of the company cannot decrypt your passwords, but they do have access to the source code of their software. Even if the password hashing takes place locally, within javascript or their app, we have no guarantee that their code has not been maliciously changed. It may correctly hash the password, but secretly store or submit the master password through some side channel.

The above situation is unlikely, I'll admit, but the fact it's possible makes me uneasy using a third party password-manager like this.

Local password managers

There are a few clever alternative password managers, but the most common type would simply do the same as the third-party ones but in a self-hosted or entirely local manner.

One such example is Pass, the unix password manager. This has the gimmick / selling point of being nothing more than a bash script that's easily vetted, and depends on GPG encryption. We have a master password, which is used to release the GPG private key, which is then used to decrypt the individual password files. The whole thing is tracked with git and works quite nicely.

The encrypted password files can be stored on a public server without worry, because the encryption algorithm is of our choosing. We can use the strongest available encryption with the longest key. Without the key, those password files become practically undecipherable.

Storing the decryption key then becomes the problem. If we have it on the server, and the server got compromised, the attacker would gain everything they need to potentially access one's passwords. As with LastPass, the best we could hope for is to slow them down, making a brute-force attack take long enough that we can change all our passwords before it succeeds. The problem is if the server was silently compromised. The attacker could brute-force the decryption at their leisure, even if it takes a supercomputer months or years.

So we should keep our decryption key very safe, perhaps only on our personal laptop. But even this has problems – the laptop could get stolen and the thief would have everything. It's also a problem if it merely got lost. The only real defence against losing the key is to print out a physical copy of it and store it somewhere (inconvenient, if you've gone for the longest and most complex key).

I should mention the existence of hardware key dongles, such as the YubiKey. In this case, the hardware dongle holds onto your encryption key and only releases it if a button is pressed immediately before. And, if the password is entered wrong more than a few times, it can lock itself out or delete the key. This does solve many problems, but it comes at a cost of inconvenience.

Desirables

My ideal password manager would behave like this:

• If a server is compromised, or a laptop stolen, the attacker would not have enough data to extract anything useful

• All the data, including decryption keys, is stored in multiple places so that losing one copy does not lock you out of anything.

• No dependency on third party software or servers

• Easy to refresh all or part of the system, if we think it's been compromised

I had been thinking about this for a while and realized there is a way of achieving this.

Shamir's Secret Sharing

Shamir's Secret Sharing is an algorithm for sharing secrets between multiple people or places. The secret is split into multiple parts, and each recipient gets one part. One part on its own is useless, but when all the parts are brought together the original secret can be reconstructed.

In fact, it's possible to arrange things so only a certain number of parts are needed. Unlike most cryptographic algorithms, this one is simple enough to fully explain with a diagram:

The secret is used as coefficients for a polynomial of a certain degree. The parts are the position of chosen points on the curve. To reconstruct the polynomial, a certain number of points are needed.

Specifically, a polynomial of degree n requires at least n + 1 points to reconstruct it.

Building a better password manager

The core of my idea is that most people own multiple devices. I own a phone, several laptops, and have access to a number of servers. I need to access the password manager on at least the laptops and phone. I would like to self-host the password manager – so why not form a distributed hosting between these devices I own?

The passwords themselves would be encrypted as with Unix Pass, so they can be stored in full on each device. Only the decryption key is of concern.

The decryption key would need to be split using Shamir's secret sharing. Let's assume I have five devices, and at least three parts are needed to recover the decryption key. When we need to access a password, our device makes contact with at least two others to collaborate.

Immediately there's a benefit that if, say, my phone got stolen, we could mark that device as blocked, and refuse to share the parts with it. I can still decrypt the passwords using the remaining devices, and when I get a new phone the parts can be regenerated.

There are a couple of details to work out here. First, secure communication between the devices. Public key encryption and certificates are well-established. It would probably make the most sense to generate our own certificates to authorize the devices.

The more subtle problem is ensuring the parts can't be collected unless the right password is provided. Without this, an attacker could steal a device, monitor the network traffic, make one false password attempt and have enough data to hypothetically recover the key.

Details of operation

Assume I need to load up a password on my laptop, and the secret sharing scheme is configured for three parts needed.

1. I enter the master password on the laptop. This is immediately run through a long hashing algorithm. The master password must never be stored or transmitted in plain.

2. The hash string is used to decrypt the related file on the laptop. This contains our part of the secret, and also possibly metadata. If the file fails to decrypt, we know the password is wrong and stop (but much like the "number of attempts" GPG gives you for entering a password, we cannot depend on that for any real security if the device is in an attacker's hands).

3. Contact is made with other devices in the system. In this case, one request is made to a server somewhere, and the other is made to my phone. Details of how it makes contact to the phone don't really matter, just as long as it manages it and an encrypted channel can be established between them.

4. At this point, the phone could notify me of the request and ask permission to continue, functioning like a 2-factor system on steroids. The step isn't needed, but as it's possible it's stupid not to. The request to the server can't have this layer, unless we wanted some complex and cumbersome setup.

5. The laptop now has to convince the other devices to send their parts to it, which means proving the valid master password was entered, but not revealing the password to the other devices, and not receiving even the encrypted secret parts before then. I expect the simplest way to do this is to have another layer of public key encryption, with the private key for this challenge contained in the metadata we decrypted earlier. With this, each device can do a challenge/response passing a token back and forth, until the devices are convinced the password was entered correctly.

6. The server and the phone now send over their encrypted parts of the key.

7. The laptop decrypts the received parts using the password hash, and combines them together to recover the GPG private key. The rest of the password store data can then be decrypted.

Step 5 maybe isn't needed. In fact, we could just send the entered password directly to the other devices and they could approve or reject the request. The connection between them is already encrypted. But I just feel inherently that things are safer if we never let the password leave a device.

The 2-factor on steroids in part 4 is a nice addition, but depending on the number of parts needed vs the number available, it may not add any extra security. An attacker could intentionally block the network request to the phone, making it resort to the other sources. On the other hand, if the other parts are stored on my other laptops, those may not be turned on and networked all the time. For general use, the three parts could be retrieved from the phone, main laptop, and main server, and the other parts only used in those extreme cases where a device is broken or stolen.

We could also add some layer that means at least one device asks separately for permission. Usually the phone would ask for permission and the main server would not, but if the phone is down, another part could be retrieved from a backup server, but its configuration would force permission to be asked, possibly by email. This would be inconvenient, but it's only meant to be a backup server when my phone isn't working.

Summary

I really like this idea, fundamentally it seems like a better concept than any other system.

I'm tempted to build a working prototype, but I expect there are a lot of annoying details to figure out, such as everything involved with the phone. The initial connection would most likely need to ping off another server, which is tedious. Also, Android/iOS development is just pain.

If anyone else is enticed by this idea and has the skills and motivation to make it happen, let me know! I am open to collaboration.