Creation of a stego object by embedding information in a cover object often distorts the cover object. As more information is embedded, more annoying noise is introduced in stego objects. Although reversible embedding methods enable us to restore the original cover object even after embedding, stego objects are not free from distortions. Embedding information does not, however, always result in damaging the contents of the cover object. This chapter introduces data embedding methods that are not based on modification of the contents of cover objects: permutation steganography, metadata steganography, and cover generation methods. This chapter focuses on elaborating the basic principles of these techniques.
TopPermutation Steganography
This section is devoted to the description of permutation steganography. Permutation steganography is an effective method for hiding messages provided that the contents of cover objects are not affected by the rearrangement of their elements. Even if rearrangement of the elements does affect the content, permutation steganography is useful if the original content can be restored by adjusting the cover object after rearrangement. Example of cover objects that can be used for permutation steganography include indexed color (palette) images (Kwan, 1998), polygonal meshes (Bogomjakov, Gotsman, & Isenburg, 2008), and HTML files (Huang, Zhong, & Sun, 2008).
In an indexed color image, color data are stored in a color map. Each color is associated with its index number in the color map, and the pixel data are specified by these color indices. The colors in the color map can be shuffled and the image appearance can be preserved if the pixel data are changed accordingly. A polygonal mesh is a geometric data set consisting of vertices and faces, both of which are indexed by numbers. The indices of vertices and faces are just arbitrary. We can change indices of vertices and faces while preserving the shape they represent. In HTML files, start-tags and empty-element tags can have attributes. The order of attribute specifications is insignificant. We can freely arrange attributes without affecting the result of rendering. These examples show that there are cover objects that can be described in more than one way while preserving their appearances completely. Permutation steganography exploits this kind of redundancy.