Snake-Oil-2-Bar

Warum 128 Schlüsselbits nutzen, wenn man auch eine Million Schlüsselbits haben kann? Um solche und ähnliche Merkwürdigkeiten geht es im zweiten Teil der Miniserie über kryptologisches Schlangenöl.

Zu Teil 1/3

Beispiel 4: KRYPTO nach Art des Chefs

Schlangenöl (so nennt man schlechte Verschlüsselungstechnik) ist nur ein historisches Phänomen? Stimmt nicht, schrieben mir die Leser Christian Berger und Chemiker. Zumindest ein Anbieter präsentiert sich heute noch wie zu besten Schlangenöl-Zeiten Ende der Neunziger: der Kryptochef mit seinem Produkt KRYPTO.

Die Skurrilitäten auf der Web-Seite des Kryptochefs sind zahlreich:

  • „Das sicherste Datenverschlüsselungs Programm der Welt“ heißt es als Willkommensgruß in großen Lettern. Ich bin beeindruckt.
  • Der Autor von KRYPTO bittet um Spenden. Wenn die Gesamtsumme von 2 Millionen Euro zusammenkommt, will er das Programm zur einer frei verfügbaren Software machen. Ob da schon jemand gespendet hat?
  • „KRYPTO benutzt eine mehrfache 256 Bit (Vollbit) Verschlüsselung“, heißt es weiter. Angeblich ist das „die technisch höchste Verschlüsselungstiefe die überhaupt auf Computern möglich ist“. Interessant, das wusste ich bisher nicht.
  • Schön auch diese Passage: „Übrigens: Fachleute aus aller Welt behaupten öffentlich: Daten Verschlüsselung wo der Datei Schlüssel genauso lang ist wie die zu verschlüsselnden Datei sei absolut sicher vor unberechtigter Daten Entschlüsselung. Ihnen ist doch wohl jetzt klar das eine unberechtigte Daten Entschlüsselung einer von KRYPTO verschlüsselten Datei daher absolut ausgeschlossen ist, für alle Zeiten und jede Technik.“
  • Und nicht zuletzt bietet der Kryptochef die Summe von 200.000 Euro für denjenigen an, der das System knacken kann. Dazu wäre aber erst einmal eine Spezifikation notwendig, die es natürlich auf der Web-Seite nicht gibt.

130 Euro will der Kryptochef für sein Programm haben (Zitat auf der Web-Seite: „eigentlich ist das zu billig“). Ein weiteres Zitat: „Den wahren Wert dieser Software werden vermutlich nur Fach Leute und Firmen erkennen.“ Dem kann ich nur zustimmen.

Beispiel 5: 1 Million Bit Schlüssellänge

Ein wahres Musterbeispiel für Schlangenöl stammte von einer US-Firma. Deren Verschlüsselungssystem namens VME setzte nach den Angaben auf der Webseite auf eine sogenannte virtuelle Verschlüsselungsmatrix, von der wieder einmal kein Mensch wusste, was sich dahinter verbarg. Rekordverdächtig war immerhin die Schlüssellänge. Diese lag bei einer Million Bit! Selbstverständlich fehlte der Hinweis nicht, dass herkömmliche Systeme mit nur etwa 40 bis 160 Bit arbeiteten. Und dann wurde noch „bewiesen“, dass VME genau so sicher war wie der One-Time-Pad. Wer’s glaubt, wird selig.

Beispiel 6: Enigma statt DES

„Professional Cryptography Software“ versprach 1996 die amerikanische Firma Enigma & Co auf ihrer Webseite. Immerhin machte das Unternehmen kein Geheimnis aus der Funktionsweise seiner Verschlüsselungssoftware. Wie der Name andeutete, verwendete diese eine Rotorchiffre nach Vorbild der Enigma. Obwohl diese Form der Verschlüsselung schon 60 Jahre zuvor unsicher war, pries Enigma & Co. sein Produkt für sicherheitsrelevante Daten an (als Spielerei für Enigma-Fans wäre es ja noch verständlich gewesen). Unter diesen Umständen muss man auch die Enigma als Schlangenöl bezeichnen.

Beispiel 7: Das gelöste PNP-Problem

In der theoretischen Informatik bezeichnet man die Menge der Probleme, die eine deterministische Turingmaschine in polynomialer Zeit lösen kann, als P. Da derartige Algorithmen vergleichsweise performant sind, kann man P auch als die Menge der effektiv lösbaren Probleme bezeichnen. Die Menge der Probleme, die eine nichtdeterministische Turingmaschine in polynomialer Zeit lösen kann, wird dagegen als NP bezeichnet. Probleme, die in NP, aber nicht in P liegen, sind nicht effektiv lösbar.

Sämtliche Erkenntnisse der letzten Jahrzehnte deuten darauf hin, dass es Probleme gibt, die in NP, aber nicht in P liegen. Das Faktorisierungsproblem und das diskrete Logarithmus-Problem sind Kandidaten dafür. Trotz allem hat bis heute noch niemand bewiesen, dass es NP-Probleme gibt, die nicht in P liegen. Es könnte also theoretisch sein, dass P=NP gilt. Dies hieße dann, dass alle Krypto-Systeme, die auf dem Faktorisierungsproblem oder dem diskreten Logarithmus-Problem basieren, möglicherweise unsicher sind – insbesondere wären davon auch RSA, DSA und Diffie-Hellman betroffen.

1 / 2 / Auf einer Seite lesen

Kommentare (21)

  1. #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. #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.

  3. #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.

  4. #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.

  5. #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.

  6. #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.

  7. #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.

  8. #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.

  9. #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!!

  10. #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.

  11. #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)…

  12. #14 haarigertroll
    21. August 2013

    Mit dem Kryptochef kann man übrigens reich werden: http://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)!

  13. #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.

  14. #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! :-)

  15. #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.

  16. #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.

  17. #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.

  18. #20 Robert
    Wien
    20. Februar 2016

    Anscheinend dürfte der Kryprochef aufgegeben haben: die Webseite gibt es offenbar nicht mehr. (Eigentlich schade.)

  19. #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?