2
$\begingroup$

I am currently learning about secret sharing and I’ve started wondering why larger companies that have access to whole server networks (like – for example – Google, Facebook, etc.) don't use “Secret Sharing” for password storage in addition to hashing and salting.

I know that such companies tend to use many different stages for storing passwords (hashing, salting and encryption in various combinations), but wouldn't more security be achieved by using “Secret Sharing” and storing the resulting shares on independent servers?

The advantage I see is that an adversary would have to have access to at least the threshold number of servers in order to retrieve the hashed passwords. Or am I missing something?

$\endgroup$
  • $\begingroup$ Because cryptography is a pain, and the less of it we can get away with the better. You're proposing something that adds considerable complexity and additional failure modes, and that I suspect gains you very little in the big picture. $\endgroup$ – Luis Casillas Nov 18 '16 at 19:46
  • $\begingroup$ @LuisCasillas Just edited and reopened the question. If you like, you can now post your comment as answer. Sorry for the temporary inconvenience… $\endgroup$ – e-sushi Nov 18 '16 at 19:58
  • $\begingroup$ @LuisCasillas I was just thinking about recent database breaches, where password hashes had been retrieved and wondered why nobody uses "Secret Sharing", since all the theory for implementing such a system exists and it doesn't look too complicated to implement. I could understand if it was just because of the amount of communication between servers, but login requests are only a small fraction of the number of requests a server gets anyway. $\endgroup$ – user41274 Nov 19 '16 at 0:21
4
$\begingroup$

How would such a scheme work? You'd have to:

  • Split the password database (or is it individual entries?) into multiple shares;
  • Distribute those shares across many servers;
  • Have a system for those servers to peer together to reconstruct the password entries;
  • Support live additions and modifications of user password entries. When a user changes their password, this is now a distributed transaction that must succeed or fail atomically (otherwise the user can't log in afterwards!).
  • Make sure that the reconstructed password entries are never written out to disk, or at least not in the clear.
  • Make sure that multiple database shares never get aggregated into the same backups.
  • Other problems I'm probably not considering.

It sounds like a very complex solution. Lots of moving parts and lots of things that could go wrong. Not just in terms of security, but also basic functionality.


And what are we supposed to gain from all this complexity? The idea is that if an attacker steals one share (or fewer than the threshold), they can't mount a brute force attack on the database. But I think that gain is put at risk by the fact that this would be a system of homogeneous, cooperative, automated peers:

  • If an attacker finds a software vulnerability that allows them to steal password shares from one server, there's a high probability that the same vulnerability can be used to steal shares from other servers, because of the system's homogeneity.
  • If an attacker can impersonate a peer, can't they just ask the true peers for the password shares needed to reconstruct the hashes? After all, the peers freely cooperate with each other to hand over their shares.

Maybe there's a way to mitigate the latter by designating, for each password entry, one peer that "owns" it, so that peer will never share its share with any other. But now the idea is getting pretty complex, more so when you throw availability requirements—when a peer goes down, can users whose entries are "owned" by that peer log in anymore? If each entry has a "primary" owner and a "standby" to take over if the primary fails, can we fool the standby into thinking that the primary failed, and does that allow us to bypass the measures?

As a contrast, many applications of secret sharing involve humans who:

  • Are adversaries who are trying to prevent at least some of the others from learning the secret.
  • Store their shares in heterogeneous environments that the others don't control.
  • Store their shares in offline environments where extraordinary measures are required to retrieve them.
  • Come together to reconstruct the secret manually in a carefully regulated ceremony designed to prevent any participants or other parties from learning the secret.

See, for example:


Dropbox recently wrote a blog post detailing their password storage strategy. They articulate a strategy that encrypts every hash with a global AES key, which looks much simpler than what you propose and arguably no less secure in practice. I'll let the quotes speak for themselves:

Finally, the resulting bcrypt hash is encrypted with AES256 using a secret key (common to all hashes) that we refer to as a pepper. The pepper is a defense in depth measure. The pepper value is stored separately in a manner that makes it difficult to discover by an attacker (i.e. not in a database table). As a result, if only the password storage is compromised, the password hashes are encrypted and of no use to an attacker.

[...]

Why is the global pepper used for encryption instead of hashing?

Recall that the global pepper is a defense in depth measure and we store it separately. But storing it separately also means that we have to include the possibility of the pepper (and not the password hashes) being compromised. If we use the global pepper for hashing, we can’t easily rotate it. Instead, using it for encryption gives us similar security but with the added ability to rotate. The input to this encryption function is randomized, but we also include a random initialization vector (IV).

Going forward, we’re considering storing the global pepper in a hardware security module (HSM). At our scale, this is an undertaking with considerable complexity, but would significantly reduce the chances of a pepper compromise.

$\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.