Zehn Beispiele für besonders schlechte Kryptografie (Teil 2/3)

Von Klaus Schmeh / 19. August 2013 / 28 Kommentare / Seite 2 von 2 / Auf einer Seite lesen

Im Oktober 2000 meldeten mehrere Internetseiten, dass ein ukrainischer Mathematiker P=NP bewiesen hätte. Waren RSA, DSA und Diffie-Hellman damit alle auf einmal hinfällig? Und das durch die Arbeit eines unbekannten Wissenschaftlers, der von Kryptografie keine Ahnung hatte? Bei näherem Hinsehen erwies sich der »Beweis« jedoch schnell als Schlangenöl. Als »totales Chaos« bezeichnete ein Mathematiker in einer Newsgruppe die Arbeit des Ukrainers und fügte hinzu: „Das ist genauso wenig ein Beweis für P=NP wie mein Telefonbuch.

« Vorherige Seite

Seite 1 / 2

Kommentare (28)

#1 H.M.Voynich
20. August 2013

Ein Schlüssel, der so lang wie die Nachricht ist, ergibt tatsächlich einen perfekten Geheimtext, weil man aus ihm jeden beliebigen Klartext (gleicher Länge) “rekonstruieren” kann. Es ist unmöglich, herauszufinden, ob dem Geheimtext SGHZJEHTM der Klartext Pepperoni, GuteNacht oder einfach xxxxxxxxx zugrunde liegt.
Deshalb funktionieren OneTimePads so gut, und 1 Millionen Bit dürften in den meisten aller Fälle genügen.

Vorausgesetzt, der Angreifer hat keine Informationen über den Schlüssel.
Zu irgendeinem Zeitpunkt aber müssen Sender und Empfänger den Schlüssel austauschen.
Genau da liegt der Hase im Pfeffer.
Der Unterschied zwischen Spinnern und Betrügern dürfte darin liegen, daß ersterer das nicht weiß und letzterer es bewußt verschweigt.

Die heute übliche Verschlüsselung bei Kommunikation über Computer, die sogar beim Browsen auf vielen Web-Seiten automatisch im Hintergrund passiert, ohne daß wir überhaupt etwas davon merken, hält das Schlüsselproblem vollständig vom Benutzer fern, weshalb es den meisten vermutlich nicht bewußt ist.
Auch dabei muß natürlich zwischen Absender und Empfänger Information über den Schlüssel übermittelt werden, die ein Dritter prinzipiell abhören kann.
Der Witz in der üblichen (Public-Key) Verschlüsselung liegt darin, daß die ausgetauschte Information nur aussagt, wie der Codetext erzeugt werden soll, aber nicht, wie man daraus wieder Klartext gewinnen kann.
Diese Information ist zwar im Prinzip vorhanden, aber dank NP nur mit der Rechenkraft aller Computer der ganzen Welt in absehbarer Zeit auffindbar (solange P nicht gleich NP ist – es geht darum, zwei extrem große Primzahlen und deren Produkt zu finden).
Und so wie die Rechner jährlich schneller werden, werden auch die Schlüssel länger.

Ein Schlüssel von 1 Millionen Bit wäre zwar wünschenswert, aber ohne sicheren Schlüsselaustausch taugt der keinen Pfifferling.
#2 malaclypse
20. August 2013

NP sind die Probleme, die eine nichtdeterministische Turingmaschine in Polynomialzeit lösen kann; nicht die, die mit einem Algorithmus in nicht polynomialer Zeit gelöst werden können.
- #3 Klaus Schmeh
  20. August 2013
  
  Danke für den Hinweis. Werde ich korrigieren.
#4 Silly Human
20. August 2013

Ich wünsche mir ja einen Link auf den ersten Teil in diesem Blogpost.
- #5 Klaus Schmeh
  20. August 2013
  
  Habe ich eingefügt.
#6 volki
20. August 2013

Eine kurze Anmerkung zu P=NP. Wie schon malaclypse geschrieben hat, ist die Erklärung von NP im Text falsch oder zumindest mißverständlich.

Ich möchte auch anmerken, dass selbst wenn P=NP bewiesen wäre, noch lange nicht RSA, DSA, oder was auch immer sofort unsicher wird. Man muß erst einmal einen schnellen Algorithmus finden. Nur weil man weiß, dass es eine schnelle Methode gibt, heißt noch lange nicht, dass man diese auch kennt.

