Schlüssel, Salz und Regenbogen

Inzwischen wissen wir, dass es verdammt viele verschiedene 256 BIT Schlüssel gibt. In „Weißt Du wieviel Sternlein stehen“ habe ich versucht, ihnen diese gigantische Zahl anhand verschiedener Beispiele zu veranschaulichen. Hier noch einmal die wichtigsten Ergebnisse zusammengefasst:

  • Die hauptsächlich verwendeten Verschlüsselungsverfahren sind symmetrische und asymmetrische Verfahren. Die Verfahren sind nicht vergleichbar.
  • Die Schlüssellänge ist nur dann als Maß für die Sicherheit eines Verfahrens heranziehbar, wenn Brute-Force die beste Methode darstellt, die Verschlüsselung zu knacken.
  • Die Formel zur Berechnung der Anzahl an verschiedenen Schlüsseln lautet N ^ k (N repräsentiert dabei die Zahl der Zeichen, die wir für den Aufbau des Schlüssels zur Verfügung haben, k steht für die Anzahl an Stellen bzw. die Länge des Schlüssels)
  • Für AES in der 256 BIT Variante erhielten wir als Ergebnis 2^256 {approx} 1,16 * 10 ^77 Schlüssel
  • Vorausgesetzt, wir könnten in jedem Atom genau einen dieser 256 BIT langen Schlüssel speichern, würden ALLE Atome des Universums gerade so ausreichen um in jedem Einzelatom einen dieser Schlüssel zu speichern.

Sind Angreifer chancenlos?

Zeit ist Geld *

 

Wie wir inzwischen wissen, muss ein Angreifer natürlich nicht alle Schlüssel durchtesten, bis er schließlich den richtigen erwischt. Wenn er die Hälfte der Schlüssel austestet, hat er immerhin eine 50% Wahrscheinlichkeit (p=0,5), den richtigen Schlüssel zu finden. Wie aber sähe es in der Praxis aus. Was braucht man an Hardware und wie lange braucht man für einen solchen Angriff.

Gehen wir einmal von einem Supercomputer aus, der

in EINER einzigen Sekunde

100 Millionen (= 10 ^8 ) dieser Schlüssel testen kann.

Das wären dann an einem Tag

24 h * 60 min * 60 sec * 10 ^8 approx 9 * 10^11 Schlüssel.

Das wären dann in einem Jahr

365 d * 9 * 10^11 approx 3,3 * 10^14 Schlüssel

Die ersten fossilen Funde der Gattung Homo sind ca. 200.000 Jahre alt. Angenommen, wir hätten zu dieser Zeit einem Freund aus Afrika einen Rechner entsprechender Leistung mit gutem Akku zur Verfügung gestellt und die Berechnung gestartet.

Dann hätten wir heute

200.000 * 3,3 * 10^14 approx 6,6 * 10 ^19

Schlüssel getestet.

Sie merken schon, wo wir uns hinbewegen?! Das war wohl nichts, ein anderer Ansatz muss her.

Parallel ist schnell?! *

Ja, im Bereich der Verschlüsselung kann man sehr viel und sehr gut parallelisieren. Das hat der ein oder andere sicher in ArchiCrypt Live gesehen. Die Version 6 nutzt geschickt die einzelnen Kerne im Prozessor aus, die an sich auch eigenständige Rechner darstellen. Man könnte die Last also auf viele verschiedene Rechner aufteilen. Der eine kleine Rechenfreund untersucht diesen Teil des Schlüsselraums, der andere jenen.

Wir sind einmal großzügig und nehmen an, dass wir durch eine geschickte Kampagne Menschen in der ganzen Welt dazu bewegen konnten, sich unserem Angriff anzuschließen.

Eine Milliarde Rechner = 10^9 Rechner stehen uns zur Verfügung!

Jetzt nähern wir uns einmal von der anderen Seite an das Problem an.

Es reicht uns, wenn wir eine 50% Wahrscheinlichkeit haben, den Schlüssel zu finden. Also müssen wir „nur“ 10^37 Schlüssel untersuchen.

Aufgeteilt auf 10^9 Rechner wären dies 10^28 Schlüssel, um die sich jeder einzelne Rechenknecht zu kümmern hat.

Wie lange benötigt dann so ein Einzelrechner für seine Aufgabe?

{10^28} / (3,3 * 10^19) {approx} 303.030.303 Jahre

Dumm gelaufen L

Schnell ist nicht schnell genug *

Die Sache ist aussichtlos für den Angreifer. Trotz äußerst großzügiger Auslegung möglicher Rahmenbedingungen, hat ein Angreifer nicht den Hauch einer Chance auf diese Art und Weise an unsere verschlüsselten Daten zu gelangen. Dumpfes durchprobieren wird auch in der Praxis nicht wirklich oft praktiziert. Allerdings kann man in einschlägigen Foren lesen, dass diese Angriffsart tatsächlich zur Anwendung kommt und immer noch großen Erfolg hat. Natürlich nicht so, wie oben beschrieben gegen 256 BIT AES. Vielleicht erzähle ich Ihnen in einem anderen Artikel einmal etwas darüber 😉

