Steganography 19 - The Order of the Code

Corinna John

Rate me:

4.99/5 (40 votes)

1 Mar 2010CPOL5 min read

48K

870

Encode a message in the order of any list

Download source - 49.62 KB

Introduction

People love chaos. Many things could be ordered and sorted, but usually we don't do it. Everything that could have a non-ambiguous order can be used to encode a number, because there are Factorial(count) enumerable permutations.

After reading this article, you'll encode messages in the order of arbitrary things. (Maybe you'll tidy up your room just for the fun of it.)

I was a little impressed by an example of storing a text message in a deck of 52 playing cards. I liked the algorithm, because it is clear and easy to implement. So I adapted it to store any stream of binary data in any Collection<IComparable>.

The class can be used to encode things in - for example - notes, shopping lists or the palette of GIF graphics. If you like the sport of Geo Caching, you often deal with lists of GPS waypoints. The order of the waypoints in a LOC or GPX file may depend on the time you plan to visit those places, the distance to your home or just arbitrary. That means we can apply the playing cards algorithm to your waypoints file, storing a short text in the order of the locations.

This article describes the generalized C# implementation and introduces a demo application for simple word lists as well as Geo Caching files. The application can import GPX and LOC files, sort them to encode an UTF-8 text message an export the result. (If nobody really needs that, it's still a quick GPX-LOC-converter.)

Encode by Sorting

The plan is to take a collection of IComparable and swap the objects to encode the content of a Stream:

