Irgendwo in Deutschland, im Mai 2007. Harry Heinzelmann nimmt als einer der ersten Kunden seine neue Bargeldkarte in der Bank entgegen – sehr begierig, denn die Einführung des neuen Systems hat sich lange hingezogen, weil Einzelhändler und Automatenaufsteller nur mühsam von seinen Vorzügen zu überzeugen waren; und die Karte erfüllt ein dringendes Bedürfnis Harrys.
Seit der Währungsumstellung vor einigen Jahren nehmen die Zigarettenautomaten in Harrys Reichweite keine Münzen mehr an. Statt sie aufwendig auf die neuen Euro-Geldstücke umzurüsten und mit noch mehr Stahlblech gegen Beraubung abzusichern, haben die Aufsteller ihre Geräte gleich einen Schritt weiter modernisiert. Nun muß der Kunde eine Plastikkarte einschieben; je nachdem, ob es eine Scheck-, Kredit- oder Guthabenkarte ist, bucht der Automat den Preis der Schachtel vom Bankkonto des Kunden ab oder direkt von der Karte; deren Speicher enthält nach der Transaktion das verbleibende Guthaben.
Dummerweise nehmen die Automaten keine Guthabenkarten mehr an, seit vor kurzem gefälschte Exemplare in großen Mengen auf dem Markt aufgetaucht sind. Es bleibt also nur noch die gute alte Scheckkarte. Die ist zwar nicht gerade fälschungssicher, aber immerhin läßt sich jede Transaktion zumindest hinterher im Kontoauszug nachvollziehen.
Das schätzt Harry nun überhaupt nicht, weil seine Frau jetzt jeden Monat durch Nachzählen den Zigarettenkonsum ihres Ehemannes mit seinen Beteuerungen vergleichen kann. Dagegen ist die Guthabenkarte neuen Typs wieder anonym wie Bargeld. Bei der Übergabe versichert ihm der Bankangestellte, der Reinfall mit den Karten alten Typs könne sich unmöglich wiederholen. Die neue Version sei nämlich smart.
"Was heißt das?"
"Intelligent."
"Wie? Kann die mit mir reden?"
"Mit Ihnen nicht. Aber zum Beispiel mit dem Zigarettenautomaten."
"Und was erzählen sich die beiden?"
"Na ja, wenn Sie die Karte in den Automaten geschoben und Ihre Zigarettensorte gewählt haben, sagt der Automat zur Karte: ,Gib mir 2,30 Euro.' Diese antwortet: ,Soviel habe ich noch.' Daraufhin zeigt Ihnen der Automat auf seinem Bildschirm den Gesamtbetrag – Sie könnten ja mehr als eine Ware angefordert haben – und bittet Sie um Bestätigung. Sie drücken den grünen Knopf und geben Ihre Geheimzahl ein, die Smartcard prüft sie nach und erzählt dann dem Automaten eine lange Geschichte."
"Was für eine Geschichte?"
"Eine Kette von Buchstaben und Zahlen, die man nicht entziffern kann. Aber für den Automaten ist es die Nachricht: ,Hier hast du 2,30 Euro, die kannst du bei unserer Bank einlösen. Du kannst nachprüfen, daß ich echt bin; auch die Bank, der du diesen Text vorlegst, kann nicht das Gegenteil behaupten, und du kannst den Betrag nicht ändern, ohne daß es der Bank auffällt.' Für den Text, den die Karte dem Automaten übermittelt, gibt es echtes Geld von der Bank; aber niemand kann ihn nachmachen. Dazu ist nur die Karte fähig, und dafür braucht sie ihre Intelligenz."
"Das heißt, die Bank ist abgesichert."
"Das ist ja auch das Wichtigste. Wir können kein Geld mehr durch gefälschte Guthabenkarten verlieren."
"Und wie bin ich abgesichert? Ich muß doch dem Automaten meine Geheimzahl verraten."
Böse Erfahrungen mit Geldautomaten haben Harry gelehrt, daß Sicherheit eine zweiseitige Sache ist: Beide Partner eines Geldgeschäfts müssen sich absichern, nicht nur die Bank – oder wer immer den Automaten besitzt (Spektrum der Wissenschaft, Mai 1995, Seite 46). Aber für derlei Fragen ist der Bankangestellte bestens präpariert. "Wenn Sie da Sorgen haben, können wir Ihnen für eine geringe Zusatzgebühr die Hochsicherheits-Geldkarte anbieten. Die verlangt keine Geheimzahl, sondern stellt Ihnen Fragen, die Sie richtig beantworten müssen – das ist das sogenannte Challenge-Response-Protokoll. Es schadet nichts, daß das Frage-Antwort-Spiel über den Automaten abläuft; denn wenn er irgend etwas an der Kommunikation zwischen Ihnen und der Karte verfälscht, wird die Nachprüfung scheitern; und es nützt ihm nichts, wenn er Protokoll führt, denn beim nächsten Mal stellt die Karte andere Fragen. Nehmen Sie aber besser einen Taschenrechner mit zum Automaten. Sie müssen die Antwort mit Hilfe Ihrer Geheimzahl aus der Frage errechnen, und die meisten Leute können das nicht im Kopf" (Spektrum der Wissenschaft, Februar 1997, Seite 10).
Das ist Harry nun wirklich zu unbequem, und man einigt sich schließlich auf einen dritten Typ Geldkarte. Auf dem intelligenten Chip ist diesmal eine Serie von Transaktionsnummern eingespeichert, Geheimzahlen für den einmaligen Gebrauch. Harry bekommt die Liste dieser Nummern auf Papier mit und ist nun endgültig beruhigt.
Da er sich den Bargeldvorrat auf seiner Karte nicht sorgfältig merkt, fällt ihm erst nach ein paar Wochen auf, daß er seine Karte sehr häufig mit frischem Geld nachladen muß. Die Karte führt jedoch kein Protokoll über seine Ausgaben – so hat er es bei der Bestellung ausdrücklich verlangt; schließlich legt er Wert auf Anonymität. Auch der Text, den die Karte an den Automaten übermittelt, enthält keinen Hinweis auf ihre Identität.
Erst nach mühsamen Recherchen wird klar, daß ein Automat auf raffinierte Weise umprogrammiert worden ist: Für eine Schachtel Zigaretten verlangt er 23 Euro von der Karte, zeigt aber auf seinem Bildschirm nach wie vor 2,30 Euro als freizugebenden Betrag an. Harry hat keine Chance, etwas zu merken, und die Karte keinen Anlaß, nicht auszuzahlen.

