Schneier on Security

A blog covering security and security technology.

U.S. Court Rules that Hashing = Searching

Really interesting post by Orin Kerr on whether, by taking hash values of someone's hard drive, the police conducted a "search":

District Court Holds that Running Hash Values on Computer Is A Search: The case is United States v. Crist, 2008 WL 4682806 (M.D.Pa. October 22 2008) (Kane, C.J.). It's a child pornography case involving a warrantless search that raises a very interesting and important question of first impression: Is running a hash a Fourth Amendment search? (For background on what a "hash" is and why it matters, see here).

First, the facts. Crist is behind on his rent payments, and his landlord starts to evict him by hiring Sell to remove Crist's belongings and throw them away. Sell comes a cross Crist's computer, and he hands over the computer to his friend Hipple who he knows is looking for a computer. Hipple starts to look through the files, and he comes across child pornography: Hipple freaks out and calls the police. The police then conduct a warrantless forensic examination of the computer:

In the forensic examination, Agent Buckwash used the following procedure. First, Agent Buckwash created an "MD5 hash value" of Crist's hard drive. An MD5 hash value is a unique alphanumeric representation of the data, a sort of "fingerprint" or "digital DNA." When creating the hash value, Agent Buckwash used a "software write protect" in order to ensure that "nothing can be written to that hard drive." Supp. Tr. 88. Next, he ran a virus scan, during which he identified three relatively innocuous viruses. After that, he created an "image," or exact copy, of all the data on Crist's hard drive.

Agent Buckwash then opened up the image (not the actual hard drive) in a software program called EnCase, which is the principal tool in the analysis. He explained that EnCase does not access the hard drive in the traditional manner, i.e., through the computer's operating system. Rather, EnCase "reads the hard drive itself." Supp. Tr. 102. In other words, it reads every file-bit by bit, cluster by cluster-and creates a index of the files contained on the hard drive. EnCase can, therefore, bypass user-defined passwords, "break down complex file structures for examination," and recover "deleted" files as long as those files have not been written over. Supp. Tr. 102-03.

Once in EnCase, Agent Buckwash ran a "hash value and signature analysis on all of the files on the hard drive." Supp. Tr. 89. In doing so, he was able to "ingerprint" each file in the computer. Once he generated hash values of the files, he compared those hash values to the hash values of files that are known or suspected to contain child pornography. Agent Buckwash discovered five videos containing known child pornography. Attachment 5. He discovered 171 videos containing suspected child pornography.

One of the interesting questions here is whether the search that resulted was within the scope of Hipple's private search; different courts have approached this question differently. But for now the most interesting question is whether running the hash was a Fourth Amendment search. The Court concluded that it was, and that the evidence of child pornography discovered had to be suppressed:

The Government argues that no search occurred in running the EnCase program because the agents "didn't look at any files, they simply accessed the computer." 2d Supp. Tr. 16. The Court rejects this view and finds that the "running of hash values" is a search protected by the Fourth Amendment.

Computers are composed of many compartments, among them a "hard drive," which in turn is composed of many "platters," or disks. To derive the hash values of Crist's computer, the Government physically removed the hard drive from the computer, created a duplicate image of the hard drive without physically invading it, and applied the EnCase program to each compartment, disk, file, folder, and bit.2d Supp. Tr. 18-19. By subjecting the entire computer to a hash value analysis-every file, internet history, picture, and "buddy list" became available for Government review. Such examination constitutes a search.

I think this is generally a correct result: See my article Searches and Seizures in a Digital World, 119 Harv. L. Rev. 531 (2005), for the details. Still, given the lack of analysis here it's somewhat hard to know what to make of the decision. Which stage was the search — the creating the duplicate? The running of the hash? It's not really clear. I don't think it matters very much to this case, because the agent who got the positive hit on the hashes didn't then get a warrant. Instead, he immediately switched over to the EnCase "gallery view" function to see the images, which seems to be to be undoudtedly a search. Still, it's a really interesting question.

Posted on November 5, 2008 at 8:28 AM • 48 Comments • View Blog Reactions

P = NP?

People have been sending me this paper that "proves" that P != NP. These sorts of papers make the rounds regularly, and my advice is to not pay attention to any of them. G.J. Woeginger keeps a list of these papers -- he has 43 so far -- and points out:

The following paragraphs list many papers that try to contribute to the P-versus-NP question. Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but "just" shows that a certain approach to settling this question will never work out.)

Of course, there's a million-dollar prize for resolving the question -- so expect the flawed proofs to continue.

Posted on November 4, 2008 at 12:12 PM • 21 Comments • View Blog Reactions

Duplicating Keys from Photographs

Impressive.

EDITED TO ADD (11/3): Here's the paper.

Posted on November 3, 2008 at 1:35 PM • 43 Comments • View Blog Reactions

Understanding Terrorist Behavior

Two items, one short and one long.

