1
$\begingroup$

I use usernames encrypted using a function f as ids of records. Users see records identified by f(username). I must not know real usernames.

I want to be protected from attack when adversary who has a username u1 and knows f generates another username u2 such that f(u1) = f(u2), logs in with this username and sees the data of user with username u1.

So, f must be:

  • deterministic: I use f(x) as identifier. It rejects RSA encryption with throwing out secret key.
  • one-way: I must not be able to get a real value from encrypted value.
  • collision-free to prevent attack describes above. It rejects md5/sha because as far as I understand they are easily crackable, especially because I don't use salt (unavoidable technical reasons).
  • quick to compute: I must handle tens of thousands messages per second. It rejects b/crypt.

Note that I don't care about length of output (it may be fixed or variable).

I was looking at MAC and Digital Signature algorithms but can't figure out which of them have required properties.

$\endgroup$
  • 1
    $\begingroup$ Actually, you don't need full collisions resistance, but only weak collision resistance / 2nd pre-image resistance which is as of now unbroken for MD5 and SHA1. SHA1 and MD5 are only broken insofar as that if the attacker gets to chose both $u_1$ and $u_2$, they can find a pair $(u_1,u_2)$ with $u_1\neq u_2$ and $f(u_1)=f(u_2)$. Also is anything speaking against plain ol' SHA256 (even though you could also "create your own hashfunction" by taking HMAC and fixing a key)? $\endgroup$ – SEJPM Apr 19 '18 at 20:24
  • 3
    $\begingroup$ Usernames generally have low enough entropy that no cheap function will be secure. $\endgroup$ – CodesInChaos Apr 19 '18 at 20:31
  • $\begingroup$ @sejpm Regarding SHA256/512 - what I'm afraid is GPU parallelization and rainbow tables (remember I can't use salt). $\endgroup$ – visa Apr 19 '18 at 21:01
  • 1
    $\begingroup$ Can you expand on why you cannot use a salt? A little more information about this system would be helpful. $\endgroup$ – Gray Apr 19 '18 at 22:48
  • $\begingroup$ @Gray It's a long story, completely out of scope of this site. As I understand from this discussion and the one on SO, sha256 with pepper is completely feasible for my use-case. $\endgroup$ – visa Apr 20 '18 at 7:18
4
$\begingroup$

At SEJPM indicated, MD5 and SHA-1 probably are resistant enough for you never to get a collision. However, that doesn't mean that either of them is secure. Neither is SHA-2 or SHA-3. That is, given that the usernames do not have a special structure that makes them hard to guess.

The problem is that user names can - generally - easily be guessed. So whatever you do to them, a deterministic algorithm will expose them. You can just perform a dictionary attack and find the resulting value in the set of stored user names. This way most usernames will easily be found.

If you want to protect them you may need a second system (trusted third party, an entity other than the user or service provider) that performs username encryption / decryption or password hashing with a pepper - a secret value just like a key.

But in general it is better to make sure that knowing the username gives the adversary few - if any - advantages. This is the case in the majority of cases, although may systems may not indicate if a username or password is incorrect - making guessing of the combination of both just that little bit harder.

$\endgroup$
  • $\begingroup$ I didn't care about guessing original username in the context of described attack, because actually users register and log in through a trusted third party which prohibits usage of existing usernames. Though sha is second pre-image resistant, second pre-image may be guessed using brute force and rainbow tables. That's why I should use pepper. Is my understanding correct? $\endgroup$ – visa Apr 20 '18 at 7:14
  • $\begingroup$ Yeah, that sounds correct. A salt would only provide limited protection. It should fully protect against rainbow tables and provide limited protection against brute force attacks. A pepper of the right size would not enable an attacker to perform the calculation at all; guessing the input of the hash would include guessing the pepper. $\endgroup$ – Maarten Bodewes Apr 20 '18 at 9:31

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.