Warum man Krypto nicht selbst machen sollte

Als ich so etwa in der 5. Klasse war, hab ich mal meine eigene Geheimschrift erfunden. Das hat mir damals unheimlich Spaß gemacht und ich kann sie sogar jetzt noch lesen und einigermaßen schreiben. Das ist ein Kinderspiel. Richtige Kryptographie ist aber alles andere als das. Immer wieder les ich von Leuten, die ihren eigenen Verschlüsselungsalgorithmus schreiben wollen — und das auch noch für eine gute Idee halten. Ich will jetzt mal versuchen, zu erklären, warum so etwas i.d.R. keine gute Idee ist. Ein paar aktuelle Begebenheiten im Security-Umfeld dienen dabei ein bisschen als Rahmenkulisse.

Warum war meine Geheimschrift von damals unsicher?

Nun, genau genommen war sie gar nicht sooo unsicher — hätte ich vor zweitausend Jahren gelebt. Aber mal der Reihe nach: Ich hatte — mehr oder weniger — für jeden Buchstaben unseres Alphabets einen eigenen überlegt. So etwas nennt sich monoalphabetische Verschlüsselung. Es gibt diverse Möglichkeiten, so etwas zu knacken. Beispielsweise kann man statistische Häufigkeitsverteilung von Buchstaben untersuchen. In der deutschen Sprache ist das „e“ am häufigsten. Also wird das Geheimzeichen, das „e“ bezeichnet in einem Geheimtext auch am häufigsten vorkommen. Das ist ein bisschen vereinfacht, aber es sollte schon deutlich werden, warum man eine monoalphabetische Verschlüsselung leicht knacken kann.

Auf diesem Niveau hat man von etwa zweitausend Jahren verschlüsselt. Die berühmte Caesar-Chiffre ist ein Beispiel dafür.

Anderthalb Jahrtausende später

Im 16. Jahrhundert wurde dann die — damals — unknackbare Verschlüsselung erfunden: Die Vigenere-Chiffre. Diese war nicht mehr monoalphabetisch, sondern polyalphabetisch, verschlüsselte also einen Buchstaben *nicht* immer gleich.

Vigenere galt lange Zeit als unknackbar. Bis ein dahergelaufener preußischer Infanterieoffizier (und Charles Babbage) eine Möglichkeit fand die „chiffre indéchiffrable“ doch zu entschlüsseln. Heute ist das Knacken von Vigenere-Texten fast nur noch eine Hausaufgabe für übermotivierte Schulkinder.

Das Prinzip wurde weiter entwickelt und polyalphabetische Chiffren blieben in Mode bis weit ins 20. Jahrhundert hinein. Auch die Enigma war effektiv nichts anderes als eine komplizierte Abwandlung von Vigenere. Auch die Enigma ist somit unsicher. Hintergründe und Funktionsweise sind trotzdem ganz interessant. Der Wikipedia-Artikel ist lesenswert.

Kurz gesagt: Es haben schon viele schlaue Köpfe Verschlüsselungsalgorithmen geschrieben. Leute ohne Ahnung haben regelmäßig schlechte Verschlüsselungen produziert. Und Leute mit Ahnung solche, die heute nur noch Schüler beschäftigen.

Wie heutige Verschlüsselungen funktionieren

Alle oben genannten Verfahren tun nichts anderes als Zeichen ersetzen. Sie sind Substitutionsverfahren. Daneben gibt es noch andere Möglichkeiten. Beispielsweise die Skytale, mit der die Reihenfolge der Buchstaben vertauscht wird. Die Skytale ist eine Permutationschiffre.

Mehrere Substitutionen hintereinander ergeben nur eine kompliziertere Substitution und mehrere Permutationen hintereinander ergeben eine kompliziertere Permutation. Beides erhöht die Sicherheit nicht. Wenn man aber beides macht. Also zuerst substituiert, dann permutiert, wieder substituiert, wieder permutiert, usw. erhält man wirklich bessere Chiffren. Das Prinzip nennt sich SP-Network und steckt in praktisch allen modernen Verschlüsselungsverfahren.

Sind SP-Networks also immer sicher?

Nein. Auch hier gibts Angriffsmöglichkeiten, wenngleich die schon deutlich ausgefeilter sein müssen. DES beispielsweise hat eine interessante Geschichte, die das verdeutlicht.