The short one: "A Look at Terrorist Behavior: How They Prepare, Where They Strike," by Brent Smith, National Institute of Justice Journal, No. 260, 2008.

The long one: How Terrorist Groups End: Lessons for Countering al Qa'ida, by Seth G. Jones and Martin C. Libicki, RAND Corporation, 2008.

Posted on November 3, 2008 at 6:57 AM • 23 Comments • View Blog Reactions

Friday Squid Blogging: Long-Arm Squid Caught by Japanese Fishermen

Video in Japanese.

And an (unrelated) cartoon.

Posted on October 31, 2008 at 4:38 PM • 7 Comments • View Blog Reactions

Podcast Interview with Me

RSA interviewed me about my talk at the RSA Conference in London earlier this week.

Posted on October 31, 2008 at 1:52 PM • 0 Comments • View Blog Reactions

Keeping America Safe from Terrorism by Monitoring Distillery Webcams

Really:

We had an email recently from an observer "curious as to why the webcam that was inside the shop/bar is no longer there, or at least, functional". The email was from the Defense Threat Reduction Agency in the United States.

When we replied that it was simply a short term technical problem, we asked why on earth they could be interested in the comings and goings of a small Distillery off the West Coast of Scotland. Were there secret manoeuvres taking place in Loch Indaal, or even a threat of terrorists infiltrating the mainland via Islay?

The answer we received was even more surreal. Evidently the mission of the DTRA is to safeguard the US and its allies from weapons of mass destruction -chemical, biological, radiological, nuclear and high explosives. The department which contacted the Distillery deals with the implementation of the Chemical Weapons Convention, going to sites to verify treaty compliance. Funnily enough chemical weapon processes look very similar to the distilling process and as part of training there is a visit to a brewery for familiarization with reactors, batch processors and evaporators. As they said, it just goes to show how "tweaks" to the process flow or equipment, can create something very pleasant (whisky) or deadly (chemical weapons).

As they say: "In the post-Cold War environment, a unified, consistent approach to deterring, reducing and countering weapons of mass destruction is essential to maintaining our national security. Under DTRA, Department of Defense resources, expertise and capabilities are combined to ensure the United States remains ready and able to address the present and future WMD threat. We perform four essential functions to accomplish our mission: combat support, technology development, threat control and threat reduction. These functions form the basis for how we are organized and our daily activities. Together, they enable us to reduce the physical and psychological terror of weapons of mass destruction, thereby enhancing the security of the world's citizens. At the dawn of the 21st century, no other task is as challenging or demanding".

Posted on October 31, 2008 at 11:15 AM • 50 Comments • View Blog Reactions

UPC Switching Scam

It's not a new scam to switch bar codes and buy merchandise for a lower value, but how do you get away with over $1M worth of merchandise with this scam?

In a statement of facts filed with Tidwell's plea, he admitted that, during one year, he and others conspired to steal more than $1 million in merchandise from large retailers and sell the items through eBay. The targeted merchandise included high-end vacuum cleaners, electric welders, power winches, personal computers, and electric generators.

Tidwell created fraudulent UPC labels on his home personal computer. Conspirators entered various stores in Ohio, Illinois, Indiana, Pennsylvania and Texas and placed the fraudulent labels on merchandise they targeted, and then bought the items from the store. The fraudulent UPC labels attached to the merchandise would cause the item to be rung up for a price far below its actual retail value.

That requires a lot of really clueless checkout clerks.

Posted on October 31, 2008 at 6:43 AM • 63 Comments • View Blog Reactions

Horrible Identity Theft Story

This is a story of how smart people can be neutralized through stupid procedures.

Here's the part of the story where some poor guy's account get's completely f-ed. This thief had been bounced to the out-sourced to security so often that he must have made a check list of any possible questions they would ask him. Through whatever means, he managed to get the answers to these questions. Now when he called, he could give us the information we were asking for, but by this point we knew his voice so well that we still tried to get him to security. It worked like this: We put him on hold and dial the extension for security. We get a security rep and start to explain the situation; we tell them he was able to give the right information, but that we know is the same guy that's been calling for weeks and we are certain he is not the account holder. They begrudgingly take the call. Minutes later another one of us gets a call from a security rep saying they are giving us a customer who has been cleared by them. And here the thief was back in our department. For those of us who had come to know him, the fight waged on night after night.

Posted on October 30, 2008 at 12:10 PM • 39 Comments • View Blog Reactions

Movie-Plot Threat: Terrorists Using Twitter

No, really. (Commentary here.)

This is just ridiculous. Of course the bad guys will use all the communications tools available to the rest of us. They have to communicate, after all. They'll also use cars, water faucets, and all-you-can-eat buffet lunches. So what?

This commentary is dead on:

