DARPA offers $50,000 prize for reading shredded messages

DARPA

The $50,000 DARPA Shredder Challenge calls on participants to reconstruct handwritten messages that have been shredded beyond recognition, including this one.

DARPA's latest tech challenge is offering $50,000 for a task worthy of secret agents: piecing together messages that have been shredded into thousands of bits.

The Defense Advanced Research Projects Agency, the Pentagon think tank that previously brought you multimillion-dollar robo-car races and a nationwide hunt for red balloons, put five ripped-up puzzles online today to kick off its Shredder Challenge. If someone wins, and I'm betting that someone will, that would be good news and bad news for the Defense Department — and for folks like you and me.


"The goal is 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," DARPA said in its contest announcement.

Here's how the contest works: Participants register via the Shredder Challenge website, and then download five bunches of files that are essentially screenshots of shredded-up documents, plus instructions. They'll have to figure out how to put the documents back together, either by using computer analysis or by matching up itty-bitty pieces of printouts. Then they'll have to send DARPA an email with scans of the completed puzzles, the answers to questions about each puzzle ... and an explanation of the reasoning process that led to the solution.

Each of the puzzles carries a point value, and an online leader board will track the scores of the top contestants. DARPA will announce the winner and the amount of the prize awarded on Dec. 5, based on the points earned as well as the time stamps for submissions.

Hundreds sign up
"We are all pretty excited about this one," Dan Kaufman, director of the Information Innovation Office, told me in an email. So are puzzle fans: Soon after the competition opened, DARPA warned in a Twitter update that, "due to interest in the Shredder Challenge, there may be a delay accessing" the puzzle website. The Web traffic jam eased once DARPA beefed up its bandwidth.

Kaufman said this afternoon that "registrations were at 240 when I last checked, and not slowing down."

When I spoke with Kaufman, he said no one had yet submitted an entry. He couldn't predict whether it would take hours or days for puzzle sleuths to submit solutions. That's what makes the exercise interesting.

Kaufman's a veteran of 2009's Red Balloon Challenge, which asked participants to figure out the locations of 10 red balloons scattered around the country. He recalled that there was similar uncertainty about the outcome back then: "We were torn between 'It will never be solved' and 'Somebody's gotta solve this.'"

It turned out that researchers from the Massachusetts Institute of Technology's Media Lab figured out the locations in just under nine hours, winning $40,000 in the process. A research paper published this week in the journal Science laid out the MIT team's winning strategy: a system of "recursive incentives" that promised payoffs for those who discovered the balloons, as well as those who recruited the discoverers.

MIT's Alexander Pentland and his colleagues said the recursive-reward arrangement could be used for life-and-death searches — for example, to look for a missing child, a criminal at large or the survivors of a natural disaster.

Good news, bad news
Kaufman told me that the winner of the Shredder Challenge may well use a method that DARPA's own researchers haven't thought of. Such methods could be used to read documents that have been shredded by the bad guys, such as al-Qaida operatives in Afghanistan. "Currently, this process is much too slow and too labor-intensive, particularly if the documents are hand-written," Kaufman said in a news release. "We are looking to the Shredder Challenge to generate some leap-ahead thinking in this area."

Better message-demangling methods also could be used by bad guys to reconstruct financial statements, credit card reports and other sensitive documents that consumers thought had been safely disposed of.

"I'm concerned about the privacy implications," my colleague at msnbc.com's Red Tape Chronicles, Bob Sullivan, told me today.

Kaufman acknowledged that the contest's outcome might make you feel less secure about what happens to their shredded documents. But if that's the case, it's better to know that up front instead of burying your head in the sand. "I would say the 'ostrich defense' is not a good one," he told me.

Who knows? Maybe the first thing to come out of DARPA's latest challenge will be a rush to buy shredders that grind paper into powder. What do you think? Weigh in with your comments below.

Other challenges from DARPA:


Connect with the Cosmic Log community by "liking" the log's Facebook page, following @b0yle on Twitter or adding me to your Google+ circle. You can also check out "The Case for Pluto," my book about the controversial dwarf planet and the search for other worlds.

Discuss this post

Jump to discussion page: 1 2

