Re: The problem with Steganography
Catching up on the thread, the comments about fitting the stego into the image reminded me of http://www.outguess.org/ by Niels Provos. Looks like he's a few months ahead of you Marc Horowitz wrote: Rick Smith [EMAIL PROTECTED] writes: Thus, a 'good' stego system must use a crypto strategy whose statistical properties mimic the noise properties of the carrying document. ... So, can't we detect the presence of stego'ed data by looking for 'noise' in the document that's *too* random? ... Once we replace those bits with data, the bits will have serously random statistical properties. So, we can detect stego'ed data if the implementation uses any well known strong encryption algorithm. If the picture was taken by an actual camera, the least significant bits will be random due to the nature of the way CCDs work in the real world. They might be biased, but it's not very hard to bias a "random" data stream. [EMAIL PROTECTED] Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32
Re: The problem with Steganography
Ben Laurie writes: If you want a lot of people to see it, you can't keep it secret. If you can't keep it secret, you may as well just come out with it and publish the bits without stego. What did I miss? It depends on how hostile the regime is. If you want to publish something but the publishing process itself is risky, you could publish it stego'd after running it through something pseudo-random, e.g. the low bits of a particular song. Hmmm I think I'm thinking... my brain is starting to swell... I'm starting to come up with something. Just as PGP doesn't use a public key algorithm to encrypt, but instead to encrypt a private-key-encryption key, you wouldn't use low-bit stego to hide the data, you'd use it to say which *other* stream of random bits had been used to exclusive-or the actual encrypted data. If the set of random (low) bits came from the same type of data stream, then the statistics would be the same. So you use 1 out of every 1024 bits to create a number, and the number selects a particular archived piece of data, and then ... and then Sigh. But here we run into security by obscurity. This only works if the algorithm to select the other audio stream is not published. As soon as you publish it, someone can de-randomize, or de-color the data, and see that you have non-statistically-correct data hidden. What you'd need to do is have an algorithm which takes in a whole big pile of bits, and depending on the recipient's private key, selects some of them for decryption. In this manner, you make the problem of detecting the stego computationally equal to decrypting the data. -- -russ nelson [EMAIL PROTECTED] http://russnelson.com Crynwr sells support for free software | PGPok | "Ask not what your country 521 Pleasant Valley Rd. | +1 315 268 1925 voice | can force other people to Potsdam, NY 13676-3213 | +1 315 268 9201 FAX | do for you..." -Perry M.
Re: The problem with Steganography
At 1:34 AM -0500 1/26/2000, Marc Horowitz wrote: Rick Smith [EMAIL PROTECTED] writes: The basic notion of stego is that one replaces 'noise' in a document with the stego'ed information. Thus, a 'good' stego system must use a crypto strategy whose statistical properties mimic the noise properties of the carrying document. Our favorite off the shelf crypto algorithms do *not* have this property -- they are designed to generate output that looks statistically random. So, can't we detect the presence of stego'ed data by looking for 'noise' in the document that's *too* random? For example, many stego implementations involve embedding data in the low order bits of a graphical image. Those low order bits undoubtedly have some measurably non-random statistical properties. Once we replace those bits with data, the bits will have serously random statistical properties. So, we can detect stego'ed data if the implementation uses any well known strong encryption algorithm. Closely matching the statistical properties of a physical device could be difficult. A different approach would be encouraging large numbers of people with video Internet feeds to "pre-stego" their material. This could be easily done by xor'ing low order bits with bits generated by some strong crypto algorithm, frequently rekeyed by dev/random. Perhaps Linux Webcam and Video chat packages could have this feature enabled as a default. Since it would be impossible to distinguish actual stego from pre-stegoed material, this would be a very effective way to protest against attempts to restrict the flow of information on the Internet. If enough people participated stego would be undetectable. Arnold Reinhold
Re: The problem with Steganography
On Tue, Jan 25, 2000 at 04:51:12PM -0800, Nelson Minar wrote: Of course, this isn't easy to do - "matching statistical properties" isn't a simple closed problem. But I bet you could do fairly well in certain circumstances. For instance, Linux uses a strong random number when starting a TCP connections. I bet you can hide a few bits of data in there and no one will see it. Any protocol that uses MACs (message authentication codes) could also work. Replace the last N bits of the MAC with your encrypted data. The MAC verification would fail at the other end, but if the recipient expected stegoed data there they could check the first (MACsize - N) bits and still detect tampering while receiving the hidden data. This should work because only the participating parties can verify the MAC. To an observer the MAC is just cryptographic noise with exactly the same statistical properties as the ciphertext you want to hide. If the remaining MAC bits authenticated the embedded ciphertext as well as the normal plaintext data then your protocol would function exactly as it did before- If anyone tampered with your data or the MAC then your software would reject the altered data just as it would if you weren't doing any stego at all. This is important because it would prevent your stego activities from being detected by an active attack on the protocol. I think I suggested something like this before, shortly after Rivest's "Chaffing and Winnowing" hit the 'net.
Re: The problem with Steganography
In message [EMAIL PROTECTED], Marc Horowitz writes: In short, is steganography the ultimate surveillance tool? Like most surveillance technologies, this is a game of constant incremental improvements. You watch me through a window, I put up curtains. You listen through a hidden microphone, I increase the background noise. Etc. As was discussed here a few weeks ago, it's very difficult to do undefeatable watermarking, and I'd say it's impossible to do undetectable watermaking in a digital medium (just compare the documents). My point is that stego could be used as a surveillance tool, but it would be difficult, and defeating it would be feasible. Therefore, I don't believe it is the "ultimate" surveillance tool. So -- has anyone on this list found the watermarking present in color copier output? --Steve Bellovin
Re: The problem with Steganography
question becomes, without identifying the location of the ciphertext in a prior agreement or on some outside channel, can a person communicate with friends without alerting enemies to the existance of secret communications? In this case you are entering the realm of psychology. There may be a number of methods, but they should be explicit enough for the friends to notice, and this in turn depends on their knowledge and willingness. How so? Some people may be intelligent enough to notice that letters from their bank form an acrostic of a URL, but others may need detailed explanations about what stego is. Bottom line is, you know your friends, you know your enemies, use your imagination. Example: money laundering works in almost every country, if they can "hide" their activities so can you too. Or you may use hidden knowldege about them and refer to it. Or you may trade off a major gain for a minor loss, say become a cigarette smuggler in the foreground to hide your setup message. Again, that all falls in the realm of psychology. j
Re: The problem with Steganography
At 12:12 AM 01/27/2000 +, Ben Laurie wrote: I can't quite see the point of forward stego. I'll leave it to Russ to explain his application if he wants to. Why not publish something public key encrypted and publish the private key later? Symmetric cryptography has two advantages in this application: 1. it requires fewer resources to implement and 2. there aren't any data dependent vulnerabilities like there are with public key algorithms. It's like encrypted e-mail: you use the symmetric key for the data and the public key to encrypt the symmetric key. Since the symmetric key is secret random data, it's less susceptable to attack. Rick. [EMAIL PROTECTED]
Re: The problem with Steganography
I wonder if stego users will have to choose between uncrackable encryption or undetectable data. I don't think so. Replacing the low-order bits of a picture with random noise (or an encrypted message) is silly - like you say, anyone can find it easily. But there is a certain amount of free entropy in a picture. And if you create a data stream to match its statistical properties, and you hide it there, no one's going to notice. Of course, this isn't easy to do - "matching statistical properties" isn't a simple closed problem. But I bet you could do fairly well in certain circumstances. For instance, Linux uses a strong random number when starting a TCP connections. I bet you can hide a few bits of data in there and no one will see it. [EMAIL PROTECTED] . . . .. . . . http://www.media.mit.edu/~nelson/
Re: The problem with Steganography
The basic notion of stego is that one replaces 'noise' in a document with the stego'ed information. Thus, a 'good' stego system must use a crypto strategy whose statistical properties mimic the noise properties of the carrying document. Our favorite off the shelf crypto algorithms do *not* have this property -- they are designed to generate output that looks statistically random. So, can't we detect the presence of stego'ed data by looking for 'noise' in the document that's *too* random? Yes, and no. There is no particular difficulty in altering the statistics of encrypted data to match whatever distribution is necessary for the noise. So there is no reason a priori to expect that stego'd data would be "too random". The real problem arises in constructing an accurate noise model. Whatever model is built can be matched, but there is always the worry that the model is not quite right. In particular, if the adversary can spend more to construct an accurate noise model than the steganographer, then he can detect the stego'd data because its statistics will differ in subtle ways from natural data. In these circumstances, it is prudent to assume that an adversary does have more money to spend than the person hiding the data. He may well be a large government agency or a private bureaucracy which is looking for illicit data. The attacker's budget will often be far bigger than that of the people who need to hide from him. All is not necessarily lost; it becomes a matter of sufficient accuracy for the purpose. In order to distinguish the stego data from natural data it may be necessary to acquire a considerable volume of messages. The stego noise model only needs to be accurate enough to make the data indistinguishable from noise for the specific volume of data being embedded. If this threshold is reached, then even if the attacker's model is better the stego can still succeed. The greater danger is a subtle but catastrophic failure of the noise model, as for example when a new statistical analysis is used which the steganographer did not consider, perhaps some kind of higher order correlation. The well funded attacker can afford to spend time searching for such statistics, and if he is lucky, the game may be over before it has begun. These considerations are the real art and science of steganography. Plunking data into LSBs is grade school stuff, analogous to ROT13 as a cipher. True steganography goes far beyond such elementary substitutions.
Re: The problem with Steganography
David Honig writes: At 03:20 PM 1/25/00 -0500, Russell Nelson wrote: I'm trying to do forward stego -- that is, publish some encrypted steganographic document, with the idea that, once everyone has a copy, *then* you reveal the key. Fascinating, captain. Canna imagine why. Blackmail? But you don't really need stego for that. You could just send a private-key-encoded file to a list of friends, saying "Please keep this until mm/dd/yy. I may send you the key later." Run a watchdog process somewhere which checks a certain newsgroup for a crypto-signed timestamped message. If it fails to see the message, it sends the key to your list of friends. You could also use it for "Oh, by the way, that gzipped file of the Linux kernel that you downloaded, that's mirrored all over everywhere? It's made with certain sub-optimal compressions. If you run it through this program, it will produce a copy of the DeCSS code." If you wanted to be really clever, you'd bury it inside some government document, so you could at least obfuscate the prosecution with claims of First Amendment rights. But that's not stego either, whether the document is encrypted or not, because you're adding bits, not replacing relatively random bits. Problem is, how do you convince them to keep a copy of that document if they're unaware that it has something buried inside it?? Now you're into psychology. Yup. And I'm certainly (obviously not) competent at that. -- -russ nelson [EMAIL PROTECTED] http://russnelson.com Crynwr sells support for free software | PGPok | "Ask not what your country 521 Pleasant Valley Rd. | +1 315 268 1925 voice | can force other people to Potsdam, NY 13676-3213 | +1 315 268 9201 FAX | do for you..." -Perry M.
Re: The problem with Steganography
On Tue, 25 Jan 2000, Rick Smith wrote: . . . . For example, many stego implementations involve embedding data in the low order bits of a graphical image. Those low order bits undoubtedly have some measurably non-random statistical properties. Once we replace those bits with data, the bits will have serously random statistical properties. So, we can detect stego'ed data if the implementation uses any well known strong encryption algorithm. Why disturb the measurably non-random statistical properties of the low order bits? No one says you have to use your crypto output straight, without 'bluing', so to speak. What if we replace every nth lower order bit, and make n relatively large? Message carrying capacity is reduced, but it becomes harder to see (guess) that a message is hidden there. I wonder if stego users will have to choose between uncrackable encryption or undetectable data. Or extreme inefficiency? Rick. [EMAIL PROTECTED]
Re: The problem with Steganography
If the picture was taken by an actual camera, the least significant bits will be random due to the nature of the way CCDs work in the real world. They might be biased, but it's not very hard to bias a "random" data stream. You could have the sender look at the bias in the odd frames, and use that in the following even frames, if the bias is similar. The recipient could compute the bias in the odd frames, and use that to normalize the stego in the even frames before applying the crypto. If the scene changes drastically, the bias may change, the sender wouldn't encode anything in that frame, and the recipient will need to resync somehow. Stego is subtle, but it's not impossible. After thinking about this a bit, perhaps the point is that any conversion, light-on-CCD to bits, bits to paper, etc., has a certain amount of bias-able "random" data and hence it is likely that any such process has a fingerprint that might even be unique as, of course, the color copier example shows can be made intentional. My knowledge of media reproduction technology in the large is near zero, but if a color copier can identify itself what is to keep it from identifying the time of day or serial numbering the individual copy or silently including a photo of the operator? Larger still, what's to prevent adding such a fingerprint to every copy of National Geographic, to every film processing lab's printing system, to every copy of every MP3 file, to the transmission of every PCS phone, etc., etc.? In short, is steganography the ultimate surveillance tool? --dan
Re: The problem with Steganography
Forgive me if I'm missing the point here but I don't think the original question was how to make steganography better and hide the message more effectively (although that's certainly a valuable goal). Sometimes it's important to hide the fact that a secret message exists. A good guy in enemy territory may wish to communicate with friends outside. Discovery of the ciphertext would alert the enemy to his presence. So the question becomes, without identifying the location of the ciphertext in a prior agreement or on some outside channel, can a person communicate with friends without alerting enemies to the existance of secret communications? For example, it's possible that this email was written by a political prisoner in a 3rd world country and he's used steganography to conceal a message to his friends and family right here in these 3 paragraphs. My question is, without prior agreement or access to an outside channel, how are his friends to know to look on the [EMAIL PROTECTED] Listserv for the ciphertext? No matter how well concealed (stego)or how well encrypted (crypto), does he have any way of notifying his friends that they should look here without alerting the enemy of his attempts to communicate? - Eric Tully
Re: The problem with Steganography
Rick Smith wrote: It sounds like there are a number of interesting design questions. For example, the sender and recipient must obviously share a secret key. Why is that obvious? What's wrong with encoding with the recipient's public key? Cheers, Ben. -- SECURE HOSTING AT THE BUNKER! http://www.thebunker.net/hosting.htm http://www.apache-ssl.org/ben.html Y19100 no-prize winner! http://www.ntk.net/index.cgi?back=2000/now0121.txt
Re: The problem with Steganography
Rick Smith wrote: Rick Smith wrote: It sounds like there are a number of interesting design questions. For example, the sender and recipient must obviously share a secret key. At 10:18 PM 01/26/2000 +, Ben Laurie wrote: Why is that obvious? What's wrong with encoding with the recipient's public key? It depends on what you're encoding. I expect we end up with a three step process: first, encrypt the data, second, stego it into the image or other file, and third, provide the recipient with information for recovering the hidden data. If we're talking about the first step, encryption of the raw data that's being stego'ed (is there a more legitimate verb for that?), then I'd prefer to use secret key encryption, since it introduces fewer uncertainties regarding the safety of the ciphertext. As to step 3, how this secret information is shared with potential recipients, public key techniques are fine. If we're talking about Russ Nelson's "forward stego" problem, then PK is overkill -- he just needs to publish the secret information and voila, the previously hidden information is uncovered. As to Russ' problem of how to keep the information "available," I suggest we look around our environments and take stock of what iconic images or files we all have and for some reason can't part with. Perhaps there's some really great crt wallpaper image that would do the job, or one could embed it in a Craig Shergold make-a-wish chain letter. Those things NEVER die. I can't quite see the point of forward stego. Why not publish something public key encrypted and publish the private key later? If you want a lot of people to see it, you can't keep it secret. If you can't keep it secret, you may as well just come out with it and publish the bits without stego. What did I miss? Cheers, Ben. -- SECURE HOSTING AT THE BUNKER! http://www.thebunker.net/hosting.htm http://www.apache-ssl.org/ben.html Y19100 no-prize winner! http://www.ntk.net/index.cgi?back=2000/now0121.txt
Re: The problem with Steganography
For example, it's possible that this email was written by a political prisoner in a 3rd world country and he's used steganography to conceal a message to his friends and family right here in these 3 paragraphs. My question is, without prior agreement or access to an outside channel, how are his friends to know to look on the [EMAIL PROTECTED] Listserv for the ciphertext? No matter how well concealed (stego)or how well encrypted (crypto), does he have any way of notifying his friends that they should look here without alerting the enemy of his attempts to communicate? Ideally, this would be handled by prearrangement, so that anyone involved in a resistance movement or who might be a target as a political prisoner would know where to post his messages and what keys to use so that they could be read. If this was not done, he could still tell his friends that he has heard that some people embed messages in that specific location. He could describe the software program used to do so, and that their public keys would be used to read the message. Maybe to be "politically correct" he could go on and say that doing this would be wrong. Presumably this would be enough of a hint for anyone; even the bad guys, of course, but they would not be able to tell whether any data was actually being sent by this channel. [Presumably the bad guys would only need to suspect, not to know for sure -- if they really don't pay attention to human rights, well, I'm sure the rubber hose will be cheap enough for them to buy. --Perry]
Re: The problem with Steganography
The problem with Steganography is that there's basically no way to clue people in to it's location without clueing everyone into it. That's not a problem. By definition, successful steganography is undetectable even when you know where to look. Otherwise the steaganography has failed. Encryption is successful if the attacker can't find information about the plaintext without the key. Ideally, he can't answer questions about the plaintext any better with access to the ciphertext than without. Steganography is successful if the attacker can't distinguish message-holding data from ordinary data without the key. Ideally, he can't guess whether a message is present any better upon inspecting the cover data than he could without being able to see it. With this model there is no problem in making everyone aware of where to look for cover traffic with stego data in it.
Re: The problem with Steganography
I think this is a security model issue. Steganography is useful if there is some out of band communication ahead of time. If there is no way to let the receiving party know that he or she will be receiving a hidden message, and how to retreive it, then steganography isn't useful. Without the knowledge of where the message is and how to retreive it, the intended recipient and the attacker are both prevented from reading it. In some situations, steganography can be usefully employed, but it isn't a panacea for all secure communication applications. The 'problem' is not with steganography, but with trying to apply it outside of a security model that permits it. On 25 Jan 2000, lcs Mixmaster Remailer wrote: The problem with Steganography is that there's basically no way to clue people in to it's location without clueing everyone into it. That's not a problem. By definition, successful steganography is undetectable even when you know where to look. Otherwise the steaganography has failed. Encryption is successful if the attacker can't find information about the plaintext without the key. Ideally, he can't answer questions about the plaintext any better with access to the ciphertext than without. Steganography is successful if the attacker can't distinguish message-holding data from ordinary data without the key. Ideally, he can't guess whether a message is present any better upon inspecting the cover data than he could without being able to see it. With this model there is no problem in making everyone aware of where to look for cover traffic with stego data in it.
Re: The problem with Steganography
lcs Mixmaster Remailer writes: The problem with Steganography is that there's basically no way to clue people in to it's location without clueing everyone into it. Encryption is successful if the attacker can't find information about the plaintext without the key. Ideally, he can't answer questions about the plaintext any better with access to the ciphertext than without. I'm trying to do forward stego -- that is, publish some encrypted steganographic document, with the idea that, once everyone has a copy, *then* you reveal the key. Problem is, how do you convince them to keep a copy of that document if they're unaware that it has something buried inside it?? In this particular case, there is no crypto -- it's completely security-by-obscurity. I've published the burial algorithm, or at least sent it to the maintainer of the software. Haven't written the retrieval algorithm yet, so in a sense the "key" is still secret. But only 33 people sucked down a copy. Maybe I should have buried it inside a pornographic picture? :) -- -russ nelson [EMAIL PROTECTED] http://russnelson.com Crynwr sells support for free software | PGPok | "Ask not what your country 521 Pleasant Valley Rd. | +1 315 268 1925 voice | can force other people to Potsdam, NY 13676-3213 | +1 315 268 9201 FAX | do for you..." -Perry M.
Re: The problem with Steganography
At 03:20 PM 1/25/00 -0500, Russell Nelson wrote: I'm trying to do forward stego -- that is, publish some encrypted steganographic document, with the idea that, once everyone has a copy, *then* you reveal the key. Fascinating, captain. Canna imagine why. Problem is, how do you convince them to keep a copy of that document if they're unaware that it has something buried inside it?? Now you're into psychology. (Not necessarily a cryptodigression: consider how the business model for an Eternity system is critical for handling various attacks/spammages) Maybe I should have buried it inside a pornographic picture? :) Primates are easy to manipulate sometimes. What docs *do* you retain? Controversial ones you think might be pulled, sure. Aesthetic ones (incl. erotica) if you think you might look at it again. (This might include personal, objectively boring pictures.) Informative ones, if you think you might refer to them again. Look at the subjective-merits that factor in. Expectation of future value; subjective current value. Ick. You'd best have a varied selection of content (e.g., images by all genres of artists; music by all genres; etc.) rather than shoot for a single "hit" bitstring. All the content would be stego'd, but diff't people download diff't covertext. How long do you need people to retain the content, btw? Perhaps once you revealed the secret message "if you play it backwards" the Saturation will increase. dh board-certified cat rancher
Re: The problem with Steganography
At 07:20 PM 01/25/2000 -, lcs Mixmaster Remailer wrote: Steganography is successful if the attacker can't distinguish message-holding data from ordinary data without the key. Ideally, he can't guess whether a message is present any better upon inspecting the cover data than he could without being able to see it. With this model there is no problem in making everyone aware of where to look for cover traffic with stego data in it. Has anyone actually built a steganographic system that has achieved this? The basic notion of stego is that one replaces 'noise' in a document with the stego'ed information. Thus, a 'good' stego system must use a crypto strategy whose statistical properties mimic the noise properties of the carrying document. Our favorite off the shelf crypto algorithms do *not* have this property -- they are designed to generate output that looks statistically random. So, can't we detect the presence of stego'ed data by looking for 'noise' in the document that's *too* random? For example, many stego implementations involve embedding data in the low order bits of a graphical image. Those low order bits undoubtedly have some measurably non-random statistical properties. Once we replace those bits with data, the bits will have serously random statistical properties. So, we can detect stego'ed data if the implementation uses any well known strong encryption algorithm. I wonder if stego users will have to choose between uncrackable encryption or undetectable data. Rick. [EMAIL PROTECTED]
