US District Court Says Calculating a Hash Value = Search

bfwebster writes "Orin Kerr over at The Volokh Conspiracy (a great legal blog, BTW) reports on a US District Court ruling issued just last week which finds that doing hash calculations on a hard drive is a form of search and thus subject to 4th Amendment limitations. In this particular case, the US District Court suppressed evidence of child pornography on a hard drive because proper warrants were not obtained before imaging the hard drive and calculating MD5 hash values for the individual files on the drive, some of which ended up matching known MD5 hash values for known child pornography image and video files. More details at Kerr's posting." Update: 10/28 16:23 GMT by T : Headline updated to reflect that this is a Federal District Court located in Pennsylvania, rather than a court of the Commonwealth itself.

Comments

It's good to see.

[UseTheSource]

The courts are finally getting up to speed on technology.

Re:It's good to see.

[UseTheSource]

It's not that child pornographers shouldn't be prosecuted, but like it or not, they're still entitled to the same due process as normal, "non-pervert" criminals. This "it's for the children" stuff shouldn't fly when we claim to follow the rule of law.

Re:It's good to see.

[ericrost]

You just wait until Obama pardons Mumia...

Not to feed the trolls, but Mumia Abu Jamal was arrested and held under the authority of the Commonwealth of Pennsylvania, Obama, as President of the United States, cannot pardon him for a State offense, only a federal one:

2. Federal convictions only

Under the Constitution, only federal criminal convictions, such as those obtained in the United States District Courts, may be pardoned by the President. In addition, the President's pardon power extends to convictions obtained in the Superior Court of the District of Columbia and military court-martial proceedings. However, the President cannot pardon a state criminal offense. Accordingly, if you are seeking clemency for a state criminal conviction, you should not complete and submit this petition. Instead, you should contact the Governor or other appropriate authorities of the state where you reside or where the conviction occurred (such as the state board of pardons and paroles) to determine whether any relief is available to you under state law. If you have a federal conviction, information about the conviction may be obtained from the clerk of the federal court where you were convicted.

Source: http://www.usdoj.gov/pardon/pardon_instructions.htm

Re:It's good to see.

[lysergic.acid]

also, wouldn't this type of search be pretty useless for identifying kiddy porn images?

md5 hashes are useful for verifying a binary package is in fact what it is supposed to be because it's hard to create a fake or altered program that produces the same md5 hash number as the authentic copy. so it's useful for verifying a "good" file, because presumably a good file won't try to deceive you, and a bad file can't reproduce the same md5 hash.

however, with something like a digital photo, all a user has to do is make a few very minor alterations (like a small watermark) to the image and it would produce a different md5 hash--essentially exploiting the inherent design of the md5 hash algorithm--and be missed by the md5 scan. these small changes could be as simple as flipping a single bit in the file, but with a standard 24-bit RGB bitmap image, each pixel is stored as three 8 bit values representing the red, green, and blue color channels. by flipping the least significant bit in each channel, you can alter up to 1/8th (12.5%) of the file without creating any perceptible changes (to human eyes at least) to the displayed image.

another method would be to employ lossy compression schemes like JPEG image compression. convert all your images to JPEG (or if they are already JPG, just compress it again at minimal compression strength) and the MD5 hashes will be completely altered. yet another method is to resize the image by a small amount--say reduce both width and height by just 1 pixel--using bicubic interpolation to scale the image up or down would preserve the image quality while completely changing the md5 signature of the file.

all of these methods would be simple to automate and allow you to easily hide known child porn images from detection using md5 comparisons.

Re:It's good to see.

[Anonymous Coward]

I used to work in an australian court. And I remember a judge in tears throwing out a paedophile case where the guy was *clearly* guilty as hell, but the prosecution had bungled it so badly it couldn't' possibly be presented to the jury in that state. Afterwards she practically broke glass screaming at the prosecutor.

Afterwards I asked her about the case and she told me that although she was bitter , even the worst of scumbags deserve a fair trial, and that fair trial wasnt it.

Later that year they retried the case properly and the guy got 20 years.

Re:It's good to see.

[Anonymous Coward]

The bible never mentions any of those punishments for those acts. You may or may not be a hypocrite, but you are certainly an ignorant idiot.

Always funny to see the ignorant hick call someone else ignorant. Feel free to review an old testament. The crushing of testicles is in there and is in fact also a crime to use on the impure and gay should they attempt to enter a church.

Like it or not, the bible has lots of nasty stuff in it. If you don't like it, it's because you're a hypocrite.

