1

This will be a long one.

Here's the thing: I want to build a privacy-preserving system where the user data is not even accessible to the database administrator.

Intuitively, I immediately thought of simply using AES to encrypt user data with their own password and hashing their username so that an attacker with access to my database would need to brute-force the password for the encrypted data to get the info and then brute-force the username to maybe get an idea of who the decrypted data is about.

This would be great but leads to the problem of forgotten passwords. If one forgets their password they could reset it by providing the correct username or recovery email (also hashed), but they could not get their data back. ProtonMail, for instance, claims your data is safe even from them, but you cannot recover your emails if you forget your password.

I then started looking at secret sharing and came across Shamir's secret. My question therefore is: Is the system I propose below worse than simply storing data in plaintext with obfuscated (hashed) usernames?

I understand that:

  1. Security does not come with complexity
  2. This system will not be entirely flawless

However, I just want to know if it is any better than a much simpler solution. Because as long as it is equally easy/hard for a hacker but harder for the database admin to gather any info from the data, it would be worth it for me.

It is "complex" because it is the only system my mind has currently come up with that allows for data encryption + somewhat simple recovery protecting data from hackers and admins. I would also happily take suggestions for other implementations.

So here we go.

The proposed system would use Shamir's secret to encrypt the user data with k=6 and n=11 so that 6/11 parts are needed to decrypt the data. User information would then be given a "weight" and utilized to store a proportional number of parts in an encrypted manner. Something like this:

Weights

  • Username: 2
  • Password: 4
  • Email: 2
  • Security Question 1: 1
  • Security Question 2: 1
  • Name + Date of Birth: 1

Based on those weights, the following is done to the user's private data (pseudocode):

SHAMIR(user_data, k=6, n=11)

This will produce something like a uint8 array with length=11. Let's call that array parts.

