Image Authentication Method by Combining Digital Signature and Watermarking
Content
IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.1, No.2, April 2007 CSES International ⓒ2007 ISSN 0973-4406
77
Image Authentication Method by Combining Digital Signature and Watermarking
Chia-Hung LU , Hao-Kuan TSO , Der-Chyuan LOU , and David Chien-Ting TAI
1
1 2 3 4
Department of Electrical Engineering, Military Academy Fengshan, Kaohsiung 830, Taiwan E-mail:[email protected]
2
Department of Computer and Information Science, Military Academy Fengshan, Kaohsiung 830, Taiwan E-mail: [email protected] Department of Electrical and Electronic Engineering Chung Cheng Institute of Technology, National Defense University Tahsi, Taoyuan 335, Taiwan E-mail: [email protected]
3
4
Department of Computer and Information Science, Military Academy Fengshan, Kaohsiung 830, Taiwan E-mail: [email protected]
Abstract
An image authentication method combining digital signature and watermarking is proposed in this paper. The proposed method not only can resist Holliman-Memon attack, but also can accurately detect the tampered location of an image. First, a watermark is created from a protected image by using an edge detection technique. Second, the created watermark is divided into blocks and embedded into the 2-LSB (top layer) of the protected image. Third, all block signatures are calculated and embedded into the 1-LSB (low layer) of the protected image. At the low layer, the calculated signatures can resist HollimanMemon attack. At the top layer, the created watermark can accurately detect the tampered location of an image. Experimental results show that the proposed method has good performance in tamper detection compared with the Celik et al.’s method.
Keywords: Image Authentication, Digital Watermarking,
Digital Signature, Tamper Detection, Holliman-Memon Attack.
Digital watermarking directly embeds some information into digital media such as images, audio files and videos [10]. Hence, it can reduce the risk of losing the signature. A general model of watermarking system is shown as Fig. 2 [9]. Generally speaking, digital watermarking techniques can be classified as spatial-domain and transform-domain methods. Spatial-domain methods [6] [4] [11-15] embed some messages in the pixel values of an image directly. It has higher performance in computing but is easy distorted suffering from attacks. The least significant bit (LSB) method is the most common technique for embedding messages in images. The LSB of each pixel of an image can be replaced with some data bits. To increase embedding capacity, many papers have proposed embedding some messages into two or more LSBs of each pixel of an image [11] [16] [17]. Transform domain methods [18-20] are messages embedding into the transformed coefficients. It is more robustness than spatial-domain methods but with low performance. Discrete cosine transform (DCT), discrete wavelet transform (DWT), and singular value decomposition (SVD) are common transform techniques. In the paper, we propose an image authentication method by combining digital signature and watermarking in spatial domain. First, a watermark is created from a protected image by using an edge detection technique. Second, the created watermark is divided into blocks and embedded into the 2-LSB (top layer) of the protected image. Third, all block signatures are calculated and embedded into the 1-LSB (low layer) of the protected image. At the low layer, the calculated signature can resist Holliman-Memon attack
1. Introduction
Multimedia has become more and more popular due to its characteristics of easy duplication and utilization. How to protect the integrity of multimedia has become a very important issue. Multimedia integrity can be authenticated by using digital signature [1-5] and watermarking [6] [7]. Digital signature is a set of features created from a medium itself. These features can be encrypted by using an encryption algorithm and store them into a file. The disadvantage is that it needs extra bandwidth to transmit the signature (shown as Fig. 1 [8]).
Manuscript Received September 1, 2006. Manuscript Revised March 1, 2007
78
IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.1, No.2, April 2007
[24]. At the top layer, the created watermark can detect the accurate location of tampered image. The rest of this paper is organized as follows. Works related to the proposed method are introduced in Section2.
||
embedded into the LSB of X r and form the watermarked image X ′ . The proposed method is described in Section 3. The experimental results are shown in Section 4. Finally, conclusions are drawn in Section 5.
M
H
M
H E
kp
Compareison E Dk
ks Fig. 1 RSA signature method
2. Related Works
Recently, many researches related to image authentication have been published. These proposed methods have the ability to detect the tampered region of an image. The capability is referred to as localization [9]. Most localized authentication methods rely on some ways of block-wise authentication. That is to say, an image is divided into blocks and each block is authenticated respectively. If a block of the image is corrupted, only the affected block fails to authenticate. In 1998, Wong [21] proposed a block-based watermarking technique first. The detailed process is illustrated as follows. The original image X is a gray-level image with M by N pixels. The watermark W is a binary image with M by N pixels formed by tiling a binary image Y. First, the original image X and the watermark W are divided into non-overlapping blocks with m by n pixels respectively, where X r and Wr represent the r block of the original image X and the watermark W. Second, a corresponding ˆ block X r is formed by setting the LSB of each block X r to zero. Third, the image dimension is utilized to compute the hash value as Eq. (1), ˆ (1) H r = H ( M , N , X r ), where H denotes the cryptographic hash function such as MD5 [22]. Forth, the signature of each block is generated by XORing the computed hash value with the corresponding watermark pattern. The above result is encrypted by the public key cryptosystem [23] as Eq. (2), (2) Cr = Ek ( H r ⊕ Wr ), where ⊕ denotes the XOR operation and Ek denotes the encryption function. Finally, the signature
Cr
th
In the verification process, the watermarked image is first partitioned into blocks X r′ and the signature Cr′ is extracted from each block. Second, the image X r′′ is obtained by setting the LSB of the watermarked image to zero. Third, the hash value is computed by using the image dimension and X r′′ as Eq. (3),
H r′ = H ( M , N , X r′′).
(3)
Finally, each block of the watermark Wr′ is obtained by XORing the computed hash value H r′ with the decrypted signatures Cr′ from each block as Eq. (4),
Wr′ = Dk ( H r′ ⊕ Cr′ ).
(4)
where Dk denotes the decryption function. Although the proposed method can detect the tampered region of an image, embedding the hash value into separated block exists a disadvantage. The blocks of the image can be swapped within the image. This is the known HollimanMemon attack [24]. The Holliman-Memon attack is an attack type of applying to block-wise watermark. Both Holliman and Memon consider that embedding the signature into each block of an image only depends on the content of the block, which is referred to as block-wise independence. By utilizing the weakness of the block-wise independence, the attacker can create a new image by assembling the independent and authentic blocks. Furthermore, when an attacker obtains some images, they can be viewed as a large database of
is
Image Authentication Method by Combining Digital Signature and Watermarking
79
these authentic blocks. Hence, if the attacker wants to forge a watermark in an image, the attacker can divide the image into blocks and replace each block with the most similar block from the database. The more the images are, the better the similarities are [9]. To prevent the problem of the Holliman-Memon attack, Wong and Memon [25] proposed another method by embedding every block index to an image. However, the attacker can also launch the counterfeiting attack and create the counterfeiting image from a large database of these watermarked images [25] [26]. Selecting a large block can reduce the effectiveness of the attack. However, if the attacker can obtain quite large images, reasonable forgery can still be happened. Hence, increasing the block size is not a good method to thwart the Holliman-Memon attack [25]. Moreover, using larger blocks will also worsen the accuracy of the tampered localization [4] [9] [26]. The counterfeiting problem mentioned above can be avoided by adding the block dimension [4]. The same authors proposed another method to thwart the attack by including the image index [6]. The method is similar to use a different key for every image and actually solves the problem. However, when an user wants to authenticate the image, the image index must be known in advance by users [6] [26]. Hence, the solution is impractical in real application. Moreover, managing different indexes for all images in a database are also an enormous burden [4]. In 1999, Wu et al. [27] suggested using a larger surrounding neighborhood (e.g., 32 by 32) to be hash and inserted in a smaller block (e.g., 24 by 24). The method is an elegant solution to solve the above problem [4] [6] [25] [26]. However, it will lose the accuracy of the tampered localization [5] [26]. In 2002, Celik et al. [4] proposed another solution to prevent the Holliman-Memon attack. They partition an image into hierarchical structure, and then the signature of each layer is embedded into the LSB of the image respectively. However, when the image is tampered, their method can only find out the block localization of the tampered region rather than the accurate location of the tampered region. Moreover, their solution is very complicated [26]. Based on the above discussion, we propose a new method combining digital signature and watermarking to improve the disadvantage of celik et al.’s method. The proposed method not only can resist HollimanMemon attack, but also can accurately detect the tampered location of an image.
3. The Proposed Method
3.1. The embedding process
The original image X is a gray-level image with M by N pixels, i.e., (5) X = { x(i, j) | 0 ≤ i ≤ M −1,0 ≤ j ≤ N −1,0 ≤ x(i, j) ≤ 255} . Step 1: Set the least two bits of every pixel of the image to zero and obtain the image X ′ . Step 2: Utilize an edge detection technique to create the watermark, i.e.,
W (i , j ) =
s=−a t =−b
∑ ∑ z ( s, t ) x′(i + s, j + t ),
a
b
(6)
where a = ( p − 1) / 2 , b = ( q − 1) / 2 , p × q is size of the filter mask. Step 3: Convert the watermark into binary image. ′ Step 4: Divide the watermark into blocks Wmn , then
permute each block (shown as Fig. 3) and encrypt them by Kp , i.e., % ′ Wmn (i, j ) = K p ⊕ Wmn (i, j ), (7) where ⊕ denotes the XOR operation. Step 5: Embed the watermark into the 2-LSB of every pixel of image X ′ . Step 6: Set the least significant bit of every pixel of the image to zero and divide the image X ′′ into ′′ blocks X mn . Step 7: Compute the larger adjacent blocks (e.g., the 3 by 3 windows), then encrypt them by the private key and insert into the middle block (shown as Fig. 4) as Eq. (8),
′′ S mn = Ek ( H { X m + o , n + p : o, p ∈ {−1, 0,1}}). (8)
s
Step 8: Embed the signature into the 1-LSB of every ˆ ′′′ pixel of X mn and obtain the stego image X . The embedding process of the digital signature and watermarking is shown in Fig. 5. 1 5 9 1 2 6 1 1 3 7 1 1 4 8 1 1 9 1 1 1 1 1 1 1 1 5 3 7 2 6 4 8
Fig.3 Permuting blocks.
80
IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.1, No.2, April 2007
Sliding window
Step 3: Label the corresponding block if the verification result is false in Step 2. Step 4: Extract the watermark from the 2-LSB of every pixel of the stego image, then decrypt them by Kp and recombination blocks to obtain W ′ . Step 5: Set least two bits of every pixel of the stego
ˆ image to zero and create a watermark W by an edge detection technique.
Fig. 4 Computing the larger adjacent blocks and inserting into the middle block.
ˆ Step 6: Convert W into the binary image.
Step 7: Compare the difference between blocks according to the result of Step 3 and label the wrong bit as Eq. (11), ˆ ′ ⎧ True, if Wmn (i, j) = Wmn (i, j) (11) Verfication = ⎨ Otherwise. ⎩False, The extraction process of the digital signature and watermarking is shown in Fig. 6.
Fig. 5 The embedding process of the digital signature and watermarking.
3.2. The verification process
ˆ ˆ Step 1: Divide the stego image X into blocks Xmn , then
extract the signature from the 1-LSB of every
Fig. 6 The extraction process of the digital signature and watermarking.
ˆ pixel of Xmn and decrypt them by the public key,
i.e.,
4. The Experimental Results
We use a gray-level image of size 256 by 256, called “Lena”, as the protected image (as shown in Fig. 7(a)). First, the least two bits of every pixel of the protected image are set to zero. Then the watermark is created by an edge detection technique (as shown in Fig. 7(b)). Finally, the digital signature is created by computing the larger adjacent blocks and inserted into the middle block. Fig. 7(c) shows the result of embedding the watermark and the digital signature into the image. The PSNR (Peak Signal to Noise Ratio) is 42.59 dB. The PSNR is defined as follows:
′ ′ H mn = DK ( S mn ).
p
(9)
′′ Step 2: Obtain Smn by computing the larger adjacent blocks and compare the difference between blocks as Eq. (10), ′ ′′ ⎧ True, if Hmn = H (Smn ) Verfication = ⎨ (10) Otherwise. ⎩False,
Image Authentication Method by Combining Digital Signature and Watermarking
81
PSNR = 10 log10
MSE = 1 m×n
255
2
( dB),
2
(12) (13) (a) (b )
MSE
∑ ∑ ( X ij − X ij′ ) ,
i =0 j =0
m −1 n − 1
where
X ij
and
X ij′ represent the protected image and
stego image respectively. A larger PSNR value represents little difference between the protected image and the stego image. In general, it is very difficult to distinguish the difference between the protected image and the stego image if the PSNR value is greater than 30 dB. To detect whether the stego image is tampered or not, the digital signature and watermarking are extracted from the stego image to verify the integrity of the image. Fig. 7(d) shows the image has been tampered. The labeled block of tampered image is shown in Fig. 7(e). Fig. 7(f) shows the accurate location of the tampered image. Moreover, we use another image with size of 256 by 256, called “Baboon”, to be the protected image (as shown in Fig. 8(a)). Fig. 8(b) shows that the stego-image has been tampered with different range. Fig. 8(c) and Fig. 8(d) show the labeled block and accurate location of the tampered image respectively. The experimental result shows that although the low layer loses the accuracy of the tampered image by using the larger adjacent blocks, the high layer can accurately detect the tampered location of the image. In 2002, Celik et al. [4] proposed an image authentication method with localization. However, by dividing the image into hierarchical structure and computing the signature of each layer, the method is too complicated [26]. Moreover, their method can not accurately detect the tampered location of the image. Table 1 shows the comparison results with the Celik et al.’s method [4]. (a) Table 1 The comparison results of different methods. Hierarchical structure The propose Two layers d method Celik et al.’s even layers method [4] HollimanMemon attack Can resist Tamper detection Accurate location ( b)
(c )
(d)
(e )
(f )
Fig. 7 (a)The protected image, (b)the watermark, (c)the stego image. (d)the tampered image, (e)the labeled region of the tampered image, (f)the accurate location of the tampered image.
(c )
(d)
Can resist
Localization
Fig. 8 (a)The protected image, (b)the tampered image, (c)the labeled block of the tampered image, (d)the accurate location of the tampered image.
82
IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.1, No.2, April 2007
5. Conclusions
In this paper, we describe the main characteristics of digital signature and watermarking. We also summarize some limits of current technologies in tamper detection of digital image. Based on the above observation, we propose an image authentication method combining digital signature and watermarking.
By embedding the digital signature and watermarking into an image, the proposed method not only can resist Holliman-Memon attack, but also can accurately detect the tampered location of the image. Experimental results show that the proposed method has good performance in tamper detection compared with the Celik et al.’s method. In the future, we will focus on the research of recovering the tampered image and enhancing the robustness of watermarking.
[10] F. Gonzalez and J. Hernandez, “A tutorial on digital watermarking,” Proceedings of IEEE 33rd Annual International Carnahan Conference on Security Technology, pp. 286-292, Oct. 1999. [11] D.-C. Lou and J.-L. Liu, “Steganographic method for secure communications,” Computers & Security, Vol. 21, No. 5, Oct. 2002, pp. 449-460. [12] M. Kutter, F. Jordan, and F. Bossen, “Digital signature of color images using amplitude modulation,” Journal of Electronic Imaging, Vol. 7, No. 2, April 1998, pp. 326-332. [13] M. D. Swanson, M. Kobayashi, and A. H. Tewfik, “Multimedia data embedding and watermarking technologies,” Proceedings of IEEE International Conference on spectrum, June 1998, Vol. 86, No. 6, pp. 1064-1087. [14] Z.-M. Lu, D.-G. Xu, and S.-H. Sun, “Multipurpose image watermarking algorithm based on multistage vector quantization,” IEEE Transactions on Image Processing, Vol. 14, No. 6, June 2005, pp. 822-831. [15] M. U. Celik, G. Sharma, A. M. Tekalp, and E. Saber, “Lossless generalized-LSB data embedding,” IEEE Transactions on Image Processing, Vol. 14, No. 2, Feb. 2005, pp. 253-266,. [16] W. N. Lie and L. C. Chang, “Data hiding in images with adaptive numbers of least significant bits based on the human visual system,” Proceedings of IEEE International Conference on Image Processing, Oct. 1999, Vol. 1, pp. 286-290. [17] Y.-K. Lee and L.-H. Chen, “High capacity image steganographic model,” IEE Proceedings - Vision, Image Signal Processing, Vol. 147, No. 3, June 2000, pp. 288-294. [18] C.-T. Hsu and J.-L. Wu, “Hidden digital watermarking in images,” IEEE Transactions on Image Processing, Vol. 8, No. 1, Jan. 1999, pp. 58-68. [19] P. Bao and X. Ma, “Image adaptive watermarking using wavelet domain singular value decomposition,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 15, No. 1, Jan. 2005, pp. 97-102. [20] I. J. Cox, J. Kilian, F. T. Leighton, and T. Shamoon, “Secure spread spectrum watermarking for multimedia,” IEEE Transactions on Image Processing, Vol. 6, No. 12, Dec. 1997, pp. 1673-1687. [21] P. W. Wong, “A public key watermark for image verification and authentication,” Proceedings of ICIP, Chicago, Oct. 1998, IL, pp. 425-429. [22] R. L. Rivest, “The MD5 message digest algorithm,” Tech. Report, 1992. [23] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol. 21, Feb. 1978, pp. 120-126. [24] M. Holliman and N. Memon, “Counterfeiting attacks on oblivious block-wise independent invisible watermarking
References
[1] G. L. Friedman, “The trustworthy digital camera: restoring credibility to the photographic image,” IEEE Transactions on Consumer Electronics, Vol. 39, Nov. 1993, pp. 905910. [2] C.-Y. Lin and S.-F. Chang, “A robust image authentication method distinguishing JPEG compression from malicious manipulation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 11, No. 2, June 1999, pp. 153-168. [3] C.-S. Lu and H.-Y. Liao, “Structural digital signature for image authentication: an incidental distortion resistant scheme,” IEEE Transactions on Multimedia, Vol. 5, No. 2, June 2003, pp. 161-173. [4] M. U. Celik, G. Sharma, and E. Saber, “Hierarchical watermarking for secure image authentication with localization,” IEEE Transactions on Image Processing, Vol. 11, No. 6, June 2002, pp. 585-594. [5] P. W. Wong and N. Memon, “Secret and public key image watermarking schemes for image authentication and ownership verification,” IEEE Transactions on Image Processing, Vol. 10, No. 10, Oct. 2001, pp. 1593-1601. C.-S. Lu and H.-Y. Liao , “Multipurpose watermarking for image authentication and protection,” IEEE Transactions on Image Processing, Vol. 10, No. 10, Oct. 2001, pp. 1579-1592. L. Xie and G. R. Arce, “A class of authentication digital watermarks for secure multimedia communication,” IEEE Transactions on Image Processing, Vol. 10, No. 11, Nov. 2001, pp. 1754-1764. S. William, Cryptography and network security, 3rd Edition, Prentice Hall, Upper Saddle River, New Jersey, 2002.
[6]
[7]
[8]
[9] I. J Cox, M. L. Miller, and J. A. Bloom, Digital watermarking, Morgan Kaufmann, San Francisco, USA, 2002.
Image Authentication Method by Combining Digital Signature and Watermarking
83
schemes,” IEEE Transactions on Image Processing, Vol. 9, No. 3, March 2000, pp. 432-441. [25] M. Holliman and N. Memon, “Secret and public key authentication watermarking schemes that resist vector quantization attack,” Proceedings of SPIE Security and Watermarking of Multimedia Contents, Vol. 3971, No. 40, Jan. 2000, pp. 417−427. [26] Fridrich, “Security of fragile authentication watermarks with localization,” Proceedings of SPIE Security and Watermarking of Multimedia Contents, April 2002, Vol. 4675, pp. 691-700.
[27] C. W. Wu, D. Coppersmith, F. C. Mintzer, C. P. Tresser, and M. M. Yeung, “Fragile imperceptible digital watermark with privacy control,” Proceedings of SPIE Security and Watermarking of Multimedia Contents, Vol. 3657, No. 8, April 1999, pp. 79−84. [28] C. G. Rafael and E. W. Richard, Digital image processing, 2nd Edition, Prentice Hall, Upper Saddle River, New Jersey, 2002.
77
Image Authentication Method by Combining Digital Signature and Watermarking
Chia-Hung LU , Hao-Kuan TSO , Der-Chyuan LOU , and David Chien-Ting TAI
1
1 2 3 4
Department of Electrical Engineering, Military Academy Fengshan, Kaohsiung 830, Taiwan E-mail:[email protected]
2
Department of Computer and Information Science, Military Academy Fengshan, Kaohsiung 830, Taiwan E-mail: [email protected] Department of Electrical and Electronic Engineering Chung Cheng Institute of Technology, National Defense University Tahsi, Taoyuan 335, Taiwan E-mail: [email protected]
3
4
Department of Computer and Information Science, Military Academy Fengshan, Kaohsiung 830, Taiwan E-mail: [email protected]
Abstract
An image authentication method combining digital signature and watermarking is proposed in this paper. The proposed method not only can resist Holliman-Memon attack, but also can accurately detect the tampered location of an image. First, a watermark is created from a protected image by using an edge detection technique. Second, the created watermark is divided into blocks and embedded into the 2-LSB (top layer) of the protected image. Third, all block signatures are calculated and embedded into the 1-LSB (low layer) of the protected image. At the low layer, the calculated signatures can resist HollimanMemon attack. At the top layer, the created watermark can accurately detect the tampered location of an image. Experimental results show that the proposed method has good performance in tamper detection compared with the Celik et al.’s method.
Keywords: Image Authentication, Digital Watermarking,
Digital Signature, Tamper Detection, Holliman-Memon Attack.
Digital watermarking directly embeds some information into digital media such as images, audio files and videos [10]. Hence, it can reduce the risk of losing the signature. A general model of watermarking system is shown as Fig. 2 [9]. Generally speaking, digital watermarking techniques can be classified as spatial-domain and transform-domain methods. Spatial-domain methods [6] [4] [11-15] embed some messages in the pixel values of an image directly. It has higher performance in computing but is easy distorted suffering from attacks. The least significant bit (LSB) method is the most common technique for embedding messages in images. The LSB of each pixel of an image can be replaced with some data bits. To increase embedding capacity, many papers have proposed embedding some messages into two or more LSBs of each pixel of an image [11] [16] [17]. Transform domain methods [18-20] are messages embedding into the transformed coefficients. It is more robustness than spatial-domain methods but with low performance. Discrete cosine transform (DCT), discrete wavelet transform (DWT), and singular value decomposition (SVD) are common transform techniques. In the paper, we propose an image authentication method by combining digital signature and watermarking in spatial domain. First, a watermark is created from a protected image by using an edge detection technique. Second, the created watermark is divided into blocks and embedded into the 2-LSB (top layer) of the protected image. Third, all block signatures are calculated and embedded into the 1-LSB (low layer) of the protected image. At the low layer, the calculated signature can resist Holliman-Memon attack
1. Introduction
Multimedia has become more and more popular due to its characteristics of easy duplication and utilization. How to protect the integrity of multimedia has become a very important issue. Multimedia integrity can be authenticated by using digital signature [1-5] and watermarking [6] [7]. Digital signature is a set of features created from a medium itself. These features can be encrypted by using an encryption algorithm and store them into a file. The disadvantage is that it needs extra bandwidth to transmit the signature (shown as Fig. 1 [8]).
Manuscript Received September 1, 2006. Manuscript Revised March 1, 2007
78
IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.1, No.2, April 2007
[24]. At the top layer, the created watermark can detect the accurate location of tampered image. The rest of this paper is organized as follows. Works related to the proposed method are introduced in Section2.
||
embedded into the LSB of X r and form the watermarked image X ′ . The proposed method is described in Section 3. The experimental results are shown in Section 4. Finally, conclusions are drawn in Section 5.
M
H
M
H E
kp
Compareison E Dk
ks Fig. 1 RSA signature method
2. Related Works
Recently, many researches related to image authentication have been published. These proposed methods have the ability to detect the tampered region of an image. The capability is referred to as localization [9]. Most localized authentication methods rely on some ways of block-wise authentication. That is to say, an image is divided into blocks and each block is authenticated respectively. If a block of the image is corrupted, only the affected block fails to authenticate. In 1998, Wong [21] proposed a block-based watermarking technique first. The detailed process is illustrated as follows. The original image X is a gray-level image with M by N pixels. The watermark W is a binary image with M by N pixels formed by tiling a binary image Y. First, the original image X and the watermark W are divided into non-overlapping blocks with m by n pixels respectively, where X r and Wr represent the r block of the original image X and the watermark W. Second, a corresponding ˆ block X r is formed by setting the LSB of each block X r to zero. Third, the image dimension is utilized to compute the hash value as Eq. (1), ˆ (1) H r = H ( M , N , X r ), where H denotes the cryptographic hash function such as MD5 [22]. Forth, the signature of each block is generated by XORing the computed hash value with the corresponding watermark pattern. The above result is encrypted by the public key cryptosystem [23] as Eq. (2), (2) Cr = Ek ( H r ⊕ Wr ), where ⊕ denotes the XOR operation and Ek denotes the encryption function. Finally, the signature
Cr
th
In the verification process, the watermarked image is first partitioned into blocks X r′ and the signature Cr′ is extracted from each block. Second, the image X r′′ is obtained by setting the LSB of the watermarked image to zero. Third, the hash value is computed by using the image dimension and X r′′ as Eq. (3),
H r′ = H ( M , N , X r′′).
(3)
Finally, each block of the watermark Wr′ is obtained by XORing the computed hash value H r′ with the decrypted signatures Cr′ from each block as Eq. (4),
Wr′ = Dk ( H r′ ⊕ Cr′ ).
(4)
where Dk denotes the decryption function. Although the proposed method can detect the tampered region of an image, embedding the hash value into separated block exists a disadvantage. The blocks of the image can be swapped within the image. This is the known HollimanMemon attack [24]. The Holliman-Memon attack is an attack type of applying to block-wise watermark. Both Holliman and Memon consider that embedding the signature into each block of an image only depends on the content of the block, which is referred to as block-wise independence. By utilizing the weakness of the block-wise independence, the attacker can create a new image by assembling the independent and authentic blocks. Furthermore, when an attacker obtains some images, they can be viewed as a large database of
is
Image Authentication Method by Combining Digital Signature and Watermarking
79
these authentic blocks. Hence, if the attacker wants to forge a watermark in an image, the attacker can divide the image into blocks and replace each block with the most similar block from the database. The more the images are, the better the similarities are [9]. To prevent the problem of the Holliman-Memon attack, Wong and Memon [25] proposed another method by embedding every block index to an image. However, the attacker can also launch the counterfeiting attack and create the counterfeiting image from a large database of these watermarked images [25] [26]. Selecting a large block can reduce the effectiveness of the attack. However, if the attacker can obtain quite large images, reasonable forgery can still be happened. Hence, increasing the block size is not a good method to thwart the Holliman-Memon attack [25]. Moreover, using larger blocks will also worsen the accuracy of the tampered localization [4] [9] [26]. The counterfeiting problem mentioned above can be avoided by adding the block dimension [4]. The same authors proposed another method to thwart the attack by including the image index [6]. The method is similar to use a different key for every image and actually solves the problem. However, when an user wants to authenticate the image, the image index must be known in advance by users [6] [26]. Hence, the solution is impractical in real application. Moreover, managing different indexes for all images in a database are also an enormous burden [4]. In 1999, Wu et al. [27] suggested using a larger surrounding neighborhood (e.g., 32 by 32) to be hash and inserted in a smaller block (e.g., 24 by 24). The method is an elegant solution to solve the above problem [4] [6] [25] [26]. However, it will lose the accuracy of the tampered localization [5] [26]. In 2002, Celik et al. [4] proposed another solution to prevent the Holliman-Memon attack. They partition an image into hierarchical structure, and then the signature of each layer is embedded into the LSB of the image respectively. However, when the image is tampered, their method can only find out the block localization of the tampered region rather than the accurate location of the tampered region. Moreover, their solution is very complicated [26]. Based on the above discussion, we propose a new method combining digital signature and watermarking to improve the disadvantage of celik et al.’s method. The proposed method not only can resist HollimanMemon attack, but also can accurately detect the tampered location of an image.
3. The Proposed Method
3.1. The embedding process
The original image X is a gray-level image with M by N pixels, i.e., (5) X = { x(i, j) | 0 ≤ i ≤ M −1,0 ≤ j ≤ N −1,0 ≤ x(i, j) ≤ 255} . Step 1: Set the least two bits of every pixel of the image to zero and obtain the image X ′ . Step 2: Utilize an edge detection technique to create the watermark, i.e.,
W (i , j ) =
s=−a t =−b
∑ ∑ z ( s, t ) x′(i + s, j + t ),
a
b
(6)
where a = ( p − 1) / 2 , b = ( q − 1) / 2 , p × q is size of the filter mask. Step 3: Convert the watermark into binary image. ′ Step 4: Divide the watermark into blocks Wmn , then
permute each block (shown as Fig. 3) and encrypt them by Kp , i.e., % ′ Wmn (i, j ) = K p ⊕ Wmn (i, j ), (7) where ⊕ denotes the XOR operation. Step 5: Embed the watermark into the 2-LSB of every pixel of image X ′ . Step 6: Set the least significant bit of every pixel of the image to zero and divide the image X ′′ into ′′ blocks X mn . Step 7: Compute the larger adjacent blocks (e.g., the 3 by 3 windows), then encrypt them by the private key and insert into the middle block (shown as Fig. 4) as Eq. (8),
′′ S mn = Ek ( H { X m + o , n + p : o, p ∈ {−1, 0,1}}). (8)
s
Step 8: Embed the signature into the 1-LSB of every ˆ ′′′ pixel of X mn and obtain the stego image X . The embedding process of the digital signature and watermarking is shown in Fig. 5. 1 5 9 1 2 6 1 1 3 7 1 1 4 8 1 1 9 1 1 1 1 1 1 1 1 5 3 7 2 6 4 8
Fig.3 Permuting blocks.
80
IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.1, No.2, April 2007
Sliding window
Step 3: Label the corresponding block if the verification result is false in Step 2. Step 4: Extract the watermark from the 2-LSB of every pixel of the stego image, then decrypt them by Kp and recombination blocks to obtain W ′ . Step 5: Set least two bits of every pixel of the stego
ˆ image to zero and create a watermark W by an edge detection technique.
Fig. 4 Computing the larger adjacent blocks and inserting into the middle block.
ˆ Step 6: Convert W into the binary image.
Step 7: Compare the difference between blocks according to the result of Step 3 and label the wrong bit as Eq. (11), ˆ ′ ⎧ True, if Wmn (i, j) = Wmn (i, j) (11) Verfication = ⎨ Otherwise. ⎩False, The extraction process of the digital signature and watermarking is shown in Fig. 6.
Fig. 5 The embedding process of the digital signature and watermarking.
3.2. The verification process
ˆ ˆ Step 1: Divide the stego image X into blocks Xmn , then
extract the signature from the 1-LSB of every
Fig. 6 The extraction process of the digital signature and watermarking.
ˆ pixel of Xmn and decrypt them by the public key,
i.e.,
4. The Experimental Results
We use a gray-level image of size 256 by 256, called “Lena”, as the protected image (as shown in Fig. 7(a)). First, the least two bits of every pixel of the protected image are set to zero. Then the watermark is created by an edge detection technique (as shown in Fig. 7(b)). Finally, the digital signature is created by computing the larger adjacent blocks and inserted into the middle block. Fig. 7(c) shows the result of embedding the watermark and the digital signature into the image. The PSNR (Peak Signal to Noise Ratio) is 42.59 dB. The PSNR is defined as follows:
′ ′ H mn = DK ( S mn ).
p
(9)
′′ Step 2: Obtain Smn by computing the larger adjacent blocks and compare the difference between blocks as Eq. (10), ′ ′′ ⎧ True, if Hmn = H (Smn ) Verfication = ⎨ (10) Otherwise. ⎩False,
Image Authentication Method by Combining Digital Signature and Watermarking
81
PSNR = 10 log10
MSE = 1 m×n
255
2
( dB),
2
(12) (13) (a) (b )
MSE
∑ ∑ ( X ij − X ij′ ) ,
i =0 j =0
m −1 n − 1
where
X ij
and
X ij′ represent the protected image and
stego image respectively. A larger PSNR value represents little difference between the protected image and the stego image. In general, it is very difficult to distinguish the difference between the protected image and the stego image if the PSNR value is greater than 30 dB. To detect whether the stego image is tampered or not, the digital signature and watermarking are extracted from the stego image to verify the integrity of the image. Fig. 7(d) shows the image has been tampered. The labeled block of tampered image is shown in Fig. 7(e). Fig. 7(f) shows the accurate location of the tampered image. Moreover, we use another image with size of 256 by 256, called “Baboon”, to be the protected image (as shown in Fig. 8(a)). Fig. 8(b) shows that the stego-image has been tampered with different range. Fig. 8(c) and Fig. 8(d) show the labeled block and accurate location of the tampered image respectively. The experimental result shows that although the low layer loses the accuracy of the tampered image by using the larger adjacent blocks, the high layer can accurately detect the tampered location of the image. In 2002, Celik et al. [4] proposed an image authentication method with localization. However, by dividing the image into hierarchical structure and computing the signature of each layer, the method is too complicated [26]. Moreover, their method can not accurately detect the tampered location of the image. Table 1 shows the comparison results with the Celik et al.’s method [4]. (a) Table 1 The comparison results of different methods. Hierarchical structure The propose Two layers d method Celik et al.’s even layers method [4] HollimanMemon attack Can resist Tamper detection Accurate location ( b)
(c )
(d)
(e )
(f )
Fig. 7 (a)The protected image, (b)the watermark, (c)the stego image. (d)the tampered image, (e)the labeled region of the tampered image, (f)the accurate location of the tampered image.
(c )
(d)
Can resist
Localization
Fig. 8 (a)The protected image, (b)the tampered image, (c)the labeled block of the tampered image, (d)the accurate location of the tampered image.
82
IJCSES International Journal of Computer Sciences and Engineering Systems, Vol.1, No.2, April 2007
5. Conclusions
In this paper, we describe the main characteristics of digital signature and watermarking. We also summarize some limits of current technologies in tamper detection of digital image. Based on the above observation, we propose an image authentication method combining digital signature and watermarking.
By embedding the digital signature and watermarking into an image, the proposed method not only can resist Holliman-Memon attack, but also can accurately detect the tampered location of the image. Experimental results show that the proposed method has good performance in tamper detection compared with the Celik et al.’s method. In the future, we will focus on the research of recovering the tampered image and enhancing the robustness of watermarking.
[10] F. Gonzalez and J. Hernandez, “A tutorial on digital watermarking,” Proceedings of IEEE 33rd Annual International Carnahan Conference on Security Technology, pp. 286-292, Oct. 1999. [11] D.-C. Lou and J.-L. Liu, “Steganographic method for secure communications,” Computers & Security, Vol. 21, No. 5, Oct. 2002, pp. 449-460. [12] M. Kutter, F. Jordan, and F. Bossen, “Digital signature of color images using amplitude modulation,” Journal of Electronic Imaging, Vol. 7, No. 2, April 1998, pp. 326-332. [13] M. D. Swanson, M. Kobayashi, and A. H. Tewfik, “Multimedia data embedding and watermarking technologies,” Proceedings of IEEE International Conference on spectrum, June 1998, Vol. 86, No. 6, pp. 1064-1087. [14] Z.-M. Lu, D.-G. Xu, and S.-H. Sun, “Multipurpose image watermarking algorithm based on multistage vector quantization,” IEEE Transactions on Image Processing, Vol. 14, No. 6, June 2005, pp. 822-831. [15] M. U. Celik, G. Sharma, A. M. Tekalp, and E. Saber, “Lossless generalized-LSB data embedding,” IEEE Transactions on Image Processing, Vol. 14, No. 2, Feb. 2005, pp. 253-266,. [16] W. N. Lie and L. C. Chang, “Data hiding in images with adaptive numbers of least significant bits based on the human visual system,” Proceedings of IEEE International Conference on Image Processing, Oct. 1999, Vol. 1, pp. 286-290. [17] Y.-K. Lee and L.-H. Chen, “High capacity image steganographic model,” IEE Proceedings - Vision, Image Signal Processing, Vol. 147, No. 3, June 2000, pp. 288-294. [18] C.-T. Hsu and J.-L. Wu, “Hidden digital watermarking in images,” IEEE Transactions on Image Processing, Vol. 8, No. 1, Jan. 1999, pp. 58-68. [19] P. Bao and X. Ma, “Image adaptive watermarking using wavelet domain singular value decomposition,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 15, No. 1, Jan. 2005, pp. 97-102. [20] I. J. Cox, J. Kilian, F. T. Leighton, and T. Shamoon, “Secure spread spectrum watermarking for multimedia,” IEEE Transactions on Image Processing, Vol. 6, No. 12, Dec. 1997, pp. 1673-1687. [21] P. W. Wong, “A public key watermark for image verification and authentication,” Proceedings of ICIP, Chicago, Oct. 1998, IL, pp. 425-429. [22] R. L. Rivest, “The MD5 message digest algorithm,” Tech. Report, 1992. [23] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol. 21, Feb. 1978, pp. 120-126. [24] M. Holliman and N. Memon, “Counterfeiting attacks on oblivious block-wise independent invisible watermarking
References
[1] G. L. Friedman, “The trustworthy digital camera: restoring credibility to the photographic image,” IEEE Transactions on Consumer Electronics, Vol. 39, Nov. 1993, pp. 905910. [2] C.-Y. Lin and S.-F. Chang, “A robust image authentication method distinguishing JPEG compression from malicious manipulation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 11, No. 2, June 1999, pp. 153-168. [3] C.-S. Lu and H.-Y. Liao, “Structural digital signature for image authentication: an incidental distortion resistant scheme,” IEEE Transactions on Multimedia, Vol. 5, No. 2, June 2003, pp. 161-173. [4] M. U. Celik, G. Sharma, and E. Saber, “Hierarchical watermarking for secure image authentication with localization,” IEEE Transactions on Image Processing, Vol. 11, No. 6, June 2002, pp. 585-594. [5] P. W. Wong and N. Memon, “Secret and public key image watermarking schemes for image authentication and ownership verification,” IEEE Transactions on Image Processing, Vol. 10, No. 10, Oct. 2001, pp. 1593-1601. C.-S. Lu and H.-Y. Liao , “Multipurpose watermarking for image authentication and protection,” IEEE Transactions on Image Processing, Vol. 10, No. 10, Oct. 2001, pp. 1579-1592. L. Xie and G. R. Arce, “A class of authentication digital watermarks for secure multimedia communication,” IEEE Transactions on Image Processing, Vol. 10, No. 11, Nov. 2001, pp. 1754-1764. S. William, Cryptography and network security, 3rd Edition, Prentice Hall, Upper Saddle River, New Jersey, 2002.
[6]
[7]
[8]
[9] I. J Cox, M. L. Miller, and J. A. Bloom, Digital watermarking, Morgan Kaufmann, San Francisco, USA, 2002.
Image Authentication Method by Combining Digital Signature and Watermarking
83
schemes,” IEEE Transactions on Image Processing, Vol. 9, No. 3, March 2000, pp. 432-441. [25] M. Holliman and N. Memon, “Secret and public key authentication watermarking schemes that resist vector quantization attack,” Proceedings of SPIE Security and Watermarking of Multimedia Contents, Vol. 3971, No. 40, Jan. 2000, pp. 417−427. [26] Fridrich, “Security of fragile authentication watermarks with localization,” Proceedings of SPIE Security and Watermarking of Multimedia Contents, April 2002, Vol. 4675, pp. 691-700.
[27] C. W. Wu, D. Coppersmith, F. C. Mintzer, C. P. Tresser, and M. M. Yeung, “Fragile imperceptible digital watermark with privacy control,” Proceedings of SPIE Security and Watermarking of Multimedia Contents, Vol. 3657, No. 8, April 1999, pp. 79−84. [28] C. G. Rafael and E. W. Richard, Digital image processing, 2nd Edition, Prentice Hall, Upper Saddle River, New Jersey, 2002.
