Slashdot Mirror
DARPA: Reconstruct Shredded Docs, Win $50K USD
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."
http://xkcd.com/538/
Someone with a unique way of reconstructing shredded documents can probably earn more than that in one afternoon of dumpster diving.
There are 4 boxes to use in the defense of liberty: soap, ballot, jury, ammo. Use in that order. Starting now.
I don't know, I've been hitting the shredded documents with a wrench for the last 10 minutes, it doesn't seem to be working.
You've got to be kidding right?
... while being hit by lightning.
I once saw The Flash rebuild a batch of shredded files in seconds.
Any adversary that shreds rather than incinerates critical information they don't want recovered isn't much of an adversary.
Beauty is in the eye of the beerholder.
Am I the only person who thinks this will be used more oft for nefarious purposes rather than for good?
"That's the way to do it" - Punch
The stasi shredded lots and lots that they're now trying to put back together again. They've been at it quite a while, too.
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.
I get this all the time. You're probably using imperial; try switching to metric.
And of course, no information like what type or level of shredding that is to be reconstructed.
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.
for the perfect un-deconstructible shredding algorithm I designed for DARPA for 500K.
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?
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.
"I hope you know how very lucky you are to know me, because I am so incredibly incredible."
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?!)
So in my Small Town environment, I just rip my stuff into 16ths, then pour my leftover stale soda all over it.
And yeah, echoing the poster below, only $50,000, really?! For a secret that could be worth BILLIONS in intel?!
My first Journal Entry ever, in 8 years! http://slashdot.org/journal/365947/aphelion-scifi-fantasy-horror-poetry-webzine
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 probably a real-life problem in disguise like a transmitted scrambled image problem or connecting/stitching problem.
i think a 80-90% un-shreddifier would be worth more than a couple of BILLION to corporations.
so they want us to help them read all the documents we shred, specifically to prevent them from being read
makes perfect sense
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.
Seems like the slashdot coverage has made the site go under
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, byebye.
-Malakai
A Dragon Lives in my Garage
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.
"That's the way to do it" - Punch
The solution will use a 3D printer, probably in orbit or on Mars. Because, space!
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.
I Browse at +4 Flamebait
Open Source Sysadmin
"The ability to reconstruct shredded documents will potentially yield information that may save lives or offer critical information about an adversary's plans."
im really hard pressed to find any case in which unless I can correctly reassemble a shredded document, people will die, so lets just forget they ever said this.
I can however postulate numerous adversaries (wikileaks, bradley manning, the pirate bay, julian assange, anyone currently serving a sentence in guantanamo for possession of a casio watch) who qualify as potentially nefarious document shredders.
TL;DR: Help the government spy on its own citizens, and we'll send you enough money to pay down those intractable federally backed student loans for another year.
Good people go to bed earlier.
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.
Wouldn't you just place dots on a grid representing ink at the edges of any given slice and then match it within a few percentage points off against the dots along the edge of all other slices? Can I patent that and prevent the other 7 billion humans out there from using my idea for the next 20 years?
Never say never. Ah!! I did it again!
Remember Ayatollah Khomeini displaying documents recovered from US Embassy in Tehran? So we are finally catching up to him in vision?
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
Don't use paper. Seriously, it's the 21st century already. Let them try reconstruction after you shredded it.
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.
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
https://www.accountkiller.com/removal-requested
They do an awfully good job at this sort of thing.
You lack imagination
-Malakai
A Dragon Lives in my Garage
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 to reconstruct many of the documents, 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 them, which are near-impossible to reconstruct.
This challenge is not about technology. It's all about convincing the world that our government DOESN'T know how to efficiently recover a shredded document. But I can't figure out just WHY they'd want to convince anyone of that...Oh wait - I got it! It's beca#%^$*
Imagine you are in a bus with Sandra Bullock... or on an elevator with Keanu Reeves...
-dZ.
Carol vs. Ghost
shredderchallenge seems to be Slashdotted, so apologies if this is a dup.
During the Iran Hostage Crisis teams of carpet weavers were recruited to piece together shredded documents. They were then published in 1982 in 54 volumes under the title "Documents From the U.S. Espionage Den".
1. Digitize the right face of the shredded stripes. You need a human or a futuristic robot.
2. Run your AI super application on your super computer to make the ends meet each other. You need a pool of humans or a futuristic robot.
3. Et-voi-la, your shredded document is back to life. And you are doomed.
Sent as ripples into the electromagnetic field. No single photon has been harmed in the process.
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 mass. There was nothing TO put back together after this process.
This technology has already been researched in Germany for the reconstruction of Stasi (DDR intelligence service) files that got shredded/ripped apart/destroyed at the time of the fall of the wall. Dunno if it would exactly match the requirements of this challenge (the site is slashdotted) but this is certainly not a new idea and I'm pretty sure there's decent technology already out there.
Kinda impossible if the shredded docs have been moistened and blended... that's what we do where I work
For piecing together shredded East Germany Secret Police (Stasi) documents: http://www.time.com/time/business/article/0,8599,1983287,00.html
Maybe DARPA needs to take a trip to Germany . . .
Schroedinger's Brexit: The UK is both in and out of the EU at the same time!
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.
Yeah. Automating this process will likely just make this pointless.
For those who seek perfection there can be no rest on this side of the grave.
I think I found my new KickStarter project: Office incinerators.
Burn papers, shred ashes, flush down toilet. Effectively impossible to reconstruct.
Here's a cookie. Now go help us research war.
Any real-world, practical uses for DARPA's "inventions" are purely coincidental. Yes, that includes the internets.
Iranian Team FTW!
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.
http://www.thefreelibrary.com/Resurrecting+shredded+documents-a0109945266
http://de.wikipedia.org/wiki/Stasi-Schnipselmaschine
DARPA just doesn't know about the one the NSA had already.... its a "need to know"...
Or perhaps they just want to see what the state of the tech out there is...
Democracy Now! - uncensored, anti-establishment news
The German project is for hand shredded papers. Reconstructing machine cross-cut shredded papers is a vastly more difficult problem.
These appear to be TIFF images, which is a commonly exploited format. Has anyone checked if these images are actually running exploits?
I get this all the time. You're probably using imperial; try switching to metric.
That's SAE you ignorant Clod!
Thats adding mercury & other chemicals to your soil.
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
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 am not interested in articles about life extension advancements.
Somebody will probably spend more than that just so they can hange the trophy on their wall, or get free advertising for their company.
If I could guarantee victory by throwing $40,000 worth of Amazon Virtual Turk at it, that would be a good deal. The trouble with any contest like this is that there is only a return if you win. The solution isn't intrinsicly valuable in the way that say, outsmarting other HFT traders is. Then again, I wouldn't put it past those guys to pay out $45,000 to all the other participants in exchange for first place. You get a guaranteed free cup of coffee at starbucks, they get $5000. Everybody wins..
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. :-)
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).
Maybe they should contract out some Iranians to do it. They did a bang up job after the US embassy was seized.
"The Muslim Student Followers of the Imam's Line published documents seized in the embassy (including painstakingly reconstructed shredded documents) in a series of books called "Documents from the US Espionage Den" (Persian: ). These books included telegrams, correspondence, and reports from the United States Department of State and Central Intelligence Agency, some of which remain classified to this day."
http://en.wikipedia.org/wiki/Den_of_Espionage
I suspect I'm joining you in going overboard. The way in which I'll dispose of sensitive documents is:
1. cross-shred (I also include non-sensitive material, as parent does)
2. dump into large trash bag, mix up the pieces
3. separate into 4 smaller groupings
4. Dispose 2 groupings at work (over 2 weeks) the other 2 groupings with council garbage collection (again, over 2 weeks)
Dumpster diving? You will have a shitty time reconstructing my important papers!
I use a crosscut shredder, then manually mix the shredded paper and then dispose of the stuff in a bag containing used kitty litter.
Turn it into a captcha solution.
Got Code?
I've been hitting the shredded documents with a wrench for the last 10 minutes
If they were my shredded documents, you might want to disinfect that wrench. The dog feces I mixed in with that load didn't look too healthy.
This issue is a bit more complicated than you think.
burn, stir, flush..DONE!
I killed da wabbit -Elmer Fudd
Well, they are spending the taxpayer dollar. Technically they have an obligation to do it as cheaply as possible.
GSA demands that you prove you aren't selling your product, service or self to anyone else for less, but they're under no obligation to take the lowest bid.
Where do you get off citing some cheapass urban folklore like this as if you know anything? Were you birthed from a GSA cloning project?
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 to their benefit, or direct donation and investment, that we might have achieved more peace and prosperity than we have by way of warfare.
This fart of an idea that we need to reconstruct shredded documents (shredded classified documents resemble instant potatoes, not large strips of paper spaghetti), so we can basically steal more intelligence from our adversaries is just one more step in the wrong direction. How far have we actually come? What great change have we been able to induce? We threaten trade embargos if people don't do what we say... why not promote trade 'beneficence' to those we wish to influence?
I could steal your car at gunpoint, drive it for a while, then spend 50k on a lawyer to get me out of it.... or maybe I can offer you 50k and you gladly hand me the keys.
Lets have a drumroll for the pseud-intellectual patriot that will tell me we've fixed everything at gunpoint, that we've accomplished great things in the wake of killing people.... with casualty numbers that are in millions. Let me preempt your response with a quick "F U".
I'm sure they would only be using the technology to potentially save lives and 'provide information on an adversary's plans'.
I do much that, but I also dump the loose shreds into half full dumpster and scatter them around. That way someone can't just grab the bag. Also, I figure that once the truck picks it up and smushes it into the back with everyone else's trash, it's even more difficult to find the pieces of.
(I'd burn it, but I live in a highly urban area that frowns on fires, thermite, pumpkin launchers, potato guns and all sorts of other good stuff.)
Why is there an "insightful" mod and why isn't it "-1"? If I wanted insight, I wouldn't be reading
I've fallen off your lawn, and I can't get up.
Many will try to do this physically. Big mistake. Instead, put the shreds in an airstream from underneath and blow it upwards. Start gently and increase the stream methodologically. That will create a sieve type action in which the lighter stuff will go higher and towards the top. At the top have an opening in which the pieces will blow into . What is needed is to get these to individually go into a small 'pipe', but individually. Once in the 'pipe', it can be streamed past multiple high speed cameras. The best solution is to run this several times and make sure that you have all the pieces. Once that has occurred, then you can assemble the pieces via algorithms.
Basically, this is a nothing more than chromatograph that uses weight and size.
I prefer the "u" in honour as it seems to be missing these days.
The answer to the first sheet is as easy as grabbing your Little Orphan Annie Decoder Ring! It says, "Remember to drink your Ovaltine!"
In other words, the government wants your help designing privacy-invading technologies.
And this is why you always burn, not shred, documents you want destroyed.
Liberty in your lifetime
Hire some speed freaks, pay them for each reconstructed page with a hit of quality crystal meth, rinse and repeat.
$50k at wholesale rates could buy a crapload of meth. Or you could use the money to set up your own meth lab.
Unfortunately, this is for United States citizens only. Sounded like a nice project to give a try.
What would I have to do if I can solve all puzzles, but cannot claim the prize? Sell it to the Chinese?
int main(void) {while(1) fork(); return 0;}
Or try using a 'spanner' - they're British Standard.
Vernor Vinge described the process some time ago in his book Rainbows End (http://mostlyfiction.com/scifi/vinge.htm)
If someone with guns or bombs going to attack (a "terrorist" attacking a building or a millitary unit attacking someone) and you want to prevent that (arrest the terrorists or count attack the unit) de-shreeding their plans would aid you in savinging the initial target.
Like all tools a better de-shredder is target netrual, it can be used for good or ill.
to leave wikileaks alone. then you would know where to find the stuff
That's because you hit things with a hammer. haven't you ever had to repair a PC?
The new right fascists are bilingual. They speak English and Bullshit.
Shredding is a function which easy. Deshredding is hard. This is a form of encryption. Would solving it prove that P = NP?