Fingerprinting documents with steganography
Blog
Jun 25, 2017 ·
post
Fingerprinting documents with steganography
Steganography is the practice of hiding messages anywhere they’re not expected.<br>In a well-executed piece of steganography, anyone who is not the intended<br>recipient can look at the message and not realize its there at all. In a recent<br>headline-making<br>story,<br>The Intercept inadvertently outed their source by publishing a document with an<br>embedded steganographic message that allowed the NSA to identify the person who<br>printed it.
These days, information is often hidden in digital media like images and audio<br>files, where flipping a few bits doesn’t change the file to the human eye (or<br>ear). Before computers came along, though, there were plenty of messages<br>creatively hidden in art, furniture, etc. There’s speculation that women in the<br>U.S. used to hide messages in their quilt work as a way to help escaped slaves<br>find friendly homes. Neal Stephenson riffs on this theme in his Quicksilver<br>Trilogy by having Eliza embed a binary code in her cross-stitching to smuggle<br>information out of the court of Louis XIV.
Hiding messages in text has always been especially challenging. There’s not much<br>room to make changes without fundamentally altering the meaning of the original<br>document, which in turn makes it obvious that something is amiss. If someone<br>other than the intended recipient of the information realizes that there’s a<br>message present at all, the steganography has, in some sense, failed.
What problem are we trying to solve?
In this post, I’ll talk about fingerprinting documents using text-based<br>steganography. The problem we’re trying to solve is as follows. We have a<br>sensitive document that must be distributed to some number of readers. Let’s<br>say, for example, that Grandpa has decided to share his famous cookie recipe<br>with each of his grandchildren. But it’s super important to him that the recipe<br>stays in the family! So they’re not allowed to share it with anyone else. If<br>Grandpa finds pieces of his cookie recipe online later, he wants to know which<br>grandchild broke the family trust.
To address this problem, he assigns each of his grandchildren an ID, which is<br>just a string of zeros and ones. Before he gives out the recipe, he identifies a<br>number of ’branchpoints’ in the text. These are places where he can make a<br>change without altering the grandchild’s experience of the recipe, or alerting<br>them that something is amiss. One such branch point might be spelling out the<br>numbers in the recipe - “ten ”instead of “10”. Another might be using imperial<br>units instead of metric. This type of method is called a canary<br>trap.
For each grandchild, he goes through the branchpoints one at a time. If the<br>grandchild’s ID has a zero at some position, he does not make a change at the<br>corresponding branch point. If it is a one, he makes the change.
Now, by looking at which changes had been made in the leaked cookie recipe, he<br>should be able to identify which grandchild was the source of the leak.
How does he find all the branchpoints he can use to effectively fingerprint<br>the recipe?
Before we can answer that question, we’ll have to take a slight detour into the<br>world of character encoding.
Digital character encoding
Computers think in binary, so when they save any symbol you might consider to be<br>text, what they’re actually saving is some string of zeros and ones. The map<br>that converts between binary and symbols is called a character encoding.
For a long time, the dominant character encoding<br>was ASCII, which can only encode 256 characters.<br>These include upper and lower case English letters, numbers, and some<br>punctuation.
A couple of decades ago, some folks got together and decided this wasn’t good<br>enough, not least because people who don’t speak English should be able to use<br>computers. They developed a specification called unicode<br>that now includes over 120,000 different characters and has the capacity to<br>expand to over one million.
Fortunately for us, there’s more room for hiding information these days than<br>there used to be. We’ll see how we can take advantage of all those extra<br>characters to find branchpoints in any document.
Identifying branchpoints
Some Unicode characters are more obviously useful than others. Take, for<br>instance, the zero width space. It has some<br>semantic significance - it tells whatever is rendering the text that it’s okay<br>to put a line break somewhere, even if there’s no other whitespace character.<br>For example, it will sometimes be used after a slash - it’s okay to start a new<br>line after a slash, but if you...