6
$\begingroup$

For a 10-digits numeric domain (swedish social security numbers), is there a hash function with the following properties?

  • no two numbers result in the same hash
  • it is not possible to deduce the number from the hash without using brute force.

Also, can I prevent rainbow tables or is the idea of creating an anonymous id-number from a known but sensitive id a doomed idea that needs to be abandoned?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Whats your use case? Do you want to compute (domain) pseudonyms? Should it be publicly computable? I guess no and there should be a secret involved as otherwise anybody can compute the respective value. $\endgroup$
    – DrLecter
    Dec 30, 2013 at 21:25
  • $\begingroup$ @DrLecter I was discussing possible strategies with friends for generating non-sensitive id's as psuedonyms for the sensitive but today often used swedish social security numbers. $\endgroup$
    – Mattias Åslund
    Dec 30, 2013 at 21:58
  • 1
    $\begingroup$ $log_2(10^{10})\simeq 33.22$. Seems easy to bruteforce $2^{33}$ different values unless you use a very slow hash construction, so I think you should consider brute forcing as feasible. $\endgroup$
    – daniel
    Dec 31, 2013 at 12:13
  • $\begingroup$ The number is (approximately) DDMMYY-XXSC. Because of encoded date and checksum, a lot of combinations can be pruned out. If you know approximately (precision 10 years) how old the person is and his/her gender, expect close to $2^{21}$ search space or so. Even worse: "Birthday attack". If you know a person's birthday and gender, the search space will be around 9 bits. $\endgroup$
    – user4982
    Jan 2, 2014 at 19:47

2 Answers 2

Reset to default
5
$\begingroup$

There are only $10^{10} \approx 2^{33}$ 10-digit numbers. Therefore, brute-forcing seems always possible, except if evaluating the hash function is very slow.

But there is another problem: a hash table associating the hash of any swedish social security number to its security number requires only about 100 GB, since each social security number can be encoded using 5 bytes. And such a hash table would enable to invert the number from the hash very quickly.

Since this big hash table needs only to be computed once, the scheme seems highly insecure.

Edit: In the original version of the post, the size of the hash table was not computed correctly. 100 GB is a rough approximation of the size of the hash table assuming elements (social security numbers) are encoded using 5 B, and that storing 10 G such elements takes about 2*5*10 GB.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I would have thought that to ensure collision resistance you'd be required to take a much larger hash than just one byte - $10^{10}$ is more like 4 bytes. I mention this because this would push your hash table up to roughly 100GB. Still not that difficult, but under certain circumstances perhaps the table size would make a difference. $\endgroup$
    – Cryptographeur
    Dec 31, 2013 at 12:50
  • $\begingroup$ I agree the hash MUST at least 34 bits to be unique, but should probably be longer to take more space. Still 80GB is not much to precalculate, so I guess this approach should be abandoned. $\endgroup$
    – Mattias Åslund
    Dec 31, 2013 at 15:34
  • $\begingroup$ I'm still curious if there is well known hash functions that conforms to the requirements above? $\endgroup$
    – Mattias Åslund
    Dec 31, 2013 at 15:35
4
$\begingroup$

Let me postulate an answer. As you don't want to reveal the association between an user and it's social security ID, can be assumed you keep these secret, so your system counts on some secrecy to be maintained. Then just add an encryption key for a symmetric cipher. You'll get a one-to-one mapping between the social security ID and the substitute ID, and to reverse the encryption will be unfeasible. So instead of use a hash, use

$SubstituteID=Encrypt("SocialSecurityID",SecretKey)$.

You don't need neither a padding nor a salt since your social security numbers are identifiers, unique for each user, and while SecretKey is kept secret no bruteforce attack can be done.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, you are right of course, I need an encryption algo rather than a hash! I still flagged the other answer as correct for explaining how it is always open for bruteforce or table lookup attacks. $\endgroup$
    – Mattias Åslund
    Dec 31, 2013 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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