The database would then use symmetric encryption (let's say AES) to store these parts as follows (only the resulting ciphertext is stored):

{
  username: AES(key=username, message=parts[0:2])
  password: AES(key=password, message=parts[2:6])
  email: AES(key=email, message=parts[6:8])
  seq1: AES(key=answer, message=parts[8:9])
  seq2: AES(key=answer, message=parts[9:10])
  id: AES(key=name+dob, message=parts[10:11])
}

Login would then happen with the traditional username+password or email+password, such that the user will be authenticated/logged in if the data is decrypted correctly. Both combinations give access to enough parts (6) to decrypt the data. From the user perspective, it's all the same as everywhere else.

Then, user forgets their password. Well, now they need to find an alternative way to gather the 4 "points" provided by the password. So they would click "Forgot Password", and a form would pop up with all the possible fields to fill in. They must then fill enough to gather 4 more parts (in addition to username or email) in order to decrypt their data. For example:

username (2) + email (2) + seq1 (1) + namedob (1) = 6

(Email verification could also be implemented)

So now the user has 6/11. Server decrypts the data, user sets a new password, data is re-encrypted, and all the fields are updated with the new parts. By definition, a user who forgot their password will have accumulated a minimum of 10 out of 11 "points" after password reset is complete (The 6 points they provided + the 4 from the new password). Therefore, 1 point could be missing. Given that the user cannot provide that last point, they can be prompted to add a new security question, at which point all is back to normal.

So, in conclusion:

I know all parts of the secret being in the same place is not great, nor is it great to use AES with low-entropy secrets.

However, this should add some security, no? To get the data, an attacker would have to brute force at least a password and a username, or, to not brute-force the password, would have to brute-force quite a bit of other data. It isn't perfect by any means, but it's better for data privacy than the standard, no? What am I missing? Assuming it's implemented perfectly and it works as intended, is it possibly worse than how companies treat our data today? For most, a database breach means the data is already out there, only the password has to be brute-forced, right?

Lastly, could these objectives be achieved in any other way?

That's it. If you've read until now, thank you. Please go easy on me.

Cheers.

EDIT: I'm also thinking somewhat about UX here. The entropy of the data used to store the parts is definitely low, but giving users a higher-entropy "random recovery code" or something would be problematic from a UX perspective.

  • If you are providing a service where each user only ever needs to see their own, user-generated data, great. But most services aren't like that. For example if you're Google and you want to provide suggestions based on people's searches, how are you going to do that if you don't know what they searched? If you're Facebook and you want to share people's photos with large groups, how are you going to do that if you can't see their photos? At that point you would need specialized crypto algorithms tailored for each individual feature that you want to provide, which is extremely difficult. – tlng05 Apr 26 '20 at 2:02
  • Yes, I understand that. I do believe there's ways to provide a useful service and even some personalization with this degree of privacy, but this is a conversation I'll leave outside of the thread. I'm happy to talk about it in private if you want! Now, from a privacy/security perspective, what's your take? Does it work? – Yakko Majuri Apr 26 '20 at 2:13
  • 1
    In your case, the username is already 2 parts of the secret. Do you really consider the username a secret? And if so, how do you perform a login? – user2313067 Apr 26 '20 at 5:21
  • Usernames in the traditional sense aren't great secrets because we share them around. But this would be for a non-interactive platform. Although you are correct. Usernames aren't great, but the point is to find an ideal breakdown of weights, so that if one has username and no password, they need enough of other data to login. Whatever I say above are just arbitrary numbers I made up. The point is to have a balance between password access and non-password access. Ideally they would be "equally as hard", even if my post above does not reflect this very well. – Yakko Majuri Apr 26 '20 at 12:39
  • Regarding login, it would go something like this (pseudocode): 1. username_parts = AES.decrypt(ciphertext1, username) 2. password_parts = AES.decrypt(ciphertext2, password) 3. username_parts.split() 4. password_parts.split() 5. decrypted_data = SHAMIR.decrypt(cipher, username_parts.join(password_parts) 6. if (decrypted_data.header.valid): login() If the decryption does not occur correctly, the data header property wouldn't be available, so the data would remain locked and the user would not log in – Yakko Majuri Apr 26 '20 at 12:39
1

The idea of Shamir’s Secret Sharing is that there are multiple parties independent on each other that know part of the secret. Where as in your case there is a single party, i.e. your server. This is like to say that some file is protected by password and keep the password together with this file.

If you want to implement Shamir’s Secret Sharing, then after user provided new password, you should generate secret parts, present them to user, and user should ask different persons to keep these parts for him. In your case this should be 11 persons. Otherwise you should not use words Shamir’s Secret Sharing.

To security: One should review many different aspects. I'd like to point to one thing only. Think of Kerckhoffs's principle. You should assume that an attacker knows all your algorithms and has a copy of all your server data. That's why in my opinion your scheme has just obscurity and actually no security that you expect.

Update

  1. According to Kerckhoffs's principle you should expect that the attacker knows username, Email and similar values which are not a part of the secret.

  2. A secret is reliable if it is random. Any security questions that are related to person life have very limited set of values and that's why give only a small number of bits of entropy. Because of small entropy they can be brute-forced much more easily than random values.

  3. Even if you want to use security questions (despite their weakness), use them directly. All other manipulations that you described don't add any security.

Security should be based on something that one knows (of course it should have high entropy) or that one has or that one is.

You are going to use AES. It is resistant to brute-forcing. But what you suggest is essentially weaker: Brute-forcing 2 security questions, birth date etc. is much more easier than brute-forcing AES.

There is no magic solution. Either you provide high security and users are responsible for their passwords. Or you provide very low security and for users their passwords. You can do both. But you should not implement the 2nd (low security) and tell your users that it is the 1st (high security).

  • Indeed, I'm aware the parts should be independent, but I'm wondering about tradeoffs here. The simplest and perhaps best way would be symmetric encryption. Password is forgotten, data is lost. Now, with what's proposed above, and I am thinking of Kerckhoffs's principle here, it is definitely better than storing data in plaintext, and it's probably worse than symmetric encryption. But where along that spectrum is it? How much easier is this to break than symmetric encryption? I'm trying to find the sweet spot between privacy and data recovery. – Yakko Majuri Apr 26 '20 at 12:27
  • The idea is that this process could be known, no problem. So I'm trying to brainstorm about the attack. Well, going the route of brute-forcing the password would be harder than with symmetric encryption because you need to bruteforce the password and email or username. What about the other route? Attacker would have to bruteforce Security Question 1, username, name, date of birth and security question 2. Some of these are easy to get, but how easy is it to get them all is my theoretical question here. – Yakko Majuri Apr 26 '20 at 12:30
  • @YakkoMajuri: See update. – mentallurg Apr 26 '20 at 13:08
  • Right. One point I want to make is that whatever I'm proposing is theoretical, and everything used in the question is merely arbitrary/for example purposes. So, perhaps the values I'm suggesting are too weak. But what about a theoretical system where achieving the 6 parts is as difficult irrespective or route. For example, username + password, or in the case of a forgotten password, username + entropy-equivalent values. I understand that one will naturally be easier than the other by definition, meaning it is inherently worse than just having one, but again, it's a tradeoff – Yakko Majuri Apr 26 '20 at 13:37
  • 1) If by entropy-equivalent values you mean security question with appropriate entropy: This would basically mean not question like "Street name you were born in? - High street 123" but "Restore password 1? - KJUaPATnncPC5wXs". If password is randomly generated, of course user cannot remember it and will keep it somewhere. Mean, very probably he will keep all his passwords together. If he lost his main password, then very probably he has lost all his passwords. A solution? For instance, password manager as software or as hardware like YubiKey or Titan. – mentallurg Apr 26 '20 at 14:03

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.