Detecting steganography in the stream of short messages I have stream of millions of short n-bit (n&lt;30) messages generated by some random number generator. The source of random number generator is not available to me.

I suspect there are messages used to convey information generated by some third parties and injected into the stream. I what to test the hypothesis of such messages existing.  

As far as I understand, the injecting of such messages would lead to the existence of at least two different sources of randomness: the one from original random number generator and the rest from encryption algorithms used by third parties. So testing my hypothesis is equivalent to detecting those modes.

My knowledge of random number generation is very limited and I would appreciate all kind of hints, pointers, ideas and references to the relevant literature. 

Adding twist on this question. 
Suppose I control the PNRG of the source (source sending only random messages without payload). Third party wants to hide their messages in my stream. 

The new questions:


Can I identify those messages injected if PRNG of the source (algorithm) in given to me?
Can I choose or modify PRNG in such way to allow injected messages to be identified?
Can third party identify the PRNG of the stream being modified in such way to allow for easy detection of non-source originating messages?
Proof of security:

Let $(x_1, ..., x_n)$ be the messages you caught.

Let $(p_1, ...)$ and $(q_1, ...)$ be three streams of random messages known to both communication partners. Let these be from a true random number source generating non-autocorrelated data.

Let $(n_1, ...)$ be another stream of data from the same source.

Since there is no correlation, it is impossible to distinguish $p_k$ from $q_k$ or $n_l$ without knowing the actual data stream.

To communicate, now pick $p_k$ if bit k of your message is $0$ and $q_k$ if it is one. If you do not wish to communicate simply send $n_k$.

Note: This all depends on a true RNG. When utilizing a PRNG, this is possible, however there exist security proofs http://en.wikipedia.org/wiki/Blum_Blum_Shub that have a security guarantee that makes this at least as hard as integer factorization.

For your twists, it really becomes a question of how much information you and the attackers have:


No. Again, Cryptographically secure RNGs are indistinguishable from true RNGs with reasonable computation power (otherwise they would not be secure...) and therefore, without knowing more about its seed, any sequence of messages is a legitimate output. Even slight shortcomings can be circumvented by utilizing an injection method like the above that uses another (differently seeded) PRNG of the same type.
Sure. Just break it. If you restrict the number of possible messages to 1, injection is only possible through side channels (e.g. the number of messages, their arrival timing, etc). Whether you can detect these depends on your exact setup.
At this point, it is not even about PRNGs anymore. If your adversary just added a MAC http://en.wikipedia.org/wiki/Message_authentication_code to their messages, they can detect your attempts at forging. (Note that this is only very losely related to question 2).