How to establish if a string contains a message

Question

If you have a string S, then the string can be composed of four things:

1. cleartext
2. 'random' data
3. encrypted data
4. compressed or otherwise non-encrypted, but modified, cleartext

If you want to see if the string is an encrypted message, (3), then you might construct a test for 'randomness', say the test is $T_0$. You'd then expect:

• $T_0(a) \approx T_0(d)$ -- i.e. not interpreting a compression as an encryption because it is ordered
• $T_0(b)$ $\not \approx$ $T_0(c)$ -- i.e. the message is detected

If the message is very well encrypted, then you'd expect:

• $T_0(b) = T_0(c)$ -- that is, the algorithm detects no patterns

Would that be correct?

I'd expect that a watermarked or steganographic image would be revealed as different from standard jpegs by a good $T_0$.

The randomness tests in 'diehard' and 'dieharder' look for specific types of pattern that would not be expected in strings of type (2). Would it not make more sense to structure a $T_0$ on known types of data, so, for example, an apparently normal image file that contained a message would stand out?

Answer 1

It will depend entirely on the specific encryption scheme. There is really no theoretical reason why a ciphertext should not be clearly identifiable as being a ciphertext and not a plaintext. In fact, take any encryption scheme and modify it so that the encryption algorithm works as before, only it appends to the ciphertext the string "THIS IS A CIPHERTEXT!", and modify the decryption algorithm to work as before only ignoring this string. For pretty much any reasonable encryption scheme this modified scheme will be (theoretically speaking) as secure as the original scheme.

Why is this? Because, when we evaluate the security of a scheme we assume that the adversary (i.e., the entity trying to break the scheme) knows what scheme he/she is breaking and is explicitly told what pieces of information are ciphertexts.