Kryptographische Protokolle und wie man es nicht macht

Veröffentlicht: 10.11.2012 in Internet, Mathematik

Kryptographie ist eine spannende Angelegenheit. Es ist schließlich kein Kinderspiel, über eine nicht vertrauenswürdige Verbindung im Internet, wo jede Zwischenstation potenziell mitlesen oder Daten verändern kann, eine vertrauenswürdige und vertrauliche Verbindung herzustellen. Da ist es nicht weiter verwunderlich, dass immer wieder Leute neue goldig glänzende Protokolle erfinden, die zwar sicher aussehen, aber leider alles andere als sicher sind. Ein warnendes Beispiel ist mir die Tage über den Weg gelaufen.

Der Erfinder des Protokolls hat sich das sogenannte Socialist Millionaire Problem angesehen. Im Kern geht es um gegenseitige Beglaubigung: Alice und Bob haben ein gemeinsames Geheimnis (zum Beispiel ein Passwort), aber sich noch nie im Leben gesehen. Bei ihrem ersten Treffen wollen sie ihre Identität überprüfen, indem sie herausfinden, ob beide das Passwort kennen. Das ist natürlich nicht so leicht, denn wenn Alice das Passwort sagt, kann Bob zwar die Identität von Alice verifizieren, aber sie risikiert damit auch, einem Fremden das Passwort zu verraten, der sich dann gegenüber dem echten Bob als Alice ausgeben kann.

Das besondere am Socialist Millionaire Protokoll ist, dass es Alice und Bob nicht nur ermöglicht das Passwort zu überprüfen, sondern auch die Eigenschaft hat, dass ein heimlich lauschender Dritter oder jemand der sich nur als Alice oder Bob ausgegeben hat, keinerlei Informationen über das wahre Passwort herausbekommen kann. Diese Eigenschaft nennt man Zero-Knowledge-Proof und wie man sich vorstellen kann ist das im Internet irrsinnig praktisch um sich auf einem Server mit einem Passwort anzumelden. Allerdings ist es auch alles andere als trivial zu bewerkstelligen.

Die Details lassen sich bei Wikipedia nachlesen, aber der wichtigste mathematische Kniff ist eine Einwegfunktion der Form y = gx mod p.  Auf deutsch heißt das: potenziere die Zahl g mit x und schau welcher Rest bleibt, wenn man das Ergebnis durch p teilt. Wenn g (auch Generator genannt) und p (auch Modulus genannt) bekannt sind, kann man aus x sehr leicht y ausrechnen, aber umgekehrt ist es sehr schwierig aus y wieder x zu bekommen. Die einzige Ausnahme ist y=1, dann ist x=0.

Genau hieran stört sich auch der oben genannte Protokollerfinder, denn wenn man x=0 in die Einwegfunktion steckt, akzeptiert das Socialist Millionaire Protocol jedes beliebige Passwort. Allerdings ist das leicht zu vermeiden:  Wenn unser Gegenüber behauptet, er hätte bei seiner Einwegfunktion den Wert y=1 bekommen, versucht er uns gerade gewaltig übers Ohr zu hauen und wir hauen ihn ebenfalls übers Ohr. Mit einem großen Knüppel.

Diese Lösung ist unserem Experten aber zu billig. Sein Gegenvorschlag lautet, dass keine Partei seine Zahlen alleine wählen darf, sondern immer noch eine Zahl der anderen Partei, den Obfuskator (Verschleierer), dazu addieren muss. Außerdem ist ihm die Mathe zu kompliziert, also lässt er die Teile weg, die ihm für die Sicherheit nicht relevant erscheinen. Im Ergebnis erhält man dann ein Protokoll wie das folgende:

Alice <— Netzwerk —> Bob
Alice und Bob wollen wissen, ob ihre Geheimnisse S_A und S_B gleich sind
Wählt Generator G_A
Wählt Obfuskator O_A1
Sendet an Bob G_A, O_A1
Wählt Modulus M_B
Wählt Obfuskator O_B1
Berechnet C_B = (G_A + O_B1)S_B mod (M_B + O_A1)
Wählt Generator G_B
Wählt Obfuskator O_B2
C_B, G_B, M_B, O_B1, O_B2 Sendet an Alice
Berechnet T_A = (G_A + O_B1)S_A mod (M_B + O_A1)
Prüft, ob T_A = C_B. Falls nein, Abbruch
Wählt Modulus M_A
Wählt Obfuskator O_A2
Berechnet C_A = (G_B + O_A2)S_A mod (M_A + O_B2)
Sendet an Bob C_A, M_A, O_A2
Berechnet T_B = (G_B + O_A2)S_B mod (M_A + O_B2)
Prüft, ob T_B = C_A. Falls nein, Abbruch
Alice und Bob wissen, dass S_A = S_B

