Least Significant Bit Encoding

Definition

What is LSB ?

Least Significat Bit LSB, the least significant bit is the lowest bit in a series of numbers in binary; which is located at the far right of a string. For example, in the binary number: 10111001, the least significant bit is the far right 1.

As binary numbers are largely used in computing and other related areas, wherein the least significant bit holds importance, especially when it comes to transmission of binary numbers.

Digital data is computed in binary format, where the rightmost digit is considered the lowest digit whereas the leftmost is considered the highest digit. In positional notation, the least significant bit is also known as the rightmost bit. It is the opposite of the most significant bit, which carries the highest value in a multiple-bit binary number as well as the number which is farthest to the right. In a multi-bit binary number, the significance of a bit decreases as it approaches the least significant bit. Since it is binary, the most significant bit can be either 1 or 0. The least significant bit is frequently employed in hash functions, checksums and pseudorandom number generators.

img

When a transmission of binary data is being done, the least significant bit is the one which is transmitted first, followed by other bits of increasing significance.

The number of image pixels in a PNG file is generally composed of RGB three primary colours (red, green, and blue). Each colour occupies 8 bits, and the value ranges from 0x00 to 0xFF, that is, there are 256 colours, which contain a total of 256 to the third power. Thus there are 16777216 colours in total.

The human eye can distinguish about 10 million different colours, which means that the human eye can't distinguish the remaining 6 million colours. LSB steganography is to modify the lowest binary bit (LSB) of RGB colour components, each colour will have 8 bits, LSB steganography is to modify the lowest bit in the number of pixels, and human eyes will not notice before and after this change, each pixel can carry 3 bits of information.

Example

PicoCTF_2017: Little School Bus

Description:

Can you help me find the data in this Little-School-Bus?

Hint:

Look at least significant bit encoding!!

Solution

As the Hint suggests the problem is related to LSB Encoding, The leftmost digit in binary is called the LSB digit

As mentioned earlier LSB encoding is done by changing the LSB bit of the colour, however, this slight variation is not noticeable. Thus by changing the LSB bit, we can hide data inside a file.

1
xxd -b ./littleschoolbus.bmp | head -n 20
Gives,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
00000000: 01000010 01001101 11100010 01001011 00000010 00000000  BM.K..
00000006: 00000000 00000000 00000000 00000000 00110110 00000000  ....6.
0000000c: 00000000 00000000 00101000 00000000 00000000 00000000  ..(...
00000012: 11111100 00000000 00000000 00000000 11000111 00000000  ......
00000018: 00000000 00000000 00000001 00000000 00011000 00000000  ......
0000001e: 00000000 00000000 00000000 00000000 10101100 01001011  .....K
00000024: 00000010 00000000 00000000 00000000 00000000 00000000  ......
0000002a: 00000000 00000000 00000000 00000000 00000000 00000000  ......
00000030: 00000000 00000000 00000000 00000000 00000000 00000000  ......
00000036: 11111110 11111111 11111111 11111110 11111110 11111111  ......
0000003c: 11111111 11111110 11111110 11111111 11111111 11111110  ......
00000042: 11111111 11111111 11111110 11111110 11111110 11111111  ......
00000048: 11111111 11111110 11111110 11111110 11111110 11111111  ......
0000004e: 11111110 11111111 11111111 11111110 11111110 11111111  ......
00000054: 11111111 11111111 11111110 11111111 11111111 11111111  ......
0000005a: 11111111 11111110 11111111 11111111 11111110 11111111  ......
00000060: 11111111 11111111 11111110 11111110 11111111 11111110  ......
00000066: 11111110 11111111 11111111 11111110 11111110 11111111  ......
0000006c: 11111110 11111111 11111110 11111111 11111111 11111110  ......
00000072: 11111111 11111111 11111110 11111111 11111110 11111111  ......
Taking the LSB bit after the many zero,

1
2
3
4
00000036: 11111110 11111111 11111111 11111110 11111110 11111111  ......
0000003c: 11111111 11111110 11111110 11111111 11111111 11111110  ......
00000042: 11111111 11111111 11111110 11111110 11111110 11111111  ......
00000048: 11111111 11111110 11111110 11111110 11111110 11111111  ......
8 bit gives
1
01100110 01101100
Which in ascii is fl?

Now we script ,

1
2
3
4
5
6
7
8
binary_data = open("littleschoolbus.bmp","rb") # Open the file binary mode
binary_data.seek(54)  #seek to 54 bytes these bytes does not contain any data
data = binary_data.read() # read the binary data
l = []
for i in data:
    l.append(bin(i)[-1])  #make a list of LSB bit
for i in range(0,500,8):
    print(chr(int(''.join(l[i:i+8]),2)),end='') # print the character
Which gives the flag !!

flag{remember_kids_protect_your_headers_afb3}

Footnote :

  1. LSB
  2. Python Binary File I/O