Broadband Method (Class Library)

Foreword

(from the article COMPUTER STEGANOGRAPHY OF YESTERDAY, TODAY, TOMORROW. Information security technologies of the 21st century. / V. Barsukov, Ph.D., Romantsov A.P. / 1998 /)
The task of reliable information protection from unauthorized access is one of the oldest and still unsolved problems. The methods and methods of concealing secret messages have been known for a long time, and this area of ​​human activity has been called steganography. This word comes from the Greek words steganos (secret, secret) and graphy (record) and thus literally means “secret writing”, although steganography methods appeared probably before the writing itself appeared (the symbols and symbols were originally used).
Later, to protect the information, coding and cryptography methods that were more efficient at the time of creation were used.
As you know, the purpose of cryptography is to block unauthorized access to information by encrypting the content of secret messages. Steganography has another task, and its purpose is to hide the very fact of the existence of a secret message. At the same time, both methods can be combined and used to increase the effectiveness of information security (for example, for transmitting cryptographic keys).
Like any tools, steganographic methods require attention and careful handling, as they can be used both for defense purposes and for attack purposes.

Algorithm

In accordance with the broadband signal method, each data bit is encoded by a sequence of altered pixel intensities in accordance with the values ​​of the pseudo-random bit bits.
The broadband signal method implies the possibility of generating the same pseudo-random sequence from the sending and receiving sides, or at least pseudo-random sequences with statistical characteristics equivalent to equal.
At the same time, not only the image itself, but also a reversible transformation of this image, for example, the spectrum obtained as a result of Fourier transforms, can act as a container for placing data. The presence of a large number of libraries that implement Fourier transforms (in all sorts of variants of fast versions) makes the implementation of algorithms not a very difficult task for programming.

Formula for placing data in a graphic file

The formula for changing the brightness of pixels depending on the value of the i-th bit of the data x [i] and the j-th bit of the pseudo-random sequence y [j]:
Cw [i, j] = C [i, j] + A * (- 1) ^ (x [i] xor y [j])
Where
C [i, j] is the brightness value of a pixel of a graphic image associated with the i-th bit of data x [i] and the j-th bit of the pseudo-random sequence y [j]
A - brightness change value (method parameter - immersion depth)

Formula for extracting data from a graphic file

When extracting data from the pixel brightness array, a weighted voting scheme is applied with coefficients equal to the difference between the average brightness value and the brightness of the voting pixel.
V [i] = SUM (Cw [i, j] -Mw [i, j]) (- 1) ^ y [j]
if V [i] <0 then x [i] == 0 else x [i] == 1
Where
Cw [i, j] is the pixel brightness value of the decoded graphic image associated with the i-th bit of data x [i] and the j-th bit of the pseudo-random sequence y [j]
Mw [i, j] - the value of the average brightness of pixels around a pixel of a decoded graphic image associated with the i-th bit of the data x [i] and the j-th bit of the pseudo-random sequence y [j]
')

Compensation of changes in the average brightness of the image when applying the method of wideband signal

The use of a pseudo-random sequence with characteristics close to equiprobable for encoding data allows to preserve the average brightness of pixels in the original graphic image and in the image containing embedded data.
However, with direct and literal application of the algorithm, the average brightness of the pixels could have been offset relative to the average brightness of the original image.
To estimate the magnitude of the bias, a statistical calculation is made of the number of zeros and ones of the function (x [i] xor y [j])
And if p0 is the probability of zeros, and p1 is the probability of ones, then an estimate of the magnitude of the change in average brightness is calculated by the formula:
dC = A * (p0-p1)
This dC estimate will be used in the formula of the algorithm itself for the method of wideband signals to compensate for the displacement of the average brightness of the image.
Cw [i, j] = C [i, j] + A * (- 1) ^ (x [i] xor y [j]) - dC

Using Noise Suppression

Since the change in brightness up or down is equally probable (or at least it is assumed by the method), then the average brightness of the original image should almost coincide with the average brightness of the image generated by the method. The same rule, apparently, should be executed for small sections of the image.
Thus, it can be assumed that the images obtained as a result of eliminating noise from the original image and as a result of eliminating noise from the generated image should practically coincide, and therefore the image obtained by using the noise elimination filter can be selected as known to the sender and receiver of information.
Thus, the formula for placing data in a graphic file can be replaced by the formula
Cw [i, j] = M [i, j] + A * (- 1) ^ (x [i] xor y [j])
Where
M [i, j] - the value of the average brightness of pixels around a pixel of the encoded graphic image associated with the i-th bit of the data x [i] and the j-th bit of the pseudo-random sequence y [j]

