As far as I know the state of the art in image stego is perturbed quantization with wet paper codes.
The essential idea with wet paper codes is that you can use error correcting codes so that even the recipient need not know which bits contain the data.
A simple analogy is that if you wanted to communicate only a single bit you could decide that the xor of all the data in the image decides the bit. Then the encoder can flip the single least distinguishable bit to encode their message.
The idea behind perturbed quantization is that when you quantize the data (e.g. while jpeg compressing it) some values will be maximally close to tied between rounding up and rounding down. If you embed your data in those values you'll minimize the embedding noise.
Unfortunately most of the work on approaches based on these ideas is academic and has no public implementation, but there is one that I'm aware of https://sourceforge.net/projects/pqstego/
There is a lot that could be done both with respect to security (e.g. using better models to predict the image to hide the stego noise better, better error correcting codes, and list decoding) and basic engineering, e.g. handling content length encoding better.
Image steganography techniques have indeed reached a level of sophistication that requires significant expertise to implement correctly. A good parallel is compression--most CS undergrads can figure out how to implement Huffman or even LZW compression, but state-of-the-art ANS (asymmetric numeral systems) is pretty dense. I believe a special type of wet paper code called a syndrome-trellis code is at the forefront of image steganography: http://dde.binghamton.edu/filler/pdf/Fill10tifs-stc.pdf. Good luck parsing that without a solid foundation in information theory.
Steganography is the current focus of my PhD research, and from my perspective the greatest security challenges are in systems engineering. Embedding secret messages into your vacation photos is one thing, but who are you sending these messages to? And why? How will they know when and where to go looking for the secret message?
Encryption entered its golden age with the advent of public-key cryptography and Diffie-Hellman key exchange, allowing two parties to share the secrets required for secure communication knowing only public information about one another. However, steganographic systems are still dependent upon lots of out-of-band secret sharing, since attempting to share the necessary secrets over public channels tends to reveal the existence of the system and opens up DoS attacks (e.g. Tor and the identity of relays). IMHO, figuring out better solutions to the system security of particular steganographic applications is a much more pressing research problem than improving statistical embedding profiles for image steganography.
You can use public key encryption which is indistinguishable from uniform. E.g. using ECDH w/ ellegator and ed25519 for the key agreement.
Then the recipient of the stego need only publish the public key. If the encoding software were part of standard linux distributions (even if just specialized security conscious distros), then the sender could obtain it without identifying themselves.
I don't think you can tackle the problems in isolation: There isn't much point in making uniform encryption if the embedding gives it away to anyone who's looking. :)
> but who are you sending these messages to?
One scheme I've been fond of is where the recipient announces their public key and that they'll accept messages in images posted to some moderately high traffic public picture board, like r/naturepics. Then then simply download and process all images submitted there.
The sender has an easy and obvious cover story for their posting and can produce as many images they need just by visiting a park with a camera.
A typical threat model is that there is a "warden" who can selectively block messages, so this would not really work since the warden would block the announcement (in theory the warden is not going to block all messages, although a formal security definition should only focus on whether or not the warden is more likely to block stegomessages than innocent messages, which is trivial if the warden blocks everything). Thus out of band communication is needed to distribute secrets; likewise, the stegosoftware itself has to be distributed out of band.
"indistinguishable from uniform"
Actually you need to be indistinguishable from the "background noise" (the thermal noise from the camera sensor) of the image, which is not uniform. In fact, the noise is correlated with the camera itself and can be used to identify which camera took a particular photo.
> Thus out of band communication is needed to distribute secrets; likewise, the stegosoftware itself has to be distributed out of band.
This is why public key cryptography is so important. Because you can use a broadcast channel -- like a Linux distro to communicate the tools and required knowledge in a way that doesn't give a strong signal that you're using it.
> "indistinguishable from uniform" Actually you need to be indistinguishable from the "background noise" (the thermal noise from the camera sensor) of the image
This isn't the case for code based encoding. The encoded values are a pseudorandom linear combination of a huge number of bits from the image and end up being extremely uniform. Consider my silly xor example: the xor of all the bits in the image is going to be close to uniform, even if the bits in the image are fairly biased.
But also more generally: If you have a way to map encrypted messages onto the space of uniform strings, then you can also remap from them onto any other required distribution in a fairly straight forward way.
Having a good error metric is important though, and it's one of the areas that seems a bit under researched.
That is not part of the threat model, and in any case is basically an out-of-band channel.
"like a Linux distro to communicate the tools and required knowledge in a way that doesn't give a strong signal that you're using it."
Again, the threat model is that the adversary controls the network and can block or modify messages at will. So unless all linux distros included the software, the adversary would simply block those that include the software. The threat model of steganography basically implies that some out of band distribution is needed.
"encoded values are a pseudorandom linear combination of a huge number of bits from the image and end up being extremely uniform"
That has nothing to do with what I was talking about. The "time domain" of the image is where the noise lies and where the bias exists in the bits. Even if it can be encoded in some way that looks uniform, that does not mean that an arbitrary change to the encoded image will have the correct bias when it is decoded.
"you can also remap from them onto any other required distribution in a fairly straight forward way."
In the forward direction, but the reverse direction is not so straightforward. This is a classic problem with doing ElGamal encryption on elliptic curves -- some curves do not have an easily invertable map from bit strings to the EC group. I do not know how hard this is to do with images, but when I last looked image stegosystems relied on heuristics and needed relatively short messages to remain secure.
> That is not part of the threat model, and in any case is basically an out-of-band channel.
It may not be the threat model you are interested in but it's part of the usage model of just about anyone capable of actually using a computer with arbitrary software, even in extremely restricted parts of the world. (users who can't run arbitrary software can't really be helped by steg stuff they can't use!)
Simplified threat models can be extremely helpful in formalizing security arguments, but taking them too and confusing them for actual usage can be devastating for the users security too.
> That has nothing to do with what I was talking about. The "time domain" of the image is where the noise lies and where the bias exists in the bits. Even if it can be encoded in some way that looks uniform, that does not mean that an arbitrary change to the encoded image will have the correct bias when it is decoded.
In fact it has everything to do with what you were talking about. One of the advantages of using wet paper codes is that you can arbitrarily preserve the properties of the underlying data while encoding uniformly random information. Even better: only the encoder needs to know about the properties that are being preserved, so it can use information which is unavailable to the attacker or the receiver such as an unquantized or higher resolution original. This is what the PQstego program I linked above does.
The encoder has significant freedom to preserve whatever properties it needs to preserve while encoding uniform data.
> but the reverse direction is not so straightforward. This is a classic problem with doing ElGamal encryption on elliptic curves
You would _very much_ not want to use ElGamal for this (or essentially any application which you didn't need its additive homomophism)-- doing so has terrible performance, terrible security properties, and terrible communications efficiency.
If you look back at my message I specifically brought up "elligator" for ECDH -- a bidirectional mapping between curve25519 points and bits. Similar approaches exist for many other curves.
> But also more generally: If you have a way to map encrypted messages onto the space of uniform strings, then you can also remap from them onto any other required distribution in a fairly straight forward way.
This is true, but it begs the question: where does the “required distribution” come from? Most (all?) steganographic techniques make heuristic arguments about some plausible cover distribution but there is no provable security as with cryptography.
There are some theoretical results on how to make steganography provably secure, but they make use of objects (“channel oracles”) which cannot feasibly be instantiated in the real world except in a handful of unique cases.
I was starting to write what I think a useful framework is-- but then realized that it's probably what a channel oracle is.
Let me guess: You provide a set of weights along with the cover data, and so long as your weighed error is below some threshold it cannot be distinguished. For some contrived signal models you can clearly construct such a map where you could prove things about the attackers ability to distinguish.
For most plausible signals like images-- you cannot make such assurances. -- if you could, stuff like lossy image compression would be a solved problem too. :)
I think that is okay: Having a framework that you can prove secure if some isolated sub-part is assumed secure would still be useful. Most cryptography (and essentially all practically useful cryptography) depends on making strong assumptions about some primitive.
We can't prove right now that we're not accidentally leaking our passwords to the world through our choice of words in these messages. Practically speaking, we're probably not.
Yes, exactly, perfectly secure steganography would be like a philosopher's stone of perfect compression for the underlying media. If you want to send something steganographically, you just encrypt it and then "decompress" the ciphertext into a cover message. The alternative--the channel oracle concept--is a non-starter for arguing real-world security because it assumes that one can efficiently draw repeated independent samples from some arbitrary "history" of the channel, which is like saying you can pause time and take as many photographs of a particular scene as you want, each with its own random observed quantum states, before deciding which picture to post to facebook.
The way around all this, of course, is to just communicate over an encrypted channel, which is exactly what Tor and other censorship circumvention systems do. But even then you have to rely on unprovable statements about the plausibility of the fact that you are using a secure channel under the given circumstances, or about the inevitable leakage from the particular implementation of the channel.
This is actually exactly my current line of research: building a better framework for separating the components of real-world steganographic systems into the parts which can be proven secure, and the parts which cannot. Your last statement does a surprisingly good job of capturing why arguing the security of steganography is so hard: information-theoretically, there is no way to prove that some observation in nature has zero mutual information with some other observation. The entire field of machine learning is devoted to finding signals in massive piles of seemingly meaningless noise, and any real instantiation of a stegosystem will inevitably make some noise that could, under the right circumstances, be detectable.
> Not going to lie I'm surprised anyone can figure out how to decrypt this in the current state of the program, well done! P.S. star my repo plz I'm trying to look employable! :)
Project wasn't building correctly to start with, UI is bit clunky (missing window frames!?).
This is different to the other stego programs out there in that it allows the user to choose how many LSB (Least significant bits) they want to use. This is important because if you use 4LSB an image can store more data but it is more obvious in the output, with 1LSB it is less obvious but you can store 1/4 as much data. My program also allows you to input text OR image into a cover image. If you are unfamiliar with steganography - I have tried to explain it simply on the github readme. ANY feedback on the program or the repo would be greatly appreciated!
I made one years ago (https://www.planet-source-code.com/vb/scripts/ShowCode.asp?t...). Had a quick look at your code and I could be mistaken, but it looks like you modify the pixels from top left to bottom right. You can make it harder to detect by selecting the pixels pseudorandomly, seeding your prng with the encryption key.
If the hidden data is encrypted anyways, then wouldn't it be indistinguishable from truely random data? What would then be the point of distributing it randomly or in order?
Actually, the thermal noise of a camera is biased so a uniform random distribution of low-order bits will be easy to detect. You need to preserve as much of the thermal noise as possible and try to choose pixels from high frequency regions of the image (where the thermal noise is harder to separate from the image itself).
So maybe the best approach would be to use a filter/transformation to exclude hard-lined regions (edges) and only embed data within variations/gradations?
Other way around: edges are a good place to try to hide stegotext because of the high frequency components (the edge effect, which is also why JPEG artifacts are worse along sharp edges).
If the cover image is a solid block of colour, you can detect the presence of the steganography by noting that the first N pixels vary slightly, and the rest are solid.
Similarly, if you have a clean reference of the source image, you could observe that the first N pixels are modified and the rest are not, and conclude that something is hidden in them.
If the pixels are selected at random, this analysis is less conclusive. Ideally you'd hide a random value in every pixel so that all pixels are manipulated equally.
Ah nice, I'll check it out! Yeah, at the minute they're from left to right but I've been doing some research into a graph-theoretic approach which looks pretty interesting.
Modern steganography does more than just use the LSBs of the image. For example, the watermarks used for SDMI (audio, not image data, but same logic applies) used techniques from communications systems like spread spectrum carriers (similar to what you might see with a digital radio system). For images you can also try to place the stegotext along edges and other high-frequency regions where there is more "noise" available to hide what you are doing. If you need to maintain secrecy, you can combine steganography with cryptography e.g. use a PRNG to select carrier frequencies (IANAL but you probably should beware of ITAR issues if you distribute such a thing).
You should also give thought to how robust you want the stegosystem to be to image filtering, downsampling, etc. The MPAA uses watermarks on movies to determine which theaters are the source of camrips, and those watermarks have to be as robust as possible (they must survive both the camera's inherent reduction in quality and possible transcoding/editing by the pirates). Not all stegosystems need to be robust, for example SDMI used one robust and one weak in an effort to identify downsampled copies of the audio (the RIAA assumed that downloaded music would always be significantly downsampled).
Do you have an algorithm that will work with recompressed lossy images?
I experimented with steganography before, but simply sending a picture via Facebook and clicking Save To Camera Roll on an iPhone causes serious data loss pretty quickly, so I couldn't get meaningful data out.
In the end I found that PDF attachments worked for my use case, but I'd still rather have an image-based steganography program if possible.
Or you can work in the frequency domain of the entire image instead of DCT blocks, which gives you a lot more room to work around various compression issues. I would also suggest that an error correcting code is helpful.
The essential idea with wet paper codes is that you can use error correcting codes so that even the recipient need not know which bits contain the data.
A simple analogy is that if you wanted to communicate only a single bit you could decide that the xor of all the data in the image decides the bit. Then the encoder can flip the single least distinguishable bit to encode their message.
The idea behind perturbed quantization is that when you quantize the data (e.g. while jpeg compressing it) some values will be maximally close to tied between rounding up and rounding down. If you embed your data in those values you'll minimize the embedding noise.
Unfortunately most of the work on approaches based on these ideas is academic and has no public implementation, but there is one that I'm aware of https://sourceforge.net/projects/pqstego/
There is a lot that could be done both with respect to security (e.g. using better models to predict the image to hide the stego noise better, better error correcting codes, and list decoding) and basic engineering, e.g. handling content length encoding better.
Steganography is the current focus of my PhD research, and from my perspective the greatest security challenges are in systems engineering. Embedding secret messages into your vacation photos is one thing, but who are you sending these messages to? And why? How will they know when and where to go looking for the secret message?
Encryption entered its golden age with the advent of public-key cryptography and Diffie-Hellman key exchange, allowing two parties to share the secrets required for secure communication knowing only public information about one another. However, steganographic systems are still dependent upon lots of out-of-band secret sharing, since attempting to share the necessary secrets over public channels tends to reveal the existence of the system and opens up DoS attacks (e.g. Tor and the identity of relays). IMHO, figuring out better solutions to the system security of particular steganographic applications is a much more pressing research problem than improving statistical embedding profiles for image steganography.
Then the recipient of the stego need only publish the public key. If the encoding software were part of standard linux distributions (even if just specialized security conscious distros), then the sender could obtain it without identifying themselves.
I don't think you can tackle the problems in isolation: There isn't much point in making uniform encryption if the embedding gives it away to anyone who's looking. :)
> but who are you sending these messages to?
One scheme I've been fond of is where the recipient announces their public key and that they'll accept messages in images posted to some moderately high traffic public picture board, like r/naturepics. Then then simply download and process all images submitted there.
The sender has an easy and obvious cover story for their posting and can produce as many images they need just by visiting a park with a camera.
A typical threat model is that there is a "warden" who can selectively block messages, so this would not really work since the warden would block the announcement (in theory the warden is not going to block all messages, although a formal security definition should only focus on whether or not the warden is more likely to block stegomessages than innocent messages, which is trivial if the warden blocks everything). Thus out of band communication is needed to distribute secrets; likewise, the stegosoftware itself has to be distributed out of band.
"indistinguishable from uniform"
Actually you need to be indistinguishable from the "background noise" (the thermal noise from the camera sensor) of the image, which is not uniform. In fact, the noise is correlated with the camera itself and can be used to identify which camera took a particular photo.
This is why public key cryptography is so important. Because you can use a broadcast channel -- like a Linux distro to communicate the tools and required knowledge in a way that doesn't give a strong signal that you're using it.
> "indistinguishable from uniform" Actually you need to be indistinguishable from the "background noise" (the thermal noise from the camera sensor) of the image
This isn't the case for code based encoding. The encoded values are a pseudorandom linear combination of a huge number of bits from the image and end up being extremely uniform. Consider my silly xor example: the xor of all the bits in the image is going to be close to uniform, even if the bits in the image are fairly biased.
But also more generally: If you have a way to map encrypted messages onto the space of uniform strings, then you can also remap from them onto any other required distribution in a fairly straight forward way.
Having a good error metric is important though, and it's one of the areas that seems a bit under researched.
That is not part of the threat model, and in any case is basically an out-of-band channel.
"like a Linux distro to communicate the tools and required knowledge in a way that doesn't give a strong signal that you're using it."
Again, the threat model is that the adversary controls the network and can block or modify messages at will. So unless all linux distros included the software, the adversary would simply block those that include the software. The threat model of steganography basically implies that some out of band distribution is needed.
"encoded values are a pseudorandom linear combination of a huge number of bits from the image and end up being extremely uniform"
That has nothing to do with what I was talking about. The "time domain" of the image is where the noise lies and where the bias exists in the bits. Even if it can be encoded in some way that looks uniform, that does not mean that an arbitrary change to the encoded image will have the correct bias when it is decoded.
"you can also remap from them onto any other required distribution in a fairly straight forward way."
In the forward direction, but the reverse direction is not so straightforward. This is a classic problem with doing ElGamal encryption on elliptic curves -- some curves do not have an easily invertable map from bit strings to the EC group. I do not know how hard this is to do with images, but when I last looked image stegosystems relied on heuristics and needed relatively short messages to remain secure.
It may not be the threat model you are interested in but it's part of the usage model of just about anyone capable of actually using a computer with arbitrary software, even in extremely restricted parts of the world. (users who can't run arbitrary software can't really be helped by steg stuff they can't use!)
Simplified threat models can be extremely helpful in formalizing security arguments, but taking them too and confusing them for actual usage can be devastating for the users security too.
> That has nothing to do with what I was talking about. The "time domain" of the image is where the noise lies and where the bias exists in the bits. Even if it can be encoded in some way that looks uniform, that does not mean that an arbitrary change to the encoded image will have the correct bias when it is decoded.
In fact it has everything to do with what you were talking about. One of the advantages of using wet paper codes is that you can arbitrarily preserve the properties of the underlying data while encoding uniformly random information. Even better: only the encoder needs to know about the properties that are being preserved, so it can use information which is unavailable to the attacker or the receiver such as an unquantized or higher resolution original. This is what the PQstego program I linked above does.
The encoder has significant freedom to preserve whatever properties it needs to preserve while encoding uniform data.
> but the reverse direction is not so straightforward. This is a classic problem with doing ElGamal encryption on elliptic curves
You would _very much_ not want to use ElGamal for this (or essentially any application which you didn't need its additive homomophism)-- doing so has terrible performance, terrible security properties, and terrible communications efficiency.
If you look back at my message I specifically brought up "elligator" for ECDH -- a bidirectional mapping between curve25519 points and bits. Similar approaches exist for many other curves.
This is true, but it begs the question: where does the “required distribution” come from? Most (all?) steganographic techniques make heuristic arguments about some plausible cover distribution but there is no provable security as with cryptography.
There are some theoretical results on how to make steganography provably secure, but they make use of objects (“channel oracles”) which cannot feasibly be instantiated in the real world except in a handful of unique cases.
Let me guess: You provide a set of weights along with the cover data, and so long as your weighed error is below some threshold it cannot be distinguished. For some contrived signal models you can clearly construct such a map where you could prove things about the attackers ability to distinguish.
For most plausible signals like images-- you cannot make such assurances. -- if you could, stuff like lossy image compression would be a solved problem too. :)
I think that is okay: Having a framework that you can prove secure if some isolated sub-part is assumed secure would still be useful. Most cryptography (and essentially all practically useful cryptography) depends on making strong assumptions about some primitive.
We can't prove right now that we're not accidentally leaking our passwords to the world through our choice of words in these messages. Practically speaking, we're probably not.
The way around all this, of course, is to just communicate over an encrypted channel, which is exactly what Tor and other censorship circumvention systems do. But even then you have to rely on unprovable statements about the plausibility of the fact that you are using a secure channel under the given circumstances, or about the inevitable leakage from the particular implementation of the channel.
This is actually exactly my current line of research: building a better framework for separating the components of real-world steganographic systems into the parts which can be proven secure, and the parts which cannot. Your last statement does a surprisingly good job of capturing why arguing the security of steganography is so hard: information-theoretically, there is no way to prove that some observation in nature has zero mutual information with some other observation. The entire field of machine learning is devoted to finding signals in massive piles of seemingly meaningless noise, and any real instantiation of a stegosystem will inevitably make some noise that could, under the right circumstances, be detectable.
> Not going to lie I'm surprised anyone can figure out how to decrypt this in the current state of the program, well done! P.S. star my repo plz I'm trying to look employable! :)
Project wasn't building correctly to start with, UI is bit clunky (missing window frames!?).
-J
Similarly, if you have a clean reference of the source image, you could observe that the first N pixels are modified and the rest are not, and conclude that something is hidden in them.
If the pixels are selected at random, this analysis is less conclusive. Ideally you'd hide a random value in every pixel so that all pixels are manipulated equally.
You should also give thought to how robust you want the stegosystem to be to image filtering, downsampling, etc. The MPAA uses watermarks on movies to determine which theaters are the source of camrips, and those watermarks have to be as robust as possible (they must survive both the camera's inherent reduction in quality and possible transcoding/editing by the pirates). Not all stegosystems need to be robust, for example SDMI used one robust and one weak in an effort to identify downsampled copies of the audio (the RIAA assumed that downloaded music would always be significantly downsampled).
I experimented with steganography before, but simply sending a picture via Facebook and clicking Save To Camera Roll on an iPhone causes serious data loss pretty quickly, so I couldn't get meaningful data out.
In the end I found that PDF attachments worked for my use case, but I'd still rather have an image-based steganography program if possible.
Discussed at the time: https://news.ycombinator.com/item?id=18342042