[email@rsasecurity.rsc03.com: RSA Conference 2003 Call for Papers - Deadline September 16!]
Suprised this never made it through, so here it is =) Papers are due
next monday.
Billy
--- Forwarded message from RSA Conference 2003
Cypherpunks, I had an interesting revelation last night. It's a bad idea to use perceptually-coded media to embed steganographic data. By definition, it means making the coder make decisions that it otherwise would not have made. If the coder is good, then the coder's decisions are not arbitrary but rather each bit is focused on producing the minimal representation necessary for adequate presentation to humans. This means that encoding extra "random" data on top of this will always produce compressed output that is of lower quality than the original. From an information theory standpoint, if you're tacking on a data stream to compressed output, the stream that is the sum of the two contains more information and must be represented with more bits. For example, to attack steganographically-encoded pictures, the pictures could be analysed and those with lower-quality encoding than expected would be flagged for analysis as suspect. The conclusion is remarkable (to my little mind, at any rate): since most media transmitted over the Internet is perceptually compressed (JPG, MOV, AVI, MP3, etc.) the efforts to steganographically encode data within most Internet media are fundamentally doomed. Where, then, can one hide information streams? The answer is wherever *random* information is communicated. (Even just partial randomness is okay; I've got a paper on this I hope to be presenting soon!) David E. Weekly Founder & Executive Director California Community Colocation Project (an OPG project) http://CommunityColo.net/ - the world's first non-profit colo!
On Fri, 13 Sep 2002, David E. Weekly wrote:
The conclusion is remarkable (to my little mind, at any rate): since most media transmitted over the Internet is perceptually compressed (JPG, MOV, AVI, MP3, etc.) the efforts to steganographically encode data within most Internet media are fundamentally doomed.
Since MP3 and JPG are lossy compression you don't want to use them in any case - you really screw up the image if you attach random data to the compressed values, and you lose the data completely if you try to compress the stegonagraphic info. So it's not useful for more basic reasons.
Where, then, can one hide information streams? The answer is wherever *random* information is communicated. (Even just partial randomness is okay; I've got a paper on this I hope to be presenting soon!)
It doesn't have to be random, it has to be complete. Random is definitly better, but it's unlikely that steganography would be needed if one could send random data for any reason to begin with. You want the message to be invisible, and anyone looking for hidden messages is certain to scan "random" data and check it for statistics. The power of statistics makes steganography really hard. Patience, persistence, truth, Dr. mike
It doesn't have to be random, it has to be complete. Random is definitly better, but it's unlikely that steganography would be needed if one could send random data for any reason to begin with. You want the message to be invisible, and anyone looking for hidden messages is certain to scan "random" data and check it for statistics. The power of statistics makes steganography really hard.
The key is to steganographically encode "random" (encrypted) data and then "shape" the result to match the mean probabilities seen in observation of a system in usual operation. This defeats statistical analysis, since your data is shaped just like everyone else's. If the bits are encrypted with a recipient's public key, only with posession of the private key can the data be perceived to be non-random, which is a nicely strong property. -David Weekly
Where, then, can one hide information streams? The answer is wherever *random* information is communicated. (Even just partial randomness is okay; I've got a paper on this I hope to be presenting soon!)
State security directive #219: "No video, film or still image shall contain within it a TV screen filled with noise. The noise should be replaced by the state-approved patterns that can be downloaded from the Bit Control Agency web servers." ===== end (of original message) Y-a*h*o-o (yes, they scan for this) spam follows: Yahoo! Finance - Get real-time stock quotes http://finance.yahoo.com
Cypherpunks,
This is certainly a point that many people are coming to believe. But I think you have to be careful with taking it to extremes. Are there problems with changing the character of noise? Yes, but as you pointed out it may be possible to sculpt the inserted information to conform to the statistical character of the overall file. One of the simplest tricks is just to insert a relatively small message in a relatively large file. Any statistical changes will be lost in the noise. This is a pretty practical solution because there are plenty of images that take hundreds of thousands if not millions of bytes. A thousand bytes of text gets lost pretty quickly. It's also important to remember that there are many tricks that avoid making changes in the usual way. I'm currently very intrigued with the potential to rearrange lists of items. (You can try out an applet here: http://www.wayner.org/books/discrypt2/sorted.php) I guess it's important not to let an obsessive attention to mathematical perfection prevent you from accomplishing something cool. After all, every RSA key can be factored eventually, but we still use the system because it's practically secure. -Peter
I had an interesting revelation last night. It's a bad idea to use perceptually-coded media to embed steganographic data. By definition, it means making the coder make decisions that it otherwise would not have made. If the coder is good, then the coder's decisions are not arbitrary but rather each bit is focused on producing the minimal representation necessary for adequate presentation to humans. This means that encoding extra "random" data on top of this will always produce compressed output that is of lower quality than the original. From an information theory standpoint, if you're tacking on a data stream to compressed output, the stream that is the sum of the two contains more information and must be represented with more bits. For example, to attack steganographically-encoded pictures, the pictures could be analysed and those with lower-quality encoding than expected would be flagged for analysis as suspect.
The conclusion is remarkable (to my little mind, at any rate): since most media transmitted over the Internet is perceptually compressed (JPG, MOV, AVI, MP3, etc.) the efforts to steganographically encode data within most Internet media are fundamentally doomed.
Where, then, can one hide information streams? The answer is wherever *random* information is communicated. (Even just partial randomness is okay; I've got a paper on this I hope to be presenting soon!)
On 14 Sep 2002 at 12:32, Peter Wayner wrote:
It's also important to remember that there are many tricks that avoid making changes in the usual way. I'm currently very intrigued with the potential to rearrange lists of items. (You can try out an applet here: http://www.wayner.org/books/discrypt2/sorted.php)
There's an error in the way youconvert arrangements into numbers. On your page you have <quote> A Strange Notation Before beginning, we need to introduce one slightly strange notation, a flexible base, where the ith digit can be any value between 0 and i+1. The digits are enumerated from right to left so the smallest value, the one with the least significance on the right, is digit 0. It can be either a 0 or a 1. The next digit to its left, the one with next-to-least significance, is digit 1 and it can be either a 0, a 1, or a 2. Here's a value in the flexible base: 321. Each digit is set to it's maximum value. What is this value in base 10? To figure this out, first find the multiple assigned to each digit. That is, how much each digit contributes to the final value. In base 10, the multiple assigned to digit 1 is 10 and the multiple assigned to digit 2 is 100. To put it simply, the multiple of digit i is 10i in base ten and 2i in base two. What is the multiple of each digit in this flexible base? In the fixed bases, each digit's multiple increases by another factor of the base for each new digit. In this example, each digit has a different value. The 0 digit can only take two values, 0 or 1. The 1 digit can take three values, 0, 1 or 2. The multiple of digit i is (i+1)!. You can check it out. What is 321 in base ten? That's 1*(1!)+2*(2!)+3*(3!)=1+4+18=23. </quote> There's no reason for the factorials in the notation, the multiple of digit i should be i, not i!, so the value of any permutation of n items should be something from 0 to n!-1. for example, for 3 items what you should have is permutation value 123 0 132 1 213 2 231 3 312 4 321 5
I guess it's important not to let an obsessive attention to mathematical perfection prevent you from accomplishing something cool. After all, every RSA key can be factored eventually, but we still use the system because it's practically secure.
-Peter
George
participants (6)
-
Billy -
David E. Weekly -
georgemw＠speakeasy.net -
Mike Rosing -
Morlock Elloi -
Peter Wayner