Zu den Kandidaten die in NP aber nicht in P liegen: Das Faktorisierungsproblem ist meiner Meinung nach ein schlechtes Beispiel, da es nicht in der Klasse NP-hard liegt. Es wäre zwar erstaunlich wenn das Faktorisierungsproblem in P liegen würde aber das hat man vom Primzahltesten auch gedacht (siehe AKS-Test) und das Faktorisierungsproblem für Polynome liegt auch in P (Lenstra, Lenstra und Lovasz haben das 1982 bewiesen).

@H.M. Voynich:

es geht darum, zwei extrem große Primzahlen und deren Produkt zu finden

Das ist aber leicht und liegt in P. Ich nehme an du meinst so etwas:

Es geht darum bei gegebenen n=p*q (aber unbekannten p und q) die Primzahlen p und q zu finden.
#7 H.M.Voynich
20. August 2013

@volki:
Ja, ich hätte schreiben sollen “mit vorgegebenem Produkt”.

“Ich möchte auch anmerken, dass selbst wenn P=NP bewiesen wäre, noch lange nicht RSA, DSA, oder was auch immer sofort unsicher wird.”
Ein nichtkonstruktiver Beweis für P=NP bedeutet zwar noch nicht, daß ein schneller Algorithmus jemals gefunden werden wird oder auch nur existiert (Polynomialzeit kann immer noch länger dauern als Exponentialzeit, wenn die Konstanten nur groß genug sind), aber jegliches Vertrauen in Methoden wie RSA würde sofort schwinden. Der Gegner könnte ihn ja bereits gefunden haben. Faktisch wäre RSA damit tot.
#8 rolak
20. August 2013

Da ich den Kryptochef schon nach dem kommentarigen Hinweis besucht hatte, vermisse ich hier die grandiose Herleitung dessen, was 256 Bit sind:

Ein Computer kennt immer nur 256 verschiedene Zeichen. 1 Zeichen = 1 Byte hat im Binär Zahlensystem genau 8 Stellen.
1 Bit kennt nur die Schaltzustände: aus oder an bzw. 0 oder 1
Durch die Kombination dieser 8 Stellen ergeben sich 256 Bit.
Die Berechnung dazu: 2 Schaltzustände hoch 8 Stellen = 256 Bit
Diese 256 Bit sind adressiert im Dezimal Zahlensystem von 0 bis 255 = 256 Bit.

Damit dürfte dann auch die Formulierung “256 Bit (Vollbit) Verschlüsselung” endgültig geklärt sein: Eine freudsche Beschwerde darüber, daß im Kasten nur noch leere Bit sind.
#9 Chemiker
20. August 2013

Das ist ja wie bei dem alten Syllogismus:

(P1) Der Kryptochef ist ein schlauer Fuchs.
(P2) Alle Füchse haben vier Beine
(C) Der Kryptochef hat vier Beine.
#10 H.M.Voynich
20. August 2013

@rolak:
Du mußt das auf englisch lesen, ist noch viel besser.
(Wie kommt man auf “indication” für “Zeichen”? Sowas fällt nicht mal google ein. “Sign” hätte ich ja noch verstanden.)
Wirklich schön, wie er das entwickelt, am Anfang hat ein Byte noch 8 Bit, am Ende 256, Beweis durch Widerspruch.
Und im nächsten Atemzug den Leuten zu erzählen, daß Zahlen größer als 256 auf dem Computer gar nicht möglich sind, denselben Leuten, die grad in der Ecke ihres Monitors eine 2013 sehen, das ist schon fuchsig.

Aber ich denke, das muß man ihm bei seinem Alter nachsehen. Immerhin ist er der, “… which programs programmers of the software (…) computers
already since it computer gives.”
Und das war bekanntlich schon seit 1941.
#11 Hammster
20. August 2013

Ich interessier mich nicht wirklich für Krypto…zeugs – lese die Kolummne aber gern. Der Kryptochef ist allerdings ein echter Burner! Me will also lern English as he speaks bekause is not english Language, it is german Language, but me better transform into what nobody can read but sound goods. Prefekt translition!
Me like!!
#12 rolak
21. August 2013

“indication” für “Zeichen”?

Nun ja, H.M.Voynich, die semantischen Räume beider Worte sind nicht disjunkt, auch wenn im Deutschen ‘Anzeichen’ wohl etwas passender sein dürfte.

auf englisch .. noch viel besser

Anders, würde ich sagen, oder die Übersetzung als durchaus unabhängig zu genießende Kirsche auf dem Sahnehäubchen bezeichnen.
#13 cimddwc
21. August 2013

