1. Start with a unique identifier

    String macAddress = "CC:3A:61:24:D6:96";

  2. Hash the identifier via MD5 implementation

    String hash = md5(macAddress); //bd37f780e10244cf28810b969559ad5b

  3. Remove all letters from the hash

    String result = hash.replaceAll("[^\\d.]", "");

    result == "3778010244288109695595"

I am using MD5 to anonymize MAC Addresses from our users. Our current web service does not accept letters for the value I wish to set, so I simply removed the letters. I am wary this will increase the chances of a collision within our database, so I come here with the question:

How likely is it result will collide with a different macAddress input compared to hash?

  • I would say that no one know. But why don't you transform the letter into number? MD5 return a byte array so all the value are in hex (0-9A-F). – Gudradain Jul 18 '14 at 19:23

Don't put too much faith in such anonymizing. Indeed, MAC addresses fit on 48 bits, out of which two are used for administrative reasons, leaving only 46 bits (at most) unknown to someone eager to recover the MAC addresses (indeed, the attacker can assume that the MAC address from a physical user machine will be "unicast" and "globally unique", so the two least significant bits of the first byte will be 0).

A good GPU will be able to compute more than 233 per second (see benchmarks here; the machine with 8 AMD R9 290X achieves more than 93 billions of MD5 per second); so that single off-the-shelf GPU can crunch through the complete 246 space in a couple of hours.

More importantly, recovering MAC addresses for tracking people makes sense only for an attacker who has known MAC addresses to track. The attacker needs not hash all 246 possible MAC addresses, only the few dozens (or hundreds or thousands or even millions) that he is trying to follow. A basic laptop, with no GPU at all, can do that in a fraction of a second.

That being said, the question you asked still makes sense mathematically. If we assume MD5 outputs to be "mostly random" values in the 2128 space, then each character in the hexadecimal string has probability 10/16 of being a digit, independently of the other digits. All the possible inputs will fall into one of the 33 categories for the 33 possible lengths for the resulting strings (0 to 32 digits). The probability of an MD5 output to fall into the category n, i.e. to contain n digits and 32-n non-digits, is:

Pn = (32!/(n!(32-n)!))·(10/16)n·(6/16)32-n

On average, if you hash k MAC addresses, you will get zn = k·Pn values in category n, and you can expect a collision when that number zn begins to get close to the square root of the space of possible values in that category, i.e. 10n. In other words, when k reaches 10n/2/Pn for some n, you are in trouble.

Let's get some numbers on that; the threshold for the various categories is:

n =  0  ->           42756232765793.7
n =  1  ->            2535132744529.3
n =  2  ->             310327495880.8
n =  3  ->              58880502453.6
n =  4  ->              15409365312.7
n =  5  ->               5220931252.0
n =  6  ->               2201337901.8
n =  7  ->               1124508269.7
n =  8  ->                682753416.9
n =  9  ->                485787572.5
n = 10  ->                400746570.8
n = 11  ->                380181578.5
n = 12  ->                412196472.8
n = 13  ->                508357082.1
n = 14  ->                710713497.4
n = 15  ->               1123736707.7
n = 16  ->               2006720463.1
n = 17  ->               4045452147.9
n = 18  ->               9210846925.9
n = 19  ->              23717908021.4
n = 20  ->              69233179091.0
n = 21  ->             229881262361.1
n = 22  ->             872338056547.2
n = 23  ->            3806833704700.6
n = 24  ->           19261224288561.1
n = 25  ->          114205011141017.5
n = 26  ->          804844014914874.4
n = 27  ->         6871878670370940.0
n = 28  ->        73015449033077408.0
n = 29  ->      1004393786461416580.0
n = 30  ->     19057032197633204000.0
n = 31  ->    560451732845470400000.0
n = 32  ->  34028236692093846000000.0

Bottom-line: when you hash MAC addresses with your "remove letters from hexadecimal" rule, you should see the first collision appear when you have hashed about 380 millions of addresses; it is expected that the first collisions will be for resulting strings of length 10 to 12 characters.

While 380 millions is still a large number, it is considerably below the values normally expected from a hash function with 128 bits of output; if you somehow kept the actual MD5 output, you would be safe until about 264 hashed MAC addresses, i.e. a lot more than is actually possible, since there are only 248 possible MAC addresses (246 in practice, as explained above).

Therefore, if you want to hash the MAC addresses, I warmly suggest that you do not remove the letters. Instead, if you must have digits and only digits, then use an encoding which keeps all the information. MD5 output is 16 bytes; the 32-character hexadecimal representation is just that: a representation. You could use an alternate representation which produces only digits. For instance, you could interpret the MD5 value as a big integer, and encode that in base 10. The corresponding Java code would look like this:

// MD5 output is a byte[], in variable md5out
String result = new BigInteger(1, md5out).ToString();

Since MD5 output is 16 bytes, the resulting integer will fit in at most 39 digits.

But remember what I wrote at the beginning: as an anonymizing system for MAC addresses, a hash function is not a very good tool... it will mostly thwart casual eavesdroppers, but why would such an eavesdropper be interested in MAC addresses anyway ? It is not an information that you can use "across the Internet". Competent attackers who are in position to exploit MAC addresses, on the other hand, will be able to see through such an anonymizing layer.

  • if not a hash function, what would you recommend? the means of anonymizing cannot require a key because then the key must be packaged in the application. – kiansheik Jul 18 '14 at 20:16
  • I don't know enough of your context to emit any recommendation. I suppose that you are trying, from a smartphone app, to obtain a kind of smartphone identifier that you wish to upload to a server of yours in order to recognize phones from each other. In that case, it seems to me that any attempt at anonymizing is hopeless, regardless of the function you use, basically because the phone can compute that function. – Tom Leek Jul 18 '14 at 20:26

The average MD5 checksum expressed as a hexadecimal string (like you're doing) has 20 digits and 12 letters. Stripping the letters means your modified MD5 has approximately 10^20 or 2^66 bits of output. The odds of a collision is the square root of the output space, or about 2^33 -- you need, on average, 8.5 billion MAC addresses to generate a collision.

For your purposes, this is probably good enough. If you needed to store all 2^64 possible MAC addresses, it wouldn't be (but neither would unmodified MD5).

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.