__                                             __ 
  ___ / /____ _  _____ ______ _____ ____    ___  ___ / /_
 (_-</ __/ -_) |/ / -_) __/ // / _ `/ _ \_ / _ \/ -_) __/
/___/\__/\__/|___/\__/_/  \_, /\_,_/_//_(_)_//_/\__/\__/ 
                         /___/              
      

LSB Replacement Explained

November 9, 2021

LSB Replacement (LSBR) is when we change the LSBs in an image (or other suitable media) to match the bits in a secret message.

This is best explained with an example. Let us assume our message is the character ”Z” and our cover image is a 3 x 3 pixel RGB image as follows:

 1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27

As this is an RGB image, each pixel has three bytes (one byte representing the colour Red, one byte representing the colour Green, and one byte representing the colour Blue), hence the image being a matrix of 3 x 9 bytes.

The ASCII code for ”Z” is decimal 90, which is the following in binary:

01011010

For this example we will use sequential embedding (rather than random embedding, or some other embedding technique) as it will keep things simple.

The first byte in the cover image is the number 1:

00000001

We simply replace the LSB with the first bit of our message (0) which changes the byte as follows:

00000000

The second byte in the cover image is the number 2:

00000010

We replace the LSB with the second bit of our message (1) which changes the byte as follows:

00000011

The third byte in the cover image is the number 3:

00000011

We replace the LSB with the third bit of our message (0) which changes the byte as follows:

00000010

Therefore when all eight bits of our secret message have been embedded in the cover image, we are left with the following stego-image:

 0  3  2  5  5  6  7  8  9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27

If we look at the first eight bytes of the image it seems like we only changed half of the bytes (only the first four bytes have new values). This is expected, as roughly half the LSBs in an image will already be set to the desired message bits. This is similar to flipping a coin eight times - we can already guess roughly half the flips will land on tails.

There are two things to note here:

(1) If the message bit and the LSB of the image byte are the same, the byte does not change.

(2) If the message bit and the LSB of the image byte are not the same, this causes even bytes to become odd (increase by one), and odd bytes to become even (decrease by one). For example, if our byte is the number eight (LSB = 0) and our message bit is one, the byte will increase by one to become nine. Similarly, if our byte is the number nine (LSB = 1) and our message bit is zero, the byte will decrease by one to become eight.

Item (2) above is a problem and makes LSBR an insecure embedding technique. The LSBs in natural images are not random, so replacing the LSBs according to our message bits introduces statistical anomalies which can be easily detected using statistical analysis. To (mostly) get around this issue, you should use LSB Matching (LSBM) or Matrix Embedding instead of LSBR.

Decoding a message in an LSBR-encoded stego-image is straightforward. If the message was embedded sequentially, the LSBs of each byte are read and combined to form the secret message. If the message was embedded randomly, a password will have been shared with the recipient which he will use in combination with a PRNG to know which LSBs to read. It should be noted the length of the message is typically prepended so the decoding software understands how many bytes it needs to parse. For example, if the secret message is ”password”, the actual message embedded into the image will be ”8password”.