I've come up with an approach to steganography which needs review of both its cryptography and its math. There's a complete working implementation at https://github.com/bramcohen/DissidentX and the explanation below is taken from the documentation files, which contain much more detail, but this covers the core idea.
This scheme is divided into three layers, which go together like this:
encode(pack(encrypt()))
The most novel part is the encode layer. It takes a key, plaintext with possible alternates, and value to encode. Intuitively, if the key and plaintext are used as the keys to a stream cipher, then it will probably be possible to make the output of that stream cipher begin with a desired value if the number of alternates is more than the number of bits in the value. Unfortunately that would require time exponential on the number of bits to find the encoding. This scheme uses a very specifically designed stream cipher which makes it possible to compute which alternates to use to get the desired value in a polynomial amount of time. Specifically, it uses each contiguous section of sixteen bytes for a stream cipher (AES in OFB mode) and xors the outputs together, and makes sure that alternates have at least fifteen fixed bytes between them. The result is that flipping an alternate always xors the output by a specific value, independently from flipping other alternates, so it's possible to calculate which alternates are needed by row reduction.
There's lots more details in the documentation, not inlined here due to sheer volume.
The specific use case this is intended for is as follows. My question is, is it possible to attack this protocol under these circumstances, either by making fake messages, or by reading messages an attacker doesn't have the key to?
The primary use case for DissidentX is encoding messages in files on the web. There should be a utility which scans all objects the user's web browser downloads (html files, images, css files, etc.) for messages using all of the keys the user has entered. Someone sending messages to that person provides a web service where users who have widely viewed web sites can upload their files and get back slightly modified version with messages steganographically added. The web users should not be able to read what the messages are, and it should be possible for the service doing the encoding to not have to keep messages in plaintext.