DES ist eines der „modernen“ Verfahren, ein SP-Network, und war lange Zeit ein weltweit genutzter Standard. Als man DES standardisiert hat, hat man den Algo der NSA gegeben. Die NSA hat sich dann den Algo mal angesehen und im Wesentlichen zwei Änderungen erwirkt. Zum einen wurde die Schlüssellänge reduziert und zum anderen funktioniert nun in DES ein kleiner Teil der Substitution ein ganz kleines bisschen anders. Warum? Keiner wusste es. Die NSA hat gesagt „Mach mal den Schlüssel kürzer und mach mal da hinten links aus der 42 ne 17.“ Und dann hat man das einfach gemacht. Es wurde natürlich gemunkelt, dass die NSA irgend ne verborgene Hintertür reingemacht hat. Genau genommen war es aber wohl umgekehrt. DES war in der ursprünglichen Form anfällig für ein Verfahren, das sich Differenzielle Kryptoanalyse und zu der Zeit der NSA vermutlich bekannt war, dem Rest der Welt aber nicht. Die Änderungen der NSA schützten DES vor dem Angriff, aber die verringerte Schlüssellänge sicherte jedem mit genug Rechenpower, die Möglichkeit DES durch einfaches Brute Forcing (d.h. Ausprobieren aller möglichen Schlüssel) zu knacken. Und es ist anzunehmen, dass die NSA genug Taschenrechner im Keller hat.

Wie an den Wikipedia-Artikeln ersichtlich werden sollte, sind heutige Verfahren (sowohl die zum Verschlüsseln als auch die zum Knacken) meist so kompliziert, dass man sich nicht mehr so einfach einem Nicht-Experten erklären kann.

Und auch Experten tun sich mit sowas schwer. Das zeigt eine weitere Anekdote: Irgendwelche Telekom-Leute hatten auch mal nen Verschlüsselungsalgorithmus schreiben wollen. Sie nannten ihn Magenta. Sie hielten ihn geheim. Sie präsentierten ihn auf einer Konferenz. — Und bereits während der Präsentation fanden ein paar der Zuhörer Schwachstellen, die sie dann auch benutzten und im Jahr darauf selbst ne Präsentation darüber hielten.

Oder kurz gesagt: Krypto ist schwer. Algorithmen, die vor zweihundert Jahren einigermaßen hätten sicher sein können, kann man sich als Normalsterblicher vielleicht noch ausdenken. Alles, was heute sicher sein soll, überlässt man lieber ausgewiesenen Experten. Und mit „Experten“ meine ich wirklich Experten. Ich hab zwar ein paar Security-Vorlesungen hinter mir, aber ich bin weit — sehr weit — davon entfernt, so ein Experte zu sein. Einen eigenen Algo schreiben ist also i.d.R. keine gute Idee.

Aber implementieren kann ich das doch wenigstens, oder?

Von Zeit zu Zeit begegnen mir Leute, die Kryptographie in irgendeiner Weise (meist handelt es sich um RSA, weil das so schön einfach ist) selbst implementieren wollen. Ich antworte dann meist, dass das ne schlechte Idee ist. Eine ziemlich schlechte. Mit zwei Ausnahmen:

Ausnahme 1: Man ist ausgewiesener Experte auf dem Gebiet.
Ausnahme 2: Man will das gar nicht wirklich verwenden, sondern macht das nur als Übung/zum Lernen/aus Spaß/was weiß ich.

In allen anderen Fällen, sollte man die Finger davon lassen und eine Bibliothek verwenden, die einer nach Ausnahme 1 geschrieben hat. Das ist einfacher und sicherer.

Manchmal hab ich das Gefühl, dass man mir das nicht glaubt. Ich höre dann zum Teil das Argument, dass man das ja testen könne. Wenn eine „gute“ Implementierung die eigenen Daten lesen kann und umgekehrt, muss man wohl alles richtig gemacht haben. Aber das ist nicht so.

Die Argumentationsweise an sich ist noch gar nicht mal so schlecht. So würde man das tatsächlich testen können. Die Frage ist nur, was „das“ ist, was man testet. Man testet nämlich nur die funktionalen Eigenschaften. Was man damit aber noch nicht gezeigt hat, ist, dass das Ganze auch sicher ist.

Security ist von allen nicht-funktionalen Eigenschaften wohl eine der am schwersten zu fassenden. Mag die eigentliche RSA-Implementierung auch korrekt sein, das „Drumherum“, das man auf den ersten Blick nicht sieht, hat einen enormen Einfluss auf die Sicherheit der gesamten Implementierung.

Hier ein paar Beispiele dazu:

Ein komplizierter, aber sehr wichtiger Teil „drum herum“ ist das Erzeugen von Zufallszahlen, die man für die Schlüssel braucht. Nicht jeder Zufall ist nämlich „zufällig genug“. Ein Bug im Zufallsgenerator in der Debian-Version von OpenSSL führte beispielsweise dazu, dass zwischen 2006 und 2008 reihenweise unsichere (weil vorhersagbare) Schlüssel erzeugt wurden.

