Linked Pixel Steganography

Linked Pixel Steganography (LPS) technique is a variant of the well-known LSB steganography. It can be applied to any type of images.

How it works

LPS doesn’t hide data sequentially in the image. It is inspired by linked list in algorithmic. Just like linked lists, every “block” contains data parts and a pointer to the next pixel holding the rest of the data. Each pixel of an image is composed of at least three channels (R, G, B). LPS uses the LSB of each channel for different usage.

Since LPS uses LSB, several pixels are needed to store the binary representation of the coordinate of the next pixel. That’s why LPS uses blocks of consecutive pixels.

The block size is calculated from the image size in pixel, it’s the number of bits needed to store the highest value (height or width). Data is then split into chunks of the same size and padding is added at the end if needed. Block positions are randomly selected and checked to make sure no previous data is overwritten.

To recover data correctly, one needs to know the coordinates of the starting pixel and calculate the block size. From then, every next pixel can be recovered by reading blocks, until the coordinates of the next pixel are (0, 0). Like in linked lists, the last element has a NULL pointer, which in this case is represented with coordinate values of 0.

Test 1 – LPS on regular PNG image with Alpha channel

Message hidden

Microsoft se plie à l’écriture inclusive à sa façon. La dernière mise à jour de son logiciel de traitement de texte Word, réservée aux abonnés Office, comprend dans ses paramètres de grammaire et de style une option de «langage inclusif». Une telle fonctionnalité «cible le langage genré à même d’exclure, de rejeter ou de stéréotyper», est-il indiqué sur le site de l’entreprise. Pour rappel, l’écriture inclusive consiste à inclure le féminin, entrecoupé de points, dans les noms, comme dans «mes ami·e·s» ou «les candidat·e·s à la présidentielle, pour le rendre «visible» et prôner des règles grammaticales plus neutres. L’expression est le fruit d’une réflexion amorcée il y a une vingtaine d’années, autour de l’idée de neutralité dans l’écriture. Longtemps cantonnée aux mouvements féministes, cette graphie s’impose désormais dans le débat public. Le logiciel Word, lui, ne propose pas l’utilisation du point milieu. Il remplacera, par exemple, le terme «les experts» par «les experts et les expertes»

Original Image on the left and image hiding data on the right:

 

Like with LSB steganography, there is no visual difference.

LSB analysis

 

We can clearly see stripes in homogenous areas, revealing the presence of hidden data. But in the center of the image it is very difficult to tell if something is hiding in the LSB. Unlike the classical LSB steganography technique, the randomness of the location where data is hidden makes steganalysis more difficult if the image is chosen correctly.

Test 2 – LPS on noisy PNG image

Message hidden

The message is the same as in test 1.

Original Image on the left and image hiding data on the right:

 

No visual difference like in the previous test.

LSB analysis

 

Just like we saw in figure 4, if the image is noisy, the LSB analysis won’t show clear visual difference. But with a good eye and by zooming, one can distinguish stripes due to LPS:

The stripes are more visible in less noisy areas.

Test 3 – Image hiding in noisy PNG image

Let’s see if steganalysis becomes simpler when there is more data hidden. For this test, the same PNG image as in test 2 was used to hide this smaller PNG image:

Original Image on the left and image hiding data on the right:

 

LSB analysis

 

although there is a lot more hidden data then in test 2, LSB analysis doesn’t show a clear visual difference. One would have to zoom in once again to see the stripes. To have a feeling of how much data is hiding inside this image, here is the LSB analysis of the same test realized on a pure black image:

 

A little more than 16% of the pixels are hiding data. It’s still not very impressive but by doing this test the limitations of LPS started to become a handicap.

Limitations

Block positions are chosen randomly. As more data is written in the image there is more chance of a collision happening. At the moment, the only way I found to cope with collisions is to keep track of previously used pixels in a list. If the newly chosen pixel isn’t valid, an other one is chosen. This step is repeated until a valid pixel is found. The result is a large increase of the execution time as data grows.

Randomly choosing a location doesn’t optimise space management. It may lead to gaps between blocks that are too small to fit a new block and thus wasting a lot of storage capacity over all the image.

Because LPS uses only 1 channel to store the actual data, it takes at least three times more storage space than classical LSB.

LPS as it is implemented right now is good for hiding data that, once hidden, doesn’t exceed 25 % of the original image. Otherwise, the execution time becomes unreasonably long.

Official GitHub page of the project