What's In the Book
    What's New
    What's Old
FAQ
Click here to experiment with hiding information in the noise of a picture.
Click here to hide a message as a baseball game's voiceover with mimic functions.
Click here to hide a message in a list of disco songs or any other list you choose.
Click here to hide a message by scrambling the letters of a word.
Steganography Links
Download Software
Errata
To contact me: p3@wayner.org
If you're interested in keeping your database secure from prying eyes, fraudsters, traitorous insiders, and hackers, check out Translucent Databases.



Hiding Information in the Order of Things


Let's say you want to send someone a message by shuffling a deck of cards, writing down a shopping list, pontificating on the 100 best anything, or just scribbling some words. One solution is to hide the information in the order of things. If there's no intrinsic or essential order, then there's no easy way for someone to discover the message even exists. If any order will do, then you can hide a message just by shuffling the objects.

This note describes a basic algorithm for encoding the message in the order of things and includes a Java applet to help you experiment.

A Strange Notation

Before beginning, we need to introduce one slightly strange notation, a flexible base, where the ith digit can be any value between 0 and i+1. The digits are enumerated from right to left so the smallest value, the one with the least significance on the right, is digit 0. It can be either a 0 or a 1. The next digit to its left, the one with next-to-least significance, is digit 1 and it can be either a 0, a 1, or a 2.

Here's a value in the flexible base: 321. Each digit is set to it's maximum value. What is this value in base 10? To figure this out, first find the multiple assigned to each digit. That is, how much each digit contributes to the final value. In base 10, the multiple assigned to digit 1 is 10 and the multiple assigned to digit 2 is 100. To put it simply, the multiple of digit i is 10i in base ten and 2i in base two. What is the multiple of each digit in this flexible base? In the fixed bases, each digit's multiple increases by another factor of the base for each new digit. In this example, each digit has a different value. The 0 digit can only take two values, 0 or 1. The 1 digit can take three values, 0, 1 or 2. The multiple of digit i is (i+1)!. You can check it out. What is 321 in base ten? That's 1*(1!)+2*(2!)+3*(3!)=1+4+18=23.

Using This Notation

This notation is a great tool for organizing the different orders for a set of objects. It allows us to count them and give them a unique number.
Let's begin with five recording artists in alphabetical order:
  • Abba
  • Barry Manilow
  • Cher
  • Donny and Marie
  • Eagles

Let's call this the master list. There are five objects and 5!=120 different ways to rearrange the list. The flexible base notation can be used as a simple way to give each arrangement a unique value. This lets us keep the different orderings straight and find an easy way to encode a message using them.

Here's an example. Like most people, I would argue that it's not possible to put these bands in order from greatest to least. Putting an order on such a list of luminaries is not possible. But if someone put a gun to my head, I would choose this order:

  • Eagles
  • Abba
  • Barry Manilow
  • Donny and Marie
  • Cher
Is it possible to turn this into a number? Yes, if you use the master list as a guide.

Here's an algorithm:
  1. Start with an alphabetical master list. Number the items beginning with zero instead of 1. That means Abba gets 0, Barry gets 1, Cher gets 2, etc.
  2. Take the first item from your arbitrary list and find it in the alphabetical master list. In this case, my first choice, the Eagles, is in position 4 at the bottom of the alphabetical master list. This will be the left most digit in our notational scheme.
  3. Delete the Eagles from the list.
  4. Now find the second band from my list, Abba, in the alphabetical list. It's first which means it comes with the digit 0. This will be the next digit in the value which now looks like: 40.
  5. Delete Abba. The alphabetical list now looks like:
    • Barry Manilow
    • Cher
    • Donny and Marie
  6. The third item on my list, Barry Manilow, is now at the top of the alphabetical list. That means it has a value of 0. After deleting it, the number now looks like 400.
  7. The fourth item, Donny and Marie, is second on the list meaning it has value 1.
  8. The final name, Cher, is ignored.
