Protocols for data hiding in pseudo-random state

An emerging form of steganographic communication uses ciphertext to replace the output of a random or strong pseudo-random number generator. PRNG-driven media, for example computer animated backdrops in video-conferencing channels, can then be used as a covert channel, if the PRNG bits that generated a piece of content can be estimated by the recipient. However, all bits sent over such a channel must be computationally indistinguishable from i.i.d. coin flips. Ciphertext messages and even key exchange datagrams are easily shaped to match this distribution; however, when placing these messages into a continous stream of PRNG bits, the sender is unable to provide synchronization markers, metadata, or error correction to ensure the message's location and proper decoding. In this paper we explore methods for message transmission and steganographic key exchange in such a "coin flip" channel. We establish that key exchange is generally not possible in this channel if an adversary possesses even a modest noise budget. If the warden is not vigilant in adding noise, however, communication is very simple.