Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?
share|improve this question
1  
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 at 13:48
1  
@Thomas, There is a probability that PRNG of the carrier is not cryptographically secure. –  Moonwalker Feb 25 at 13:54
    
@Thomas so cryptographically secure PRNG are indistinguishable for third party observer? –  Moonwalker Feb 25 at 13:57
3  
@Moonwalker: well, yes, that's actually pretty much the definition for "cryptographically secure PRNG" –  poncho Feb 25 at 14:00
1  
@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 at 14:24
show 6 more comments

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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 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. –  dionadar Feb 25 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 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. –  dionadar Feb 25 at 23:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.