Interessante 8→256-Bit-Herleitungen beim Kryptochef, in der Tat. 🙂 Wenn der wüsste, dass aktuelle Prozessoren mehr als nur 8-Bit-Register haben, sondern locker mit 256-Bit-Registern umgehen, würde er wohl mit einer Schlüsselgröße werben, die fast allen Atomen im beobachtbaren Universum entspricht (wenn er denn was mit Zahlen à la 10^77 anfangen kann)…
#14 haarigertroll
21. August 2013

Mit dem Kryptochef kann man übrigens reich werden: https://www.heise.de/extras/foren/S-KRYPTOCHEF-erklaert-Warum/forum-44438/msg-10976673/read/
Es gibt 200.000 Euro Belohnung für’s Schlüssel-Knacken vom Chef (persönlich)!
#15 Freejack
21. August 2013

Kryptochefs Vollbitverschlüsselung gibt es unverändert seit Jahren, ist mir vor Ewigkeiten schon mal über den Weg gelaufen. Für mich war das bisher kein Schlangenöl, sondern Satire. Schlangenöl war damals jedenfalls der Passwortschutz von MS Office Dokumenten. Da gab es sogar Tools dafür, in denen angeblich sogar Warteschleifen drin waren, damit wenigsten der Eindruck entsteht es sei ein Rechenaufwand zum Dechiffrieren notwendig.

Schade das so wenig über die Algorithmen bekannt wird. Es wäre schon lehrreich zu wissen wo die Schwachstellen jeweils liegen.
#16 Thorsten
23. August 2013

Das m.E. beste Zitat vom Kryptochef (“persönlich!”) wurde noch gar nicht erwähnt. In den AGB (?) steht im Absatz 11 die wunderbare Formulierung:
Fallen Sie nicht auf andere Betrüger im Internet (…) rein.
Mir gefällt dabei das “andere” so gut! 🙂
#17 chefin
3. Februar 2014

Ob Kryptochef Satire oder Unwissenheit ist, muss jeder selbst entscheiden.

Aber was man erkennen kann: er benutzt einen OTP-Algorythmus. Dazu legt er eine Datei aus Zufallszahlen an oder benutzt die Bytefolge einer Datei die man vorgibt. Dabei muss die Datei LÄNGER als das zu Verschlüsselnde sein. Absolut logisch und nachgewiesenermassen Unknackbar. Und dieser Nachweis ist sehr einfach zu machen.

Nimm ein Byte, sagen wir hex40 (Ascii A), verschlüssel es über XOR mit einem anderen Byte. Es kommt etwas raus das zwischen 00 und ff Hex liegt. Ohne das Schlüsselbyte kann das Ergebniss beim Versuch es zu entschlüsseln alles sein von 00 bis ff. Den für jedes Byte gibt es genau ein Schlüsselbyte das immer zum selben Ergebniss führt.

Eine Verschlüsselung “34 44 f3 7b” kann ich auf das Wort ABER-EVER-DANN-GOOD-KANN-TREE-WORT-….und viele weitere Worte mit 4 Buchstaben zurück führen. Es wird nie möglich sein rauszufinden welches Wort ich verschlüsselt habe ohne den Schlüssel zu kennen. Man kann nur die Anzahl an Byte erkennen.

Man muss also nur diese 256 Möglichkeiten abchecken um die Sicherheit zu beweisen. Seine 256 Bit sind dann falsch ausgedrückt von ihm und sollten besser 256 Möglichkeiten heisen. Und mehr gibt es auch nicht wenn man 8Bit benutzt als Basis. Die 200.000 wird also nur derjenige bekommen, der beide Dateien in seinen Besitz bringt.. Allerdings ist das nicht Knacken. Wenn ich mir das Passwort besorge knacke ich jede Verschlüsselung.

Das aber zwischen Funktionieren und Benutzen ein Unterschied ist, unterschlägt er. OTP hat einen sehr geringen Nutzwert und eine hohe Anfälligkeit gegen Manipulation. Selbst wenn ich einige Dateien mitnehme auf einem Datenträger, könnte ein Angreifer diesen Datenträger ohne mein Wissen lesen und damit alle Dateien entschlüsseln.

Man kann also nicht sagen, das Kryptochef Schlangenöl verkauft, da sein Programm sehr korrekt arbeitet und sein versprechen das die verschlüsselte Datei unknackbar ist gehalten wird. Er verschweigt nur, das es einfach unpraktikabel ist.
#18 JoselB
18. Dezember 2015

