Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Some Background:

There is an entity with an identifier and some information. The identifier of this entity is a string with a known scheme/pattern(Which means the total number of such possible entities is say 10-100 million).

Information about the entities is stored in two geographically distributed systems. A third system is responsible for aggregating information about these entities.

And here is where the security comes into play - The third system should not know the actual identifiers of the entities and should not be able to derive the actual identifiers.

Existing proposed solution:

Both of the sites storing information about the entities decide upon a one way hashing algorithm to use, say 'PBKDF-2' and also securely communicate a long random salt that they will use while hashing. Both the sites do the one way hashing and send the hash as identifier to the third entity. The third entity can still merge the entities based on the hash but does not know the actual identifier.

Problem with the solution:

Since the set of all possible entity identifiers can be recreated(about 10-100 million), someone can execute a dictionary attack fairly easily. The salt makes it a bit more difficult but that's just some more additional overhead and does not provide a lot of comfort.

Alternatives proposed:

  1. Use multiple hashing cycles with different salts
  2. Use multiple hashing cycles with different salts and ciphers(scrypt, bcrypt and PBKDF-2)
  3. Use mappings of identifiers to random strings (but that adds the overhead of always communicating the mappings between the two systems)

Please let me know if any of the three approaches listed above is acceptable. If there is some other more known/acceptable solution to scenarios like above(which I imagine must be plenty out there), I would gladly appreciate and accept them.

share|improve this question
    
Who issues the identifiers? You could always mix in a secret key to the "hash" you send to the third system. If the secret is known only by the first two systems and is sufficiently long (at least 128 bits), the third system wouldn't be able to figure out the inverse mapping. –  mikeazo May 23 at 17:49
    
So you are suggesting that adding of this long random string to the identifier then one way hashing with a shared secret salt should be sufficient for the above case? –  MickJ May 23 at 17:57
    
It sounds like the long random salt is generated anew for each session. If it is long enough, then the server that does the merging shouldn't be able to reverse it without knowing the salt. –  mikeazo May 23 at 18:10

1 Answer 1

If you have a secret key (256-bits) shared between the two systems that see the entity identifiers, you can use HMAC-SHA256 to map entity identifiers to a random string. Under the assumption that HMAC-SHA256 security is good (which is widely believed to be a reasonable one), this is just as secure as having generated a truly random mapping, but requires only communicating 256-bits instead of the full mapping. If there are multiple rounds of this process of aggregation, you could use a different secret key or a different (public) nonce if it is not necessary for the aggregating system to know which entities are the same between rounds.

However, it sounds like the information associated with each entity will not be encrypted (since it needs to be processed in some fashion by the third system), and you therefore have to very carefully consider whether it may be possible to de-anonymize the entities based on their associated information. There have been many cases of researchers de-anonymizing (http://en.wikipedia.org/wiki/De-anonymization) supposedly annoymized datasets.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.