I find steganography (hiding information so that it remains unnoticed unless you know it’s there) a very interesting subject. If you read my blog you already know that.

I thought it would be great to hide data in lists of things. I could permutate the order of elements, so that information is contained in that order. If we have n elements in a list, we have n! permutations of those elements… so we can hide log2(n!) bits.

I’ve implemented a little program that does that. It’s called stegotation. The worst part of implementing it was to convert from a binary stream to a mixed-base number (a permutation can be thought as a number that has a mixed-base in all its digits: n, n-1, n-2, …., 3, 2, 1). I had to do it as in school times: dividing. But the numbers are so big! Fortunately Python comes to the rescue with built-in multi-precision numbers. Great!

The program encodes the data as follows:

• It compresses the data using zlib.
• Prepends a length field (2 bytes).
• Pads with random data till we have floor(log2(n!)/8) bytes.
• Converts this to a big number.
• Converts this to a mixed-base number by dividing by 2, 3, 4, ….
• Encodes these numbers as a word list.

Decoding the data is just the same backwards.

I was about to add a password (to derive a symmetric key from it and encrypt data with it using, for instance, a stream cipher), but it would complicate everything if I want you to test it. It’s very easy to implement if you want.

Ok. Now the example. I have a list of bands that performed in the Primavera Sound 2005 festival last weekend. It’s called bandlist.txt. Then I hide a message. It’s very short (because the list of bands is small), only a enumeration of some bands I liked.

stegotation.py hide bandlist.txt chronicle.txt bandlistwithhiddenmessage.txt

The resulting list is called bandlistwithhiddenmessage.txt.

To recover the message, you only need to type:

stegotation.py recover bandlistwithhiddenmessage.txt recovered.txt

I hope that someone will succeed in decoding the data and tells me which bands I liked.

This entry was posted on Tuesday, May 31st, 2005 at 01:15 and is filed under Altres llengües, [en], Formiguer, Seguretat. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.