Pizzaschachteln und Marlboro *

Verbannen Sie also das Bild des Hackers , der, umgeben von Pizzaschachteln, vor sich den überquellenden Aschenbecher und um sich ein Meer aus leeren Cola-Flaschen, im Scheine seines Monitors, mit zittrigen Händen Passwörter in die Tastatur eingibt.

Hollywood hat da saubere Arbeit geleistet – Password Swordfish lässt grüßen!

Noch ein Mythos:
Um zu erkennen, ob ein Nutzer ein Passwort richtig angegeben hat, ist das Passwort irgendwo gespeichert.

Nein: Ein Programm, welches erkennt, ob ihr Passwort richtig oder falsch ist, hat ihr Passwort nicht gespeichert. Falls doch, war ein „Fachmann“ alter Schule am Werk. Anders ausgedrückt: Wer das Paswort speichert, verdient Programmierverbot.

Noch ein Mythos:

Das Passwort welches Sie eingeben, wird direkt genutzt, um Daten zu ver- oder entschlüsseln.

Die Daten werden nicht mit Ihrem Passwort ver-/oder entschlüsselt (hoffentlich). Das Passwort ist lediglich ein Startwert, mit dessen Hilfe der eigentliche Schlüssel dann berechnet wird. Dieser Schlüssel sollte perfekt auf den verwendeten Algorithmus abgestimmt sein.

Wie aus Lumpi01 ein Schlüssel wird *

Salt

Salt

Wir reden hier immer von einem 256 BIT Schlüssel. In Wahrheit sitzen aber Sie vor dem Rechner und geben ein Passwort ein.

Ich hoffe, nicht so etwas wie Lumpi01!

 

Erkennen, was Sache ist! *

Wieso sind das aber Mythen. Wie sollte ein Programm erkennen, ob ein Passwort richtig eingegeben wurde,wenn es das Passwort selbst nicht kennt?

Sie kennen aus Ihrer Schulzeit vielleicht noch die s.g. (Einstellige) Quersumme.

Man hat eine Zahl und addiert die einzelnen Ziffern auf. Das macht man so lange auch mit einem Zwischenergebnis, bis eine einstellige Zahl als Ergebnis vorliegt.

Angenommen, wir haben eine Nachricht mit dem Schlüssel 78 verschlüsselt und abgespeichert.

78 ->Quersumme = 7+8=15 -> Quersumme = 1+5 = 6

Diese Quersumme speichern wir uns jetzt bei die verschlüsselte Nachricht.

Jetzt soll wieder entschlüsselt werden. Das Programm liest den verschlüsselten Text ein und die gespeicherte Quersumme 6.

Können Sie aus dieser Zahl 6 zurückrechnen auf die ursprüngliche Zahl 78, unser Passwort also knacken?

Nein, sicher nicht!

Das ursprüngliche Passwort 78 ist aus der Ziffer 6 nicht herzuleiten.

Wenn ich jetzt die Zahl 79 eingebe, kann das Programm aber sagen, dass das mit Sicherheit nicht das richtige Passwort ist. Auch die Zahl 12 würde zu einer solchen Meldung führen. Die Quersummen stimmen ja nicht mit der gespeicherten 6 überein.

Natürlich ist die Quersumme nicht geeignet, wirklich als Verfahren in der Verschlüsselung zum Einsatz zu kommen. Aber das Prinzip ist erkennbar.

Man speichert einen Wert, der eine Aussag darüber zulässt, ob ein eingegebenes Passwort korrekt ist und hat nicht das Problem, das Passwort selbst abspeichern zu müssen. Zugleich kann man aus diesem Prüfwert keine Rückschlüsse auf das wirkliche Passwort ziehen.

Hash me if you can *

In der Kryptografie verwendet man s.g. Einweg-Hashfunktionen um aus einem Eingangswert beliebiger Länge einen s.g. Hashwert fester Länge zu erhalten. Also ziemlich ähnlich zu unserem Quersummenbeispiel.

Egal, ob man 5 Zeichen in die Hashfunktion gibt, oder 1000 Wörter, das Ergebnis hat eine feste Länge [SHA-1, secure hash algorithm, zum Beispiel 160 BIT].

