3
$\begingroup$

I am not thinking only steganography in images, I think it is also possible to encode data for example into the length of spaces of a clear html text.

I suspect, the steganography changes (elevates) the entropy of the non-significant part of the messages.

But:

  1. How to detect in the general case, what is "non-significant"?
  2. Sometimes the hidden content has also a low entropy, while "clean" content can have also high.

For (1): Afaik, it is impossible, the only possibility would be to use some application-level decoding and interpretation.

For (2): I think, there is (should be) some type of correlation between the entropy (complexity) of non-significant part and the significant part of the carrier content, too. Some type of uncommon deviation could be maybe detected.

Does such technique, algorithm already exist?

$\endgroup$
  • $\begingroup$ I don't think what you are asking is possible in general. A good steganographic algorithm could make the hidden content have similar entropy as the "empty" non-significant content, simply by compressing and/or expanding the stored data. $\endgroup$ – otus Sep 12 '15 at 18:42
  • $\begingroup$ @otus 1) That is right, but some other parameters could be maybe also examined in this case. 2) Even if the problem can't be solved perfectly, some type of "theoretical optimum" could exist with a partial solution. $\endgroup$ – peterh Sep 12 '15 at 19:33
  • $\begingroup$ I have another idea: somehow to measure correlations between the significant and non-significant parts of the message. $\endgroup$ – peterh Sep 16 '15 at 3:23
0
$\begingroup$

You cannot detect the use of steganography without taking into account the inherent variation in the protocol. Of course, you should be able to detect bad steganographic practices that operate outside the normal limits - you don't expect huge swaths of whitespace in HTML - but well applied steganography should be hard to detect by definition. So I agree with your evaluation of (1).


Entropy is not complexity. Pi may be considered complex if you try to estimate the value of subsequent digits (in whatever base) without using the common methods to calculate Pi. A common X.509 certificate is rather complex, but only the modulus (of the public key within the certificate) and signature may contain entropy.

Furthermore, I don't see how complexity of the significant part and non-significant part are necessarily related in any way. Take the certificate: you can easily re-encode it using XML encoding rules. Now generally a converter doesn't add any whitespace. However, a simple XHTML file may contain a lot of whitespace placed almost randomly between tags as it may be human generated.

As there doesn't necessarily seem to be a correlation, it would be impossible to create a generic algorithm that could detect steganography. Of course, heuristics can be used, but given that the amount of variation is unknown it advance, there must be either false positives, false negatives or both given any protocol that allows variation and any steganographic practice.

So I don't agree with your assessment of (2), and in my opinion, no generic algorithm should be possible to exist. Proof: take a protocol that randomly adds a space or tab character, ignored by the receiving party. Replace these by a CPA secure ciphertext, bit by bit. Now both the original data and space/tab encoded ciphertext should be completely random to an adversary.

$\endgroup$
  • $\begingroup$ Re. "Entropy is not complexity". The quintessential definition of entropy is complexity for the bulk of science. The entire 2nd law revolves around that and even shares a similar formula measuring it. It also underpins the basis of compressibility theory which is recognised by NIST in multiple randomness tests. One day, we're going to have to sort this out and come up with a correct definition, perhaps using Kolmogorov/algorithmic complexity. It cannot be right that $H(\pi)$ changes depending on a priori /posteriori knowledge. There shouldn't be an epistemological distinction. $\endgroup$ – Paul Uszak Jul 21 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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