Kleine Anmerkung: Die Aussage, dass eine Datei mit einer anderen gleicher Größe zu verschlüsseln, absolut sicher ist, stimmt nur bedingt. Die meisten Dateiformate haben eine wesentlich niedrigere Entropie als Datengröße. Im (zugegeben unwahrscheinlichem) Extremfall sind der Informationsgehalt von Schlüssel und Verschlüsseltem so gering und die Struktur der Dateien entsprechend passend, dass sich mit ungüstigem Verfahren für beide Dateien der Inhalt bei geringem Aufwand mit an Sicherheit grenzender Wahrscheinlichkeit bestimmen lässt. Auch wenn man sich natürlich nie zu 100% sicher kann, dass man wirklich die richtigen Ausgangsdateien gefunden hat und der Kryptotext nicht nur zufällig zu dem gefundenen Inhalt passt.

Gehen wir von einer Entropie von 2 Bit pro 8 Bit-Zeichen aus (deutsche Sprache hat nach kurzer Internetrecherche anscheinend 1 bis 1,3 Bit), so wäre es für Textdateien zumindest theoretisch möglich, Schlüsse zu Teilen des Inhalts zu ziehen. Da allerdings für natürliche Sprache nur ein kleiner Bereich des Zeichensatzes genutzt wird, ist das Verhältnis von 2 zu 8 Bit in der Praxis eher 2 zu 4 bis 6 Bit, weil die restlichen Bit nahezu konstant sind. Hier kommt es also sehr wohl darauf an, wie die beiden Dateien miteinander verrechnet werden.

Sorry, dass ich zu einem so alten Post noch was schreibe, aber ich konnte die Kommentare nicht einfach so stehen lassen.
#19 JoselB
18. Dezember 2015

Mein Kommentar von eben noch anhand des Beispiels von chefin erklärt:

Der Kryptotext “34 44 f3 7b” wird aus 2 Wörtern mit 4 Zeichen mit jeweils 256 möglichen Werten erzeugt. Das heißt, es gibt für beide Wörter über 4 Milliarden Möglichkeiten, bzw über 18 Trillionen Kombinationen wovon wiederum 4 Milliarden Kombinationen den Kryptotext ergeben. Also unknackbar…

Zumindest theoretisch, denn wurde Text mit Text verschlüsselt, so sieht die sache gleich anders aus, schließlich ist “ÛñOÏ” zum Beispiel wohl in keiner Sprache der Welt ein Wort. Es gibt vermutlich um die 1000 Wörter mit vier Zeichen, woraus sich 1 Million Kombinationen ergeben. Allerdings werden davon deutlich weniger als tausend Kombinationen zu “34 44 f3 7b” passen, da nicht alle Buchstaben gleich häufig vorkommen. Hat man sehr viel Glück, passt überhaupt nur eine Kombination. Sind es mehrere, wird zum Beispiel eine Kombination mit BAUM wesentlich wahrscheinlicher als eine mit AAKE. Man kann zwar immer noch nicht sagen, welches Wort mit welchem verschlüsselt wurde, hat aber eine kleine Liste an Kombinationen wovon eine noch kleinere wahrscheinlich ist. Für eine Datei die wirklich nur aus zufälligen Zeichen besteht gilt das natürlich nicht mehr, aber hier liegt die Betonung auf “wirklich zufällig”.

Nochmals ein Sorry an Klaus für den Moderationsaufwand.
#20 Robert
Wien
20. Februar 2016

Anscheinend dürfte der Kryprochef aufgegeben haben: die Webseite gibt es offenbar nicht mehr. (Eigentlich schade.)
#21 skateddy
Berlin
25. Februar 2016

Zentrales Prinzip bei OTP ist, dass alle von Mallory aus CypherText mit zufälligen Schlüsseln entschlüsselten PlainText(e) GLEICH WAHRSCHEINLICH sind und damit keine PT Kandidaten anfallen. Für die Beweisbarkeit der Sicherheit des OTP-Verfahrens gelten zwei Annahmen: (1) Der Schlüssel darf nicht kürzer als der PlainText sein (darf also nicht über dem PT rotieren) und (2) muss der Schlüssel eine hohe Entropie aufweisen und darf keinerlei Strukturen zeigen. Das ist imho nur mit physikalisch erzeugtem Zufall machbar. Dafür gibt es einige gute Lösungen z.B. die auf http://www.ibbergmann.org. Text mit Text zu verschlüsseln ist also kein richtig angewandtes OTP! Natürlich könnte man auch mit guten PRNG Zufall aus einem beliebigen CT alle möglichen PT generieren, sich dann den ansprechendsten heraus greifen und behaupten, dass man OTP geknackt hätte. Siehe https://de.wikipedia.org/wiki/Infinite-Monkey-Theorem. Was als Kritik am OTP bleibt ist die Notwendigkeit des geheimen Schlüsselaustausches, hat da ev. jemand eine gute Idee, die über den bekannten Diplomatenkoffer hinaus geht?
#22 Troll
19. September 2017

