C# Quellcode für Visual Studio (.NET 2.0) - 35 kB

C# Quellcode für SharpDevelop (.NET 1.1) - 30 kB

Worum geht es?

Was haben ein GIF-Bild, eine HTML-Seite, und ein Einkaufszettel gemeinsam? Sie alle sind oder enthalten Listen, die keine besondere Reihenfolge erfordern. die Farben in der Palette eines GIF-Bildes können jede Reihenoflge haben, so wie die Attribute in einem HTML-Tag, oder die Wörter auf deinem Einkaufszettel.

In jeder Liste mit anzahl Elementen, können wir anzahl-1 Bits verstecken, nur durch das Sortieren der Einträge. Keine Tricks, keine komplizierten Formeln. Fangen wir an mit einer einfache Liste von Wörtern, dann setzen wir das Prinzip fort mit GIF-Paletten und danach mit HTML-Seiten. Der Algorithmus ist immer der gleiche, weil alle Listen im Grunde gleich sind.

Der erste Schritt ist, die Listenelemente in eine bestimmte Reihenfolge zu zwingen. Diese kann alphabetisch sein, oder eine eigene Sortierung. Dann wird die sortierte Liste neu sortiert, abhängig von den Bits der geheimen Nachricht.

Wenn du die Standard-Sortierung kennst, kannst du die Liste noch einmal sortieren, und die Stegano-Liste mit der sortierten Liste vergleichen. Die Unterschiede sagen dir alles über die Nachrichten-Bits, von denen die Reihenfolge stammte:

Zeile für Zeile

Man braucht nicht unbedingt einen Computer für Listen-Steganografie. Such dir ein Stück Papier und einen Stift, und schreib neun Tiere auf. Nein, das ist nicht der Anfang eines Psychotests, es ist ein Trägerdokument. Die Wörter brauchen eine Standard-Sortierung, auf die wir uns bei der späteren Neu-Sortierung beziehen können, darum sortieren wir sie alphabetisch. Diese Seite wurde aus dem Englischen übersetzt, daher die Unstimmigkeiten.

  1. Vogel
  2. Katze
  3. Dinosaurier
  4. Hund
  5. Fisch
  6. Pferd
  7. Kaninchen
  8. Schaf
  9. Einhorn

Ohne mathematische Tricks können neun Listeneinträge 9-1 = 8 Bits an geheimer Information verstecken, zum Beispiel das ASCII-Zeichen 'c' (99 or 01100011). Jeder Eintrag (außer dem Letzten) repräsentiert ein Bit. Für jedes 1-Bit verschieben wir das ersten Element aus der Original-Liste in die neue Liste, für 0-Bits verschieben wir einen anderen Eitnrag in die neue Liste. Angefangen mit dem höchsten Bit, läuft der Prozess folgendermaßen ab:

Original-Liste        Neue Liste

Vogel                 ---
Katze                 ---
Dinosaurier           ---
Hund                  ---
Fisch                 ---
Pferd                 ---
Kaninchen             ---
Schaf                 ---
Einhorn               ---

'0' Verstecken - Irgendein Element außer dem Ersten verschieben

Vogel                 Dinosaurier
Katze                 ---
---                   ---
Hund                  ---
Fisch                 ---
Pferd                 ---
Kaninchen             ---
Schaf                 ---
Einhorn               ---


'1' Verstecken - Erstes Element verschieben

---                   Dinosaurier
Katze                 Vogel
---                   ---
Hund                  ---
Fisch                 ---
Pferd                 ---
Kaninchen             ---
Schaf                 ---
Einhorn               ---

'1' Verstecken - Erstes Element verschieben

---                  Dinosaurier
---                  Vogel
---                  Katze
Hund                 ---
Fisch                ---
Pferd                ---
Kaninchen            ---
Schaf                ---
Einhorn              ---

'0' Verstecken - Irgendein Element außer dem Ersten verschieben

---                  Dinosaurier
---                  Vogel
---                  Katze
Hund                  Kaninchen
Fisch                 ---
Pferd                ---
---                  ---
Schaf                ---
Einhorn              ---

... ... und so weiter ... ...

'1' Verstecken - Erstes Element verschieben

