7

NB: I originally posted this on SO (link), but then realise Security SE be more suitable, since there's existing questions around Crypto-PAn, which is similar here

I have a logfile of database queries that I'd like to anonymise - these are obtained from clients, and then analysed externally. The clients would like to anonymise these enough to protect identifying information, but still leave enough to allow useful analysis.

Some lines may contain IP addresses (e.g. source IP) - I believe I can use something like Crypto-PAn to anonymise those. My understanding is that this anonymising is injective (1:1) as well as repeatable, but also non-reversible.

Likewise, lines may also contain fields and values - e.g. { "name.first": "John" }.

For the values, I'm happy to just use straight MD5 (or similar on the contents) - it's not as critical that we see what they are.

However, for the database fields, we'd like to preserve these in a somewhat human-readable format. This is because we'd be doing performance analysis based around those fields (e.g. grouping queries by the fields etc.)

For example, name.first might become Tree.Blackboard.

The constraints are:

  • Each input word should map to one hash, and vice versa (I understand there will be some collisions, but hopefully they are rare enough).
  • Repeatable - If we have multiple logfiles, we want the same hash generated each time - this will allow us to compare across logfiles.
  • Not reversible - Ideally, there shouldn't be an easy way to reverse the hash to get the original field name.
  • Human readable - The hash should be human-readable/pronounceable, but they do't necessarily need to be valid English words (e.g. Flerti is acceptable, 037751d79d1ebfdd0664b2c66b8d66d1 is not)

I discussed with a colleague, and one way we thought was:

  • Take the field name - and pass it through a standard one-way hash (e.g. MD5).
  • Take enough low-order bits from the resulting hash to map to a dictionary of English words (e.g. 1,000,000 valid words). Use the integer equivalent of those bits, and do a mod to index to a word in that dictionary.

The idea being that - the words would be readable yet also always consistent (assuming your dictionary stayed the same).

If some individuals were worried about dictionary attacks (i.e. the field name "firstname" would always map to say "Blackboard"), then that person could have their own specific keyfile used to salt the hash. This means that it would be repeatable for anonymised logfiles from them (i.e. "firstname" might always map to "Billion" for them), but it would not be the same as for other people who use other keyfiles.

Question 1 - Are there already an existing cryptographic algorithm (similar to Crypto-PAn) that can be used to anonymise strings in some pronounceable/readable fashion?

Question 2 - If not, do you see any glaring holes in the simplistic approach described above?

  • 1
    2: Yes, MD5 is too fast. You should use PBKDF2 or bcrypt or scrypt. – user49075 Jun 26 '15 at 7:49
4

You might try a syllable hash.

Start with a basic hash algorithm to digest individual data identifiers; it doesn't really have to be crypto-strength, and I'd recommend against. Most implementations will produce a byte array which is perfect; a few will produce a single larger primitive or arrays of larger primitives in which case you'll want to split them into bytes.

Then, find or create a lookup of possible byte values that map to simple consonant-value pairs (Ba, Be, Bi, Bo, Bu, Cha, Che, Chi, Cho, Chu, Da, De, Di, Do, Du etc). The order of the syllables and their mapping to byte values doesn't matter; the hashing is the non-reversible part of the operation, not the syllable mapping. Remember you only get 256, and if you use a secure hash it might also be wise to include a few mappings that add information without adding a syllable (a hyphen, or vowels which would be added to the previous syllable's vowel to create a dipthong or digraph).

With a basic 32-bit checksum hash like FNV-1 or Murmur, this will give you words of seemingly random construction in the 2-4 syllable range with the average trending high (and the chance of recognizable single-syllable words being almost nonexistant especially if leading zeroes are treated the same as inlined or trailing zeroes in the byte array). Using a crypto hash, you'll probably have to XOR-fold the bytes, as something like SHA-1 will give you 10-syllable words, which is why I'd recommend against a crypto hash.

It'll probably sound like some alternate-reality Japanese, but you'll be able to pronounce the resulting identifiers. To make it more English-sounding, you might start with a list of the most common English syllables, like this one. However, this list will include syllables that are common because they're prefixes or suffixes to word roots, while you'll be injecting them in random places in the word.

2

What are you trying to achieve? Do you want to anonymize a database with sensitive data in order to be able to give it away safely to an external QA test team without compromizing the content? In this case, anonymizing the person and firm names is not sufficient, because the rest of the data has a footprint as well which allows to draw conclusions to the owner of the data. Also you said each data should map to a hash and vice versa, but it should not be reversible. This is a contradiction, it is not possible to achieve both.

Regarding an algorithm, look how PGP creates fingerprints. They are pronouncable and hashes, consisting of a sequence of English words.

While the hash function itself is not reversible, hashes allow to uniquely identify a record belonging to this hash.

There are open source clones of PGP available so you should be able to get the source code.

Instead of hashing you can add a field which you fill with random strings generated by an algorithm like:

void Main()
{
    MakeRandomString(4).Dump();
}


private string MakeRandomString(int n)  
{  
    var bits = new List<string>()  
    {  
            "na",  "bla",  "chee",  "dee",  "ay",              
            "tree", "th",  "goo",  "foo",              
            "ook",  "ta",  "bee",              
            "zoo",  "ai",  "kawee",  "jam",  "ya"            
    };  

    StringBuilder sb = new StringBuilder();  
    Random r = new Random();  
    for (int i = 0; i < n; i++)  
    {  
        sb.Append(bits[r.Next(bits.Count)]);  
    }  

    return sb.ToString();  
}  

This will create random fantasy words like:

cheekaweefoobla
yataaitree
deetreenana

It is a slightly changed code I took from here. For export you can use that field as reference. It will be able to map the original row. You can improve the code above by using a cryptographic random generator.

  • The logfiles will be shipped off-site. As mentioned, the actual field values will just be MD5-ed - we won't really care what the contents are. It's the field-names that we need to preserve in some kind of manner, to make off-site analysis easier. When I say mapped, what I mean is - each input string should consistently produce the same hash output. And each hash output should only be producible by a single output (I understand this isn't quite possible, since you can get collisions, but as close as possible). Does that make more sense? – victorhooi Jun 26 '15 at 7:27

Your Answer

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

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