Security levels in steganography – Insecurity does not imply detectability

This paper takes a fresh look at security notions for steganography – the art of encoding secret messages into unsuspicious covertexts such that an adversary cannot distinguish the resulting stegotexts from original covertexts. However, stegosystems that fulfil the security notion used so far are quite inefficient. The current setting is not able to quantify the power of the adversary and thus leads to extremely high requirements. We will show that there exist stegosystems that are not secure with respect to the measure insecurity considered so far. However, it is totally unclear how they could be successfully attacked when used in practice. This indicates that a different notion of security is needed which we call detectability. We propose different variants of (un)-detectability and discuss their appropriateness by constructing concrete examples of stegosystems and covertext distributions. As main technical contribution we design a framework for steganography that exploits the difficulty to get detailed information about the covertext distribution. This way, for the first time a tight analytical relationship between the task of discovering the use of stegosystems and the task of differentiating between possible covertext distributions is obtained.