Geheime Botschaften in Bildern

1. Verstecken statt verschlüsseln

In Kryptographie im Terminal hast du Nachrichten verschlüsselt. Wer die verschlüsselte Datei abfängt, kann sie nicht lesen, aber er weiß, dass da etwas Geheimes ist. Manchmal ist schon das zu viel.

Steganographie (griechisch für »verdecktes Schreiben«) versteckt, dass es eine Nachricht gibt. Früher war das unsichtbare Tinte oder ein winziger Mikropunkt auf einem Brief. Heute ist es oft ein Bild: Ein Foto hat Hunderttausende Pixel, und an jedem kann man ein wenig ändern, ohne dass es jemand sieht. Die Kunst ist, genau so wenig zu ändern, dass niemand Verdacht schöpft, weder ein Mensch noch ein Programm, das danach sucht.

Beides lässt sich kombinieren: erst verschlüsseln, dann verstecken. Dann muss jemand die Nachricht erst finden und kann sie danach noch immer nicht lesen.

2. Einrichten

Lege einen Ordner an und öffne ihn mit StrgK StrgO:

mkdir /workspace/stego

Hol dir die Bilder dieser Seite: zwei Fotos und ein Fundstück, in dem schon etwas versteckt ist.

wget https://workspace.hackschule.de/steganography/fundstueck.png
wget https://workspace.hackschule.de/steganography/strandhaeuser.png
wget https://workspace.hackschule.de/steganography/moewen.png

Die Fotos der Strandhäuser und der Möwen mit freundlicher Genehmigung von Ian Kobylanski · https://koby.photography/

PNG-Dateien sind komprimiert, aber ohne Verlust: Jedes Pixel kommt genau so wieder heraus, wie es hineingesteckt wurde. Das ist wichtig, denn eine versteckte Botschaft lebt in den kleinsten Unterschieden. Ein JPEG würde sie beim Speichern zerstören. Das Lesen und Schreiben übernimmt eine Bibliothek:

gem install chunky_png

pip install pillow

3. Ein Bild ist eine Liste von Zahlen

Jedes Pixel hat drei Kanäle, Rot, Grün und Blau, jeder eine Zahl von 0 bis 255. Ein Bild mit 480 × 320 Pixeln ist also nichts anderes als 480 · 320 · 3 = 460.800 Zahlen. Das Gerüst unten holt sie in eine einzige Liste, Zeile für Zeile, und macht aus so einer Liste wieder ein Bild.

Lege die Datei stego.rb an:

require 'chunky_png'

# Rot, Grün und Blau jedes Pixels, Zeile für Zeile, in einem Array:
# [r0, g0, b0, r1, g1, b1, ...]
def channels(image)
    image.pixels.flat_map { |c| [ChunkyPNG::Color.r(c), ChunkyPNG::Color.g(c), ChunkyPNG::Color.b(c)] }
end

# Das Bild zu einem solchen Array
def from_channels(width, height, values)
    ChunkyPNG::Image.new(width, height, values.each_slice(3).map { |r, g, b| ChunkyPNG::Color.rgb(r, g, b) })
end

# Ein Bild aus einem einzigen Bit jedes Kanals: 255, wo es gesetzt ist, sonst 0
def bit_plane(image, bit = 0)
end

image = ChunkyPNG::Image.from_file('fundstueck.png')
p [image.width, image.height]
p channels(image)[0, 6]

Starte es mit ruby stego.rb.

Lege die Datei stego.py an:

from PIL import Image


# Rot, Grün und Blau jedes Pixels, Zeile für Zeile, in einer Liste:
# [r0, g0, b0, r1, g1, b1, ...]
def channels(image):
    return list(image.convert('RGB').tobytes())


# Das Bild zu einer solchen Liste
def from_channels(width, height, values):
    return Image.frombytes('RGB', (width, height), bytes(values))


# Ein Bild aus einem einzigen Bit jedes Kanals: 255, wo es gesetzt ist, sonst 0
def bit_plane(image, bit=0):
    pass


image = Image.open('fundstueck.png')
print(image.size)
print(channels(image)[:6])

Starte es mit python3 stego.py.

Die ersten sechs Zahlen sind die ersten beiden Pixel oben links, ein helles Himmelblau: 68, 168, 224 und noch einmal dasselbe.

Das unterste Bit

