Please create an account to participate in the Slashdot moderation system

 



Forgot your password?
typodupeerror
Encryption Privacy Security Technology

San Francisco Team Wins DARPA's De-Shredding Contest 94

Posted by timothy
from the california-v-greenwood-1988 dept.
New submitter karlnyberg writes with an update to the recently announced de-shredding challenge posted by DARPA: "The team 'All Your Shreds Are Belong To U.S.' has correctly solved all five puzzles, and the Challenge has now ended. You may view the winning team's submissions as well as the complete puzzle solutions by following the links on our homepage. We recognize that many of our participants have devoted countless hours to painstakingly piecing our puzzles back together, and we truly appreciate everyone's efforts. Hopefully you enjoyed the Challenge and learned something new along the way. We certainly did!"
This discussion has been archived. No new comments can be posted.

San Francisco Team Wins DARPA's De-Shredding Contest

Comments Filter:
  • Jackasses (Score:5, Interesting)

    by masternerdguy (2468142) on Friday December 02, 2011 @06:47PM (#38245602)
    Thanks for helping the government spy on me.
    • by datapharmer (1099455) on Friday December 02, 2011 @06:58PM (#38245728) Homepage
      Psshht. shredding is for newbs. Shred, burn, mix ashes with sludge from numerous porta-potties, divide contents and freeze. Shoot it into the air with a homemade cannon. Let it be cherished by a naive meteorite collector where it is safe from discovery by the secret black helicopter cia-army-fbi-nsa police detectives and you are good to go.
      • I use water.

        There is a bucket in the corner, documents that have been scanned are tossed in the bucket, water is topped up every so often. Stir the paper around, bag the ball of gunk and recycle or garbage it.

        Works quite well.

    • by cultiv8 (1660093)
      Seriously, now i can't even throw shredded paper on my neighbors yard without fear of getting caught.
    • Re:Jackasses (Score:5, Insightful)

      by mrmeval (662166) <[moc.liamg] [ta] [lavemrm]> on Friday December 02, 2011 @07:32PM (#38246056) Journal

      The government just PAID to prove that five shredding methods suck.

      If you're still using them you're just a narcissistic terror poodle.

    • Re:Jackasses (Score:5, Insightful)

      by artor3 (1344997) on Friday December 02, 2011 @08:00PM (#38246316)

      Oh for fucks sake. THEY DON'T CARE ABOUT YOU. There are no feds swooping in in black helicopters to dig through your garbage and piece together your shredded electric bill.

      Honestly, mods, giving positive reinforcement to this sort of paranoia is only hurting the people suffering from it.

      • Re: (Score:3, Interesting)

        The stories about them placing GPS modules in cars because the people bothered to make jokes on the internet or happened to be related to a criminal say otherwise.

        And in this day and age, everybody's a criminal. The FBI follow up on every anonymous tip sent to them online, and no matter what you tell them, they will follow you around until you're officially deemed uninteresting. Then they'll check up on you every now and then just to make sure. And they will dig up something on you that will justify th
      • Re: (Score:3, Insightful)

        by Beeftopia (1846720)
        Even paranoids have enemies.
      • by hairyfeet (841228)

        Ya know, i used to laugh at all the shit, now I'm not so sure. Whatever is coming out of those C130s that fly over sure as fuck ain't like anything they USED to fly and I've been watching them fly over from the local AFB since I was a kid so I'd have noticed, but whatever is in the C130s now leaves a film almost like crop dusting and whatever it is makes people hack like mad the next day.

        So frankly who knows. I do know with all the lies they have been caught in from just the last 20 years i wouldn't trust

      • by ultranova (717540)

        Oh for fucks sake. THEY DON'T CARE ABOUT YOU.

        Of course they do. As times keep on getting worse, the possibility of Joe 99% engaging in subversive actions gets ever greater, so if the 1% are to keep on looting the rest, they need to tighten the grip ever more. And of course, even in good times, "they" are people who love having power over others, either because they think they know better than everyone else or simply because they have issues.

        There are no feds swooping in in black helicopters to dig through

    • by ultranova (717540)

      Thanks for helping the government spy on me.

      If you don't want the government to spy on you, burn the papers and scatter the ashes. Shredders have never provided any real security, since you can simply re-assemble the pieces by hand, it just takes a while.

  • opportunity (Score:3, Insightful)

    by roman_mir (125474) on Friday December 02, 2011 @06:55PM (#38245674) Homepage Journal

    There is a business opportunity for better shredders, the kind that would pulverize the paper or better just burn it.

    A shredder with a vortex or a burner inside.

    Don't get me wrong, it's an interesting technical challenge that this was done, but if you want to keep your paper out of government's hands you shouldn't be just shredding the paper.

    • Re:opportunity (Score:5, Insightful)

      by Beardo the Bearded (321478) on Friday December 02, 2011 @07:30PM (#38246032)

      Actually, it's not the "US government reading our stuff" thing that caused this whole contest. If The NSA wants your credit card info, they'll just ask Visa for it, pay the usual fees, then just get it mailed to them.

      The government shreds a lot of paper. Probably more in a day than I generate in a lifetime. The Classified shit they shred when they're done (IAW DOD-WTF-1234) because it's easier than burning. Trust me, you don't want to burn Classified stuff.

      Someone probably said, "hey, do you guys think that with today's video cards and CPU power, someone could unshred our shit?"

      "Oh... aw fuck, Dave, I dunno. Let's ask DARPA."

      Thus the challenge.

      • why cant we burn classified stuff? if memory serves paper is pretty flammable. thats one of the great things about paper as a medium, its really fragile, hell if they wanted to they could wet the paper, mix up some plaster, turn the classified documents into paper mache and then shoot it to shit when it dries, theres no coming back from that.
        • by wasme (35127)
          You don't want to burn classified stuff because the government can read what was on the paper from the smoke patterns rising from the incinerator. . (Yes, the above was a joke. And not an original one either. I heard it a few years ago when an ex-government spook was being interviewed on the radio and he was talking about how paranoid he'd become about destroying personal information. Referring to how much he learned over his career about the tools available to recover stuff (from paper, or from harddrive
        • by TheLink (130905)
          I think the trick is to somehow make an incinerator that's the size of an office shredder, is very safe and can handle paper AND staples/paper clips without breaking.

          The trouble is the safety bit especially when the device has to be small.

          Anyone can make a big incinerator. I suppose in top secret places, you'd shred the documents first then send the results to be incinerated. So the documents are exposed in shredded form only within the premise.
          • by wwphx (225607)
            There was an incident a decade or two back where a US TLA shut down one of its document incinerators for maintenance, and they decided to inspect it since it was offline. They dug around the ashes and found totally intact burn bags. They were piling them in so fast and deep that it squeezed out the oxygen and the bags on the bottom didn't burn.

            I think there was an engineering and procedure mod before the incinerator went back online.
      • by TubeSteak (669689)

        The government shreds a lot of paper. Probably more in a day than I generate in a lifetime. The Classified shit they shred when they're done (IAW DOD-WTF-1234) because it's easier than burning. Trust me, you don't want to burn Classified stuff.

        Someone probably said, "hey, do you guys think that with today's video cards and CPU power, someone could unshred our shit?"

        "Oh... aw fuck, Dave, I dunno. Let's ask DARPA."

        Thus the challenge.

        Not at all.
        When the government shreds classified documents, at a bare minimum, they turn it into confetti.
        At the highest classification levels, you end up with strips less than 1mm x 5mm.
        There's nothing recoverable from that level of shred.

        • by ultranova (717540)

          At the highest classification levels, you end up with strips less than 1mm x 5mm.
          There's nothing recoverable from that level of shred.

          Of course there is, it's just a lot of work. Scan the pieces, find likely matching edges for each piece based on how closely they match, then start going through various combinations based on image (letter shape) recognition, filter based on a dictionary (what combinations create legible words).

          • by kcitren (72383)
            Documents are shredded one by one, a bag full of shredded materials might have hundreds of pages in it, each cross-shredded uniformly.
    • by Anonymous Coward
      What is this "paper"?
      Why does it hold your secrets?
      No matter. Encrypt.
    • Re:opportunity (Score:4, Interesting)

      by chill (34294) on Friday December 02, 2011 @08:36PM (#38246582) Journal

      Not really. There are already tons of better shredders, and they don't cost a whole lot. I bought one that cuts pieces into little diamond-shaped bits about 1/3 of the size of the shreds shown in the DARPA challenge. It cost me about $125 at an office supply store.

      The one that is at my office, for non-classified documents, cuts into little squares about 2mm x 2mm. The one for the Confidential documents does a better job that that. Most of the stuff looks like powder instead of shreds.

      Anyway, this isn't about spy vs spy stuff. It is for basic corporate and citizen espionage. How simple is it to piece together stuff you grab from drug dealers and other criminals who bought a shredder at an office supply store?

      • by Fnord666 (889225)

        Anyway, this isn't about spy vs spy stuff.

        Funny you should say that, because actually it was. See the solution to the challenge and the puzzles for full details.

      • Anyway, this isn't about spy vs spy stuff. It is for basic corporate and citizen espionage. How simple is it to piece together stuff you grab from drug dealers and other criminals who bought a shredder at an office supply store?

        Whatever happened to flash paper

    • by cvtan (752695)
      Assume for environmental reasons that you don't want to burn the docs and you want to recycle the paper. One tactic might be to scrape off the top layer of the doc so the printing is removed. Another method might be to shred the paper so that a human cannot handle the pieces for re-assembly either by making the pieces really small or by tearing the edges so they are too hairy to fit together.
      • by roman_mir (125474)

        I wouldn't be concerned about any environment at all if the threat to me is from a gov't. I would only be concerned with my secrets. Environment is not even in the distant back of my mind when I want to hide my secrets from a gov't.

    • by wwphx (225607)
      A friend of mine worked crypto during the Vietnam War. He told me about a shredder they had that you put a document in one end and you got dust out of the other. If you weren't wearing a mask and you inhaled a lungful of it, it could kill you.

      I don't think it's practical tech for home use.
  • by AceJohnny (253840) <jlargentaye@gmai ... minus herbivore> on Friday December 02, 2011 @06:56PM (#38245694) Journal

    Vernor Vinge's 2006 novel Rainbow's End [wikipedia.org] explained how a library was being digitized by shredding all the books, thus destroying the analog knowledge.

    One step closer...

  • Meh (Score:5, Funny)

    by Anonymous Coward on Friday December 02, 2011 @06:56PM (#38245698)

    Wake me up when they have the Ash Challenge.

    • and that is why a wood stove is so nice, you have a warrent to go through my home, or you break in to steal confidential information, fine and if you want my documents they are in that bucket of ash i haven't had the time to dump in the woods behind my house. go to.

  • by TaoPhoenix (980487) <TaoPhoenix@yahoo.com> on Friday December 02, 2011 @06:57PM (#38245706) Journal

    Previous topics included that the abilities gained were worth far more than $50,000.

    So was this a fancy Job Application?

  • As I said before... (Score:5, Interesting)

    by damn_registrars (1103043) <damn.registrars@gmail.com> on Friday December 02, 2011 @07:09PM (#38245850) Homepage Journal
    I don't see this being very useful for overseas operations. They mentioned before this would be good for recovering documents shredded by "warlords' operations" but that doesn't seem to make a lot of sense. Many of the warlords we are most concerned about right now have such a dramatically different sense of morality than our own that they use rape as a weapon - or tool, really - of war.

    Why, then, would we expect them to use a shredder for their documents, when they can much more easily set fire to the documents? No amount of de-shredding is going to put back together documents that have been incinerated.

    I suspect we are much more likely to see this used by the FBI than the CIA or DOD.
    • by Firethorn (177587) on Friday December 02, 2011 @07:21PM (#38245938) Homepage Journal

      You might be suprised. A fire can be dangerous, a shredder is convenient. Also, we can reconstruct documents that have been burned, and if you have a big stack it can actually take longer to burn them beyond recovery. Why? It's about oxygen availability - the corners, top and bottom pages will burn first, but the center of a pile of documents will often remain intact, yielding valuable intelligence if recovered.

      Having looked up the shred, it seems to be standard commercial shred sizes - the DOD goes quite a bit smaller than that.

      • A fire can be dangerous, a shredder is convenient

        A warlord is more or less equally as dangerous as uncontrolled fire.

        if you have a big stack it can actually take longer to burn them beyond recovery. Why? It's about oxygen availability - the corners, top and bottom pages will burn first, but the center of a pile of documents will often remain intact

        That is assuming that someone is burning only paper. Indeed, a stack of paper can be a bitch to burn beyond recognition. But if you're in the business of raping women and torching villages, you just throw the documents into a building that you are going to burn to the ground and then you leave town. Eventually the temperature of the fire gets high enough that the paper incinerates well beyond any hope of recovery.

        And fire is one th

        • But if you're in the business of raping women and torching villages, you just throw the documents into a building that you are going to burn to the ground

          Just for clarification... are you suggesting that a warlord leave his sensitive documents with a henchman to leave in a building that they must then burn to the ground. then leave without verifying that it succeeded?

          Heh. That reminds me of the Onion article where the US offered to donate Al-Qaeda 600 million dollars so they could build a fancy HQ building.

        • by Firethorn (177587)

          A warlord is more or less equally as dangerous as uncontrolled fire.

          Just because he's unconcerned with the safety of others and their stuff, doesn't mean that he's unconcerned about the safety of himself and his stuff.

          That is assuming that someone is burning only paper. Indeed, a stack of paper can be a bitch to burn beyond recognition. But if you're in the business of raping women and torching villages, you just throw the documents into a building that you are going to burn to the ground and then you leave town. Eventually the temperature of the fire gets high enough that the paper incinerates well beyond any hope of recovery.

          You're positing a pretty one-dimensional warlord in this case, who always has a building at hand to torch whenever he needs to dispose of some documents. Most warlords aren't fighting all the time, and often the important papers are back at his palatial palace of an HQ, where he DOES have electricity most, if not all of the time due to being first on the repa

    • by artor3 (1344997)

      Just because they're barbaric in the moral sense doesn't mean they are in the technological sense. They are quite capable of using computers and cell phones and shredders.

      • They are quite capable of using computers and cell phones and shredders.

        They certainly are. However a shredder requires electricity, and warlords often thrive in areas with inconsistent (or worse) electricity. In comparison, any hack with matches and gasoline can torch a building, day or night.

    • by gatkinso (15975)

      DOCEX (document exploitation) is a very active activity within the armed forces.

    • by pryoplasm (809342)

      It seems to me that a large amount of people commenting in this have not tried to burn a large amount of paper, something easily 20-30 reams worth of documents worth....

      From personal experience, burning is an option, but as my oh so wise leadership mentioned during the burning " It would burn quicker if you shredded it first...."

  • ... will it un-blend?

  • by Anonymous Coward

    I'd be happy to help train DARPA's AI, but not when it's going to assist such an unconstitutional monster as the Patriot Act. That's like, you know, pumping the bellows on the forge building your chains.

  • simplified test (Score:5, Informative)

    by demonbug (309515) on Friday December 02, 2011 @07:31PM (#38246040) Journal

    The test was actually much simpler than any real-world application might be. Each puzzle was really only one or two (or a few) shredded pages, with various degrees of shredding and various bits of writing. It is a first step, but nowhere near what you would be dealing with in any real-world situation where hundreds or thousands of pages of shredded documents would be mixed together.

    I participated (a bit) with the UCSD team that basically made a crowd-sourced jigsaw puzzle to do it - at last check they were in the top 5, but I don't think they got the last puzzle (yet). This approach seems reasonable for the relatively simple puzzles of the challenge, but it really wouldn't scale very well - requires a lot of labor.

    It sounds like the winning team had a much better (and more scaleable) strategy, where an algorithm scores all of the pieces for fit in a particular place and then allows the user(s) to choose the best piece from a few high-scoring ones. While I still don't think this would work very well in a real-world scenario, obviously it would work better than depending on massive crowd sourcing.

    • Re:simplified test (Score:4, Interesting)

      by fluffy99 (870997) on Friday December 02, 2011 @08:41PM (#38246620)

      The test was actually much simpler than any real-world application might be. Each puzzle was really only one or two (or a few) shredded pages, with various degrees of shredding and various bits of writing.

      Yes and no. The finest shred was actually pretty close to the current DOD spec of 1mm x 5mm for classified documents. You'll find that most sensitive but not classified shredders shred into much larger pieces, somewhere in the middle of the range given in the contest. You are correct that a typical shred bag has a large quantity of shredded pages mixed together.

      Still DARPA got what they wanted - ideas on how to approach this problem. I doubt crowd sourcing is a viable option for them, but it was interesting to see the method.

      • by deroby (568773)

        True, but it's unlikely to find a heap of shreds related to 2-3 pages.
        It's more likely you'll find the equivalent of hundreds of pages thrown together in a heap.
        This makes scanning a much bigger job (*), as well as the actual piecing stuff together again.

        (*: I haven't checked the results yet, but did they consider that each piece has two sides ?)

  • by De Lemming (227104) on Friday December 02, 2011 @07:50PM (#38246224) Homepage

    Here's a nice explanation of the participant which reassembled four of the five documents, finishing in third place.

    You should probably start burning your mail: What I learned from the DARPA Shredder Challenge [marcnewlin.com].

    • Four out of five documents? I thought it would be a trash bag with two reams of shredded low-quality office depot brand paper. Let's see them digitize that! It's not like they can use a document feeder.
  • by intx13 (808988) on Friday December 02, 2011 @07:54PM (#38246252) Homepage
    NSA-approved shredders are good enough for destroying classified documents up to TS; the shredded remains do not need to be controlled. The shreddings are fine enough that no piece of output can contain a single glyph at any reasonable font size. The shreddings of even a single piece of paper are shuffled together by the action of the blades. These shredders aren't cheap, but I bet they'll stand up to state-level threats of reconstruction for the next 10 years or so.

    If that's not good enough, some locations use burn-boxes - never trust a machine to do thermodynamic's job!
    • Re: (Score:2, Informative)

      by Anonymous Coward

      The NSA-approved shredder I used made chad so fine that the frayed fibres
      at the edges made up a large percentage and maybe the majority of the surface
      of each chad. There is so much information lost in that area that it may not be
      possible to reconstruct such documents in the future even with state-level resources.

  • In 1989 when the MfS offices were stormed they tried to shred a whole lot of documents, according to wikipedia there are still 16000 bags of shredded documents to reassemble. I think it would be a really useful application of the outcome of this contest to help put some of those documents back together.
    • by AHuxley (892839)
      Thats always a fun one. Some in the West helped the East or where blackmailed.
      With everyday of sorting, a name might drop out.
      Just think what the East had on some EU political parties too :)

The most exciting phrase to hear in science, the one that heralds new discoveries, is not "Eureka!" (I found it!) but "That's funny ..." -- Isaac Asimov

Working...