A question regarding relevance of vulnerability of MD5 when linking multiple records together

Question

I have been studying a Supreme Court case "IMS Health vs Sorrel".

In this case a Friend of Court brief filled by "Electronic Privacy Information Center" states that use of MD5 hash function to link multiple records together is suspect, since MD5 is broken.

I find this argument incorrect, the only use of MD5 (it is unknown whether it is salted or not) is to compute a hash to protect patient identity and not for signing purpose. Thus the usual arguments against use of MD5 do not apply.

Here is the quote from the brief http://epic.org/amicus/sorrell/EPIC_amicus_Sorrell_final.pdf

The first is the deidentification of the patient’s actual identity through a cryptographic technique known as “hashing.”

In ideal circumstances, a record containing the hashed representation of the patient’s actual identity could never be linked to the actual patient. But the cryptographic technique chosen to protect patient privacy in this matter has been suspect for at least 15 years, can now be broken using nothing more than an ordinary desktop computer, and is considered unsuitable for further use by the federal government.

Vlastimil Klima, Finding MD5 Collisions – A Toy For a Notebook (Mar. 5, 2005);9 Chad Dougherty, Vulnerability Note VU#836068: MD5 Vulnerable to Collision Attacks, United States Computer Emergency Readiness Team (Dec. 31, 2008).10 See generally, Wikipedia, “MD5,” (“. . .

it has been shown that MD5 is not collision resistant; as such, MD5 is not suitable for applications like SSL certificates or digital signatures that rely on this property. . . . The security of the MD5 hash function is severely compromised.”)11

Answer 1

If MD5 is used to hash "something like patient name or SSN or some unique personal identifier" in order to "ensure that a multiple prescriptions of the same patient (as identified by the personal identifier) are linked to each other, without revealing the identifier itself", then that solution is technically imperfect, but not for reasons related to weaknesses of MD5 highlighted in the question (there are better arguments in the legal memo itself, and some of the documents that it references).

Fact is, the risk of collisions with MD5 used in this way is negligible as far as the cryptographic community knows, even facing an adversary that deliberately attempts to create collisions. That's because the known weaknesses in MD5 currently only allow to create collisions between two artificially crafted data sets, not among a legitimate and an artificial data set, must less between two legitimate data sets. Thus MD5 collisions are a non-issue in that application, because they won't happen; and more importantly, the real issue is elsewhere.

The real issue (and what the legal memo is mostly about) is to protect the anonymity of patients, and that's something MD5, or any hash, is not designed to do, and does not. Knowing the input of the hash ("Patient name or SSN or some unique personal identifier"), it is possible to compute the output and check it against the hash to determine if a case/file belongs to that patient. Change MD5 to any better hash function like SHA-512, and that problem remains.

One option could be to use a MAC of patient info, with the key held by a trusted authority (in some cases that could be a Smart Card). That makes it impossible for a party with no access to the trusted authority to check if a file matches a patient id, unless she knows a file pertaining to that patient; further, access to the trusted authority can be logged, which is a deterrent against misuse. That's imperfect, and comes with a cost, and new risks (e.g. that patient info could be intercepted in transit to the trusted authority, or in the logs), thus I am not even sure this is preferable. But if we do use a MAC, we should use HMAC-SHA-512 rather than HMAC-MD5 (even though there is no known attack against HMAC-MD5; rationale is the same as for the car engineer, who won't use tires known to explode at high speed, even on a low-speed car when they would be safe, and save a little cost and energy).

Private Information Retrieval aims at solving the kind of issues the medical research community has. It works, but is a significant departure from existing practice. For pharmacies, some (not me) might advocate an intelligent tag that answer yes or no when asked if it is for a given patient, and reset after a number of no.