Jede dieser Zahlen ist im Computer acht Bits, eine Zahl im Zweiersystem. 208 ist 11010000: 128 + 64 + 16. Das Bit ganz rechts, das unterste Bit, zählt nur 1. Ändert man es, wird aus 208 die 209, ein Blau, das kein Mensch von 208 unterscheiden kann. Das oberste Bit dagegen zählt 128: Aus 208 würde 80, ein ganz anderes Blau.

Schreib bit_plane(image, bit): Es macht aus jedem Kanal 255, wenn sein Bit Nummer bit gesetzt ist, und sonst 0, und gibt das als neues Bild zurück, mit from_channels. Man nennt so ein Bild eine Bitebene. Die Bitebene 7 zeigt grob das Bild selbst; je tiefer das Bit, desto mehr sieht es nach Rauschen aus.

Sieh dir die Bitebenen 0 und 1 des Fundstücks an. Speichere sie dafür als Bilder und öffne sie in Visual Studio Code:

image = ChunkyPNG::Image.from_file('fundstueck.png')
bit_plane(image, 0).save('ebene-0.png')
bit_plane(image, 1).save('ebene-1.png')

image = Image.open('fundstueck.png')
bit_plane(image, 0).save('ebene-0.png')
bit_plane(image, 1).save('ebene-1.png')

In Bitebene 1 steht ein Hinweis, mitten in einem Foto, das ganz normal aussieht. Bitebene 0 sieht dagegen nach Rauschen aus, wie bei jedem Foto, nur dass in ihr diesmal etwas steckt.

4. Eine Botschaft im untersten Bit

Das Verfahren heißt Least Significant Bit, kurz LSB: Jedes unterste Bit jedes Kanals wird durch ein Bit der Botschaft ersetzt. Damit ein Programm die Botschaft wieder herausholen kann, müssen beide Seiten dieselben Regeln benutzen. Hier sind sie:

1. Die Botschaft ist Text, als Bytes in UTF-8. Vor diese Bytes kommt ihre Länge als Zahl mit 32 Bit, also 4 Bytes. So weiß, wer liest, wie viele Bytes kommen.
2. Jedes Byte wird zu 8 Bits, das höchste Bit zuerst: Aus »A« (65) wird 01000001.
3. Die Bits kommen der Reihe nach in die untersten Bits der Kanäle: das erste in Rot des ersten Pixels, das zweite in Grün, das dritte in Blau, dann das zweite Pixel und so weiter, Zeile für Zeile, genau in der Reihenfolge von channels.

Schreib hide(image, message): Es gibt ein neues Bild zurück, in dem die Botschaft steckt, und meldet einen Fehler, wenn sie nicht hineinpasst. Und schreib reveal(image): Es liest zuerst 32 Bits und daraus die Länge, dann so viele Bytes, und macht wieder Text daraus.

Jetzt kannst du lesen, was im Fundstück steckt:

puts reveal(ChunkyPNG::Image.from_file('fundstueck.png'))

print(reveal(Image.open('fundstueck.png')))

Versteck eine eigene Botschaft in strandhaeuser.png, speichere das Ergebnis als geheim.png und öffne beide nebeneinander. Findest du einen Unterschied?

5. Wie viel passt hinein?

Ein Bild mit 480 × 320 Pixeln hat 460.800 Kanäle und damit 460.800 unterste Bits: 57.600 Bytes, davon 4 für die Länge. Das ist eine ganze Menge Text, etwa 30 Seiten eines Buchs.

Die Spezifikation des GIF-Formats ist größer, 83.003 Bytes. Hol sie dir und versuch, sie in strandhaeuser.png zu verstecken:

wget https://workspace.hackschule.de/lzw/spec-gif89a.txt

Mehr passt hinein, wenn man mehr als ein Bit pro Kanal ersetzt. Gib hide und reveal einen weiteren Parameter depth, wie viele der untersten Bits jeder Kanal trägt, zum Beispiel hide(image, message, 2). Mit 2 Bits passt die Spezifikation hinein. Nur: Mit jedem Bit mehr wird der Unterschied größer. Ein Kanal kann sich mit 1 Bit um höchstens 1 ändern, mit 2 Bits um 3, mit 4 Bits um 15.

So sieht der Himmel aus moewen.png aus, wenn alle untersten Bits voller Daten sind:

Mit 1 und 2 Bits sieht man nichts. Mit 4 Bits sieht man Rauschen und Streifen: Im glatten Verlauf des Himmels behält jeder Kanal nur noch seine oberen 4 Bits, also 16 Stufen statt 256, und der Verlauf zerfällt in Bänder. Gerade glatte Flächen verraten zu viele versteckte Daten; in Laub, Wellen oder Stoff fällt dasselbe Rauschen kaum auf.

