[chongli]

To answer the question: It shows up as a specific type of noise that's easy to detect. Some of the crypto / math people will be able to explain it much better than I can.

Ahhh. What if you were to use a video instead of a still image and only use a handful of pixels (or macroblocks) in each frame, chosen randomly (the random seed exchanged out-of-band)? Seems like that would give you a very high cover:hidden text ratio.

[rosser]

Seems like that would give you a very high cover:hidden text ratio.

It would, but that doesn't change the principles used to detect the steganographically encoded cyphertext. The bits would still be twiddled in the same way, and could be found in the same way.

[chongli]

The question is: would it be feasible to search for them? Scan every single video on youtube looking for noise with some elevated probability of containing hidden text? What happens when you find a candidate? Pick random pixels out of every frame and then try and brute force it with every known symmetric cipher and every single key?

You could flip a single, random, least-significant bit on each frame of a 1 hour movie. This would allow you to store a 10.5KB encrypted message within. I'd like to know how anyone could possibly find those bits, let alone decipher them.

[rosser]

Depends on your use case and threat model.

If I'm the Secret Police in some oppressive state, then I just need to find out whether you seem to be using stego — which is naturally against the law, itself, and hence grounds for arrest. Then, I can use rubber hoses, bamboo splinters, the threat of violence against your loved ones, and what-not to "brute force" your passphrase.

If I'm the NSA, I just detect the presence of stego and stash the container for later — say, when my quantum computer finally works as advertised, or I can plant a keylogger or turn on the back door on the your computers and sniff your passphrase, or simply mine your social graph until I find some other means of compromising you.

The possibilities are hardly limited to a naïve, brute-force search across the set of (crypto algorithm, passphrase) tuples.

EDIT: But, to your point: yes, using video makes finding stego harder. It doesn't change the nature of the problem, though; it just changes its scale. Against adversaries with the computational power of a modern nation-state, however, if you're relying on scale to hide your behavior, licit or otherwise, you're only deluding yourself.

[chongli]

If I'm the Secret Police in some oppressive state, then I just need to find out whether you seem to be using stego — which is naturally against the law, itself, and hence grounds for arrest. Then, I can use rubber hoses, bamboo splinters, the threat of violence against your loved ones, and what-not to "brute force" your passphrase.

Me? I'm the entire population of the country. Which one of us is using stego?

To my reckoning, the search space would put the number of atoms in the universe to shame.

[rosser]

Maybe start with the guy who uploaded the video to YouTube?

[jcarpio]

I'd like to know if there's been an implementation of that. I remember reading about such a thing in William Gibson's Pattern Recognition.