San Francisco Team Wins DARPA's De-Shredding Contest

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!"

Comments

Jackasses

[masternerdguy]

Thanks for helping the government spy on me.

Re:Jackasses

[datapharmer]

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.

Re:Jackasses

[Dunbal]

Yeah they don't care about you because you have nothing. Wait until you have something (if ever). Then you'll understand.

Re:Jackasses

[mrmeval]

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

[artor3]

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:Jackasses

[Ethanol-fueled]

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 their interest.

This is what happens when elite law enforcement agencies operate like profit-seeking enterprises, instead of serving and protecting the people. It's bust, bust, bust as long as they make their numbers and get a bigger budget.

Re:Jackasses

[Beeftopia]

Even paranoids have enemies.

Re:Jackasses

[Jafafa Hots]

I was arrested for making a donut joke in front of an undercover cop once.

Seriously.

Well, that's not what they SAID though. They said it was "disorderly conduct."

Re:Jackasses

[Hyperhaplo]

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.

Re:Jackasses

[ultranova]

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 your garbage and piece together your shredded electric bill.

Of course not. It's spy drones for overall surveillance, sewage analysis to find any "undesirable" habits, and the electric bill goes to the government straight from the electric company.

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

Sadly, in the light of Carnivore and Palantir, I'd say it's not paranoia but well justified caution.

opportunity

[roman_mir]

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

[Beardo the Bearded]

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.

Re:opportunity

[chill]

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?

Re:opportunity

[Fnord666]

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.

Ob Rainbow's End reference

[AceJohnny]

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

One step closer...

Meh

[Anonymous Coward]

Wake me up when they have the Ash Challenge.

$50,000

[TaoPhoenix]

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

So was this a fancy Job Application?

WTF?

[Scareduck]

It's not paranoid when they've established a consistent pattern of spying on citizens without cause in the wake of 9/11.

Re:WTF?

[PhunkySchtuff]

It's not paranoid when they've established a consistent pattern of spying on citizens without cause in the wake of 9/11.

Yes, because everyone knows they weren't spying on you before 9/11.
Sure, their legally granted powers have increased without bounds since then, but they've been spying on you right from the start.

Re:WTF?

[rahvin112]

Actually they weren't allowed to under previous law. So they simply paid the British and Australians to do it for them and did likewise for them.

Now that law doesn't exist so they don't need to bother with the loophole of paying a friendly country to do the spying job for them. You don't think the massive data center being built at Fort Williams in Utah is for spying on other countries do you?

Re:WTF?

[Anonymous Coward]

Actually, this is incorrect. Legally, the big five were not allowed to spy on each other: Australia, New Zealand, Canada, The United Kingdom and of course The United States, all collaborated on SIGINT, but were not allowed to intercept each other's communications. There were exceptions, however, such as Aid to Police, but this required warrants etc.

If a signal was being intercepted, and it was determined that one of it's end points was one of the five, it was no longer fair game to be intercepted.

If you read the above article (under controversy) it plainly accuses the US of misusing the material for its own ends.

As a former CF SIGINT Operator I can assure you that we at least did not bend or break the agreement.

As I said before...

[damn_registrars]

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.

Re:As I said before...

[Firethorn]

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.

Re:As I said before...

[damn_registrars]

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 thing that warlords are almost universally good at. One may find themselves in a place where electricity for running a shredder is hard - or even impossible - to come by, but they can always find something they are interested in burning to the ground, even when they are fleeing someone else.

simplified test

[demonbug]

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

[fluffy99]

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.

Explanation of strategy for the Shredder Challenge

[De Lemming]

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.

Shredders are good enough for classified docs

[intx13]

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:Shredders are good enough for classified docs

[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.

Stasi

[crash123]

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.

Re:Undercover?

[Jafafa Hots]

He did blow his cover, but not on the spot.
His whole crew did, I guess.

I was 18, made the remark in front of him on a street corner.
A few days later a cop car pulls up, they arrest me after I tell them I have no ID, and on the car ride downtown they say "soo.. we hear you think Buffalo cops are all too fat to run, huh? Well, the cop you might like to have a chance to talk to you about that. How would you like that?"

I just said "ok."

Charges were automatically dropped like 6 months later (ACD - Adjournment with Contemplation of Dismissal)
Cost me $350 for a lawyer because when I showed up without one the judge rescheduled and said to me angrily "don't come back here without a lawyer."

My view of the police and justice system dimmed somewhat as a result of this. The education was well worth the $350 though.