6. Entdecken

Wer nach versteckten Botschaften sucht, hat das Bild ohne Botschaft nicht zum Vergleich. Trotzdem gibt es Spuren.

Was die Bitebene zeigt

Hier sind die Strandhäuser und daneben ihre Bitebene 0: so, wie sie sind, mit der GIF-Spezifikation als Text im untersten Bit (so viel davon hineinpasst), und mit derselben Spezifikation, aber vorher komprimiert:

Text verrät sich: In UTF-8 ist bei den meisten Zeichen das oberste Bit jedes Bytes 0, und Buchstaben, Leerzeichen und Zeilenenden wiederholen sich. Jedes achte Bit ist fast immer gleich, und das ergibt die Streifen. Komprimierte Daten dagegen sehen aus wie Zufall: Ein guter Kompressor nimmt jede Wiederholung heraus, und übrig bleiben Bits, die so oft 0 wie 1 sind. Die Bitebene sieht dann aus wie bei einem gewöhnlichen Foto. Verschlüsselte Daten sehen genauso aus.

Komprimiere eine Botschaft vor dem Verstecken:

require 'zlib'
packed = Zlib::Deflate.deflate(File.binread('spec-gif89a.txt'), 9)

import zlib
packed = zlib.compress(open('spec-gif89a.txt', 'rb').read(), 9)

Der Chi-Quadrat-Test

Ist die Botschaft damit unauffindbar? Nein, und gerade weil ihre Bits so gleichmäßig sind. Andreas Westfeld und Andreas Pfitzmann haben 1999 gezeigt, wie man das merkt.

Ersetzt man das unterste Bit, wird aus einer 208 entweder 208 oder 209, aus einer 209 ebenso. Die Werte 208 und 209 bilden ein Paar, und dasselbe gilt für 0 und 1, 2 und 3, bis 254 und 255. Sind die versteckten Bits zufällig, landet jeder Wert eines Paares mit gleicher Wahrscheinlichkeit auf dem einen oder dem anderen. Nach dem Verstecken kommen deshalb beide Werte eines Paares gleich oft vor. In einem gewöhnlichen Foto ist das nicht so: Dort ist 208 vielleicht 300-mal da und 209 nur 250-mal.

Der Chi-Quadrat-Test misst, wie weit die Paare von »gleich oft« entfernt sind, verglichen mit dem, was der Zufall allein ergäbe. Für jedes Paar zählst du, wie oft seine beiden Werte vorkommen, a und b. Gleich oft hieße: jeder \( e = \frac{a+b}{2} \)-mal. Dann rechnest du

$$\chi^2 = \sum_{\text{Paare}} \left( \frac{(a-e)^2}{e} + \frac{(b-e)^2}{e} \right)$$

und teilst durch die Zahl der Paare. Paare mit \( e < 5 \) lässt du weg, sie sind zu selten, um etwas zu sagen. Kommt etwa 1 heraus, sind die Paare genau so gleich, wie es zufällige unterste Bits machen: verdächtig. Ein Foto ohne Botschaft liegt weit darüber.

Schreib chi_square(image, top, bottom): Es rechnet den Test für die Zeilen top bis bottom des Bildes. Mit Pillow schneidet image.crop((0, top, image.width, bottom)) diese Zeilen aus, mit ChunkyPNG image.crop(0, top, image.width, bottom - top).

Rechne den Test für die Strandhäuser ohne Botschaft und mit der komprimierten Spezifikation, jeweils für die Zeilen 0 bis 40, 40 bis 80, 80 bis 120 und 120 bis 160. Die Botschaft füllt nur die obersten gut 110 Zeilen.

Der Test findet die Botschaft und sogar, wo sie aufhört: Dort, wo sie steckt, liegt das Ergebnis nahe bei 1, darunter ist es so groß wie ohne Botschaft. Am deutlichsten ist es im Himmel, wo das Foto ohne Botschaft weit über 100 ergibt. Rechne zum Vergleich auch die Zeilen 200 bis 240, die Türen mit ihrer feinen Maserung: Dort ist der Test schon ohne Botschaft klein, denn das Rauschen des Fotos ist dort selbst fast so gleichmäßig wie eine Botschaft. Eine Botschaft in solchen Flächen fällt viel weniger auf. Was hilft noch?

