Dienstag, 16. April 2013

Digitale visuelle Kryptographie

Das erste Mal, als ich mit visueller "Kryptographie" zu tun hatte, war ich noch ein kleines Kind: Ich hatte ein Buch, in dem Man gewisse Textzeilen nur gut lesen konnte, wenn man eine rote Folie davor hielt. Die Zeilen waren in einem schwachen grau vor einem roten Zahlen-/Zeichenmeer geschrieben. Mit großer Anstrenung konnte man den Text trotzdem lesen, aber mit der Folie, die das rote Zahlenmeer verschwinden ließ, war es wesentlich besser.

Natürlich ist das keine echte Kryptographie. Dennoch hat es rein von der Mechanik viel mit der klassischen visuellen Kryptographie gemeinsam:



Man schiebt immer noch aufeinander, diesmal aber bedruckte Folien, die man dazu auch noch sehr genau ausrichten muss, um zu sehen, was verschlüsselt wurde, sogar wirklich verschlüsselt und das sehr sicher. Ein sogenanntes One-Time-Pad. Hat man nur einen der beiden Teile, ist es unmöglich auf den "Klartext" zu schließen (vorausgesetzt man hatte halbwegs gute Zufallszahlen beim Verschlüsseln). Wie das Verschlüsseln genau funktioniert will ich hier nicht erklären. Diese Webseite zeigt das ziemlich gut und wer selbst ein paar Bilder erstellen möchte, kann das hier ziemlich einfach tun.

Zum Entschlüsseln dieser Bilder, braucht man nichts weiter als eine Person, die Folien aufeinander schieben kann. Keinen PC oder Taschenrechner. Das ist der große Vorteil.


Genau diesen Vorteil werde ich nun allerdings wieder nehmen. Ich wollte eine Methode entwickeln um farbige Bilder am PC visuell zu verschlüsseln. Kein AES, Blowfish oder wie sie alle heißen, ich wollte, dass man das Ergebnis sehen kann und mit genau diesem sichtbaren Ergebnis auch arbeiten, es also wieder entschlüsseln kann.



Farbige Bilder sind nun schon allein in sofern schwieriger zu handhaben, da es (bei RGB-kodierten Bildern) drei zu verschlüsselnde Werte pro Bildpunkt gibt: R, G und B, also rot, grün und blau.

Meine erste Idee war eine recht simple und kryptographisch auch sehr fragwürdige:
Gehe das Bild von links nach rechts, von oben nach unten, Pixel für Pixel durch und hole dir die Werte der einzelnen Farben. Mache das gleiche mit dem darauffolgenden Pixel. Verrechne nun die jeweils passenden Werte binär mit XOR (⊻), also R1 ⊻ R2, G1 ⊻ G2 und B1 ⊻ B2 und speichere das Ergebnis in den aktuellen Pixel.

Hier eine Grafik zur Veranschaulichung:


Die Grafik zeigt auch, was passiert, wenn in der aktuellen Reihe kein Pixel mehr übrig ist: es geht in der nächsten Reihe weiter, bis zum Ende.
Was passiert nun aber beim letzten Pixel? Der letzte Pixel hat keinen weiteren Pixel. Hier kommt das Fünkchen Kryptographie ins Spiel. Ich erfinde einen letzten Pixel. Dadurch dass er nicht gespeichert wird, eignet er sich als Passwort, denn nur mit ihm lassen sich die Farben aller vorherigen Pixel korrekt wiederherstellen. Geht man von 8-Bit pro Farbe (R, G oder B) aus, können diese jeweils die Werte 0 bis 255 annehmen. Dadurch ergeben sich 256³, also 16.777.216 mögliche Passwörter. Schon mal gar nicht so schlecht. 

Hier gerade gezeigtes Katzenbild mit dem Passwort (35,68,201):


Die Form der Katze ist weiterhin gut zu erkennen und auch die Relationen der Farben zueinander sind noch vollständig erhalten (die XOR-Operation hebt sie sogar regelrecht hervor - größere Farbunterschiede zum nächsten Pixel erscheinen heller). Mit einem gut geratenen Passwort kann man das Bild immerhin etwas dem Original näher bringen. Hier mit (25, 50, 250) versucht:


Zum sicheren Verschlüsseln eines Bildes taugt dieses Verfahren also nur bedingt, eher als optischer Effekt. Es lassen sich lediglich die Originalfarben verschleiern.

Also zurück zum Bekannten: Das One-Time-Pad. Beim One-Time-Pad ist das Passwort immer exakt genauso lang wie der zu verschlüsselnde Text. Zunächst versuchte ich also jeden Pixel mit einer Zahl zu verschlüsseln. Obiges Katzenbild hat die Ausmaße 400x267 Pixel. Insgesamt sind das 106.800 Pixel. Für jedes dieser ließ ich nun eine Zufallszahl (Z) generieren und verrechnete sie mit den drei Farbwerten. Diesmal addierte ich: R1+Z, G1+Z und B1+Z. Das Ergebnis sieht schon etwas vielversprechender aus:


Als Passwort hat man dann ein schwarz-weiß-Bild (256 Grautöne) mit selbiger Größe:



