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.
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.
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.
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.
I had been thinking about this for a while and realized there is a way of achieving this.
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.
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.
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.
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.