• Weniger verstecken und die Bits über das ganze Bild verteilen, an Stellen, die ein Schlüssel auswählt. Dann ist jede Zeile nur ein wenig gleicher als sonst, und der Test wird unsicher.
• ±1 statt Ersetzen: Passt das unterste Bit nicht, wird der Wert zufällig um 1 erhöht oder erniedrigt, statt das Bit zu setzen. Aus 208 kann dann auch 207 werden, und die Paare gleichen sich nicht mehr an. Andere Tests finden auch das, aber schwerer.
• Gar nicht mehr Bits ersetzen, sondern ein anderes Verfahren, das sich nach dem richtet, was das Auge sieht. Darum geht es im Rest dieser Seite.

7. Farbklassen

Das LSB-Verfahren lässt sich auch anders beschreiben. Alle Farben, die sich nur im untersten Bit jedes Kanals unterscheiden, bilden eine Farbklasse: zum Beispiel die 8 Farben mit Rot 208 oder 209, Grün 148 oder 149 und Blau 36 oder 37. Innerhalb einer Klasse sieht keine Farbe anders aus als die anderen. Ein Pixel darf also jede Farbe seiner Klasse annehmen, und welche es annimmt, trägt die Botschaft: 8 Möglichkeiten sind 3 Bits.

Im RGB-Würfel mit 256 × 256 × 256 Farben sind diese Klassen kleine Würfel mit der Kantenlänge 2. Warum nicht 3? Dann hat eine Klasse 3 · 3 · 3 = 27 Farben, und jedes Pixel kann eine von 27 Möglichkeiten tragen. Das sind \( \log_2 27 \approx 4{,}75 \) Bits, keine ganze Zahl. Ersetzen kann man da nichts mehr. Man braucht eine andere Idee.

Eine Zahl mit wechselnder Basis

Du kennst diese Idee von der Uhr. 3725 Sekunden sind 1 Stunde, 2 Minuten und 5 Sekunden: 3725 durch 60 ist 62, Rest 5; 62 durch 60 ist 1, Rest 2; übrig bleibt 1. Die Sekunden und Minuten haben die Basis 60, die Stunden 24. Jede Stelle hat ihre eigene Basis.

Genauso wird die Botschaft eine einzige große Zahl \( P \), und jedes Pixel eine Stelle. Seine Basis ist die Größe \( s \) seiner Klasse:

