Slashdot Mirror
Researchers Calculate Capacity of a Steganographic Channel
KentuckyFC writes "Steganography is the art of hiding a message in such a way that only the sender and receiver realize it is there. (By contrast, cryptography disguises the content of a message but makes no attempt to hide it.) The central problem for steganographers is how much data can be hidden without being detected. But the complexity of this problem has meant it has been largely ignored. Now two computer scientists (one working for Google) have made a major theoretical breakthrough by tackling the problem in the same way that the electrical engineer Claude Shannon calculated the capacity of an ordinary communications channel in the 1940s. In Shannon's theory, a transmission is considered successful if the decoder properly determines which message the encoder has sent. In the stego-channel, a transmission is successful if the decoder properly determines the sent message without anybody else detecting its presence (abstract). Studying a stego-channel in this way leads to some counter-intuitive results: for example, in certain circumstances, doubling the number of algorithms looking for hidden data can increase the capacity of the steganographic channel"
How is that counter-intuitive? Many of us regularly backup our stuff here in slashdot, and no one has complained so far (which, being the slashdot crowd what it is, is definite proof that no one has noticed).
In fact, a port of gmail drive to slashdot is already in beta.
Around the turn of the millennium steganography became a big topic, the idea being that using PGP would only draw attention from the authorities. In my Amazon review of Schneier's Applied Cryptography I even complained that Bruce didn't talk about how to hide even the use of crypto.
But now that SSL is everywhere and the use of encrypted VPNs is a typical part of telecommuting, I don't think cryptography suggests the same anti-authoritarian counter-culture rumblings it used to. Do we need to hide crypto anymore?
hiding a message in such a way that only the sender and receiver realize it is there
I ignore lots of ads served up by them. They might as well not be there, I can't name one.
This issue is a bit more complicated than you think.
"Steganography is the art of hiding a message in such a way that only the sender and receiver realize it is there. (By contrast, cryptography disguises the content of a message but makes no attempt to hide it.) "
There's a secret message in this post. Can anyone find it?
Shai Schticks:"You don't make peace with friends, you make peace with enemies"
In the stego-channel, a transmission is successful if the decoder properly determines the sent message without anybody else detecting its presence (abstract).
When my girlfriend is talking on the phone, I am almost never aware that a message is being sent. She is so effective, in fact, that often when I am the intended recipient I am not aware that a message is being sent!
Umm. Duh.
Crypto and compressed data both tend to look like white noise. That makes them ideal stego candidates. When the data itself has a uniform distribution, it's really hard to to spot. It gets even harder if you apply a one time pad of random low-order bits to the stego medium and then modulate your signal in those bits. Thus, the actual channel capacity is nearly identical to the bitrate of the low order pre-wash bits. QED. No fancy assumptions needed.
p.s. Nabalzbhf Pbjneq sbe Cerfvqrag!
Studying a stego-channel in this way leads to some counter-intuitive results: for example, in certain circumstances, doubling the number of algorithms looking for hidden data can increase the capacity of the steganographic channel"
That's not what the paper claims. It claims that when there are multiple detectors, adding noise to the channel between the two detectors can increase the available bandwidth. This isn't really all that counter-intuitive when you think about it.
I've always had a warm spot for stenography, and it's actually much handier for certain types of communications than others. For example, in the two nights preceeding the last Democratic National Convention that was held in Chicago (1996), a subversive media organization, armed with clunky digital cameras and a T-1 on the south side donated by the Teamsters photographed and filmed more than a hundred instances of police brutality, uploading them to the web with about a 30 minute delay.
You had to actually drive downtown to where the T-1 terminated to upload things in those days, see.
But how did we communicate our plans and schemes to actually be present at "hotspots" when the shit really went down? Stenography. It went like this:
I have a number, that number is 356-32395510. I tell you that number. Then I take an image file and UUencode it. (for those who don't remember what that does, it's great for turning a binary file into a flat text file without losing any data). Then I take the message that I want to give you and drop it manually into the UUencoded file, like this:
Every third character on every second line starting from line 910, (the third, fifth and sixth digits of the are decoys) counting whitespace. The numbers always changed and had to be memorized when received as they were never written down. Everything to the left of the dash tells you what digits to the right of the dash are decoys. Use the number to find the characters and you have the message. Pull them out and you can UUdecode your picture again and look at it. Leave them in and the file looks merely corrupt. Email the stenographed file to the recipient who's memorized your number and there you have it.
The upside to this method is plausible deniability. If the fuzz finds a corrupt file called "FATLADYSEXHAHA.uue" on your computer, they have nothing. However, if they find a PGP file that you refuse to open for them, there can be issues.
Of course it's possible to break that kind of thing, but the point of stenography is that the man does not know it's a message of any kind, let alone a radical one all about how awesome cuba is.
If there's going to be a practical use for this (and the conclusions don't say they've calculated "the answer", just that they've developed a framework, gaaah!) then my gut tells me that the answer is "not very much" - somehwere around the rounding-errors of the encoding mechanism.
So, does anyone know how much data can be stuffed, undetectably, into a 700MB AVI file?
politicians are like babies' nappies: they should both be changed regularly and for the same reasons
Anywhere between 0 and a bit less than 700MB of data, depending on desired quality of video. A one frame video stream with an unrecognized FOURCC tag as an alternate stream is valid AVI - the alternate stream is ignored by players, and can contain encrypted data. It is 'invisible' to non-uber users, and could concievably be an "experimental audio codec" for plausable deniability.
So, does anyone know how much data can be stuffed, undetectably, into a 700MB AVI file?
700 MB, if you do it in the dark.
I always thought Steganography was the act of writing on large, plate-backed dinosaurs. Ya learn something new every day here!
http://photobombers.com/ Funny pix
That's not steganography. That's encryption, and a crappy one at that. If you take your PGP file (and remove any unnecessary header stuff), it will also look like a corrupt file, just like your UUencoded image. Steganography is hiding some data inside something else, like hiding a message in an image. For example, the police see an image of kittens, but you hid your child porn in the LSBs of the image, they can't see it.
Kaylee: Although I'm getting some weird chatter on the the official two-six-two. Sounds like they're talking about... ducks?
No idea, but it is probably a lot less than you can stuff undetectably on a 700MB WAV file ;)
You can hide as much data as there is noise on your file (granted it is compressed and cryptographed), so when you record that WAV file, be sure to do that in a noisy anvironment. By the way, I didn't RTFA, to see what those people really discovered (obviously, not what the sumary say they did), I'm here to see if it is worth it.
Rethinking email
I think the email you are about to receive inviting you for a walk in the woods, may have a hidden message in it.
My mom used to hide notes from the rest of the family, in plain sight, using short hand.
She was a secretary, back in the day. When you saw some scribbling on a note, you knew it was the chrismas shopping list or something, but who the hell knows what it said - even if you had a copy of Gregg's you'd be hard pressed to figure it out, unless you really wanted to spoil the surprise.
This issue is a bit more complicated than you think.
... of Pamela Anderson. There appears to be quite a bit of excess capacity available.
Have gnu, will travel.
Calculating this with any accuracy would require knowledge of both the width of a Stegasaur (which can be approximated from their fossils), but also how fast they ran. Given other arguments about the unknowns of dinosaurs, the figures we can guesstimate for their speed are just to varied to calculate this capacity to any meaningful value.
The cop says, "If you're doing nothing wrong, you have nothing to hide."
Answer: "Why are you wearing clothes? Got something to hide?"
Pavlov wouldn't be so famous if he'd used a can opener instead of a bell.
Sorry, but I mod subsequent anonymous posts to -1 or 0 to encode my secret messages.
The The secure capacity C (W, g, A) of a stego-channel give W [noise], g [steganalyzer], and A [attack] is given by C (W, g, A) = sup I(X;Z) for X an element of S0.
I is the spectral inf-mutual information rate for the pair of general sequences.
Z is the stego channel after encoding, noise, and attack (before decoding).
S0 is the secure input set, the set of encoded data that remains impossible to steganalyze after the addition of noise (but not necessarily attack).
I think mathematicians like to make their papers overly complex.
Well, I've read the published paper, and I still don't have a clue what the answer is.
That's steganography at work! The answer is hidden.
In Sorcery and Cecelia (or maybe it started in the sequel), the heroines knit fashionable items for each other, and code the message in the pattern of knits and purls.
Sometimes people think there is a steganographic message, when there isn't. The Bible Codes are an example. The idea is that God hid secret messages in the Bible which are revealed by equidistant letter spacing. Never mind that such "messages" can be found by ELS in any sufficient large work. Practitioners never seem to find the messages until after they become relevant...
It's part of a hidden, encrypted data stream!
Actually, TFA is a steganographic message to the Manchurian candidate.
Set your phasers on "funky"!