---                  Dinosaurier
---                  Vogel
---                  Katze
---                  Kaninchen
---                  Einhorn
---                  Fisch
---                  Hund
Schaf                Pferd
---                  ---

Kein nicht-erster Element für ein '0'-Bit übrig,
dass bedeutet keine Kapazität für weitere Bits.
Letzten Eintrag trotzdem verschieben.

---                  Dinosaurier
---                  Vogel
---                  Katze
---                  Kaninchen
---                  Einhorn
---                  Fisch
---                  Hund
---                  Pferd
---                  Schaf

Die neue Liste enthält die gleichen Einträge wie die alte, und einen zusätzlichen Sub-Inhalt, von den nur wir etwas wissen. Das versteckte Byte kann wieder gelesen werden, wenn wir den gleichen Prozess rückwärts durchspielen.

Sortierte Liste      Trägerliste

Vogel                Dinosaurier
Katze                Vogel
Dinosaurier          Katze
Hund                 Kaninchen
Fisch                Einhorn
Pferd                Fisch
Kaninchen            Hund
Schaf                Pferd
Einhorn              Schaf

'Dinosaurier' ist nicht das erste Element der sortierten Liste, also war das versteckte Bit '0'.
Notier dir das, und streich das Element aus beiden Listen.

Vogel                ---
Katze                Vogel
---                  Katze
Hund                 Kaninchen
Fisch                Einhorn
Pferd                Fisch
Kaninchen            Hund
Schaf                Pferd
Einhorn              Schaf

'Vogel' aus der Trägerliste ist das erste Element in der sortierten Liste => '01'.

---                  ---
Katze                ---
---                  Katze
Hund                 Kaninchen
Fisch                Einhorn
Pferd                Fisch
Kaninchen            Hund
Schaf                Pferd
Einhorn              Schaf

'Katze' aus der Trägerliste ist das erste Element in der sortierten Liste => '011'.

---                  ---
---                  ---
---                  ---
Hund                 Kaninchen
Fisch                Einhorn
Pferd                Fisch
Kaninchen            Hund
Schaf                Pferd
Einhorn              Schaf

'Dinosaurier' ist nicht das erste Element der sortierten Liste => '0110'.
... ... und so weiter für alle Tiere ... ...

Das lateinische Alphabet ist keine gute Standard-Sortierung, denn jeder würde es gleich als Erstes ausprobieren. Mein Vorschlag: Misch dir Buchstaben durcheinander, und schreib dir ein benutzerdefiniertes Alphabet. Die Liste wie oben sortieren, können wir genausogut mit C#:

public StringCollection Hide(String[] lines, Stream message, String alphabet)
{
 //sort the lines according to a custom alphabet
 StringCollection originalList = Utilities.SortLines(lines, alphabetFileName);
 StringCollection resultList = new StringCollection();

 int messageByte = message.ReadByte();
 bool messageBit = false;
 int listElementIndex = 0;
 Random random = new Random();

 //for each byte of the message
 while (messageByte > -1) {
       //for each bit
       for (int bitIndex=0; bitIndex<8; bitIndex++) {

           //decide which line is going to be the next one in the new list

           messageBit = ((messageByte & (1 << bitIndex)) > 0) ? true : false;

           if (messageBit) {
              //pick the first line from the remaining original list
              listElementIndex = 0;
           }else{
              //pick any line but the first one
              listElementIndex = random.Next(1, originalList.Count);
           }

           //move the line from old list to new list

           resultList.Add(originalList[listElementIndex]);
           originalList.RemoveAt(listElementIndex);
       }

       //repeat this with the next byte of the message
       messageByte = message.ReadByte();
 }

 //copy unused list elements, if there are any
 foreach (String s in originalList) {
         resultList.Add(s);
 }

 return resultList;
}

Mit einer Liste und einem Alphabet lässt sich der Prozess ganz einfach umkehren:

