# Is there a deterministic one-way collision-free crypto algorithm?

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.

• 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)? – SEJPM Apr 19 '18 at 20:24
• Usernames generally have low enough entropy that no cheap function will be secure. – CodesInChaos Apr 19 '18 at 20:31
• @sejpm Regarding SHA256/512 - what I'm afraid is GPU parallelization and rainbow tables (remember I can't use salt). – visa Apr 19 '18 at 21:01
• @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. – visa Apr 20 '18 at 7:18