Steven Aftergood, a veteran intelligence analyst at the Federation of the American Scientists, doesn't dismiss the Army presentation out of hand. But nor does he think it's tackling a terribly seriously threat. "Red-teaming exercises to anticipate adversary operations are fundamental. But they need to be informed by a sense of what's realistic and important and what's not," he tells Danger Room. "If we have time to worry about 'Twitter threats' then we're in good shape. I mean, it's important to keep some sense of proportion."

Posted on October 30, 2008 at 7:51 AM • 33 Comments • View Blog Reactions

TSA News

Item 1: Kip Hawley says that the TSA may reduce size restrictions on liquids. You'll still have to take them out of your bag, but they can be larger than three ounces. The reasons -- so he states -- are that technologies are getting better, not that the threat is reduced.

I'm skeptical, of course. But read his post; it's interesting.

Item 2: Hawley responded to my response to his blog post about an article about me in The Atlantic.

Item 3: The Atlantic is holding a contest, based on Hawley's comment that the TSA is basically there to catch stupid terrorists:

And so, a contest: How would the Hawley Principle of Federally-Endorsed Mediocrity apply to other government endeavors?

Not the same as my movie-plot threat contest, but fun all the same.

Item 4: What would the TSA make of this?

Posted on October 29, 2008 at 2:27 PM • 33 Comments • View Blog Reactions

The Skein Hash Function

NIST is holding a competition to replace the SHA family of hash functions, which have been increasingly under attack. (I wrote about an early NIST hash workshop here.)

Skein is our submission (myself and seven others: Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker). Here's the paper:

Executive Summary

Skein is a new family of cryptographic hash functions. Its design combines speed, security, simplicity, and a great deal of flexibility in a modular package that is easy to analyze.

Skein is fast. Skein-512 -- our primary proposal -- hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core -- almost twice as fast as SHA-512 and three times faster than SHA-256. An optional hash-tree mode speeds up parallelizable implementations even more. Skein is fast for short messages, too; Skein-512 hashes short messages in about 1000 clock cycles.

Skein is secure. Its conservative design is based on the Threefish block cipher. Our current best attack on Threefish-512 is on 25 of 72 rounds, for a safety factor of 2.9. For comparison, at a similar stage in the standardization process, the AES encryption algorithm had an attack on 6 of 10 rounds, for a safety factor of only 1.7. Additionally, Skein has a number of provably secure properties, greatly increasing confidence in the algorithm.

Skein is simple. Using only three primitive operations, the Skein compression function can be easily understood and remembered. The rest of the algorithm is a straightforward iteration of this function.

Skein is flexible. Skein is defined for three different internal state sizes -- 256 bits, 512 bits, and 1024 bits -- and any output size. This allows Skein to be a drop-in replacement for the entire SHA family of hash functions. A completely optional and extendable argument system makes Skein an efficient tool to use for a very large number of functions: a PRNG, a stream cipher, a key derivation function, authentication without the overhead of HMAC, and a personalization capability. All these features can be implemented with very low overhead. Together with the Threefish large-block cipher at Skein core, this design provides a full set of symmetric cryptographic primitives suitable for most modern applications.

Skein is efficient on a variety of platforms, both hardware and software. Skein-512 can be implemented in about 200 bytes of state. Small devices, such as 8-bit smart cards, can implement Skein-256 using about 100 bytes of memory. Larger devices can implement the larger versions of Skein to achieve faster speeds.

Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Here's source code, text vectors, and the like for Skein. Watch the Skein website for any updates -- new code, new results, new implementations, the proofs.

NIST's deadline is Friday. It seems as if everyone -- including many amateurs -- is working on a hash function, and I predict that NIST will receive at least 80 submissions. (Compare this to the sixteen NIST submissions received for the AES competition in 1998.) I expect people to start posting their submissions over the weekend. (Ron Rivest already presented MD6 at Crypto in August.) Probably the best place to watch for new hash functions is here; I'll try to keep a listing of the submissions myself.

The selection process will take around four years. I've previously called this sort of thing a cryptographic demolition derby -- last one left standing wins -- but that's only half true. Certainly all the groups will spend the next couple of years trying to cryptanalyze each other, but in the end there will be a bunch of unbroken algorithms; NIST will select one based on performance and features.

NIST has stated that the goal of this process is not to choose the best standard but to choose a good standard. I think that's smart of them; in this process, "best" is the enemy of "good." My advice is this: immediately sort them based on performance and features. Ask the cryptographic community to focus its attention on the top dozen, rather than spread its attention across all 80 -- although I also expect that most of the amateur submissions will be rejected by NIST for not being "complete and proper." Otherwise, people will break the easy ones and the better ones will go unanalyzed.

EDITED TO ADD (10/30): Here is a single website for all information, including cryptanalysis, of all the SHA-3 submissions. A spoke to a reporter who told me that, as of yesterday, NIST had received 30 submissions. And three news articles about Skein.

Posted on October 29, 2008 at 6:35 AM • 103 Comments • View Blog Reactions

Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.