Re:It's good to see.

[kvezach]

No. The break against MD5 is not a preimage attack, it's a collision attack. This means you can pad two files so that MD5(a + pad1) = MD5(b + pad2). It doesn't mean that you can make a file so that MD5(a + pad) = MD5(b) - not in anything less than 2^64 expected time and space, anyway.

that's basically what they were doing.

[yincrash]

you can't generate md5s w/o actually looking at all of the data in the file.

Re:that's basically what they were doing.

[Anonymous Coward]

"We got this guy, but let's get a warrant before we scan his hard drive."

The odd thing is that the computer was in the landlord's friend's friend's (brother's dogwalker's sister-in-law's... whoops, got carried away) possession having been seized during the eviction. The vast majority of precedent (used whenever the government wants data from phone companies and mail servers, etc) says that if the guy with the data freely gives it to the cops, they don't need no steenkin warrant.

While the overall decision is welcome (that the government can't just force their way into my house and hash my drive on a whim), the method by which the decision was arrived at is unsound, and will almost certainly be overturned on the grounds that it wasn't the pedophile's drive anymore, therefore the pedophile had no standing to object to the search.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Error made by Slashdot in headline

[bfwebster]

When I submitted this story, I gave it the headline "US Court:...". Someone changed that to "PA Court Says...". That's wrong. This is a ruling from a US District (Federal) court, not a Pennsylvania state court, and so carries much more weight. ..bruce..

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:MD5 Collisions...

[Trevin]

Even if the hard drive has a couple of million files on it and there are a few thousand known hashes of illegal files, the odds of having a different file with a matching hash are in the neighborhood of 10^28 to 1 against.

Re:That's a terrible argument

[msuarezalvarez]

What evidence? Some md5 hashes that happen to match hashes from a select number of images? Odds are if we hash out every file on your hard drive we will also find matches to that same list.

Actually, odds are the hashes will not match...

Re:That's a terrible argument

[Sun.Jedi]

Better a few guilty men go free on a technicality than allow officers to become a law unto themselves.

The largest US gang has a well documented record that would seem to indicate your statement is out of date.

As another everyday example, here's a big surprise, no?

I'm not intending to troll/flamebait here, but MY perception is there is very little accountability for the 'on the job' crew in blue amongst themselves. It is also my perspective that there is very little integrity once one subscribes to the original meaning of the thin blue line.

Re:That's a terrible argument

[johnlcallaway]

Odds yes.

But no guarantee.

A better check is hash and file size, since it is more difficult for two files of the same size to have the same hash by chance. Especially using compression due to images or videos of the same dimensions reducing to different sizes.

Hash and file size checks are useful for checking if a file is intact and possibly not altered. They are great for lookups.

But, in the end, you still need the file to validate the correct item is found. Hashmaps store both the key and hash for this very reason. The hash is a quick lookup, but the key is needed to verify the right element has been found.

Unless the hash is the same size as the key.....

Cops blow it again

[russotto]

Not only did they search the drive without a warrant, but they also got the defendant to confess to putting the files there by questioning him without reading his rights and telling him that he didn't need an attorney. Genius.

Even dumber: Based on the testimony of the guy who originally found the child porn, they could have gone to a magistrate and gotten a warrant. Then there would have been no issue of a warrantless search.

BTW, for those considering the abandoned-property angle -- the court goes into that. It wasn't a legal eviction and the defendant hadn't abandoned his stuff; he merely hadn't removed it all yet.

Re:What was the chain of custody

[Anonymous Coward]

As far as I've understood:

1) Computer Owner was evicted. Left computer behind - maybe to collect later - who knows what the verbal agreement was here, I imagine the PC owner has claimed that we was going to pick it up and that it wasn't abandoned or trash.

2) Home Owner hires someone to clear out the stuff left behind.

3) Hired Person finds PC, and takes custody of PC.

4) Hired Person passes on PC to friend, who therefore has custody.

5) Friend discovers porn, calls police.

So the evidence could be tainted by the hired person and the friend. In addition the owner could have had access. The owner has a grudge against the PC owner as they never paid, it isn't inconceivable that they could have arranged for something to be added to get the person in trouble as punishment.

A proper forensic examination might have resolved what happened. This is unlikely now.

Re:good point

[MasterOfMagic]

Chain of custody. Very important in forensics.

