Fuzzy Image Authentication with Error Localization and Correction

Abstract

Traditionally, multimedia data such as audio, images, and videos have been protected using message authentication code (MAC) for authenticity and integrity verification. Standard MAC algorithms are very good at strict protection against manipulations. However, the sensitivity of a standard MAC is extremely high to manipulations, making it unsuitable for application in multimedia, where minor modifications are sometimes acceptable. Multimedia data, such as images, are usually pre-processed with standard image processing operations, compression, quantization, etc. which modifies the original image data. This processing yields the integrity verification and authentication on images to fail if the standard MAC based algorithms are used. Retransmissions may help in reducing the problem to a certain extent; however, retransmissions might not be possible over a unidirectional channel or in real-time transmissions where receiving an authentic part of an image (or other signals in general such as audio or video) might be better than having no image at all. There are specialized algorithms for image authentication which are tolerant to a certain degree of modifications in the data, introduced by channel noise or image processing operations. Such algorithms are called fuzzy authentication algorithms (Ur-Rehman O, Applications of Iterative Soft Decision Decoding, 2013) or fuzzy image authentication algorithms when applied to images. The decision of these authentication algorithms is not a strict binary decision as that of a standard MAC. Such algorithms are tolerant to modifications and this tolerance level can be adjusted by adjusting the parameters of the algorithm to vary their lenience to modifications. Fuzzy image authentication algorithms should be designed in a manner that they can differentiate legitimate manipulations from illegitimate manipulations. Many such algorithms have been proposed in literature for image authentication. These algorithms are normally based on image content rather than the data itself. Even if certain operations such as compression, quantization, etc. are applied, the content of the image remains unchanged. In this chapter, algorithms for fuzzy image authentication, with error localization and correction capabilities are discussed. Once the modifications in the image are localized to a specific region within the image, they can be corrected using the error correcting codes embedded in the authentication algorithms. These fuzzy image authentication algorithms will help in partial image acceptance despite minor errors left uncorrected by the error correcting codes. Simulation results given in this chapter show how such algorithms react to bit (and/or block) errors and how the error correction and fuzzy authentication has little or no visual impact on the resultant image quality.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

5.1 Introduction

During the transmission of multimedia data from source to sink, multiple elements may contribute to data alteration. These elements typically include quantization mechanisms inside the source encoder (or decoder), compression mechanisms, such as lossy compression, and the channel noise, such as the one induced by a wireless medium. In order to cope with such forms of data modifications, communication systems typically employ error correcting codes, which add protection (parity) bits to the original data in such a manner that some or all of the modifications (or errors) in the data can be corrected. Some of the most widely used error correcting codes include Reed–Solomon (RS) codes [1], turbo codes [2] and low density parity check (LDPC) codes [3]. These error correcting codes are good at correcting a certain predefined number of bit modifications. However, if the number of errors exceeds the error correction capability of the codes, they are not correctable. In such a situation, different mechanisms are employed by the data transmission protocols for data recovery. Automatic Repeat reQuest (ARQ) [4] (or its variant called Hybrid-ARQ) is an example of such protocols, where the erroneous data is retransmitted up to a few times, until either the data is received as intended or a threshold number of retransmissions have been done. Most of these communication protocols use error detection codes, such as cyclic redundancy code (CRC) [5] or a message authentication code (MAC) [6, 7], to verify the integrity of data. Hashed message authentication code (HMAC) [8], such as SHA-2, is used as a means to authenticate the origin of the data in addition to its integrity.

Standard MAC and HMAC algorithms are designed such that even a single bit modification in the data changes its MAC by almost 50 %. These authentication algorithms are “hard authentication” algorithms, where the authentication decision is a strict “NO” when the data or its MAC has changed even by a single bit. In such a case, the transmitted image (or a videoframe) will not be accepted as authentic at the receiver. In case of multimedia, such as an image or a videoframe, a few bit modifications might not have any visual impact on the content of the multimedia due to the nature of multimedia and the human visual perceptual system. For example, a few modifications in the least significant bits of an image data might not change the content and a bare human eye might not be able to differentiate between the original and modified image. If it is not possible to perform retransmissions using (H)-ARQ, e.g., either there is no feedback channel or a real-time communication is intended, or if the number of errors exceeds the error correction capability of the channel codes, the erroneous multimedia content will usually be discarded if hard authentication algorithms are used. In such a case, the receiver might interpolate or extrapolate the data, e.g., in a video stream the previous frame might be re-played or a blank frame might be inserted between the previous and the next frame. This is due to the fact that in some applications, it is be better to have partial data than no data at all.

