How should US SSN be anonimized?

Question

I have just gotten access to a US government dataset. It is not open, but could eventually be made open. The dataset includes hashed US SSNs. It looks like they used some general hashing function that is causing collisions. The collisions are already a problem in the relatively small version of the dataset I have now. Once the full version is pulled, the collisions will be even worse. How should one anonimized a US SSN to avoid collisions while still protecting the private information?

Answer 1

Since SSN has only 9 digits, changing hash function will not suffice because attacker can simply apply the function to all 10^9 SSN's and match the result against the database.

One option is to use a permutation cipher, destroying the private key afterward. Make sure that the cipher is resilient to known plaintext attack (since attackers are likely to know the content of the database that pertains to them, and possible to a handful of others).

Another option is to generate a private permutation of 10^9 element set using "true" randomness (from /dev/random to specialized hardware). There is numerous literature on how to generate random permutations. Of course, it is important to apply random permutation to the entire 10^9 elements, not just to the subset you have!

The best way is to combine the two approaches.

No matter what you do, do not forget to buy the liability insurance.

Answer 2

This is an expansion to this answer, so please give the votes to that one.

Another option is to generate a private permutation of 10^9 element set using "true" randomness

To anonymize the data for sharing AND to keep an id field for joining, you need to make a list of all unique SSNs, generate a random string for each, and then re-write the random string in the place of the SSN. This way, multiple tables/files are still joinable but the SSN is no longer part of the data.

Say I have 2 SSNs in one file:

1112223333, A, 2
2223334444, B, 3

And another 2 in another file (where one is the same and can join the files)

2223334444, B, 3
9998887777, C, 4

A small code would then read these files and create a list (set) of unique SSNs.

1112223333
2223334444
9998887777

Then the code would generate a random string that is independent from the SSN (not a hash function). There is no constraint to 10e9 integer characters. There is a constraint that no two random string is the same, but that is not hard to avoid based on either generating a new random string if it already exists, or using a string with a length that makes it impossible* to have duplicates.

1112223333,M2dMCUl80c6WNHYbBKvJ
2223334444,7kDZBCWAmuS9UpyKT9JV
9998887777,zIHKMe7DYfrRNDb0FirU

Or with a dictionary form:

my_dict = {1112223333 : 'M2dMCUl80c6WNHYbBKvJ'
          ,2223334444 : '7kDZBCWAmuS9UpyKT9JV'
          , 9998887777 : 'zIHKMe7DYfrRNDb0FirU'}

Then re-write the files/tables with the value from the dictionary, instead of the key. With python

  #my_dict = create_random_dict(ssn_list) # no function exists in this example

  rows = [] # sample input data for first file
  rows.append([1112223333, 'A', 2])
  rows.append([2223334444, 'B', 3])

  for row in rows:
        print ','.join([str(my_dict.get(row[0]))] + [str(x) for x in row[1:]])

Gives as an output for the first file:

M2dMCUl80c6WNHYbBKvJ,A,2
7kDZBCWAmuS9UpyKT9JV,B,3

And as an output for the second file:

7kDZBCWAmuS9UpyKT9JV, B, 3
zIHKMe7DYfrRNDb0FirU, C, 4

If my_dict is only in memory, then there is no chance to map the anonymized string back to the SSN, but you can still link different records by the anonymized string.

Answer 3

Since the SSNs you received are already hashed (poorly), why not just replace the existing hashes with random unique strings? That way there's absolutely no way to attack the encryption, since the original data is completely destroyed -- and it solves your collision problem as well (assuming there aren't any actual duplicates in the data). This also assumes that the only reason you're keeping around the SSN data at all is to use it as a unique identifier. If you don't need it for that, you should ask yourself if you need to distribute it at all, or can simply delete that portion of the data set.