Und Anfang diesen Jahres wurde bekannt, dass eine ganze Menge RSA-Zertifikate unsichere Schlüssel enthalten. Der Modulus (ein Teil des öffentlichen Schlüssels) war bei manchen Zertifikaten gleich. Anders als im verlinkten Heise-Artikel behauptet, bedeutet ein gleicher Modulus noch nicht, dass der private Schlüssel gleich ist. Allerdings könnte eine Partei den privaten Schlüssel der anderen errechnen, wenn man die eigenen Zufallszahlen, aufbewahrt hat. Und Außenstehende können über einen komplizierten Trick Nachrichten, die an beide Empfänger gehen, lesen.

Noch schlimmer ist es, wenn zwei Moduli einen ggT größer 1 haben. Das bedeutet, dass nur eine von zwei Zufallszahlen sich wiederholt hat. In diesem Fall sind beide Schlüssel gebrochen, weil jeder den privaten Schlüssel errechnen kann.

Und wahrscheinlich gibt es noch diverse andere Dinge „drum herum“, die man beachten muss, damit RSA sicher ist.

Für RSA werden also ein paar Anforderungen an die Zufallszahlen gestellt. Sie sollten „nicht zu klein“ sein. Beide sollten „ähnlich groß“ sein. Aber die Differenz zwischen beiden darf auch wieder „nicht zu klein“ sein. Und sie sollten natürlich nicht wiederverwendet werden (wie oben erläutert).

Das alles macht die Implementierung von RSA doch nicht mehr ganz so einfach, wie gedacht. Oder kurz: Lieber nicht selbst schreiben.

Aber zumindest verwenden kann man Krypto doch bedenkenlos, oder?

Oder? Wie sich gerade mal wieder zeigt, ist selbst das nicht ganz so einfach. Ein bisschen Hintergrundwissen ist selbst dafür nötig, damit nichts schief geht. Verwenden kann man das, ja. Aber nicht bedenkenlos. Ich kann hier keine Security-Schulung ersetzen, aber ich will an ein paar Beispielen zeigen, was man alles falsch machen kann. Aus gegebenen Anlass nehm ich mal als Beispiel das Speichern von Benutzerpasswörtern.

Zuerst einmal ist es extrem wichtig, dass man die Passwörter nicht im Klartext abspeichert. Im Allgemeinen speichert man Passwörter also gehasht. Die Frage ist nun: Mit welchem Algorithmus? Dass md5 mittlerweile gebrochen ist, hat auch Microsoft mittlerweile mitgekriegt (oder: schmerzlich erfahren müssen). Wobei das Problem im Falle Microsoft nicht direkt Passwörter betrifft.

md5 ist gebrochen, was in diesem Fall bedeutet, dass es möglich ist, systematisch Kollisionen zu erzeugen. Das funktioniert in etwa folgendermaßen: „Hallo MS, hier ist ein harmloses Dokument. Unterschreib mal!“ „OK“ *MS unterschreibt harmloses Dokument* *Angreifer bastelt ein gefährliches Dokument, das fast so aussieht, wie das harmlose (d.h. den selben Hash hat)* *Angreifer schnipselt die Signatur weg und klebt sie auf das nicht-mehr-ganz-so-harmlose Dokument* Jetzt sieht es so aus, als hätte MS die Schadsoftware als harmloses Update unterschrieben. Das funktioniert aber nur, wenn man systematisch Kollisionen erzeugen kann. Und genau das ist wohl mit Flame ausgenutzt worden. Wenn das stimmt, was Heise sagt, hat sich damit MS nicht gerade mit Ruhm bekleckert…

Zurück zu unserem Passwort-Szenario: Hilft das einem Angreifer, an die Passwörter zu kommen? Ne. Der Angreifer kann bei einem bekannten Passwort ein anderes erzeugen, das dann auch funktioniert. Das ist zwar lustig, aber nicht wirklich schlimm. Die Kollisionsresistenz interessiert bei Zertifikaten, bei Passworten interessiert viel eher eine Eigenschaft, die sich Preimage Resistance oder Einwegeigenschaft nennt. Aus dem Hash soll sich das Passwort nicht schneller als per Brute Force ermitteln lassen. Nach meinem Kenntnisstand ist md5 dahingehend noch nicht kompromittiert. Aber, wenn es schon praktikable Kollisionsangriffe gegen md5 gibt, kann man vermuten, dass es wahrscheinlicher ist, dass es irgendwann auch einen Preimage-Angriff auf md5 gibt, als auf einen moderneren Algorithmus. Während es also ausgesprochen dumm ist, md5 für digitale Signaturen zu verwenden, ist es nur „unvorsichtig“ md5 für Passworte zu benutzen. Wenn man also die Wahl hat, sollte man eher auf einen Algorithmus der SHA2-Familie setzen.