Allerdings erwartet man in der Verschlüsselung schon etwas mehr von einem solchen Verfahren.

  • Es soll leicht sein, aus einer Nachricht N (wäre in unserem Beispiel unsere Eingangszahl bei der Quersumme, später zum Beispiel das Passwort) den Hashwert h zu berechnen. Das ist bei unserer Quersumme der Fall. War ja nicht schwer, zu 78 die Quersumme zu berechnen.
  • Es soll schwer sein, zu einem Hashwert h eine Nachricht zu erzeugen, die als Ergebnis h liefern würde. Das trifft auf unsere Quersumme schon nicht mehr zu. Wie wir gesehen haben, ist es sehr leicht gewesen die Zahlen 87 und 96 zu finden, die ebenfalls als Quersumme 6 haben.
  • Es soll schwer sein, bei vorhandener Nachricht N eine zweite Nachricht N‘ zu finden, die den gleichen Hashwert liefert. Das bietet unsere Quersumme auch nicht. Es ist in unserem Beispiel (79) alleine durch Tausch der Ziffern möglich, eine solche „Nachricht“ zu erzeugen.
  • Wir brauchen noch etwas. Es soll schwer sein, zwei beliebige Nachrichten zu finden, die den gleichen Hashwert liefern. Die Betonung liegt auf beliebig. Eine solche Eigenschaft wird als Kollisionsresistenz bezeichnet. Unsere Quersumme fällt hier natürlich auch durch. Wir können uns massenhaft Paare bilden, die gleiche Quersummen erzeugen.

Vielleicht noch ein weniger mathematisch abstraktes Bild, damit man sich etwas unter einer solchen Einweg-Hashfunktion vorstellen kann.

Sie brauchen eine Vase, ein Handtuch und einen Hammer. Vase in Handtuch, Hammer mehrfach auf Handtuch.

Den Inhalt des Handtuchs kippen Sie jetzt vor sich auf den Boden. Achten Sie darauf, dass Ihr Partner nicht in der Nähe ist J

Die Vase ist das Passwort (Nachricht) das wi in unsere Einweg-Hashfunktion geben und die Scherben sind der Hashwert.

Das nenne ich eine brauchbare Einweg-Hashfunktion, oder?

Prüfen wir das einmal:

  1. Anforderung 1 ist erfüllt. Es war leicht, den Hashwert (sind die Scherben) aus der Nachricht (ist die Vase) zu erzeugen.
  2. Anforderung 2 ist erfüllt. Es dürfte schwer sein, eine Vase zu töpfern, die nach entsprechender Bearbeitung die gleichen Scherben liefert.
  3. Anforderung 3 ist erfüllt. Auch wenn ich die Vase habe, ich finde so schnell keine Vase, die die gleichen Scherben erzeugen würde.
  4. Anforderung 4 ist erfüllt. Ich könnte vermutlich Millionen Vasen zerschmettern und es wären keine zwei Vasen darunter, die die gleichen Scherben erzeugen.

Ich bin gerade am überlegen, ob ich mir die Funktion nicht patentieren lassen soll 😉 Es ist aber nur ein Bild, mit denen ich Ihnen die Eigenschaften erklären möchte.

Eigentlich sollte klar sein, warum man diese Funktionen Einweg-Hashfunktion nennt. Versuchen Sie mal aus Ihren Scherben (dem Hashwert) wieder die Vase (das Passwort) zu rekonstruieren. Viel Spaß beim Kleben.

In der symmetrischen Kryptografie kommen diese Verfahren zum Einsatz, um aus Ihrem Passwort den Schlüssel für die Verschlüsselung zu erzeugen (Schlüsselableitungsfunktionen, key-derivation-functions; hier nicht behandelt) und, um eine Möglichkeit zu haben, die Richtigkeit eines Passwortes zu prüfen (darüber reden wir hier).

Sie speichern sich also den Hashwert des Passwortes. Gibt der Nutzer jetzt sein Passwort ein, berechnen Sie dauras wieder einen Hashwert und vergleichen ihn mit dem gespeicherten Wert. Stimmen beide Werte überein, ist das eingegebene Passwort korrekt, ansonsten nicht.

Am Ende eines Regenbogens … *

…ist kein Topf mit Gold, sondern sind Tabellen!

Die Angreifer sind findig. Sie sind nicht dumm und haben erkannt, dass man mit stumpfem Durchprobieren aller Schlüssel nicht ans Ziel kommt.

Tja, die Rainbow-Tables (Regenbogen-Tabellen). Sie machen es sich zu Nutze, dass ein Passwort wie Lumpi01 jedes Mal, wenn man es in die Einweg-Hashfunktion gibt, als Ergebnis z.B. 0101 1111 liefert. Wenn man das einmal berechnet hat, kann man es auch speichern. Man merkt sich also 0101 1111 und schreibt es zusammen mit Lumpi01 in einer Datenbank. Beim nächsten Angriff spart man sich die Neuberechnung des Hashwerts und sieht einfach in der Spalte Hashwert 0101 1111 nach und findet Lumpi01. Das spart enorm Rechenzeit. Macht man das für eine gewisse Zahl an Schlüsseln, sieht man schnell, dass irgendwann einmal Speicherprobleme auftreten. Jeder Schlüssel muss zusammen mit dem Hashwert in einer Datenbank abgelegt werden. Hier können wir wieder unser Problem mit den Atomen aus „Weißt Du wieviel Sternlein stehen“ ins Spiel bringen. Speichern aller Wertepaare ist unmöglich, weil wir einen gigantischen Speicherplatzbedarf hätten.