public Stream Extract(String[] lines, String alphabet)
{
 //initialize empty writer for the message
 BinaryWriter messageWriter = new BinaryWriter(new MemoryStream());

 StringCollection carrierList = new StringCollection();
 carrierList.AddRange(lines);
 carrierList.RemoveAt(carrierList.Count - 1);

 //sort -> get original list
 StringCollection originalList = Utilities.SortLines(lines, alphabetFileName);
 String[] unchangeableOriginalList = new String[originalList.Count];
 originalList.CopyTo(unchangeableOriginalList, 0);

 int messageBit = 0;
 int messageBitIndex = 0;
 int messageByte = 0;

 foreach (String s in carrierList) {

         //decide which bit the entry's position hides

         if (s == originalList[0]) {
            messageBit = 1;
         }else{
            messageBit = 0;
         }

         //remove the item from the sorted list
         originalList.Remove(s);

         //add the bit to the message
         messageByte += (byte)(messageBit << messageBitIndex);

         messageBitIndex++;
         if (messageBitIndex > 7) {
            //append the byte to the message
            messageWriter.Write((byte)messageByte);
            messageByte = 0;
            messageBitIndex = 0;
         }
 }

 //return message stream
 messageWriter.Seek(0, SeekOrigin.Begin);
 return messageWriter.BaseStream;
}

Bunte Bits

Jede indizierte Bitmap enthält eine Liste, die sich auf die gleiche Weise missbrauchen lässt. Diese beiden Paletten gehören zum gleichen GIF-Bild. Eine ist das Original, die andere enthält einen versteckten Text von 31 Zeichen:

Wieder ist das Erste was wir brauchen eine Palette mit einer Standard-Sortierung. In diesem Beispiel werden wir die Farben nach ihren ARGB-Werten sortieren.

public Bitmap Hide(Bitmap image, Stream message)
{
 //list the palette entries an integer values
 int[] colors = new int[image.Palette.Entries.Length];
 for (int n = 0; n < colors.Length; n++) {
     colors[n] = image.Palette.Entries[n].ToArgb();
 }

 //initialize empty list for the resulting palette
 ArrayList resultList = new ArrayList(colors.Length);

 //initialize and fill list for the sorted palette
 ArrayList originalList = new ArrayList(colors);
 originalList.Sort();

Viele Pixel verweisen auf die Paletteneinträge, und die werden wir ebenfalls anpassen müssen. Also sollten wir, wenn wir eine Farbe in die neue Palette verschieben, alten und neuen Index notieren.

 //initialize list for the mapping of old indices to new indices
 SortedList oldIndexToNewIndex = new SortedList(colors.Length);

Jetzt sind die Listen fertig, und wir können in die Nachricht eintauchen und für jedes Bit eine Farbe verschieben...

 Random random = new Random();
 int listElementIndex = 0;
 bool messageBit = false;
 int messageByte = message.ReadByte();

 //for each byte of the message
 while (messageByte > -1) {
       //for each bit
       for (int bitIndex = 0; bitIndex < 8; bitIndex++) {

           //decide which color is going to be the next one in the new palette

           messageBit = ((messageByte & (1 < bitIndex)) > 0) ? true : false;

           if (messageBit) {
              listElementIndex = 0;
           }else{
              listElementIndex = random.Next(1, originalList.Count);
           }

...aber nicht vergessen, von welcher Position in der Original-Palette die Einträge kamen! Tausende Pixel warten auf aktualisierte Farbindizes.

           //log change of index for this color
           int originalPaletteIndex = Array.IndexOf(colors, originalList[listElementIndex]);
           if( ! oldIndexToNewIndex.ContainsKey(originalPaletteIndex)) {
               //add mapping, ignore if the original palette contains more than one entry for this color
               oldIndexToNewIndex.Add(originalPaletteIndex, resultList.Count);
           }

           //move the color from old palette to new palette
           resultList.Add(originalList[listElementIndex]);
           originalList.RemoveAt(listElementIndex);
     }

     //repeat this with the next byte of the message
     messageByte = message.ReadByte();
     }
 //copy unused palette entries
 foreach (object obj in originalList) {
    int originalPaletteIndex = Array.IndexOf(colors, obj);
    oldIndexToNewIndex.Add(originalPaletteIndex, resultList.Count);
    resultList.Add(obj);
 }

 //create new image
 Bitmap newImage = CreateBitmap(image, resultList, oldIndexToNewIndex);
 return newImage;
}