I've found that using shredded paper to line gerbil or snake cages (I donate the paper to friends) is a pretty good way to ensure that nobody attempts to piece my "secret documents" - i.e. junk mail with my address on it in 90% of cases - back together.

  • 7 votes
Reply#2 - Thu Oct 27, 2011 9:07 PM EDT

Heck someone can get that by just accessing your information via 411.com or whitepages.com.

    #2.1 - Tue Nov 1, 2011 3:31 PM EDT
    Reply

    if you shred your docs, and toss a handful or two into the regular garbage and the rest into the recycle bin, how could anyone piece it all back together?

    • 5 votes
    Reply#3 - Thu Oct 27, 2011 9:39 PM EDT

    True! And, beyond that, if you shred a bunch of unrelated papers and then stir up the bits, it seems highly unlikely that anyone would ever be able to reassemble them. By the time they did, the information would be obsolete and meaningless.

    • 1 vote
    #3.1 - Thu Oct 27, 2011 9:42 PM EDT

    Why bother. It's my understanding that the Germans already have a machine that will put shredded paper back together.

    • 2 votes
    #3.2 - Thu Oct 27, 2011 10:11 PM EDT

    How about - just get a good quality shredder that makes pieces so tiny that it's going to be next to impossible to put them together? The pieces in the picture are not tiny enough - that's what you get for using a mediocre shredder.

    • 2 votes
    #3.3 - Fri Oct 28, 2011 12:35 AM EDT

    When I cut up credit cards, I throw away part of them one week and the rest sometime later.

    • 2 votes
    #3.4 - Fri Oct 28, 2011 7:20 AM EDT

    1) Buy metal garbage can.

    2) Buy lighter fluid.

    3) ???

    4) Profit

    • 8 votes
    #3.5 - Fri Oct 28, 2011 8:12 AM EDT

    I do a similar practice of separating shredded documents/credit cards into different garbage bins and throw them out at different times. I'll also shred in some non important papers, like form letters addressed to nobody and mix it in. I've used piles of it to help light the bbq.

    If I had the time, I'd take on this challenge. I've always been a whiz at jig saw puzzles and can easily spend countless hours on this. I bet I can have it together in 3-4 days. I just don't have the time anymore.

      #3.6 - Fri Oct 28, 2011 10:57 AM EDT
      Reply

      Write a computer program (in MATLAB) that takes an image of the pieces and first aligns the letters on pieces as to the orientation and then begins matching edges with a certain probability...then check to see if the document reads well or makes sense...seem like a pretty straightforward project.

      Still, write a computer program that can piece together shredded documents and people will just invent a better shredder...maybe one that adds water to the shreds and creates a slurry in the can...then, you are back nothing.

      • 1 vote
      Reply#4 - Thu Oct 27, 2011 9:53 PM EDT

      Better shredders exist. The one that created the shreds in the picture is only a mediocre one.

      Devising a computationally efficient algorithm to put the pieces together has got to be no joke. If it was, DARPA wouldn't have offered a reward for it.

        #4.1 - Fri Oct 28, 2011 12:36 AM EDT
        Reply

        Why just mix paper with it lots of disgusting things work much better. Cat litter box or used baby diapers come to mind. Still even simple water will make it into a glue. I know a company i worked for years ago used to mix soapy water with finely shredded dod confidential documents and sell the resulting stuff to a paper mill.

          Reply#5 - Thu Oct 27, 2011 10:03 PM EDT

          I remember the Man Show had one of these. You opened it up and inside were two little Asian girls they kept in line by threatening to adopt them out to Rosie O'Donnell.

          • 1 vote
          Reply#6 - Thu Oct 27, 2011 10:18 PM EDT

          Burn the documents. It's hard to realign ashes.

          • 7 votes
          Reply#7 - Thu Oct 27, 2011 10:28 PM EDT

          I shred the paper, then when I make a fire for my fireplace, I toss in the shredded paper.  Unless there is a way to get words off of ash, I am 100% certain my info is safely destroyed

          • 3 votes
          Reply#8 - Thu Oct 27, 2011 11:01 PM EDT

          See you in federal prison when EPA gets to your house for burning commercial waste without a permit and endangering the lives of polar bears, arctic seals, and Santa's elves. They are tracking back to your IP address right now. Run for your freedom before the find the shredded porn.

          • 1 vote
          #8.1 - Sat Oct 29, 2011 11:43 PM EDT
          Reply

          I like a good challenge so I've signed up and have downloaded the five images and questions.

          I have always enjoyed reconstructing a mystery . . . it's all in fun.

          • 2 votes
          Reply#9 - Thu Oct 27, 2011 11:23 PM EDT

          It does look fun but when I tried to register all I received was a error message?

            #9.1 - Mon Oct 31, 2011 1:07 PM EDT
            Reply

            there was a story on MSNBC here a couple of weeks ago where some Israelis had invented a computer program to piece together sections of documents that were in pieces, but also which had been dispersed to museums all over the world. Time to look THAT up!

              Reply#10 - Thu Oct 27, 2011 11:25 PM EDT

              Use the paper that the bookies use that dissolves the instant it hits water. Fire works too. They should work on a computer program that can match a partial fingerprint from a shell casing to a list of possible matches. Most criminals have their prints on file. Not too many use gloves to load clips. It makes it difficult to do.

                Reply#11 - Thu Oct 27, 2011 11:57 PM EDT

                1. Flush about 1/4 - 1/2 of your shred down the john. Anybody desperate enough to go get it can do so.

                2. Doesn't the government use cross-cut shredders (like we did 25 years ago) any more?

                  Reply#12 - Fri Oct 28, 2011 12:36 AM EDT

                  I thought embassies and field agents burn the papers these days?

                  What ever happened to the Ricky McCormick case and his encrypted notes?

                    Reply#13 - Fri Oct 28, 2011 6:58 AM EDT

                    My perspective on this is that I am a bit dumbfounded that reassembling and reading shredded documents is viewed as a "challenge" at the dawn of the early-21st century . . .

                    Considering (a) that one registers for the DARPA Shredder Challenge and downloads the five puzzles on Friday October 28, 2011 and (b) that the solutions need to be completed for submission by Sunday December 4, 2011, this maps to 38 days, which in some respects is not a lot of time when one essentially has to start from scratch with nothing more onboard than a vastly high I. Q., a Mac Pro, and advanced expertise in Computer Science and Mathematics . . .

                    In some respects, I am intrigued by the challenge, but in the grand scheme of everything the practical reality is that with only one $50,000 prize being awarded, the probability of making any money is dismal at best, since it is highly likely that there are a few idiot savants who can solve all five puzzles in just a few minutes, although finding the idiot savants might not be so easy, unless one of their caregivers happens to have enough time to read "Cosmic Log" on a daily basis . . .

                    If the shredded pieces are scanned at a sufficiently high resolution, then this is a trivial problem, because no two pieces will be identical, which basically reduces the problem to solving a typical puzzle that has no identical puzzle pieces but has a single definitive solution, which in some respects is a variation of the Four Color Map Problem and the Königsberg Bridge Problem, along with a few other such things . . .

                    http://en.wikipedia.org/wiki/Four_color_theorem

                    http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html

                    http://mathworld.wolfram.com/EulerianCycle.html

                    http://mathworld.wolfram.com/HamiltonianCycle.html

                    Doing it solely with a set of computer algorithms is a bit too complex of an activity when one allows for a bit of imprecision in the fit of some of the shredded pieces of paper or bits of paper simply being missing, but using a combination of computer algorithms and human perception does not appear to me to be a vastly difficult strategy, since a set of computer algorithms can get the shredded paper pieces "ballpark", at which time a person can do a bit of fine-tuning, since yet another presumption regarding the computer algorithms is that they include providing the ability to move and to reorient the shredded paper pieces visually, perhaps on an iPad using touch gestures, which is considerably easier for a person to do than for a computer algorithm to do, since if it is done via a set of computer algorithm, then the content on the surface of the shredded pieces of paper must be considered and handled by additional computer algorithms, which adds significant complexity to the complete set of computer algorithms . . .

                    [NOTE: Intuition strongly suggests that the DARPA Shredder Challenge is an excellent project for a one or perhaps two semester fourth-year Computer Science undergraduate course, although yet another likely reality is that some brighter junior high school students should have all five puzzles solved sometime this weekend, depending primarily on their abilities to postpone spanking the monkey for a few days . . . ]

                    If the CIA, FBI, NSA, and all the intelligence services of our great nation's military do not already have the ability to solve these puzzles very quickly, then this is quite disturbing news and certainly is definitive proof that our intelligence agencies are headed by dimwitted leaders, at best, where the key to understanding this perspective is that it specifically excludes any need whatsoever to wander into cryptoanalysis, which is a completely different and vastly more complex problem altogether, for sure . . .

                    For sure!

                    For example, if the message or information contained on the shredded pieces of paper comprises several languages and secret codes, then best wishes on solving the problem if you happen to be fluent in only one language and have no ideas about deciphering secret codes, but if it simply is a matter of arranging a set of puzzle pieces where (a) no two puzzle pieces are identical and (b) there are no missing puzzle pieces that are crucial to the solution, then I suggest that it is a trivial problem, especially when there is a bit of significant help from a set of computer algorithms that arrange the puzzle pieces in a "ballpark" best-fit pattern before the work transfers to a human puzzle solver for fine-tuning and completing . . .

                    Nevertheless, since I am intrigued by the DARPA Shredder Challenge, I registered and downloaded the five puzzles, and after doing an quick overview, the puzzles increase in complexity where the first puzzle is one image of a bunch of shredded pieces of paper, while the fifth puzzle comprises twenty images of a bunch of significantly smaller shredded pieces of paper, which tends strongly to skew the overall strategy in favor of a set of computer algorithms, although for all practical purposes solving the fifth puzzle mostly is a matter of being able to solve twenty of the first puzzles, albeit with a few caveats, since in the universe of Computer Science and Mathematics (a) doing something one time is the specific case but (b) doing it two times is the general case, at least with respect to devising algorithms and formulas . . .

                    In fact, my general perspective is that the DARPA Shredder Challenge is yet another variation of what I like to call "The National I. Q. Test™", where for example one of the easiest aspects of "The National I. Q. Test" to understand involves purported "I. Q. Tests" that are sold at bookstores and are available online, where the fact of the matter is that if you pay for an "I. Q. Test" then you automatically fail "The National I. Q. Test", because this is definitive proof (a) that you are unaware of your innate intelligence and (b) that you actually believe someone else knows enough to be able to determine your intelligence with any accuracy . . .

                    Explaining my perspective on "The National I. Q. Test" with an example, when I was in the fifth grade and the teacher switched to focusing on multiplication of single and double-digit numbers, I would sneak out of the classroom and then spend the next hour or so crawling around underneath the classroom, which among other things was possible, because the classroom was a portable building on piers, so it was approximately three feet above ground . . .

                    Apparently, unbeknown to me at the time, I was not so successful in clandestinely sneaking out of the classroom, and the fact that I crawled around underneath the classroom every day at approximately the same time for an hour or so greatly disturbed the teacher, who one can only guess must have imagined that I was "dog boy" or otherwise mentally challenged . . .

                    After a while, one day the teacher told me that there was fellow in another classroom who was having problems with puzzles and needed some help and that she thought I might be able to help the fellow with his puzzles, which I thought was a great idea and looked to be a lot of FUN--which it was--except that the fellow really was having a lot of difficulties solving very simple puzzles . . .

                    As an example, one of the puzzles involved determining the easiest and most efficient way to get exactly one quart of water into bucket from a stream in the fewest number of trips when you have a two-quart bucket and a five-quart bucket . . .

                    My first solution was to suggest walking to the stream and then filling the two-quart bucket half full, but the fellow did not like this solution, so I continued with more solutions of increasing complexity until the fellow was happy, even though the first solution was the best, at least with a few caveats . . .

                    Some of the moderately complex solutions included me drinking some of the water to avoid the additional rule regarding the way unneeded water had to be handled, where it had to be taken back to stream in a bucket and then dumped in the stream, which also did not make the fellow happen, even though (a) drinking four quarts of water clearly is not a difficult thing to do and (b) there were no formally stated time limits on getting exactly one quart of water into one of the buckets, where this flavor of the solution maps to one trip to the stream to fill the five-quart bucket, and then filling the two-quart bucket from the five-quart bucket two times, where each time you drink the two quarts of water, and then you have one quart of water in the five-quart bucket remaining, which solves the problem in one trip . . .

                    [NOTE: Yet another solution is to take both buckets to the stream, but the rules prevent it . . . ]

                    Granted, I made a few presumptions regarding the one-trip solution with the two-quart bucket, but this is way it works, and the three primary presumptions were (a) that I could do this on either summer solstice or winter equinox on a day with clear skies, (b) that I had an accurately set wristwatch, and (c) that there was a tiny sharp-edged rock that I could use to scratch a line on the inside of the metal bucket at its halfway point, which makes excellent sense if you ponder it for a while and know something about sundials and so forth . . .

                    Of course, there are other ways to determine the halfway point of the two-quart bucket, including having a bit of FUN with some sticks and shrubbery, but so what . . .

                    So what!

                    And so forth and so on, with the result that after helping the fellow solve all his puzzles, nobody had any problems with my crawling around underneath the classroom, which was all I knew about it for about three more decades, at which time I learned that the fellow actually was a clinical psychologist and that the puzzles were an I. Q. Test, with the result being that there was no way to measure my I. Q. other than to state that it was higher than the test was able to measure, which at the time was 170, which mapped to my I. Q. being "well over 170", for sure . . .

                    For sure!

                    Curiously, this does not always map to my being particularly smart in some respects, but it makes it virtually trivial for me to make sense of certain types of puzzles, which specifically nvolve numerical sequences, geometric patterns, and analogies, with analogies being very easy, although my solutions sometimes are based on some of the more highly abstruse and arcane definitions and uses of words, since I enjoy studying "The Oxford Dictionary of the English Language" and the history and evolution of the way words are used over time, where I might solve an analogy using the definition of one word from the 19th century but using the definition of another word from the 11th century, unless someone reminds me that I need to restrict the solution for an analogy solely to the 20th or 21st century definitions of words . . .

                    Summarizing, while this is an intriguing puzzle, it has a trivial solution, and in the grand scheme of everything I think that at the end of 38 days it is highly likely that one will have more money by working at Walmart as a customer greeter than by playing with this puzzle, which from my perspective is the practical solution to the higher-level puzzle, which to be specific is to avoid being on any official list compiled by the federal government of people who clearly have no clues about Artificial Intelligence, Computer Science, Geometry, Mathematics, and Pattern Recognition . . .

                    Explained another way, you want to register but you do not want to submit an entry or, even worse, to win . . .

                    In other words, you want to be on the list of people who are intrigued by the problem (hence registered and downloaded the puzzles) but have sufficient sense to realize that it is part of a "psyop" designed specifically (a) to trick our great nation's enemies into believing that our intelligence community recently fell off a turnip truck and (b) to compile a list of people who have nothing better to do than to waste time solving trivial puzzles for free . . .

                    Lots of FUN! :-o

                    P. S. If anyone had taken the time to ask me why I crawled around underneath the classroom during multiplication table time, the answer is that I was a bit dumbfounded that anyone in the 5th grade would be unable to multiply single-digit and double-digit numbers in their mind virtually instantly, so rather than endure an hour of mind-numbing multiplication table drills, I thought it made more sense to crawl around underneath the classroom to study the plumbing pipes and how they were installed, routed, and connected, since at the time I had changed my career goal from (a) being a garbage truck owner-operator to (b) being a plumber, which is fabulous . . .

                    Fabulous! :D

                    • 2 votes
                    Reply#14 - Fri Oct 28, 2011 7:05 AM EDT

                    Better than your mundane idea is the following one. Travel to Iran. They are experts in this field. Just use your post as a show of your intelligence. Iran reassembled by hand millions of shredded documents the US left behind when we fled that country. They employed only the finest looking women they could find because the ugly women were all busy fighting Iraq which was the Iranian men's way of getting rid of them. You get to meet selectively breed hot Iranian chicks which are fine looking indeed. You get to solve your virginity problem and win this prize when you return with the secret Iranian techniques.

                      #14.1 - Sat Oct 29, 2011 11:56 PM EDT
                      Reply

                      Ah, use a blender and turn it to high pulses. It will turn it to dust for crying out load.

                        Reply#15 - Fri Oct 28, 2011 7:17 AM EDT

                        Creating a paper shreder that turns paper into powder is very simple I can't understand why some one hasn't done it already or has it?

                          Reply#16 - Fri Oct 28, 2011 8:09 AM EDT

                          Ask an Iranian in the late 70s. They were able to piece together the "shredded messages from the US Emabassy"

                          • 1 vote
                          Reply#17 - Fri Oct 28, 2011 8:51 AM EDT

                          why anyone would want to do this, is completely beyond me .... Makes me want to listen to Styx - Too Much Time On My Hands!

                          • 1 vote
                          Reply#18 - Fri Oct 28, 2011 9:11 AM EDT

                          Styx?! - Now you dated yourself..... :) One of my favorite bands as a teenager. Oops, now I've dated myself too....

                          • 1 vote
                          #18.1 - Fri Oct 28, 2011 10:12 AM EDT

                          I still have my original "Paradise Theater" LP with the cool laser graphic on the disc! Only played once, when I recorded it to a cassette--which, by the time was wore out, I was tired of it--so yeah, still in Pristine Condition! Wonder what I could get on eBay for it?! lol. And yes...I'm dated now!

                          • 1 vote
                          #18.2 - Fri Oct 28, 2011 3:27 PM EDT

                          LOL .. thanks :) 44yrs, young and proud of it! Should have been born a decade before, I'm thinking, lol ... One of the simple pleasures in life, great classic rock! My 'hobby of choice' .. internet DJ'ing! Could never sit still long enough to piece together bits of shredded paper, but could sit for hours and play the tunes!

                            #18.3 - Fri Oct 28, 2011 5:30 PM EDT
                            Reply

                            Be better to just zap it with one of their laser beams why use a shredder!

                            • 1 vote
                            Reply#19 - Fri Oct 28, 2011 9:33 AM EDT

                            I know what it says!!!! "Drink More Ovaltine"(from A Christmas Story)!!

                            • 2 votes
                            Reply#20 - Fri Oct 28, 2011 9:35 AM EDT

                            Cross shredders are your friend. Straight cutting like these guys did is pointless.

                              Reply#21 - Fri Oct 28, 2011 11:24 AM EDT

                              I think a lot of you misunderstand this contest. It's not to help DARPA shred documents better, it's to determine if there is a better way to piece together someone else's shredded documents. I'm fairly certain that if this was a simple task the challenge would not have been put forth.

                                Reply#22 - Fri Oct 28, 2011 11:25 AM EDT

                                If you blow each piece up large enough you'll probably notice that no two pieces are cut exactly the same. You might be able to match up each individual fiber

                                What's the point? Anybody with really sensitive material would take the effort to make sure their documents were totally destroyed. Shredding isn't enough.

                                • 1 vote
                                #22.1 - Fri Oct 28, 2011 11:43 AM EDT
                                Reply

                                Compress it into a block and then grind that block into sawdust. Problem solved.

                                  Reply#23 - Fri Oct 28, 2011 11:28 AM EDT

                                  I don't see why a prize is necessary for this.

                                    Reply#24 - Fri Oct 28, 2011 11:36 AM EDT

                                    Why not burn the documents? No one can get documents out of ashes (Skinny Block Lit. Mr. Tomphson)

                                      Reply#25 - Fri Oct 28, 2011 11:37 AM EDT

                                      We always do things the hard way, that's why. Remember in the 1960s, when the Space Race was happening. Our astronauts needed to write in space so the US spent over $30,000.00 developing a pen that would work in zero gravity, upside down, etc. ...

                                      The Russians sent a pencil.

                                      • 2 votes
                                      #25.1 - Fri Oct 28, 2011 4:56 PM EDT
                                      Reply

                                      i can do it

                                        Reply#26 - Fri Oct 28, 2011 11:39 AM EDT
                                        Jump to discussion page: 1 2
                                        You're in Easy Mode. If you prefer, you can use XHTML Mode instead.
                                        As a new user, you may notice a few temporary content restrictions. Click here for more info.