DARPA Unshredding Contest

DARPA held an unshredding contest, and there’s a winner:

“Lots of experts were skeptical that a solution could be produced at all let alone within the short time frame,” said Dan Kaufman, director, DARPA Information Innovation Office. “The most effective approaches were not purely computational or crowd-sourced, but used a combination blended with some clever detective work. We are impressed by the ingenuity this type of competition elicits.”

Lots of information about the contest and the winners here. This is the winning entry. And this is the original input for the challenge.

Posted on December 8, 2011 at 6:12 AM21 Comments

Comments

bob December 8, 2011 7:00 AM

Oh, they used those big huge shreddings like a $20 civilian shredder; I was picturing shreds from a real, GSA approved shredder.

I’ve always wanted to tackle one of those, but it would probably take a 60,000 core botnet.

Plus real shreddings come in a big pile made from 1000 different pages (and if they’re smart, all the same color).

lazlo December 8, 2011 7:33 AM

Yet more evidence that Vernor Vinge is actually a time traveler cleverly disguising himself as a sci-fi author. (one of the ideas in Rainbows End was that there was a company that had a very efficient de-shredding algorithm, and it became more economical to digitize books by feeding them into a wood chipper and blowing the shreds down a tube full of sensors… much to the consternation of librarians everywhere.)

aikimark December 8, 2011 8:37 AM

Congratulations to the winning team,
All Your Shreds Are Belong To U.S.

Love the team name.

Clive Robinson December 8, 2011 8:54 AM

It looks like it was a fun competition but…

Shreading is known to be no good against even a technicaly unsophisticated enemy.

If you are old enough you may remember the “Iranian Students” who reconstructed thousands of CIA and US Diplomatic cables, files and other documents.

For those that are unfamiliar with shreaders they come in a variety of forms,

1, Strip.
2, Square cross cut.
3, Diamond cross cut.
4, Spiral cross cut.
5, Random feed Pin Punch.
6, Ball mill.
7, Liquidiser.

The first is pointless for anything other than making bedding for your pet rabbits. Because the width of the strip is generaly two or more times the character width, thus even the human eye can put the documents back together fairly quickly, especialy as the shreads of one page invariably end up next to each other in the shreded bag.

Likewise most commercial (square) cross cut shreaders, the advantage these have over the strip cutters is you can generaly get considerably more documents in a single waste sack. But again all that has happened is the same wide strips of the strip cutter get choped into length of an inch or less which still alows fairly easy orientation by human eye and thus reconstruction.

Some low grade square cross cut shreaders produce strips only 2mm wide and 5mm long but they jam easily and are just a pain to use. They also have a habit of putting visable tool marks on the “chads” such that not only can they be orientated with out refrence to what is printed on the page usually the tool marks can identify where across the page the chad came from…

Rarer and generaly better made are diamond and spiral cross cutters, the size of the chads can be very small and importantly because the way they work tends to leave uniform tool marks. It would not be impossible to put a document back together but at 1mm by 1mm there is one heck of a lot of them in a single A4 sheet, and they get easily miked up in the waste hopper and bag.

Randomised feed Pin Punch systems, I’ve only ever seen two of these and they don’t half suck up the electricity. Put simply they cut the paper into strips that then get feed randomly into a pin punch system with ten or more pin punches that reduces the strips into 1mm diameter or smaller disks that then get fed along different length channels before being re-mixed in the waste hopper and sack. Good luck with putting that back together.

However the prefered method of shreading for security apprears to be either the ball mill or liquidizer depending on the quantity to be dealt with.

Basicaly the ball mill is the same machine that is used to make “paper fiber” in a paper making factory, it breaks the paper down into a slury of celulose fibers that can then be pressed out to form sheets of low grade cardboard, toilet paper etc.

A liquidizer looks just like the juicer you have at home, your confidential information (KeyMat tapes and cards) because of their small size get poped in the top with a suitable liquid (light vegtable oil or other flamable liquid) the vortex effect ensures that the paper gets reduced to less than fiber and very very well mixed. The resulting “fuel” gets burnt or can be pressed into “barbecue brick” sized lumps

For those that have “optical media” to be got rid of a belt sander will if applied to the right side will grind of the foil and track lands and pits. If you are in a real hurry a microwave oven will do a fair job of making them irrecoverable in just a few seconds. However don’t do this in a poorly ventilated area the fumes coming off have what are politly called “Toxilogical Disadvantages” or in laymans terms “they are going to kill you today or in the near future with some horrible disease such as emphasima or worse”.