Die korrespondierende Extract-Methode änelt einer Kombination der Hide- und Extract-Methoden für Text-Listen. Sie sortiert die Palette, rekonstruiert die Nachricht, und entfernt dann die Nachricht aus dem Bild (produziert ein Bild mit einer Palette in Standard-Sortierung). Das hier ist die Palette aus dem Beispiel, nachdem die Nachricht ausgelesen und entfernt wurde:

Tags voller Text-Listen

Ein HTML-Document selbst ist keine sortierbare Liste, die Tags müssen in ihrer Reihenfolge bleiben. Aber innerhalb der Tags stehen Attribute, und diese können beliebig sortiert werden. Das heißt, jedes Tag einer HTML-Seite kann Attributes.Count-1 Bits speichern. Die meisten Tags haben gerade genug Attribute für ein oder zwei Bits, aber wir können die Nachricht über alle Tags der Seite verteilen.

public void Hide(String sourceFileName, String destinationFileName, Stream message, String alphabet) {
       //initializations skipped
       // ... ... ...

       //list the HTML tags
       HtmlTagCollection tags = FindTags(htmlDocument);

       //loop over tags
       foreach (HtmlTag tag in tags) {

       //write beginning of the tag
       insertTextBuilder.Remove(0, insertTextBuilder.Length);
       insertTextBuilder.AppendFormat("<{0}", tag.Name);

       //list attribute names
       String[] attributeNames = new String[tag.Attributes.Count];
       for (int n = 0; n < attributeNames.Length; n++) {
          attributeNames[n] = tag.Attributes[n].Name;
       }

Ab hier ist der Code fast der gleiche wie in den anderen Hide-Methoden:

       //get default sorting
       StringCollection originalList = Utilities.SortLines(attributeNames, alphabet);
       StringCollection resultList = new StringCollection();

       if (tag.Attributes.Count > 1) {
          //the tag has capacoty for one or more bits

          for (int n = 0; n < attributeNames.Length - 1; n++) {

              //get next bit of the message

              bitIndex++;
              if (bitIndex == 8) {
                 bitIndex = 0;
                 if (messageByte > -1) {
                    messageByte = message.ReadByte();
                 }
              }

              if (messageByte > -1) {

                 //decide which attribute is going to be the next one in the new tag

                 messageBit = ((messageByte & (1 << bitIndex)) > 0) ? true : false;

                 if (messageBit) {
                    listElementIndex = 0;
                 }else{
                    listElementIndex = random.Next(1, originalList.Count);
                 }
              }else{
                 listElementIndex = 0;
              }

              //move the attribute from old list to new list
              resultList.Add(originalList[listElementIndex]);
              originalList.RemoveAt(listElementIndex);
          }
       }

       if (originalList.Count > 0) {
          //add the last element - it never hides data
          resultList.Add(originalList[0]);
       }

Die sortierten Attribute müssen zuück ins Dokument geschrieben werden. Der größte Teil des Codes wurde aus dem letzten HTML-Artikel dieser Serie kopiert, und muss hier hoffentlich nicht extra erklärt werden. ;-)

       HtmlTag.HtmlAttribute attribute;
       foreach (String attributeName in resultList) {
              attribute = tag.Attributes.GetByName(attributeName);

              insertTextBuilder.Append(" ");
              if (attribute.Value.Length > 0) {
                 insertTextBuilder.AppendFormat("{0}={1}", attribute.Name, attribute.Value);
              }else{
                 insertTextBuilder.Append(attributeName);
              }
       }

       //replace old tag with new tag
       //.. ... ...
}

Hast du bemerkt, dass die drei Hide-Methoden fast das gleiche tun? Die Extract-Methoden sind genauso ähnlich. Bitte lies sie im vollständigen Quelltext nach, falls du noch keine Bits-Allergie hast...

Die Demo-Anwendung

Die Anwendung besteht aus drei three "Halbduplex-Dialogen". Man kann entweder einen leeren Träger und eine Nachricht, oder einen Träger zum Auslesen einer Nachricht angeben. Bei Text-Listen und Bildern kann man das Ergebnis sofort sehen.

In den Dialogen für Text-Listen und HTML-Dokumente kann man eine "Alphabet-Datei" angeben. Das ist eine Textdatei mit einem benutzerdefinierten Alphabet. Ein beispielhaftes Alphabet findest du in testdata/demo.txt.