Automatic calculation of the depth of immersion.

When used to place data in a graphic file of the formula
Cw [i, j] = C [i, j] + A * (- 1) ^ (x [i] xor y [j]) - dC
and to extract the data from the graphic file of the formula
V [i] = SUM (Cw [i, j] -Mw [i, j]) (- 1) ^ y [j]
if V [i] <0 then x [i] == 0 else x [i] == 1
it is possible to give an estimate for choosing the optimal value of the algorithm parameter — the immersion value A based on statistical estimates.
So adding or subtracting the value of A from the brightness values ​​of the pixels will increase the square of the variance of the final image by the value of A ^ 2.
At the same time, we assume it equally probable to add and subtract the value of A from the brightness of a pixel.
So, when using a locally averaged value M in the recovery formula, you can set the value of A using the following formula
A = SQRT (AVG (C [i, j] -M [i, j]) ^ 2)

The role of coefficients in the voting scheme

When using the voting scheme in the original methodology, the vote coefficients equal to the difference between the average brightness value and the voting pixel brightness are the vote coefficients from the statistical criterion for separating two simple statistical hypotheses known as the “Most Powerful” to separate two simple hypotheses about the normal distribution or with parameters (A, A), or with parameters (-A, A).
Since, when receiving and extracting data from a graphic file, the value of A is not known reliably, its average value can be selected as SQRT (AVG (Cw [i, j] -Mw [i, j]) ^ 2), which in turn, coincides with the dispersion of the same distribution.

Evidence

The coefficients of the votes, using the statistical criterion "Most powerful", can be calculated using the formula -log (P1 (x) / P0 (x)), where P0 and P1 are the probability values ​​of the statistics being studied, and x is the difference between the average the brightness value and the brightness of the voting pixel.
Pn (x) = exp (- (xA) ^ 2 / A ^ 2) / (SQRT (2 * pi) * A)
-log (Pn (x)) = -log (exp (- (xA) ^ 2 / A ^ 2) / (SQRT (2 * pi) * A)) = (xA) ^ 2 / A ^ 2 + log ( SQRT (2 * pi) * A),
which means
-log (Pn (x) / Pn (-x)) = (xA) ^ 2 / A ^ 2 + log (SQRT (2 * pi) * A) - (- xA) ^ 2 / A ^ 2-log ( SQRT (2 * pi) * A) = ((xA) ^ 2- (x + A) ^ 2) / A ^ 2 = 4 * x / A ^ 2 = O (x)
Thus, using a voting scheme with vote coefficients equal to the difference between the average brightness value and the brightness of the voting pixel is a statistical criterion for the separation of two simple statistical hypotheses known as the “Most Powerful” to separate two simple hypotheses about normal distribution with parameters (A, A) and parameters (-A, A).

Improving the voting scheme

We will continue to use the statistical criterion for separating two simple statistical hypotheses known as the “Most Powerful”, however, to calculate the probabilities, we use not the predetermined hypothesis about the normal distribution of the difference between the average brightness value and the brightness of the voting pixel, but the actual selective statistical information from the available data.
Let be
Pw (x) is the sample distribution of actually calculated values ​​Cw [i, j] -Mw [i, j], where Cw [i, j] is the pixel brightness value of the decoded graphic image and Mw [i, j] is the average brightness value of pixels around the pixel of the graphic being decoded mapped to the i-th bit of the decoded data x [i] and the j-th bit of the pseudo-random sequence y [j].
dCw = A * (p0-p1) = E Pw = SUM i * Pw (i) = AVG (Cw [i, j] -Mw [i, j]) is the sample mean value of the brightness shift in the blurred image
Aw = SQRT (E Pw ^ 2 - (E Pw) ^ 2) = SQRT (SUM i ^ 2 * Pw (i) - (SUM i * Pw (i)) ^ 2) - the sample dispersion value of the brightness shift of the blurred image

Method 1

We use the correction factor dCw when counting votes
V [i] = SUM (Cw [i, j] -Mw [i, j] -dCw) (- 1) ^ y [j]

Method 2

We will use the “Most Powerful” statistical criterion to separate two hypotheses with average values ​​above and below dCw and distribution functions P1 and P2, such that P1 (dCw + x) = P0 (dCw-x) and P1xP0 = Pw — where P1xP0 (t) = SUM P1 (i) * P0 (j) | i + j = t is the operation of convolution of two functions.

