The following is derived from S-Tools BMP - How it is done by Andy Brown:
"S-Tools works by 'spreading' the bit-pattern of the message file to be hidden across the least-significant bits of the color levels in the image. S-Tools tries to reduce the number of image colors in a manner that preserves as much of the image detail as possible. It is difficult to tell the difference between a 256 color image and one reduced to 32."
"S-Tools adds some extra information on to the front of the message file before hiding. 32 bits of time-dependent random garbage is added first. This step means that two identical hidden files that are encrypted in CBC or PCBC mode will never encipher to the same ciphertext. The 32 bit length of the hidden file is then included. This is required for S- Tools to be able to extract the hidden file. Encryption will conceal this value."
"To further conceal the presence of a file, S-Tools picks its bits from the image based on the output of a random number generator. This is designed to defeat an attacker who might apply a statistical randomness test to the lower bits of the image to determine whether encrypted data is hidden there (well-encrypted data shows up as pure white noise). The random number generator used by S-Tools is based on the output of the MD5 message digest algorithm, and is not easily (if at all) defeatable" [S-Tools Documentation by Andy Brown].