The landlord and his friend might have had a motive to lie about the guy that was behind on his rent payments. From the blurb from the article, it doesn't seem that his landlord had completed the eviction procedure yet, and was anxious to get Crist out of his house and a new tenant in. The eviction process is not immediate. So he gives Crist's computer to his friend, his friend backdates the clock, and his friend puts kiddie porn on there and turns it over to the cops.

The fact is that the police cannot be certain of the chain of custody in this case without a warrant. With a warrant, they take affidavits in support of chain of custody before they go poking around. It's clear and documented using established procedure. The landlord and his friend can still lie, but they're now subject to the penalties for filing a false statement. Without that supporting documentation and especially because of the nature of the case and the possible motives of the landlord and his friends, it makes the chain of custody issue important.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:good point

[MasterOfMagic]

According to the article, the computer was removed from the defendant's residence by his landlord's friend because the landlord was in the process of evicting the defendant for non-payment of rent. This computer was not found abandoned on the side of the road with the trash. There's no clear indicator that the defendant gave the computer to the landlord's friend, which means the computer is the defendant's property. Therefore, the landlord's friend does not have the right to consent to a search of the computer. This means that the police need a warrant to search that computer, and given the evidence that the landlord's friend had, they would have likely gotten a warrant without any issue.

It's a procedural screwup on the part of the police. It happens. They're human.

Re:MD5 Collisions...

[Anonymous Coward]

The fact that there are collisions is a fun anomoly as long as you can't generate collisions with an algorithm, not anything useful.

Yeah, sure is a good thing that it's not possible to do that with MD5 hashes.

Re:good point

[Chris Burke]

The problem I have here is I would think that this would come under reasonable cause.
Someone calling the police and saying "Hey I found kiddie porn on this computer." seems to be reasonable cause to me.

It seems that way to me as well, and had they tried to get a warrant based on probable cause, it probably would have succeeded.

Conducting the search without a warrant, however, isn't going to fly unless their are also "exigent circumstances". Which in this case would mean the police have reason to believe that any potential evidence on the laptop would vanish before they could acquire a warrant. Since the laptop was in the possession of the 3rd party who called the police to report the crime, that seems unlikely.

So not getting the warrant was a big mistake, and it's likely a criminal will walk as a result. Even though it's sad, this has to happen. Failing to get a conviction and having the perp walk free is the only thing that motivates police to follow all the correct procedures and guarantee all the suspect's rights. Now the police know that a warrant is not optional when searching a laptop. So in the future the cops won't make this mistake, perps will be caught using proper rules of evidence, and our rights will be more secure.

Re:That's a terrible argument

[blueg3]

Yes, that's the birthday paradox. I'm not sure offhand how big the NCMEC database is, which is usually what they're comparing against, but let's try some math.

Let's say your hard drive has N files and the database has M items (so, comparing a list of N to another list of M hashes). Your hard drive doesn't actually contain any of the files used to generate the "bad" hash list. The probability of a hash collision is approximately P = 1 - exp( -N*M / (2 * 2^128) ). Assuming the value in the exponent is small, this is approximately P = N*M/2^129. 2^129 is in the rough vicinity of 10^43. In order for you to have a one in a billion (10^9) chance of a false positive, the product N*M would have to be ~10^34. If the hash list has a billion items (I think it's smaller than that, by quite a lot), you'd need 10^25 files on your disk -- well beyond the capacity of readily-available desktop storage.

MD5 hashes are useful because they're resilient to even birthday collisions. What they're not resilient to, it turns out, is intentionally creating two files with the same MD5 hash. (Even then, it is infeasible to generate two files with the same MD5 hash and the same size.)

Re:MD5 Collisions...

[Free the Cowards]

False. MD5 has the property that if you can find two bytestreams that collide, appending identical data to the end will continue to produce two different files that collide. Furthermore, the collision-finders are able to take an arbitrary prefix, and then append random data to that prefix until a collision is found.

What does this mean? It means you can take a file with a blob of random data in the middle, then generate two files with identical hashes but different random blobs of data in the middle.

This, in turn, allows you to do things like create applications, postscript files, HTML files, and other things which hash identically but act or display completely differently. (You embed both behaviors in the file, then switch depending on the contents of the random data. A close examination will turn up the "bad" side, lying inactive, but simply opening the file will make it appear that all is well.)

It's certainly not as good as being able to match an arbitrary hash, but MD5 collisions are entirely practical to take advantage of today.

At this point, MD5 should be considered to be a checksum, not a validator. MD5 is still very good at detecting random noise injected into a data stream but it should no longer be considered to have any real utility for detecting malicious changes.