Z-OAXN: An Approach to Reducing the Pixel Changes in LSB_Based Image Steganography

Abstract

Image steganography is a way of hiding information in image files. LSB is one of the most commonly-used algorithms in this field which depends on embedding data in the least significant bits of bytes representing visual properties of pixels in the image file. This paper introduces a reversible logic function called the Zolfaghari function and exploits the properties of this function to propose an approach called Z-OAXN to modify the traditional LSB algorithm in order to reduce the average pixel change probability. Analytical modelings as well as experimental results are used to evaluate the approach and both demonstrate that it can reduce the average pixel change probability in contrast to the traditional LSB technique by 64 to 100 percent.

1 Introduction and Basic Concepts

Steganography is a technique in which one type of data is hidden in another. For example, in image steganography, any type of data can be hidden in an image file. One of the most commonly used algorithms for image steganography is the Least Significant Bit (LSB) algorithm. LSB uses the least significant bits of the bytes presenting the pixels of the image in a bitmap file to embed the bits of the data to be hidden. For example, suppose that a short text message like “Hello” is to be hidden in a 24-bit bit map image file. The ASCII code for the character H is 01001000 , this code is 01100101 for e, 01101100 for l and 01101111 for 0. Thus, the message can be shown as 0100100001100101011011000110110001101111 in the form of a bit stream. The bit stream is thus accommodated in the image file as shown by figure 1.

Figure 1: The message “Hello” embedded in a 24-bit bit map file by LSB

Suppose that the traditional LSB algorithm is applied to a 24-bit bitmap file to hide a given stream of bits. If we designate the probability that a pixel is changed after embedding the data with and the inverse probability (the probability that a pixel remains unchanged) with, we can interpretas the probability that neither of the LSBs of the 3 bytes representing a pixel are changed or each of the 3 LSBs is the same as the corresponding bit in the data to be hidden. Thus, can be given by equation 1.

(Equation 1)

Accordingly, can be calculated as follows:

(Equation 2)

In this paper, we refer to the average probability that a pixel is changed as the Average Pixel Change Probability or APCP for short. Our proposed approach to reducing APCP is called Z-OAXN. We use 24-bit bitmap pictures to explain the approach but it is applicable to some other picture formats- especially those which use lossless compression algorithms such as GIF- with minor changes. The main idea behind the Z-OAXN approach is making use of a reversible function called the Zolfaghari function to replace the LSBs of bytes which present pixels of the image. In order to explain the Z-OAXN approach, we need to present some basic concepts and some definitions which follow.

Definition: A gate -or a circuit at all- is reversible if it implements a bijective logic function [56]. A bijective function is one that is surjective and injective. Reversible functions are all conservative functions, that is, they have identical numbers of input and output lines and also identical numbers of 1s in the input and the output. Thus, the output of a bijective function can be considered as a permutation of the input. In other words, a reversible function leaves its inputs unchanged except for the last input whose change depends on the values of the other inputs (and maybe the last input itself). Bijective functions (permutations) can be denoted with different notations one of which is the cycle notation [56]. In this notation, disjoint cycles are used to show the permutation. For example, a function that swaps 000(0) and 001(1) and also swaps 110(6) and 111(7) in the input and the output is denoted by (0, 1) (6, 7).

Definition: An m-CNOT gate is a gate with m+1 inputs (and the same number of outputs) which transfers its first inputs to the output without any changes and complements the last input if all the first inputs are equal to 1; otherwise the last output is left unchanged like the others. An m-CNOT gate can be implemented by AND and XOR function as figure2 shows.

Figure 2: An implementation of a CNOT gate

It can be observed from figure 2 that the last output of an m-CNOT gate whose inputs are , ,… can be demonstrated as .

Definition: An m-input OAXN (OR-AND-XNOR) function is a function whose last output is 1 if all the inputs have identical values and is 0 otherwise. Other outputs are equal to their corresponding inputs. It is obvious that this function gives 1 as its last output in only two cases. The first case is when all the inputs are equal to 1. This is the only case in which the AND function of the m inputs will be equal to 1. The second case is when all the inputs have 0 values. The latter case is the only case in which the OR function of the inputs can be 0 or equally the NOR function is 1. Therefore the last output of an m-input OAXN function can be realized by an m-input AND function, an m-input NOR function and a two-input OR function as figure 3 shows.

Figure 3: The last output of an m-input OAXN function

But for simplicity in demonstrating the OAXN function in terms of well-known reversible gates, we propose another implementation for it. This implementation is showed in figure 4.

Figure 4: The XNOR Implementation of an m-input OAXN function

In figure 4, the output of the XNOR gate is 1 only if the OR gate and the AND gate have identical outputs and this is possible only in two cases. The first case is when the AND and the OR both are 1, which requires all the inputs to be 1. The second case is when both AND and OR produce 0 outputs, which requires all the inputs to be 0. It is obvious that the implementation shown in figure 4 is equivalent to the one demonstrated in figure 3 from the output point of view. The name OAXN (OR-AND-XNOR) has been derived from the idea behind the implementation shown in figure 4.

For consistency with previous works, we can show the OAXN function in terms of NOT and CNOT functions. To do this, we must note that if we show the last output of a CNOT gate by and show the last output of an OAXN function by , we will have:

(Equation 3)

Or:

(Equation 4)

Equation 4 shows that the OAXN function can be implemented by the NOT and CNOT gates as shown in figure 5.

Figure 5: Implementing the OAXN function with NOT and CNOT gates

