First off, this question is not about password hashing, my requirements are different. In particular I fully agree that salts are not useful for adding cryptographical complexity in password hashes, since the salt is almost always known to the attacker. In my situation, the salt is unknown.

I have a table with records, one column of which contains a username, covering two different dates. There may be multiple records with the same username. I want to share this table with someone else, however this person is not allowed to know which username goes with which record, however he should be able to link records for the same username on the same date.

My suggested solution to this is to generate a (CSPRNG) 1024-bit random salt for each date. I then hash the usernames, using the salt for their respective dates, and replace the username with this. I will send the tables, however not the salts.

My claim is that it is computationally infeasible (on current non-quatum-computing hardware) for the recipient of this data to:

  • provided he has a username, find out which data belong to this username
  • find out (just on the username column) which records belong to the same user, unless the records are on the same date
  • even if he knows the true and hashed usernames of 99.9% of the records, to determine the usernames from the hashed values of the remaining 0.1%

To be complete: I do realise that there is always a chance that two different usernames map to the same hash, thereby losing the property that the recipient should be able to distinguish which records had the same usernames in the original table, however these chances are so astronomically small that I'm willing to accept them.

My question: Is my claim correct? Is there any documentation I can point to that supports this (without someone needing a PhD in mathematics --- I would like to be able to "prove" this to the legal department)? I guess I'm looking for the same kind of guarantees that (a)symmetrically encrypting the value with an key that is later deleted, gives, even though I feel that hashing with a 1024-bit salt is stronger than encryption with a 1024-bit key.

Note that it's (for organisational reasons) not feasible for me to just map every username to a random value, and store this value in memory so that if I see the same username/date again, I will use the same value.

  • 1
    In terms of terminology, what you call a 'salt' is, in your context, typically called a key. – Jacco Jul 27 '16 at 10:47
  • Your initial assumption about salts / complexity is completely incorrect. It's unclear to me what you mean by "dates" in the above. If you think about reusing salts then you'll leak identical user names. This means that if one username is known, that another username will show up with the same value. Currently I'm not sure if I understand the protocol. The choice of a 1024 bit "salt" shows that you are insecure about using crypto; I'd consider external help. – Maarten Bodewes Aug 3 '16 at 9:16
  • I'm very much seeking external help here on StackExchange :). It't true that any salt larger than the resulting hash size is useless, however 1024bit was chosen. The problem is that I'm using hashing different from how 99% of the people use it, and I was hoping for some pointers to papers/external documentation/others that describe this use. EU Article 29 working group (the EU's top privacy authority) describes hashing with salt as a valid pseudonymisation technique, but also there there is no description of the "guarantees" when the salt is destroyed. – Claude Aug 3 '16 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.