1

In my database, I would like to encrypt every identifiable piece of information, including the username, such that people with access to the database cannot deduce the actual username (because it could potentially indicate the actual identity of the user).

And, also, users should have the ability to log in.

What would be the best strategy to achieve this?

Currently, I am hashing the username and password together (it's ok that it can never be decrypted). However, this introduces the ability to perform a rainbow table attack (or?).

My next idea would then be to discard a large chunk of the hash -- large enough so that any outcome of a rainbow table attack would become inconclusive. This would of course introduce a higher collision rate, which is undesirable.

Then again, a rainbow table attack would be able to produce a set of candidates, which would not be good.

Are there any other known strategies to this kind of problem?

HelloWorld
  • 303
  • 2
  • 10
  • there's is no "best" anything in security, it's all a matter of finding the apropos counter to a specific threat. – dandavis Dec 13 '18 at 17:59
  • Do we also consider that the attacker can also gain access to the application server to steal the encryption keys? – kelalaka Dec 13 '18 at 21:07

2 Answers2

3

There is a standard solution to defeating rainbow tables: Add a salt to what you are hashing. A salt is a random value which you generate separately for each password hash and store together with that hash.

This, however, requires that you have to know which hash you are checking against (unless you want to try every single entry in your database until you found one which matches, of course. When your solution doesn't need to scale to a large number of accounts, this might be a viable option). So you will need to know which account the user wants to log into before you can check if their password is correct. What you could do is to have three columns in your database:

hash(username)
salt
hash(password + salt)

When someone tries to log in with the credentials admin : hunter2, you generate the hash of admin. use it to retrieve the salt, calculate the hash of hunter2salt and see if it matches.

Now it is of course possible to brute-force usernames, and do it even faster with a rainbow-table. But usernames should usually not be nearly as sensitive as passwords. You can make that less convenient by using a slow has function and by using a pepper (a salt which is the same for every entry - works against pre-calculated rainbow tables).

Philipp
  • 48,867
  • 8
  • 127
  • 157
  • A salt strategy is good and I will add also a good strategy for key rotation – camp0 Dec 13 '18 at 16:52
  • Of course I know about salts ;) But how would the user get the salt salter on, when logging in, to generate the username hash? That is the logical puzzle here. I need the server to take a username, then to generate something irreversible that it can look up in the database. Thus, it must be deterministic. – HelloWorld Dec 13 '18 at 16:56
  • @HelloWorld I expanded the answer. – Philipp Dec 13 '18 at 17:00
  • @Philipp But that doesn't prevent rainbow attacks on the first column (hash(username)). Remember, I want to keep the username just as secret as the password. In my system, the username should be considered highly sensitive. I want people to be able to remain anonymous. – HelloWorld Dec 13 '18 at 17:02
  • @HelloWorld I expanded the answer a bit more, but I am afraid what you are trying to do is impossible, unless it's OK for you if your login time increases linearly with the number of user accounts you have. – Philipp Dec 13 '18 at 17:05
  • @Philipp I guess what I'm wondering, is if it's possible or not :) However, I'm still not seeing an improvement over my initial suggestion: salting the username with the password, e.g. hash(username + password). But I am unsure if that is wise. – HelloWorld Dec 13 '18 at 17:07
  • @HelloWorld You could indeed use a truncated hash for the usernames and then put the full username into the non-truncated password hash. That way you can not deduce all the usernames in the database, because there might be many plausible usernames which hash to each entry. Keep in mind that this means that usernames might have hash collisions in this case. That means you might need to check an username against multiple entries. – Philipp Dec 13 '18 at 17:16
  • 1
    There is also another problem you should be aware of: If you don't want to know any usernames, then it might get impossible to check if a newly chosen username is already taken. You can get around that if you want to allow non-unique usernames by design. But it gets awkward if two people with the same username also happen to use the same password. – Philipp Dec 13 '18 at 17:18
  • I think storing _hash(username)_ is a really bad idea (even truncated), because it'll allow to get usernames using rainbow tables and then it would be much more easy to brute force _hash(username+password)_ – Strigo Dec 13 '18 at 20:10
  • 1
    "In my system, the username should be considered highly sensitive. I want people to be able to remain anonymous." In such case, why even implement usernames to begin with? Using the right password would be what allowed you to log into your nameless account. You may want to have a look at the way 4chan implements this. – Ángel Dec 13 '18 at 21:54
0

You should consider that generating rainbow tables (RT) is a really hard work. If someone steals all your base at once, then it'll be much faster to brute force all pairs of username+password he want to check then to generate RT and search against it.

So if you use pepper you shouldn't worry about someone using RT in case he steals all your user hashes. In case he gets the hashes piece by piece (say, he dumps hashes of new users everyday), then in long term the attacker can benefit from generating and using RT.

Pair of username+password has entropy higher then password alone, making RT generation and brute force very hard (if you don't store hash(username) or any other way compromise usernames!). I think I would enforce some (not too strict) password policy and wouldn't worry about RT attack.

Strigo
  • 86
  • 4