Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
Could you explain a bit more detailed how MD5 is used in this case (i.e. what is hashed here)? –  Paŭlo Ebermann Dec 17 '12 at 8:47
1  
Something like Patient name or SSN or some unique personal identifier. The hash would 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. E.g. For each prescriptions you calculate a hash using MD5 for the patient identifier, and then all the prescriptions which have the same hash are linked to each other. A collision would result in two different patients getting their prescriptions mixed up which in turn would actually make re-identification harder. –  akshay bhat Dec 17 '12 at 10:59
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
TLDR; it took me 5 minutes to write a shell script that generates a rainbow table for SSNs. The resulting file is about 100 gigabytes, and can be used (especially if sorted) to instantaneously look up the SSN of any individual if given an MD5 of the SSN. –  Stephen Touset Dec 17 '12 at 21:16
1  
It's worth noting that salts would have prevented a rainbow table, but brute force over a billion possible SSNs is still reasonable with dedicated hardware. HMAC with a secret key is the way to go. –  Stephen Touset Dec 17 '12 at 21:22
    
Thanks for your answer, This data is actually publicly distributed and available for purchase. Hence the use case here is only to link multiple prescriptions together consistently without actually revealing patient identity/identifier. Most likely the personal identifier would be something more complicated than a simple SSN, most likely a synthetic identifier which would be virtually untraceable. (unless of course you rely on other approaches such as re-identification.) Thanks again. –  akshay bhat Dec 18 '12 at 2:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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