"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:
- The original must be a valid carrier per the channel constraints.
- The security goal is met even if the adversary get holds of the original from which the carrier was prepared.
- When there's no payload in a carrier, the carrier must exactly match the original.
- 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.