In order to solve this issue, fuzzy authentication algorithms [9] have been introduced in literature. Primarily, these algorithms include approximate message authentication code (AMAC) [10], image message authentication code (IMAC) [11] and noise tolerant message authentication code (NTMAC) [12]. Some fuzzy as well as standard hard authentication algorithms, tailored specifically for multimedia data, have also been proposed [13–16]. In most of the cases, these algorithms work in little or no coordination with the other modules of the communication systems. This means normally the source coding module has little to do with the cryptographic module and the cryptographic module performs in little coordination with the channel coding. Recently, it has been shown that a better coordination between the different components of communication system improves the channel coding results as well as the authentication results [17]. Some recent fuzzy authentication algorithms, where different components of a communication system interact for authentication as well as error localization and recovery from some errors, are weighted noise tolerant authentication code (WNTMAC) [15], error correcting noise tolerant message authentication code (EC-NTMAC) [18, 19]. In WNTMAC, a different weight is assigned to important and non-important parts of a message. Important parts are provided more protection than the non-important parts. More efforts are spent on the important blocks to identify and correct errors, whereas lesser efforts are spent on the data parts of lesser importance. In EC-NTMAC, the NTMAC algorithm for fuzzy authentication is extended and error correction capability is integrated into the fuzzy authentication algorithm to do error correction in addition to fuzzy authentication. Applications in image authentication together with simulation results are given in [18, 19].

This chapter is organized as follows. In Sect. 5.2, a brief overview of the building blocks used in the fuzzy image authentication algorithms is given. This includes the frequency domain transformation, such as discrete cosine transform and error correcting codes such as turbo codes. In Sect. 5.3, applications of error correcting codes in image authentication are discussed. In Sect. 5.4, two fuzzy authentication algorithms for image authentication based on the integration of error correcting codes are discussed. The performance and security analysis of these algorithms is given in Sect. 5.5. Finally, simulation results are shown in Sect. 5.6 to show the performance.

5.2 Building Blocks of the Fuzzy Image Authentication Algorithms

5.2.1 Content Based Authentication

In order to have the capability to authenticate multimedia data, such as images or videoframes (this chapter discusses only image authentication from this point onward), despite certain changes in the original data, it is advantageous to base the authentication on the content rather than the actual data. The actual data of an image, such as the bit or byte values might change due to quantization, compression, etc. The features of an image are, however, not changed by small modifications. Image authentication based on its content or distinct features, rather than the actual data, is called content-based authentication. Different feature extraction techniques have been proposed in literature by the image processing community. The features can be as simple as the image contour, edges, Fourier, wavelet, or cosine transform coefficients or more complex features such as those based on the image textures. The fuzzy authentication algorithms discussed in this chapter are based on the frequency domain features obtained using the discrete cosine transform (DCT) [22] of an image.

5.2.2 Discrete Cosine Transform

DCT [22] is one of the most widely used techniques in image processing. Other widely used transforms are the discrete Fourier transform (DFT) and the discrete wavelet transform (DWT). Chen and Pratt [20] pioneered the application of DCT in image processing. DCT removes correlation from image data, after which each transform coefficient can be encoded independently without devitalizing compression efficiency [21]. Since DCT combines most of the energy in a few transform elements, it is preferred as compared to DFT.

DCT of a matrix (called a block in image processing terminology) is defined as follows [22, 24]:

$$X(l,k) = \alpha (l)\alpha (k)\frac{2}{N}\sum\limits_{m = 0}^{N - 1} {\sum\limits_{n = 0}^{N - 1} x (m,n)\;cos\left[ {\frac{{\pi (2n + 1)}}{{2N}}} \right]} .$$

(5.1)

where,