The NOT gates on the output lines of the second CNOT gate in figure 5 are necessary because the OAXN function should not change its inputs except for the last one.

Definition: An m-Zolfaghari function is a function with m+1 inputs and m+1 outputs which returns the complement of the last input as its last output if all its first m inputs have identical values and returns its last input unchanged in any other case. Such a function does not change its other inputs at all. The last output of an m-Zolfaghari function can be easily implemented by an OAXN between the first m inputs and an XOR function between the last input and the output of the OAXN function. Figure 6 shows such an implementation.

Figure 6: The last output of an m-Zolfaghari function

An m-Zolfaghari function is a permutation that can be designated in the cycle notation as (0, 1) ( ) since swaps the 00…00 pattern with 00…01 and 11…10 with 11…11 in the output.

According to figure 6, an m-Zolfaghari function can be implemented using an OAXN function and a CNOT gate as shown in figure 7. The reasoning is similar to that presented for the case of the OAXN function.

Figure7: Implementing the Zolfaghari function using the OAXN and CNOT

If we replace the OAXN function in figure 7 by the implementation given for it in figure 5, we will observe that the Zolfaghari function can be implemented using NOT and CNOT functions. Such an implementation has been shown in figure 8.

Figure 8: The Zolfaghari function in terms of NOT and CNOT

The Zolfaghari function has two important properties. The first is its reversibility. As figure 8 shows, The Zolfaghari function is reversible (because it can be implemented using the reversible NOT and CNOT functions). This is important because allows this function to be exploited in our proposed steganographic approach. In fact, this reversibility allows the hidden data to be revealed when required. The second important property of the Zolfaghari function is that it changes its last input with a relatively low probability. This property is important in steganography as well, because helps reduced the changes imposed to the cover image and makes it more difficult to discover the fact that some secret data has been hidden in it. The probability that the last input is changed by an m-Zolfaghari function is obviously equivalent to the probability that the output of the OAXN function of the first m inputs is 1. Since the OAXN function is 1 only in 2 cases among the possible cases, this probability can simply be calculated as follows.

(Equation 5)

The rest of this paper is organized as follows. Section 2 is dedicated to discussing the related works, Section 3 introduces the Z-OAXN approach, Section 4 evaluates the proposed approach and Section 5 is dedicated to conclusions and proposing further works.

2 Related Works

There has been a lot of research regarding steganography and steganalysis in recent years. Among relevant topics on which large numbers of research works have been done, we can refer to topics such as developing steganography methods [19,32,33,38], developing techniques for steganography in video, audio, etc [8], applying statistical methods to steganography [5,35], benchmarking and performance evaluation of steganographic techniques [4,15,17,18,41], presenting techniques to choose among steganographic algorithms [27], presenting techniques for choosing proper host and cover files [29], developing steganalysis methods [20,22,23,39,47], applying statistical methods to steganalysis [28], applying artificial intelligence to steganalysis [6,16,24] and developing steganographic techniques that resist against steganalysis [3,7]. But the most relevant works to this paper are those that deal with analyzing, optimizing or introducing new variants of the LSB algorithm or finding new applications for it. In the following, we discuss some of these works.

Chan and Cheng [50] proposed an optimization method which can augment the simple LSB algorithm and enhance the quality of the stego image with minor computational complexity and without any visually sensible changes in the cover image. They analytically modeled the worst case for their proposed method from the point of view mean square error between the cover image and the stego image.

Dabeer, et al [48, 54, 55], proposed an approach to exploit hypothesis theory in steganalysis of images containing data hidden by LSB algorithm. Their approach reduces the problem of composite hypothesis testing to a simple hypothesis testing problem for an image with a known Probability Mass Function (PMF). They used images with known PMFs to obtain tests based on estimation of the host PMF and showed that their tests have superior self calibration and receiver operating characteristics compared with previously known tests.

Goljan [51] presented a modular method for estimating the length of a bit stream embedded in randomly distributed of an image using the LSB algorithm. They also refined their approach to produce more accurate results for different types of natural images. They showed that their proposed approach has the advantage that fits well to statistical image models.

Celik, et al [40], modified the traditional LSB method to obtain a reversible technique for embedding data. Their approach makes it possible to fully recover the host data when recovering the embedded data. The main idea behind their technique is transmitting parts of the host data that are suspectible to embedding distortion along with the hidden data after compression.

Cvejic and Seppänen [45, 52, 53] proposed an LSB audio watermarking approach which decreases the distortion imposed to the host audio. In their proposed approach higher robustness against noise through embedding the watermark bits in higher LSB layers. They showed true listening tests that their approach also improves the perceptual quality of the watermarked audio.

Ker [46, 49, 54, 37] argued that LSB matching is harder to discover than the LSB replacement method and therefore proposed modified variants of this method for embedding data in gray scale and color bitmaps. He argued that the Histogram Characteristic Function introduced by Harmsen [57] is effective for color images but ineffective to use on gray scale images. He used two techniques to make HCF more applicable. The first technique is calibrating the output using a down sampled image and the second is exploiting the adjacency histogram instead of the usual histogram. He demonstrated that his approach outperforms previous the traditional LSB matching technique especially in cases that the cover image is stored in JPEG files.

Ker [42] combined the structural and combinatorial descriptors exploited by previous frameworks to introduce a general framework for steganalysis of simple LSB replacement in image files which can result in more powerful detection algorithms. He also introduced and studied a novel descriptor and showed through experiments that their suggested descriptor can perform that previously known ones.