Clive Robinson December 8, 2011 9:39 AM

@ Brian Raaen,

“I think the remote control humming bird is amazing”

It’s definatly cute and invokes the “I want one for Xmas” response in me.

What I would like to know is what happened to the Hypersonic flight test drone DARPA and co were involved with. For some reason it disapeared on it’s second test flight over the Pacific a few month back).

And for those wondering why the Pacific apperas to be the new “Area 51” it might have something to do with kinetic energy, at over 1500meters/second (4 to 10 times a bullet) and weighing in at something equivelent to a small car it would make a quite interesting hole in whatever it hit… Especialy as the fule was rumoured to be hydrogen. I guess you could look at the result as being a cross between an anti-nuke missile and a deep penetration bunker buster bomb…

3nonymous December 8, 2011 10:03 AM

All I’ve got is a simple strip shredder.

But I’m sure I could start a business selling “Triple SHRED” (or, in hipster spelling, shr3d) services, telling companies that I shred their documents 3 times…

hmmm December 8, 2011 10:10 AM

The least you could do would be to make it unpleasant for a “de-shredder” to pull the shredded document pieces from your trash can by mixing in some coffee grounds, “clumps” from your cat’s litter box, spoiled food from the refrigerator, and so on…

karrde December 8, 2011 11:11 AM

@3nonymous:
There’s a company out there that offers secure shredding. (I assume on-site, secure shredding.)

But they probably don’t guarantee unreadability.

My personal document-destruction method involves a fireplace, so I guess it’s pretty secure. On the other hand, the contents of my file-cabinet aren’t very high-value to most attackers…

Dirk Praet December 8, 2011 11:51 AM

Makes you wonder whose documents they didn’t manage to piece back together and didn’t want to spend several millions on a contractor for. Whenever I want stuff properly destroyed, the incinerator does a fine job.

Chris December 8, 2011 12:01 PM

Actually, you (Bruce) wrote about this. May I quote: “If an adversary can recover your key by taking a bag of shredded documents from your trash and paying 100 unemployed worker in some backwater counter ten cents per hour for a year to piece the shredded pages together, that would be $26,000 well spent.”
Applied Cryptography, 2nd ed., p185.
You were quite wrong about the amount of work necessary, but then again the book was written 15 years ago.

LinkTheValiant December 8, 2011 1:02 PM

One of my tasks is document destruction for my department. We have a shredder that would be in category 2.5 under Mr. Robinson’s classification scheme. That is to say, it produces chads of approximately 2mm by 5mm, while producing uniform tool marks.

I’m not sure which cross-cut shredders Mr. Robinson has used, but ours, while certainly suffering from the security problems he states (~6,000 chads per sheet, way too few,) does at least perform reliably in producing pet bed linings without constant jams. It uses opposing strip cutters, as any standard shredder does, with a spiral cross-cut running the length of the cutter. This spiral does a good job of keeping the machine from jamming, as the cross-cut is never binding on the paper’s grain all at once.

I wouldn’t say that the cost-benefit ratio of “unshredding” this waste would be unfavourable to criminals necessarily, but since our shredder can handle staples, paper clips, and the odd optical disc, it would be hazardous, to say the least. . .

Brett December 8, 2011 1:40 PM

The problem, as I see it, is that if the solution utilises crowdsourcing it’ll never be used in any real scenario.

Mark December 8, 2011 4:05 PM

You can take your paper docs, roll them into little logs, and burn them on a small grill without accelerants. Then put the ashes in the garden. Sure, it’s kind of slow, but it works well and I think it’s good for your plants.

Vega P December 11, 2011 12:29 PM

I wonder if a massive termite farm is the answer to the question of secure shredding. Just wet the paper, drop it down the chute where termites reduce it to un-deshreddable biomass.

Jonadab December 13, 2011 8:00 AM

Of course, if you want to be really secure, you place your document in the middle of a stack of five hundred irrelevant junk documents (or lorem ipsum) printed on the same paper with the same printer, feed the whole stack through a diamond crosscut shredder, place the resulting confetti in an enclosed glass box with multiple high-powered fans to stir it all around, then incinerate it, stir the ashes, mix the resulting ash powder into a hogshead of gasoline, incinerate that, gather up the final ashes and sprinkle them from an airplane over several square miles of ocean, push the planet containing said ocean into the sun, then destroy the universe. Because you can never be too sure.

Either that or, yeah, if it’s as sensitive as all that, DON’T PRINT A HARD COPY YOU MORON.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.