$$\alpha (i) = \left\{ \begin{array}{l} 1/\sqrt 2 \;,\;i = 0\\ 1\;,\;1 \le i \le N - 1 \end{array} \right.$$

It can be observed from (1) that the element at the index (0, 0) of the DCT (called DC element) represents the average intensity of the corresponding block and contains most of the energy and perceptual information. Elements at the indexes other than (0, 0) are known as AC elements. AC elements in the upper minor diagonals have more information as compared to the AC elements in the lower minor diagonals. If the DC components together with a reasonable number of AC components are retained, e.g., by passing the DCT elements through a low-pass filter, the inverse transform of the DCT (IDCT) can reconstruct the original block with some or no loss in quality. By increasing the number of AC components, the loss in the quality of reconstruction decreases.

The inverse of a 2-D DCT for l, k = 0, 1, …, N − 1 can be calculated as follows,

$$ x(l,\,k)=\alpha (l)\alpha (k)\frac{2}{N}\sum_{m=0}^{N-1}{\sum_{n=0}^{N-1}{X(m,\,n)\cos \left[\frac{\pi (2m+1)}{2N} \right]\cos \left[\frac{\pi (2n+1)}{2N} \right]}}$$

(5.2)

5.2.3 Error Correcting Codes

5.2.3.1 Error Correcting Codes in Image Authentication

Error correcting codes, such as RS codes, turbo codes, or LDPC codes, are used to detect and correct the errors introduced in the data by different means, such as by the transmission noise over a communication channel or during storage over a storage medium. The choice of error correcting codes depends on the noise environment and the desired error correction capability. RS codes are good at correcting burst errors in addition to the sporadic errors and work more naturally on symbols. LDPC codes and turbo codes operate on large data sets such as multimedia data and their error correction capability has been demonstrated to be very closer to the Shannon limit [24]. Error correcting codes, when combined with image authentication, increase the tolerance of the authentication algorithm. They also help in identification of the error location and correcting the errors if they are within the error correction capability. Mostly such errors are due to unintentional modifications and therefore in a small number. In this section, a short introduction of some of most widely used error correcting codes is given. These codes are also used in the algorithms discussed next and therefore, they are introduced here before their application is discussed.

5.2.3.2 Reed–Solomon Codes

RS codes were proposed by Reed and Solomon in their legendry paper [1]. RS codes are nonbinary cyclic codes. RS codes work on symbols rather than bits, where each symbols is a Galois field (GF) element. Each symbol is made up of m-bits, such that m is an integer and usually 2 ≤ m ≤ 8. The m-bit elements are defined over the Galois Field GF(q), where q = p^m and p is a prime number typically chosen to be 2. RS codes are linear block codes, which mean that they encode data in blocks. An RS(n, k) code takes a data block of k symbols and protect it by appending n − k parity symbols to produce a block of n symbols.

Here,

$$ 0<\text{k}<\text{n}<{{\text{p}}^{\text{m}}}+2 $$

(5.3)

The error correcting capability of RS codes is measured in symbols instead of bits. Thus, a burst of bit errors can be grouped in to fewer symbols and then corrected as symbols. The choice of the number of parity symbols dictates how many errors should be corrected by the RS(n, k) codes. If t symbol errors are desired to be corrected by the RS(n, k) code, then n − k must be chosen such that 2t ≤ n − k.

RS codes are also good at correcting erasures, where erasures are the errors whose positions are known in advance via some a priori knowledge. The joint error and erasure correction capability of RS codes is expressed as,

$$ 2{{\text{N}}_{\text{e}}}+{{\text{N}}_{\text{r}}}\le \text{n}-\text{k} $$

(5.4)

where N_e is the number of errors and N_r is the number of erasures. (4) means that if t symbol errors are to be corrected (i.e., N_e = t and N_r = 0), then 2t parity symbols are needed. If only erasure correction is desired, then erasures equal to twice the number of errors are correctable, i.e., up to 2t erasures can be corrected.

The decoding algorithm for RS codes can either be a hard or a soft decision decoder. Hard decision decoders are the ones that operate on discrete values. Most widely used hard decision decoding algorithms for RS codes are Berlekamp–Massey [25] algorithm and the Euclidean algorithm [26]. Soft decision decoders, on the other hand, operate on continuous values or floating point numbers. They usually take soft values at the input and generate soft values at the output (soft input soft output (SISO) decoders). However, in general they can also generate only hard output. Well-known soft decision decoding algorithms for RS codes are Guruswami–Sudan [27] decoding algorithm and the Koetter-Vardy [28] decoding algorithm. A more generalized approach is to output a list of codewords when it is not possible to decide on one codeword, e.g., multiple codewords are equiprobable to have been transmitted, given the received word. This approach is called list decoding [29].

Since the hard decision decoders operate on the quantized data, where some information is lost during quantization, their decoding performance is typically not as good as that of the corresponding soft decision decoder [9].

5.2.3.3 Turbo Codes

Turbo codes, proposed by Berrou, Glavieux, and Thitimajshima in 1993, were the first practical codes shown to approach the channel capacity [2]. Turbo codes are theoretically a concatenation of two codes connected by an interleaver. In practice, the constituent codes are usually convolutional codes connected in parallel. For encoding, the input data is interleaved and passed through the encoders. Without loss of generality, it can be said that the input data is passed through an identity interleaver and then through the first encoder and in parallel the input data is passed through another (nonidentity) interleaver before the second encoder. The result is the original data and two encoded sequences or the parity bits.

The decoder for turbo codes is usually a soft decision iterative decoder. The decoder’s task is to find the most probable codeword based on the demodulated received sequences and a priori knowledge or probabilities about the messages and their occurrence. The decoding in turbo codes is performed by two decoders, each one capable of working on soft input and producing soft output—or the likelihood information about the output bits. The most common SISO decoding algorithms are soft output viterbi algorithm (SOVA) and the maximum a posteriori orobability (MAP) decoding algorithm. The decoding is performed in turns by the constituent decoders. It starts with one decoder and the output of the decoder is an estimate of the first codeword. This estimate is used as a priori information in improving the decoding results of the second decoder, which works on the second encoded sequence and the interleaved output of the first decoder. The used interleaver is the same as the one used in the encoding. This decoding process is repeated iteratively, each time improving the confidence level in the decoded sequence and increasing the reliability of the decoded bits. Repeating the iterations many times would result in a convergence to a final decision about the most probable codeword.

The likelihood of the input and the output bits in the decoders are normally represented as log likelihood ratios (LLRs). The LLR of each bit is based on the a priori probability of the bit and the current observation of the bit. If the sequence to be decoded is x = (x₁, x₂, x₃, …, x_n), then the LLR of each bit x_i can be represented as,

$$ LLR({{x}_{i}})=\log \frac{\Pr ({{x}_{i}}=1,observation)}{\Pr ({{x}_{i}}=0,observation)} $$

(5.5)

It can be noticed from (5) that the LLR of a bit is based on the a priori probabilities of that bit and the current observation of the bit value.

5.3 Applications of Error Correcting Codes in Image Authentication

In practice, it is important to not only authenticate an image and verify its integrity but also to locate any modifications in the image. Existence of modifications can be detected using CRC [5], MACs [6, 7], digital signatures or digital watermarking [30]. Additionally, it is also very important to locate the exact positions of modifications, to as fine grained level as possible, to find out which objects in the image have changed. However, recently it is getting important to look for methods to do error correction in addition to error detection and localization. Error correcting codes, such as RS and turbo codes, have been used in image authentication algorithms to get an additional error localization and correction capability. They have been widely used in detecting errors in the image, isolating the (potentially) erroneous locations and if possible correcting those (potentially) erroneous parts of the image. When combined with the authentication mechanisms, the error correcting codes can help in partial image recovery even if complete image recovery is not possible. This is particularly helpful in multimedia streams, where a partially authentic image (or part wise authentic image) might be more useful than having no image at all.

In [11], approximate image message authentication codes (A-IMACs) approach for fuzzy image authentication is proposed. The proposed A-IMAC is tolerant to small image modifications but at the same time it is capable of detecting and locating intentional tampering. A-IMAC is based on different composite techniques such as block smoothing, block averaging, parallel AMAC and image histogram enhancement. The performance of A-IMAC in discussed in [11] for three image modification scenarios, i.e., JPEG compression, image forgery, and additive Gaussian noise.

Digital watermarking methods for image authentication with error detection and reconstruction, based on error correcting codes, have also been proposed in literature [31–33]. In [31], RS codes are used to generate parity symbols for each row and column of an image. The resultant parity symbols (as bits) are then embedded as a watermark in the two least significant bit planes of the image. If the watermarked image changes, such that the RS decoder can correct the changes, they are corrected to restore the original image data. A scrambling method is used such that a burst of data modifications is transformed into random noise.

In [32], a watermarking approach is proposed in which the image is divided into blocks and the block hash is encoded with a systematic error correcting code. The parity symbols are then embedded into the blocks. During verification, the hash of each block is recovered with the embedded parity symbols, if the number of tampered blocks does not exceed a threshold value. The size of parity symbols is smaller than the total size of block hashes.

In [33], two techniques for self-embedding an image in itself are introduced with the aim to protect the image content. The self-embedding helps in recovering portions of the image which are cropped, replaced, damaged, or tampered in general. In the first method, the 8 × 8 blocks of an image are transformed into frequency domain using DCT and after quantizing the coefficients they are embedded in the least significant bits of other, distant blocks. This method provides a good quality of reconstruction but it is very fragile and can be classified as fragile watermarking technique [30]. The second method is based on the principle similar to differential encoding where a circular shift of the original image with decreased color depth is embedded into the original image. It is shown that the quality of the reconstructed image degrades with the increasing level of noise in the tampered image. This method can be classified as a semi-robust watermark [30].

5.4 Fuzzy Image Authentication Codes with Error Localization and Correction

5.4.1 Fuzzy Authentication Based on Image Features

The algorithms introduced in this section (for error correction and soft authentication) are based on image features extracted in the transform domain. The aim is to authenticate the images in the presence of minor modifications and to be able to locate and correct those modifications before declaring the image authentic or unauthentic. Another aim is to be able to locate major modifications in the images protected with the proposed fuzzy authentication algorithms. The features extracted from images are protected by error correcting codes so that minor changes in the features can be reconstructed in case of noise or distortions. This means that as long as the features are correct or correctable, the image is considered authentic, but if the features are distorted to an extent that the reconstruction is not possible, then the image is declared unauthentic. There are many other ways of capturing the features of an image, such as those based on edge detection to capture the contours of image objects, corner detection, blob detection, affine invariant features, image gradient-based features, etc. [34].

The features based on the frequency domain transform, such as DFT, DWT, or DCT are usually extracted by splitting the image into equal sized smaller blocks. Typical dimensions of a block used in practice are 8 × 8 pixels, such as in JPEG and JPEG2000 [35, 36]. Then the desired transform is applied on image block by block. DCT is used in this chapter for frequency domain transformation. The high energy components in the DCT of a block capture the most essential features. Thus, if a “reasonable number” of high energy components are retained, the block can be reconstructed through the inverse DCT (IDCT). This reasonable number determines the quality of reconstruction. If the number of retained components is too small, the quality of reconstruction is not satisfactory. If the number of retained components is increased, the quality of reconstruction is improved. This number also determines the quality of compression and decompression and is represented through the different quantization matrices in JPEG2000.

5.4.2 Image Error Correcting Column-Wise Message Authentication Code (IECC-MAC)

The algorithms for error correction and fuzzy authentication of images introduced in this chapter are based on DCT. The first algorithm is called IECC-MAC [18]. It protects the DC coefficients (as they are the most important) of an image by standard MACs and performs fuzzy authentication with error tolerance on the received (noisy) images. The algorithm is able to localize errors to a smaller part of the modified image and to correct a certain number of these modifications. The algorithms for sender and the receiver side are explained below. Definition 1 is essential to understand the concept of the proposed algorithms,

Definition 1

Suppose that a message M is transmitted over a noisy medium along with its n-bit MAC, denoted as H. Let Mʹ be the received message and Hʹ be the received MAC. Let Hʺ be the MAC recalculated on Mʹ and let d be a small positive integer (d ≪ n). Mʹ is called d-fuzzy-authenticated if HD(Hʹ, Hʺ) ≤ d, where HD is the Hamming distance.

This method of fuzzy authentication, where the Hamming distance between H′ and H″ does not have to be equal to zero for message acceptance, is based on the fact that the MACs of two different messages cannot be the same or even close to each other, in order to avoid near collision attacks [16, 37].

For the sake of simplicity, let’s assume that an N × N pixel image has to be transmitted. For other dimensions, padding or row/column repetitions etc. can be used. Let the image be divided into m × m pixel blocks such that m|N, where both N and m are positive integers and m is typically equal to 8. DCT is calculated for each block and the DC components are chosen for protection, by storing them in a DC matrix corresponding to the DC elements of the whole image. This process is described in Fig. 5.1.

Fig. 5.1

Perform DCT block-wise and keep the DC element.

Standard MAC is computed column-wise on the DC matrix (one MAC for each column of DC elements) to get a total of N/m MACs. These MACs are combined together to get a column-wise MAC (C-MAC) and transmitted together with the compressed image. A compression is achieved by keeping the DC coefficient and the first few minor diagonals of each DCT matrix, which can be chosen according to the desired image quality as is done in JPEG [35]. An inverse DCT (IDCT) of each DCT matrix (with the DC element and reduced number of AC elements) gives a compressed image. The process of calculation of C-MACs and then combining them to get IECC-MAC is shown in Fig. 5.2.

Fig. 5.2

IECC-MAC tag calculation on the DC elements of columns of blocks.

The receiver receives the (potentially noisy) compressed image I′ and its (potentially noisy) C-MAC′. The receiver recalculates a C-MAC (denoted as C-MAC″) on the image I′ using the same steps as above. C-MAC′ is then compared with C-MAC″ for each of the component MACs. If the Hamming distance between the recalculated MAC (denoted as H″) and the received MAC (called H′) of a column of DC elements is lower than d, i.e., if M′ is not d-fuzzy-authenticated according to definition 1, the corresponding column of blocks in the image I′ is marked as suspicious, otherwise the column is declared to be authentic. The marked columns are called suspicious as they might potentially have errors. After the suspicious columns are marked, they are tried to be corrected using the bit reliability values or the LLRs of each bit.

The LLRs can be obtained from the SISO channel decoder, for example the MAP decoder for turbo codes. If no channel decoder is used, then the channel measurements are taken as the LLRs of each bit. Based on these LLRs and the received signal values, error correction is attempted. The process of error correction works as follows: The bits of the marked suspicious columns are sorted based on their absolute values of LLRs. A combination of least reliable bits is then flipped, followed by recalculation of the MAC (H″) on the DC components of the (bit-flipped) column and calculating its Hamming distance with H′. If the bit-flipped form of marked column is d-fuzzy-authenticated, the corresponding column of blocks in the received image (I′) is accepted as authentic; otherwise, the iterations are continued till a maximum (threshold) number of iterations have been performed. The error localization and correction is shown in Fig. 5.3.

Fig. 5.3

Error localization and correction using IECC-MAC

The threshold on the maximum number of iterations (T_itr) is predefined and is given by,

$$ {{\text{T}}_{\text{itr}}}={{2}^{{}\eta{}}}$$

(5.6)

where η is a small positive integer (typically, 0 ≤ η ≤ 24). T_itr can be made adaptive, by choosing the value of η depending on the bit error rate (BER) and also based on the application demand.

The error localization property of IEC-MAC algorithm needs to be further optimized because IEC-MAC localizes errors to the column level. It would be better to localize errors, correct them, and perform fuzzy authentication at the block level. Due to the errors being localized at the column level, extra processing for iterative error correction is required. To improve the error localization, another algorithm called the image error correcting-noise tolerant message authentication code (IEC-NTMAC) is introduced. IEC-NTMAC is based on the EC-NTMAC algorithm [16] and marks the image blocks as suspicious, as opposed to the columns of image blocks, which is done by IEC-MAC.

5.4.3 Image Error Correction Noise Tolerant Message Authentication Code (IEC-NTMAC)

For error localization to a more fine grained level, an algorithm based on the EC-NTMAC [15] is proposed. It has an enhanced error localization and image recovery capability as compared to IEC-MAC.

The IEC-NTMAC algorithm works by calculating an NTMAC for each of the DC component in the DCT sub-matrix. Although a complete standard MAC is calculated for each DC component, only a small portion (called sub-MAC) is retained, e.g., the last s-bits of the MAC (see NTMAC and W-NTMAC [15]). All of these sub-MACs are appended together to constitute a complete NTMAC for each column of the DC matrix. Now the same step is repeated for all the columns, giving N/m NTMACs. Using an NTMAC not only improves the error localization to block level but also improves the error correction. The reason is that smaller blocks can be corrected more efficiently (in terms of processing power and memory consumption) as compared to the whole column of blocks.

IEC-NTMAC generation for an image I is shown in Fig. 5.4.

Fig. 5.4

Calculation of IEC-NTMAC at the sender side.

The receiver receives a compressed image (denoted as I′) as well as its IEC-NTMAC (denoted as IEC-NTMAC′). The receiver recalculates the IEC-NTMAC on I′ by using the same algorithm as explained above (let the recalculated IEC-NTMAC be denoted as IEC-NTMAC″). IEC-NTMAC′ is compared with IEC-NTMAC″ through a comparison of the corresponding sub-MACs. If the sub-MACs are d-fuzzy-authenticated according to definition 1, then the DC component is accepted as authentic and the image block corresponding to the DC component is declared authentic. Otherwise, if the sub-MACs are not d-fuzzy-authenticated, the block is marked as suspicious. All the blocks marked as suspicious identify the potential modifications in the image and are tried to be corrected using the iterative error correction algorithm explained in Sect. 2.2 on IEC-MAC. The major difference is that in Sect. 2.2, the whole suspicious column of image blocks is considered. Thus, it is good to identify the error locations to a column level but depending on the image resolution, it might be computationally very expensive to do the error recovery. In IEC-NTMAC, only the suspicious blocks are tried for error recovery, therefore the error recovery is computationally less expensive as compared to IECC-MAC. The pseudo-code of the IEC-NTMAC verification and error localization with error recovery at the receiver is given below and also depicted in Fig. 5.5.

Fig. 5.5

Error localization and correction using IEC-NTMAC at the receiver side

5.5 Performance and Security Analysis of the Proposed Fuzzy Authentication Algorithms

5.5.1 Performance Study

To analyze the algorithms, it is assumed that an ideal n-bit MAC (n ≥ 256) is used for each column of the DC coefficients. The image is divided into m × m nonoverlapping blocks to get a total of m ², k-bit DC coefficients.

At the receiver, the fuzzy authentication is considered to be successful if the Hamming distance between the received and the recalculated MACs does not exceed a threshold value. For such a fuzzy authentication algorithm, there is a possibility of the following two types of errors,

False Rejection

A correct image (or a complete column of blocks or individual blocks) is discarded, though it should have been declared authentic.

False Acceptance

An incorrect image (or a complete column of blocks or individual blocks) is accepted, though it should have been declared unauthentic.

If the BER is too high, false rejection will reduce the efficiency of the proposed schemes. When channel is in good state, i.e., the BER is low, false rejection will happen rarely. The probability of a false rejection for hard verification, i.e., with d = 0, is given by,

$$ 1-{{(1-BER)}^{n}}$$

(5.7)

The false rejection probability for fuzzy authentication is given by,

$$ \begin{aligned}& \Pr (FALSE~REJECTION) \\& ={{(1-BER)}^{mk}}\sum_{i=d+1}^{mn}{(\begin{aligned}& mn \\& ~~i \end{aligned} )BE{{R}^{i}}{{(1-BER)}^{mn-i}}}\end{aligned} $$

(5.8)

which is much smaller than that for hard authentication.

To calculate the probability of a false acceptance, suppose that R is the number of non-authentic column-wise MACs and E is the number of erroneous bits. The probability of a false acceptance in the presence of e erroneous bits in DC coefficient is given by,

$$ \begin{aligned}& \Pr (FALSE~ACCEPTANCE) \\& =\Pr (R=0|E=e) \\& =\sum_{i=1}^{e}{{{p}_{i}}{{q}_{i}}}\end{aligned} $$

(5.9)

where p _i is the probability of a false acceptance in each column when i DC coefficients are erroneous and q _i is the conditional probability of i erroneous DC coefficients when e bits are in error. p _i is approximated by binomial distribution while q _i can be estimated using classical occupancy problem [12–15]:

$$\begin{array}{l} \Pr (FALSE\,\,ACCEPTANCE)\\ = \sum\limits_{i = 0}^e {{{\left( {\frac{{\sum\limits_{k = 0}^d {\left( \begin{array}{l} m\\ k \end{array} \right)} }}{{{2^n}}}} \right)}^i}\left( \begin{array}{l} m\\ i \end{array} \right)\sum\limits_{j = 0}^i {{{( - 1)}^j}\frac{{\left( \begin{array}{l} i\\ j \end{array} \right){{(i - j)}^e}}}{{{m^e}}}} } \end{array}$$

(5.10)

5.5.2 Security Analysis

Algorithms introduced in this chapter are based on the ideal standard MAC, so the generic attacks on the standard MACs are considered as potential threats. In the given approaches, MACs may tolerate a modest number of errors; therefore, the security strength is reduced in general as compared to hard authentication MACs. In IECC-MAC, each DC element is protected by one MAC and the attacker has to forge the DC coefficients in such a way that column MACs can be d-fuzzy-authenticated. In IEC-NTMAC, the attacker even has more difficult task due to random partitioning [15].

A common approach to approximate the required complexity (data/time) for forgery attack on the MACs is given by “birthday paradox” which is based on finding collisions. For the fuzzy authentication, an attacker has to perform a near collision attack [37]. Near collision refers to a message pair, such that their MACs differ a little from each other. By extending the ordinary birthday paradox to the introduced fuzzy authentication scheme with a threshold d, it is expected to have a near collision with at most d-bit differences with the data complexity of,

$$ \sqrt{\frac{{{2}^{n}}}{\sum_{d=0}^{d}{(\begin{aligned}& n \\& \,d \end{aligned} )}}}$$

(5.11)

The value of n is usually chosen to be 256 (bits). The threshold value is set in such a way that the false acceptance and false rejection rates are minimized. There are other experimental methods to find a conveniently safe threshold zone by image processing techniques [10]. It can be observed that with the smaller threshold values, the security strength can be compensated by selecting longer MAC lengths [38]. The security of IEC-NTMAC is even higher due to secret partitioning. The attacker requires knowledge of partitioning methods before launching any attack.

5.6 Simulation Results

5.6.1 Simulation Parameters

Simulation results, for both of the proposed algorithms, are based on image transmission over additive white Gaussian noise (AWGN) channel with binary phase shift keying (BPSK) modulation. Results are given in the presence of as well as in the absence of channel coding (turbo Codes of rate-1/3). The LLRs produced by the decoder for convolutional turbo codes (CTC) are used for bit reliabilities, whereas the channel measurements are used as bit reliabilities in the absence of channel coding.

The source image is chosen as a grayscale image of 128 × 128 pixels, where each pixel requires 1 byte. The image is split into 8 × 8 pixel nonoverlapping blocks resulting in a total of 16 × 16 blocks for the chosen image resolution. DCT for each of these blocks is calculated and the DC components of the DCT matrices are protected using the algorithms explained earlier in Sect. 5.2. The DC and AC elements in the DCT matrix are of 16 bits each (and therefore need 2 bytes).

5.6.2 Data Rate Analysis

SHA-256 is used as the standard MAC in the simulations. For a grayscale 128 × 128 pixels image protected using SHA-256, in total 128 × 128 × 8 bits of image data plus 256 bits of MAC (SHA-256) need to be transmitted. This is equal to 131,328 bits.

By protecting the DC elements using an IECC-MAC, 16 × 256 bits (= 4096 bits) of MACs are computed column-wise. The first 5 minor diagonals of the DCT matrices are transmitted (as compressed image in the simulations), which is 15 × 16 × 16 × 16 = 61,440 bits of data, where 15 is the number of elements from the 5 diagonals of each DCT matrix, 16 × 16 is the number of DCT matrices and the last 16 is the size (in bits) of each element in the DCT matrix. Thus, 61440 + 4096 = 65536 bits are transmitted in total, which is approximately 50 % of the data that was transmitted by protecting the image using a standard MAC. Using IEC-NTMAC based error protection, the number of data bits transmitted is the same as in IECC-MAC. Each EC-NTMAC is 256 bits long. Thus, again approximately 50 % of the whole data is transmitted as compared to the conventional data transmission.

5.6.3 Simulation Results for IECC-MAC

Figure 5.6 shows the simulations results for IECC-MAC in the absence of channel coding at E_b/N₀ of 12.5 dB. Figure 5.6a shows the source image that is to be transmitted after protection with IECC-MAC. Figure 5.6b shows the image received at the receiver side. Figure 5.6c shows how the suspicious block positions are highlighted in red (columns of suspicious blocks) followed by the suspicious blocks mapped into the received image. Finally, the resultant image is shown, which is obtained by performing the error correction of IECC-MAC algorithms over the suspicious image based on the localized errors.

Fig. 5.6

IECC-MAC at 12.5 dB without channel coding.

Figure 5.7 shows the simulation results for IECC-MAC in the presence of channel coding (Turbo codes of rate-1/3) at E_b/N₀ of 2.0 dB. It can be observed that due to the presence of turbo codes, lesser number of erroneous blocks is obtained at a much lower E_b/N₀.

Fig. 5.7

IECC-MAC at 2.0 dB with CTC of rate-1/3

Figure 5.8 shows the results of IECC-MAC after forgery attack. Figure 5.8a shows an airplane image. Figure 5.8b shows a forged image, where the serial number “01568” of the airplane has been removed. IECC-NTMAC is able to localize these modifications, as shown in Fig. 5.8c but is not able to correct them.

Fig. 5.8

a An airplane. b The number removed. c Modifications identified using IECC-MAC

5.6.4 Simulation Results Using IEC-NTMAC

Images protected using IEC-NTMACs have better error localization capabilities and so they can be reconstructed more efficiently as compared to IECC-MAC. Simulation results in the presence and absence of channel coding, similar to the previous subsection, are presented in Fig. 5.9 and 5.10. Figure 5.11 shows the forgery attack on the airplane image. The error localization of IEC-NTMAC is refined to the block level, so it can be seen that the exact area of forgery has been marked by the IEC-NTMAC.

Fig. 5.9

IEC-NTMAC at 12 dB without channel coding

Fig. 5.10

IEC-NTMAC at 2.75 dB with CTC of rate-1/3

Fig. 5.11

a An airplane. b The number removed (forgery). c Modifications identified using IEC-NTMAC

5.6.5 Image Error Rate (IER)

IER is defined as the number of times the whole image is declared as unauthentic divided by the number of times the image was received at the receiver, i.e.,

$$ IER=\frac{\text{Nunmer of times the image is declared unauthentic }}{\text{Number of times the image is received}}$$

(5.12)

IER for both the algorithms is shown in Fig. 5.5 at different values of E_b/N₀. Three different curves are plotted for comparison. These curves show the IER in the presence of a standard MAC based protection, then in the presence of IECC-MAC and finally in the presence of IEC-NTMAC. Figure 5.5 shows that IEC-NTMAC provides the lowest IER and performs the best amongst the proposed algorithms (Fig. 5.12).

Fig. 5.12

IER over the AWGN channel with BPSK modulation and turbo codes of rate-1/3.