Didier Stevens

In my previous post about steganography and rainbow tables, I explained a technique to hide data in a rainbow table. The disadvantage of this method is that there is a way, albeit costly, to detect the hidden data. This is because we replace the random bytes, that makeup the start of the chain, by the data we want to hide, thereby breaking the chain. A broken chain can be detected by recalculating the chain and comparing the recalculated hash with the stored hash. If they differ, the chain is broken.

But if we know that we are breaking chains, why don’t we fix them? We can proceed as follows:

• replace the start of the chain (random bytes) with the data we want to hide
• recalculate the chain
• replace the hash of the chain with the new hash we calculated

This way, there are no more broken chains that give away our hidden secret. But now there is another telltale sign that the rainbow table has been modified to hide data: the hashes aren’t sorted anymore. Remember that a rainbow table has to be sorted (the sort key is the index of the hash) to be useful. It is very unlikely that our new hash is greater (or equal) than it’s predecessor and smaller (or equal) than its successor. Detecting an unsorted rainbow table is much easier than finding broken chains.

OK, so if the new rainbow table is unsorted, why don’t we just sort it again? Well, if we resort the rainbow table, we destroy the order in which we stored our hidden data, so we loose the hidden data itself.

You could keep the original order of the hidden data by creating an index, this is another file that indexes the chains with hidden data. For example, you could make a list of all the hashes with hidden data. This list will then allow you to retrieve all chains with hidden data in the correct order. And the fact that you have such a list of chains isn’t necessarily suspicious, it’s just a list of hashes you want to crack…

But there is a simple way out of the unsorted rainbow table problem. Rainbow tables generated with the rtgen program are unsorted. In fact, you have to sort them with the rtsort command after generating them, before they can be used by the rtcrack program. The solution is to adapt the rtgen program to generate a rainbow table with hidden data, and keep this unsorted rainbow table.

And this is not so difficult. We add this method to the chain class:

void CChainWalkContext::InjectHiddenData(FILE *fFile, int bytes)
{
  unsigned char *byteInject;
  int iIter;
  int iChar;

  byteInject = (unsigned char *) &m_nIndex;

  for (iIter = 0; iIter < bytes; iIter++)
  {
    if ((iChar = fgetc(fFile)) == EOF)
      return;
    byteInject [iIter] = iChar;
  }
}

The arguments are a file handle to the file with data we want to hide, and the number of bytes per chain we use to hide data. We call the InjectHiddenData method in the rtgen program just after having generated random data (cwc.GenerateRandomIndex();, line 206 of file RainbowTableGenerate.cpp).

Our modified rtgen program allows us to generate an unsorted rainbow table with hidden data. The only way to detect this hidden data is with statistical analysis, provided that the hidden data doesn’t appear random. There are no broken chains that indicate hidden data, unlike with the previous method.
The disadvantage of this method is that you’ll have to generate a new rainbow table to hide your data, which is a lengthy process.

To extract the data file, use the same program as for the previous method, rtreveal

If you don’t feel comfortable using an unsorted rainbow table to hide data, I have probably two extra techniques for you.
One technique creates a sorted rainbow table without broken chains and it is fast. The disadvantage is that it stores much less hidden data. But you’ll have to wait a bit before I publish this technique. I’ve submitted an article about this steganographic technique to 2600 Magazine, and I can only release it after it gets published or refused.

The other technique also creates a sorted rainbow table without broken chains and it is fast, but I still have to work on it. It works, but it might be detectable. I’ll publish it when I’ve finished working on it.