Also erdachte man ein Verfahren, welches einen guten Kompromiss zwischen Rechenzeit und Speicherplatzbedarf darstellt. Als Ergebnis dieser Suche präsentieren sich heute die s.g. Rainbow Tables, die im Prinzip die Umsetzung eines bereits 1980 gemachten Vorschlags von Martin Hellmann (einer der bekanntesten Kryptologen) darstellen.

Mit diesen Tabellen lässt sich zum Beispiel die Gesprächs- und SMS-Verschlüsselung von Handys – A5/1 innerhalb von wenigen Sekunden knacken.

Jemandem die Suppe versalzen *

Mit ein bisschen Salz kann man der Regenbogenfraktion den Spaß gehörig verderben.

Die Regenbogentabellen funktionieren nur, weil die Angreifer davon ausgehen, dass man beim Verschlüsseln mit identischem Passwort auch immer identischen verschlüsselten Text erhält. Hört sich ja auch logisch an, oder?

Also:

Egal, ob jetzt Oma Lisbeth „Heute Treffen um 00.00 Uhr“ mit „Lumpi01“ verschlüsselt, oder ich.

Am Ende muss „hajhstzueiooluhaoäaoirio#“ als Ergebnis erscheinen.

Zum Entsetzen der Angreifer hilft hier ein möglichst zufällig erzeugter Wert, den man mit dem eigentlichen Passwort verknüpft und unverschlüsselt mit der Nachricht abspeichern kann. Der Wert muss für jede Nachricht neu erzeugt werden.

Diesen Wert bezeichnet man als Salz (Salt), er muss nicht geheim gehalten werden.

Was macht man mit dem Salz und wie wirkt es?

Man verknüpft das Salz mit dem Passwort und verschlüsselt dann mit dem Ergebnis dieser Verknüpfung.

Als Eingangswert für die eigentliche Verschlüsselung dient also nicht mehr „Lumpi01„,

sondern z.B. „Lumpi01Ghafst„. Gahfst wäre unser Salt-Wert.

Im Ergebnis erhalten wir jetzt nicht mehr „hajhstzueiooluhaoäaoirio#„, sondern zum Beispiel

Kjkjhlakjzuwqiezbypöäüo„. Oma Lisbeth schickt uns mit dieser Nachricht auch den Salt-Wert. Der muss ja nicht mehr geheim gehalten werden.

Unser Angreifer fängt jetzt die Nachricht ab und steht vor dem Problem, dass in seinen Tabellen nur ein Eintrag zu „Lumpi01“ nicht aber zu „Lumpi01Ghafst“ enthalten ist. Folglich kann er seine Regenbogen Tabelle am Ende des Regenbogens vergraben, weil sie unbrauchbar ist. Er müsste sie komplett unter Verwendung des Salt-Wertes (dieser ändert sich ja per Definition jedes Mal) neu erstellen.

Fazit: Die Kryptografie hält mächtige mathematische Verfahren bereit, um sensible Informationen mit hoher Verlässlichkeit zu schützen. Immer wieder hat man es bei optimalen Verschlüsselungsmethoden mit extrem großen Zahlen zu tun, die zunächst unkommentiert wenig beeindruckend sind. Wirft man einen Blick hinter die Kulissen und versucht, die großen Zahlen etwas griffiger zu präsentieren, wird schnell klar, wie wirksam Verschlüsselung ist und welche Waffen sie im Kampf gegen Datendiebe bereithält.

Das nächste Mal sehen wir uns an, mit welchen Waffen Datendiebe ins Feld ziehen, um Verschlüsselungen doch zu brechen.

Das könnte Dich auch interessieren...

3 Antworten

  1. Leonhardt, Dietgart sagt:

    Vielen Dank für die bildliche Darstellung der komplexen und imaginären Zusammenhänge. Ich freue mich schon auf den nächsten Teil davon.

    Herzlichst
    D. Leonhardt

  1. 12. Dezember 2011

    […] ← Vorherige Nächste […]

  2. 22. Dezember 2011

    […] Sie die vorangegangenen Artikel  ["Weißt Du wieviel Sternlein stehen", "Schlüssel,Salz und Regenbogen"] gelesen haben, gehören Sie inzwischen ja schon eher zu den Wissenden im Bereich der […]

Zum Angang...