4 ms·

DARPA: Shredder Challenge Solved. See images from the winning entry.

54 points by petedoyle 15y ago

DisasterPlan 15y ago
Burn all your shredding Write with invisible ink (lemon juice, ACME Brand , etc...) Small font, tight spacing. ;-)
masukomi 15y ago
Why are they all straight shreds? Bad guys don't know how to go to Staples.com and buy a Diamond shredder? Sure, it's useful to be able to decode those but if you're going to throw $50,000 on the table why not at least ask for something slightly more sophisticated than aligning what are essentially rectangles. I wouldn't be surprised if someone out there makes a cheap consumer grade shredder with some shape more obnoxious than diamonds too...
- GHFigs 15y ago
  Bad guys don't know how to go to Staples.com and buy a Diamond shredder? Staples.com doesn't actually carry diamond-cut shredders. At least, none that I can find. The smallest shred size I can find there is 3.175mm x 9.525 mm. By comparison, the document in the fifth puzzle is taken from a legal pad (8.7 mm line spacing), and the shreds are only a little bit longer. Would the shape really make that much of a difference at this scale?
  - adrianN 15y ago
    I'm no expert, but I'd say having shreds for which the orientation is not as obvious makes the problem much harder. Add to that the amount of work necessary to get a clean image of the thousands of particles a page produces... Amazon sells relatively cheap security level 4, and rather expensive security level 6 shredders.
Tichy 15y ago
I supose I can save the money for a new shredder now. Home incinerators for the rescue?
- minus1 15y ago
  This is not a solved problem by any means. I finished in the top ten, and most competitive teams used a combination of image processing for chad suggestion and brute force. It required hundreds of man hours to reassemble just a handful of documents under controlled conditions. Imagining a real-life scenario of dozens or hundreds of documents mixed together in a shredder bin makes my head hurt. So, I wouldn't worry too much about your shredded docs just yet.
DanBC 15y ago
I guess that the use of sensitive documents rules out Mechanical Turk or a game version for the real work, but I'd be interested to see what turkers could do.
- minus1 15y ago
  One team used a crowd sourced "game" method with some success. They had thousands of people register, and were able to solve the first few problems quickly, but they began to stall on the more complex puzzles. I was surprised to find that this method doesn't scale well when the puzzle reaches a certain size.
chr15 15y ago
I'm really interested in seeing the algorithms and implementation behind the solutions.
- otaviogood 15y ago
  The third place guy posted an explanation of his algorithms here: http://www.marcnewlin.com/2011/12/you-should-probably-start-burning-your_02.html http://www.marcnewlin.com/2011/12/you-should-probably-start-... I was on the winning team and we have been writing up our algorithms too. Hopefully we'll be able to post them soon.
dhughes 15y ago
I'd be impressed if they could reassemble a shreded CD or DVD.

54 points by petedoyle 15y ago

Burn all your shredding Write with invisible ink (lemon juice, ACME Brand , etc...) Small font, tight spacing. ;-)

Why are they all straight shreds? Bad guys don't know how to go to Staples.com and buy a Diamond shredder? Sure, it's useful to be able to decode those but if you're going to throw $50,000 on the table why not at least ask for something slightly more sophisticated than aligning what are essentially rectangles. I wouldn't be surprised if someone out there makes a cheap consumer grade shredder with some shape more obnoxious than diamonds too...

GHFigs 15y ago
Bad guys don't know how to go to Staples.com and buy a Diamond shredder? Staples.com doesn't actually carry diamond-cut shredders. At least, none that I can find. The smallest shred size I can find there is 3.175mm x 9.525 mm. By comparison, the document in the fifth puzzle is taken from a legal pad (8.7 mm line spacing), and the shreds are only a little bit longer. Would the shape really make that much of a difference at this scale?
- adrianN 15y ago
  I'm no expert, but I'd say having shreds for which the orientation is not as obvious makes the problem much harder. Add to that the amount of work necessary to get a clean image of the thousands of particles a page produces... Amazon sells relatively cheap security level 4, and rather expensive security level 6 shredders.

Tichy 15y ago

I supose I can save the money for a new shredder now. Home incinerators for the rescue?

minus1 15y ago
This is not a solved problem by any means. I finished in the top ten, and most competitive teams used a combination of image processing for chad suggestion and brute force. It required hundreds of man hours to reassemble just a handful of documents under controlled conditions. Imagining a real-life scenario of dozens or hundreds of documents mixed together in a shredder bin makes my head hurt. So, I wouldn't worry too much about your shredded docs just yet.

DanBC 15y ago

I guess that the use of sensitive documents rules out Mechanical Turk or a game version for the real work, but I'd be interested to see what turkers could do.

minus1 15y ago
One team used a crowd sourced "game" method with some success. They had thousands of people register, and were able to solve the first few problems quickly, but they began to stall on the more complex puzzles. I was surprised to find that this method doesn't scale well when the puzzle reaches a certain size.

chr15 15y ago

I'm really interested in seeing the algorithms and implementation behind the solutions.

otaviogood 15y ago
The third place guy posted an explanation of his algorithms here: http://www.marcnewlin.com/2011/12/you-should-probably-start-burning-your_02.html http://www.marcnewlin.com/2011/12/you-should-probably-start-... I was on the winning team and we have been writing up our algorithms too. Hopefully we'll be able to post them soon.

dhughes 15y ago

I'd be impressed if they could reassemble a shreded CD or DVD.