Also einfach einen SHA2-Algo verwenden und gut? Nein. Es gibt noch etwas, das man beachten sollte. Viele Leute verwenden unsichere Passwörter. Diese lassen sich über Wörterbuchangriffe oder per Brute Force ermitteln. Und das gilt es zu verhindern oder zumindest zu erschweren.

Das Knacken ist zwar mitunter aber etwas aufwendig. Man kann den Aufwand aber reduzieren, indem man quasi alle möglichen Passworte und deren Hashes einmal berechnet. Wenn man die Liste einmal hat, muss man nur noch nachgucken, was das Passwort zu einem gegebenen Hash ist. Mit so einer Liste lohnen sich also auch Angriffe, die sich ansonsten nicht lohnen würden, weil man nicht mehr selbst alles ausprobieren muss, sondern nur noch in einer Datenbank nachguckt. Eine intelligente Art der Speicherung (so genannte Rainbow Tables) machen die Daten handhabbar. Selbst mit Rainbow Table kann die DB zwar mehrere GB bis mehrere TB groß sein, aber solche Datenbanken existieren bereits.

Um dem entgegen zu wirken, benutzt man i.d.R. so genannte Salts. Man verlängert quasi das Passwort um eine zufällig generierte Zeichenkette und macht so das Erzeugen einer Rainbow Table unwirtschaftlich. LinkedIn hatte wohl kein Salz in die Suppe getan. Und das ist wohl nur ein Eisberg mit Spitzen.

Ein weiterer Trick, um Passwörter zu schützen, ist, Hashes in mehreren Runden anzuwenden („Key Stretching„). Also statt einmal den Hash über einem (gesalzenen) Passwort zu berechnen, schreibt man sich ne Schleife:

1
2
3
hash := password;
for i in 1..1000 do
  hash := hash_algo(hash);

Das macht die Berechnung des Hash-Wertes tausend mal langsamer. Für den normalen Einsatz spielt das i.d.R. keine Rolle, ob jetzt Mikrosekunden oder Millisekunden gebraucht werden, um heraus zu finden, ob man sich vertippt hat. Will man aber ein Passwort knacken, dauert das eben auch 1000 mal so lang. Zehn Tage sind dabei noch einigermaßen akzeptabel. Zehntausend Tage i.d.R. nicht mehr.

Wenn man sich nicht ganz sicher ist, wie sicher so ein Hash-Algorithmus ist, kann man auch noch ein bisschen weiter tricksen und die Berechnung verkomplizieren. Das macht z.B. md5crypt. md5crypt ist nicht der normale md5, sondern eine abgewandelte Version davon.

Poul-Henning Kamp, der Autor von md5crypt, sagt jetzt, dass md5crypt unsicher ist und nicht mehr verwendet werden sollte. Das liegt hauptsächlich daran, dass er mittlerweile zu schnell zu berechnen ist (md5crypt hat eine eingebaute — feste(!) — Anzahl an Iterationen). Dadurch wird Brute Forcing mittlerweile handhabbar. Aufgrund von Moore’s Law müsste man quasi alle anderthalb Jahre die Rundenzahl verdoppeln, um das Sicherheitniveau zu halten.

Kamp schlägt also vor, eine eigene Abwandlung eines Hash-Algorithmus zu schreiben und die Rundenanzahl dynamisch anpassbar zu machen. Heise hat das erstmal etwas missverständlich formuliert und dann mit einem schönen Zitat nachgebessert. Auch hier gilt natürlich, dass es keine gute Idee ist, seinen eigenen Hash-Algorithmus zu schreiben. Aber bestehende abwandeln und kombinieren, ist durchaus möglich.

Allerdings… auch das ist nicht ganz einfach und erfordert ein bisschen Hintergrundwissen. Beispiel:

  • sha512(md5(pw)) ist nicht allzu viel sicherer als md5 alleine (wenn md5 kollidiert, kollidiert auch der neue Hash)
  • md5(sha512(pw)) hat das Problem nicht. Allerdings ist das Ergebnis trotzdem nur 128 bit lang.
  • concat(md5(pw), sha512(pw)) sollte OK sein
  • concat(md5(sha512(pw)), sha512(md5(pw))) ist auch zumindest problematisch. Beweis.

Langer Rede kurzer Sinn

Kryptographie ganz selber machen ist eine dumme Idee. Und selbst Kryptographie richtig benutzen, ist nicht ganz einfach.

Lesenswertes

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.