Perfect Steganography

Question

History contain many example of old steganography. We also have digital steganography.

Is there any kind of “Perfect Steganography”, in a sense that only the designer can extract the concealed message?

Update Is there a (formal?) definition of 'perfect steganographic hiding' where only the key-holder / designer can provably recover the data and if so are there any known constructions satisfying it?

Answer 1

"Perfect Steganography" is not well defined. Whatever that is, it must obey Kerckhoff's principle: adversaries know all about the system, except non-public keys. That's enough to exclude many steganography systems in actual use.

I'll use the following largely standard terminology:

• Payload is digital data one wants to transmit covertly; that's the question's "concealed message". Only its size is constrained.
• Carrier is the data in which a payload might be concealed.
• Channel is the vehicle by which said carrier is transmitted, and imposes a set of constraints on the carrier (like: being a bytestring of at most such size conforming to JPEG syntax, though perhaps with stricter constraints on padding and comment fields)
• Original (if any) is data from which the carrier is prepared, with a set of constraints of its own (like, being the output of a consumer digital camera) and prescribed relation with the carrier (typically, a rendition of the carrier for human perception must be perceived as one for the original; or at least as a reduced-quality version of the original).

A steganography system must allow a sender holding a key (perhaps, public) and possibly a payload to construct a carrier; and a receiver with a key (same symmetric key, or private key matching public key) to determine if there was a payload in that carrier, and in the affirmative recover the payload.

An adversary's goal is to distinguish if a carrier carries a payload or not (better than random). The receiver must be extra careful not to leak that info, and that's hard, especially against active adversaries. We can assume that the adversary has the choice of payload within size constraints, much like modern cryptography assumes chosen plaintext.
_{Note: the question's goal "extract the concealed message" could mean that an adversary tries to reduce the size of the carrier while keeping the possibility to recover the payload when latter given the key, but that is not a usual goal, and I won't consider it further.}

Payload confidentiality follows from security under chosen payload (argument: if the payload was intelligible, comparison with chosen payload would yield a distinguisher). It would anyway be trivial to add payload encryption on top of steganography if chosen payload was not assumed.

Often, extra properties are required:

1. The original must be a valid carrier per the channel constraints.
2. The security goal is met even if the adversary get holds of the original from which the carrier was prepared.
3. When there's no payload in a carrier, the carrier must exactly match the original.
4. The process by which an original is transformed into a carrier when no payload is embedded is constrained (e.g. is a certain pre-existing program).

Property 3 implies 1, and is incompatible with 2. There is overlap between channel constraints and constraints in 4.

Note: I've left aside watermarking, even though there is overlap with steganography.

---

The possibility (or not) of making a demonstrably secure steganography system depends heavily on the constraints set: on channel, original, payload size, and extra properties. There are many combinations of constraints depending on use case. Channel and original constraints vary immensely. Payload size can range from the text GO to terabytes.

The simplest demonstrably secure steganography system are those where constraints allow to embed a little more uniformly random bits in a carrier than the payload length (after compression). We can set these bits of the carrier either to true randomness (for no payload), or to the ciphertext of some authenticated encryption of the payload having the property that ciphertext is indistinguishable from random (which is easy and common). The receiver extracts the bits, perform the decryption/integrity check, concludes there's no payload if the integrity check fails, and otherwise has recovered the payload.

Such system must match whatever reasonable definition of perfect steganography is chosen (if a reusable key is not required, we can even use an information-theoretic MAC and replace encryption by a One-Time-Pad, to become information-theoretically secure regardless of the adversary's computing power).

Here is an example with properties 2 and 4, where original is any JPEG file, and channel is a PDF file with a PAdES digital signature made using 4096-bit RSA per RSASSA-PSS with SHA-512. I posit existence of a program that transforms JPEG files into signed PDF with said signature that uses a CSPRNG at step 4 of EMSA-PSS-ENCODE, reading:

Generate a random octet string salt of length sLen

In the context, sLen is 4096-64-512 = 3520 bits, which can legitimately be random per the channel's constraints and property 4. That is enough for a 64-bit MAC per HMAC-SHA-256, a 64-bit IV for the most significant bits of a counter for AES-256-CTR, and 424 bytes of payload (over 1k byte of compressed text), used instead of the random octet string when there is a payload.

---

When the channel allows no bit that can be arbitrary random, it becomes much more difficult to make a demonstrably secure steganography system. In particular, with property 3, it becomes critical that the adversary can't have a better model of the original than the system assumes.

Answer 2

Is there a (formal?) definition of 'perfect steganographic hiding' where only the key-holder / designer can provably recover the data and if so are there any known constructions satisfying it?

Is it acceptable to post a link here to my own work? If not, then please feel free to delete this answer.

I believe that perfect steganography may be approachable and have an example implementation (MacOS only at present I am afraid). 'Perfect Steganography' post on my blog.

I think that the way the payload is woven into the jpeg makes it virtually impossible to detect the presence of the payload, but I am not sure how this could be made 'provable'.

In response to calls for proof, I have provided three images, one with no payload, one with a short message ("hello World"), and one with the first sentence of 'Lorem Ipsum'

http://vanleersum.uk/downloads/images/Drawing1.jpg http://vanleersum.uk/downloads/images/Drawing2.jpg http://vanleersum.uk/downloads/images/Drawing3.jpg

You will need my app to read the payload.... but maybe you can tell me which is which. I did need to run the 'untouched' image through my app as the optimisation in the tool is more aggressive. The original image was 240kB, but after running though my tool it was 188kB for all three. If this is unfair, then I will post the original too.....

In answer to the 'lack of detail' comment. What I am doing is subtly modifying the DCT data in a manner consistent with JPG standards and expectations, but doing so in a way that provides a signal to my tool. This signal is mapped to a byte array that carries the encrypted payload. Nothing in the way the DCT data is presented is unexpected - any compliant jpeg codec will read the image just fine. The image will have small deviations from the original, but these deviations will be equivalent to those experienced by using different implementations of DiscreteCosineTransform or different quantisation tables or different quality setting. All of which could occur from platform to platform or implementation to implementation. For reference, I am using jpeg-9c as my base code, and tinyAES for my crypto.