Vertrauliche Kommunikation mit natürlichen Mitteln

Selbstverständlich wird das geschilderte Szenario sich so nie abspielen; das Problem ist ja erkannt. Ungesichert ist Zahlen mit der Geldkarte so, als reichte man dem Kassierer den Geldbeutel und stellte ihm frei, sich zu bedienen. Aber wie ist es zu lösen?
Eigentlich ist das ein Standardproblem der Kryptographie. Zwei Parteien wollen vertrauensvoll miteinander kommunizieren, nämlich Harry und seine Smartcard, die in diesem Zusammenhang Sally heißen möge. Moni Naor, Benny Pinkas und Adi Shamir von der Abteilung für angewandte Mathematik und Informatik des Weizmann-Instituts in Rehovot (Israel), über deren Arbeit hier berichtet wird, haben die Namen nicht nur nach den Anfangsbuchstaben von human und smartcard gewählt, sondern auch in offensichtlicher Anspielung auf den Film "Harry und Sally", der die lebenslangen Kommunikationswirren seiner Titelhelden zum Gegenstand hat. Shamir ist als einer der Schöpfer des kryptographischen RSA-Algorithmus und als Urheber eines heroisch gescheiterten Angriffs auf den Data Encryption Standard (DES) bekannt geworden (Spektrum der Wissenschaft, Oktober 1979, Seite 92, und Mai 1993, Seite 19).
Harry und Sally wollen sich also vergewissern, daß der jeweilige Kommunikationspartner der ist, der zu sein er behauptet, und daß seine Nachricht nicht verfälscht worden ist. Sie können das nur über einen Kanal tun, über den eine dritte Partei namens Peggy verfügt; im Beispiel ist das der Zigarettenautomat samt Tastatur und Bildschirm. Peggy kann mitlesen und Nachrichten nach Belieben manipulieren.
Aber das hilft ihr nicht, wenn Harry und Sally ein Geheimnis haben, an dem Peggy keinen Anteil hat. Dann verschlüsselt der Absender (zum Beispiel Sally) die Nachricht mit Hilfe des Geheimnisses, der Empfänger (Harry) macht sie damit wieder lesbar, jeder Manipulationsversuch Peggys würde die Nachricht unentzifferbar machen und dadurch dem Empfänger unweigerlich auffallen, und schließlich kann Peggy auch durch ausgiebiges Zuhören das Geheimnis nicht erschließen.
Ver- und Entschlüsseln sind jedoch mit Rechenoperationen verbunden - für einen Computer oder den Chip auf einer Smartcard ein Kinderspiel, aber für einen Menschen ohne Hilfsmittel kaum oder gar nicht zu erledigen. Selbst die einfachste Form ist mühsame Schreibarbeit, wenn auch so gut wie kein Denken erforderlich ist: Man wende die Operation "ausschließliches Oder" jeweils auf Paare von Bits an (bitwise exclusive OR oder kurz bitwise XOR).
Klartext und geheimer Schlüssel seien gleich lang und mögen in Form von Bitketten (Folgen aus Nullen und Einsen) vorliegen. Man schreibe beide untereinander und in eine dritte Zeile immer dann eine Null, wenn darüber zwei gleiche Ziffern stehen, sonst eine Eins. Dadurch ergibt sich der Chiffretext. Der Empfänger gewinnt daraus den Klartext zurück, indem er dasselbe Verfahren auf Chiffretext und Schlüssel anwendet. Wenn Absender und Empfänger als Schlüssel eine zufällige Folge verwenden, hat der Chiffretext ebenfalls alle Eigenschaften einer zufälligen Folge; also kann ein Lauscher keine Information aus ihm ziehen.
Nun ist der Mensch zwar von Natur aus ein schlechter (und langsamer) Rechner. Selbst die stupide Anwendung des bitwise XOR würde ihn viel Zeit kosten. Dafür bewältigt er mit Leichtigkeit Informationsverarbeitungsaufgaben, die Computern heute noch zu schaffen machen: Sehen zum Beispiel. Das liefert die Motivation für die zentrale Idee von Naor und seinen Kollegen: Man präsentiere dem menschlichen Empfänger der heiklen Nachricht Chiffretext und Schlüssel als Bilder und lasse sein Sehsystem die XOR-Operation elegant erledigen. Der so rekonstruierte Klartext ist dann ebenfalls ein Bild.
Man denke zunächst an ein Bild, das nur Schwarz und Weiß, aber keine Grauwerte enthält. Der Inhalt kann so banal sein wie die Preisangabe 2,30 Euro, die Sally unverfälschbar an Harry übermitteln möchte, oder so individuell wie die Strichzeichnung eines Gesichts, das Harry auf den ersten Blick wiedererkennt. Damit würde sich Sally sozusagen persönlich zu erkennen geben. Das Schwarzweißbild ist, wie auf einem Fernseh- oder Computerbildschirm üblich, in kleine Quadrate (Pixel) aufgelöst, die jedes für sich entweder schwarz oder weiß sind.
Beim Verschlüsseln werden aus jedem Pixel vier Subpixel: 2×2 Quadratchen mit der halben Seitenlänge. Der Schlüssel besteht aus genauso vielen Pixeln wie das Klartextbild. Von den vier Subpixeln sind dabei stets zwei weiß und zwei schwarz. Aber welche? Es gibt sechs Möglichkeiten, von vier Quadratchen genau zwei schwarz zu machen (Bild 1). Welche von ihnen gewählt wird, entscheidet für jedes Pixel einzeln der Zufall. Aus der Entfernung betrachtet ergibt sich insgesamt ein gleichmäßig graues Bild, denn genau die Hälfte der Fläche ist von schwarzer Farbe bedeckt, und Schwarz und Weiß sind sehr gleichmäßig verteilt.
Aus Klartext und Schlüssel ergibt der Chiffretext auf folgende Weise: Ist das Klartextpixel weiß, so wird das zugehörige (aus vier Subpixeln bestehende) Pixel des Schlüssels unverändert in den Chiffretext übernommen; ist der Klartext an dieser Stelle dagegen schwarz, so werden Schwarz und Weiß des Schlüsselpixels vertauscht. Im Ergebnis ist der Chiffretext wieder ein Bild, das aus lauter halb-schwarzen Pixeln besteht. Es sieht auf die Entfernung genau so gleichmäßig grau aus wie der Schlüssel und unterscheidet sich auch bei näherer Betrachtung nicht grundsätzlich von diesem: Die Anordnung von Schwarz und Weiß in jedem Pixel ist von einer zufallsbestimmten Anordnung nicht zu unterscheiden.
Harry trägt den Schlüssel auf eine transparente Folie (wie man sie für Overhead-Projektoren verwendet) aufgedruckt mit sich herum. Sally, die Smartcard, sendet den Chiffretext an Peggy, den Zigarettenautomaten, mit der Aufforderung, ihn unverändert auf den Bildschirm zu bringen. Harry legt die Folie auf den Schirm; Löcher in der Folie und Führungsstifte an den Ecken des Bildschirms helfen ihm, sie paßgenau auszurichten – und wie durch Zauberei entsteht aus zwei langweilig grauen Feldern das Klartextbild wieder (Bild 2).
Wie kommt das? Wo im Klartextbild ein weißes Pixel war, kommen in den Subpixeln von Chiffretext und Schlüssel Schwarz auf Schwarz und Weiß auf Weiß zu liegen. Aus der Hälfte der Pixelfläche dringt also (weil dort der Bildschirm weiß und die Folie transparent ist) Licht in das Auge des Betrachters, und aus der Entfernung erscheint die entsprechende Stelle grau. Bei einem schwarzen Klartextpixel trifft dagegen Weiß auf Schwarz und Schwarz auf Weiß; also kommt an dieser Stelle gar kein Licht durch, weswegen sie schwarz erscheint. Aus einem schwarzweißen Bild wird im Endeffekt ein schwarzgraues; aber das hindert das menschliche Sehsystem nicht sonderlich beim Erkennen, da es ohnehin Unterschiede in der Gesamthelligkeit automatisch kompensiert.
In der Sprache der Aussagenlogik formuliert, realisiert das Aufeinanderlegen von Schlüssel und Chiffretext nicht das ausschließliche Oder, wie es eigentlich richtig wäre, sondern das gewöhnliche Oder: Ein Subpixel erscheint schon dann schwarz, wenn es im Schlüssel oder im Chiffretext schwarz ist – oder auch in beiden zugleich. Erst durch die Aufteilung in Subpixel kommt doch noch der Effekt des ausschließlichen Oder zustande.
Im Prinzip würde das Verfahren auch noch funktionieren, wenn jedes Pixel in zwei statt vier Subpixel zerlegt würde. Dann gäbe es zwar nur noch zwei Möglichkeiten, Schwarz und Weiß auf die Subpixel zu verteilen, aber das wäre ausreichend. Naor und seine Kollegen bevorzugen die Vierteilung, weil dann die kleinen Pixelchen wieder quadratisch gewählt werden können.
Außerdem bringt der Zusatzaufwand einen gewissen Zugewinn an Sicherheit. Wenn Peggy den Chiffretext verfälschen möchte, tut sie gut daran, sich an das Schema zu halten, daß genau zwei von vier Subpixeln schwarz sind; denn jede Abweichung würde, wenn sie nicht nur sehr sporadisch vorkommt, als weißer beziehungsweise schwarzer Fleck auf dem (unbedeckten) Bildschirm ins Auge springen. Wenn sie des weiteren nicht sehr genau weiß, wie sie den Chiffretext verfälschen soll, werden sich in der Kombination von Schlüssel und Chiffretext häufig dunkelgraue Pixel finden (drei von vier Subpixeln sind schwarz). Daran würde Harry sofort erkennen, daß Peggy versucht, ihn hereinzulegen.
Wie bei dieser Art der Verschlüsselung üblich, kann Peggy den Chiffretext zwar nach beliebigen Verfahren analysieren; Sally stellt ihn ihr ja zur Wiedergabe auf dem Bildschirm zur Verfügung. Aber Peggy hat nichts davon, denn der Chiffretext hat alle Merkmale einer Zufallsfolge.
Sie ist allerdings in einer besseren Situation als ein Lauscher in der Leitung, der den Inhalt einer vertraulichen Kommunikation ermitteln möchte: Peggy weiß, was auf dem Bild ist, nämlich die Preisangabe, die sie soeben erst Sally mitgeteilt hat. Also rekonstruiert sie aus Chiffretext und bekanntem Klartext den Schlüssel mit einer bitweisen XOR-Operation, die ihr als Computer leicht von der Hand geht, verschlüsselt mit dem so ergaunerten Schlüssel einen Klartext mit einer falschen Preisangabe, und wieder fällt Harry darauf herein.
Dagegen hilft es, das Bild mit einem wiedererkennbaren Gesicht zu versehen, das zwar Harry, nicht aber Peggy geläufig ist. Außerdem kann Sally den Teil der Information, den Peggy kennt, nach Belieben auf der Bildfläche verschieben; Harry ist durch ein paar Worte auf der Folie vorab instruiert worden, wo im Bild die Preisangabe steht. So weiß Peggy nicht, an welcher Stelle sich die Information befindet, die sie zur Rekonstruktion des Schlüssels löschen müßte.
Erst wenn Peggy zahlreiche Transaktionen mit ein und derselben Smartcard aufzeichnet, gewinnt sie ein auf die Dauer immer detaillierteres Bild von dem geheimen Schlüssel. Je nach Zigarettenkonsum sollte sich Harry also alle paar Wochen bis Monate eine neue Folie zulegen. Dazu muß er die Smartcard nicht erneuern; es genügt, wenn er sie in seinen (vertrauenswürdigen) Heimcomputer steckt und um einen neuen Schlüssel bittet. An Hardware braucht er sonst nichts weiter als einen Drucker, der auch Folien verarbeitet.