1. Die Ziffer für das nächste Pixel ist \( P \bmod s \), der Rest beim Teilen. Das Pixel bekommt die Farbe mit dieser Nummer in seiner Klasse.
2. Weiter geht es mit \( P \,//\, s \), dem Ergebnis der Division ohne Rest.
3. Das wiederholt sich, bis \( P \) null ist.

Zum Lesen geht man rückwärts, vom letzten benutzten Pixel bis zum ersten: \( P \) beginnt bei 0, und für jedes Pixel wird \( P = P \cdot s + \text{Nummer seiner Farbe} \). Das ist dasselbe wie »1 Stunde ist 60 Minuten, plus 2 Minuten, mal 60, plus 5 Sekunden«. Dafür muss der Leser wissen, wie viele Pixel benutzt wurden; diese Zahl steht vorher in den untersten Bits der ersten 11 Pixel, 33 Bits.

Ruby und Python rechnen mit beliebig großen ganzen Zahlen, ohne Bibliothek: Eine Botschaft mit 20.000 Bytes ist eine Zahl mit 160.000 Bits, und % und // (in Ruby divmod) funktionieren genauso wie mit kleinen Zahlen. Je größer die Zahl, desto länger dauert jede Division; für ein paar Sätze merkst du davon nichts.

Mit BoxClasses(2) ist das wieder das LSB-Verfahren, 3 Bits pro Pixel. Mit 3 sind es 4,75 Bits, mit 5 schon fast 7. So lässt sich die Menge, die man versteckt, fein einstellen, nicht nur in Schritten von ganzen Bits.

8. Am Test vorbei

Mit Würfeln der Breite 2 ist das Verfahren wieder das LSB-Verfahren, und der Chi-Quadrat-Test findet es wie vorher. Mit der Breite 3 ändert sich etwas, das man nicht sofort sieht: Jetzt kann ein Kanal nicht mehr nur das unterste Bit wechseln, sondern einen von drei Werten annehmen. Was macht der Test daraus?

image = ChunkyPNG::Image.from_file('strandhaeuser.png')
hidden = embed(image, File.read('spec-gif89a.txt')[0, 20000], BoxClasses.new(3))
puts chi_square(hidden, 0, 40)

image = Image.open('strandhaeuser.png')
hidden = embed(image, open('spec-gif89a.txt').read()[:20000], BoxClasses(3))
print(chi_square(hidden, 0, 40))

Die Botschaft füllt die obersten gut 70 Zeilen, und trotzdem schlägt der Test nicht an. Er vergleicht die Paare 2k und 2k+1, weil das LSB-Verfahren genau diese beiden Werte gleich häufig macht. Würfel der Breite 3 machen aber Gruppen von drei Werten gleich häufig: 0, 1 und 2, dann 3, 4 und 5. Die Paare des Tests liegen quer dazu, 2 und 3 etwa gehören zu verschiedenen Gruppen. So geht es mit jeder ungeraden Breite. Bei der Breite 4 dagegen liegt jedes Paar in einer Gruppe, und der Test findet die Botschaft wieder.

Jede Farbe einer Gruppe kommt nach dem Verstecken gleich oft vor. Bei der Breite 4 liegen in jeder Gruppe zwei ganze Paare, also werden auch die Paare gleich. Bei der Breite 3 schneiden die Gruppen durch die Paare hindurch: 2 und 3, 8 und 9 liegen in verschiedenen Gruppen.

Der Test muss also wissen, wonach er sucht. Er lässt sich leicht verallgemeinern: Statt der Paare nimmt er Gruppen von width Werten, die Werte \( k \cdot w \) bis \( k \cdot w + w - 1 \). Für jede Gruppe ist \( e \) der Durchschnitt ihrer Zählungen, und sie trägt \( \sum (c - e)^2 / e \) bei, über ihre \( w \) Zählungen \( c \). Geteilt durch \( w - 1 \) ergibt eine Gruppe, die nur der Zufall gleichmacht, wieder etwa 1. Mit \( w = 2 \) ist das genau der Test von vorhin.

Für den versteckten Text mit der Breite 3 ergibt der Test mit width 3 jetzt etwa 1. Wer etwas verstecken will, darf sich nicht darauf verlassen, dass der andere sein Verfahren nicht kennt; ein paar Breiten auszuprobieren dauert nur Sekunden. In der Kryptographie heißt das Prinzip von Kerckhoffs: Ein Verfahren muss sicher bleiben, auch wenn der Gegner alles darüber weiß außer dem Schlüssel.

Das zweite Fundstück

Hol dir noch ein Bild:

wget https://workspace.hackschule.de/steganography/fundstueck-2.png

Darin steckt eine Botschaft, versteckt mit Würfeln, aber welche Breite sie haben, steht nirgends. Probier mit deinem Test die Breiten 2 bis 8 für die Zeilen 0 bis 40 aus:

image = ChunkyPNG::Image.from_file('fundstueck-2.png')
(2..8).each { |width| puts "#{width}: #{chi_square(image, 0, 40, width).round(1)}" }

image = Image.open('fundstueck-2.png')
for width in range(2, 9):
    print(width, round(chi_square(image, 0, 40, width), 1))

9. Wie geht es weiter?

• Mit Schlüssel: Wähle die Pixel nicht der Reihe nach, sondern in einer Reihenfolge, die ein Zufallsgenerator mit einem geheimen Startwert festlegt. Wer den Schlüssel nicht kennt, weiß nicht einmal, welche Pixel er untersuchen soll.
• Ohne feste Breite: Der Test mit Gruppen findet Würfel jeder Breite, weil alle Pixel dieselben Klassen haben. Was, wenn ein Schlüssel für jedes Pixel eine andere Einteilung wählt?
• Andere Farbräume: Ein Würfel in RGB ist nicht die beste Farbklasse, denn das Auge sieht RGB nicht gleichmäßig: Unterschiede in der Helligkeit sieht es viel genauer als im Farbton. Im Handbuch unter Farbräume stehen Farbräume wie CIELab und OKLab, in denen gleiche Abstände ungefähr gleich verschieden aussehen. Schreib eine Klasseneinteilung mit Quadern in einem davon, mit mehr Stufen für die Helligkeit als für die Farbe; embed und extract brauchen von ihr nur cell und members.
• Töne: Eine WAV-Datei ist eine Liste von Zahlen wie ein Bild, nur in der Zeit. Das unterste Bit eines Tons hört man genauso wenig.
• JPEG: In einem JPEG gibt es keine Pixel, die man ändern könnte, nur die Koeffizienten der DCT aus Ein JPEG-Decoder. Verfahren wie F5 verstecken ihre Bits dort.