Auf den ersten Blick sieht es ja ganz ordentlich aus. Das Passwort S_A beziehungsweise S_B wird niemals über das Netzwerk übertragen, sondern nur die mit der Einwegfunktion verschlüsselte Version. Das Protokoll ist auch korrekt: wenn Alice und Bob das gleiche Passwort kennen, kommt das am Ende immer so heraus. Aber ist es sicher?

Zunächst einmal schauen wir uns den Obfuskator an. Nehmen wir an, die böse Eve gibt sich als Bob aus und möchte einen ganz bestimmten Generator benutzen, zum Beispiel die Eins. Weil 1x=1 für jedes beliebige x ist, würde das Protokoll dann immer ergeben, dass die Passwörter gleich sind und Eve hätte sich erfolgreich als Bob ausgegeben. Leider gibt uns Alice den Generator G_A vor, aber das macht nichts: Wir wählen einfach unseren Obfuskator O_B1 = 1-G_A und behaupten gegenüber Alice scheinheilig, dass wir C_B=1 herausbekommen haben. Alice rechnet G_A+1-G_A=1 als Generator aus, womit auch T_A=1 wird, und schon ist das „Passwort“ akzeptiert.

Gut, damit hat sich der ganze Additionszauber als völlig nutzlos erwiesen, aber der Trick mit der Eins lässt sich ja wie schon beim originalen Socialist Millionaire Protocol leicht feststellen und durch adäquate Gewaltanwendung kurieren. Leider kommt es noch schlimmer.

Angenommen, Eve gibt sich gegenüber dem echten Bob als Alice aus und stößt das Protokoll ganz normal an, bis Bob C_B ausgerechnet und an Eve gesendet hat. Eve kann zwar die Einwegfunktion nicht umdrehen, aber sie weiß, dass C_B = (G_A + O_B1)S_B mod (M_B + O_A1) ist. G_A und O_A1 hat sie selbst gewählt, O_B1 und M_B hat ihr Bob zusammen mit C_B verraten. Wenn Bob jetzt mit dem Protokoll fortfährt, muss Eve nur mit ihren Obfuskatoren dafür sorgen, dass für C_A wieder genau die gleiche Rechnung zu lösen ist, was kein Problem ist, weil Bob seine Werte G_B und O_B2 zuerst wählt und Eve sich darauf einstellen kann. Bob kann zwar feststellen, dass Eve wieder genau die gleiche Rechnung durchgeführt hat und deswegen das Passwort gar nicht kennen muss, aber niemand kann Eve daran hindern, sich gegenüber der echten Alice als Bob auszugeben und wieder diese Rechnung zu erzwingen. Alice hat keine Chance, den Betrug zu entdecken.

Genau genommen muss Eve nicht einmal aktiv am Protokoll teilnehmen; es reicht völlig aus, wenn sie Alice und Bob belauscht, und schon bekommt sie nicht nur einen, sondern sogar zwei Werte der Einwegfunktion geschenkt — bei jedem Durchlauf. Und damit ist das Protokoll vollständig gebrochen. Jeder Angreifer kann allein durch Mithören genug Informationen sammeln, um sich anschließend selbst als legitime Partei auszugeben. Das ist so ziemlich das Gegenteil von einem Zero-Knowledge-Proof.

Was lernen wir daraus? Erstens, kryptographische Protokolle zu entwerfen ist schwer. Schon kleine Details können die Sicherheit kompromittieren. Zweitens, dass das Passwort nicht im Klartext übertragen wird heißt noch lange nicht, dass es keine passwort-äquivalenten Informationen gibt, die ein Angreifer abhören und missbrauchen kann. Und drittens, die Kardinalregel bei Challenge-Response-Verfahren: der Angreifer darf niemals und unter keinen Umständen Einfluss auf die Challenge nehmen können.

Advertisements
Kommentare
  1. Kenny sagt:

    Gut zu wissen. Habe den Artikel mal offline genommen, damit niemand auf die Idee kommt, es einzusetzen. 🙂

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s