It is currently possible to embed a secret message either sequentially (begin at the first image byte and sequentially alter the LSBs) or randomly (scatter the changes throughout the image).
In this article we discuss a new steganography technique, RECT (short for rectangle), which aims to reduce the effectiveness of Regular and Singular Groups (RS) by embedding the message in a rectangle in the centre of the image.
According to Fridrich et al [1]:
”The RS Steganalysis is more accurate for messages that are
randomly scattered in the stego-image than for messages
concentrated in a localized area of the image.”
We will take advantage of this weakness by creating a technique which sequentially embeds a message in the center of the image. This attacks both of RS’s weaknesses: we are embedding sequentially rather than randomly, and we are storing the message in a localised area of the image.
The downside to this is it is likely our message will need to be small, otherwise the rectangle will no longer be ”concentrated” or ”localized”.
To ensure our message is hidden in a rectangular shape, we start from the centre pixel and embed in a clockwise spiral. For example, in the 5 x 5 greyscale image below, X represents each byte, and A to I represent the sequence of bytes altered by RECT:
X X X X X
X G H I X
X F A B X
X E D C X
X X X X X
We start at A, move right one byte to B, move down one byte to C, move left one byte to D, and so on. This allows us to embed any message in a rectangular shape, regardless of its size.
To thoroughly understand the performance of RECT, we have prepared the following test setup:
* Two sets of images: ten natural images and ten artificial images. Each image is 192 x 192 pixels and in RGB format.
* We create five messages for each image: a message which alters 1% of the image’s bytes; a message which alters 10% of the image’s bytes; a message which alters 25% of the image’s bytes; a message which alters 50% of the image’s bytes; and a message which alters 100% of the image’s bytes. As each image has a different number of bytes (different file size), we calculate the message lengths individually for each image. The messages are then dynamically generated by encrypting a series of ”A”s with AES.
* We have created an encoder and decoder which can handle the various steganography algorithms and spreads.
* We have written a script which tests RECT against Sample Pairs Analysis (SPA), RS, Weighted Stego-Image (WS), Triples Analysis (TA), and deep learning steganalysis using Aletheia.
The above requires 4,500 individual tests. The results are displayed in eight tables: LSBR False Negative Rates (Natural Images), LSBR False Negative Rates (Artificial Images), LSBM False Negative Rates (Natural Images), LSBM False Negative Rates (Artificial Images), Matrix Embedding False Negative Rates (Natural Images), and Matrix Embedding False Negative Rates (Artificial Images). Instead of showing the individual results for each image, we have aggregated the results into a single score.
We have taken an attackers perspective, so the result in each cell is the percentage of tests which caused a false negative. By false negative we mean the steganalysis technique failed to detect a hidden message, and classified the stego-image as a cover image.
To make it easier to see the results at a glance, we have colour coded the cells as follows: green means 80%+ false negative rate, red means 80%+ detection rate, and colourless refers to everything else. As an attacker, we are most interested in rows which are entirely green (ideally with scores of 100%), as it means our stego-images have a high chance of being undetected.
| LSBR False Negative Rates (Natural Images) | |||||
| SPA | RS | WS | TA | ML (LSBR Model) | |
| Sequential, 1% | 100% | 100% | 100% | 100% | 80% |
| Sequential, 10% | 70% | 50% | 10% | 80% | 70% |
| Sequential, 25% | 0% | 0% | 0% | 0% | 60% |
| Sequential, 50% | 0% | 0% | 0% | 0% | 40% |
| Sequential, 100% | 0% | 10% | 0% | 0% | 0% |
| Random, 1% | 100% | 100% | 100% | 100% | 30% |
| Random, 10% | 0% | 40% | 0% | 10% | 0% |
| Random, 25% | 0% | 0% | 0% | 0% | 0% |
| Random, 50% | 0% | 0% | 0% | 0% | 0% |
| Random, 100% | 0% | 10% | 0% | 0% | 0% |
| RECT, 1% | 100% | 100% | 100% | 100% | 80% |
| RECT, 10% | 100% | 90% | 60% | 100% | 80% |
| RECT, 25% | 0% | 0% | 0% | 30% | 70% |
| RECT, 50% | 0% | 0% | 0% | 0% | 60% |
| RECT, 100% | 0% | 30% | 0% | 0% | 0% |
| LSBR False Negative Rates (Artificial Images) | |||||
| SPA | RS | WS | TA | ML (LSBR Model) | |
| Sequential, 1% | 100% | 100% | 90% | 100% | 100% |
| Sequential, 10% | 60% | 70% | 30% | 100% | 100% |
| Sequential, 25% | 0% | 0% | 0% | 30% | 90% |
| Sequential, 50% | 0% | 0% | 0% | 10% | 90% |
| Sequential, 100% | 0% | 0% | 0% | 0% | 0% |
| Random, 1% | 100% | 100% | 90% | 100% | 50% |
| Random, 10% | 10% | 40% | 0% | 10% | 0% |
| Random, 25% | 0% | 0% | 0% | 0% | 0% |
| Random, 50% | 0% | 0% | 0% | 0% | 0% |
| Random, 100% | 0% | 0% | 0% | 0% | 0% |
| RECT, 1% | 100% | 100% | 90% | 100% | 100% |
| RECT, 10% | 90% | 90% | 60% | 100% | 100% |
| RECT, 25% | 10% | 10% | 0% | 70% | 80% |
| RECT, 50% | 0% | 0% | 0% | 0% | 70% |
| RECT, 100% | 0% | 70% | 0% | 0% | 0% |
| LSBM False Negative Rates (Natural Images) | |||||
| SPA | RS | WS | TA | ML (LSBM Model) | |
| Sequential, 1% | 100% | 100% | 100% | 100% | 90% |
| Sequential, 10% | 90% | 100% | 90% | 100% | 70% |
| Sequential, 25% | 90% | 90% | 90% | 90% | 50% |
| Sequential, 50% | 90% | 90% | 90% | 90% | 40% |
| Sequential, 100% | 90% | 90% | 90% | 90% | 0% |
| Random, 1% | 100% | 100% | 100% | 100% | 20% |
| Random, 10% | 100% | 100% | 90% | 100% | 0% |
| Random, 25% | 90% | 100% | 90% | 90% | 0% |
| Random, 50% | 90% | 90% | 90% | 90% | 0% |
| Random, 100% | 90% | 80% | 90% | 90% | 0% |
| RECT, 1% | 100% | 100% | 100% | 100% | 90% |
| RECT, 10% | 100% | 100% | 100% | 100% | 90% |
| RECT, 25% | 100% | 100% | 100% | 100% | 90% |
| RECT, 50% | 90% | 100% | 90% | 100% | 80% |
| RECT, 100% | 90% | 90% | 90% | 90% | 0% |
| LSBM False Negative Rates (Artificial Images) | |||||
| SPA | RS | WS | TA | ML (LSBM Model) | |
| Sequential, 1% | 100% | 100% | 90% | 100% | 100% |
| Sequential, 10% | 80% | 80% | 50% | 100% | 100% |
| Sequential, 25% | 50% | 60% | 50% | 70% | 100% |
| Sequential, 50% | 50% | 50% | 50% | 50% | 100% |
| Sequential, 100% | 20% | 10% | 20% | 30% | 0% |
| Random, 1% | 100% | 100% | 90% | 100% | 100% |
| Random, 10% | 80% | 90% | 60% | 80% | 10% |
| Random, 25% | 40% | 80% | 30% | 10% | 0% |
| Random, 50% | 30% | 30% | 30% | 20% | 0% |
| Random, 100% | 20% | 0% | 20% | 30% | 0% |
| RECT, 1% | 100% | 100% | 90% | 100% | 100% |
| RECT, 10% | 100% | 100% | 90% | 100% | 100% |
| RECT, 25% | 100% | 80% | 60% | 90% | 100% |
| RECT, 50% | 60% | 50% | 40% | 70% | 90% |
| RECT, 100% | 20% | 10% | 20% | 30% | 0% |
| Matrix Embedding False Negative Rates (Natural Images) | |||||
| SPA | RS | WS | TA | ML (LSBM Model) | |
| Sequential, 1% | 100% | 100% | 100% | 100% | 90% |
| Sequential, 10% | 90% | 100% | 90% | 100% | 80% |
| Sequential, 25% | 90% | 90% | 90% | 90% | 70% |
| Sequential, 50% | 90% | 90% | 90% | 90% | 40% |
| Sequential, 100% | 90% | 90% | 90% | 90% | 0% |
| Random, 1% | 100% | 100% | 100% | 100% | 70% |
| Random, 10% | 100% | 100% | 100% | 100% | 10% |
| Random, 25% | 90% | 100% | 90% | 100% | 0% |
| Random, 50% | 90% | 100% | 90% | 90% | 0% |
| Random, 100% | 90% | 90% | 90% | 90% | 0% |
| RECT, 1% | 100% | 100% | 100% | 100% | 90% |
| RECT, 10% | 100% | 100% | 100% | 100% | 90% |
| RECT, 25% | 100% | 100% | 100% | 100% | 80% |
| RECT, 50% | 90% | 100% | 90% | 100% | 50% |
| RECT, 100% | 90% | 90% | 90% | 90% | 0% |
| Matrix Embedding False Negative Rates (Artificial Images) | |||||
| SPA | RS | WS | TA | ML (LSBM Model) | |
| Sequential, 1% | 100% | 100% | 90% | 100% | 100% |
| Sequential, 10% | 90% | 90% | 70% | 100% | 100% |
| Sequential, 25% | 70% | 90% | 50% | 70% | 100% |
| Sequential, 50% | 50% | 60% | 40% | 50% | 100% |
| Sequential, 100% | 30% | 30% | 30% | 10% | 0% |
| Random, 1% | 100% | 100% | 90% | 100% | 100% |
| Random, 10% | 90% | 90% | 80% | 100% | 10% |
| Random, 25% | 70% | 90% | 50% | 70% | 0% |
| Random, 50% | 40% | 90% | 30% | 10% | 0% |
| Random, 100% | 20% | 30% | 20% | 20% | 0% |
| RECT, 1% | 100% | 100% | 90% | 100% | 100% |
| RECT, 10% | 100% | 100% | 90% | 100% | 100% |
| RECT, 25% | 100% | 90% | 80% | 100% | 100% |
| RECT, 50% | 60% | 70% | 60% | 60% | 90% |
| RECT, 100% | 20% | 30% | 30% | 20% | 0% |
As we can see, RECT is superior to sequential embedding and random embedding for resisting steganalysis.
| Average False Negative Rate Per Embedding Spread | |
| Average | |
| RECT (Natural Images) | 74% |
| RECT (Artificial Images) | 70% |
| Sequential (Natural Images) | 70% |
| Sequential (Artificial Images) | 63% |
| Random (Natural Images) | 62% |
| Random (Artificial Images) | 45% |
Focusing on RS, and using 25% embedding as a baseline, since RECT works best with small messages, we can see RECT performs 6% better than sequential embedding and 5% better than random embedding when used with natural images, and 8% better than sequential embedding and 11% better than random embedding when used with artificial images.
| Average False Negative Rate Per Embedding Spread (RS, Max. 25%) | |
| Average | |
| RECT (Natural Images) | 91% |
| RECT (Artificial Images) | 89% |
| Random (Natural Images) | 87% |
| Sequential (Natural Images) | 86% |
| Sequential (Artificial Images) | 82% |
| Random (Artificial Images) | 80% |
In conclusion, RECT is a superior embedding technique for resisting steganalysis, especially RS, and should be considered in place of sequential embedding and random embedding when working with small messages.
[1] J. Fridrich, M. Goljan, and R. Du, “Reliable detection of lsb steganography in color and grayscale images,” in Proceedings of the 2001 Workshop on Multimedia and Security: New Challenges, 2001, p. 27–30.