Didier Stevens

(IN)SECURE Magazine has published my research on steganography with rainbow tables. As promised, I publish my last algorithm now (my previous posts: part 1, part 2).

This steganographic technique is based on the fact that a rainbow table contains chains with the same hash index but with a different start index.

A rainbow table is just a sequence of records. Each record has 2 fields of 8 bytes each, this makes a record 16 bytes wide. Therefore the size of a rainbow table is a multiple of 16. A record represents a chain. The first field is the password that started the chain. Actually, the first field is an index into the keyspace of all possible passwords for the given rainbow table set. It is a random number between 0 and the size of the keyspace – 1. The second field is the hash of the last password in the chain (actually, this is also an index and not the real hash). The rainbow table is sorted on the second field: the record with the lowest hash is first in the table and the one with the highest hash is last.

This is the hex dump of a rainbow table (the first 16 chains). The green box highlights the random data, notice that the 3 most significant bytes are 0. The blue box highlights the hash, notice that this column is sorted.
My steganographic technique is based on the fact that a rainbow table contains chains with the same hash index but with a different start index.

Take the rainbow table I’ve used in my tests. It’s 1 GB large and has 67.108.864 chains. It contains 9.513.435 pairs of chains with the same hash index but with a different start index. For 4.756.561 of these pairs, the first chain has a higher start index than the second chain. And for 4.756.874 of these pairs, the opposite is true: the first chain has a lower start index than the second chain. This even distribution should be no surprise, as the rainbow table is only sorted on the hash index and not on the start index.

We can change the order of these pairs without breaking the chain and without disrupting the order of the rainbow table. This will allow us to encode 1 bit per chain. I define the following encoding convention:

• a pair of chains with the same hash index and with the start index of the first chain smaller than the second chain represents a bit equal to zero
• a pair of chains with the same hash index and with the start index of the first chain greater than the second chain represents a bit equal to one

In our test table, the pair in the green box represents a 0 (0x1C7F02C85E < 0x2D1AB4B674) and the pair in the red box represents a 1 (0x94BD2F41F2 > 0x65616DC547).

Use this algorithm to hide a file in a sorted rainbow table:

• start a sequential search of chain pairs with equal hash indexes and different start indexes
• for each bit of the file to hide
  • if the bit is 0 and the chain pair has a first start index higher than the second, swap the order of the chains
  • if the bit is 1 and the chain pair has a first start index lower than the second, swap the order of the chains

To extract the hidden file, use this algorithm:

• start a sequential search of chain pairs with equal hash indexes and different start indexes
• if a chain pair has a first start index lower than the second, write a bit equal to 0
• if a chain pair has a first start index higher than the second, write a bit equal to 1

PoC code to store and retrieve data in rainbow tables using this technique can be found here.

Use rthide2 to hide data in a rainbow table, it takes 3 arguments:

• the rainbow table (remains unchanged)
• the file to hide (remains unchanged)
• the new rainbow table

To hide a file data.zip inside a rainbow table called lm_alpha-numeric-symbol14-space#1-7_0_5400x67108864_0.rt, use this command:

rthide2 lm_alpha-numeric-symbol14-space#1-7_0_5400x67108864_0.rt data.zip lm_alpha-numeric-symbol14-space#1-7_0_5400x67108864_0.rt.stego

This will create a new rainbow table called lm_alpha-numeric-symbol14-space#1-7_0_5400x67108864_0.rt.stego

Use rtreveal2 to extract data from a rainbow table, it takes 3 arguments:

• the rainbow table
• the file to create
• the size of the hidden file

To extract the data, issue this command (you have to know the length of the hidden file, my PoC program doesn’t store this).
rtreveal2 lm_alpha-numeric-symbol14-space#1-7_0_5400x67108864_0.rt.stego data.zip 1620

1620 is the length of file data.zip

The advantages of this technique over the previous techniques I developed is that it creates sorted rainbow tables without broken links, and that it is fast. The disadvantage is that it stores much less hidden data. In my example, a maximum of about 1 MB (9.513.435 bits) can be hidden in a rainbow table of 1 GB. Statistical analysis is the only way to detect the hidden data, but you can foil this by making your data appear random, for example with strong encryption.