13th Jun 2008
(not actually about bees)
13th Jun 2008
A neat steganographic trick: find a form of artificial data partially driven by pseudo-random bits, rip out the PRNG, and replace it with a ciphertext beacon. If the PRNG state can be estimated by someone who receives the data, you have a covert channel. Example:
These are two of my PhD students. We created some novelty iChat backdrops, like this “rainclouds in the office” deal. The rain and lightning are driven by a PRNG, which we replaced with a contaminated patch that grabs ciphertext from another application. On the other side we can extract the PRNG bits by the position of the raindrops. With various animations we can transmit ciphertext on the order of 500bps.
What’s so great about this? Well, first of all, it’s almost perfect. The cat-and-mouse game of steganography usually involves tampering with natural data like images; inevitably, this tampering tweaks some obscure statistics that give away the embedding. You refine your tampering, Wendy refines her classifier. There is no obvious end to this game, because nobody has perfect statistical knowledge of images, video or audio clips.
In our case, we decided to tamper with a data source that is engineered to be indistinguishable from iid coin flips. If the original PRNG was strong, there’s really no way you can tell (that’s the “almost” part—Apple’s built-in PRNG is pretty weak, so you can’t just doctor an existing animation.)
Second of all, it’s supraliminal. A “subliminal” channel is a mainstream crypto term for steganography, coined by Gus Simmons (see a great story on this in the May 1998 IEEE Journal of Selected Areas in Communications.) This has nothing to do with so-called subliminal messages; it just means hiding data in a throwaway part of a message that nobody notices. In contrast, a “supraliminal” channel hides data in very blatant, obvious, visible parts of a message. Peter Wayner’s mimic functions, which transform messages into text dialogs, are supraliminal. So are these animations: if you try to wipe out the channel, you tamper with content.
Which is the point of a supraliminal channel. We introduced the term in a 1998 paper at the 2nd Information Hiding Workshop in Portland (jeez, so much happened that year,) and the purpose was to establish a brief uncensorable channel which can be used as a primitive in a key-exchange protocol. You see, steganography is for people who aren’t allowed to do key exchange. You have an environment where sending crypto is banned, sending key data is banned, sending random strings is banned. And if you try to embed your public key in an image, you have to do it without a secret key—meaning that the warden can erase the channel. A supraliminal channel allows you to send that initial public data without the erasure.
The one caveat is that anything you send over this public channel cannot have any structure or meaning that distinguishes it from channel noise. You can’t send plain text, you can’t send an RSA key (what a coincidence, those bits form a number that I can’t factor) but you can do Diffie-Hellman with a known p, if your values (mod p) are slightly fixed to look uniform over n-bit strings.
Thirdly, this was fun. I’ve done a lot of fun projects before, breaking DRM schemes, taking part in contests, running our own security contests, creating end-to-end prototypes, but this one was the coolest. It involved coding, reverse-engineering, data collection and analysis, protocol design, and actual graphic design. Half the challenge was coming up with fun ideas for novelty backdrops.
We presented this at Information Hiding 08 in Santa Barbara, and for fun I used a contaiminated background animation in the Keynote slide theme. You can put these things anywhere.
BTW, I got a lot of useful information on Quartz Composer programming from Kineme.net, and without their help we wouldn’t have been able to make our animations draggable into iChat. We owe those dudes a debt of gratitude.
You are currently browsing the archives for the Useful Arts category.