Putting P1 (dCw + x) = P0 (dCw-x) = f (x), we recover the unknown distribution f (x) from its own convolution function fxf,
We assume that for a known computed sampling distribution Pw (x), the equality fxf (x) = Pw (dCw + x) holds
After the function f (x) is calculated, we will use the voting factors calculated by the formula -log (f (x-dCw) / f (x + dCw)) for voting

Formulas implemented in the library

Formula for placing data in a graphic file

The formula for changing the brightness of pixels depending on the value of the i-th bit of the data x [i] and the j-th bit of the pseudo-random sequence y [j]:
Cw [i, j] = C [i, j] + A * (- 1) ^ (x [i] xor y [j])
Where
C [i, j] is the brightness value of a pixel of a graphic image associated with the i-th bit of data x [i] and the j-th bit of the pseudo-random sequence y [j]
A = SQRT (AVG (C [i, j] -M [i, j]) ^ 2)

Formula for extracting data from a graphic file

When extracting data from the pixel brightness array, a weighted voting scheme is applied with coefficients equal to the difference between the average brightness value and the brightness of the voting pixel.
V [i] = SUM (log (Pn (Cw [i, j] -Mw [i, j]) / Pn (Mw [i, j] -Cw [i, j])) (- 1) ^ y [ j]
if V [i] <0 then x [i] == 0 else x [i] == 1
Where
Pn is the probability value of the statistics with a normal distribution, the average value and the variance value equal to A = SQRT (AVG (Cw [i, j] -Mw [i, j]) ^ 2)
Cw [i, j] is the pixel brightness value of the decoded graphic image associated with the i-th bit of data x [i] and the j-th bit of the pseudo-random sequence y [j]
Mw [i, j] - the value of the average brightness of pixels around a pixel of a decoded graphic image associated with the i-th bit of the data x [i] and the j-th bit of the pseudo-random sequence y [j]

Image size required

If a
- L8 - the number of bits of data transmitted
- N - the number of variable pixels for each transmitted bit
then the required number of pixels in a graphic image must be at least L8 * N, that is, the inequality L8 * N> = W * H * K must be satisfied, where W and H are the width and height of the graphic image, K is the number of color channels of the graphic image .

Implementation of the broadband signal method

- For generating a pseudo-random sequence and for generating indexes of positions, algorithms using user-defined data, called a steganographic key, are used to embed data bits in an image.
“Although cryptographic algorithms are used for generating pseudo-random sequences and for generating indices, as algorithms with the most studied statistical properties, the broadband signal method is NOT ENCRYPTION, but is one of the methods of covert transmission of information, that is, the STEGANOGRAPHIC method.
- The mean pixel brightness values ​​are obtained by applying a graphic blur filter to the incoming graphic image.

Additional options in the current library implementation

In addition to the broadband signal method itself, in the current implementation of the library, there are embedded algorithms with which
- the original sample graphic image can be automatically scaled to a size sufficient to transfer all the necessary data
- the required depth of immersion can be calculated automatically
- the source data are texts of RTF format and can be compressed by data compression algorithm,
- error correction codes can be added to the transmitted data,
- sequences of bits can be placed in the image not sequentially, but in accordance with the selected bit allocation algorithm in the graphic file.
- The parameters of the program algorithms can be embedded in the transmitted image as a barcode. To generate a pseudo-random sequence and to generate indices for embedding data bits in an image, algorithms are used using a string entered by the user and called a steganographic key. When transferring data, the steganographic key is transmitted along with the barcode.

Used software

- Microsoft Visual Studio 2013 C # - environment and programming language
- EmguCV / OpenCV - C # / C ++ library of structures and algorithms for image processing
- FFTWSharp / FFTW - C # / C ++ library that implements fast discrete Fourier transform algorithms
- ZXing.Net - .Net library for processing bar codes
- FFTTools - C # library that implements FFT algorithms for digital image processing github.com/dprotopopov/FFTTools

Screenshots of programs

Literature

- Vyacheslav Sergeevich Barsukov, Candidate of Technical Sciences. Romantsov Andrey Petrovich. COMPUTER STEGANOGRAPHY OF YESTERDAY, TODAY, TOMORROW. Information security technologies of the 21st century. Publication. 1998. www.ess.ru/sites/default/files/files/articles/1998/0405/1998_0405_03.pdf
- Dmitry Protopopov. Fourier processing of digital images. Internet publishing. habrahabr.ru/post/265781

Project Internet address: github.com/dprotopopov/mssove2