Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Encryption The Military Build

DARPA: Reconstruct Shredded Docs, Win $50K USD 209

Posted by timothy from the perfect-for-our-recycled-checkbooks dept.
ematic writes with a link to an interesting competition from DARPA: "The ability to reconstruct shredded documents will potentially yield information that may save lives or offer critical information about an adversary's plans. Currently, this process is much too slow and too labor-intensive, particularly if the documents are handwritten. We are looking to the Shredder Challenge to generate some leap-ahead thinking in this area. The Shredder Challenge is composed of five separate problems. The overall prize awarded depends on the number and difficulty of problems solved."
This discussion has been archived. No new comments can be posted.

DARPA: Reconstruct Shredded Docs, Win $50K USD More

DARPA: Reconstruct Shredded Docs, Win $50K USD

Comments Filter:

  • Puny prize (Score:4, Insightful)

    by afidel ( 530433 ) on Thursday October 27, 2011 @02:28PM (#37860066)
    Someone with a unique way of reconstructing shredded documents can probably earn more than that in one afternoon of dumpster diving.
    • Especially if they are DARPA's dumpsters.

      • Puny prize. Especially if they are DARPA's dumpsters.

        I'd expect that DARPA has incinerators. Documents --> office shredder --> building incinerator --> dumpster. If someone can reconstruct documents from a bag of ash then I agree, the prize should be much much larger. :-)

    • Re:Puny prize (Score:5, Informative)

      by lgw ( 121541 ) on Thursday October 27, 2011 @02:37PM (#37860238) Journal

      Well, the normal approach is to scan all the remains, calculate a checksum for the pattern along each edge, then match the checksums to reconstruct the docuement. Without crosscut shredding this is very fast and effective.

      As I understand it, the government now shreds anything important (paper, hard drive, etc) down to less than 1mm on a side, so it's not such an easy problem these days - veyr many disctint pieces, and not much distinctness along the edges.

      • Re: (Score:2)

        by bberens ( 965711 )
        Some enterprising youngster will ramp up a few hundred Amazon EC2 virtual servers and crunch through it in a few minutes.

      • Even when I first got into the Navy (which was like 25 years ago... damn I'm old), we were using cross-cut shredders to destroy classified paperwork. These things practically turned the paper to dust - the individual pieces were like maybe 3/8" long by, I don't know, 1/32" wide? There's no freaking way you could put these back together.

        And if that wasn't good enough, one ship I was on had a paper mulcher. You threw in the paper you wanted destroyed, and it ground it up with water into a sodden, pulpy gray m

        • Re: (Score:2)

          by Ihmhi ( 1206036 )

          And then there's situations where an organization or person really doesn't want you to read their paperwork and they have a furnace that can flash burn paper in a handful of seconds. What's Darpa gonna do, offer $50,000 for the guy who figures out how to reconstitute ash?

      • Re: (Score:3)

        by jd ( 1658 )

        With this problem, you'd do basically the same thing but you'd want slightly more data to handle the smaller size. (For handwriting, pressure and gradient would be the most obvious extensions to use. For original printed documents, you MAY be able to use any random fluctuations in toner or ink, since any fluctuations will be highly localized. For photocopies, the contrast of the copy might not be enough to show up extremely small variations - I'm really not sure what you could use there.)

        However, you needn'

      • Re: (Score:2)

        by v1 ( 525388 )

        As I understand it, the government now shreds anything important (paper, hard drive, etc) down to less than 1mm on a side, so it's not such an easy problem these days - veyr many disctint pieces, and not much distinctness along the edges.

        Depends on how much they value their privacy. Subs cross cut, then run it through another machine that somehow grinds that into what can best be described as "coarse paper dust", and then they flush the dust out into the water, while they're at depth. (i.e. not only a tou

  • ... while being hit by lightning.

    I once saw The Flash rebuild a batch of shredded files in seconds.

  • Shred? (Score:5, Insightful)

    by MarkGriz ( 520778 ) on Thursday October 27, 2011 @02:32PM (#37860134)

    Any adversary that shreds rather than incinerates critical information they don't want recovered isn't much of an adversary.

    • Re: (Score:2)

      by lgw ( 121541 )

      Incenerating is a notoriously poor plan - there were some great art projects made from confidential documents that were incenerated, and were carried up the chimney ony slightly burnt and found by artists.

      • Re: (Score:2)

        by Arlet ( 29997 )

        First shredding, and then incinerating would seem fairly fool-proof though.

      • Re: (Score:3)

        by Surt ( 22457 )

        Any adversary whose incineration chimney doesn't have a tight particle filter isn't much of an adversary.

      • a poor half assed incineration perhaps. If by incineration you mean dumping a pile of un-shredded papers into a normal run of the mill fireplace yes. If you mean a closed stove or chamber designed for incineration with a decent filter that does not allow anything of significant size out then reconstruction is pretty much impossible.

        • Re: (Score:2)

          by rthille ( 8526 )

          All you really need to reconstruct it is a piece of angel food cake.

        • Re: (Score:3)

          by lgw ( 121541 )

          The recurrent problem seems to be that you contract for the one and get the other in practice. That sort of problem is why the popular shredding services will shred your documents on their truck while you watch, so at least you know what you're getting.

    • You can sometimes recover information from incinerated documents as well. I'd reccomend both. Or maybe just not writing it down in the first place.

    • I think the challenge includes documents that were blown up during a battle. The adversary might not have enough time to burn or shred a document when the tanks are rolling in, but the fight itself could have the effect of shredding.

    • Well, considering that just about every major government has tried to redact a pdf by drawing black boxes over it, I wouldn't be surprised to learn that shredders are being misused too.

    • Re:Shred? (Score:4, Informative)

      by TheRaven64 ( 641858 ) on Thursday October 27, 2011 @03:18PM (#37860838) Journal
      I did some work for a company that stores legal documents a few years ago. When things are ready for disposal, they are shredded loaded into a locked container. This container is then driven away and not unlocked until it arrives at its destination. Once there, it's emptied into a swimming pool filled with bleach. It is then removed from there and recycled. By the time it comes out of the bleach, it is small fragments of white fluff.

  • Am I the only person who thinks this will be used more oft for nefarious purposes rather than for good?

    • Right, the POINT of shredding documents is ... so that they cannot be looked at by anyone. It depends on your adversary. Casual ruffians might steal an untouched stack of papers thrown into the dumpster, but they won't bother with shredded stuff. If we're talking about the Big Corp level where they might actually pay a full timer to rebuild shredded stuff, then ... the smart first company would destroy the document even further. Funny thing is, a lot of shredders are pretty dumb - 8 page capacities. (Really

      • If I'm shredding something especially sensitive- I usually put the shredded paper in with the same bag as the kitty litter.

        Doesn't make reassembling the documents any easier- but if any crook goes to the trouble of doing that... maybe they deserve access to my security codes.

        • If I'm shredding something especially sensitive- I usually put the shredded paper in with the same bag as the kitty litter.

          Doesn't make reassembling the documents any easier- but if any crook goes to the trouble of doing that... maybe they deserve access to my security codes.

          Not bad. I use my shred as litter for my chickens, then it goes into the garden for fertilizer.

        • Re: (Score:2)

          by heypete ( 60671 )

          I figure that diluting things a bit also helps, and often shred some non-sensitive documents. When I empty the shredded paper (consisting of shredded sensitive and non-sensitive documents) into the recycling bag, I mix up the paper so pieces from the same document aren't grouped together.

          Perhaps a bit overkill, but it's only a slight bit of extra work. It's also fun to feed stuff into the shredder.

    • One person's "nefarious" is another's "good".

  • Cheapasses (Score:5, Insightful)

    by RobinEggs ( 1453925 ) on Thursday October 27, 2011 @02:33PM (#37860174)
    You gotta love when someone offers a $50,000 prize for an improvement that would save them millions of dollars in labor, not to mention the value of files reconstructed that might have been ignored before it became so much easier to do.

    A million dollars for improving the movie recommendations on Netflix, and $50,000 for a massive intelligence breakthrough?

    Way to go, Pentagon. Way to prove that even with a defense budget of $649 billion dollars you can still be a total cheapass.

    • Yep. Whoever solves this puzzle might want to retain copyright on their work rather than sell it for only $50,000 and then go to work for whomever DoD is planning to use this against.

      • A matter of lazyness. Imagine you come up with a new super-awesome idea worth millions. You have two options.

        1. Sell it to the highest bidder. You'll get a million or so. You're not going to be one of the mega-wealthy on that, but you can retire early and live a life of comfortable luxury.
        2. Found a business. Now you can be one of the mega-wealthy, but only if you have business savvy, and legal knowledge, and a bit of luck. You'll also spend the next few decades in meetings, running your new company. You

    • Re: (Score:3)

      by Surt ( 22457 )

      Well, they are spending the taxpayer dollar. Technically they have an obligation to do it as cheaply as possible. Netflix can just raise its rates, or split its service and demand more money for each, etc.

      • Re:Cheapasses (Score:4)

        by pclminion ( 145572 ) on Thursday October 27, 2011 @02:59PM (#37860592)

        Well, they are spending the taxpayer dollar. Technically they have an obligation to do it as cheaply as possible.

        In other words, the government is obligated to obtain the shittiest services possible? Speak for yourself. Me, as a taxpayer? Fuck that. If you can't afford to do things the right way with the taxes you currently collect, you either need to cancel a lot of spending or raise taxes. "Buy crappy stuff at a discount" is not an option I find acceptable.

        • In other words, the government is obligated to obtain the shittiest services possible?

          You may not know just how right you are...

          Many government agencies, from the federal down to the municipal, are actually required to accept the lowest bid. They also have no clawback provisions and no punishments for completing a project over-budget.

          It doesn't take a genius to see what will go wrong, and yet they continue using this system....

        • Are you actually part of the 53%?

        • Re: (Score:2)

          by Surt ( 22457 )

          No, they have an obligation to do whatever they must, at the cheapest price they can. Would you rather have the government do X for $100 or $200? Now X vs Y ... that's a matter for the people/congress to decide. This is why government procurement programs are supposed to take bids. So that they can deliver the same service at the lowest price.

          • Would you rather have the government do X for $100 or $200?

            If they can cut $100 of spending on pointless program Y, then I don't mind if that $100 gets put on beneficial program X. Looking at line items in isolation is meaningless.

    • $50k is more appropriate for the effort required to build a better shredder that defeats whatever scheme they come up with.

      • Re: (Score:2)

        by Arlet ( 29997 )

        Maybe DARPA's purpose is to build a better shredder, and this is just a cheap way to get it tested.

    • Dumbasses (Score:2, Insightful)

      by malakai ( 136531 )

      I know you are a 7 digit, so I shouldn't expect much, but read the fucking article. You have to submit a solution to the 'fake' challenge. This nets them no value. You don't turn in your code, or handover the process you used to solve it. At most you specify "I did this manually, automatically, or a mix". So you can win $50k for solving something, and then walk away. You can tell them to fuck off, you won't sell them your super-secret procedure no matter how much they offer you. But thanks for the 50k, kk,

  • Almost sounds like this would require a lot of venture capital to pull off and should warrant far more than a 50k prize.

    For large jobs, I can using air blowing conveyor belts to align and feed the scraps into a series of modified industrial sheet fed image scanners and allow a computer to itemize each of the images and convert them to OCR formatted files. Once completed, write a puzzle algorithm to piece them together electronically.

    • Re: (Score:3)

      by malakai ( 136531 )

      This has nothing to do with scanning the fragments. They give you a tiff, with an alpha channel, and each scrapped already pressed out and scanned into the image.

      The thought being, in the field, you can get the grunts to take back the bag of shreds, lay them out in blocks, scan them, and submit the blocks to some back-end program that will do some jigsaw algo to put together pieces within the block. You'll just have to make sure each shred is surrounded by a space.

      Honestly, I'm surprised some archaeological

    • Correction: *Two* sheet fed image scanners. One on top, one underneath. Unless you have some way to flip every piece to the correct orientation.
  • Scan the crap out of the paper, write a fingerprint matching algorithm to line up the fibers. I've often thought if I wasn't busy with a real job, this would be fun to implement. Probably a good graduate paper too.

  • I love all the cool technical challenges DARPA comes out with, but is recovering shredded doccuments really something we should be helping the government with?

    • Re: (Score:2)

      by Dunbal ( 464142 ) *
      Of course. It is your civic duty to do your part for The Cause, citizen. And please let us know if you see your neighbor doing anything suspicious.

    • Re: (Score:2)

      by malakai ( 136531 )

      It is if you want to know things like, say, someone plans to blow up another nations ambassador in your capital.

      While it would be nice if all terrorist were dumb enough to leave their info on thumb drives like Osama, we have to presume many still write things down, and then tell some lackey to 'get rid of all that' with a big old shredder...

    • Ask not what your country can do for you, ask how you can de-shred documents for your country.
  • Makes you wonder why people think shredding their documents is a good way to protect the information on them. A little time and patience can reconstruct shredded files. Fire seems like a much better way to dispose of potentially damaging hard copies of stuff. Although I'm not sure they can make burning barrels office safe.
    • Not a burn barrel but they could put in an incinerator. They then could get some green credentials as they would be heating their building with renewable resources.
    • Shredding IS a good way to protect the information. After shredding my bank statements with the cheap-ass shredder I bought at Office Depot, a bad guy would have to spend more time/money reconstructing the statement than he'd be able to extract from my bank account. And really good shredders essentially pulverize the paper - I don't think there's too much fear of being able to un-shred US gov't cross-cut shredder processed documents, for example.
  • This actually looks like a ton of fun. After looking at the basic documents they tried to put other indirection in the images like color levels that really need to be sorted before the actual shredding issue is resolved. There is a mix of up/down and useless data on the page, but the ligatures seem consistent on the images - brute force on the first page is probably the most cost effective solution - the others seem to be order of magnitude problems. The reality of this being "shredded" solution is proba

  • That's a little... cheap (Score:4, Insightful)

    by Leebert ( 1694 ) * on Thursday October 27, 2011 @02:43PM (#37860340)

    I think you'd be better off, if you were successful, to simply commercialize it. $50,000? That's like the first year's support contract on the software you'll sell them for $300,000 per seat. And since it's "enterprise" software, it doesn't even have to actually work particularly well. That's why you sell the support contracts.

    • Re: (Score:3)

      by malakai ( 136531 )

      The 50k is prize money to reward you for trying and doing. It doesn't give them the rights to your technology. You can set whatever price you want on it. But they may now know that 20 other people came really close, and your 'super amazing proprietary' algorithm isn't all that super amazing. This gives them a better negotiating position. You may win the 50k and some other guy may end up with the contract for 10million over 3 years.

  • Outsource it to 30 years ago (Score:3)

    by xenocide2 ( 231786 ) on Thursday October 27, 2011 @02:46PM (#37860392) Homepage

    Off the top of my head, this seems very close to the techniques used for shotgun sequencing of genomic data. Lots of little strands you want to line up. Just in multiple dimensions.

    • Yes but with shotgun sequencing you would need several rounds of fragmentation. So unless you have thousands of copies of the same page shredded with a high enough variance to detect overlap, we're talking about a very different problem.
  • Comment removed based on user account deletion

    • Re: (Score:2)

      by malakai ( 136531 )

      im really hard pressed to find any case in which unless I can correctly reassemble a shredded document, people will die

      You lack imagination

    • Re: (Score:2)

      by dzfoo ( 772245 )

      Imagine you are in a bus with Sandra Bullock... or on an elevator with Keanu Reeves...

              -dZ.

  • Remember Ayatollah Khomeini displaying documents recovered from US Embassy in Tehran? So we are finally catching up to him in vision?

  • Don't use paper. Seriously, it's the 21st century already. Let them try reconstruction after you shredded [about.com] it.

  • Scan all the shreds.
    Encode them based on the first 0.1 mm of ink on the long edge
    Compare all similar edge strings
    Recombine the ID of matching strings
    Done

    Error correction:
    If multiple edge strings match, do an OCR to see which solution fits best

    • Re: (Score:2)

      by malakai ( 136531 )

      50k is an afternoon away from you.

      They even scanned all the shreds for you, so you don't even have to get up.

    • You put the "brute" in brute force.

      Check out the factorial function and get back to us when you realize what it means http://en.wikipedia.org/wiki/Factorial [wikipedia.org]

    • Yeah well there's a difference between theory and practice.

      Actually many of the great successes of AI (and even then some would debate how great they've been) are simple-sounding in principle but tough to get right. Things like route planning (just start a directed random walk from the start and finish and explore the graph until they connect to each other), web search (just weight results by popularity/links), document search (just show anything with a partial match), OCR (just threshold the image and m

  • They do an awfully good job at this sort of thing.

    • Re: (Score:2)

      by bberens ( 965711 )
      It would be funny to outsource the manual work of putting the puzzle pieces together out to China for $10k, collect the difference.
  • After the Iranian Revolution in 1979, they raided the U.S. embassy and CIA office. U.S. personnel shredded all the documents they could (using strip shredders), but the Iranians used rug weavers [slashdot.org] to reconstruct many of the documents [gwu.edu], and sold them as a book. This is the reason strip shredders are rarely used nowadays.

    Aside from the obvious espionage uses, this would probably also be very useful for archeology. Some of the most common archeological finds are shattered pottery with pictures or writing on

  • Documents From the U.S. Espionage Den (Score:4, Interesting)

    by alanw ( 1822 ) <alan@wylie.me.uk> on Thursday October 27, 2011 @03:04PM (#37860660) Homepage

    shredderchallenge seems to be Slashdotted, so apologies if this is a dup.

    During the Iran Hostage Crisis [wikipedia.org] teams of carpet weavers were recruited to piece together [gwu.edu] shredded documents. They were then published in 1982 in 54 volumes under the title "Documents From the U.S. Espionage Den" [archive.org].

  • Some folks in Germany have done this already . . . (Score:4, Informative)

    by PolygamousRanchKid ( 1290638 ) on Thursday October 27, 2011 @03:11PM (#37860744)

    For piecing together shredded East Germany Secret Police (Stasi) documents: http://www.time.com/time/business/article/0,8599,1983287,00.html [time.com]

    Maybe DARPA needs to take a trip to Germany . . .

  • They should call up the people at CSI. They already have the tech, you put a fuzzy picture on the computer screen, say "Enhance" to it, and it shows you the original document. They just need to use whatever software those TV folks are using.

    • I think unshred is the next menu selection after uncrop.

    • They should call up the people at CSI. They already have the tech, you put a fuzzy picture on the computer screen, say "Enhance" to it, and it shows you the original document. They just need to use whatever software those TV folks are using.

      If not they can surely just create a GUI interface using Visual Basic that can track the necessary shreds.

  • This is a common problem with ancient religious texts as often they are fragmented, scattered, and in some cases the bits exists in different parts of the world. A type of recognition tech was used to help piece together parts of the dead sea scrolls:

    http://www.livescience.com/16620-digitized-cairo-genizah-texts.html [livescience.com]

    I recall copying some of the original texts myself, and frankly, I'm surprised they lasted as long as they did in the earthenware jars we made for them.

  • I think whatever they are proposing will work with a single cut shredder. However, we have a cross cut shredder that leaves behind only bits of confetti. Try pasting THAT together, I dare you, Especially after I toss and randomize the remains. (and maybe let someone use it to line their cat's litter box first).

  • Turn it into a captcha solution.

  • burn, stir, flush..DONE!

  • As a nation (and this is not just a US-only thing, though our budgets on these things are ridiculously destructive to our economy), we have spent so much trying to fight, spy upon, manipulate, etc, our adversaries; so much so, with so little actual 'impact' to show for it, that one has to wonder if there is a different approach that could be made.

    Many have considered that the billions upon trillions spent in the middle east on war, if instead being allocated to some form of beneficence, like trade deficit t

Slashdot Top Deals

The Tao doesn't take sides; it gives birth to both wins and losses. The Guru doesn't take sides; she welcomes both hackers and lusers.

Close