Today Will Clarkson, Tim Weyrich, Adam Finkelstein, Nadia Heninger, Alex Halderman and I released a paper, Fingerprinting Blank Paper Using Commodity Scanners. The paper will appear in the Proceedings of the IEEE Symposium on Security and Privacy, in May 2009.
Here’s the paper’s abstract:
This paper presents a novel technique for authenticating physical documents based on random, naturally occurring imperfections in paper texture. We introduce a new method for measuring the three-dimensional surface of a page using only a commodity scanner and without modifying the document in any way. From this physical feature, we generate a concise fingerprint that uniquely identifies the document. Our technique is secure against counterfeiting and robust to harsh handling; it can be used even before any content is printed on a page. It has a wide range of applications, including detecting forged currency and tickets, authenticating passports, and halting counterfeit goods. Document identification could also be applied maliciously to de-anonymize printed surveys and to compromise the secrecy of paper ballots.
Viewed under a microscope, an ordinary piece of paper looks like this:
The microscope clearly shows individual wood fibers, laid down in a pattern that is unique to this piece of paper.
If you scan a piece of paper on an ordinary desktop scanner, it just looks white. But pick a small area of the paper, digitally enhance the contrast and expand the image, and you see something like this:
The light and dark areas you see are due to two factors: inherent color variation in the surface, and partial shadows cast by fibers in the paper surface. If you rotate the paper and scan again, the inherent color at each point will be the same, but the shadows will be different because the scanner’s light source will strike the paper from a different angle. These differences allow us to map out the tiny hills and valleys on the surface of the paper.
Here is a visualization of surface shape from one of our experiments:
This part of the paper had the word “sum” printed on it. You can clearly see the raised areas where toner was applied to the paper to make the letters. Around the letters you can see the background texture of the paper.
Computing the surface texture is only one part of the job. From the texture, you want to compute a concise, secure “fingerprint” which can survive ordinary wear and tear on the paper, such as crumpling, scribbling or printing, and moisture. You also want to understand how secure the technology will be in various applications. Our full paper addresses these issues too. The bottom-line result is a sort of unique fingerprint for each piece of paper, which can be determined using an ordinary desktop scanner.
For more information, see the project website or our research paper.
I’d like to hear where Ed’s crew stand on this one:
http://www.onthecommons.org/content.php?id=2408
BTW, the govt transparency thread was closed 🙁 feel free to move this comment to the correct location.
As your microscopic pic shows, there is a randomness in the pattern of the wood fiber of the paper. Wouldn’t the machine that manufactured the paper, continue to create the randomness of pattern of the wood fiber in all of the paper it creates, making its’ pages indistinguishable from one to another?
Joe
Paper isn’t woven, it’s matted. A drastically oversimplified example: cook a lot of spaghetti. Pour the spaghetti into baking pans, say half an inch thick, put a flat weight on top, and let it dry.
You wind up with a ‘web’ of matted fibers in a completely random arrangement. Every time you do it, it will be different.
A more accurate depictions is here http://www.madehow.com/Volume-2/Paper.html
How do you deal with issues like chemical contamination due to ordinary handeling?
At the sort of resolution you are looking at ordinary skin flakes and body oils will be stuck to/in the paper fibers.
And if one of the people reading the document at the time was smoking then I would expect a whole host of chemical nasties including ammonia to be in/on the paper.
Over a relativly short period of time I would expect a lot of these chemicals to have a marked effect on the fiber profile so effectivly changing the shadow patterns.
Thanks for blogging about your paper – may I ask whether you have considered applying the same process to vellum?
One research problem I have been looking at for some years is to do with reconstructing the original sequence of pages in a particular 15th century manuscript. Being able to work out a kind of “visual fingerprint” for each animal whose skin was used to make the vellum would be a major step forward – large pieces of vellum were normally folded and trimmed into gatherings, so anything that would yield a likely match between two vellum bifolios would be a major step forward.
That speckle pattern is what optical mice use to track movement which is why they would much better on a piece of normal (non-gloss) paper than they do on a plastic table top. You could probably hack an optical mouse to generate the same sort of security signatures, and maybe cheaper and faster than a scanner.
Really “robust to harsh handling” ? Paper tends to get hairy as it gets older, I have trouble believing the hairs won’t substantially change the light/dark shadows and once the paper is hairy it will give a different pattern every time it gets moved. No one has yet figured out a signature system for spam emails that is robust to minor changes in punctuation, whitespace and a handful of random characters so it seems like this is a very similar problem from a mathematical point of view. Also, dusty environments? Dampness causing paper distortion?
Off-topic: New DRM found in iPod Shuffle
http://www.eff.org/deeplinks/2009/03/apple-adds-still-more-drm-ipod-shuffle
Mangled trackbacks — there’s two of them, above, mistaken for normal comments by the blog software due to whatever malformations in the data.
you could also generate unique cryptographic hashing tags and metadata to provide resistance against tamper attacks in paper document acquisition systems.
like a a great system of hashing for documents lik hashing the ocr plaintext output/content, date scanned and the PAPER finger print together to make the document hash
Question:
Would this method accurately differentiate two different paper stocks as well as fingerprint a given piece of paper? Would characteristics of the same manufacturer and paper content be statistically correlated through this program?
If you rotate the paper and scan again, the inherent color at each point will be the same, but the shadows will be different because the scanner’s light source will strike the paper from a different site:http://freedom-to-tinker.com/blog/ “post new comment” angle. These differences allow us to map out the tiny hills and valleys on the surface of the paper.
If you rotate the paper and scan again, the inherent color at each point will be the same, but the shadows will be different because the scanner’s light source will strike the paper from a different site:http://freedom-to-tinker.com/blog/ “post new comment” angle. These differences allow us to map out the tiny hills and valleys on the surface of the paper.
Hi
Does this method rely on having the exact identical scanner for both registration and validation? If not, how do you correct for that?
Even if using the exact identical scanner for registration and valdation, but the latter is done months or years later and the scanner is degraded in light source or CCD performance?
Just my $0,02
This is even more frightening than the yellow dots….