U.S. troops in hostile areas sometimes find reams of shredded documents that might provide important information if someone could reassemble them quickly. But what’s the chance of that? With this in mind, the Defense Advanced Research Projects Agency, whose work helped create the Internet, recently launched the Shredder Challenge and invited groups to solve five increasingly difficult shredded-document puzzles. The winner would get $50,000. New Scientist magazine called it “the race to crack the world’s hardest puzzle.” Or, as Dan Kaufman, director of DARPA’s information innovation office, put it: “Lots of experts were skeptical that a solution could be produced at all, let alone within the short time frame.”
About 9,000 teams took up the challenge, and two days before the Dec. 4 deadline, a San Francisco-based group called “All Your Shreds Are Belong to U.S.” solved the puzzles. According to a DARPA announcement, the group used “a combination of custom-coded, computer-vision algorithms to suggest fragment pairings to human assemblers for verification.” It took All Your Shreds nearly 600 man-hours to come up with a solution and reassemble the five documents, which had been shredded into more than 10,000 pieces.
DARPA said, “The goal was to identify and assess potential capabilities that could be used by our warfighters operating in war zones, but might also create vulnerabilities to sensitive information that is protected through our own shredding practices throughout the U.S. national security community.”
The agency’s director, Regina E. Dugan, said the contest demonstrated the usefulness of having a large number of problem-solvers. “The varied methods used have potential implications for so-called ‘wicked problems,’ generally considered insolvable by conventional means,” she said.”
According to New Scientist, the All Your Shreds team was made up of three programmers: Otavio Good, creator of the visual translation tool Word Lens; Luke Alonso, a mobile phone software developer; and Keith Walker, who works on satellite software at Lockheed Martin. Their winning algorithm automatically suggested matching pieces of the shredded documents based on factors such as the shape of the rip or the marks on the paper. The trio then tasked a group of friends to assemble the bits by hand.
Good told the magazine that his team’s success doesn’t mean that shredded documents will soon be insecure: “The challenges that DARPA gave us were actually simple compared to if you have a bin full of lots of shredded pieces of paper. Reconstructing these documents was not easy at all. I don’t think you have much to worry about with your shredded documents.”