# Detecting steganography in the stream of short messages

I have stream of millions of short n-bit (n<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:

1. Can I identify those messages injected if PRNG of the source (algorithm) in given to me?
2. Can I choose or modify PRNG in such way to allow injected messages to be identified?
3. Can third party identify the PRNG of the stream being modified in such way to allow for easy detection of non-source originating messages?
-
If both the carrier (main stream of bits) and the encryption covering the "steganography" are cryptographically secure, I'm pretty sure you have no way to detect the existence of those messages. In general what happens here is the warden either blocks or corrupts the channel, since the supposed existence of a hidden encrypted stream is impossible to prove or disprove from the data alone. Could you be more specific about the scenario you are describing, because it seems to me that a generic answer won't be very fulfilling? – Thomas Feb 25 '14 at 13:48
@Thomas, There is a probability that PRNG of the carrier is not cryptographically secure. – Moonwalker Feb 25 '14 at 13:54
@Thomas so cryptographically secure PRNG are indistinguishable for third party observer? – Moonwalker Feb 25 '14 at 13:57
@Moonwalker: well, yes, that's actually pretty much the definition for "cryptographically secure PRNG" – poncho Feb 25 '14 at 14:00
@Moonwalker: that question is both broad and tough; there's no really good way, even if you had access to the RNG design, which you don't. About the best you can do against an unknown generator is run a bunch of statistical tests on the output, and see if you see something unexpected. – poncho Feb 25 '14 at 14:24

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:

1. 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.

2. 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.

3. 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).

-
About 3 question. Can third party detect messages of original stream being MACed? Sorry for possibly silly question, but I didn't get it from reading wiki. – Moonwalker Feb 25 '14 at 20:06
Maybe I misunderstood your third question - a MAC ensures that no one but trusted parties can send a message. If the adversary therefore adds a MAC to their hidden messages, modification of the hidden message is detectable. – gha.st Feb 25 '14 at 21:33
Sorry for not being clear. In my scenario the length of output of the source is fixed so it is either PRNG output or less long PRNG output with MAC somehow added to it. The length of output is equal to n bits in both cases. In this scenario can a third party distinguish stream of messages generated by PRNG from stream of messages generated by PRNG with somehow added MAC? – Moonwalker Feb 25 '14 at 23:23
That question is to open to answer. It depends on many things: How secure is your PRNG? How many simple streams do you have? And finally, what is your MAC algorithm? Using a secure PRNG and HMAC with a secure keyed hash function would make it impossible. – gha.st Feb 25 '14 at 23:29