Schaut man sich das verschlüsselte Bild allerdings genauer an, kann man sehr leicht Umrisse erkennen. Manche Teile scheinen aus eher schwarz-weißem Rauschen zu bestehen, andere sind eher farbig. 
Das Problem ist: Dadurch, dass ich für jeden Pixel nur eine Zufallszahl genommen habe, verschlüssele ich eigentlich nicht die Farben, sondern nur die Helligkeit der Pixel. Das ist kryptographisch wieder sehr fragwürdig, da sich so der Zufall (Passwortbild) wieder teilweise herausrechnen lässt und der Passwortschutz damit nichtig ist...

Will man also ein so verschlüsseltes Bild knacken kann man folgendes tun: Nehme von jedem Pixel den rot-Wert und reduziere ihn um sich selbst. Reduziere dann die beiden anderen Farbwerte ebenfalls um diesen Wert. 
Bsp: (45, 76, 201) -> (0, 29, 156). So kann man viel vom vorher reingerechneten Passwort wieder eliminieren.
Auf das verschlüsselte Bild angewendet:


Das sieht schon stark nach unserer Katze aus! Man kann die Methode natürlich auch mit dem grün- oder blau-Wert machen:

blau entfernt

grün entfernt

Zwar bekommt man so definitiv nicht das Originalbild zurück, doch es reicht aus um teilweise auch sehr feine Strukturen erkennen zu können. Sicher verschlüsselt geht jedenfalls anders.


Die logische Lösung wäre nun, einfach 3 Zufallszahlen für jeden Pixel zu verwenden. Genau das werde ich am Ende auch tun, denn das ist wirklich zu 100% kryptographisch sicher, wenn man gute Zufallszahlen hat.

Dennoch möchte ich noch zeigen, was passiert, wenn man zuerst die ganz oben gezeigte XOR-Schiebe-"Verschlüsselung" und anschließend das Helligkeits-One-Time-Pad anwendet.
Hier mal das Katzenbild mit Passwort (35,68,201) und den 106.800 Zufallszahlen:


Versucht man dieses Bild auf bekannte Weise zu knacken erhält man Folgendes:


Hier ist es schon wesentlich schwieriger ordentliche Strukturen zu erkennen. Auch ein Zurück-XOR-Schieben mit geratenem Passwort würde wenig daran ändern, wenn nicht sogar das Bild noch unkenntlicher machen. Aber auch diese Verbund-Methode ist natürlich kryptographisch nicht sicher.

Richtig sicher ist nur das hier:

Das verschlüsselte Bild

320.400 Zufallszahlen sind nun mit dem Bild verrechnet. Jegliche Strukturen sind aufgehoben. Das Passwortbild ist nicht mehr vom verschlüsselten Bild unterscheidbar:

Passwortbild

Ein Hackversuch nach oben genanntem Schema läuft daher auch komplett ins Leere:



Selbstverständlich kann man auch alle 3 Methoden kombinieren (ist dennoch nicht sicherer als die letzte Methode alleine), aber so paranoid ist schätze ich niemand. Das ist dann wohl eher was für die Rätselfreunde unter uns ;)


 □

Kommentare:

  1. Beindruckend, da steckt eine Menge Arbeit und Denkaufwand dahinter. Hast du das im Rahmen eines Uni-Projektes o.ä. gemacht oder Just 4 Fun?

    Ich habe noch eine Verständnisfrage dazu.
    Die Zufallszahlen, mit denen du die Farbwerte der einzelnen Pixel verrechnest - müssen Ganzzahlen zwischen 0 und 255 sein, damit am Ende das Passwortbild entstehen kann, richtig? (erste Methode mit einem Z)

    AntwortenLöschen
    Antworten
    1. Danke, wenn ich ehrlich bin war es gar nicht mal so viel Arbeit. Habs just 4 fun gemacht, wollte sehen wie es aussieht und ob es funktionieren kann.

      Tatsächlich braucht jede der Verschlüsselungsmethoden jeweils nur an die 25 Zeilen Python-Code. Es gibt eine geniale Bibliothek zum bearbeiten von Bildern, die hat es mir sehr erleichtert (http://www.pythonware.com/products/pil/). Ist natürlich nicht unbedingt der performanteste Code, aber er kann noch ein paar Sachen , die ich im Artikel nicht erwähnt habe. Z.B. die Verschlüsselung mit einem kurzen Passwort, das dann als Seed für einen Pseudo-Random-Generator dient. Der verwendete PRNG (http://de.wikipedia.org/wiki/Mersenne-Twister) ist aber eigentlich nicht für kryptographische Zwecke geeignet, da müsste ich noch einen besseren suchen.

      Zu deiner Frage:
      Ich generiere tatsächlich Zufallszahlen zwischen 0 und 255. Im Grunde wäre es aber egal, in welchen die Grenzen ich die Zahlen generiere, ich rechne dann sowieso Modulo 256, dann ist es in den benötigten Grenzen. Ohne Modulo würden ja auch beim Addieren der Werte später Zahlen größer 255 herauskommen, oder beim wieder entschlüsseln negative Werte. Hab im Artikel bewusst Beispiele gewählt, bei denen das nicht passiert.

      Löschen