A square-root law for active wardens

The Square Root Law of Ker, Filler and Fridrich establishes asymptotic capacity limits for steganographic communication, caused by the watchful eye of a passive warden. We exhibit a separate fundamental limit of steganographic communication caused by a second phenomenon, the noise inflicted by an active warden. When a steganographic channel is not protected by a secret key, for example when it is used for key exchange, the number of errors needed to derail the channel grows no faster than the square root of the cover length. This means that contrary to intuition, embedding a message across a larger cover makes transmission less robust. This result is so pessimistic that it applies even to the transmission of a single datagram, a message of constant length, within a cover stream of arbitrary size. It is also true if the warden is forced by channel constraints to inflict noise randomly instead of surgically. While this law does not apply when the sender and receiver share a key in advance, ultimately this result implies that an active warden can indefinitely postpone the initial handshake of steganographic communication with a vanishingly small error rate. It also causes us to question whether the notion of a supraliminal channel is physically realizable, as even very highly robust communications channels become increasingly vulnerable for larger covers.