Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum MaxPlanck Institute of Computer Science, Saarbruecken, Germany
4920
Yun Q. Shi (Ed.)
Transactions on Data Hiding and Multimedia Security III
13
Volume Editor Yun Q. Shi New Jersey Institute of Technology Newark, NJ, 07102, USA Email:
[email protected] Library of Congress Control Number: 2008927739 CR Subject Classification (1998): K.4.1, K.6.5, H.5.1, D.4.6, E.3, E.4, F.2.2, H.3, I.4 LNCS Sublibrary: SL 4 – Security and Cryptology ISSN ISBN10 ISBN13
18613043 3540690166 Springer Berlin Heidelberg New York 9783540690160 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com © SpringerVerlag Berlin Heidelberg 2008 Printed in Germany Typesetting: Cameraready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acidfree paper SPIN: 12280889 06/3180 543210
Preface
In this volume, we present the third issue of the LNCS Transactions on Data Hiding and Multimedia Security. Continuing the tradition of the previous two editions, we are delighted to present contributions in the areas of steganography and digital watermarking. The first two papers in this issue deal with the security of steganographic systems. It is already widely accepted that the application of covering codes to data embedding can improve both the embedding efficiency and the security of steganographic schemes. In the first paper, Bierbrauer and Fridrich describe several families of covering codes, allowing a better performance compared to linear codes which are currently in use in steganography. In the second paper, Korzhik et al. propose to customize the notion of the Bhattacharyya distance in order to measure the detectability of steganographic systems through steganalysis. In the third paper, Jamzad and Kermani present a novel image steganographic scheme based on Gabor filters and neural networks. Finally, this volume contains two papers dealing with digital watermarking and data hiding. In the fourth paper, Venturini introduces and analyzes a new covert channel, called the timing channel, and proposes countermeasures to reduce its capacity. Finally, in the fifth paper, VilaForcén et al. analyze the performance of additive attacks against quantizationbased datahiding methods. We hope that this issue is of great interest to the datahiding community and that these papers will trigger new research in the field of data hiding and multimedia security. Finally, we want to thank all the authors, reviewers and editors who have devoted their valuable time to the success of this third issue. As always, special thanks go to Springer and Alfred Hofmann for their continuous support. January 2008
Yun Q. Shi (EditorinChief) HyoungJoong Kim (Vice EditorinChief) Stefan Katzenbeisser (Vice EditorinChief)
LNCS Transactions on Data Hiding and Multimedia Security Editorial Board
EditorinChief Yun Q. Shi
New Jersey Institute of Technology, Newark, NJ, USA
[email protected] Vice EditorsinChief HyoungJoong Kim Stefan Katzenbeisser
Korea University, Seoul, Korea
[email protected] Philips Research Europe, Eindhoven, Netherlands
[email protected] Associate Editors Mauro Barni Jeffrey Bloom Jana Dittmann
Jiwu Huang Mohan Kankanhalli Darko Kirovski C.C. Jay Kuo HeungKyu Lee
Benoit Macq Nasir Memon
University of Siena, Siena, Italy
[email protected] Thomson, Princeton, NJ, USA
[email protected] OttovonGuerickeUniversity Magdeburg, Magdeburg, Germany
[email protected] Sun Yatsen University, Guangzhou, China
[email protected] National University of Singapore, Singapore
[email protected] Microsoft, Redmond, WA, USA
[email protected] University of Southern California, Los Angeles, USA
[email protected] Korea Advanced Institute of Science and Technology, Daejeon, Korea
[email protected] Catholic University of Louvain, Belgium
[email protected] Polytechnic University, Brooklyn, NY, USA
[email protected] VIII
Organization
Kivanc Mihcak Hideki Noda JengShyang Pan
Fernando PerezGonzalez Andreas Pfitzmann Alessandro Piva YongMan Ro
AhmadReza Sadeghi Kouichi Sakurai Qibin Sun Edward Wong
Bogazici University, Istanbul, Turkey
[email protected] Kyushu Institute of Technology, Iizuka, Japan
[email protected] National Kaohsiung University of Applied Sciences, Kaohsiung, Taiwan
[email protected] University of Vigo, Vigo, Spain
[email protected] Dresden University of Technology, Germany
[email protected] University of Florence, Florence, Italy
[email protected] Information and Communications University, Daejeon, Korea
[email protected] RuhrUniversity, Bochum, Germany
[email protected] Kyushu University, Fukuoka, Japan
[email protected] Institute of Infocomm Research, Singapore
[email protected] Polytechnic University, Brooklyn, NY, USA
[email protected] Advisory Board Pil Joong Lee
Bede Liu
Pohang University of Science and Technology, Pohang, Korea
[email protected] Princeton University, Princeton, NJ, USA
[email protected] Table of Contents
Constructing Good Covering Codes for Applications in Steganography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J¨ urgen Bierbrauer and Jessica Fridrich On the Use of Bhattacharyya Distance as a Measure of the Detectability of Steganographic Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Valery Korzhik, Hideki Imai, Junji Shikata, Guillermo MoralesLuna, and Ekaterina Gerling
1
23
Secure Steganography Using Gabor Filter and Neural Networks . . . . . . . . Mansour Jamzad and Zahra Zahedi Kermani
33
Oracle Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ilaria Venturini
50
QuantizationBased Methods: Additive Attacks Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . J.E. VilaForc´en, S. Voloshynovskiy, O. Koval, F. P´erezGonz´ alez, and T. Pun Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
91
Constructing Good Covering Codes for Applications in Steganography J¨ urgen Bierbrauer1 and Jessica Fridrich2 1
2
Department of Mathematical Sciences Michigan Technological University HOUGHTON (MI) 49931, USA Department of Electrical and Computer Engineering Binghamton University BINGHAMTON (NY) 139026000
Abstract. Application of covering codes to data embedding improves embedding eﬃciency and security of steganographic schemes. In this paper, we describe several familes of covering codes constructed using the blockwise direct sum of factorizations. We show that nonlinear constructions oﬀer better performance compared to simple linear covering codes currently used by steganographers. Implementation details are given for a selected code family.
1
Introduction
Steganography is the art of stealth communication. Its purpose is to make communication undetectable. The steganography problem is also known as the prisoners’ dilemma formulated by Simmons [28]. Alice and Bob are imprisoned and want to hatch an escape plan. They are allowed to communicate via a channel monitored by a warden. If the warden ﬁnds out that they are communicating secretly, he throws them into solitary conﬁnement. Thus, the prisoners need to design a method to exchange messages without raising the warden’s suspicion. The prisoners hide their messages in innocuouslooking cover objects by slightly modifying them (obtaining stego objects). The embedding process is usually driven by a stego key, which is a secret shared between Alice and Bob. It is typically used to select a subset of the cover object and the order in which the cover object elements are visited during embedding. The most important property of any steganographic communication is statistical undetectability. In other words, the warden should not be able to distinguish between cover and stego objects. Formal description of this requirement in informationtheoretic terms was given by Cachin [4]. If the communication channel that Alice and Bob use is distortionfree, we speak about the passive warden scenario. Digital multimedia ﬁles, such as digital images, audio, or video, are conveniently used in steganography today because they are digitized forms of physical quantities, such as photon counts or voltages, and thus contain certain small level Y.Q. Shi (Ed.): Transactions on DHMS III, LNCS 4920, pp. 1–22, 2008. c SpringerVerlag Berlin Heidelberg 2008
2
J. Bierbrauer and J. Fridrich
of noise. Because of the presence of this indeterministic component, steganographers hope that part of this component can be replaced with pseudorandom (e.g., encrypted) message bits, thus obtaining a secure steganographic method. Intuitively, the fewer changes the embedding process incurs, the smaller the chance that the embedding modiﬁcations will be statistically detectable. We acknowledge, though, that the number of changes is not the only important factor inﬂuencing the security of the steganographic scheme. The choice of the cover object and the character of modiﬁcations play an equally important role. For example, it is known that embedding in spatial domain of a decompressed JPEG image can be easily detectable even when only one embedding change is carried out [15]. Furthermore, the impact of embedding realized by ﬂipping LSBs of pixels (Least Signiﬁcant Bit) is relatively easy to detect even at very low embedding rates [22]. Nevertheless, it is true that for two steganographic schemes with the same embedding mechanism, the one that introduces fewer embedding changes will be more secure. Steganographers use the concept of embedding eﬃciency to quantify how eﬀectively a given algorithm embeds data. The embedding eﬃciency is deﬁned [32] as the average number of random message bits embedded using one embedding change. There is evidence that schemes with low embedding eﬃciency oﬀer worse security than schemes with higher eﬃciency. For example, the popular JPEG steganography program OutGuess [26] embeds messages in DCT coefﬁcients (Discrete Cosine Transform) in two passes. In the ﬁrst pass, it embeds with eﬃciency 2 by matching the LSBs of DCT coeﬃcients with message bits. In the second pass, more changes are imposed on the previously nonvisited DCT coeﬃcients. While this has the beneﬁt of preserving the global DCT histogram, the embedding eﬃciency decreases signiﬁcantly. On the other hand, the Model based Steganography (MBS) [27] without deblocking preserves even more statistics than OutGuess and does so at a higher embedding eﬃciency. Steganalysis of both schemes [14] indicates that MBS is signiﬁcantly harder to detect than OutGuess. The importance of high embedding eﬃciency for steganography and the relevance of covering codes to this problem were recognized for the ﬁrst time by Crandall [7], who showed that linear codes can markedly improve the embedding eﬃciency. He called this type of embedding ”matrix embedding”, which was made popular in the stego community by Westfeld in his F5 algorithm [32]. Crandall refers to an unpublished article by Bierbrauer [2] that provides deeper insight into this problem from the point of view of a coding theorist. The connection between linear covering codes and steganography has also appeared in the paper by Galand and Kabatiansky [17] who addressed both the passive and active warden scenarios. In this paper, we describe and extend the original Bierbrauer’s work. We believe that the steganographic community will beneﬁt from this work as it formulates the problem of embedding eﬃciency in codingtheoretic language and makes a connection with a large body of work in coding. Moreover, we point out the importance of certain families of codes to steganography and show
Constructing Good Covering Codes for Applications in Steganography
3
that nonlinear codes have better performance than known linear constructions, e.g., matrix embedding. In Section 2, the connection between covering functions and steganography is formally established. In Sections 3, we show how codingtheoretic bounds translate to bounds on basic descriptors of steganographic schemes. Section 4 contains basic methods for constructing good covering codes (good in the sense of providing high steganographic embedding eﬃciency). In Section 5, we study some good families of nonlinear codes. Section 6 lists the best currently known covering functions that we expect to ﬁnd applications in steganography. The embedding eﬃciency of steganographic schemes that use these covering functions is compared and contrasted to theoretical bounds in Section 7. To enable practical implementation of steganographic schemes that use the proposed constructions, in Section 8 we describe the details of the nonlinear NordstromRobinson code and some covering functions related to it. While the description is more involved than in the linear case, the resulting algorithm is very eﬃcient. The paper is concluded in Section 9.
2
The Link to Coding Theory
For concreteness, we assume that the cover object used for communication is a grayscale digital image whose pixels are integers between 0 and 255. We assign a bit to each pixel value (the LSB of the grayscale value). We will further assume that the embedding mechanism is ﬂipping the LSB, while stressing that other embedding operations or bit assignments are certainly possible. We also assume that the sender can use all pixels for embedding, i.e., the embedding is not constrained to any selection channel [13]. Possible directions one can take for application of covering codes to nontrivial selection channels (wet paper codes) were brieﬂy discussed in [13]. Let us assume that the embedding proceeds by blocks. The cover image is divided into disjoint segments of N pixels. Let x = (x1 , x2 , . . . , xN ) be the bitstring formed by their least signiﬁcant bits. Here we view the entries, the bits, as elements of the ﬁeld F2 = {0, 1}. Formally we can write x ∈ FN 2 . Assume the secret message has been encoded as a bitstring. We scan this bitstring and divide it into segments of length n, for some number n < N. What we want to construct is a suitable function f, which maps bitstrings of length N to bitstrings of length n, formally n f : FN 2 −→ F2 , which allows us to extract n bits of the secret message. This means that for given x ∈ FN 2 (the LSBs of the corresponding segment of the cover image) and y ∈ Fn2 (a segment of the secret message) we want to replace x by x such that f (x ) = y. An important question is the relation between x and x . If x and x diﬀer in 3 of their N coordinates, then that means that 3 of our segment of N pixels need to be changed. Our goal is to keep that number of changes to a minimum. The number of coordinates where the entries of two strings x, x diﬀer is a basic notion of coding theory. It is the Hamming distance d(x, x ). If we
4
J. Bierbrauer and J. Fridrich
want to control the worst case, then we ﬁx an upper bound ρ on the embedding distortion d(x, x ). This leads to the following notion: Deﬁnition 1. A covering function COV (ρ, N, n) is a mapping n f : FN 2 −→ F2 n N which satisfies the following: for every x ∈ FN 2 , y ∈ F2 there is some x ∈ F2 such that d(x, x ) ≤ ρ and f (x ) = y.
A covering function COV (ρ, N, n) enables construction of a steganographic scheme that can embed n bits in N pixels using at most ρ embedding changes. We say that the scheme has relative capacity α = n/N , change rate ρ/N , and embedding eﬃciency e = α/(ρ/N ) = n/ρ. We remark here that the embedding eﬃciency in steganography is typically deﬁned in a slightly diﬀerent manner as the expected number of bits embedded per one embedding change, where the expectation is taken over all possible covers x ∈ FN 2 and messages. More on this diﬀerence is included in Section 7. We now switch to terminology more commonly used in coding. For readers not familiar with coding theory, we recommend the introductory text [1]. Calling N the length, n the redundancy, and ρ the covering radius, the following design problems arise: – We want n/N, the relative redundancy, to be large (large relative capacity). – We want ρ/N, the relative covering radius, to be small to have good embedding eﬃciency. – Finally, there should be an eﬀective algorithm that calculates x . In coding theory, a code is deﬁned simply as a subset of the space of all tuples of a certain length N over some alphabet, where N is the length of the code. We speak of a binary code if the alphabet has two elements. Historically, coding theory developed in the context of information transmission over noisy channels. Typically in these applications the most important parameter is the minimum distance d : any two diﬀerent elements of the code should be at Hamming distance ≥ d. In other words, if two elements of the code (codewords) are diﬀerent, then they are very diﬀerent. In our context, the basic parameter is the covering radius: Deﬁnition 2. Let C ⊂ FN 2 . The covering radius of the code C is the smallest number ρ such that any N tuple is at Hamming distance ≤ ρ from some codeword. Informally, one speaks of errorcorrecting codes if the minimum distance is the important parameter, of covering codes if one is more interested in the covering radius. While the minimum distance concerns only the distances between codewords (in a way it ignores the ambient space FN 2 ), the covering radius is deﬁned in terms of the embedding of the code in its ambient space.
Constructing Good Covering Codes for Applications in Steganography
5
Deﬁnition 1 demands that the inverse image f −1 (y) be a covering code of radius ρ for every choice of y ∈ Fn2 . It follows that FN 2 is the disjoint union of 2n such covering codes. Clearly, this is an equivalent description of a covering function: Theorem 1. The following are equivalent: – A covering function COV (ρ, N, n). n – A partition of FN 2 into 2 covering codes of covering radius ρ. We now give an example of a covering function constructed from a linear code. This was also discussed, for example, in [32]. Start from the matrix ⎛ ⎞ 1001101 H = ⎝0 1 0 1 0 1 1⎠ 0010111 whose entries are elements of F2 . Consider the linear mapping f : F72 −→ F32 deﬁned by f (x1 , x2 , x3 , x4 , x5 , x6 , x7 ) = (y1 , y2 , y3 ), where y1 = x1 + x4 + x5 + x7 , y2 = x2 + x4 + x6 + x7 , y3 = x3 + x5 + x6 + x7 . This function can be described in terms of matrix H. In fact, yi is the dot product of x and the ith row of H. We claim that f is a COV (1, 7, 3). For example, f (0011010) = 100. Assume y = 111. We claim that it is possible to replace x = 0011010 by x such that f (x ) = 111 and d(x, x ) = 1. In fact, we claim more: the coordinate where x has to be changed is uniquely determined. In our case, this is coordinate number 6, so x = 0011000. Here is the general embedding rule: form f (x) + y (in the example this is 011). Find the column of H which has these entries (in our example, this is the sixth column). This marks the coordinate where x needs to be changed to embed payload y. This procedure indicates how H and f were constructed and how this can be generalized: the columns of H are simply all nonzero 3tuples in some order. In general, we start from our choice of n and write a matrix H whose columns consist of all nonzero ntuples. Then H has N = 2n − 1 columns. The covering n function f : FN 2 −→ F2 is deﬁned by way of the dot products with the rows of H, just as in the example n = 3. Then f is a covering function of radius 1 giving us the following theorem. Theorem 2. For every n there is a COV (1, 2n − 1, n). These covering functions are wellknown not only in coding theory but also in the steganographic community [32]. They are equivalent to the binary Hamming codes and are by deﬁnition linear (over F2 ). Every linear covering function can of course be described in terms of an (n, N )matrix H. Obviously the covering radius will be ≤ ρ if and only if every vector from Fn2 can be written as a linear combination of at most ρ columns of H. As 0columns and repeated columns are not helpful for this purpose, we may as well assume that the columns of H are
6
J. Bierbrauer and J. Fridrich
distinct and nonzero. The code f −1 (0) is a linear covering code of radius ρ. Vice versa, it is also clear that the existence of such a covering code can be used to construct H and f. The matrix H is known as a check matrix of the code. We have just proved the following theorem: Theorem 3. The following are equivalent: – A linear COV (ρ, N, n). – A binary linear code of length N and dimension N − n of covering radius ρ. – A collection of N nonzero bitstrings of length n with the property that every element of Fn2 can be written as a sum of at most ρ bitstrings from the collection. The description of covering functions in terms of covering codes was ﬁrst given by Crandall [7] who references [2]. The textbook [1] contains a description, which is more general in that it considers arbitrary alphabets. Here we concentrate on the binary case as it is by far the most interesting. Galand and Kabatiansky [17] treat the case of the description corresponding to linear covering codes. In Section 4, we are going to see that nonlinear constructions can in fact be very powerful. For readers who are interested in more technical material on covering codes and wider connections to other mathematical disciplines, we now include a brief discussion supplied with appropriate references. The notion of covering functions was introduced in [2,1] in a slightly more general form, using arbitrary alphabets. Deﬁnition 1 is the binary case. Covering codes are classical objects in coding theory. A recent book on the subject is Covering codes by Cohen, Honkala, Litsyn and Lobstein [6]. By Theorem 1 a covering function is equivalent with a partition of the ambient space into covering codes. These partitions have been studied by the coding community. In EtzionGreenberg [11], they appear under the name covering by coverings. There is also a graphtheoretic link. In fact, the graphtheoretic problem is more general. It applies to any graph G. The problem we are interested in arises as the special case when G is a Hamming graph (the vertices are the bitstrings of length N, two bitstrings form an edge if their distance is 1). A ρdominating set D of graph G is deﬁned as a set of vertices, such that each vertex of G has distance ≤ ρ from a vertex of D. The ρdomatic number of graph G is the smallest number of subsets when the vertices are partitioned into ρdominating sets. This notion seems to go back to Zelinka [33] and Carnielli [5]. More information on ¨ the subject is in Osterg˚ ard [24].
3
CodingTheoretic Bounds and Linear Constructions
As explained in the introduction, to minimize the statistical impact of embedding, the steganographic scheme should have high embedding eﬃciency. In terms of covering functions COV (ρ, N, n), we would like to know for what values of the three parameters covering functions exist and which functions allow high embedding eﬃciency n/ρ. In this section, we ﬁrst establish a useful inequality
Constructing Good Covering Codes for Applications in Steganography
7
that will give us bounds on the maximal achievable embedding eﬃciency. Then, we give examples of linear covering functions that can be used in steganography directly or as ingredients in more advanced constructions described in Section 5. We start with some simple recursive constructions. Proposition 1. IfCOV (ρi , Ni , ni ) exist for i = 1, 2, . . . , then COV ( ρi , Ni , ni ) exists. The existence of COV (ρ, N, n) implies the existence of COV (ρ + 1, N, n), COV (ρ, N + 1, n), COV (ρ, N, n − 1) and of COV (c · ρ, c · N, c · n) for every natural number c. This hardly needs a proof. For the ﬁrst property simply write your bitstring of length Ni as a concatenation of strings of length Ni each and apply the COV (ρi , Ni , ni ) to the corresponding segment. The rest is equally obvious and follows immediately from the deﬁnition. For example, using the stego terminology, if we can embed n bits using at most ρ changes in N pixels, it is certainly true that we can embed the same payload in the same pixels using at most ρ + 1 changes, etc. In order to obtain a bound connecting the three parameters of a covering function, observe that the existence of a COV (ρ, N, n) implies the existence of a covering code with at most 2N −n codewords. This is because the sets f −1 yN∈ (y), ρ . Each codeword thus determines Fn2 partition the ambient space FN 2 i=0 i vectors at Hamming distance at most ρ. Adding up all those numbers must give us at least 2N , the number of all vectors in our space: Theorem 4 (sphere covering bound). If COV (ρ, N, n) exists, then ρ N i=0
i
≥ 2n .
As a trivial example, Theorem 4 tells us that COV (1, N, n) can exist only if N ≥ 2n −1. This shows that covering functions constructed from Hamming codes (Theorem 2) reach this bound. Thus, the associated steganographic schemes are optimal in the following sense. Given ρ = 1 and n, the covering function realized using the Hamming code embeds the largest possible relative payload α = n/N (because it has the smallest possible N ). The embedding eﬃciency is n/ρ = n. A less trivial example is COV (3, N, 11), where Theorem 4 tells us
N N 1+N + + ≥ 211 = 2048. 2 3 For N = 23 we have equality. The corresponding code exists. It is the single most famous code, the binary Golay code. We see that it deﬁnes a COV (3, 23, 11), which can embed 11 bits in 23 pixels by at most 3 changes with embedding eﬃciency e = 11/3. The cases when Theorem 4 is satisﬁed with equality correspond
8
J. Bierbrauer and J. Fridrich
to perfect codes. We conclude that the Hamming codes and the binary Golay code are perfect. Unfortunately, the binary Golay code is the only nontrivial binary perfect code with covering radius > 1, so the situation will never be quite as nice again. We now list several other known families of linear covering functions that provide high embedding eﬃciency and are thus of interest to the steganographic community. Linear covering functions can be considered from a geometric point of view as well. Consider the linear covering function deﬁned by the check matrix ⎛ ⎞ 1001 H = ⎝0 1 0 1⎠ 0011 Recalling Theorem 3, since any threebit message can be obtained by adding at most 2 columns, this check matrix deﬁnes a COV (2, 4, 3). This code is graphically represented in Figure 1 by viewing the black dots as pixels and the attached labels as messages. Notice that any threebit message can be obtained by adding at most 2 labels of the two black dots. The quadrangle consisting of black dots has the property that each of the remaining 3 points is on some line through two of the quadrangle points. Readers familiar with projective geometry may recognize Figure 1 as the Fano plane P G(2, 2). This special case can be generalized by looking at nonzero bitstrings of length n as points of a (n − 1)dimensional projective geometry P G(n − 1, 2) deﬁned over F2 . In this language, a linear COV (2, N, n) is equivalent with a set K of N points in P G(n − 1, 2) having the 100 11111 00000 00000 11111 00000 11111 00000 11111 00000 11111
110
101 111
1111 0000 0000 1111 0000 1111 0000 1111 11111 00000 00000 11111 00000 11111 00000 11111 010
011
1111 0000 0000 1111 0000 1111 0000 1111 001
Fig. 1. Fano plane and COV (2, 4, 3)
Constructing Good Covering Codes for Applications in Steganography
9
property that each point of P G(n − 1, 2) is on a line containing 2 points of K. The family of linear covering functions COV (2, N, n) for n ≤ 7 and minimal N has been completely classiﬁed in DavydovMarcuginiPambianco [10]. A family of linear covering functions with covering radius 2, which often yields the best known values, was constructed in GabidulinDavydovTombak [16] (GDT): (1) COV (2, 5 · 2a−1 − 1, 2a + 1) for a ≥ 1. The smallest member of the family is the COV (2, 4, 3), which we just constructed in the Fano plane. The next parameters are COV (2, 9, 5), COV (2, 19, 7), COV (2, 39, 9), COV (2, 79, 11). The Hamming code Hm (m ≥ 3) is known to have a subcode Bm of codimension m within Hm (a primitive BCHcode), which has covering radius 3. The corresponding parameters as a covering function are therefore COV (3, 2m − 1, 2m) for m ≥ 3.
(2)
The comparison of embedding eﬃciency of steganographic schemes based on the linear coverings is compared to best nonlinear constructions in Section 7.
4
The Blockwise Direct Sum
In this section, we introduce a recursive procedure called the blockwise direct sum BDS of nonlinear codes. This very useful tool for constructing coverings is of great interest to us because it can give us covering functions leading to steganographic schemes with higher embedding eﬃciency than linear covering functions. In fact, virtually all known interesting constructions of coverings make use of it. Although the material in this and the next section is mathematically rather involved, it is mostly selfcontained and accessible with only elementary knowledge of coding theory. In order to apply the BDS, we need a reﬁnement of the concept of a partition of the ambient space into subcodes: Deﬁnition 3. Let D ⊂ C ⊂ FN 2 . We say that C/D is a factorization if C can be written as the disjoint union of cosets of D and FN 2 is a disjoint union of cosets of C. Here a coset of D is a set of the form D + x, in other words a translate. The number of participating cosets of D in C is of course C/D, the index of D in C. In all cases that we consider, the index will have the form 2n . We deﬁne n to be the dimension of C/D (or codimension of D in C) in these cases. The redundancy k of C/D is deﬁned as the redundancy of C, its codimension in the ambient space. We will write U for the ambient space. Observe that whenever two linear codes form a chain, e.g., D ⊂ C, then they form a factorization. The length is the dimension of ambient space.
10
J. Bierbrauer and J. Fridrich
As an example, consider the factorization U/Hm , where Hm is the Hamming code. The length is 2m − 1, we have dim(U/Hm ) = m and the redundancy is 0 because the larger of the chain of codes is the ambient space. In general, factorizations of redundancy 0 are precisely covering functions. We need a notion which applies to factorizations and generalizes the covering radius (see Honkala [20]): Deﬁnition 4. Let C/D be a factorization. For every x in the ambient space let m(x) be the minimum of the distances from x to one of the cosets and M (x) the maximum. The norm ν = ν(C/D) is the maximum, taken over all x, of m(x) + M (x). In order to get a feeling for this notion, consider the case when C = U. Then each x ∈ U is contained in one of the cosets deﬁning the factorization. It follows m(x) = 0. The norm is therefore the maximum of the M (x). As all cosets of D have the same structure, in particular the same covering radius, it follows that the norm simply equals the covering radius ρ of D. To sum this up: a factorization U/D is nothing but a COV (ρ, N, n), where N is the length, n = dim(U/D) and ρ = ν(U/D) is the norm. The BDS is a simple and eﬀective construction which uses as input two factorizations of equal dimension and outputs a factorization of larger length. This is relevant to our problem as we can control the covering radius of the output factorization in terms of the norms of the input. Deﬁnition 5. Let C1 /D1 and C2 /D2 be factorizations of lengths Ni and equal dimension n. Number the participating cosets D1 (i) and D2 (i) for i = 1, . . . , 2n . The blockwise direct sum (C1 /D1 ) ∨ (C2 /D2 ) is defined by n
C = ∪2i=1 D1 (i) × D2 (i). The length of the BDS is the sum N1 + N2 of the lengths and (C1 × C2 )/C is a factorization, again of dimension n. The BDS is wellknown in the theory of errorcorrecting codes. It can be used to construct codes with large minimum distance. For the theory of covering codes, it seems to be indispensible. We just convinced ourselves that it works well on the level of factorizations. The main point is that we can control the covering radius: Theorem 5. Let C be the blockwise direct sum of two factorizations with identical dimension n, lengths Ni , norms νi and redundancies ki , as in Definition 5. Then C has length N1 + N2 and redundancy k1 + k2 + n. The covering radius of C satisfies ρ(C) ≤ (ν1 + ν2 )/2 . Proof. The number of elements of C is obvious. Let (x, y) in the ambient space. Choose j, k such that d(x, D1 (j)) and d(y, D2 (k)) are minimal. It follows from the deﬁnition of the norm that the sum of the distances from (x, y) to D1 (j) × D2 (j) and to D1 (k) × D2 (k) is at most ν1 + ν2 . One of the two distances must be ≤ (ν1 + ν2 )/2.
Constructing Good Covering Codes for Applications in Steganography
11
Let us express the concepts of a factorization and of the BDS in terms of covering functions. The factorization in the terminology of Deﬁnition 3 is equivalently k+n described by a mapping f = (fl , fr ) : FN where fl (x) ∈ Fk2 , fr (x) ∈ 2 −→ F2 n −1 −1 F2 , f (0, 0) = D, each f (a, b) is a coset of D and C is the union of the f −1 (0, b). If f1 = (f1,l , f1,r ) and f2 = (f2,l , f2,r ) describe the factorizations C1 /D1 and C2 /D2 in Deﬁnition 5, then the BDS is deﬁned by (f1 ∨ f2 )(x, y) = (f1,l (x), f2,l (y), f1,r (x) + f2,r (y)) ∈ Fk21 +k2 +n .
(3)
All we need in order to put the BDS to work are good factorizations to use as inputs. It turns out that a famous family of nonlinear codes, the Preparata codes, are extremely valuable ingredients for this machinery.
5
Some Families of Good Factorizations
We know that each COV (ρ, N, n) is nothing but a factorization of redundancy 0, length N and dimension n. It can therefore itself be used as ingredient in the BDS. A factorization we know from Section 3 is Hm /Bm , of length 2m − 1, dimension m and redundancy m. The norm is clearly ≤ 4 as Hm has covering radius 1 and Bm has covering radius 3. An important nonlinear factorization is furnished by a famous family of nonlinear codes, the Preparata codes. Codes with their parameters were ﬁrst constructed by Preparata [25], where the reader can ﬁnd the proof of the following theorem: Theorem 6. For every even m ≥ 4 there is a subcode Pm ⊂ Hm such that Hm /Pm is a factorization of dimension m − 1 and norm 3. More precisely we / Hm has have that the covering radius of Pm is 3 and that every vector x ∈ distance at most 2 from Pm . The factorization of Theorem 6 is the most important nonlinear ingredient in constructions of covering codes and covering functions [19]. The smallest member P4 of the Preparata family was constructed in 1967 [23]. We denote its extension P 4 by N R (for the notion of an extension see the paragraph preceding Table 5 below where some elementary facts are explained). This is the famous NordstromRobinson code. It is also the smallest member of the Kerdock codes, a family of nonlinear codes closely related to the Preparata codes. The NordstromRobinson code has an unusually large group of automorphisms (of order 8! = 40, 320) and is optimal in many respects. It can be found inside the binary Golay code. No linear codes with similar properties as N R can exist. There are numerous links from the Preparata and Kerdock codes to other mathematical areas, such as ﬁnite geometries and group theory. It had been observed early on that the Preparata and Kerdock codes behave like pairs of binary linear codes related by duality, which sounds strange as they are not linear. An explanation for this phenomenon was given in [19]. There are families of linear
12
J. Bierbrauer and J. Fridrich
codes deﬁned over the alphabet Z4 = Z/4Z, the integers mod 4, which map to the Preparata and Kerdock codes under the Gray map γ. The Gray map takes 0 ∈ Z4 to 00, the zerodivisor 2 to the pair 11 and the units 1, 3 ∈ Z4 to the pairs of weight 1. It is the only nonlinear element in the construction. The original observation that the Preparata and Kerdock codes behave almost as if they were dual linear codes is explained by the fact that their preimages under γ are in fact dual Z4 linear codes. The same feature explains why Hm /Pm is a factorization. An explicit proof is in Wan’s book Quaternary codes [31]. In order to understand the factorizations given in the following table, we recall some elementary facts and constructions. The sum zero code consists of the bitstrings of even weight. It has codimension 1 in ambient space, being the dual of the repetition code. We denote it by A. In algebra it is also known as the augmentation ideal. If C is a code of length N then its extension C has length N + 1. It has the same number of codewords as C and is deﬁned such that it is contained in the sum zero code A of length N + 1. If C/D is a factorization, then C/D is a factorization as well. Let ν be the norm of C/D. The norm of C/D is then the even number among {ν + 1, ν + 2}. We arrive at the following list of factorizations. Some factorizations factorization length dim red norm U/Hm 2m − 1 m 0 1 U/H m 2m m+1 0 2 m A/H m 2 m 1 2 Hm /Bm 2m − 1 m m 4 U/GDTm 5 · 2m−1 − 1 2m + 1 0 2 Hm /Pm 2m − 1 m−1 m 3 U/Pm 2m − 1 2m − 1 0 3 m H m /P m 2 m−1 m+1 4 U/P m 2m 2m 0 4 A/P m 2m 2m − 1 1 4 Here m has to be even and ≥ 4 whenever Pm is involved. Recall that Hm are the Hamming codes, Bm is the BCHcode introduced in Section 3, and GDTm is the code from [16] mentioned in the same section.
6
The Best Known Covering Functions
We now give examples of some of the best known covering functions based on the factorizations given in the table at the end of the preceding section. They are included here as a concise summary of the best tools the coding theory currently provides to steganographers for construction of embedding schemes with high embedding eﬃciency. Their performance is displayed graphically in Section 7. For practitioners, we give a detailed description of the embedding and extraction algorithm for one selected nonlinear covering function in Section 8.
Constructing Good Covering Codes for Applications in Steganography
13
The examples below are from EtzionGreenberg [11] and from Struik’s dissertation [30]. Observe that the BDS can be constructed whenever we have factorizations of equal dimension. Application to Hm /Pm and A/H m−1 (both of dimension m − 1) yields, with m = 2a, COV (2, 6 · 4a−1 − 1, 4a), a ≥ 2. (4) The ﬁrst members of this family are COV (2, 23, 8), COV (2, 95, 12), COV (2, 383, 16), COV (2, 1535, 20). The pair U/GDTm and H2m+2 /P2m+2 yields COV (2, 4m+1 + 5 · 2m−1 − 2, 4m + 3) for m ≥ 1.
(5)
The ﬁrst members of this family are COV (2, 19, 7), COV (2, 72, 11), COV (2, 274, 15), COV (2, 1062, 19). As both Hm /Pm and H m /P m have dimension m − 1, we can form the BDS. It has length 2m − 1 + 2m , redundancy m + (m − 1) + (m + 1) = 3m and covering radius 3. Let m = 2a. This yields COV (3, 2 · 4a − 1, 6a), a ≥ 2.
(6)
The smallest examples are COV (3, 31, 12), COV (3, 127, 18) and COV (3, 511, 24). These BDS can also be used as ingredients. In fact, (Hm /Pm ) ∨ (H m /P m ) ⊂ Hm × (Hm × F2 ), and this pair forms a factorization of dimension m and norm 3 + 2 = 5. This gives us the following two additional factorizations to complement Table 5 where m = 2a ≥ 4 : factorization length dim red norm above 2m+1 − 1 m 2m 5 extension 2m+1 m 2m + 1 6 Using as second ingredient A/H m and forming the BDS, we obtain, with m = 2a, the family COV (3, 3 · 4a − 1, 6a + 1) for a ≥ 2, whose smallest members are COV (3, 47, 13), COV (3, 191, 19), COV (3, 767, 25).
(7)
14
J. Bierbrauer and J. Fridrich
Forming the BDS of both table entries instead yields, with m = 2a, COV (5, 4a+1 − 1, 10a + 1) for a ≥ 2,
(8)
with the following smallest members COV (5, 63, 21) and COV (5, 255, 31). The BDS of Hm /Pm and Hm−1 /Bm−1 yields a covering function of length 2m − 1 + 2m−1 − 1, covering radius 3 and redundancy 3m − 1. Letting m = 2(a + 1), this becomes (9) COV (3, 6 · 4a − 2, 6a + 4) for a ≥ 1, with the smallest members COV (3, 22, 10), COV (3, 94, 16), COV (3, 382, 22). Finally, we use the direct sum construction of Proposition 1. As an example, the direct sum of the binary Golay code COV (3, 23, 11) and the nonlinear COV (2, 23, 8) yields COV (5, 46, 19). (10)
7
Performance
Having derived some families of good covering codes, we now study the embedding eﬃciency that these codes oﬀer to steganographers. As explained in the introduction, an important concept in steganography is the embedding eﬃciency, which is deﬁned as the ratio between the number of embedded bits and the number of embedding changes. Using the notation COV (ρ, N, n) for the covering function, we remind the terminology from Section 2 where we called the ratio α = n/N the relative capacity and e = n/ρ the embedding eﬃciency (in bits per embedding change). In Figure 2, we show the embedding eﬃciency as a function of 1/α for the binary Hamming code, the binary Golay code, and the families (1)–(10). The upper bound on e for a ﬁxed α can be obtained from the spherecovering bound (see, e.g., [13]) α , (11) e ≤ −1 H (α) where H −1 (α) is the inverse of the binary entropy function H(x) = −x log2 x − (1 − x) log2 (1 − x) on the interval [0, 1/2]. Observe that the recursive constructions of Proposition 1 imply that each COV (ρ, N, n) gives us constructions not only of its asymptotic parameters (N/n, n/ρ) but of an inﬁnite set of such parameter pairs that is dense in the region to the right and down of (N/n, n/ρ). This observation is important for practical applications in steganography – the sender should choose the covering code with relative capacity α slightly above the relative message length that he wants to communicate to the recipient.
Constructing Good Covering Codes for Applications in Steganography
15
9
8
7
n /ρ
6 Bound Hamming Golay GDT (1) BCH (2) BDS (4) BDS (5) BDS (6) BDS (7) BDS (8) BDS (9) BDS (10)
5
4
3
2
2
4
6
8
10
1/α
12
14
16
18
20
Fig. 2. Embedding eﬃciency n/ρ as a function of 1/α for various covering functions COV (ρ, N, n)
Members of the family (6) and (8) lead to the highest embedding eﬃciency, providing signiﬁcant improvement over the simple binary Hamming codes. Observe that since the covering radius ρ gives a bound on the average number of embedding changes ρa , the embedding eﬃciency as deﬁned in this paper is a lower bound on the embedding eﬃency n/ρa as typically deﬁned in steganographic literature. From our perspective, it is preferable to work with a simple invariant like ρ. The situation is analogous to the classical coding theory scenario where in most situations the minimum distance d, rather than the average distance, is used to obtain bounds on the error probability. Actually, the diﬀerence n/ρa − e is small and goes to 0 with increasing length. The last issue that needs to be addressed for practical applications is the implementation complexity. This is the topic of the next section where we discuss implementation details for the family of codes (4), as an example.
8
Implementation
In this section, we describe in detail the embedding algorithm and the algorithm for extracting the secret message bits based on the covering codes (4) for m = 4
16
J. Bierbrauer and J. Fridrich
(the covering function COV (2, 23, 8)). We start by detailing the factorizations Hm /Pm , A/H m−1 and their covering functions. 8.1
The Factorization H4 /P4 and Its Covering Function
Start with a description of the NordstromRobinson code N R = P 4 . This is a binary code of length 16, with 28 codewords, minimum distance 6 and covering radius 4. It is the smallest member of the Preparata family and the single most famous nonlinear code. Among its exceptional properties is the presence of a huge group of symmetries, of order 8! For an introduction see [3]. As mentioned earlier, the charm of the Preparata codes is that they are essentially linear over Z4 . This means that there is an underlying code, which is linear over Z4 , and the binary code in question is the image of this Z4 linear code under the Gray map γ, where γ : 0 → 00, 1 → 10, 3 → 01, 2 → 11. In order to construct the NordstromRobinson code start from the binary matrix ⎞ ⎛ 1000 0111 ⎜ 0100 1011 ⎟ ⎟ ⎜ (12) ⎝ 0010 1101 ⎠ , 0001 1110 which generates the extended Hamming code [8, 4, 4]2 (length 8, dimension 4, minimum distance 4). As this code is equal to its orthogonal with respect to the ordinary dot product (it is selfdual) it is tempting to lift this matrix to a matrix with entries in Z4 . Observe that the factor ring of Z4 mod {0, 2} is the binary ﬁeld F2 . Lifting means that each entry 0 ∈ F2 should become 0 or 2 in Z4 and each 1 ∈ F2 should be replaced by 1 or 3 in Z4 . We want the lift to have the property that it is selfdual over Z4 . After a moment’s thought this leads to the matrix ⎛ ⎞ 1000 2333 ⎜ 0100 1231 ⎟ ⎟ G = (IP ) = ⎜ ⎝ 0010 1123 ⎠ . 0001 1312 The selfdual Z4 linear code generated by the rows of this matrix is known as the octacode N . The NordstromRobinson code is its image under the Gray map: N R = P 4 = γ(N ). The length and number of codewords are as promised and it is not hard to check that the minimum distance and covering radius are as claimed. The codewords of N are x(a, b, c, d) = (lr) where l = (a, b, c, d), a, b, c, d ∈ Z4 . and r = s(l) = (2a + b + c + d, −a + 2b + c − d, −a − b + 2c + d, −a + b − c + 2d). The proof of the following lemma can be left as an easy exercise, using the selfduality of N .
Constructing Good Covering Codes for Applications in Steganography
17
Lemma 1. Let x ∈ N and νi (x) for i ∈ Z4 the frequency of i as an entry of x. Then the νi (x) have the same parity. In order to see that U/N R is a factorization, observe that N is systematic: in the projection on the left half of parameters each quaternary quadruple occurs precisely once. It follows that the binary code N R is systematic as well: in the projection on the left half of parameters each binary 8tuple occurs precisely once. Systematic codes can always be embedded in factorizations. In fact, the (0, y), where y ∈ Z44 are representatives of pairwise disjoint cosets of N . The union of those cosets is the ambient space U = Z48 . It follows that the same is true for N R. The codewords of N R are (γ(l), γ(s(l)), where l ∈ Z44 . Write as (x, y) ∈ F8+8 2 (x, y) = (γ(l), y) = (γ(l), γ(s(l))) + (0, y + γ(s(l))). This decomposition enables us to formulate the following proposition. Proposition 2. A COV (4, 16, 8) corresponding to the factorization F16 2 /N R is given by f (x, y) = y + γ(s(γ −1 (x))). Here x, y ∈ F82 . As an example, consider (x, y) = (00100111, 10011001). Then γ −1 (x) = 0132, s(0132) = 2332, γ(2332) = 11010111 and f (x, y) = 10011001 + 11010111 = 01001110. The observation that systematic codes can be embedded in factorizations is from Stinson [29], where a characterization of resilient functions is given in terms of factorizations. The factorization U/N R itself is not an interesting covering function. It yields good results when used as an ingredient in the BDS. We mentioned and used a factorization H 4 /N R of length 16, dimension 3 and redundancy 5. Here H 4 is the extended Hamming code, a linear [16, 11, 4]code. At ﬁrst we have to see that N R is in fact contained in the Hamming code. Let ⎛
11000000 ⎜ 00110000 ⎜ G=⎜ ⎜ 00001100 ⎝ 00000011 01010101
⎞ 00111111 11001111 ⎟ ⎟ 11110011 ⎟ ⎟. 11111100 ⎠ 01010101
This is a check matrix of the extended Hamming code H 4 = [16, 11, 4]2 (equivalently: no 3 columns of G add to the 0column). It is orthogonal to all codewords
18
J. Bierbrauer and J. Fridrich
of N R (for the ﬁrst 4 rows of G this is obvious, for the last row use Lemma 1). It follows N R ⊂ H 4 . Let T = γ(2200), γ(2020), γ(2002) . Then (0, T ) ⊂ H 4 as those vectors are orthogonal to the rows of G. The ﬁrst half of coordinates shows that the cosets N R + (0, t), t ∈ T are pairwise disjoint. This deﬁnes a factorization H 4 /N R. −→ F82 which Let us calculate the covering function f = (f1 , f2 ) : F16 2 describes the factorization H 4 /N R. Let ri , i = 1, . . . , 5 be the rows and sj , j = 1, . . . , 16 the columns of G. Let z = (xy) ∈ F8+8 and denote by ei 2 the elementary vectors. The ﬁrst section simply is the syndrome: f1 (z) = (z · r1 , z · r2 , z · r3 , z · r4 , z · r5 ) = (σz · r5 ) ∈ F4+1 . 2 Let the F2 linear mapping β : T −→ e6 , e7 , e8 be deﬁned by β(γ(2200)) = e6 , β(γ(2020)) = e7 , β(γ(2002)) = e8 . In order to calculate f2 , proceed as follows: – If σ has odd weight, then f1 (z) = sj is a column of G. Let z = z + ej , γ −1 (z ) = (l, r). Then γ(r − s(l)) = (0, t) for t ∈ T. Let f2 (z) = β(t). – If σ has even weight, then f1 (z) = s1 + sj for a uniquely determined column sj of G. Let z = z + e1 + ej and continue as in the preceding case. As an example, consider z = 1100100100011001. The syndrome is the sum of columns number 1, 2, 5, 8, 12, 13, 16 of G : f1 (z) = 10110. As σ = 1011 has weight 3, we have that f1 (z) = s11 is a column of G. It follows z = 1100100100111001 ∈ H 4 . Then l = 2013, r = 0213, s(l) = 0033, r − s(l) = 0220 ∈ γ −1 (0, T ) as promised. Applying γ and β yields f2 (z) = e6 + e7 : f (z) = (f1 (z)f2 (z)) = 10110110. This can be adapted to obtain the covering function g describing the factorization H4 /P4 of the shortened codes: Let z ∈ F15 2 . Add a parity check bit in the beginning to obtain z ∈ F16 of even weight. Then 2 . g(z) = (g1 (z)g2 (z)) = (z · r2 , z · r3 , z · r4 , z · r5 f2 (z )) ∈ F4+3 2 This function g = (g1 , g2 ) is the covering function of the ﬁrst factorization H4 /P4 and constitutes the ﬁrst ingredient in the construction of COV (2, 23, 8) (family (4) in the beginning of Section 6). To give an example of how the function
Constructing Good Covering Codes for Applications in Steganography
19
works, let z = 110000010001100. Then z = 1100000100011001. Application of f as before yields f (z ) = 10010011. Now g(z) is obtained by removing the ﬁrst bit: g(z) = 0010011. 8.2
The Factorization A/H 3 and Its Covering Function
This factorization has length 8 and dimension 3. Here H 3 is the extended Hamming code [8, 4, 4]2 again. Using its generator matrix as given in the beginning of the present section, we can write the corresponding covering function as h(y) = (h1 (y), h2 (y)), where y ∈ F82 and h1 (y) = y1 + · · · + y8 , h2 (y) = (y1 + y6 + y7 + y8 , y2 + y5 + y7 + y8 , y3 + y5 + y6 + y8 ). 8.3
Message Extraction Algorithm
We are now ready to describe the algorithm using which the recipient can extract the secret message. Since we are using a covering COV (2, 23, 8), we extract 8 secret message bits from a block of 23 pixels. Using (3), the covering function of a COV (2, 23, 8) is g ∨ h, concretely (g ∨ h)(x, y) = (g1 (x), h1 (y), g2 (x) + h2 (y)) ∈ F82 , 8 where, of course, x ∈ F15 2 , y ∈ F2 . To complete the description of the steganographic scheme, we need to explain the embedding mechanism.
8.4
Message Embedding Algorithm
Here, we describe the action of the embedder whose task is to hide 8 message bits in a cover image block consisting of 23 pixels by modifying at most 2 LSBs. be given such that f (x, y) = (g ∨ h)(x, y) = (a, b, c) ∈ F4+1+3 Let (x, y) ∈ F15+8 2 2 and let (A, B, C) ∈ F4+1+3 be the section of the secret message that we wish to 2 embed. We need to describe how to change (x, y) in at most 2 coordinates such that the resulting bitstring is mapped to (A, B, C). Naturally, we use matrix G above and its submatrix G obtained by omitting the ﬁrst row of G. The linear mapping h is based on matrix ⎛ ⎞ 11111111 ⎜ 10000111 ⎟ ⎟ H =⎜ ⎝ 01001011 ⎠ . 00101101 Observe that the columns of G are all quadruples, starting with the 0 quadruple and the columns of H are all quadruples that start with 1. We can describe the embedding procedure. Number the columns of G from 0 to 15, those of H from 1 to 8.
20
J. Bierbrauer and J. Fridrich
– Assume b + B = 1, A = a. Let (1, c + C) be column number j of H. Change bit number j of y, leave x unchanged. – Assume b + B = 1, A = a. Choose j as above and choose i ≤ 15 such that a + A is column i of G . Change the ith bit of x and the jth bit of y. – Let B = b, A = a. Change y in two coordinates j1 and j2 such that the corresponding columns of H add to (0, c + C). – Let B = b, A = a. Consider the 8 pairs of columns of G that add to A + a. This corresponds to 7 vectors x1 , . . . , x7 at distance 2 from x and one vector x8 at distance 1 (the corresponding column of G being A = a). The values g2 (xi ) are all diﬀerent. Choose i such that g2 (xi ) + g2 (x) = C + c. This completes the description of a steganographic scheme based on family (4) for m = 4, or COV (2, 23, 8).
9
Conclusion
In this paper, we show that certain families of nonlinear codes can achieve markedly better performance (higher embedding eﬃciency) for applications in steganography than simple linear codes currently in use. We construct the codes using the blockwise direct sum of code factorizations. For practitioners, we provide a detailed description of one selected family of covering functions. The smallest open problem in constructing good families of coverings is the existence of COV (2, 12, 6). A more general problem is to use the known families of good Z4 linear codes for the construction of covering codes and covering functions. An even more ambitious aim is to bring algebraicgeometric codes into play. Finally, the theory of covering functions should not be restricted to the binary case.
References 1. Bierbrauer, J.: Introduction to Coding Theory. Chapman and Hall, CRC Press (2005) 2. Bierbrauer, J.: Crandall’s problem (unpublished, 1998), available from, http://www.ws.binghamton.edu/fridrich/covcodes.pdf 3. Bierbrauer, J.: NordstromRobinson code and A7 geometry. Finite Fields and Their Applications 13, 158–170 (2007) 4. Cachin, C.: An informationtheoretic model for steganography. In: Aucsmith, D. (ed.) IH 1998. LNCS, vol. 1525, pp. 306–318. Springer, Heidelberg (1998) 5. Carnielli, W.A.: On covering and coloring problems for rook domains. Discrete Mathematics 57, 9–16 (1985) 6. Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. North Holland, Amsterdam (1997) 7. Crandall, R.: Some notes on steganography. Posted on steganography mailing list (1998), http://os.inf.tudresden.de/∼ westfeld/crandall.pdf 8. Davydov, A.A.: New constructions of covering codes. Designs, Codes and Cryptography 22, 305–316 (2001)
Constructing Good Covering Codes for Applications in Steganography
21
9. Davydov, A.A., Faina, G., Marcugini, S., Pambianco, F.: Locally optimal (nonshortening) linear covering codes and minimal saturating sets in projective spaces. IEEE Transactions on Information Theory 51, 4378–4387 (2005) 10. Davydov, A.A., Marcugini, S., Pambianco, F.: Minimal 1 saturating sets and complete caps in binary projective spaces. Journal of Combinatorial Theory A 113, 647–663 (2006) 11. Etzion, T., Greenberg, G.: Constructions for perfect mixed codes and other covering codes. IEEE Transactions on Information Theory 39, 209–214 (1993) 12. Etzion, T., Mounits, B.: Quasiperfect codes with small distance. IEEE Transactions on Information Theory 51, 3938–3946 (2005) 13. Fridrich, J., Goljan, M., Soukal, D.: Eﬃcient Wet Paper Codes. In: Barni, M., HerreraJoancomart´ı, J., Katzenbeisser, S., P´erezGonz´ alez, F. (eds.) IH 2005. LNCS, vol. 3727, pp. 204–218. Springer, Heidelberg (2005) 14. Fridrich, J.: FeatureBased Steganalysis for JPEG Images and its Implications for Future Design of Steganographic Schemes. In: Fridrich, J. (ed.) IH 2004. LNCS, vol. 3200, pp. 67–81. Springer, Heidelberg (2004) 15. Fridrich, J., Goljan, M., Du, R.: Steganalysis Based on JPEG Compatibility. In: Tescher, et al. (eds.) Proc. SPIE Multimedia Systems and Applications IV, SPIE, vol. 4518, Denver, CO. pp. 275–280 (August 2001) 16. Gabidulin, E.M., Davydov, A.A., Tombak, I.M.: Codes with covering radius 2 and other new covering codes. IEEE Transactions on Information Theory 37, 219–224 (1991) 17. Galand, F., Kabatiansky, G.: Information hiding by coverings. In: Proceedings of the IEEE Information Theory Workshop 2004, pp. 151–154 (2004) 18. Goppa, V.D.: Codes on algebraic curves. Soviet Math. Doklady 24, 170–172 (1981) 19. Hammons Jr, A.R., Kumar, P.V., Calderbank, A.R., Sloane, N.J.A., Sol´e, P.: The Z4 linearity of Kerdock, Preparata, Goethals and related codes. IEEE Transactions on Information Theory 40, 301–319 (1994) 20. Honkala, I.S.: On (k, t)subnormal covering codes. IEEE Transactions on Information Theory 37, 1203–1206 (1991) 21. Kaikkonen, M.K., Rosendahl, P.: New covering codes from an ADSlike construction. IEEE Transactions on Information Theory 49, 1809–1812 (2003) 22. Ker, A.: A General Framework for Structural Analysis of LSB Replacement. In: Barni, M., HerreraJoancomart´ı, J., Katzenbeisser, S., P´erezGonz´ alez, F. (eds.) IH 2005. LNCS, vol. 3727, pp. 296–311. Springer, Heidelberg (2005) 23. Nordstrom, A.W., Robinson, J.P.: An optimum nonlinear code. Information and Control 11, 613–616 (1967) ¨ 24. Osterg˚ a, P.: A coloring problem in Hamming spaces. European Journal of Combinatorics 18, 303–309 (1997) 25. Preparata, F.P.: A class of optimum nonlinear doubleerrorcorrecting codes. Information and Control 13, 378–400 (1968) 26. Provos, N.: Defending Against Statistical Steganalysis. In: 10th USENIX Security Symposium, Washington, DC (2001) 27. Sallee, P.: Model Based Steganography. In: Kalker, T., Cox, I., Ro, Y.M. (eds.) IWDW 2003. LNCS, vol. 2939, pp. 154–167. Springer, Heidelberg (2004) 28. Simmons, G.J.: The Prisoners’ Problem and the Subliminal Channel. In: Chaum, D. (ed.) Advances in Cryptology: Proceedings of Crypto 1983, pp. 51–67. Plenum Press (1984)
22
J. Bierbrauer and J. Fridrich
29. Stinson, D.R.: Resilient functions and large sets of orthogonal arrays. Congressus Numerantium 92, 105–110 (1993) 30. Struik, R.: Covering Codes, Ph.D. dissertation, Eindhoven (1994) 31. Wan, Z.X.: Quaternary codes. World Scientiﬁc, Singapore (1997) 32. Westfeld, A.: High Capacity Despite Better Steganalysis (F5–A Steganographic Algorithm). In: Moskowitz, I.S. (ed.) IH 2001. LNCS, vol. 2137, pp. 289–302. Springer, Heidelberg (2001) 33. Zelinka, B.: On kdomatic numbers of graphs. Czechoslovak Math. Journal 33, 309–311 (1983)
On the Use of Bhattacharyya Distance as a Measure of the Detectability of Steganographic Systems Valery Korzhik1 , Hideki Imai2 , Junji Shikata3 , Guillermo MoralesLuna4, , and Ekaterina Gerling1 1
3
State University of Telecommunications, St. Petersburg, Russia
[email protected] 2 Chuo University and National Institute of Advanced Industrial Science and Technology (AIST), Japan
[email protected] Graduate School of Environment and Information Science, Yokohama National University, Japan
[email protected] 4 Computer Science, CINVESTAVIPN, Mexico City, Mexico
[email protected] Abstract. It is very common to use the notion of relative entropy (or KullbackLeibler divergence) as a measure for the discrimination diﬃculty among the hypotheses testing of presence and absence within a steganographic system. Relative entropy is not a symmetric function and sometimes it is very hard to compute its values. We propose to customize the notion of Bhattacharyya distance to the solution of the same problem. The main properties of Bhattacharyya distance are presented. We show applications of this new steganographic system security criterion within the model with a Gaussian colored covertext and within spreadspectrum watermarking by a white Gaussian sequence. Keywords: Steganography, Bhattacharyya distance, spread spectrum signal, detectability of stegosystems.
1
Introduction
It is very common to think that a natural way of deﬁning the detectability of a steganographic (SG) system is in terms of relative entropies (or KullbackLeibler divergence) D (PS PX ), D (PX PS ), where PS is the probability distribution on a covertext S and PX is the probability distribution on a stegotext X (C. Cachin pioneered the use of such criterion for SG systems [1]). In the case of any two continuous distributions P , Q, the relative entropies can be presented as in [2] P (ω) P (ω) log D (P Q) = dω (1) Q(ω) Ω where Ω is the space of possible measurements.
Dr. MoralesLuna acknowledges the support of Mexican Conacyt.
Y.Q. Shi (Ed.): Transactions on DHMS III, LNCS 4920, pp. 23–32, 2008. c SpringerVerlag Berlin Heidelberg 2008
24
V. Korzhik et al.
The eﬃciency of hypothesis testing can be characterized by two probabilities: the probability Pm of missing (when the stegosignal has been embedded but the detector wrongly declares its absence) and the probability Pf a of false alarm (when the stegosignal has not been embedded but the detector wrongly declares its presence). A lower bound [3,4] for the Bayesian probability error Pe = π0 Pf a + π1 Pm , where π0 and π1 are priors of the hypotheses, is J Pe > π0 π1 exp − 2 where J = D (PS PX ) + D (PX PS ). It follows from Information Theory [2] that, for any hypothesis testing rule, the following inequalities hold Pf a 1 − Pf a (2) Pf a log + (1 − Pf a ) log ≤ D (PS PX ) 1 − Pm Pm Pm 1 − Pm (3) Pm log + (1 − Pm ) log ≤ D (PX PS ) 1 − Pf a Pf a For Pf a = 0, we get from relation (2), Pm ≥ 2−D(PS PX ) . We can see from (2), (3) that the SG system is unconditionally secure (or perfectly undetectable) if D (PS PX ) = 0 = D (PX PS ). It has been proved [4] that the relative entropies D (PS PX ) , D (PX PS ), given by (1), can be calculated for general zeromean (N dimensional) Gaussian distributions PS , PX , as follows 1 1 D (PX N PS N ) = − ln det (IN + δR) + tr (δR) 2 2 1 1 ˜ ˜ + tr (δ R) D (PS N PX N ) = − ln det IN + δ R (4) 2 2 where IN is the (N × N )identity matrix, tr(·) denotes the trace of a matrix, RX N , RS N are the covariance matrices of the Gaussian N dimensional random vectors X N (stegotext) and S N (covertext), respectively, and ˜ = RS N R−1N − IN . , δR δR = RX N R−1 N − IN S
X
For a good stegosystem, whenever RX N is close to RS N , the parameter J can be accurately approximated [4] by the relation 1 (5) J ≈ tr (δR)2 2 It can be seen from (5) that even for the fortunate case of a “good” stegosystem with Gaussian covertext distribution we will face a serious problem under the calculation of J by (5). Moreover, it has been shown in [5] that the Gaussian distribution is not the case for typical images and then a calculation of relative entropy by (1) poses a very hard problem. In Section 2 we propose another measure of the detectability of stegosystems based on Bhattacharyya distance (BD). We present its properties and explicit forms for some probability distributions. In Section 3 we describe some applications of a new criterion to estimate the security for the stegosystem (SGS) based on additive spreadspectrum watermarking. Section 4 concludes the paper.
On the Use of Bhattacharyya Distance
2
25
BD and Its Main Properties
Thomas Kailath pioneered in applying BD to an estimation of the error probability. BD has been eﬀectively used by Kailath [6] as a technique to estimate the probability of error for an optimal receiver under the condition of binary signaling over noisy channel. Later this criterion was used by many researchers in communication theory [7,8]. Accordingly with [6], BD is deﬁned between two probability distributions PS and PX over a space Ω as DB (PS , PX ) = − ln ρB (PS , PX ) where ρB (PS , PX ) =
PX (ω)PS (ω) dω.
(6)
(7)
Ω
From (6), (7), it follows that DB (PS , PX ) = DB (PX , PS ), thus DB is a symmetric function, and although it does not satisfy the triangle inequality [6], the slight variant 1 − ρ2B does indeed satisfy it. Therefore under this criterion it is not necessary to calculate the two values D (PX PS ) and D (PS PX ) as was the case for the criterion based on relative entropy [4]. (The triangle inequality can be useful in the case of double embedding in diﬀerent nodes of a computer network, for instance.) If prior probabilities π0 and π1 coincide (e.g. π0 = π1 = 1/2) then the Bayesian error probability Pe under the condition of optimal hypothesis testing is bounded [6] as 1 2 1 ρ (PX , PS ) ≤ Pe ≤ ρB (PX , PS ) 4 B 2
(8)
For the special case PX = PS we obtain ρB (PX , PS ) = 1 and DB (PX , PS ) = 0. This means that the SGS is unconditionally secure. We will say that it is εsecure if DB (PX , PS ) = ε. Then in this case, Pe ≥
1 exp (−2ε) . 4
(9)
Inequality (9) states that if DB (PX , PS ) is very close to 0 or ρB (PX , PS ) is very close to 1 then the stegosystem occurs almost secure. If X N , S N are N dimensional Gaussian random vectors then [6] DB (PX N , PS N ) =
1 T (v N − vS N ) R−1 (vX N − vS N ) + 8 X 1 det R ln √ 2 det RX N det RS N
(10)
where vX N , vS N are the mean value vectors and RX N , RS N are the covariance matrices of the N dimensional random vectors X N , S N , respectively, the superindex T denotes matrix transposition and R = 12 (RX N + RS N ).
26
V. Korzhik et al.
In the particular case when vX N = vS N (which holds whenever the vectors X N , S N have zeromean) we get from (10) DB (PX N , PS N ) =
det R 1 ln √ . 2 det RX N det RS N
(11)
In another particular case, when RX N = RS N = R, we get from (10) DB (PX N , PS N ) =
1 (v N − vS N )T R−1 (vX N − vS N ) . 8 X
If the space Ω is discretevalued, we may rephrase (7) as
PX N (ω)PS N (ω). ρB (PX N , PS N ) = ω∈Ω
The upper bound in (8) can be improved in general [8] if the modiﬁed Bhattacharyya coeﬃcient ρB (PX N , PS N ) is used in (6), where 1−s s PX ρB (PX N , PS N ) = min N (ω)P N (ω) dω S 0≤s≤1
3
Ω
Design of an almost Secure SGS Invariant to Covertext Distribution
Let us consider the conventional spreadspectrum (SS) embedding in the additive manner (12) X N = aS N + W N where the host signal S N is a Gaussian random vector with independent identically distributed components, i.e. S N ∼ N (0, σS IN ) scaled by a, and W N is 2 also chosen as a Gaussian zero mean i.i.d. random vector with σW . If variance the coeﬃcient a is chosen as α = 1 −
D 2 2σS
2 and σW = D 1−
D 2 4σS
then the
embedding distortion equals D and D (PX N PS N ) = 0 [4]. This means that such SGS is a perfectly undetectable stegosystem. But it is very impractical to model covertext as an i.i.d. random vector. If we assume that S N is a correlated source then, as it has been proved in [4], a perfectly undetectable SGS can be achieved after an application to S N of the KarhunenLo`eve transform (KLT), an additive scaled embedding(as in (12)) into the KLT coeﬃcients and a recovering of the stegotext by the inverse KLT transform. However, an application of KLT requires the knowledge of the covariance matrix of S N . Obviously, the number of real images that can appeared as covertext is huge and, even though there exists the average covariance matrix for typical images, it is impossible to take it for performance evaluation of KLT in a particular image. Let us consider the embedding function in the form (12) for a stegotext with arbitrary probability distribution when D and N are chosen in a such a way that
On the Use of Bhattacharyya Distance
27
at least an εsecure SGS can be provided, i.e. with either D (PX N PS N ) = ε or DB (PX N , PS N ) = ε. In this case the attacker must distinguish between Gaussian noises created by the embedding process from those introduced during the image acquisition itself [5]. Generally, a device noise have nonGaussian distribution [9] and it requires the use of embedding noise approximating a device noise closely as possible. We consider in the current paper the model with colored Gaussian covertext and i.i.d. Gaussian embedding noise. The main goal of our investigation is to ﬁnd out how the correlation of stegotext aﬀects on the security of such SGsystems. Let us assume that the covariance matrix of the Gaussian covertext S N is ⎤ ⎡ 1 r12 . . . r1,N −1 r1N ⎢ r21 1 . . . r2,N −1 r2N ⎥ ⎥ ⎢ ⎥ .. .. . .. 2 ⎢ .. RS N = σS ⎢ .. ⎥ . . . . ⎥ ⎢ ⎣ rN −1,1 rN −1,2 . . . 1 rN −1,N ⎦ rN 1 rN 2 . . . rN,N −1 1 , and S(i) is the ith sample of the where for each i, j ≤ N , rij = E(S(i)S(j)) 2 σS covertext. Then it is easy to see that the covariance matrix of the stegotext X N after the embedding by (12) will be ⎤ ⎡ d r12 . . . r1,N −1 r1N ⎢ r21 d . . . r2,N −1 r2N ⎥ ⎥ ⎢ ⎥ . .. .. .. 2 −1 ⎢ .. RX N = σS d ⎢ .. ⎥ . . . . ⎥ ⎢ ⎣ rN −1,1 rN −1,2 . . . d rN −1,N ⎦ rN 1 rN 2 . . . rN,N −1 d −2 D where d = 1 − 2σ . 2 S
In the particular case of exponential correlation, when S N is an AR(1) zero mean sequence, the following Toeplitz matrix RS N and “almostToeplitz” matrix RX N result: ⎡ ⎤ 1 r . . . rN −2 rN −1 ⎢ r 1 . . . rN −3 rN −2 ⎥ ⎢ ⎥ ⎢ .. .. ⎥ . .. . . RS N = σS2 ⎢ .. ⎥ . . . . ⎢ ⎥ ⎣ rN −2 rN −3 . . . 1 r ⎦ rN −1 rN −2 . . . r 1 (13) ⎤ ⎡ d r . . . rN −2 rN −1 ⎢ r d . . . rN −3 rN −2 ⎥ ⎥ ⎢ .. .. ⎥ . .. . . −1 2 ⎢ RX N = d σS ⎢ .. ⎥ . . . . ⎥ ⎢ N −2 N −3 ⎣r r ... d r ⎦ d rN −1 rN −2 . . . r Unfortunately it is not easy to calculate the relative entropy by (4) (and even an approximation by (5)) for these matrices. If we assume the Bhattacharrya
28
V. Korzhik et al.
distance as a diﬀerence measure between the two Gaussian zero mean colored distributions PX N , PS N we get, by (6), (8), (11), √ 1 2 1 det RX N det RS N Pe ≥ ρ = (14) 4 4 det 12 (RX N + RS N ) where RX N , RS N are given in (13). After simple transforms and taking into account (13) we get ⎡ −1 ⎤ t r . . . rN −2 rN −1 ⎢ r t−1 . . . rN −3 rN −2 ⎥ ⎢ ⎥ 1 . .. . . .. .. ⎥ 2 ⎢ R = (RX N + RS N ) = tσS ⎢ .. ⎥ . . . . ⎢ ⎥ 2 ⎣ rN −2 rN −3 . . . t−1 r ⎦ rN −1 rN −2 . . . r t−1 −1
where t = 1+d2 . The determinant of the Toeplitz matrix RS N can easily be calculated [10] as det RS N = σS2N (1 − r2 )N −1 . (15) For the almostToeplitz matrices RS N and R, their determinants can be found [7] as N N aN , det R = tσS2 bN (16) det RX N = d−1 σS2 where the parameters aN and bN are calculated through the recurrence formulas α0 = 1 α1 = d + (d − 2)r2 ∀n = 2, . . . , N − 1 : αn = (d + (d − 2)r2 )αn−1 − ((d − 1)r)2 αn−2
(17)
aN = dαN −1 − ((d − 1)r)2 αN −2 and β0 = 1 β1 = d1 + (d1 − 2)r2 ∀n = 2, . . . , N − 1 : βn = (d1 + (d1 − 2)r2 )βn−1 − ((d1 − 1)r)2 βn−2
(18)
bN = d1 βN −1 − ((d1 − 1)r)2 βN −2 with d1 = t−1 . Example. Let us take r = 0.5 and N = 200. Then by (14), (15) and (16), ρ2 = 0.856.
Although the lower bound for Pe has been exhibited here in a closed form, it is still diﬃcult to calculate it by the recurrence formulas (17), (18) for large N . It is possible [11] to change the recurrence equations (17) into an explicit form αn = c1 xn1 + c2 xn2
(19)
On the Use of Bhattacharyya Distance
29
Table 1. The resulting ρ2 by (23) for d = 1.01 and diﬀerent r and N r 0.5 0.9 0.95 0.99
50 1 0.961 0.841 0.062
100 0.999 0.922 0.705 0.004
N 200 0.999 0.849 0.495 1.23×10−6
500 0.997 0.664 0.171 4.82×10−13
where x1 , x2 are the roots of the quadratic equation x2 − (d + (d − 2)r2 )x + ((d − 1)r)2 = 0
(20)
and the coeﬃcients are c1 =
(d + (d − 2)r2 ) − x2 x1 − x2
,
c2 = 1 − c 1 .
The explicit formula for the second recurrence relation (18) can be found in a similar manner. But unfortunately for large N , relations (19), (20) pose hard calculations. For a “good” SGsystem, we may expect d ≈ 1, hence ((d − 1)r)2 > 1, this probability can be approximated as P ≈ Q η−1 ηw η = ηa . We may express now the parameter d presented in (23) in terms of ηw as −2 −2 2 1 4ηw D = 1− = (26) d= 1− 2 2 2σS 2ηw (2ηw − 1)
On the Use of Bhattacharyya Distance
31
Example. Let us take ηw = 100, ηa = 70 and N = 500. Then we get by (26) that d = 1.01 and t = 0.995. The calculation by (23) ρ2 = 0.664. √ for r = 0.9 gives −4 On the other hand we have, by (25), that P ≈ Q( 11.6) ≈ 3 × 10 for N0 = 5. This means that we are able to embed 100 bits of information in a secure manner (because ρ2 is close to 1) and simultaneously to get enough reliability of these bits extraction by the legal user.
For a blind decoder, the decision about the information bit ˆb is taken as Λ˜ =
N0
n=1
˜ X(n)W (n) ⇒ ˆb =
0 if Λ˜ ≥ 0 1 if Λ˜ < 0
It can be proved [13] that the error probability for blind decoder can be approximated as (4ηw − 1) ηa ˜ (27) N0 P ≈Q 4 (ηw − ηa + ηw ηa ) ηw N0 If ηw >> 1 we get from (27), P˜ ≈ Q ηw . Example. Under the same conditions as in previous example, we get the probability P˜ ≈ 1.2×10−2 if only N0 = 500. This means that one bit can be embedded
in an “almost secure” manner (since ρ2 is close to 1). In order to increase the number of bits embedded into a covertext for the case of a blind decoder, it is necessary to use the so called informed encoder as, for instance, improved spread spectrum technique (ISS) [14] or quantized projection technique (QP) [15]. However both of these techniques should be revised in terms of steganography. We are going to consider this problem in the near future.
4
Conclusion
In this paper, a novel criterion of undetectability of SGS based on Bhattacharyya distance has been proposed. We state that for some models of SGS, this notion is more convenient for calculations and analysis than the commonly used relative entropy criterion. In fact, the new criterion is based on a symmetric measure and gives both lower and upper bounds for the Bayesian probability error for optimal hypothesis testing. We show an application of this criterion to performance evaluation for optimal detecting of the SGS with Gaussian exponential correlated covertext and additive white noise watermark. The last model of covertext embedding is of, both theoretical and practical, interest to steganography. In fact, we cannot provide perfectly undetectable SGS in practice because it is not known exactly the probability distribution of the covertext. What we have to do is just the design of an almost undetectable SGS, which is robust to covertext distributions. Since stegotext as a rule may include device noises [5] that can be approximated by colored Gaussian noise, the problem of SGS
32
V. Korzhik et al.
detecting consists in the discrimination of two Gaussian processes. Although the correlation matrix of a device noise is not necessary exponential, we may assume that formula (23) diﬀers not so much from the real situation whenever the correlation of the adjacent sample in the covertext is not too large (say, at most 0.9) and the distortion due to embedding is small. In these conditions, we are able to design a real SGS with scaled stegotext and additive white noise watermark that is both secure and reliable, at least against additive noise attack. Of course the assumption about informed decoder is too restrictive in practice whereas the use of blind decoders results in very lower data transmission rate. Therefore there is an open problem consisting on how to adapt informed encoder (as ISS or QP) into SGsystems.
References 1. Cachin, C.: An informationtheoretic model for steganography. In: Aucsmith, D. (ed.) IH 1998. LNCS, vol. 1525, pp. 306–318. Springer, Heidelberg (1998) 2. Cover, T.M., Thomas, J.A.: Elements of Information Theory. John Wiley, Chichester (1991) 3. Poor, H.V.: An Introduction to Signal Detection and Estimation. Springer, Heidelberg (1994) 4. Wang, Y., Moulin, P.: Steganalysis of blockstructured stegotext. In: Security, Steganography, and Watermarking of Multimedia Contents. SPIE Proceedings, vol. 5306, San Jose, California USA, pp. 477–488 (2004) 5. Sallee, P.: Modelbased steganography. In: Kalker, T., Cox, I., Ro, Y.M. (eds.) IWDW 2003. LNCS, vol. 2939, pp. 154–167. Springer, Heidelberg (2004) 6. Kailath, T.: The divergence and Bhattacharyya distance measures in signal selection. IEEE Trans. Commun. Tech. 15, 52–60 (1967) 7. Korzhik, V.I., Fink, L.M.: Errorcorrecting Codes on Channels with Random Structure (in Russian), Svyaz, Moscow (1975) 8. Van Trees, H.L.: Detection, Estimation, and Modulation Theory. Parts III. John Wiley, Chichester (1973) 9. Huang, J., Mumford, D.: Statistics of natural images and models. In: Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 541–547 (1999) 10. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1983) 11. Hall, M.: Combinatorial Theory. John Wiley & Sons, Chichester (1986) 12. Korzhik, V., Lee, M.H., MoralesLuna, G.: Stegosystems based on noisy channels. In: IX Reuni´ on Espa˜ nola de Criptolog´ıa y Seguridad de la Informaci´ on, Universidad Aut´ onoma de Barcelona (2006) 13. Korzhik, V., MoralesLuna, G., Lee, M.H.: On the existence of perfect stegosystems. In: Barni, M., Cox, I., Kalker, T., Kim, H.J. (eds.) IWDW 2005. LNCS, vol. 3710, pp. 30–38. Springer, Heidelberg (2005) 14. Malvar, H.S., Florˆencio, D.: Improved spread spectrum: A new modulation technique for robust watermarking. IEEE Trans. on Signal Processing 51, 898–905 (2001) 15. P´erezFreire, L., Comesa˜ naAlfaro, P., P´erezGonz´ alez, F.: Detection in quantizationbased watermarking: performance and security issues. In: P.W. Wong, E.J. Delp (eds). Security, Steganography, and Watermarking of Multimedia Contents. SPIE Proceedings, vol. 5681, San Jose, California USA, pp. 721–733 (2005)
Secure Steganography Using Gabor Filter and Neural Networks Mansour Jamzad and Zahra Zahedi Kermani Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
[email protected],
[email protected] Abstract. The main concern of steganography (image hiding) methods is to embed a secret image into a host image in such a way that it causes minimum distortion to the host; to make it possible to extract a version of secret image from the host in such a way that the extracted version of secret image be as similar as possible to its original version (this should be possible even after usual attacks on the host image), and to provide ways of embedding secret images with larger size into a given host image. In this paper we propose a method that covers all above mentioned concerns by suggesting the idea of ﬁnding from an image data base, the most suitable host for a given secret image. In our method, the secret and host images are divided into blocks of size 4 × 4. Each block in secret image is taken as a texture pattern for which using Gabor ﬁlter, the most similar block is found among the blocks of host image candidates. Using this similarity criterion and Kohonen neural network, the most suitable host image is selected from an image database. Embedding is done by placing the blocks of secret image on their corresponding blocks in the selected host image. The location addresses of blocks in host that were replaced by blocks of secret image are saved. They are converted to a bit string that is embedded in DCT coeﬃcients of the hybrid image. Our experimental results showed a high level of capacity, robustness and minimum distortion when using standard images as secret and host images. Keywords: Steganography, Gabor Filter, Texture similarity, Kohonen Neural Networks, DCT, Image database.
1
Introduction
Recent progresses in digital communication has made it possible to use intelligent methods for secret communication. One such method is image hiding in which a secret image is hidden in a host or cover image. The modiﬁed host image that contains the secret image is referred to as hybrid (stego) image. There are several methods for hiding a secret image in a host image. Mainly they can be divided into methods that embed the secret image into the host
Miss Z.Zahedi Kermani obtained her MS in computer engineering in 2001 and parts of this work was accomplished during her graduate studies.
Y.Q. Shi (Ed.): Transactions on DHMS III, LNCS 4920, pp. 33–49, 2008. c SpringerVerlag Berlin Heidelberg 2008
34
M. Jamzad and Z.Z. Kermani
image in spatial domain and those that use transform domain. For spatial domain methods, the simplest methods are those that modify the least signiﬁcant bits of pixels in the host image [1,2]. The advantages of these methods are their simplicity but they are weak in resisting simple attacks such as compression, etc. In these methods the capacity of embedding a secret image is limited and an increase in capacity severely inﬂuences the visual quality of hybrid image. Image hiding techniques that are implemented in transform domain have made it possible to take advantage of features in human visual system [3,4]. These methods are more robust with respect to compression and some transforms, because they focus on the same features of image as compression techniques do. As another example, we can refer to [5] that uses the middle frequency coeﬃcients of DCT and the quantization table of JPEG to embed a secret image. Also in [6] the authors have used the embedded zero tree Wavelet (EZW) to encode a host image to embed a secret image. In [7] Wavelet transform is applied both on cover and secret image to produce their SPIHT (set partitioning in hierarchical trees) encoded version. Then the encoded cover image is used as the carrier for the encoded secret image. The spread spectrum techniques that are implemented in frequency domain, can provide high robustness regarding usual attacks. This is due to the fact that they consider the hidden message as a narrowband signal and spread it over a wider frequency band. One disadvantage of these methods is that, since they have to merge the key into a noisy pattern and then embed the merged data into the frequency domain coeﬃcients, this process may cause severe degradation in host image depending on the noisy pattern [8]. All these methods try to embed a given secret image into one particular cover image. The capacity and visual perception quality of ﬁnal hybrid image highly depends on the size and content of both the secret and cover images. In fact, increasing the size of secret image not only will reduce the quality of hybrid image but also will reduce its robustness with respect to general attacks. According to our survey on present methods, it seems that the main problem is their low capacity, because they do not have a preprocessing step to select the best suitable cover image for a given secret image. As a result, the capacity and visual perception of the hybrid image is limited depending on the size and content of secret image and the give host image. In addition they do not use the error control codes for improving the robustness of key. Generally, capacity, visual perception and resistance are three criteria that are used to compare the performance of image hiding methods. Figure 1 shows the relation between these three criteria. For example,if the ﬁrst criterion is assumed constant, and the second one is increased, then the third criterion decreases subsequently. Depending on the size and content of both secret and host images, the appropriate level of each criteria will be determined. Most image hiding method try to remain loyal to the assumption that the host image is ﬁxed, and by the time that the secret image becomes available, they will embed it into that particular host. Although in practice the above assumption might be a fact in some situations, but we can think of many other applications,
Secure Steganography Using Gabor Filter and Neural Networks
35
Fig. 1. Relation between three criterion: capacity, visual perception and resistance
where the aim is to have a secure method for embedding a secret image in any host, as long as the main concerns in image hiding is satisﬁed. Therefore, in this paper we proposed a method that assumes the freedom of selecting the host for a given secret image, because in image hiding, the host image acts as a carrier and its content is not important to us. In our method for a given secret image, the most suitable host is selected from an image database in such a way that it provides a balance level between capacity, visual perception and resistance (robustness). In addition we introduced an error control code to improve the robustness of a location address bit string used to retrieve the secret image from the hybrid image. We assume that the secret image is considered as a mosaic (blocks) of diﬀerent textures [9]. If these blocks are placed over their similar blocks in host image in a known order, then by having the location address of these blocks and their placement order in host image, retrieving the secret image will be like solving a puzzle of disordered pieces when one has the key that provides the order of putting parts together. Figure 2 shows a visual presentation of this idea. Our method assumes that the secret and cover images are of monochrome type. However, this method can be extend to color images as well. In this case,
Fig. 2. a) Host image, (b) Secret image. The 1st and 2nd block of secret image are replaced in location (2,2) and (30,5) of the host image, respectively.
36
M. Jamzad and Z.Z. Kermani
we can convert both the secret and cover images using Y C b C r color model and perform our method on the Y channel (e.g. monochrome version of the color image). The rest of this paper is organized as follows: In section 2 diﬀerent steps of our algorithm is described. In section 3 we evaluate the performance of our method. In section 4 it is shown how the secret image can be extracted in case the hybrid image is lost. In section 5 we describe how the performance of our method can be improved by increasing the number of host images. And ﬁnally we give our conclusion on this research.
2
Our Algorithm
We describe how to ﬁnd the best candidate host image from an image database in such a way that its content is most similar to that of a given secret image. Our image database contained 6 standard images of size 128 × 128, and the secret images were of size 64 × 64. The main idea of content based similarity is based on ﬁnding similar texture patterns (i.e. similar blocks of size 4 × 4) in secret and host image(s) and save their location addresses in host image(s) as a bit string. The reason for selecting block size of 4 × 4 is that it should be of a number as 2n , to ﬁt a ﬁx number of times into times into host and secret images that are assumed to be of size 2m , too. Some possible candidate values for n are 1, 2, 3or4, that provides the block size of 2 × 2, 4 × 4, 8 × 8 or 16 × 16, respectively. Texture similarities on blocks of size 2 × 2 and 16 × 16 are not reliable because of too few and too many possible combination of gray level values within the block. The reason of selecting block size of 4 × 4 instead of 8 × 8 was because it is easier to ﬁnd more perceptual similarities between textures of size 4 × 4. Therefore, replacing a block of size 4 × 4 in host with its most similar one from the secret image, produces less visible distortion to the host compared to block size of 8×8.
Fig. 3. Applying a bank of 12 Gabor ﬁlters with 4 angles and 3 scales on a secret image of size 64 × 64
Secure Steganography Using Gabor Filter and Neural Networks
37
As a similarity measure for textures we have used Gabor ﬁlter analysis provided in [9]. In this method the similarity is determined by comparison of a feature vector calculated for a block of size 4 × 4 in secret image and a set of feature vectors constructed for blocks of host images. The feature vector of host images of our image database are saved in a feature vector database. In the following sections we use the term block for a subimage of size 4 × 4. 2.1
Selecting Appropriate Parameters for Gabor Filter
We have implemented a bank of Gabor ﬁlters using diﬀerent scales and angles (i.e. parameters) [10]. Diﬀerent values for these parameters can be selected, but it has been shown that using six angles can provide a complete representation of the image. In our implementation we found that using 4 angles (i.e. 0, 45, 90 and 135 degrees) and 3 scales (i.e. 1,2 and 3) provides acceptable performance in determining texture similarities. Four angles and three scales produce 12 Gabor ﬁlters that are applied on the secret image. Figure 3 shows the procedure of applying Gabor ﬁlter on a secret image. Each of 12 images in Fig.3(a) shows the real value of Gabor ﬁlter that is mapped in the gray scale range of [0 − 255] for visualization purpose. Fig 3(b) is the secret image and the tile images on Fig 3(c) are the results of convolving the corresponding Gabor ﬁlters with a secret image. The procedure shown in Fig 3 is applied on all candidate host images in our image database as well. In this way, as shown in Fig 3(c) for each candidate host image, we obtain a set of 12 images that are the result of convolving Gabor ﬁlters with that host image. 2.2
Creating a Database for Feature Vectors
Comparison of texture similarity between secret and host images is based on feature vector comparison. The secret and host images are divided into blocks. For each block, the mean and standard deviation of its corresponding blocks in each of 12 ﬁltered images of Fig 3(c) is calculated. In this way, a 24 component feature vector is obtained. Fig 4 shows a visualization of this procedure. Within this procedure, we have calculated the above mentioned feature vector for all host images in our image database and created a feature vector database. Assuming to have N images of size 256 × 256 in the image database, the number of entries for feature vector database will be equal to N × ((256 × 256)/(4 × 4)) = N × 4096. 2.3
Using Kohonen Neural Network as a Mean of Fast Search
Due to the large number of records in feature vector database, we must have an eﬃcient method for indexing and searching in it. Therefore, the input records of this database were fed into a Kohonen neural network (NN) that is a self organizing neural network. At the beginning, there was no particular structure among the records in this database, but after training, the texture patterns in all host images were grouped in a cluster. The training algorithm uses a mechanism called ”selecting the winning node”. In this mechanism, for each input
38
M. Jamzad and Z.Z. Kermani
Fig. 4. Visualization of the procedure that calculates a 24 component feature vector. The component vector is deﬁned as (m1,m2,...m12,v1,v2,...v12).
feature vector, the Euclidean distance between it and all nodes is calculated. The node with minimum distance is selected to be the winning node (e.g. this is the matching procedure of an input feature vector with a cluster of feature vectors in Kohonen NN [11]. Then the weight of this winning node and its neighbors are updated. By implementing this algorithm on all feature vectors in database, the feature vectors will be grouped in such a way that those close to each other will always activate the same node. The initial learning rate of this network was 1, and the feature vector records were given to the network for training purpose, eight times, where the learning rate was reduced in half each time. 2.4
How to Find the Best Host Image for Embedding
We have used the above mentioned feature vectors to ﬁnd the most similar texture in image database. For each block in secret image, its feature vector is calculated and is given to the neural network. At network’s output, only one node is activated. This node indicates the index of a group of similar blocks in the image database. In this group, by using the feature vector distance measure, the nearest block of an image in database to the block of secret image is determined. This procedure is carried on for all blocks of the secret image. At the end, the image in database having the most number of similar blocks, is chosen to be the host image. Figure 5 shows an illustration of this procedure that shows the Boat image was the most suitable to host the Jet secret image. Although the quality of the stegoimage (hybrid image) highly depends on the host image selected from the database, but since this selection is done based on a similarity measure, therefore, the quality of stegoimage depends on the number
Secure Steganography Using Gabor Filter and Neural Networks
39
Fig. 5. Illustration of the procedure for selecting the most suitable host image for a given secret image
of images and their variety made available in image database. In practice, the users of such systems can carefully provide a class or family of images in database such that it could give a high level of similarity to a given class of secrete images. However, if we add M images (each having K, 4 × 4 blocks) to our existing database, then the training time of NN will increase linearly with a factor of M × K. However, since training is done only once, this increase of time can be acceptable. To evaluate the increase of time in searching for the most similar image in the database, we refer to the process of selecting the most similar image as described in above. In this process, for each block of secret image, only one node in NN is activated. Therefore this part does not require any additional time. However, each activated node in NN refers to a list of images in which a block most similar to the examining block of the secret image was found. It is clear that if the number of images in database increases, this list will be longer (more number of images will appear in this list). When the above procedure is carried on for all K blocks of secret image, we will have K lists, each containing image names that contain blocks most similar to a corresponding block of the secrete image. If the number of images in database is increased, the number of elements in these lists will increase linearly. The ﬁnal step of ﬁning the most similar image from database, is to go through all these lists and ﬁnd the image with maximum number of repetition (e.g. the image with most number of similar blocks to the blocks of secret image). As a result, at this step, we will expect to have a linear increase in search time in these lists. 2.5
How to Hide and Retrieve the Secret Image
After choosing the host image, for each block in secret image, the most similar block to it in host image is found and is replaced with that block of secret image. The position (location address) of this block in host image is saved. This procedure is repeated for all blocks in the secret image. At the end of this procedure, we have a modiﬁed host image in which the entire secret image is
40
M. Jamzad and Z.Z. Kermani
embedded. At this stage, the sequence of above mentioned location addresses is saved into a location bit string. The image obtained in this step is called ﬁrst step hybrid image. The rest of hiding procedure is summarized as follows: 1. Apply DCT with block size of 8 × 8 on the ﬁrst step hybrid image. 2. Apply Hamming code to the location address bit string. The reason for using the Hamming code is due to its ability to recover the error bits in the extracted location address bit string. This procedure will improve the security of extracting the secret image from the stegoimage, in case of degradation imposed on it. 3. Choose a seed for a random number (key) and construct a sequence of location addresses. These addresses indicate the position of elements (8 × 8 blocks) of DCT in ﬁrst step hybrid image, in which bits of secured location bit string (e.g. as described in step 2) will be embedded. 4. Modify middle frequencies of DCT coeﬃcients in randomly selected blocks to embed bits of location address bit string. The reason for selecting middle frequencies is that these frequencies are less likely to be modiﬁed by compression methods. The number of DCT coeﬃcients in the middle frequencies need to be changed depends on the number of bits needed to represent the secured location address. 5. Apply inverse DCT transform to obtain the modiﬁed host image (ﬁnal hybrid image) which contains the secret image. In retrieval stage, in order to extract the secret image, we apply DCT on ﬁnal hybrid image. Then using the same key, we ﬁnd the addresses of all blocks which DCT coeﬃcients were modiﬁed to embed the location address bit string. In this way, the bit string that contains the location addresses is retrieved. Thus, those blocks in host image that contain the blocks of secret image, are determined. As a result the entire secret image is extracted.
3
Performance Evaluation of Our Method
Our algorithm was implemented using Visual C++ on a PC with Pentium II processor of 500 MHz. The image database contained 65 images of ﬁxed size 128 × 128. The secret image was of size 64 × 64. All images were 8 bit gray scale. For evaluation purpose, we used PSNR measure that is deﬁned as follows: L2 M SE
(1)
N 1 (xi − x¯i )2 N i=1
(2)
P SN R = 10 log10 M SE =
In the above equations, L is the maximum gray level value, which is 255 for 8 bit gray scale image. xi is the real value of the signal and x¯i is the signal value after modiﬁcation. N is the total number of signals.
Secure Steganography Using Gabor Filter and Neural Networks
41
The amount of error in extracted signal (i.e. bit string of location address) is measured by Bit Error Rate (BER) that is equal to the number of error bits in extracted signal divided by total number of bits in original location address bit string. In our evaluations, we considered the eﬀect of BER on three features such as capacity, perceived quality and robustness of hybrid images, as described in following.
Fig. 6. An example of selecting three candidate images to host a secret image. The PSNR was 30, 28 and 29 for images in (a),(b) and (c), respectively. Images (e),(f) and (g) show the host image in which the secret image is hidden.
3.1
Performance of Selecting the Host Image
Selecting the appropriate host image highly depends on the variety of images available in image database. We shall note that there is no need to have a host image similar to the secret image or even there is no need to have similar objects in host and secret images. Figure 6 shows the performance of our algorithm by selecting diﬀerent host images. According to PSNR, Fig 6 (a), (c) and (b) are the 1st, 2nd and 3rd candidates for the given secret image, respectively. Figures (d),(e) and (f) show the host images in which the same secret image is hidden. In fact, MSE increases for candidate host images that have lower similarity with the secret image while PSNR decreases in such cases.
42
3.2
M. Jamzad and Z.Z. Kermani
Performance with Respect to Capacity and Comparison with Related Works
The capacity of data hiding increases proportional to the increase in the variety of textures available in host image. Such host images give higher PSNR ratio compared to images having less variety in textures. As described in section 2.5, in our method the location address bit string that is saved in middle frequencies of DCT coeﬃcients of blocks of size 8 × 8 of ﬁnal hybrid image. This bit string represents the location addresses of blocks in host image that are replaced by their corresponding most similar blocks of secret image. There are some other methods of data hiding [13,14] that take the secret data as a binary data (for example for an eight bit per pixel secret image of size 64 × 64 it uses 64 × 64 × 8 = 32768 bits) and replace them in middle frequencies of DCT coeﬃcients of blocks of size 8 × 8 of original host image. Then the ﬁnal hybrid image is obtained by applying inverse DCT. These methods do not use any similarity measure between blocks of host and secret image. We have compared the performance of our method (named MY DCT) with that of above mentioned ones (named OLD DCT) by comparing the PSNR of the original image and the ﬁnal hybrid image in each method. This result is shown in ﬁgure 7. As it is seen, in both methods the PSNR decreases with respect to increase in capacity (number of bits embedded) while our algorithm could provide better PSNR in all cases. In addition, in both methods the image quality decreases while the number of bits in secret image increases.
Fig. 7. The relation between PSNR and the number of bits embedded in host image. Old DCT indicates using direct embedding of bits in DCT coeﬃcients and MyDCT shows embedding using Gabor ﬁlter.
Secure Steganography Using Gabor Filter and Neural Networks
3.3
43
The Eﬀect of Error Bit
Any error in the extracted location address bit string that represents block location addresses in host image, is equivalent to losing the data of one or more blocks in secret image. It means that choosing an appropriate method for embedding the location address bit string in DCT coeﬃcients is of high importance. Therefore, we applied error control coding methods to increase the performance of correct extraction of location address bit string. We have used Hamming code to protect this bit string. However, one might use diﬀerent methods for error control coding that gives higher protection by the cost of increase in overhead bits. This topic is widely addressed in cryptography and related topics. 3.4
Robustness
One of the weak points in most image hiding algorithms is that if the host image goes under some attacks, then extracting secret image without applying preprocessing routines such as error control codes becomes very diﬃcult. We have tested our method against JPEG compression attack with quality factor of Q=75, 50, 25, 10 and 5. (e.g. Q factor ranges from 1 to 100, a factor of 1 produces the smallest, worst quality image and a factor of 100 produces the largest, best quality image). In all compressed images with above mentioned quality factors still we were able to extract the secret image but with lower quality, depending
Fig. 8. The eﬀect of compression on robustness of our method. In all images the secret image could be extracted from the hybrid image.
44
M. Jamzad and Z.Z. Kermani
Fig. 9. he eﬀect of compression on robustness, by means of the relation between quality factor in JPEG and BER (Bit Error Rate) when the Peppers and Bridge images were selected as secret and host images, respectively
on the value of Q. However, this low quality can be improved by postprocessing image restoration or enhancement methods. An example is shown in ﬁgure 8 the Peppers and Bridge images were selected as secret and host images, respectively. The bit error rate (BER) shown under each image changed from 30, 36.5, 40, 45 and 50, for images (bf), respectively. BER increases with decrease in Q factor. Figure 8(a) is the Bridge image in which the secret image is hidden without compression. Figure 9 shows the relation between BER and Q Factor. 3.5
Performance Evaluation with Respect to Stegoanalysis Methods
Stegoanalysis methods evaluate the robustness of stego image if it goes under a test to verify containing a secret image in it. In this section, we evaluate the security of the proposed algorithm using a blind steganalyzer. Universal steganalysers are composed of two important components [19]. These are feature extraction and feature classiﬁcation. In feature extraction, a set of distinguishing statistics are obtained from a data set of images. There is no welldeﬁned approach to obtaining these statistics, but often they are proposed by observing general image features that exhibit strong variation under embedding. Feature classiﬁcation, operates in two modes. First, the obtained distinguishing statistics from both cover and stego images are used to train a classiﬁer. Second, the trained classiﬁer is used to classify an input image as either being cover image or carrying a hidden message (e.g. a stego image in our application). One of the steganalysis techniques is waveletbased steganalysis. This approach is proposed by Lyu and Farid [16,17] for feature extraction from images.
Secure Steganography Using Gabor Filter and Neural Networks
45
The authors argue that most of the speciﬁc steganalysis techniques concentrate on ﬁrst order statistics, (i.e., histogram of DCT coeﬃcients) since simple countermeasures could keep the ﬁrstorder statistics intact, thus making the steganalysis technique useless. So they proposed building a model for natural images by using higher order statistics and then showed that images with messages embedded in them deviate from this model. Quadratic mirror ﬁlters are used to decompose the image into wavelet domain, after which statistics such as mean, variance, skewness, and kurtosis are calculated for each subband. Additionally the same statistics are calculated for the error obtained from a linear predictor of coeﬃcient magnitudes of each subband, as the second part of the feature set. More recently, in [18], Lyu and Farid expanded their feature set to include a set of phase statistics. As noted in their work, these additional features have little eﬀect on the performance of the steganalyzer. We have tested our proposed method with a blind steganalyzer that uses only the original set of features as suggested in [17]. In this test, we selected 110 JPEG images from Washington Image Database [20] which included some popular images usually used in image processing algorithms. We resized these images into two sets of 110 images of size 256 × 256 and512 × 512. These two sets were used as our cover image database. In addition 65 images from the above mentioned 110 images were selected at random and resized into 64 × 64 as secret images. For a given secret image, the best cover image is selected from the above mentioned cover image database and then using our proposed algorithm, the secret image is hidden in it. Since we have 65 secret images, the procedure of secret image embedding is repeated 65 times. At the end of this stage we have 65 stegimages. We selected 40 of these stegimages at random. Also we picked up the clean version (i.e. the version before embedding the secret image) of the same 40 images. Using wavelet based stegoanalyzer [17] we trained a Fisher Discriminant classiﬁer for each set of 40 stegimages and clean images. We used this classiﬁer to classify the remaining 25 steg and 25 clean images (e.g. from the set of 65 images described above). The results are reported with True positives and False positives measures, if they are determined to contain a secret image or be clean, respectively. The steps of randomly selecting 40 stegimages, etc, and then Table 1. Waveletbased steganalyzer detection accuracy obtained for secret images of size 64 × 64 and cover images of size 256 × 256 and 512 × 512, given in rows 1 and 2, respectively Average Secret Average Cover Image Size Image Size (KBytes) (KBytes) 4.3 63.5 4.3 256
Embedding Rate False Positives True Positives (Hidden data Recognition Recognition per bit) 0.067 32.28% 56% 0.016 32.57% 52.37%
46
M. Jamzad and Z.Z. Kermani
classifying the remaining steg and clean images were repeated 8 times. The average detection accuracy are shown in columns 4 and 5 of Table 1. The analysis of the method and the experimental results show that applying the wavelet based steganalysis method on clean and stegimages, can not reliably detect steg and nonsteg images. Note that the performance of our method improves when the size of host image is increased from 256 × 256 to 512 × 512 for the same secret image of size 64 × 64.
4
Extracting Secret Image When the Final Hybrid Image Is Lost
One of the advantages of our method or any other method that selects the host according to its similarity to the secret image, is that even if the ﬁnal hybrid image is not available (lost), still we can extract a low quality version of the secret image (e,g. pseudosecret image). Because the original host is is known to us and is available in database and also we have the key, we can extract the correct order of 4x4 blocks representing the secret image from the original host. Theoretically, in this situation, the amount of similarity between the pseudosecret image and the real secrete image depends on how well (similar) the host was selected. In addition the accuracy of similarity of host and secret images, highly depends on the number of images in database and how well those images were selected to become a good candidate for a wide range of secrete images. For example, for certain applications, we can add a family of well suited images in database in such a way that it provides the most similarity to a given family of secret images. However, since there is a high similarity between the extracted blocks from the original host and those blocks of original secret image, therefore, the obtained pseudosecret image would have an acceptable similarity to the original secret image [12]. In addition, if the ﬁnal hybrid image is degraded severely, we can assume the hybrid image in not available. Then, since we know the key and the original host image, therefore we extract a rough version of the secret image from the original host image as described in above. On the other hand, since mostly, there are blocks in secret image that are similar to each other in texture content, therefore, we can use one block in host image (that is most similar to those in secret image) to represent all of those similar blocks in secret image. Using this similarity criterion, the capacity increases tremendously, but of course it will aﬀect on the perceptual quality of the ﬁnal extracted secret image, depending on the similarity measures used to select similar blocks in secret image.
5
Improving Performance by Selecting More Than One Host Image
Our experimental results showed that the overall performance of our method can be improved by selecting more than one host image to embed the secret
Secure Steganography Using Gabor Filter and Neural Networks
47
Fig. 10. The relation between PSNR and the number of host images used
image. That is, the blocks of secret image is distributed in two or more host images depending on the similarity measure being imposed. Figure 10 shows the performance of our method by comparing the PSNR while the number of host images increased from 2 to 6. The PSNR increased from 24 when using 2 host images to 34.5 in case of using 6 host images. However, for a ﬁxed size of secret image, if we use more than one host image, it will reduce the capacity of each host, that is it will host fewer number of blocks from the secret image. As a result due to fewer modiﬁcations in hosts, they will have less degradation compared with when using only one host. On the contrary, if we use more than one host, we can increase the size of secret image.
6
Conclusion
Performance of image hiding methods highly depends on the capacity and robustness of hybrid image and the similarity of retrieved secret image to its original version. All these should be achieved by minimum distortion to the host image. Most existing methods are based on the fact that a given secret image should be embedded into one particular host image. These methods provide certain amount of limitations in capacity, robustness and also similarity, because the host is not selected according to the content of the secret image and for some reasons it is selected to be the host. These methods provide certain level of limitations in fulﬁlling the general concerns of steganography. However, if we assume that there are applications where there is no restriction on selecting the host image, then some new ideas in image hiding algorithms can explore. In this paper we suggested one such algorithm that we believe it provides a high level of capacity, robustness and also similarity, while maintaining the minimum distortion in the host image(s). Our main idea is based on dividing the secret image into small blocks of size 4×4
48
M. Jamzad and Z.Z. Kermani
and consider these blocks as texture patterns. Then using the similarity measure provided by Gabor ﬁlter, for any given block in a secret image, the most similar block in a host image is found and the secret block is placed there. However, in order to achieve more capacity and also decrease host image distortion, we introduced the idea of embedding the secret image blocks into more than one host image. Therefore, if we develop an image database containing enough variety of images, then we can expect to ﬁnd suitable image(s) to embed the desired secrete image in such a way that the requirements of capacity, robustness and visual perception are satisﬁed in an optimal level. Our experimental results conﬁrmed that using multiple host images, not only allows us to increase the size of secret image to any desired size, but also reduces the amount of distortions imposed on host images. We believe that our method can produce even better results, if we use several image databases developed for diﬀerent image classes (i.e. ﬂowers, faces, cars, foods, nature, etc.) and use the right database for a given secrete image. The idea of using diﬀerent class of image databases are widely used in content based image retrieval. In this regard another approach is to use at least three databases for images with low, medium and high details. Then we can select the database according to the level of detail in the given secret image. There are many known methods for ﬁnding the level of detail in an image [15]. In our future work, we are going to implement this idea and evaluate its performance. Moreover, we believe, allowing the option of selecting the most suitable host for a given secret image, could lead to many new methods in steganography.
Acknowledgments We would like to highly appreciate the eﬀorts of Miss H.Sajedi who is currently doing her PhD in Department of Computer Engineering, Sharif University of Technology, for preparing the stegoanalysis tests for our method.
References 1. Tsai, P., Hu, Y.C., Chang, C.C.: An image hiding technique using block truncation coding. In: Proceedings of Pasiﬁc Rim Workshop on Digital Steganography, July 2002, Kitakyushu, Japan, pp. 54–64 (2002) 2. Wang, R.Z., Lin, J.F., Lin, J.C.: Image hiding by optimal LSB substitution and genetic algorithm. Journal of Pattern Recognition 34(3), 671–683 (2001) 3. Chae, J.J., Mukherjee, D., Manjunath, B.S.: Color Image Embedding using Multidimensional Lattice Structures. In: Proceeding of IEEE International Conference of Image Processing (ICIP 1998), October, 1998, Chicago, vol. 1, pp. 460–464 (1998) 4. Kim, Y.S.: A wavelet based watermarking method for digital images using human visual system. Sogang University (1999) 5. Chang, C.C., Chen, L.Z., Chung, L.Z.: A steganograhpic method based upon JPEG and quantization table modiﬁcation. Information Society 141, 123–138 (2002)
Secure Steganography Using Gabor Filter and Neural Networks
49
6. Spaukling, J., Hoda, H., Shirazi, M.N., Kawaguchi, E.: BPCS steganography using EZW lossy compression images. Pattern Recognition Letters 23, 1579–1587 (2002) 7. Tsai, P., Hu, Y.C., Chang, C.C.: A progressive secret reveal system based on SPIHT image transmission. Journal of Signal Processing: Image Communication 19, 285– 297 (2004) 8. Marvel, L.M.: Image steganography for hidden communication. University of Delaware, Spring (1999) 9. Ma, W.Y.: Texture features and learning similarity. University of California, Santa Barbara (1996) 10. Manjunath, B.S.: Gabor wavelet transform and application to problems in early vision. In: Proc.26th conference on signals, systems and computers, October 1992, Paciﬁc Grove, CA, pp. 796–800 (1992) 11. Principe, J.C., Euliano, N.R., Lefebvre, W.C.: Neural and Adaptive Systems: Fundamentals Through Simulations. John Wiley and Sons, Chichester (2000) 12. Zahedi Kermani, Z., Jamzad, M.: A robust steganography algorithm based on texture similarity using Gabor ﬁlter. In: The 5th IEEE Int. Symposium Signal Processing and Information Technology (ISSPIT), December 1821, 2005, Athens, Greece (2005) 13. Csurka, C., Deguillaume, F., Ruanaidh, J.J.K.O., Pun, T.: A Bayesian, approach to aﬃne transformation resistant image and video watermarking. In: Proc. Int. Workshop on Information Hiding, September 1999, Dresden, Germany (1999) 14. Piva, A., Barni, M., Bartonili, F., Cappellini, V.: DCTbased watermark recovering without resorting to the un uncorrupted original image. In: IEEE Int. Conference on Image Processing, October 1997, Santa Barbara, CA, vol. 1, pp. 520–523 (1997) 15. Franco, R., Malah, D.: Adaptive Image Partitioning for Fractal Coding Achieving Designated Rates Under a Complexity Constraint. In: IEEE 2001 International Conference on Image Processing (2001) 16. Lyu, S., Farid, H.: Detecting hidden messages using higherorder statistics and support vector machines. In: Proc. 5th Int. Workshop on Information Hiding (2002) 17. Lyu, S., Farid, H.: Steganalysis using color wavelet statistics and oneclass support vector machines. In: Proc. SPIE 5306, pp. 35–45 (2004) 18. Lyu, S., Farid, H.: Steganalysis using higher order image statistics. IEEE Trans. Inf. Forens. Secur. 111–119 (2006) 19. Kharrazi, M., Husrev, T., Sencar, H.T., Memon, N.: ’Performance study of common image steganography and steganalysis techniques’. Journal of Electronic Imaging 15(4), 41–104 (2006) 20. http://www.cs.washington.edu/research/imagedatabase/groundtruth/
Oracle Channels Ilaria Venturini Laboratoire des Signaux et Syst`emes (LSS) ´ ´ Ecole Sup´erieure d’Electricit´ e (Sup´elec) 3, rue Joliot Curie 91192 Gif sur Yvette Cedex  France
[email protected] Abstract. The paper is structured into three main parts. In the ﬁrst part, we focus on information leakage through new covert channels, we term oracle channels, which occur in case oracle attacks are performed on watermarked digital media or multimedia. In the second part, we show how to counteract oracle channels without resorting to protection tools that are quite demanding for communication networks. In the third part, we follow the informationtheoretic approach to show that the countermeasures proposed in the second part do reduce the secret information leakage that ﬂows through oracle channels, without sensibly compromising the detector reliability in case no oracle attack is performed. Keywords: Covert channels, Covert communications, Information hiding, Information leakage, Oracle attacks, Secure watermarking, Subliminal channels.
1
Introduction
Digital media have been used to host authorized secret information. From the communication perspective, authorized secret information that is hidden in them gives rise to communication channels named subliminal channels [1]. A subliminal channel is a communication channel having the following characteristic properties: i) there are both sender and receiver as authorized parties who agree to share any private key, knowledge of details concerning the communication network (protocols, transmission strategies, layers, etc) and algorithms to be exploited; ii) a subliminal channel is foreseen by the scheme designer within a cover channel that was designed for other purposes. iii) it does not violate the cover channel security; iv) it should be easy to detect by the authorized receiver, while diﬃcult to detect by any unauthorized receiver. Examples of subliminal channels are digital watermark channels, i.e. channels where the watermark is transmitted. Watermarks are media embedded into host Y.Q. Shi (Ed.): Transactions on DHMS III, LNCS 4920, pp. 50–69, 2008. c SpringerVerlag Berlin Heidelberg 2008
Oracle Channels
51
media for several diﬀerent goals depending on the application of interest. In fact, watermarks may convey information such as media’s origin, intended destination, owner, content integrity etc. and maintain some desired property such as imperceptibility, blindness, robustness, fragility, semifragility, security, varying with the intended application area. For what concerns unauthorized secret information, we are aware that some form of unauthorized covert communication may occur by means of techniques that were never intended to be used to convey information. For instance, the noise made by a device, as well as the amount of power drawn by a device, can be utilized to transmit information. On the Internet, information is often segmented into packets in order to be transmitted. Since n packets can be ordered in n! ways, by selecting a speciﬁc ordering, information can be transmitted without storing extra information. During a communication protocol, the sender can exploit the acknowledgment timing so as to convey covert information, if the receiving party can repeat observations [2,3]. A security protocol is a distributed algorithm containing a set of prescribed message exchanges between parties over an insecure network. Their security usually relies on encryption, so that they are computation or communication demanding. All these forms of covert communication give rise to channels that are cases of covert channels. The ﬁrst deﬁnition of covert channel appeared in [4]. A covert channel is a communication channel which exploits a cover channel and violates a security policy. Diﬀerent types of covert channels proliferated in the meanwhile. Covert channels that are known so far share the following characteristic aspects. i) There are cooperating malicious or selﬁsh parties, speciﬁcally the covert sender who conveys information through a cover communication channel (that was devised for other purposes) and some designated covert receivers. There is a predetermined agreedupon arrangement by the communicating parties including private key sharing, knowledge of details concerning the communication network (protocols, transmission strategies, layers, etc) and algorithms to be exploited. ii) A covert channel is not foreseen by the designer of the utilized cover channel. iii) The security of the used cover channel is violated by a covert channel. iv) A covert channel is diﬃcult to detect. In [5] a procedure for automatically detecting whether covert information has been embedded into JPEG images from the Internet and the performed experimental results to discover this eventuality, are described. Watching traﬃc through a network, by the administrator or by the socalled network radar algorithms, in order to detect suspicious activity, is a widely used technique for detecting whether a covert channel is going on (see for instance [6]). This is a more diﬃcult task in an ad hoc wireless than in a wired network. In fact, it is diﬃcult to distinguish unusual from usual traﬃc in an ad hoc wireless network which is without a centralized control and where there is communication channel sharing. v) A covert channel needs neither high rate (therefore no high capacity) nor particularly low loss rate since it can reduce its rate signiﬁcantly (therefore it needs no constant rate).
52
I. Venturini
vi) Covert information can be either stored in suitable locations or transmitted by the transmission modality. So far, a great attention has been devoted to covert channels in multilevel information systems, wired computer networks and, in the last few years, also in ad hoc wireless networks. For instance, on the Internet, special parts of a TCP/IP packet header that are not used as locations for transmission or that are optional, have been used to covertly send supplementary information that can be easily reassembled by the receiving party with the use of the stegokey [7]. In [8], covert low rate information is sent by a technique the authors refer to as generation of phantom packets. Covert channels on an autonomous wireless ad hoc network, composed of mobile nodes, have been described which utilize special parts of a reactive routing protocol, where initiation of routes occur according to demand [9,10]. In [11], timing attacks on implementations of RSA, DiﬃeHellman and other systems are described, under the hypothesis that the attacker can make reasonably accurate timing measurements. Moreover, there are cases of unauthorized secret information transmission where covert information is not intentionally transmitted by a malicious or selﬁsh covert sender, rather it is leaked by an attacker alone. Information leakage, as secret information that is revealed to an unauthorized party without any malicious sender, may occur in several scenarios and may require diﬀerent computational eﬀorts. For instance, inference channels, that have received considerable attention in the literature on secure databases, are covert channels such that stored sensitive information can be leaked from stored nonsensitive information [12]. Leak free channels do not exist so far and it seems unlikely that nontrivial ones shall be developed, even if security protocols are used. Here we focus on oracle attacks, that can be considered as particular information leakage attacks which leak the secret watermark, hidden into watermarked digital media or multimedia. The evaluated watermark is removed in copyright and copy protection applications. We claim that every algorithm which makes use of some secret information should face in its very formulation possible information leakage to an unauthorized party. Thus a secure channel designer should aim at maximizing security by minimizing (secret) information leakage. Our problem is how to cope with information leakage threats by the very deﬁnition of algorithms without resorting to protections that turn out to be quite demanding, i.e. requiring a relevant communication network cost. A network cost is not a welldeﬁned notion including computational complexity and network technological practicalities such as communication overhead as interactive connections, key management, accessing to huge data bases. A low network cost is a priority for wireless ad hoc networks [13]. Here we show that, from the communication perspective, oracle attacks form a new class of covert channels we term oracle channels. This helps us to formulate methods for counteracting them. Moreover, the counteracting methods we propose aim to keep low the network cost. The rest of this paper is organized as follows. In Section 2 known oracle attacks are brieﬂy recalled. In Section 3, new covert channels are described, speciﬁcally
Oracle Channels
53
the oracle channels. In Section 4, tools to counteract oracle channels are premised. Three counteracting methods are presented in Section 5. In Section 6, the tradeoﬀ between counteracting oracle channels and detection reliability is analyzed by means of informationtheoretic notions. Section 7 concludes the paper.
2
Known Oracle Attacks
For surveys on watermarking security the reader is referred to [14,15,16,17,18]. Here we focus on watermark evaluation as performed by oracle attacks. 2.1
The Oracle Model
There are several kinds of oracles: deterministic or probabilistic devices with a more or less decision/computation power, the most powerful being the Turing oracle. Speciﬁcally, an oracle attack deals with an algorithmic oracle which is either a hardware or a software device, the detector, whose input is the query and whose output is a binary decision answer on the input. The oracle evaluates a given detection formula on every input under a predetermined threshold and gives always the same answer on the same input. Such an oracle may give a false answer under an acceptable decision threshold, following a binary Hypothesis Testing. It works by exploiting secret data that are not public because of the designer’s decision. Therefore there is the problem of keeping such data secret. To gain knowledge about such secret data, the attacker works as described in the following attacker model. 2.2
The Attacker Model
1. The attacker is active. 2. The attacker is allowed to use a sealed black box watermark detector on a chosen medium of interest. We observe that a black box detector is a quite realistic assumption since most honest users want to easily obtain right and quick decision answers about their media rather than to implement algorithms. 3. The attacker has unlimited access to the detector. 4. The attacker has no knowledge of the secret key but still has a knowledge of the used algorithms that varies with the watermarking scheme. In many cases, the attacker knows the detection formula, in others knows only some properties the detection formula has to meet, i.e. the attacker knows a family of formulas. If the attacker knows absolutely nothing about the algorithms, then the attacker should proceed randomly and interactively with the oracle in order to perform an oracle attack. Of course, the successful convergence problem of such an ineﬃcient attack should be settled. 5. The attacker could exploit also the statistical proﬁling of the media. Therefore, the wellknown Kerckhoﬀs assumption, where there are only the involved algorithms to be known, cannot be assumed with its full meaning [19]. 6. The attacker does not dispose of the unwatermarked medium.
54
I. Venturini
The ﬁrst wellknown oracle attack is the sensitivity analysis attack described for symmetric schemes designed for copy protection [20,21]. The detection formula, known to the attacker, is of linear correlation type and the watermark is binary. The authors are aware that the attack is eﬀective under more general assumptions. Some variations of it can be adapted so as to become threats for several data hiding methods. The watermark is private as well as the decision thresholds thr, T hr, with thr < T hr and [thr, T hr] as the uncertainty interval. The watermark is ﬁrst evaluated by leakage in order to be removed. To this aim, a short path out of the detection region (geometrically represented), i.e. the region where the detection values are greater than the decision threshold, is exploited. Such a short path is the normal to (the tangent of) the detection region. Once such a direction has been determined, the considered medium is forced by the attacker to move along it by some amount, iteratively and interactively with the oracle, until the detection region boundary is crossed. The watermark is estimated as a zero mean binary vector. The complexity of the sensitivity attack is linear with the size Lx of the input. Its stochastic convergence has been proven in [22]. The gradient descendent attack is a version of the sensitivity attack where the watermark is estimated by using a gradient descendent algorithm. In [22], a noniterative formulation of the sensitivity analysis attack, at a copyright protection setting, obtains the watermark as the solution of a linear system with N equations and N unknowns, by at most Lx + 1 operations, starting from suitable guess values. The watermark is an arbitrary vector of real numbers. Such an attack is also extended to a wide family of detection functions including linear correlation, provided that the gradient of the detection function is calculated. Such a method shows that if the attacker knows the detection formula, established numerical methods for solving equation systems may be used to calculate the unknown watermark. In [23], a formulation of the sensitivity analysis attack is given by exploiting the well known Newton iterative approximation method. Therefore the attacker needs only to know that the used (unknown) detection formula meets the Newton’s method hypothesis, namely diﬀerentiability, and to start from a good guess value. Such a method shows that established numerical approximation methods may enlarge the class of detection formulas to all formulas that meet the assumptions of the used approximation method. Convergence, at least locally, is assured provided that the initial guess value is good enough. In [24] an iterative sensitivity attack is formulated for quantizationbased watermarking. In [25,26] a sensitivity attack variation is outlined for selective integrity veriﬁcation watermarking schemes. Although in the integrity scenario the attacker’s aim is not unauthorized removal of the watermark, the watermark evaluation phase typical of oracle attacks remains crucial. The focus in those papers is on countermeasures: in [25] only a countermeasure that is based on time delay is discussed; in [26] also randomization is addressed. In the present paper, the setting is not limited to the integrity application.
Oracle Channels
3
55
A Channel Model for Oracle Attacks
Several communication channel models for watermarking have been formulated. We recall that watermarking communication has ﬁrst received an oversimpliﬁed modeling where the watermark is the information and the cover signal is the channel that limits the detection of the watermark since the watermark is a weak signal. Then watermarking has been modeled as communication with side information at the embedding, being the host known at the embedding phase [15,27]. Later, watermarking communication has been modeled as a communication channel having a covert channel for transmitting the watermark, with side information available at the embedding as well as at the detection phases [28]. Such a covert channel is publicly known to exist and does not violate security. Therefore it is better classiﬁed as a subliminal channel. A formulation following the theory of games has also been given, where the scheme designer wants to maximize the rate of reliable transmission whereas the attacker wants to minimize it [28,29]. Our approach is diﬀerent here. We aim at modeling oracle attacks on actual environments as sketched in Figures 1, 2 and 3. Scenarios in Figures 2 and 3 require a major network cost than that in Figure 1. Let us suppose that a receiver Re utilizes a sealed black box executable software Al(r, k) on a watermarked medium r. The key k has been implemented by the watermarker inside Al and it is not an input to Al as r is. Figure 1 synthesizes the scenario in case Re, after having possibly downloaded both r and the executable software detector Al(r, k) into his DHN (Digital Home Network), operates at his DHN. Figure 2 synthesizes the same scenario but utilizes a remote site, where Al(r, k) is, of a wired network which oﬀers the service. Analogously, in Figure 3 the service is oﬀered by a node of a mobile ad hoc network. We assume the untrustworthy scenario where Re becomes the attacker. Al outputs a binary decision answer a, on every input r, by following a binary Hypothesis Testing decision procedure that utilizes a detection formula whose computational properties (as linearity, complexity, etc.) are overlooked here. We distinguish the following detection channels in the previous ﬁgures. The channel between Re and Al, where r is sent as input to Al(r, k) and then
r Re −→ DHN ←− a
r channel −→ Al(r, k) ←− a
Fig. 1. r and Al(r, k) are at the DHN ; r is the generic, either unmodiﬁed or modiﬁed, input to Al(r, k) through the DHN channel from Re to Al(r, k). The decision answer a by Al(r, k) on r is returned to Re through the DHN channel from Al(r, k) to Re.
56
I. Venturini
r r Re −→ wired network channel −→ Al(r, k) ←− ←− a a
Fig. 2. Executable software Al(r, k) is at a site of a wired network (for instance at the remote server of the creator of that software). Al(r, k) sends, through a wired network channel, its decision response on r as a binary output whose generic element is a, once r has been given as input to Al(r, k).
r r Re −→ wireless network channel −→ Al(r, k) ←− ←− a a
Fig. 3. Software Al(r, k) is at a node of a mobile network and sends its decision response a on the either unmodiﬁed or modiﬁed input r through nodes of a wireless ad hoc network
a = Al(r, k) is sent to Re. Such a channel is in the DHN of Re in Figure 1, in a wired network in Figure 2 and in a wireless ad hoc network in Figure 3. We term Q such a channel. We suppose that Q is noiseless. Let Qn , with n having a ﬁnite range, n = 1, ..., N , N ≥ 2, denote Q at its nth usage. Since Q is a noiseless channel, any transmitted decision answer a = Al(r, k), with a either 1 or 0 at each Qn , is received without error. An information rate is achievable for Q. Re uses Al as an oracle. The information about the watermark leaks from the received response at usage n ﬂowing through a Qo,n from Al to Re. An information rate is also achievable for covert channel Qo = {Qo,n }. We term oracle channel the channel Qo in Q where the information exploited by Re leaks through. Typical properties of an oracle channel are expressed in the following items i)vi) which are correspondent to the items for classical covert channels we have pointed out in the Introduction. i) There is no malicious sender. Re is the unique attacker. Sender Al does not collaborate, under a predetermined agreement, with Re to set up and maintain Qo . Al simply helps Re as long as it outputs answers on inputs sent by Re. ii) Qo is not foreseen by the watermarking scheme designer.
Oracle Channels
57
iii) Qo violates the Q security. iv) Qo is diﬃcult to detect. v) Short answers characterize channel Qo . vi) Secret information is leaked rather than sent/received. Clearly, oracle channels diﬀer from classical covert channels.
4
Counteracting Oracle Channels
In order to counteract oracle attacks, the authors of [20,21] propose: 1. A decision interval, i.e. two thresholds thr and T hr, with thr < T hr. Any detection value below thr denotes that the watermark misses. Any detection value above T hr denotes that the proper watermark is present. Within the interval [thr, T hr], values become 0 or 1 randomly, based on the pdf of a squared sine function. 2. Nonlinear ingredients in the detection formula. Such a line is also in [30,31] and, more eﬀectively, in [32] where a fractal decision boundary (as for instance the Peano curve) has been exploited. We propose that in order to counteract Re in getting secret information, the scheme designer can modify algorithm Al so as Al gets a memory as a storing location for hashed versions of its inputs. Speciﬁcally, as an alternative to suitable communication protocols, that necessarily involve protected connections for the interactive behavior of the involved parties, the scheme designer can counteract a possible unknown channel Qo of a known channel Q by acting on Q via a modiﬁcation of algorithm Al(r, k). Here we formulate three methods to modify Al(r, k) into algorithm Ali (r, k), i = 1, 2, 3, having a hash table μi as its own memory. Thus channels Q, Qo become channels Qi , Qi,o , respectively. Let us premise the hash table deﬁnition that shall be utilized in Section 5. 4.1
Hash Tables for Values of Stable Hash Functions
Hash functions have been used for data indexing and for detecting data manipulation. In order to guarantee that it is diﬃcult to ﬁnd y = x such that h(y) = h(x), a traditional hash function h(.) is not stable in the sense that even if y is obtained from x by a small change, h(y) is very diﬀerent from h(x). Known cryptographic hash functions are not stable. Nowadays, it is widely recognized that digital media most often require soft hashing in the sense that a hash function is stable in a neighbor of its input (e.g. the perceptual hash functions as reviewed in [33]). As stable hash functions we take the similarity preserving hash functions in [34]. Choosing a random vector ran from the Lu,v dimensional Gaussian distribution, where Lu,v is the common length of vectors u and v, a hash function hran (u) is deﬁned as follows: 1 if ran · u ≥ 0 hran (u) = 0 if ran · u < 0
58
I. Venturini
where the product between ran and u is the scalar product. For a family of similarity preserving hash functions the probability that hran (u) = hran (v) is as follows: θ(u, v)  (1) P (hran (u) = hran (v)) = 1 − π where θ(u, v) is the angle between u and v computed by θ(·, ·) that takes values in [0, π]. The similarity function sim(u, v) = 1 − θ(u,v) π  maps pairs of vectors u, v to a real number in the interval [0, 1]. The extreme values 0 and 1 are obtained as follows: θ(u, v) 1 if u and v are identical sim(u, v) = 1 − = (2) 0 if u and v have opposite directions π Since the output of each hran (.) is one bit, by concatenating the output of t such hash functions, the following hash functions composed of t bits h(u) = hran1 (u) . . . hrant (u) h(v) = hran1 (v) . . . hrant (v) are obtained. Similarity of such binary strings can be measured by the Extended Hamming Distance, dEHD , as for instance in [35] with a threshold δ. The error probability Pe (h(u) = h(v)  u = v) is negligible as soon as it is below a predetermined threshold in [0, 1]. A hash table can be used to store the results of a similarity preserving hash function h(.). Hash tables [36] are used to eﬃciently perform search, insertion and removal of values by means of an access function H, that is a speciﬁc hash function for hash table lookup which associates each elements of a set with a position (the hash address) of the table, say in 1, . . . , M . Often such an access function H is the composition of two functions: the ﬁrst function associates a binary string to an integer; the second associates an integer to one position of the table, i.e. to an integer in 1, . . . , M . An eﬃcient handling of collisions is fundamental for hash tables. Figure 4 shows a typical hash table, where each 1 2 3 4
h(x) h(y) 0 h(u) .. . 10 h(z) 11 0 .. . M 0 Fig. 4. Typical hash table with addresses from 1 to M
Oracle Channels
59
location is either empty, and then contains the null element 0, or contains a hash value obtained by h(.).
5
The Methods
To formulate the methods we propose, we write h(r) ∈ μi to express that some h(u) is within μi such that dEHD (h(r), h(u)) < δ, i.e. h(r) approximately matches with h(u). For vector r as input, ﬁrst of all each Ali (r, k) has to verify whether there exists some hashed vector h(u) within μi which approximately matches with h(r), being u a previous input to Ali . Then Ali continues to work accordingly. Having memory μi a ﬁnite dimension, every Ali deletes a stored h(r) from its full hash table following a suitable strategy. Let Δi represent the average time interval during which h(r) remains in memory μi . Δi depends on the (secret) dimension of μi . Resizing the hash table can be exploited to cope with such a removal problem. 5.1
Method 1
By Method 1 algorithm Al is modiﬁed into algorithm Al1 . Algorithm Al1 increases randomness in the sense that Al1 returns also random bits a, with a ∈ {1, 0} as its decision responses. We denote by 1, 0 randomly generated numbers 1, 0, respectively. Speciﬁcally, Al1 randomizes its decision responses on suitable inputs only. To this aim Al1 (r, k) ∈ {a, a}, works as follows: i) if h(r) ∈ / μ1 , then Al1 (r, k) works as Al(r, k) and then stores h(r) in μ1 ; ii) if h(r) ∈ μ1 , then Al1 (r, k) stores h(r) in μ1 and returns 0 or 1 randomly. We do not address here random/pseudorandom bit generation. We allow diﬀerent techniques to be possibly used in Al1 and allow to follow a secret distribution chosen by the designer. We suppose that Al1 does not take into account time duration. 5.2
Method 2
By Method 2 algorithm Al is modiﬁed into algorithm Al2 . Method 2 takes into account the time durations of decision answers. We suppose that decision answers by Al2 take a time duration that can be diﬀerent even for the same answer on the same input, in case it is repeated. Algorithm Al2 is designed to honor the following temporal constraint. The Temporal Constraint  Let Al2 (r, k)Q2,n stand for the time duration of the response given by Al2 at the channel usage Q2,n and n = 1, ..., N . The desired temporal constraint can be expressed, for signals r, r , as Al2 (r , k)Q2,m+j > Al2 (r, k)Q2,m if dEHD (h(r), h(r )) ≤ δ
(3)
for j ≥ 1, m = 1, ..., N and Q2,m , Q2,m+j ∈ {Q2,n }. Thus r is an input to Al2 within the average time interval Δ2 during which h(r) remains in memory μ2 .
60
I. Venturini
To take time duration into account, we write ∗a to mean that a is delayed. The delay duration is here denoted as  ∗  = c. Al2 (r, k) ∈ {a, ∗a} works as follows: i) if h(r) ∈ / μ2 , then Al2 (r, k) works as Al(r, k) and then stores h(r) in μ2 ; ii) if h(r) ∈ μ2 , then Al2 (r, k) stores h(r) in μ2 and returns ∗a. This means that Al2 delays its response a on r, speciﬁcally that Al2 answers after c time units. The c’s values can be tuned to obtain the desired time delay. 5.3
Method 3
By Method 3 algorithm Al is modiﬁed into algorithm Al3 . Method 3 increases randomness as well as delays its decision responses. Al3 (r, k) ∈ {a, ∗a}, works as follows: i) if h(r) ∈ / μ3 , then Al3 (r, k) works as Al(r, k) and then stores h(r) in μ3 ; ii) if h(r) ∈ μ3 , then Al3 (r, k), stores h(r) in μ3 and returns ∗a, i.e. Al3 (r, k) answers 0 or 1 randomly after c time units. Therefore decision answers by Al3 take a diﬀerent time duration as long as Al3 behaves as Al2 . 5.4
Computational Overhead
The computational overhead each Ali suﬀers with respect to Al consists of the creation and management of hash table memory μi . We can state that nonetheless the network cost does not signiﬁcantly increase because: – for what concerns storage, although it is not a major cost for a network, the increase is not signiﬁcant since the dimension of hash tables has not to be large in order to be practical; – for what concerns management, the used hash functions should map most of the signals onto unique integers, i.e. the number of collisions should be suﬃciently small, and thus O(1) search time is realistic for elements stored in the hash table. Otherwise, collisions are handled in an eﬃcient manner [36]. We do not detail here on this subject matter. Also possible hash table resizing can be performed in an eﬃcient manner.
6
TradeOﬀ between Counteracting and Detection Reliability
Here we analyze the tradeoﬀ between the success of each algorithm Ali to counteract information leakage and the Ali detection reliability as deﬁned in the Hypothesis Testing setting. Let us suppose that the attacker uses an Ali , i = 1, 2, 3, as a sealed black box, instead of Al, to perform an oracle attack. Let αi be the obtained sequence of responses instead of sequence α obtained under Al. We suppose that each request by the attacker occurs within the time interval Δi related to the hash
Oracle Channels
61
table μi , and therefore αi is obtained from media whose hashed versions are in the memory of Ali . Point i) of Propositions 1, 2 and 3 show that the proposed countermeasures are adequate. However, the following caveat arises: Caveat: Ali , i = 1, 2, 3, might be less reliable than Al when no oracle attack is being performed. In fact, there may be a hashed value in memory μi of Ali , i = 1, 2, 3, such that an approximate match is found in the hash table for some r. Point ii) of Propositions 1, 2 and 3 show that each Ali has practically the same reliability Al has when no oracle attack is performed. An informationtheoretic perspective has been widely followed in steganography and watermarking, as e.g. in [37] among others. To make this paper selfcontained, we adapt to our context the basic informationtheoretic notions [38,39] we utilize. Let X, W, Y and R be discrete vectorvalued random variables for the original host signal, the watermark, the watermarked signal and the signal which is input to the detector, respectively. Let medium r, the watermarked y = x[w], watermark w and medium x be a generic realization of R, Y, W and X, respectively. We suppose that w is not a deterministic function of x or y or r. The independence between W and R is globally stated about their probability distributions as pWR = pW .pR , where pWR is the joint probability distribution (i.e. pWR = P (W = w, R = r)) and pW .pR the product of the two marginal distributions pW , pR . The distance from the independence condition between W and R can be measured by the KullbackLeibler distance (or relative entropy or information discrimination) that deﬁnes the mutual information I(W; R) between W and R as D(pWR //pW .pR ) =
w,r
p(w, r)log
p(w, r) =def I(W; R) p(w).p(r)
(4)
with p(w, r) > 0 and p(w).p(r) ≥ 0. The informationdiscrimination is a pseudodistance. In general it has no upper bound and it is asymmetric. I(W; R) ≥ 0 and is symmetric. If W is a deterministic function of R, or R is of W, then I(W; R) = 0. A communication channel is characterized by a probability transition matrix that determines, given the input, the conditional distribution of the output. Capacity is one of its basic properties. As pointed out already in [3], having capacity an asymptotic character, it is ﬁne for very long ﬁles or documents sent over a long period of time. It has been shown that existing watermarking systems operate far below capacity. We will not address capacity anymore in the sequel. The mutual information between W and itself, I(W; W), that expectably is the maximum value of dependence, is obtained from (4) as [38] I(W; W) =def H(W).
(5)
62
I. Venturini
The conditional entropy H(WR) is the uncertainty associated with W given R. Since H(W) ≥ H(WR) (6) adding condition variables possibly leads to decrease entropy on the average. Equality holds if variables are stochastically independent of one another. From I(W; R) = H(W) + H(R) − H(W, R) = H(W) − H(WR) since H(W, R) = H(WR) + H(R), I(W; R) is the reduction in uncertainty concerning W due to R, i.e. the reduction in entropy that R provides about W. Let A = AN = (A1 , . . . , AN ) be a decision response ﬁnite sequence of binary random variables whose generic element is simply denoted as A. Let α = αN = (a1 , . . . , aN ) be a sequence of generic realizations of the random variables in A such that a1 = Al(r1 , k), a2 = Al(r2 , k), . . . , aN = Al(rN , k). Decision responses are obtained by statistical binary Hypothesis Testing (that is a steganalysis procedure [40,41,42]). Therefore α may contain some wrong answers, under a suitable decision threshold. Let R = RN = (R1 , . . . , RN ) be a ﬁnite sequence of discrete vectorvalued random variables whose generic element is simply denoted as R. Let ρ = ρN = (r1 , . . . , rN ) be a ﬁnite media sequence of generic realizations of the random variables in R, i.e. r is the generic realization of R such that rN +1 is obtained by the attacker performing modiﬁcations on rN , after having observed both rN and aN . Then we consider H(WR, A) with H(WR, A) = H(WR) − H(AR).
(7)
I(W; R, A) = H(W) − H(WR, A)
(8)
I(W; R, A) > 0, with
has to be minimized for the secrecy issue, provided that the watermark is not a deterministic function of the host content. The Shannon’s perfect secrecy for W on I(W; R, A) requires I(W; R, A) = 0, that can be approximated if W and pair (R, A) can be considered as stochastically independent of one another. However, this is not realistic outside degenerate cases and therefore the hopefully minimized I(W; R, A) is positive such that it cannot be approximated to zero. 6.1
Performance of Method 1
For what concerns Method 1, Proposition 1 holds. Proposition 1. Under algorithm Al1 used as a sealed black box, i) during an oracle attack, the mutual information I(W; R, A) under Al1 at step N ≥ 2 is less than the one under Al; ii) Al1 is less reliable than Al during an oracle attack ;
Oracle Channels
63
iii) without performing an oracle attack, detection reliability under Al1 and that under Al are practically the same. Proof  i) The ﬁnite sequence of the generic decision answers by Al1 until the current step N ≥ 2 can be written as follows: α1 = α1,N = (a1,1 , a1,2 , . . . , a1,N ) = (a, a, . . . , a) where the ﬁrst element a = Al1 (r1 , k) = Al(r1 , k) is the generic answer on the original r1 ; the second element is the random answer on the modiﬁed r1 ; and so on. Let A1,N be the random variable whose generic realization is a1,N . We have to show that, at step N ≥ 2, I(W; R1,N , A1,N ) < I(W; RN , AN ), where R1,N is RN relative to Al1 . Since, for N ≥ 2, A1,N is ‘more random’ than AN because the probability to be random for a1,N is greater than zero while the probability to be random for aN is zero, H(WR1,N , A1,N ) ≥ H(WRN , AN ) From (8), I(W; R1,N , A1,N ) = H(W) − H(WR1,N , A1,N ) and I(W; RN , AN ) = H(W) − H(WRN , AN ) hold and therefore I(W; R1,N , A1,N ) ≤ I(W; RN , AN ) with I(W; R1,N , A1,N ) < I(W; RN , AN ) in nondegenerated scenarios.
ii) During an oracle attack, Al1 is obviously less reliable than Al because of its greater randomness that increases the error probability of its decision responses.
iii) Under the assumption that the error probability of hash functions is negligible, α1 is a sequence obtained on signals in ρ1 very few of which have their hash version that match with elements in μ1 . This entails that Al1 has practically the same detection reliability Al has when no attack occurs since it gives the same answers on the same inputs. Thus for AN , A1,N with probability distributions pAN ,pA1,N ; RN , R1,N with probability distributions pRN , pR1,N D(pA1,N //pAN ) ∼ 0 and D(pR1,N //pRN ) ∼ 0 and I(W; R1,N , A1,N ) ∼ I(W; RN , AN )
64
6.2
I. Venturini
Performance of Method 2
Time duration of the decision responses is basic for Method 2. Let a = t > 0 denote the time duration, measured by the assumed time unit, to obtain decision response a by Al. Let E{t} be the expected value of t. For channels that work interactively and are eﬀective if the time duration of responses is reasonable, as oracle channels do, time duration of the decision response is a relevant notion to be taken into account also at the informationtheoretic setting. The Temporal Mutual Information  The temporal mutual information, It (W; R, A), relates information leakage with the time duration of the decision response. In [3] the temporal capacity is deﬁned. Here we deﬁne the temporal mutual information It (W; R, A) as follows It (W; R, A) =
I(W; R, A) . E{t}
(9)
The time response of Al at the denominator of (9) makes It (W; R, A) to decrease as E{t} increases. If the temporal mutual information decreases then the information rate also decreases. For what concerns Method 2, Proposition 2 holds. Proposition 2. Under algorithm Al2 used as a sealed black box, i) the temporal mutual information under Al2 at step N ≥ 2 is less than the one under Al during an oracle attack ; ii) Al2 is reliable as Al is during an oracle attack ; iii) without performing an oracle attack, detection reliability under Al2 and that under Al are practically the same. Proof  i) The ﬁnite sequence of the generic decision answers by Al2 until step N can be written as follows: α2 = α2,N = (a2,1 , a2,2 , . . . , a2,N ) = (a, ∗a, . . . , ∗a) where the ﬁrst element a = Al2 (r1 , k) = Al(r1 , k) is the generic answer on the original r = r1 ; the second element is the answer on r2 that is the modiﬁed r1 , and so on. Let A2,N be the random variable whose generic realization is a2,N . We have to show that, at step N ≥ 2, It (W; R2,N , A2,N ) < It (W; RN , AN ), where R2,N and RN are practically the same. Since t2,N = a2,N  > aN , because a2,N diﬀers from aN only because of ∗ whose meaning is delay, the expected value E{t2,N } is such that E{t2,N } > E{tN } while I(W; R2,N , A2,N ) = I(W; RN , AN ).
Oracle Channels
65
Then It (W; RN , AN ) =
I(W; R2,N , A2,N ) I(W; RN , AN ) > = It (W; R2,N , A2,N )
E{tN } E{t2,N }
ii) Under the assumption that the error probability of the used hash functions are negligible, every α2 is a sequence obtained on signals in ρ2 very few of which have their hash versions that match with elements in μ2 . This entails that Al2 has obviously the same detection reliability Al has also during an oracle attack as an immediate consequence of the fact that Al2 returns exactly the same decision responses of Al on the same inputs, possibly at a delayed time instant.
iii) Under the assumption that the error probability of hash functions is negligible, Al2 has practically the same detection reliability Al has when no attack occurs since it gives the same answers on the same inputs. Thus for AN , A2,N with probability distributions pAN , pA2,N ; RN , R2,N with probability distributions pRN , pR2,N , as in point iii) of Proposition 1, at a greater extent D(pA2,N //pAN ) ∼ 0 and D(pR2,N //pRN ) ∼ 0 and I(W; R2,N , A2,N ) ∼ I(W; RN , AN )
6.3
Performance of Method 3
For what concerns Method 3, Proposition 3 holds as a Corollary of Proposition 1 and Proposition 2. Proposition 3. Under algorithm Al3 used as a sealed black box, i) during an oracle attack, the temporal mutual information at step N ≥ 2 is less than the one under Al; ii) Al3 is less reliable than Al during an oracle attack ; iii) without performing an oracle attack, detection reliability under Al3 and that under Al are practically the same. Proof  i) We have to show that It (W;R3,N , A3,N ) < It (W; RN , AN ), where R3,N is modiﬁed by Al3 . In the following sequence α3 = α3,N = (a3,1 , a3,2 , . . . , a3,N ) = (a, ∗a, . . . , ∗a) the ﬁrst element a = Al3 (r1 , k) = Al(r1 , k) is the answer on the original r = r1 , the second element is the answer on the modiﬁed r1 , and so on. Let A3,N be the random variable whose generic realization is a3,N . Now under Al3 the temporal mutual information decreases, at step N ≥ 2, because in It (W; RN , AN ) =
I(W; R3,N , A3,N ) I(W; RN , AN ) > = It (W; R3,N , A3,N ) E{tN } E{t3,N }
the numerator decreases under Al3 as under Al1 and the denominator increases under Al3 as under Al2 .
66
I. Venturini
ii) During an oracle attack, Al3 is obviously less reliable than Al at the same extent Al1 is.
iii) Al3 has practically the same reliability Al has when no attack occurs as a consequence of item iii) of Proposition 1 and of Proposition 2.
7
Conclusions and Further Work
Oracle attacks have been shown in this paper to be new covert channels, we term oracle channels. This helped us to propose modiﬁcation methods for watermarking detection algorithms so as to face how to contrast possible oracle channels at the very formulation phase of watermarking schemes. An important aspect of our proposals is that they aim reducing information leakage at a low network cost. Informationtheoretic notions allow us to prove that the modiﬁed algorithms that can be obtained by the proposed methods do enhance security with respect to oracle attacks and moreover their detection reliability is practically the same in case no oracle attack is performed. However, for what concerns Method 1 and Method 3, a good reliability does not allow increasing randomness to a degree such that the mutual information becomes negligible. As a consequence of Propositions 1, 2 and 3, during an oracle attack, the diminution of the information leakage for channel Qi , i = 1, 2, 3, with respect to that of Q, entails an information rate decrease of oracle channel Qi,o with respect to that of oracle channel Qo . The proposed methods are designed to work under the usual assumption of one attacker who disposes of one detector with one chosen medium as input. If this is not the case, diﬀerent actual scenarios are in order. Let us consider the following two strategies (suggested to us by a Referee) an attacker could follow to nullify the countermeasures here proposed. Case 1. Oracle attack using diﬀerent detectors To cope with such a case, some technique of collaborating algorithms on the same data structure should be exploited. For instance, diﬀerent detector copies made by one attacker, could be forced, at the implementation level, to share the same hash memory if they are copies that are stored in a peertopeer network or in the same network device. Otherwise, diﬀerent detectors with diﬀerent hash memories should be stored in diﬀerent subnetworks and should require diﬀerent attackers who communicate and collaborate each other. Such a scenario should require a relevant computation or communication overhead. Case 2. Oracle attack with several contents, feeding them to the detector in such a way that when the attacked version of a content is input again to the detector, its hash was already removed from the memory. To cope with such a case, a new larger table is built up [36], whenever, at the implementation setting, the previously designed table turns out to be soon dramatically inadequate. The total cost is O(M ) because all the contents of the original table, whose size is M , are added to the new table. If enlarging
Oracle Channels
67
the hash table all at once may interrupt timecritical operations, resizing has to be gradual. (For instance, a new hash table can be allocated without deallocation of the old one, and both tables are checked during lookups, for a while. Each new insertion is performed into the new table together with also the insertion of some element of the old table. Finally the old table is deallocated when all elements are removed from it.) Linear hashing permits incremental hash table expansion. Consistent hashing decreases the resizing cost by using access hash functions such that the addresses of most values do not change when the table is resized.
References 1. Simmons, G.J.: Subliminal Channels: Past and Present. European Trans. on Telecommunications 5(4), 459–473 (1994) 2. Millen, J.: 20 years of covert channel modeling and analysis. In: Proceedings of Symposium on Security and Privacy, pp. 113–114. IEEE Computer Society Press, Los Alamitos (1999) 3. Moskowitz, I., Kang, M.: Covert channels  here to stay. In: Proceedings of COMPASS 1994, pp. 235–243. IEEE, Los Alamitos (1994) 4. Lampson, B.W.: A Note on the Conﬁnment Problem. Comm. ACM 16, 613–615 (1973) 5. Provos, N., Honeyman, P.: Detecting Steganographic Content on the Internet. IEEE Trans. on Information Theory 49(3), 563–593 (2003) 6. Tumoian, E., Anikeev, M.: Network Based Detection of Passive Covert Channels in TCP/IP. In: Proceedings of the IEEE Conference on Local Computer Networks 30th Anniversary, pp. 802–809. IEEE, Los Alamitos (2005) 7. Ahsan, K., Kundur, D.: Practical Data hiding in TCP/IP. In: Proceedings of Workshop on multimedia Security at ACM Multimedia 2002, ACM Press, New York (2002) 8. Servetto, S.D., Vetterli, M.: Communication Using Phantoms: Covert Channels in the Internet. In: Proceedings IEEE International Symposium on Information Theory (ISIT), USA (2001) 9. Li, S., Ephremides, A.: A Network Layer Covert Channel in Adhoc Wireless Networks. In: Proceedings of Int. Conf. on Image Processing 1998 (ICIP 1998), vol. 1, pp. 88–96. IEEE, Los Alamitos (2004) 10. Shnayder, V.: Opportunities for Language Based Information Flow Security in Sensor Networks (2004) 11. Kocher, P.C.: Timing attacks on implementations of DiﬃeHellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996) 12. Jajodia, S., Meadows, C.: Inference Problems in Multilevel Secure Database Management Systems. Information Security 570–585 (1991) 13. Zeng, W., Lan, J., Zhuang, X.: Network friendly media security: rationales, solutions and open issues. In: Proceedings IEEE Int. Conf. on Image Processing (ICIP 2004), IEEE, Singapore (2004) 14. Barni, M., Bartolini, F., Furon, T.: A general framework for robust watermarking security. Signal Processing, Elsevier, special issue on Security of Data Hiding Technologies, vol. 83, pp. 2069–2084 (invited paper) (2003)
68
I. Venturini
15. Barni, M., Bartolini, F.: Watermarking Systems Engineering: Enabling Digital Assets Security and other Applications. Dekker Inc (2004) 16. Cayre, F., Fontaine, C., Furon, T.: Watermarking security part I: Theory. In: Delp, E.J., Wong, P.W. (eds.) Proc. SPIEIS&T Electronic Imaging. SPIE, San Jose, CA, USA (2005) 17. Cayre, F., Fontaine, C., Furon, T.: Watermarking security part II: Practice. In: Delp, E.J., Wong, P.W. (eds.) Proc. SPIEIST Electronic Imaging. SPIE, San Jose, CA, USA (2005) 18. Furon, T.: A survey of watermarking security. In: Barni, M., Cox, I., Kalker, T., Kim, H.J. (eds.) IWDW 2005. LNCS, vol. 3710, pp. 201–215. Springer, Heidelberg (2005) 19. Fridrich, J., Goljan, M.: Practical steganalysis of digital images: state of the art. In: Proceedings of SPIE Photonics West, vol. 4675, pp. 1–13 (2002) 20. Linnartz, J.P., van Dijk, M.: Analysis of the sensitivity attack against electronic watermarks in images. In: Aucsmith, D. (ed.) IH 1998. LNCS, vol. 1525, pp. 258– 272. Springer, Heidelberg (1998) 21. Kalker, T., Linnartz, J.P., van Dijk, M.: Watermark estimation through detector analysis. In: Proc. of Int. Conf. on Image Processing 1998 (ICIP 1998), vol. 1, pp. 425–429. IEEE, Los Alamitos (1998) 22. Choubassi, M.E., Moulin, P.: New sensitivity analysis attack. In: Proceedings of International Symposium on Electronic Imaging, Security and Watermarking of Multimedia Contents VII. IS&T/SPIE, pp. 734–745 (2005) 23. Comesana, P., PerezFreire, L., PerezGonzalez, F.: The Return of the Sensitivity Attack. In: Barni, M., Cox, I., Kalker, T., Kim, H.J. (eds.) IWDW 2005. LNCS, vol. 3710, pp. 260–274. Springer, Heidelberg (2005) 24. PerezFreire, L., ComesanaAlfaro, P., PerezGonzales, F.: Detection in quantizationbased watermarking: performance and security issues. In: Proceedings of International Symposium on Electronic Imaging, Security and Watermarking of Multimedia Contents VII. IS&T/SPIE, pp. 721–733 (2005) 25. Venturini, I.: Counteracting oracle attacks. In: Proc. of the Multimedia and Security Work. 2004 (MM and Sec 2004), pp. 187–192. ACM Press, Magdeburg, Germany (2004) 26. Venturini, I.: Oracle attacks and covert channels. In: Barni, M., Cox, I., Kalker, T., Kim, H.J. (eds.) IWDW 2005. LNCS, vol. 3710, pp. 171–185. Springer, Heidelberg (2005) 27. Cox, I., Miller, M., Bloom, J.: Digital Watermarking. Morgan Kaufmann Pub., Academic Press (2002) 28. Moulin, P., O’Sullivan, J.: Informationtheoretic analysis of watermarking. In: Proc. of Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP 2000), IEEE, Los Alamitos (2000) 29. Moulin, P., O’Sullivan, J.: Informationtheoretic analysis of information hiding. IEEE Trans. on Information Theory 49(3), 563–593 (2003) 30. Furon, T., Venturini, I., Duhamel, P.: An uniﬁed approach of asymmetric watermarking schemes. In: Proceedings of International Symposium on Electronic Imaging, Security and Watermarking of Multimedia Contents III. IS&T/SPIE, pp. 269–279 (2001) 31. Furon, T., Macq, B., Hurley, B., Silvestre, G.: JANIS: Just Another Norder sideInformed watermarking Scheme. In: Proceedings of IEEE International Conf. on Image Processing, ICIP 2002, vol. 3, pp. 153–156. IEEE, NY, USA (2002)
Oracle Channels
69
32. Tewﬁk, A., Mansour, M.: Secure watermark detection with nonparametric decision boundaries. In: Proc. of Int. Conf. on Acoustics, Speech and Signal Processing 2002 (ICASSP 2002), pp. 2089–2092. IEEE, Los Alamitos (2002) 33. Kalker, T., Haitsma, J., Oosteveen, J.: Issues with digital watermarking and perceptual hashing (2001) 34. Charikar, M.: Similarity estimation techniques from rounding algorithms. In: Proceedings of STOC 2002, pp. 380–388. ACM, New York (2002) 35. Kulyukin, V.A., Bookstein, A.: Integrated Object Recognition with Extended Hamming Distance (2000) 36. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw Hill (2001) 37. Mittelholzer, T.: An informationtheoretic approach to steganography and watermarking. In: Pﬁtzmann, A. (ed.) IH 1999. LNCS, vol. 1768, pp. 1–17. Springer, Heidelberg (2000) 38. Fabris, F.: Teoria dell’informazione, codici, cifrari. Boringhieri (2001) 39. Cover, T., Thomas, J.: Elements of Information Theory. John Wiley and Sons, New York (1991) 40. Maurer, U.M.: Authentication Theory and Hypothesis Testing. IEEE Transactions on Information Theory 46(4), 1350–1356 (2000) 41. Cachin, C.: An InformationTheoretic Model for Steganography. Information and Computation 192, 41–56 (2004) 42. Chandramouli, R., Subbalakshmi, K.P.: Current Trends in Steganalysis: A Critical Survey (2005)
QuantizationBased Methods: Additive Attacks Performance Analysis J.E. VilaForc´en1, , S. Voloshynovskiy1, , O. Koval1 , F. P´erezGonz´alez2, and T. Pun1 1
2
Computer Vision and Multimedia Laboratory, University of Geneva, 24 Rue G´en´eralDufour, 1204 Geneva, Switzerland
[email protected] Departamento de Teor´ıa de la Se˜ nal y Comunicaciones, ETSI Telecom., Universidad de Vigo, 36200 Vigo
Abstract. The main goal of this study consists in the development of the worst case additive attack (WCAA) for Mary quantizationbased datahiding methods using as design criteria the error probability and the maximum achievable rate of reliable communications. Our analysis focuses on the practical scheme known as distortioncompensated dither modulation (DCDM). From the mathematical point of view, the problem of the worst case attack (WCA) design using probability of error as a cost function is formulated as the maximization of the average probability of error subject to the introduced distortion for a given decoding rule. When mutual information is selected as a cost function, a solution of the minimization problem should provide such an attacking noise probability density function (pdf) that will maximally decrease the rate of reliable communications for an arbitrary decoder structure. The obtained results demonstrate that, within the class of additive attacks, the developed attack leads to a stronger performance decrease for the considered class of embedding techniques than the additive white Gaussian or uniform noise attacks.
1
Introduction
Datahiding techniques aim at reliably communicating the largest possible amount of information under given distortion constraints. Their resistance against diﬀerent attacks determine the possible application scenarios. The knowledge of the WCA allows to create a fair benchmark for datahiding techniques and makes it possible to provide reliable communications with the use of appropriate error correction codes. In general, digital datahiding can be considered as a game between the datahider and the attacker. This threeparty twoplayers game was already investigated by Moulin and O’Sullivan [11] where two setups are analyzed. In the ﬁrst one, the host is assumed to be available at both encoder and decoder prior to
He is on leave to Universidad Carlos III de Madrid, Av. de la Universidad 30, 28911 Leganes, Madrid, Spain. The corresponding author.
Y.Q. Shi (Ed.): Transactions on DHMS III, LNCS 4920, pp. 70–90, 2008. c SpringerVerlag Berlin Heidelberg 2008
QuantizationBased Methods: Additive Attacks Performance Analysis
71
the transmission, the socalled private game. In the second one, the host is only available at the encoder as in Fig. 1, i.e., the public game. The performance is analyzed with respect to the maximum achievable rate when the decoder is aware of the attacking channel and therefore maximum likelihood (ML) decoding is applied. The knowledge of the attacking channel at the decoder is not a realistic assumption for most practical applications. Such a situation was analyzed by SomekhBaruch and Merhav, who considered the datahiding problem in terms of maximum achievable rates and error exponents. They assumed that the host data is available either at both encoder and decoder [15] or only at the encoder [16] and supposed that neither the encoder nor the decoder are aware of the attacker’s strategy. In their consideration, the class of potentially applied attacks is signiﬁcantly broader than in the previous study case [11] and includes any conditional pdf that satisﬁes a certain energy constraint. Quantizationbased datahiding methods have attracted attention in the watermarking community. They are a practical implementation of a binning technique for channels whose state is noncausally available at the encoder considered by Gel’fand and Pinsker [7]. Recently it has been also demonstrated [12] that quantizationbased datahiding performance coincides with the spread spectrum (SS) datahiding at the lowwatermarktonoise ratio (WNR) by taking into account the host statistics and by abandoning the assumption of an inﬁnite image to watermark ratio. The quantizationbased methods have been widely tested against a ﬁxed channel and assuming that the channel transition pdf is available at the decoder. A minimum Euclidean distance (MD) decoder is implemented as an equivalent of the ML decoder under the assumption of a pdf created by the symmetric extension of a monotonically nonincreasing function [1]. It is a common practice in the datahiding community to measure the performance in terms of the error rate for a given decoding rule as well as the maximum achievable rate of reliable communications. In this paper we will analyze the WCAA using both criteria. In this paper we restrict the encoding to the quantizationbased one and the channel to the class of additive attacks only. We assume that the attacker might be informed of the encoding strategy and also of the decoding one for the error exponent analysis, while both encoder and decoder are uninformed of the channel. Furthermore, the encoder is aware of the host data but not of the attacking strategy. It is important to note that the optimality of the attack critically relies on the input alphabet even under powerlimited attacks. McKellips and Verdu showed that the additive white Gaussian noise (AWGN) is not the WCAA for discrete input alphabets such as pulse amplitude modulation [10]. Similar conclusion for datahiding was obtained by P´erezGonz´alez et al. [14], who demonstrated that the uniform noise attack performs worse than the AWGN attack for some WNRs. In [13], P´erezGonz´alez demonstrated that the AWGN cannot indeed be the WCAA because of its inﬁnite support. VilaForc´en et al. [18] and Goteti
72
J.E. VilaForc´en et al.
and Moulin [8] solved independently the minmax problem for the DCDM [2] in terms of probability of error for the ﬁxed decoder, binary signaling, the subclass of additive attacks in datahiding and detectionformulation, respectively. Simultaneously, VilaForc´en et al. [19] and Tzoschoppe et al. [17] derived the WCAA for DCDM using the mutual information as objective function for additive attacks. This paper aims at establishing the informationtheoretic limits of Mary quantizationbased datahiding techniques and developing a benchmark that can be used for the a comparison of diﬀerent quantizationbased methods. The selection of the distortion compensation parameter α (see Section 2.2) ﬁxes the encoder structure for the quantizationbased methods. Although the optimal α can easily be determined when the power of the noise is available at the encoder prior to the transmission [5], this is not always feasible for various practical scenarios. Nevertheless, the availability of the attacking power and of the attacking pdf is a very common assumption in most datahiding schemes. We will demonstrate that for a speciﬁc decoder (MD decoder) it is possible to calculate the optimal α independently of the attack variance and pdf for the block error probability as a cost function. The paper is organized as follows. Problem formulation is given in Section 2. The investigation of the WCAA for a ﬁxed quantizationbased datahiding scenario is performed in Section 3, where the cost function is the probability of error. The informationtheoretic analysis of Section 4 derives the information bounds where the cost function is the mutual information between the input message and the channel output. Notations: We use capital letters to denote scalar random variables X, bold capital letters to denote vector random variables X and corresponding small letters x and x to denote the realizations of scalar and vector random variables, respectively. An information message and a set of messages with cardinality M is designated as m ∈ M, M = {1, 2, . . . , M}, respectively. A host signal distributed according to the pdf fX (x) is denoted by X ∼ fX (x); Z ∼ fZ (z), W ∼ fW (w) and V ∼ fV (v) represents the attack, the watermark and the received signal, respectively. The step of quantization is equal to Δ and the distortioncompensation factor is denoted as α . The variance of the watermark is 2 2 σW and the variance of the attack is σZ . The WNR is given by WNR = 10 log10 ξ, σ2
where ξ = σW 2 . The set of natural numbers is denoted as N and IN denotes the Z N × N identity matrix.
2 2.1
Digital DataHiding: Binning Approach Gel’fandPinsker Formulation of the DataHiding Problem
The Gel’fandPinsker problem [7] has been recently revealed as the appropriate theoretical framework of datahiding communications with side information. The Gel’fandPinsker datahiding setup is presented in Fig. 1. In order to communicate a message m ∈ M, M = {1, 2, . . . , M}, the encoder performs a mapping
QuantizationBased Methods: Additive Attacks Performance Analysis
73
X m
Encoder φ
W
Embedder ϕ
Y
DMC fVY (vy)
V
Decoder ψ
m ˆ
K Fig. 1. Gel’fandPinsker datahiding setup
φ : M × X N × K → W N based on a noncausally available host realization x ∈ X N and the key k ∈ K, K = {1, 2, . . . , K}. The stego data Y is obtained using the embedding mapping: ϕ : W N × X N → Y N . The decoder estimates the transmitted message from the channel output as ψ : V N × K → M. According to this scheme, a key is available at both encoder and decoder. Nevertheless, key management is outside of the scope of this paper and we will not consider it further. Two constraints apply to the Gel’fandPinsker framework in the datahiding scenario: the embedding and the channel constraints [11]. Let d(·, ·) be a non2 2 , σZ be two positive numbers, the embedder is said to negative function and σW satisfy the embedding constraint if:
2 d(x, y)fX,Y (x, y) ≤ σW ,
(1)
x∈X N y∈Y N
where d(x, y) =
1 N
N i=1
d(xi , yi ).
Analogously, the channel is said to satisfy the channel constraint if:
2 d(y, v)fY,V (y, v) ≤ σZ .
(2)
y∈Y N v∈V N
Costa setup: Costa considered the Gel’fandPinsker problem for the independent and identically distributed (i.i.d.) Gaussian case and mean squared error distance 2 IN ). It is possible to [3]. The embedder ϕ produces Y = W + X, X ∼ N (0, σX 2 write the channel output as: V = X + W + Z, where Z ∼ N (0, σZ IN ), and the estimate of the message m ˆ is obtained at the decoder given V. In the Costa setup, α denotes an optimization parameter used for the codebook construction 2 σW at the encoder selected to maximize the achievable rate when αopt = σ2 +σ 2 W Z assuming that the encoder knows in advance the noise variance. In this case, the proposed setup achieves host interference cancellation and: R(αopt ) = C AWGN =
1 σ2 log2 1 + W 2 2 σZ
that corresponds to the AWGN channel capacity without host interference.
(3)
74
J.E. VilaForc´en et al.
1
2
Δ
 12B
2 
1
Th
Fig. 2. DCDM output pdf fDCDM for the message m = 1 and binary signaling under high rate assumption
2.2
QuantizationBased DataHiding Techniques
Aiming at reducing the Costa codebook exponential complexity, a number of practical datahiding algorithms exploit structured codebooks instead of random ones. The most famous discrete approximations to Costa problem are known as DCDM [2] and scalar Costa scheme (SCS) [5]. The structured codebooks are designed using quantizers (or lattices [6]) which should achieve host interference cancellation. Assuming that the channel transition pdf is given by some additive noise pdf, within the class of quantizationbased methods, we focus our analysis on DCDM and dither modulation (DM) [2]. For the DCDM case, the stego data is obtained as follows: φDCDM (m, x, α ) = y = x + α (Qm (x) − x),
(4)
where 0 < α ≤ 1 is the analogue of the Costa optimization parameter α. If α = 1, the DCDM (4) simpliﬁes to the DM (φDM (m, x) = y = Qm (x)). 2 2 2 The embedding distortion for the DCDM is σW = α Δ 12 . In this case, the pdf of the stego image is represented by a train of uniform pulses of width 2B = (1 − α )Δ centered at the quantizer reconstruction level as a result of the distortion compensation1 . An example of such a pdf fDCDM corresponding to Δ the communications of the message m = 1 is given in Fig. 2 where Th = 2M denotes the distance between two neighbor quantizer decision and reconstruction levels. Using the MD decoding rule (m ˆ MD = argminm∈M v −Qm (v)2 ) , the correct decoding region Rm and the complementary error region Rm associated to a message m, are deﬁned as it is depicted in Fig. 3 [14]. R1
R1 1
R1 2
Δ

R1 1
R1 2 
R1
R1
1
Th
Fig. 3. DM and DCDM correct decoding region R1 and error decoding region R1 for the message m = 1 and binary signaling when the MD decoder is used 1
The analysis is performed here in the framework of Eggers et al. [5] disregarding the host pdf impact. If host pdf is taken into account, we refer readers to [9, 12] for more details.
QuantizationBased Methods: Additive Attacks Performance Analysis
3
75
Error Probability as a Cost Function
When the average error probability is selected as a cost function, we formulate the problem of Fig. 1 as: ∗(N )
PB
= min max PB (φ, ψ, fV Y (··)), φ,ψ fV Y (··)
(5)
where PB (φ, ψ, fV Y (··)) is the average error probability for an encoder φ, de∗(N )
coder ψ and channel fV Y (··), and PB is the resulting error probability. The error probability depends on the particular encoder and decoder pair (φ, ψ) and ˆ = mM = m]. the attacking channel fVY (vy), i.e., PB (φ, ψ, fV Y (vy)) = Pr[m Here, we assume that the attacker knows both encoder and decoder strategies and selects its attacking strategy accordingly. Both encoder and decoder select their strategy without knowing the attack in advance. Although this is a very conservative setup, it is also important for various practical scenarios. The more advantageous setup for the datahider is based on the assumption that the decoder selects its strategy knowing the attacker choice: min max min PB (φ, ψ, fV Y (··)). φ
fV Y (··)
ψ
(6)
Here, the attacker knows only the encoding function, which is ﬁxed prior to the attack, and the decoder is assumed to be aware of the attack pdf. In the general case, SomekhBaruch and Merhav [15] have shown the following inequalities for the above scenarios: min max PB (φ, ψ, fV Y (··)) ≥ min max min PB (φ, ψ, fV Y (··)) φ,ψ fV Y (··)
φ
fV Y (··)
ψ
= min max PB (φ, ψ ML , fV Y (··)), φ
fV Y (··)
(7) (8)
where the equality (8) is a consequence of the fact that the decoder is aware of the attacking pdf and therefore the minimization at the decoder results in the optimal ML decoding strategy ψ ML . In the analysis of the WCAA using the error probability as a cost function, we will further assume that the MD decoder is applied. In the class of additive attacks, the attacking channel transition pdf is only determined by the pdf of the additive noise fZ (z). Finally, in this analysis we assume independence of the error probability on the quantization bin where the received signal v lies (because the error region Rm (Fig. 3) has periodical structure and the host pdf fX (x) is assumed to be asymptotically constant within each quantization bin). Applying (7) to the quantizationbased datahiding (Section 2.2) and assuming an additive attacking scenario, the MD decoding rule and highrate, one has: max PB (α , ψ MD , fZ (·)) ≥ min PB (φ, ψ MD , f˜Z (·)), (9) min α
fZ (·)
α
76
J.E. VilaForc´en et al.
where the equality holds if, and only if, the ﬁxed attack pdf f˜Z (z) coincides with the WCAA. Here, the encoder optimization is reduced to the selection of an optimal parameter α since Δ is ﬁxed by the embedding constraint, and the channel is reduced to the selection of the worst additive noise pdf. The problem (9) implies that the attacker might know both encoding and decoding strategy. Here, we target ﬁnding the WCAA pdf and the optimum ﬁxed encoding strategy independently of the particular attacking case which guarantees reliable communications and provides an upper bound on the error probability. Considering the previously discussed quantizationbased techniques and the MD decoder, and assuming that the message m is communicated, the probability of correct decoding PBc is determined as [14]: PBc = Pr[V − Qm (V )2 < V − Qm (V )2 : ∀ m ∈ M, m = m] = Pr[V ∈ Rm M = m].
(10)
The error probability can be obtained as PB = 1 − PBc . We can represent the error probability as the integral of the equivalent noise pdf fZeq M = fZ ∗fDCDM over the error region Rm : 1 fZ M (zeq M = m)dzeq . (11) PB = M Rm eq For the Mary case, it is possible to write the probability of error as a sum of integrals as: ∞ 1 (k+1)Δ−Δ/2M PB = 2 fZeq M (zeq M = m)dzeq . (12) M kΔ+Δ/2M k=0
In the case of DCDM the pdf is given by the convolution of the attacking pdf with the selfnoise pdf (periodic uniform pdf, Fig. 2) [14]. The following subsections are dedicated to the analysis of the error probability (12) for the WCAA as well as for the AWGN and uniform noise attacks. 3.1
The WCAA
The problem of the WCAA for digital communications based on binary pulse amplitude modulation (PAM) was considered in [10] using the error probability under attack power constraint. In this paper, the problem of the WCAA is addressed for the quantizationbased datahiding methods. The problem can be formulated as the lefthand part of (9), where the encoder is optimized over all α such that 0 < α ≤ 1, and the attacker selects the attack pdf fZ (·) maximizing the error probability PB . Since the encoder must be ﬁxed in advance in the practical setups, we will ﬁrst solve the above minmax problem as an internal maximization problem for a given encoder/decoder pair: fZeq (zeq M = m)dzeq , (13) max PB (α , ψ MD , fZ (·)) = max fZ (·)
fZ (·)
Rm
QuantizationBased Methods: Additive Attacks Performance Analysis
0 1
(1a) α =0.6, 0dB.
α
0
z
=0.8, 0dB.
z
=0.8, 5dB.
(2c)
0
0 1 α
0
z
1 (3b)
α
0
z =1, 5dB.
fZ (z)
fZ (z)
1
0
1
z
z
(3c)
α
0
z
1
1
=0.8, 15dB. (2e)
40
α
0
20
z =1, 10dB.
1
0
1
z
=0.8, 20dB.
20 0
1 (3d)
α
40
0 1
20 0
1
=0.8, 10dB. (2d)
20
1
40
20
1
0 1
=1, 0dB.
α
0
40
20
1
0 1
fZ (z)
20
0
z
40
20
1
40
fZ (z)
40
α
0
0 1
0 1
(2b)
1
40
20
1
0
z
20
(1c) α =0.6, 10dB. (1d) α =0.6, 15dB. (1e) α =0.6, 20dB.
0 1
0 1
fZ (z)
fZ (z)
fZ (z)
0
fZ (z)
1
40
20
(3a)
0
z
(1b) α =0.6, 5dB.
40
(2a)
0 1
25
fZ (z)
0
z
40
fZ (z)
1
20
fZ (z)
0
20
50
fZ (z)
20
40
fZ (z)
40
fZ (z)
fZ (z)
40
77
α
0
z =1, 15dB.
1
1 (3e)
α
0
1
z =1, 20dB.
Fig. 4. WCAA optimization resulting pdfs for diﬀerent α and WNR, binary signaling
subject to the constraints:
∞
−∞
fZ (z)dz = 1,
∞ −∞
2 z 2 fZ (z)dz ≤ σZ ,
(14)
2 where the ﬁrst constraint follows from the pdf deﬁnition and σZ constrains the attack power. We will derive the WCAA based on (13) for a ﬁxed α and use it for the solution of (9) accordingly. The distortion compensation parameter α leading to the minimum error probability will be the solution to (9). Unfortunately, no close analytical solution has been found. The resulting attacking pdfs obtained using numerical optimization are presented in Figs. 4 and 5 for diﬀerent WNRs and α values assuming Δ = 2. The obtained pdfs are nonmonotonic functions. Thus, the MD decoder is not equivalent to the ML decoder. The obtained error probability is depicted in Fig. 7, where its maximum is equal to 1 since we are assuming a ﬁxed decoder (MD decoder). In a diﬀerent decoding scenario when it is possible to invert the bit values, the maximum error probability will be equal to 0.5. The broad variability of the obtained pdfs is not very convenient and tractable for various practical applications. Unfortunately, there is no close form approximation to the whole range of considered WNRs. Therefore, motivated by simplicity and benchmarking purposes, we have chosen an approximation based on a socalled 3 − δ attack whose pdf is presented in Fig. 6, where T denotes the
J.E. VilaForc´en et al.
0 0
z
1
(1a) α =0.6, 0dB.
20
α
0
z
=0.8, 0dB.
z
=0.8, 5dB.
(2c)
0 α
0
z =1, 0dB.
1 (3b)
α
0
z =1, 5dB.
fZ (z)
fZ (z) z
0
z
1
1 (3c)
α
0
z
1
1
=0.8, 15dB. (2e)
40
α
0
20
1
z =1, 10dB.
0
z
1
=0.8, 20dB.
20 0
1 (3d)
α
40
0 1
20 0
1
=0.8, 10dB. (2d)
0 1
1
40
20
1
20
0 1
α
0
40
20
1
0 1
fZ (z)
20
0
z
40
20
1
40
fZ (z)
40
α
0
0 1
0 1
(2b)
1
40
20
1
0
z
25
(1c) α =0.6, 10dB. (1d) α =0.6, 15dB. (1e) α =0.6, 20dB.
0 1
0 1
fZ (z)
fZ (z)
fZ (z)
1
40
0
fZ (z)
0
z
(1b) α =0.6, 5dB.
40
(3a)
0 1
20
fZ (z)
1
(2a)
20
50
fZ (z)
0
20
40
fZ (z)
20
40
fZ (z)
40
fZ (z)
fZ (z)
40
fZ (z)
78
α
0
z =1, 15dB.
1
1 (3e)
α
0
z
1
=1, 20dB.
Fig. 5. WCAA optimization resulting pdfs for diﬀerent α and WNR, quaternary signaling
position of the lateral deltas and A their height. The 3 − δ attack is a good approximation to the pdfs obtained in the medium and highWNRs and provides a simple and powerful attacking strategy, which approximates the WCAA and might be used for testing diﬀerent datahiding algorithms. In order to demonstrate how accurate this approximation is, one needs to compare the average error probability caused by this attack versus the numerically obtained results. For this purpose, the optimization of the 3 − δ attack parameters has been performed for the DCDM considering the DM as a particular case for α = 1. Δ When T − B < Th = 2M , the error probability is equal to the integral of the equivalent noise pdf fZeq M (zeq M = m) over the error region Rm that can be found analitically: A PB = (T + B − Th ), (15) B
A −T
1 − 2A 0
A T
Fig. 6. 3 − δ attack, 0 ≤ A ≤ 0.5
QuantizationBased Methods: Additive Attacks Performance Analysis
101
102
100
3δ, α = 1 Opt. α = 1 3δ, α = 0.8 Opt. α = 0.8
5
0
5
10
15
20
PB
PB
100
79
25
3δ, α = 1 Opt. α = 1 3δ, α = 0.9 Opt. α = 0.9
101
102
5
0
5
10
15
WNR, [dB]
WNR, [dB]
(a)
(b)
20
25
Fig. 7. Error probability comparison between the numerical optimization results and the 3 − δ attack case: (a) binary signaling and (b) quaternary signaling
where 2B = (1 − α )Δ and A = of T = Topt1 :
2 σZ 2T 2 .
Topt1 =
It is maximized for the following selection
Δ(1 − M(1 − α )) . M
(16)
The value of Topt1 should be always positive, implying that α >
M−1 M .
M−1 M .
It can
For a given attack variance be demonstrated that Topt1 → 0 as α → 2 = 2T 2 A > 0 and Topt1 → 0, one has A → 0.5 (its maximum value to satisfy σZ the technical requirement to pdf in Fig. 6). Simplifying (15) for α → M−1 M implies that PB → 1. Thus, A = 0.5 and PB = 1 for α ≤ If α >
M−1 M
M−1 M .
and T = Topt1 , the error probability is given by: 2 Mα σZ . 2 24 · σW (1 − α )(1 − M(1 − α )) 2
PB =
(17)
This result is valid if Topt1 − B < Th , and this constraint implies that α ≤ 1 1 − 3M . For this case, the minimum of the error probability is achieved at: α opt =
2(M − 1) . 2M − 1
(18)
1 In case the previous condition does not hold (α > 1− 3M ), the error probability is calculated as: PB = 2A. The maximum is found for the minimum possible T = Topt2 = Th + B, and the error probability is: 2 M2 α σZ 2 (1 + M(1 − α ))2 . 3 · σW 2
PB =
(19)
The comparison presented in Fig. 7 demonstrates that the 3δ attack produces asymptotically the same error probability as the numerical optimization results presented in Figs. 4 and 5.
80
J.E. VilaForc´en et al.
The optimization results (Figs. 4 and 5) demonstrate that for very lowWNR the WCAA structure does not necessarily corresponds to the 3δ attack. Nevertheless, the 3δ attack is a good approximation to the WCAA despite of its simplicity as shown in Fig. 7. 3.2
AWGN Attack
This Section contains the error probability analysis of the Mary DM and DCDM techniques under the AWGN attack. DM analysis: In the DM case, the equivalent noise pdf is given by a train of Gaussian functions: 2
z − eq2 1 2σ Z , e fZeq M (zeq M = m) = 2 2πσZ
(20)
2 where σZ denotes the variance of the attack. The error probability can be therefore calculated using (12).
DCDM analysis: In the DCDM case the equivalent noise pdf is given by [14]: zeq + B zeq − B 1 fZeq M (zeq M = m) = −Q , Q 2B σZ σZ
x 2 where Q is the Qfunction Q(x) = √12π 0 e−t /2 dt and B is the halfwidth of the selfnoise pdf. The analytical expression for the error probability (11) does not exist, and it is evaluated numerically using (12). 3.3
Uniform Noise Attack
It was shown [14] that the uniform noise attack produces higher error probability than the AWGN attack for some particular WNR in the binary signaling case. This fact contradicts the common belief that the AWGN is the WCAA for all datahiding methods since it has the highest diﬀerential entropy among all pdfs with bounded variance. We consider the uniform noise attack Z ∼ U(−η, η) with 2 2 = η3 . variance σZ DM analysis: The equivalent noise pdf is given by a train of uniform pulses. In the case when the power of the attack is not strong enough, i.e., all noise samples are within the quantization bin of the sent message, the error probability is zero. For stronger attacks the error probability is deﬁned by the integral of the equivalent noise pdf (a uniform pdf) over the error region using (12). The Δ analytical solution when η < 2M+1 M 2 in the Mary case is: ⎧ Δ η < 2M ; ⎪ ⎨ 0, 2M−1 Δ Δ MD Unif. PB (α = 1, ψ , fZ (·)) = 1 − 2Mη , 2M ≤ η < M Δ (21) 2; ⎪ ⎩ Δ M−1 2M−1 Δ 2M+1 Δ η M , M 2 ≤ η < M 2.
QuantizationBased Methods: Additive Attacks Performance Analysis 100
81
100
PB
PB
Unif. AWGN 3−δ 101
101 Unif. AWGN 3−δ
102
5
0
5
10
15
20
25
102
5
WNR, [dB]
0
5
10
15
20
25
WNR, [dB]
(a)
(b)
Fig. 8. Error probability analysis results for diﬀerent attacking strategies: (a) DM performance and (b) DCDM for α = 0.8 performance and binary signaling
In the third case, the error probability decreases while the WNR decreases as well. This eﬀect is caused by the entrance of the noise into the nearest correct region and a smaller portion of the attack power is present in the error region. Because of this eﬀect we have a non strictly decreasing probability of error as Δ a function of the WNR. If η > 2M+1 M 2 , the error probability starts increasing again since the received pdf enters again the error region. DCDM Analysis: Under the uniform noise attack, the bit error probability is equal to the integral of the equivalent noise pdf fZeq M (zeq M = m) (a train of trapezoidal functions) over the error region (12). The resulting analytical equation for η + B < Δ − Th in the Mary case is:
PB (α , ψ
MD
, fZUnif.(·))
⎧ ⎨ 0, =
k1 2, ⎩ 8M 1 1 min{ 2B , 2η }
Th > η + B; η − B < Th < η + B; · k2 , Th < η − B,
(22)
where k1 = (2(η + B)M − Δ)(2mM(η + B) + 4nM + mΔ), + ((η − B) − Th ) , m = min{1/2B,1/2η} k2 = (η+B)−η−B 2 η−B−(η+B) and n = −m(η + B). If η + B > Δ − Th , the error probability decreases as in the DM case. 3.4
Error Probability Analysis Conclusions
The eﬃciency of the AWGN and the uniform noise attacks is compared with the 3δ attack in Fig. 8, demonstrating that the gap between the AWGN attack and the 3 − δ approximation of the WCAA can be larger than 5decibel (dB) in terms of the WNR. The error probability as a function of the distortion compensation parameter for a given WNR demonstrates that the 3 − δ attacking scheme is worse than either the uniform or Gaussian ones (Fig. 9). If the noise pdf is known, it is possible to select such an α that minimizes the error probability for the given WNR in Fig. 9. For example, if WNR = 0dB and Gaussian noise is applied, the optimal distortion compensation factor is α = 0.53, resulting in PB = 0.23.
82
J.E. VilaForc´en et al. 100
100
PB
PB
101 3−δ AWGN Unif. 101
0
3−δ AWGN Unif.
102
0.2
0.4
0.6
0.8
103
1.0
0
0.2
0.4
0.6
0.8
1.0
α
α
(a)
(b)
Fig. 9. Error probability comparison as a function of the distortion compensation parameter for the 3 − δ, Gaussian and uniform attacks and binary signaling: (a) WNR = 0dB and (b) WNR = 10dB
100
100
PB
101
102
PB
WNR = 0dB WNR = 5dB WNR = 10dB WNR = 15dB WNR = 20dB
WNR = 0dB WNR = 5dB WNR = 10dB WNR = 15dB WNR = 20dB
101
α = 2/3 103
0
0.2
α = 6/7
0.4
0.6
α
0.8
1.0
102
0
0.2
0.4
0.6
0.8
1.0
WNR, [dB]
(a)
(b)
Fig. 10. Error probability analysis results as a function of the distortion compensation parameter α for the 3 − δ attack: (a) binary signaling and (b) quaternary signaling
Nevertheless, the encoder and the decoder are in general uninformed of the attacking strategy in advance and a mismatch in the attacking scheme may cause a bit error probability of 1, while for α = 0.66 the maximum bit error probability is PB = 0.33. According to the optimal compensation parameter given by (18), one can conclude that, independently of the operational WNR, α = α opt guarantees the lowest error probability of the analyzed datahiding techniques under the 3 − δ attack (Fig. 10). Having this bound on the error probability, it is possible to guarantee reliable communications using proper error correction codes. Therefore, one can select such a ﬁxed distortion compensation parameter α = α opt at the uninformed encoder and the MD decoder, which guarantees a bounded error probability. Substituting (18) into (17), one obtains the upper bound on the error probability under the 3 − δ approximation of the WCAA: PB (α opt ) =
1 M(M − 1)ξ −1 . 6
(23)
QuantizationBased Methods: Additive Attacks Performance Analysis
4
83
Mutual Information as a Cost Function
The analysis of the WCA with mutual information as a cost function provides the informationtheoretic performance limit (in terms of achievable rate of reliable communications) that can be used for benchmarking of diﬀerent practical robust datahiding techniques. Moulin and O’Sullivan [11] considered the maximum achievable rate in the Gel’fandPinsker setup (Section 2) as a maxmin problem: C = max min [I(U ; V ) − I(U ; X)] , φ
fV Y (··)
(24)
2 for a blockwise memoryless attack, the embedder distortion constraint σW and 2 the attacker distortion constraint σZ . In the case of practical quantizationbased methods the mutual information is measured between the communicated message M and the channel output V [13]: Iφ,fV Y (··) (M ; V ), where the subscript means that the mutual information depends on both encoder design and attack pdf. It was shown in [13] that modulo operation does not reduce the mutual information between V and M if the host is assumed to be ﬂat within the quantization bins. Consequently:
Iφ,fV Y (··) (M ; V ) = Iφ,fV Y (··) (M ; V ),
(25)
where V = QΔ (V ) − V , and the above problem can be reformulated as: max min Iφ,fV Y (··) (M ; V ). φ
fV Y (··)
(26)
Rewriting the inequalities (7)–(8) for the mutual information as a cost function, we have: max min Iφ,fV Y (··) (M ; V ) ≤ max Iφ,f˜V Y (··) (M ; V ), φ
φ
fV Y (··)
with equality if, and only if, the ﬁxed attack f˜V Y (··) coincides with the WCA. Thus, the decoder in Fig. 1 is not ﬁxed and we assume that the channel attack pdf fV Y (··) is available at the decoder (informed decoder) and, consequently, ML decoding is performed. Under previous assumptions of quantizationbased embedding and additive attack, it is possible to rewrite (26) as: min Iα ,fZ (·) (M ; V ). max α
fZ (·)
(27)
As for the error probability analysis case, we address the problem of the WCAA and the optimal encoding strategy for the WCAA. It is known [4] that the mutual information can be expressed in the general case as a KullbackLeibler divergence (KLD): Iα ,fZ (·) (M ; V ) = D(fMV (m, v )fV (v )pM (m)) fV M (v M = m) dv , = fMV (m, v ) log2 fV (v )
(28)
84
J.E. VilaForc´en et al.
where fM,V (m, v ) is the joint pdf of the input message and the modulo of the channel output, pM (m) denotes the marginal probability mass function (pmf) of the input messages and fV (v ) the marginal pdf of the modulo of the channel output. In fact, (28) can be written as the KLD between the received pdf when one of the symbols has been sent, and the average of the pdfs of all possible symbols. Assuming equiprobable symbols in the Mary signaling case, one obtains [13]: M 1 D fV M (v M = m)fV (v ) M m=1 = D fV M (v M = 1)fV (v ) ,
Iα ,fZ (·) (M ; V ) =
(29)
where: D fV M (v M = m)fV (v ) = D fV M (v M = 1)fV (v ) ,
(30)
since fV M (v M = 1) and fV M (v M = m) are the same pdf shifted for all M 1 m ∈ M and fV (v ) = M m=1 fV M (v M = m). The next subsections are dedicated to the analysis of the DM and the DCDM under WCAA, AWGN attack and the uniform noise attack. 4.1
The WCAA
The problem of the WCAA using the mutual information as a cost function can be formulated using (27) and (29). Since the encoder must be ﬁxed in advance as for the probability of error analysis case, we solve the maxmin problem as a constrained minimization problem: (31) min Iα ,fZ (·) (M ; V ) = min D fV M (v M = 1fV (v ) , fZ (·)
fZ (·)
where 0 < α ≤ 1. The constraints in (31) are the same as in the error probability oriented analysis case (14). Unfortunately, this problem has no closed form solution and it was solved numerically. The obtained results are presented for diﬀerent α values in Fig. 11. 2.0
1.0
0.6
α = 0.95 α = 0.70 α = 0.50
1.5
I(M ; V )
I(M ; V )
0.8
0.4
1.0 0.5
0.2 0 15
α = 0.95 α = 0.70 α = 0.50
10
5
0
5
WNR, [dB]
(a)
10
15
20
0 15
10
5
0
5
10
15
20
WNR, [dB]
(b)
Fig. 11. Mutual information analysis results for the WCAA case: (a) binary signaling and (b) quaternary signaling
QuantizationBased Methods: Additive Attacks Performance Analysis 0.10
I(M ; V )
0.6 0.4
α α α α α
=1 = 0.7 = 0.5 = 0.4 = 0.1
10
5
I(M ; V )
1.0 0.8
85
0.05
α α α α α
=1 = 0.7 = 0.5 = 0.4 = 0.1
0.2 0 15
0
5
10
15
0 15
20
12
9
6
3
0
WNR, [dB]
WNR, [dB]
(a)
(b)
Fig. 12. Mutual information analysis results for the uniform noise attack case and binary signaling: (a) global performance analysis and (b) magniﬁcation of the lowWNR regime
4.2
AWGN Attack
When the DM and the DCDM undergo the AWGN, no closed analytical solution to the mutual information minimization problem exists; the minimization was therefore performed using numerical computations. 4.3
Uniform Noise Attack
It was shown [14] that the uniform noise attack is stronger than the AWGN attack for some WNRs when the error probability is used as a cost function. One of the properties of the KLD measure states that it is equal to zero if, and only if, the two pdfs are equal. In case the uniform noise attack is applied, this condition holds for some particular values of WNR for the mutual information 2 given by (29). It can be demonstrated that I(M ; V ) = 0 when ξ = αk2 , k ∈ N for the Mary signaling. This particular behaviour allows the attacker to achieve zero rate of communication with smaller attacking power than was predicted by the datahider. The mutual information of quantizationbased datahiding techniques for the uniform noise attacking case with binary and quaternary signaling is depicted in Fig. 12. It demonstrates that the eﬃciency of the attack 1.0
0.6
1.0 WCAA AWGN Uniform
0.8
I(M ; V )
I(M ; V )
0.8
0.4 0.2 0 15
0.6
WCAA AWGN Uniform
0.4 0.2
10
5
0
5
WNR, [dB]
(a)
10
15
20
0 15
10
5
0
5
10
15
20
WNR, [dB]
(b)
Fig. 13. Comparison of diﬀerent attacks using mutual information as a cost function: (a) α = 0.95, binary signaling and (b) α = 0.5, binary signaling
86
J.E. VilaForc´en et al.
strongly depends on the value of the distortion compensation parameter, and shows the oscillating behaviour at the lowWNR detailed in Fig. 12(b). The uniform noise attack guarantees that it is not possible to communicate 2 using the DCDM at ξ ≤ α , and therefore distortion compensation parameter α has a strong inﬂuence on the performance at the lowWNR. As a consequence, 2 ξ = α represents the WNR corresponding to zero rate communication, if the 2 w ≥ D . attacking variance satisﬁes σZ α2 4.4
Mutual Information Analysis Conclusions
The results presented in Fig. 13 for various α demonstrate that the developed attack produces the maximum loss in terms of mutual information for all WNRs in comparison with the AWGN or uniform noise attacks. In the analysis of the WCAA using the error probability as a cost function, the optimal α parameter was found. Unfortunately, it is not the case in the mutual information oriented analysis, and its value varies with the WNR. In Fig. 14 the optimum α values as a function of the WNR are presented for several cardinalities of the input messages in comparison with the optimum SCS parameter [5]. It demonstrates that the SCS optimum distortion compensation parameter designed for the AWGN is also a good approximation for the WCAA case. Recalling (27), we can conclude that it is not possible to ﬁnd a unique optimum α for the mutual information analysis case, contrarily to the error probability 1.0 0.8 0.6
α
2 DCDM 4 DCDM 8 DCDM ∞ DCDM SCS
0.4 0.2 0 15
10
5
0
5
10
15
20
WNR, [dB]
Fig. 14. Optimum distortion compensation parameter α when the mutual information is selected as a cost function
I(M ; V )
2.5 2.0 1.5 1.0
3.0
2 DCDM WCAA 4 DCDM WCAA 8 DCDM WCAA 16 DCDM WCAA 32 DCDM WCAA ∞ DCDM WCAA ∞ DCDM AWGN
2.5
I(M ; V )
3.0
0.5 0 15
2.0 1.5
2 4 8 2 4 8
DCDM DCDM DCDM DCDM DCDM DCDM
WCAA WCAA WCAA AWGN AWGN AWGN
1.0 0.5
10
5
0
5
WNR, [dB]
(a)
10
15
20
0 15
10
5
0
5
10
15
20
WNR, [dB]
(b)
Fig. 15. Maximum achievable rate for diﬀerent cardinalities of the input alphabet under the WCAA compared to the AWGN (a) for M → ∞ and (b) for M < ∞
QuantizationBased Methods: Additive Attacks Performance Analysis
87
one when the decoder was ﬁxed to the suboptimum MD decoder. Thus, the datahider cannot blindly select a value of the distortion compensation blindly which guarantees reliable communications at any given WNR. It is possible to observe a saturation of the optimum value of α in Fig. 14 for small dimensionality and large WNR. Therefore, it is possible to select an optimum α if the WNR range is known, located in the highWNR regime and requirements of small dimensionality apply. For example, working in the highWNR with WNR > 5dB and M = 2, optimum α can be chosen as α = 0.71.
(3a) M=8, 15dB.
0
z
1
(3b) M=8, 10dB.
0 0
z
1
1
(4a) M=16, 15dB.
0
z
(4b) M=16, 10dB.
(4c) M=16, 5dB.
0
1 0
1
0
z
1
(5a) M=32, 15dB.
0
z
1
(5b) M=32, 10dB.
0
1 0
1
0
z
1
0
z
1
(6a) M=∞, 15dB. (6b) M=∞, 10dB.
0
z
(6c) M=∞, 5dB.
1
fZ (z)
fZ (z) fZ (z)
fZ (z) fZ (z)
1
0
z
(6d) M=∞, 0dB.
1
0
z
1
(5f) M=32, 10dB. 4
1 0
1
2
1
2
0 1
1
0 0
z
(5e) M=32, 5dB.
1
0
z
4
1
2
1
1
(4f) M=16, 10dB.
1
1
(5d) M=32, 0dB.
0 1
0
z
2
1
0 1
2
fZ (z)
1
1
(5c) M=32, 5dB.
2
fZ (z)
2
0
z
0
z
2
0 1
1
0 1
(4e) M=16, 5dB.
3
0
z
4
1
1
6
0 1
0
z
(4d) M=16, 0dB.
1
1
(3f) M=8, 10dB.
0 1
2
fZ (z)
fZ (z)
2
1
1
2
1
2
0 0
z
0
z
(3e) M=8, 5dB.
3
1
0 1
6
1
1
1
(3d) M=8, 0dB.
1
1
0
z
0
z
4
0 1
0 1
2
1
2
0 1
0
z
(3c) M=8, 5dB.
fZ (z)
1
0 1
2
fZ (z)
2
fZ (z)
0 1
1
(2f) M=4, 10dB.
2
3
6
1
fZ (z)
1
0
z
(2e) M=4, 5dB.
6
1
0 1
fZ (z)
0
z
(2d) M=4, 0dB.
1
1
1
0
z
12
fZ (z)
0 1
0
z
fZ (z)
1
1
(1f) M=2, 10dB.
0 1
2
fZ (z)
fZ (z)
0
1
(2c) M=4, 5dB.
2
1
0
z
1
2
0 1
0
z
(1e) M=2, 5dB.
3
20 0
1
6
1
1
(2b) M=4, 10dB.
2
fZ (z)
0
z
1
(1d) M=2, 0dB.
0 1
0
z
fZ (z)
1
(2a) M=4, 15dB.
fZ (z)
1
6 0
1
fZ (z)
0
z
1
2
0 1
0
z
(1c) M=2, 5dB.
fZ (z)
fZ (z)
fZ (z)
1
2 0
1
2
0
fZ (z)
1
(1b) M=2, 10dB.
2
fZ (z)
0
z
fZ (z)
(1a) M=2, 15dB.
0 1
fZ (z)
1
fZ (z)
0
z
40
12
fZ (z)
0 1
2
fZ (z)
0
2
4
fZ (z)
1
4
fZ (z)
4
fZ (z)
fZ (z)
2
2 0
1
0
z
(6e) M=∞, 5dB.
1
1
0
z
(6f) M=∞, 10dB.
Fig. 16. Pdfs of the WCAA for diﬀerent input distribution and WNRs
1
88
J.E. VilaForc´en et al.
Using the optimum α for each WNR, the resulting mutual information (31) is presented in Fig. 15(a) for diﬀerent cardinalities of the input alphabet compared to the performance of the AWGN using the optimized α = αopt parameter [11]. The obtained performance demonstrates that the developed WCAA is worse than the AWGN whenever the optimum distortion compensation parameter is selected. The pdfs of the WCAA for diﬀerent cardinalities of the input alphabet and WNRs are depicted in Fig. 16. The results presented here have been obtained with a numerical optimization tolerance up to 10−12 . Previous results [13] have already proven that the optimal WCAA pdf must be strictly inside the bin (and following the AWGN cannot be the WCAA). However, it is possible to achieve nearly optimal solutions with larger support of the pdf. The periodical repetition of the constellations yields a similar eﬀective attack whilst using a larger power. In the presented experiments, the bin width was chosen as Δ = 2. The support of the presented WCAA pdfs does not vary signiﬁcantly. The optimum distortion compensation parameter α increments with the WNR and so the power of the embedded signal while the selfnoise support decrements. Thus, the support of the attack remains nearly the same for all WNRs. Larger variations can be observed at the highWNR and for high dimensionality, where the optimum α variation is smaller. It is possible to observe in Figs. 15(a) and 16 that the impact of the WCAA is very similar to a truncated Gaussian and that the diﬀerence in terms of the mutual information is negligible. Although the AWGN is not the WCAA, its performance is an accurate and practical approximation to the WCAA in the asymptotic case when M → ∞. For M < ∞, the diﬀerence might be important for some WNRs and it is needed to consider the real WCAA as it is presented in Fig. 15(b).
5
Conclusions
In this paper we addressed the problem of the WCAA for the quantizationbased datahiding techniques from the probability of error and mutual information perspectives. The comparison between the analyzed cost functions demonstrated that in a rigid scenario with a ﬁxed decoder, the attacker can decrease the rate of reliable communication more severely than by using either the AWGN or the uniform noise attacks. We showed that the AWGN attack is not the WCAA in general, and we obtained an accurate and practical analytical approximation to the WCAA, the socalled 3 − δ attack, when the cost function is the probability of error for the ﬁxed MD decoder. For the 3 − δ attack, α = 2(M−1) 2M−1 was found to be the optimal value for the MD decoder that allows to communicate with an upper bounded probability of error for a given WNR. This value could be ﬁxed without prior knowledge of the attacking pdf. The analysis results obtained by means of numerical optimization showed that there exists a worse attack than the AWGN when the mutual information
QuantizationBased Methods: Additive Attacks Performance Analysis
89
was used as a cost function. Contrarily to the error probability analysis case, the optimal distortion compensation parameter (α ) depends on the operational WNR for the mutual information analysis case. The particular behaviour of the mutual information under uniform noise attack was considered, achieving 2 2 w such that σZ ≥ D . The zerorate communication for attacking variances σZ α2 presented results should serve as a basis for the development of fair benchmarks for various datahiding technologies.
Acknowledgment The authors acknowledge the valuable comments of the anonymous reviewers that helped to enhance the clarity and technical content of the paper. This paper was partially supported by SNF Professorship grant No PP00268653/1, Interactive Multimodal Information Management (IM2) project and by the European Commission through the IST Programme under Contract IST2002507932 ECRYPT. The authors are thankful to the members of the Stochastic Image Processing group at University of Geneva and to Pedro Comesa˜ na and Luis P´erezFreire of the Signal Processing in Communications Group at University of Vigo for many helpful and interesting discussions. The information in this document reﬂects only the author’s views, is provided as is and no guarantee or warranty is given that the information is ﬁt for any particular purpose. The user thereof uses the information at its sole risk and liability.
References 1. Barni, M., Bartolini, F.: Watermarking Systems Engineering. Marcel Dekker, Inc., New York (2004) 2. Chen, B., Wornell, G.W.: Quantization index modulation: A class of provably good methods for digital watermarking and information embedding. IEEE Transactions on Information Theory 47(4), 1423–1443 (2001) 3. Costa, M.: Writing on dirty paper. IEEE Transactions on Information Theory 29(3), 439–441 (1983) 4. Cover, T., Thomas, J.: Elements of Information Theory. Wiley and Sons, New York (1991) 5. Eggers, J.J., B¨ auml, R., Tzschoppe, R., Girod, B.: Scalar costa scheme for information embedding. IEEE Transactions on Signal Processing 51(4), 1003–1019 (2003) 6. Erez, U., Zamir, R.: Lattice decoding can achieve 0.5 log(1+snr) over the additive white gaussian noise channel using nested codes. In: IEEE International Symposium on Information Theory, Jun 2001, Washington DC, USA, p. 125 (2001) 7. Gel’fand, S.I., Pinsker, M.S.: Coding for channel with random parameters. Problems of Control and Information Theory 9(1), 19–31 (1980) 8. Goteti, A.K., Moulin, P.: QIM watermarking games. In: Proceedings of IEEE International Conference on Image Processing, vol. 2, pp. 717–720 (October 2004) 9. Koval, O., Voloshynovskiy, S., P´erezGonz´ alez, F., Deguillaume, F., Pun, T.: Quantizationbased watermarking performance improvement using host statistics: AWGN attack case. In: Proceedings of ACM Multimedia and Security Workshop, September 2021, 2004, Magdeburg, Germany (2004)
90
J.E. VilaForc´en et al.
10. McKellips, A., Verdu, S.: Worst case additive noise for binaryinput channels and zerothreshold detection under constraints of power and divergence. IEEE Transactions on Information Theory 43(4), 1256–1264 (1997) 11. Moulin, P., O’Sullivan, J.: Informationtheoretic analysis of information hiding. IEEE Transactions on Information Theory 49(3), 563–593 (2003) 12. P´erezFreire, L., P´erezGonz´ alez, F., Voloshynovskiy, S.: Revealing the true achievable rates of scalar costa scheme. In: IEEE International Workshop on Multimedia Signal Processing, September 29October 1, 2004, Siena, Italy (2004) 13. P´erezGonz´ alez, F.: The importance of aliasing in structured quantization modulation data hiding. In: International Workshop on Digital Watermarking, Seoul, Korea, pp. 1–17 (2003) 14. P´erezGonz´ alez, F., Balado, F., Hern´ andez, J.R.: Performance analysis of existing and new methods for data hiding with knownhost information in additive channels. IEEE Transactions on Signal Processing, Special Issue on Signal Processing for Data Hiding in Digital Media and Secure Content Delivery 51(4), 960–980 (2003) 15. SomekhBaruch, A., Merhav, N.: On the error exponent and capacity games of private watermarking systems. IEEE Transactions on Information Theory 49(3), 537–562 (2003) 16. SomekhBaruch, A., Merhav, N.: On the capacity game of public watermarking systems. IEEE Transactions on Information Theory 49(3), 511–524 (2004) 17. Tzschoppe, R., B¨ auml, R., Fischer, R., Kaup, A., Huber, J.: Additive NonGaussian Attacks on the Scalar Costa Scheme (SCS). In: Proceedings of IS&T/SPIE 17th Annual Symposium: Electronic Imaging 2005. Security, Steganography, and Watermarking of Multimedia Contents VII, vol. 5681, January 2005, San Jose, USA (2005) 18. VilaForc´en, J.E., Voloshynovskiy, S., Koval, O., P´erezGonz´ alez, F., Pun, T.: Worst case additive attack against quantizationbased watermarking techniques. In: IEEE International Workshop on Multimedia Signal Processing, pp. 135–138, September 29October 1, 2004, Siena, Italy (2004) 19. VilaForc´en, J.E., Voloshynovskiy, S., Koval, O., P´erezGonz´ alez, F., Pun, T.: Worst case additive attack against quantizationbased datahiding methods. In: Proceedings of IS&T/SPIE 17th Annual Symposium: Electronic Imaging 2005. Security, Steganography, and Watermarking of Multimedia Contents VII, January 1620, 2005, San Jose, USA (2005)
Author Index
Bierbrauer, J¨ urgen Fridrich, Jessica Gerling, Ekaterina Imai, Hideki
1
MoralesLuna, Guillermo
23
P´erezGonz´ alez, F. Pun, T. 70
1
70
23 Shikata, Junji
Jamzad, Mansour
23
33
Kermani, Zahra Zahedi Korzhik, Valery 23 Koval, O. 70
33
Venturini, Ilaria 50 VilaForc´en, J.E. 70 Voloshynovskiy, S. 70
23