public static void Encode<T>(
	Collection<T> source, // the carrier list
	Collection<T> result, // an empty list to store the result
	Stream messageStream) // the message to encode
	where T: class, IComparable
{

Every message is a number. We don't need to know if it is plain text, a music file or anything else, because we'll treat the whole stream as one big integer.

// initialize message
messageStream.Position = 0;
byte[] buffer = new byte[messageStream.Length];
messageStream.Read(buffer, 0, buffer.Length);
BigInteger message = new BigInteger(buffer);

Before we can order a list of objects, we have to define a sort key and its default order. For a list of people, the names can do the job. Geo Caches (Waypoints) can be sorted by coordinates, ID, name, distance to home, ... anyway, IComparable objects compare themselves. We'll sort the carrier items the way they want to be sorted and define that order as "0".

// initialize source list in "0"-order
T[] sortedItems = new T[source.Count];
source.CopyTo(sortedItems, 0);
Array.Sort(sortedItems);

A list in default order (i.e. alphabetical) encodes a value of "0". The first two items swapped might mean "1" and so on. One possible way to place the items of the source list in the free slots of the code list is integer division: For each item of the source list, you divide the message by the count of free slots and place the item [remainder] slots from the left. Hence we need a carrier list of the same length as the source list, and we need to know the current count of free slots in that list.

// initialize carrier
Collection<int /> freeIndexes = new Collection<int />();
result.Clear();
for (int n = 0; n < source.Count; n++)
{
	freeIndexes.Add(n);
	result.Add(null);
}

After these preparations, we can iterate over the source list (which is in "0"-order") and calculate each item's new position from the remaining message.

int skip = 0;
for (int indexSource = 0; indexSource < source.Count; indexSource++)
{
	skip = (message % freeIndexes.Count).IntValue();
	message = message / freeIndexes.Count;
	int resultIndex = freeIndexes[skip];
	result[resultIndex] = sortedItems[indexSource];
	freeIndexes.RemoveAt(skip);
}

Here's the complete encoder method:

public static void Encode<T>(
	Collection<T> source, // the carrier list
	Collection<T> result, // an empty list to store the result
	Stream messageStream) // the message to encode
	where T: class, IComparable
{
	// sort source list into "0"-order
	T[] sortedItems = new T[source.Count];
	source.CopyTo(sortedItems, 0);
	Array.Sort(sortedItems);
	
	// initialize message
	messageStream.Position = 0;
	byte[] buffer = new byte[messageStream.Length];
	messageStream.Read(buffer, 0, buffer.Length);
	BigInteger message = new BigInteger(buffer);
	
	// initialize carrier
	Collection<int> freeIndexes = new Collection<int>();
	result.Clear();
	for (int n = 0; n < source.Count; n++)
	{
		freeIndexes.Add(n);
		result.Add(null);
	}

	// encode by integer division
	int skip = 0;
	for (int indexSource = 0; indexSource < source.Count; indexSource++)
	{
		skip = (message % freeIndexes.Count).IntValue();
		message = message / freeIndexes.Count;
		int resultIndex = freeIndexes[skip];
		result[resultIndex] = sortedItems[indexSource];
		freeIndexes.RemoveAt(skip);
	}
}

How many bytes can a list store? The count of possible permutations is the factorial of the list's length. Every smaller number is the number of a specific permutation, hence a valid message. That means, every message shorter than the size of Factorial(length) - rounded off to the count of fully used bytes - is the unique number of a permutation.

public static long GetCapacity(long listLength)
{
	BigInteger capacity = new BigInteger(listLength);
	capacity = Factorial(capacity);
	int byteCapacity = (capacity.bitCount() / 8) - 1;
	return byteCapacity;
}

Decode the Order

This time we start with a carrier list in some specific order and a message of "0". For each list item, we have to find out the remainder of the integer division in the encoding process, so we can revert the divisions. How do we know how many free slots an item skipped? Well, the source list was in "0"-order, so after one item only "bigger" items could follow. That means, the count of "bigger" items to the left is exactly the skip count which is exactly the remainder of the former division.

The message was being divided by the count of free slots, resulting in a known remainder. Before that step, it had already been divided by all earlier counts of free slots. So we can multiply the skip value by (list.Count - position) for each position that came before the current one, sum up those values for all list items - and the result will be the message number.

Here's the decoder method:

public static void Decode<T>(
	Collection<T> carrier, // the carrier list
	Stream messageStream)  // an empty tream to store the message
	where T : class, IComparable
{
	// get the source list in "0"-order
	T[] sortedItems = new T[carrier.Count];
	carrier.CopyTo(sortedItems, 0);
	Array.Sort(sortedItems);
	// initialize message
	BigInteger message = new BigInteger(0);

	for (int carrierIndex = 0; carrierIndex < carrier.Count; carrierIndex++)
	{
		// count skipped slots to reconstruct the division's remainder
		int skip = 0;
		for (int countIndex = 0; countIndex < carrierIndex; countIndex++)
		{
			if (carrier[countIndex].CompareTo(carrier[carrierIndex]) > 0)
			{	// There is a bigger item to the left. It's place
				// must have been skipped by the current item.
				skip++;
			}
		}
	
		// Revert the division that resulted in this skip value
		int itemOrdinal = Array.IndexOf(sortedItems, carrier[carrierIndex])+1;
		BigInteger value = new BigInteger(skip);
		for (int countIndex = 1; countIndex < itemOrdinal; countIndex++)
		{
			value *= (carrier.Count - countIndex + 1);
		}
		message += value;
	}

	// write message
	byte[] messageBytes = message.getBytes();
	messageStream.Write(messageBytes, 0, messageBytes.Length);
	messageStream.Position = 0;
}

Flexible Sort Keys

When you're sorting objects, a unique sort key is important: In an address book, two people can have the same name, but unique birthdays - in another address book the names may be unique, but not the birthdays. On a route of waypoints some spots can have the same latitude, but a unique timestamp - on other routes the elevation can be the only unique property.

As the best sort key depends on the given data, it should be a property of the collection. After you filled it with comparable objects, you just tell the collection which field is the comparable one.

// fill the typesafe flexi-collection with objects
FlexibleComparableCollection<GeoCache> source = 
		new FlexibleComparableCollection<GeoCache>();
foreach (ListViewItem viewItem in lstGC.Items) {
	source.Add((GeoCache)viewItem.Tag);
}
// get the property name from the selected radio button
source.ComparablePropertyName = GetGCSortPropertyName();

How does this work? By a little reflection! FlexibleComparableCollection is a typesafe generic collection. When ComparablePropertyName is set, it looks up the property in its item type and then informs each item.

public class FlexibleComparableCollection<T> : Collection<T>
where T : FlexibleComparable
{
  private PropertyInfo comparableProperty;
  public string ComparablePropertyName {
	get {
		if (this.comparableProperty != null)
			return this.comparableProperty.Name;
		else	return string.Empty;
	}
	set {
		this.comparableProperty = typeof(T).GetProperty(value);
		foreach (FlexibleComparable item in this.Items) {
			item.UpdateComparableValue(this.comparableProperty);
		}
	}
  }
}

The items are derived from FlexibleComparable:

public class FlexibleComparable : IComparable
{	// read the key value only when it changes
	private object comparableValue;
	internal void UpdateComparableValue(PropertyInfo comparableProperty)
	{
		this.comparableValue = comparableProperty.GetValue(this, null);
	}

	// Interface IComparable
	public int CompareTo(object obj)
	{
		IComparable thisValue = this.comparableValue as IComparable;
		if (thisValue == null) return -1;

		IComparable otherValue;
		FlexibleComparable other = obj as FlexibleComparable;
		
		// get the other's key value (if any), or compare to the whole object
		if (other == null) otherValue = other as IComparable;
		else otherValue = other.comparableValue as IComparable;
	
		// compare, if you can!
		if (otherValue == null) return 1;
		else return thisValue.CompareTo(otherValue);
	}
}

That is all you need to abuse any collection of anything as a carrier medium. You only have to pick or invent a non-ambiguous property and make sure the message fits into the list.

private void EncodeInSomething()
{	// set up carrier list
	FlexibleComparableCollection<Something> source = GetList();
	source.ComparablePropertyName = "ChosenField";
	// initialize message and destination list
	Stream message = TextToStream(txtMessage.Text);
	Collection<Something> result = new Collection<Something>();
	// encode message
	OrderUtility.Encode<Something>(source, result, message);
	SaveList(result);
}

private void DecodeInSomething()
{	// set up carrier list
	FlexibleComparableCollection<Something> carrier = GetList();
	carrier.ComparablePropertyName = "ChoseField";
	// decode message
	MemoryStream message = new MemoryStream();
	OrderUtility.Decode<Something>(carrier, message);
	txtMessage.Text = new StreamReader(message).ReadToEnd();
}

The Demo Application

The application lets you enter word lists and import/edit GPS data. It displays the capacity of the current list and lets you encode/decode plain text. For a better understanding, the last tab page uses the number 1..256 as the carrier list, so you can see how the order changes with the encoded text.

Conclusion

With those few lines of code we're able to define a sort key on a list of objects, encode a binary message in the list's order and decode it again. The only requirement is one unique property, but it has to be unique only for the actual list, not for the class of objects in general.

Special thanks to Chew Keong TAN for his C# BigInteger Class and Peter Jerde for explaining the basics.