Informatica 33 (2009) 41-48 41 Steganography Combining Data Decomposition Mechanism and Stego-coding Method Xinpeng Zhang, Shuozhong Wang and Weiming Zhang School of Communication and Information Engineering, Shanghai University, China E-mail: {xzhang,shuowang,weimingzhang}@shu.edu.cn Keywords: steganography, data decomposition, embedding efficiency Received: September 1, 2008 A novel steganographic scheme based on data decomposition and stego-coding mechanisms is proposed. In this scheme, a secret message is represented as a sequence of digits in a notational system with a prime base. Each digit block is decomposed into a number of shares. By using stego-coding technique, these shares are then embedded in different cover images respectively. In each cover, a share is carried by a group of cover pixels and, at most, only one pixel in the group is increased or decreased by a small magnitude. That implies a high embedding efficiency, and therefore distortion introduced to the covers is low, leading to enhanced imperceptibility of the secret message. A further advantage of the scheme is that, even a part of stego-images are lost during transmission, the receiver can still extract embedded messages from the surviving covers. Povzetek: Predstavljena je nova steganografska metoda. 1 Introduction Steganography is a branch of information hiding that aims to send secret messages under the cover of a carrier signal. While many steganographic methods have been proposed for various types of cover media in recent years, techniques of steganalysis have also rapidly developed to detect the presence of secret messages based on statistical abnormality caused by data hiding [1, 2]. Generally speaking, the more the embedded data, the more vulnerable the system will be to the steganalytic attempts. When a multimedia product is under suspicion, the channel warden may refuse to transmit it, and the source of the message can be tracked. As a countermeasure, the data-hider always tries to improve statistical imperceptibility of the hidden message. An important technique to improve imperceptibility is to reduce the amount of alterations to be introduced into the cover for hiding the same quantity of data, in other words, to improve embedding efficiency. For example, Matrix encoding uses less than one change of the least significant bit (LSB) in average to embed l bits into 2l-1 pixels [3]. In this way, distortion is significantly lowered compared to a plain LSB technique in which secret bits simply replace the LSB. Further, some effective encoding methods derived from the cyclic coding have been described [4], and the matrix encoding can be viewed as a special case. In [5], two methods based on random linear codes and simplex codes are developed for large payloads. Another method, termed running coding, can also be performed on a data stream derived from the host in a dynamically running manner [6]. All the above-mentioned stego-coding techniques are independent of any particular cover-bit-modification approaches. For example, if a stego-coding method is used in the LSB plane of an image, adding 1 to a pixel is equivalent to subtracting 1 from the pixel to flip its LSB for carrying the secret message. In addition, we [7] and Fridrich et al. [8] independently presented a same method with better performance, termed respectively exploiting modification direction (EMD) and grid coloring (GC for short). Using this method, log2(2g+1) secret bits are embedded into q cover pixels and, at most, only one pixel is increased or decreased by 1. In [8], a data-hiding approach incorporating GC with Hamming-derived steganographic encoding technique is also studied, which in fact is a special case of GC. We also applied the wet paper codes to steganography to further increase embedding efficiency [9, 10 11]. Since stego-covers may be lost due to an active warden or poor channel conditions, a steganographic system capable of resisting interference is also desired to the data-hider. This paper proposes a novel steganographic scheme by introducing a data decomposition mechanism together with stego-coding techniques, such as running coding and EMD embedding methods. In this way, the secret message is inserted into a number of cover images with high embedding efficiency. Even a part of stego-images are missing, one can still extract the hidden message from the remaining covers. The rest of this paper is organized as follows. Section 2 introduces the related stego-coding methods. The proposed scheme is described in Section 3 and 4. Then, the experimental results are shown in Section 5. Finally, we conclude in Section 6. 42 Informatica 33 (2009) 41-48 X. Zhang et al. 2 Related Stego-coding methods In stego-coding methods, a number of patterns of cover data are used to represent a type of secret data, and the data-hider modifies the original cover data to the nearest pattern mapping the secret data to be hidden. This way, by changing a small part of cover data, a fairly large amount of secret data can be embedded. In this section, we briefly review the related techniques including running coding and EMD embedding methods. 2.1 Running coding With running coding method [6], each secret bit is represented by a series of consecutive cover bits, and each available cover bit also relates to several consecutive secret bits. In other words, the secret message is embedded as a data stream, and each coverbit-alteration is used to embed several consecutive secret bits. Assume that the secret message to be hidden contains Kbits: [x1, x2, ..., xK], and the available LSB for carrying the secret message are [bu, b12, ..., b1jT; b21, b2,2, ..., b2j; ...; bK>1, bK2, ..., bKT], where Tis an integer power of 2 (T = 2'). A binary generating matrix G sized (t+1) x T is first constructed. Denote the elements in G as g(i, j), where 1 < i < t+1 and 1 < j < T. Assign all the elements in the first row as '1' and make all the 2' columns in G mutually different. For example, the generating matrix of the 4th running coding is 3. If the bit is '1', define this '1' together with the following ' bits as a sub-vector with a length (t+1). Obviously, the sub-vector in this case must be identical to one of the columns in G. That means Z is segmented into a sequence of sub-vectors, each being either a column of the generating matrix G or a single zero. According to (2), flipping the value of host bit bvj will change the value of yv+i-1 if g(i, j) = 1 (1 < i < '+1, 1 < j < T). Thus, we can modify only one host bit to change the values of several yvs. Assume that a sub-vector [zv, zv+1, ..., zv+t]T is same as the j-th column of G. By flipping the value of host bit bvj, the data-hider may make [y'v, y'v+1, ..., y'v+t] identical to [xv, xv+l, xv+iL where [y'v, y'v+1, ..., yWI are obtained from the modified host bits according to (2). This way, the secret data can be embedding using a small number of bit-alterations. 2.2 EMD embedding EMD embedding [7] is an alternative method for inserting secret data into a certain cover image with a high embedding efficiency. Using this method, each symbol in notational system with an odd base will be carried by a group of pixels, and, at most, only one pixel is increased or decreased by 1. Denote a secret symbol in notational system with an odd base (2q+1) as 5, and the gray values of pixels in a group as g1, g2, ..., gq. Calculate the extraction functionf as a weighted sum modulus (2q+1) "1 1 1 1" G = 0 0 1 1 (1) 0 1 0 1 [0, if xv = yv 11, if xv * yv (3) Orderly arrange all zvs to form a vector Z = [z1, z2, ..., zK]T, and divide Z into a set of sub-vectors in the following way: 1. Scan the vector Z from the beginning to the end; 2. If the encountered bit is '0', define this '0' as a sub-vector containing only one element; f (g1, g2,..., gq)=£(g1 • i)mod (2q +1) (4) According to the original host data and the generating matrix G, calculate '+1 T r , yv =ZZ[g(i,j)"bv-i+1,j] mod 2, i=1 j=1 (2) v = 1, 2,..., K where bv-i+1j- = 0 if v-i+1 < 0. The data-hider can use a small number of alterations in these host bits to make the values of yvs equal to the secret bits xvs. Let Consider the vector [g1, g2, ..., gq] as a hyper-cube in q-dimensional space. The extraction function must have the following two properties: 1) values of the extraction function on all hyper-cubes fall in the interval [0 2q], and 2) the values of f on any hyper-cube and its 2q neighbors are mutually different. This implies that a symbol in the (2q+1)-ary notational system can be carried by a pixel-group, and, at most, only one pixel will be increased or decreased by 1. If the symbol 5 equals the extraction function of the original corresponding pixel-group, no modification is needed. When 5 ^ f, calculate u = 5 - f mod p. If u is no more than q, increase the value of gu by 1, otherwise, decrease the value of gp-u by 1. For example, considering an original pixel-group [137 139 141 140] with q = 4, f = 3 and a corresponding symbol 4 in 9-ary notational system, a data-hider can calculate u = 1, so he can increase the gray value of the first pixel by 1 to produce the stego-pixels [138 139 141 140]. If the symbol to be hidden is 0, u = 8 can be calculated and the gray value of the forth pixel will be decrease by 1 to yield [137 139 141 139]. 3 Data embedding procedure In this proposed scheme, a secret message is firstly represented as a series of shares according to a data i=1 zv = STEGANOGRAPHY COMBINING DATA. Informatica 33 (2009) 41-48 43 decomposition mechanism and various indices, and the shares corresponding to different indices are respectively inserted into different cover images. Then, a generalized running coding or EMD method is employed to keep stego-induced distortion at a low level, and redundancy in the shares ensures that one can recover the original secret message from a part of stego-covers. 3.1 Data decomposition At the beginning, a data-hider converts a secret message into a digit sequence in a notational system with an odd and prime base p, such as 3, 5, 7, 11, etc. If the secret message is a binary stream, it can be segmented into many pieces, each having L1 bits, and the decimal value of each secret piece is represented by L2 digits in a p-ary notational system, where L = [¿2 ■ log 2 p J (5) ^R = 1 - Li 1 L2 ■ l0§2 P L1 + 1 (6) J=k,i dk,2 - dkm ]■A (7) where m < n < p, A = 1 1 1 1 a1 a2 a3 - an 2 2 2 2 a1 a2 a3 an a an a a„ (8) "1 1 1 1" A= 2 4 0 1 (9) 4 1 0 1 For example, the binary message (1001 1101 0110) can be rewritten as (14 23 11) in 5-ary notational system when Li = 4 and L2 = 2. Thus, the rate of redundancy in the digit sequence With large L1 and L2, Rr is very close to 0, therefore can be ignored. So, the secret message is regarded as a digit sequence in p-ary notational system in the following discussion. Then, the data-hider segments the secret digit sequence into a series of blocks, each of which contains m digits. Denote the number of blocks as K, and the block as (dk>1, dk,2, • ••, dk,m} (k = 1, 2, ..., K). Inspired by [12], decompose each secret block into n shares, (sk>1, sk,2, ..., skn}, in the following way, and the symbol "•" in (7) is a multiplication operator with a modulus p. We call a1, a2, ..., and @n as indices. All indices lie between [0 p-1] and are mutually different. For example, assuming p = 5, n = 4, m = 3, and a digit block {2, 4, 1} can be represented as 4 shares: 4, 4, 2, and 2. Note that the shares are also within the p-ary notational system. Collect all shares and divide them into n sets {su, SK,n}, each of which contains K shares. Then, the n share-sets and their corresponding indices will be embedded into n cover images, respectively. Since the indices are within [0 p-1], they can also be regarded as symbols in the p-ary notational system. In other words, each cover image will be used to conceal (K+l) symbols in the p-ary notational system, s1t, s2,t, •.., sKt and at (t = 1, 2, •.., n). 3.2 Generalized running coding In order to improve steganographic imperceptibility, we use stego-coding technique to lower the distortion caused by data embedding. As mentioned above, running coding in [6] is only suitable for binary data-hiding system. This subsection generalizes the running coding method, so that the secret symbols in the p-ary notational system can be carried by a sequence of gray-pixel-value of cover image. Actually, for each cover image, either generalized running coding or EMD embedding can be employed to embed the shares and index. In the generalized running coding method, each secret symbol in the p-ary notational system is represented by a series of consecutive cover values, and each cover value also relates to several consecutive secret symbols. Thus, a data-hider can modify a selected cover value to embed several secret symbols, so that the distortion introduced into the cover signal is significantly reduced, which also means the data-hiding efficiency is increased. For convenience, we denote the (K+l) symbols in the p-ary notational system to be embedded into a certain cover as [x1, x2, •.., xK+1]. Pseudo-randomly select (K+l)T pixels in cover image according to a secret key, and denote the gray-levels of them as [hu, h12, •.., h1kk+1; h%u h2,2, •.., h2,k+1; •..; hT1, hT2, •.., hT,k+1]. That means the number of host values is T times of that of secret symbols. 3.2.1 The case of T=p' Firstly, we discuss the case that T is an integer power of p (T = pt). Inspired from [6], construct a generating matrix G sized (t+1) x T. Denote the elements in G as g(i, j), and assign them according to the following principle, 1. All elements are integers within [0, p-1]. 2. All elements in the first row are 1. 3. All pt columns in G are different. For example, when p=3 and k=9, [ i 5 5 k ,1 k ,2 k m-1 m-1 m-1 m-1 44 Informatica 33 (2009) 41-48 X. Zhang et al. "1 1 1 1 1 1 1 1 1" G = 0 1 2 0 1 2 0 1 2 (10) 0 0 0 1 1 1 2 2 2 From the original host data and the generating matrix G, calculate i+1 T yv = ZZ[&0'j)■ hv-.+i,j ] mod t=i j=i p- (ii) v = 1,2, K +1 where hv-i+1j- = 0 if v—+1 < 0. That means the value of yv is determined by (/+1) x T host values hv_u, hv-t,2, hv-t'T, hv-t+11, hv-t+1,2' hv-t+1'T, ..., hv,1' hv,2' ..., hv,T. Similarly, we will modify a small number of host values to make each yv equal to the corresponding secret xv. Let ^v = xv - yv mod p, v = 1,2, ..., K +1 (12) Arrange all the zv to form a vector Z = [z1, z2, ... , zK+1]T, and then divide Z into a set of sub-vectors in the following way: 1. Scan the vector Z from the beginning to the end; 2. If the encountered digit is '0', define this '0' as a sub-vector containing only one element; 3. If the encountered digit zv is not '0', define this digit together with the following t digits as a sub-vector with a length (t+1). Because all the elements in the first row of G are 1 and p is prime, the sub-vector in this case must be equal to product of zv and one of the columns in G with modulus p. Equation (11) indicates that any change on host value hvj will affect the values of yv, yv+1, ..., yv+t. Thus, we can modify only one host value but embed several secret symbols. Assume that zv is not 0 and the sub-vector [zv, zv+1, ..., zv+t]T equals the product of zv and the j-th column of G with modulus p. Either increasing the value of hvj by zv or decreasing the value of hvj by p-zv will make [y'v, y'v+1, ..., y'v+t] identical to [xn Xv+1, ..., xv+t], where [y'v, y'v+1, ..., y'v+t] are obtained from the modified host values according to (11). In this way, all secret symbols can be embedded by performing the similar operation for all sub-vectors. Consider that, for example, a host value sequence with length 21 for carrying secret message is [40 187 99, 93 231 19, 82 78 33, 11 176 134, 56 27 121, 31 249 83, 90 111 24], and 7 secret digits in ternary system, implying p = 3, [2110100]. Because T = 21/7 = 31, construct a generating matrix G. G = 111 0 1 2 (13) From (11), the vector Y is [2200021], so that Z = [0210112]T. Append '0' to the end of Z and segment it into 5 sub-vectors: [0], [21]T, [0], [11]T, and [20]T. Note that appending '1' or '2' is also allowable. Since the sub-vector [21]T is a product of 2 and the 3rd column of G with modulus 3, the data-hider should increase h2,3 by 2 or decrease h2,3 by 1. To lower the distortion, the value of h2,3 is decreased by 1. Similarly, h5,2 should be increased by 1, and h71 decreased by 1. So, the stego-sequence [40 187 99, 93 231 18, 82 78 33, 11 176 134, 56 28 121, 31 249 83, 89 111 24] are produced. In this way, 7 symbols in ternary system are embedded by adding/subtracting 1 to/from three pixels. On the receiving side, a simple calculation of (11) can recover the embedded data, when the receiver knows the values ofp, T and G. A ratio between the number of embedded bits and the distortion energy caused by data hiding, E, is used to indicate the embedding efficiency. As mentioned above, a sub-vector must be '0', or contains (t+1) elements and begins with a non-zero digit. Since the values of z are also uniformly distributed within [0, p-1], the probability of the former case is 1/p, while that of the later case is (p-1)/p. In the former case, the secret symbol has been represented and any modification is needless, while in the later case, a modification on one host value is made to embed (t+1) digits. In average, (p-t-t+p)/p secret symbols are embedded by modifying (p-1)/p host values. As p is odd, the modifications on host values are within [(1-p)/2, (p-1)/2], thus, E = [(p ■ t -1+p V p]-l°g2 p p -1 2 ( p-1)/2 7 2 1 u=1 (14) pp = (p ■ t - t + p)-log2 p ( p-1)/2 2 ■ 2 u2 u =1 which is significantly larger than 2, the embedding efficiency of plain LSB replacement/matching method. 3.2.2 The case of p' < T < pt+1 If T is not an integer power of p, i.e., pl < T