This algorithm produces the value 4001, a number in the flexible base. What is this value in base 10? 4*4!+0*3!+0*2!+1=97. Notice that this algorithm's output depends entirely upon the structure of the master list and this list always gets the value 000...000. It is relatively easy to prove that any arbitrary list can produce any arbitrary value with the choice of the right master list.

Sending A Hidden Message



How can you send a hidden message in a list of bands? If there are n! ways to arrange n items, then you can pack in log 2 n! bits into one choice of n items. In the last example, there were five items and 5!=120 possibilities. This means you can put in just under 7 bits. I could have been sending the message of 97=1100001 when I offered the list:
  • Eagles
  • Abba
  • Barry Manilow
  • Donny and Marie
  • Cher
If you want to send a message, you just need to figure out how many bits are in the message and then find a list of objects long enough to encode the bits. Then use the algorithm above to find an ordering of the objects that encodes that number.The algorithm above can be run in reverse to turn a number in the flexible base notation into a list of objects.

Adding a Password


The algorithm for turning a list of objects into a number relied upon a master list arranged in alphabetical order. There is no reason we have to use an alphabetical ordering. Any master list could serve our purpose. Alphabetical is just one way to define a master list..

If you want a simple password, just agree upon a secret ordering of the master list. This is like a one-time pad. It's a bit cumbersome, but ultimately very secure.

You can also use a traditional password to make life a bit simpler. This requires a  cryptographically secure hash function, an algorithm that takes a pile of data and scrambles it beyond recognition.

An ideal hash function, h(x), will be so inscrutible that it will be impossible to take h(x) and figure out the x that produced it and this is why some call it a one-way function. There are several commonly accepted hash functions like the SHA (Secure Hash Algorithm) and MD-5 (Message Digest-5). Many encryption functions can act in the same way.

You can use the hash function to create a shared secret master list. For every item in the master list, compute h(password, item). Then put this list in alphabetical order. Here's an example:
 
value
 h(password,value)
 new position
Abba
 4012309120980149123
 2
Barry Manilow
 7209213098091234412
 4
Cher
 1321592349102981234
 1
Donny and Marie
 5282394209230235122
 3
Eagles
 8293408028341203943
 5
 
If these were the values produced by h(password, value), then the new secret master list produced by this password would be:
  • Cher
  • Abba
  • Donny and Marie
  • Barry Manilow
  • Eagles

Notice that the master list can be assembled from just the password and the items in the list. There's no need for anyone to remember the order itself. Anyone can decode the message encoded in the order of items in a list by knowing the password alone.

Bandwidth


This method can be quite efficient if the size of the objects is limited. You can store log2n! bits in a list of n items. This value essentially tracks the value of log2 n because log2n!=log2 1+log22+log23+ ... +log2n. Every new item in the list of objects adds log2n bits to the capacity.

If the size of the objects is tightly limited, then the channel can be quite efficient. 256 objects can be represented by 256 bytes. log2 256!=1684 or 210 bytes. That's 82% of the channel. A program called GifShuffle uses this math to store a message in the order of colors in a GIF image.








Applet



If you have a Java-enabled browser, then an applet will start up below.

Here are instructions for using it:
  1. Choose a password. Only people with the password will be able to get the message.
  2. Write your message. This version only sends upper-case letters to reduce the complexity of the message.
  3. Add your list. The software begins with some disco songs, but you can make your own list. You can add your own. Put one list item on each line. Don't hit return or you'll split an item into two parts that might be resorted. 
  4. Press encode.
  5. The list will now be resorted. The new order hides your message. If you're curious, the software converted your message into a big integer that's you can see. Then, it used this information to choose one of the n! different ways to arrange n items.
  6. Cut and paste the result into a message to your friend.
  7. To decode, make sure to copy the list exactly. Any typographic error can scramble it. 
  8. Type in the same password.
  9. Press decode. The message should appear in the message slot.

Your browser doesn't recognize Java applets. Get one that does.
Please let me know if you make any changes. I'll be glad to roll good ideas into the source tree. Write me, p3@wayner.org, if you have trouble.