btw: Kryptochef ist ein Troll
#23 Christian
9. Mai 2018

Hallo zusammen,
Ich weiß gar nicht, ob dieses Blog noch “lebt”, aber anscheinend ist der Cryptochef (oder sein Stellvertreter) wieder da: https://www.message-encryptor.de
Wir hatten einen kurzen und von seiner Seite aus heftiger werdenden “Disput” auf Facebook, nach der Aussage seinerseits, es gäbe keinen Algorithmus war ich dann auch schon raus … so ein Humbug.
#24 Marc
9. Mai 2018

@Christian
Dies scheint wieder in Richtung OTP zu gehen, zumindest macht es den Eindruck, wenn er von Schlüsseldateien spricht. Ich hoffe dem Typ ist klar, dass man bei OTP den Schlüssel nur einmal verwenden darf, also jede Nachricht mit einem anderen Schlüssel verschlüsselt werden MUSS !
- #25 Christian
  10. Mai 2018
  
  Ja, seine Beschreibung ging in die Richtung, er schrieb in etwa: “… Es gibt keinen Algorithmus außer, dass zufällige Werte aus einer Reihe von möglichen Werten ausgesucht werden. …”. Daran stören mich zwei Dinge: “Es gibt keinen Algorithmus …”, was natürlich Humbug ist, und “ausgesucht”. Ich denke mir auch, dass die Zufallswerte nicht durch Hardware erzeugt werden (irgendein Rauschgenerator), sondern Pseudozufall ist. Das “Aussuchen” ist vermutlich eine Art Salt, … vermutlich. Zum Schlüsselaustausch hat er nichts verlauten lassen …
#26 Marc
21. Oktober 2018

@Christian
Ein kleiner Nachtrag hierzu. Auf http://www.Message-Encryptor.de beschreibt er doch, wie es funktioniert. Und die Lösung für den Schlüsselaustausch ist hier natürlich auch ganz einfach : die gute alte Post 🙂
Ich muss also erstmal USB-Sticks mit Schlüsseldateien mit der Post hin- und herschicken, um überhaupt kommunizieren zu können. Da wird sich wohl in Zunkunft so mancher NSA-Mitarbeiter bei der Deutschen Post bewerben.
#27 Mike
11. Juli 2019

Die Seite kryptochef.net leitet inzwischen direkt auf verschiedene Scam Kampagnen weiter. Ist in etwa dasselbe Niveau, aber vielleicht kann man trotzdem den Link löschen?
#28 Wandee Thaweetham
Chanthaburi - Thailand
14. April 2022

@Chefin
Hex 40 = @ and Hex 41 = A in ASCII
@skateddy
Geheimer Schlüsselaustausch

Schlage vor ihr beide lest was Shannon eigentlich über den Vernam Cipher geschrieben hat. Es war eine Analyse des Verfahrens, das für jeden Plaintext Buchstaben einen eigenen nicht wiederholbaren Schlüsselbuchstaben benötigt. RMLM ≤ RKLK

Sollte der Plaintext in seiner Länge die Anzahl der verfügbaren Schlüsselbuchstaben überschreiten, schlägt Shannon einen ‘Markoff process’ vor, der die Buchstaben mit Symbolen ersetzt um den benötigten Schlüssel zu erstellen.

Shannon’s Analyse verlangt aber auch, dass der Plaintext ein Produkt ist das sinnvoll ist. Wenn unser Plaintext aber eine willkürliche Auswahl von Buchstaben ist, zum Beispiel 2000 Buchstaben, dann hat der Schlüssel keine Bedeutung mehr. Ein oder zwei Buchstaben sind genug um den ganzen Text zu verschlüsseln. Der Cipher hält für jeden Cipher Buchstaben immer eine 1/n (n= Anzahl der Buchstaben in dem Alphabet das benutzt wird).

Es sollte keine Schwierigkeit sein einen Schlüssel der ein oder zwei Buchstaben besitzt unbemerkt auszutauschen.