Erweiterungen

Das Prinzip der visuellen Kryptographie ist nicht auf die Kommunikation mit suspekten Geldannahmestellen (points of sale, POS) beschränkt. Es ist überall dort einsetzbar, wo für die Annahme der Nachricht ein vertrauenswürdiger Computer nicht zur Verfügung steht. So könnte etwa der Repräsentant einer Firma in einem Land, in dem man niemandem traut, von seiner Zentrale eine – sorgfältig zu hütende – Schlüsselfolie mitbekommen und dann vertrauliche Nachrichten per Telefax empfangen. Ein Mithörer in der Leitung oder jeder, der das empfangene Fax zu Gesicht bekommt, sieht nicht mehr als ein langweiliges Graufeld. Erst mit der darübergelegten Folie kommt die Nachricht zum Vorschein – vorausgesetzt, das Faxgerät arbeitet präzise genug.
Häufig soll eine vertrauliche Nachricht nur dann lesbar sein, wenn mehrere Personen zugleich ihre Schlüssel einsetzen, vergleichbar einem Tresor, der nur mit mehreren Schlüsseln zugleich zu öffnen ist. Auch das läßt sich mit Folien bewerkstelligen. Wenn etwa eine Nachricht vier Personen, die sich zusammentun, zugänglich sein soll, aber nicht drei von ihnen, würde jede von den vieren eine Folie ausgehändigt bekommen, die anstelle der Klartextpixel wieder Quadrate aus Subpixeln enthält – diesmal sind es 3×3 Stück. Von diesen neun Feldern sind stets fünf schwarz und die restlichen vier weiß, und ihre Verteilung ist anscheinend vom Zufall bestimmt. Alle vier Folien sind gleichmäßig grau; das gilt auch noch, wenn man zwei oder drei von ihnen übereinanderlegt. Erst beim Auflegen der vierten Folie erscheint dunkelgrau auf schwarz das Klarbild (Kasten auf dieser Seite). Man käme auch mit acht statt neun Subpixeln aus, hätte dann aber wieder das Problem der ungleichmäßigen Anordnung.
Sogar Bilder, die nicht nur Schwarz und Weiß, sondern auch Graustufen enthalten, lassen sich auf elegantem Wege auf zwei Folien verteilen, so daß jede einzelne keine brauchbare Information enthält. Die Pixel bestehen in diesem Falle aus Halbkreisen mit zufälliger Orientierung. Die Information steckt in dem Winkel, um den zusammengehörige Halbkreise auf beiden Folien gegeneinander verdreht sind: Für ein weißes Pixel liegen sie genau aufeinander, so daß ein kompletter Halbkreis transparent bleibt, für ein schwarzes Pixel sind sie um 180 Grad gegeneinander verdreht und bedecken dadurch gemeinsam den ganzen Kreis, und für die Grautöne liegt der Drehwinkel zwischen diesen beiden Extremen (Bild 3).
Schließlich kann sich Harry auch gegen Mißbrauch seiner Karte absichern, ohne zum Zigarettenholen jedesmal seinen Taschenrechner oder eine Liste von Transaktionsnummern mitbringen zu müssen. Um sich Sally gegenüber als rechtmäßiger Kartenbesitzer auszuweisen, genügt ebenfalls eine Folie, zur Not von derselben Art wie die beschriebene Schlüsselfolie. Besser funktioniert es, wenn sie mit farbigen Pixeln in – zum Beispiel – zehn verschiedenen Farben bedruckt ist. Sally kennt die Folie; sie sendet als Frage (challenge) einen fast schwarzen Bildschirm, auf dem nur ein paar weiße Pixel aufleuchten, und fragt nach den Farben der Pixel auf der darübergelegten Farbfolie. Harry hat keine Schwierigkeiten, als Antwort (response) die richtigen Farben einzugeben. Peggy hört auch diesmal mit, könnte sogar Frage und Antwort verfälschen – aber sie hat nichts davon, denn beim nächsten Mal fragt Sally nach der Farbe anderer, jedesmal zufällig ausgewählter Punkte. Da dauert es sehr lange, bis Peggy ausreichend Kenntnis von der Folie hat, um sich gegenüber Sally als Harry ausgeben zu können.<üb Kasten>Das Vier-Folien-PrinzipEin Pixelbild soll nur von vier (aber nicht von weniger) Berechtigten zusammen dekodierbar sein. Dann bedruckt man die Folien, die den Berechtigten ausgehändigt werden, wie folgt: Für ein weißes Pixel werden auf die vier Folien zum Beispiel die Subpixelmuster der oberen Reihe gedruckt, für ein schwarzes die der unteren Reihe. Legt man alle vier Folien übereinander, so bleibt für die Muster der oberen Reihe genau eines der neun Felder (im Beispiel das linke obere) durchsichtig, in der unteren Reihe dagegen gar keines. Das Klartextbild ist also nicht schwarz-weiß, sondern schwarz-dunkelgrau, aber gut erkennbar. Wenn man dagegen zwei dieser Muster – einerlei aus welcher Reihe – aufeinanderlegt, ergeben sich in jedem Fall sechs schwarze Felder, bei drei Mustern sieben. Zwei oder drei Folieninhaber können also aus dem Zusammenlegen ihrer Folien noch keine Information ziehen. Selbstverständlich wird nicht jedes Pixel nach diesem Schema verschlüsselt; sonst wäre das Klarbild aus einer einzigen Folie leicht rekonstruierbar. Vielmehr werden für jeden Bildpunkt die Plätze der Subpixel zufallsabhängig permutiert. Insbesondere kann das gemeinsame weiße Feld der oberen Reihe statt links oben an irgendeiner Stelle des 3×3-Quadrates liegen, und ein und dieselbe Belegung mit Subpixeln kann ebensogut von einem weißen wie von einem schwarzen Pixel stammen.Literaturhinweise
Geheimsprachen. Von Albrecht Beutelspacher. Beck, München 1997.
Visual Cryptography. Von Moni Naor und Adi Shamir in: Eurocrypt '94. Springer Lecture Notes in Computer Science 950, 1995, Seiten 1 bis 12. Im World Wide Web zu beziehen über http://www.wisdom.weizmann.ac.il/Papers/trs/CS94-14/abstract.html.
Visual Authentication and Identification. Von Moni Naor und Benny Pinkas. Im World Wide Web zu beziehen über http://www.wisdom.weizmann.ac.il/~naor/PAPERS/vis_auth.ps


Aus: Spektrum der Wissenschaft 7 / 1998, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH