I have a photo with a resolution of $1024 \times 768$ which means $786432$ pixels in total. Let's suppose it's a 24-bit color RGB image (so 1 pixel = 3 bytes = 24 bits) and I want to hide information by only modifying the last bit of a color value. What is the maximum number of bytes that I can hide in this photo?
This is one of those answers that - depends.
The amount of data that can be hidden inside an image depends on the image. This is one of the concepts that most steganographers miss. We have to go to the definition of steganography. Hiding a secret message with emphasis on the hiding part. That means that a message may or may not be contained within the pixels of an image, creating plausible deniability. If you overtly don't bother to hide it, you might as well traditionally encrypt the message with AES, append it to an email and add "Secret message attached" to the subject heading.
It is also a requirement that the message is compressed /encrypted or generally whitened. Whist encryption is not absolutely necessary for steganography to be successful, the message has to be converted to almost randomly distributed bits. Any uncompressed /unencypted pattern can be easily discovered via heuristic or frequency analysis of the image. After all, image noise is almost uniformly random. If compression is used, the amount of data is becomes contingent on it's type and therefore it depends.
From a capacity and mathematical deniability perspective, the following type of image is optimum:-
It's just random noise in all three colour channels. If the least significant bit contained the compressed message, and the message was textual, you might expect 9 Mbits of capacity£. You may have issues of plausible deniability though if you're sending many of these images without a really good excuse. And they'd have to be in the form of a lossless format, which again is uncommon. Tools like OpenPuff can use lossy formats but that then reduces the message capacity.
Here the whole mountain side is blown out. Image analysis would easily identify manipulation of the least significant bits of the mountainside as they're all meant to be exactly 255,255,255. Almost half of the image can't be used. The steganographic tool would have to determine this. An image with deep shade presents the same problem featuring an expected RGB of 0,0,0 for that part of the image. So again the message size depends.
So you're left with using images like:-
In this instance you might get 9-18 Mbits of text$, but you're reduced to sending grainy images all the time for this message capacity. The sensor noise will mask the whitened message, especially if you use less than 1 bit per channel per pixel. And they have to be lossless formats like BMP /JPEG2000 /TIFF or PNG. None of these are particularly common in the social Facebook world, compromising the plausible deniability argument. A lossy format will reduce the message size again.
Algebraically, you can form an equation like:-
capacity = (usable %age) X (encoded bits) x (no.pixels)
which represents the difficult relationship of:-
capacity = F(artistic composition, SNR, image size)
In summary, the message size is very difficult to quantify without a detailed analysis of your photo. Why don't you post it? The most important take away here is that the issue with steganography is not encrypting a message in an image, but being able to deny that there is one in the first place. This is similar to the deniability issues with disc encryption software like TrueCrypt.
£ I'm assuming that a large sample of English prose can be compressed to 2 bits /byte. Capacity = 1024*768*3*4 =~ 9e6 bits where 4 is the compression ratio.
$ In an image this noisy (low SNR), it might be possible to utilise 2 bits per image byte for the message. Or even more?
With any image, how much change in a pixel can happen, before you notice a change? For a computer, even if only one bit in a thousand changes, it can notice... as long as it has the original image to compare against. But for stenography, you could use a picture you just took and destroy the original as soon as you used it to hide the data.
For a human... a 24 bit image has a possible about 16M colors. The human eye is said to be able to distinguish 10M colors. If you take a bit out of every byte, at the least significant bit position, or 3 bits out of every 24 bit pixel, you reduce the color availability, down to just north of 2M colors (2^21). You can see that in the image below. It shows a background with rectangles where I have modified 1, 2, 3, 4, and 5 bits. Anything more than 1 or 2 bits and it gets noticeable. Take into account that this is larger swatches, noticing discrepancies at the pixel level would be harder for the human eye. And also take into account that here you have a base comparison, the background. In a pixel by pixel change, and without the original image, there would not be that clear baseline for the eye to catch on. A change of 1 or 2 bits, in the least significant bits, would be hard to detect.
But let's play it safe and only take one out of every 8 bits, and being smart, we take the least significant bit out of every color in every pixel. That means we have one eight of the original 786432(pixels) * 3 bytes (24 bit per pixel) available to us = 294k. Compress the message you want to hide in the picture, then encrypt it (compress first!). Stick it in that 294k. You are golden.
Short answer... 294k compressed, easy, and forget detection... compression alone randomizes the data you are sending; encryption further randomizes your compressed data. Random bits in the least significant color bits of each pixel... how can you tell from noise?