Ein Artikel von Koblitz-Menezez setzt sich mit unsicheren Verschlüsselungsverfahren (oder zumindest unvollständigen Sicherheits-Beweisen) auseinander.

Traditionally, the security of a public-key system rests upon the assumed difficulty of a certain mathematical problem. Hence, newcomers to the field would logically expect that the problems that are used in security proofs come from a small set of extensively studied, natural problems. But they are in for an unpleasant surprise. What they encounter instead is a menagerie of ornate and bizarre mathematical problems whose presumed intractability is a basic assumption in the theorems about the security of many of the cryptographic protocols that have been proposed in the literature.

In der aktuellen Ausgabe der Notices of the AMS gibt es einen Artikel The Brave New World of Bodacious Assumptions in Cryptography von Koblitz und Menezez.

Bodacious mußte ich auch erst im Wörterbuch nachschlagen, dort findet man: ‘aufregend, großartig, riesig, toll’. Also: “Die schöne neue Welt der großartigen Annahmen in der Kryptographie”.

Es geht um Public Key-Kryptographie, also um die Verschlüsselungsverfahren, die heute bei jeder elektronischen Kommunikation im Internet, Handy oder am Bankautomaten benutzt werden (siehe K 8).

Diese Public Key-Verfahren beruhen alle auf “Einwegfunktionen”: Funktionen y=f(x), die leicht berechenbar sind, für die aber die Umkehrfunktion x=f-1(y) schwer zu berechnen ist.

In der Praxis werden vor allem 2 Verfahren verwendet:
– RSA (siehe K 3): baut darauf auf, daß man leicht Primzahlen multiplizieren kann, es umgekehrt aber schwierig ist, große Zahlen in Primfaktoren zu zerlegen
– ECC (siehe K 10): baut darauf auf, daß man bei einer elliptischen Kurve leicht die ‘Vielfachen’ eines Punktes P berechnen kann, es aber schwierig ist, aus nP wieder P zu berechnen.

Als sicher gelten die Verfahren, wenn man keine Entschlüsselungsverfahren in subexponentieller Zeit findet (siehe K 13). Viele kryptographische Forschungsarbeiten beschäftigen sich deshalb mit der Suche nach schnellen Entschlüsselungsverfahren. Ein Ansatz, der von Koblitz und Menezes in Frage gestellt wird:

Traditionally, many mathematicians working in cryptography have tended to regard the question of security of a type of public-key system as equivalent to hardness of inverting the underlying one-way function.
However, this answer to the security question is woefully inadequate. In the first place, the implication goes only one way: if the underlying problem is efficiently solvable, then the system is insecure; but if it is intractable, the system is not necessarily secure.

Das wird dann am Beispiel von RSA ausgeführt, u.a. verweisen sie auf den Artikel Breaking RSA may not be equivalent to Factoring von Boneh und Venkatesan.
Nebenbei wird noch erklärt, daß es aus heutiger Sicht mit den heutigen Erkenntnissen vor 20 Jahren besser gewesen wäre, nicht auf RSA, sondern auf das Rabin-Williams-Verfahren zu setzen. Dafür sei es jetzt aber zu spät: “In the real world, however, it is too late for that. Because of progress in factoring, for the highest security it is now recommended that 15360-bit N be used for any factorization-based cryptosystem. Meanwhile, the very highest security level with ECC requires q of 571 bits. Thus, users of RSA who are willing to change their software to accommodate a different system are going to switch to ECC, not to Rabin-Williams. If [4] had been published twenty years earlier, the history of digital signatures might have been very different.”

Im Gegensatz zu RSA, wo die Äquivalenz der Entschlüsselung zur Primfaktorzerlegung unklar ist, geht man bei ECC davon aus, daß die Sicherheit äquivalent zur Unlösbarkeit der Berechnung ‘diskreter Logarithmen’ (siehe K 7) ist.

Im Hauptteil des Artikels setzen sich die Autoren dann mit verschiedenen neueren Verfahren auseinander, es geht um:

Pairing-based Cryptography
– die Boneh-Boyen-Signatur
Ordered Multi-Signatures (ein Verfahren “to secure routing of messages through a network”),

und sie begründen, teilweise recht polemisch, warum sie mit den Beweisen der Sicherheit dieser Verfahren nicht einverstanden sind.

Trotzdem braucht man, so Koblitz und Menezez in ihrer Konklusion, seine Kreditkarten nicht wegzuwerfen oder auf Online-Einkäufe zu verzichten:
“In the first place, fallacies found in proofs of security do not necessarily lead to an actual breach. […] In the second place, cryptographic protocols are not developed and marketed in the real world unless they have been approved by certain industrialstandards bodies.[…]”

Disclaimer: Ich kann nicht beurteilen, ob die Einschätzungen der Autoren zutreffen. Koblitz ist einer der Erfinder von ECC und als solcher sicher kein unbeteiligter Beobachter.

Quelle:
The Brave New World of Bodacious Assumptions in Cryptography
Intractable Problems in Cryptography

Teil 1, Teil 2,Teil 3, Teil 4, Teil 5, Teil 6, Teil 7, Teil 8, Teil 9, Teil 10, Teil 11, Teil 12, Teil 13

Kommentare (4)

  1. #1 Stefan
    19. April 2010

    Da ich eher im biologischen Bereich zu Hause bin, hab ich natürlich keine Ahnung von der grundlegenden Materie. Ich habe mich jedoch ein bisschen mit Kryptographie für den “Hausgebrauch” beschäftigt und zwei Dinge wurden mir sehr schnell klar:

    Erstens ist jede Methode nur auf einem bestimmten Niveau wirklich sicher und zumindest theoretisch kann auch der sicherste Schlüssel per Brute-Force und seeeehr viel Glück schnell geknackt werden.

    Zweitens ist jedes Verschlüsselungsverfahren nur so sicher, wie das Drumherum, welches es anwendet. Das kann z.B. entweder mit der verwendeten Infrastruktur bzw. Software oder dem Userverhalten scheitern. Daher wird jemand, der an bestimmte Informationen will, mit ziemlicher Sicherheit versuchen, an Codes und geheime Schlüssel zu kommen. (s. EC-Karten, usw.) Das mathematische Knacken des geheimen Schlüssels dürfte in der Praxis sehr mühsam sein.

    Soviel zur Praxis. In der Theorie kann ich leider nicht mitreden. 😉

  2. #2 Hanno
    19. April 2010

    Ich möcht mal ein paar Ergänzungen, bzw. Korrekturen anbringen. “Elliptische Kurven” sind erstmal kein direktes Kryptoverfahren, was da verwendet wird ist El Gamal. Das wird allerdings nach wie vor weit häufiger “normal”, also ohne elliptische Kurven, eingesetzt (ist auch unter dem Namen DSA zu finden).

    Was man bei den elliptischen Kurven macht, ist, den selben Algorithmus zu nutzen, aber halt auf einem anderen Zahlenraum, eben den elliptischen Kurven.

    Bei El Gamal geht man davon aus, dass es so sicher wie das darunterliegende Problem (diskreter Logarithmus) ist, aber ich glaube bewiesen ist das auch nicht. Müsste ich aber nachrecherchieren. Dass RSA nicht bewiesen so sicher ist wie Faktorisierung ist eigentlich bekannt, allerdings geht glaub ich auch niemand wirklich davon aus, dass es nicht so ist. Es gibt zumindest keinerlei Angriffe die sich das zunutze machen würden.

    Benutzt man nun als Basis von El Gamal elliptische Kurven, so behaupten einige, sei das mit viel kürzeren Schlüssellängen genauso sicher. Das wird aber von führenden Kryptografen angezweifelt. Das Problem dabei ist, dass diese Verfahren und auch die darunterliegenden Probleme weit weniger untersucht sind. Insofern nehmen viele an, dass ECC nur deshalb “sicherer” sind, weil sie weniger gut untersucht wurden. Bruce Schneier etwa dazu:
    http://www.schneier.com/crypto-gram-9911.html#EllipticCurvePublic-KeyCryptography

    So, hoffe ein bißchen zur Verwirrung beigetragen zu haben 😉

  3. #3 derari
    28. April 2010

    Beruht nicht Verschlüsselung an sich auf der unbewiesenen Vermutung dass NP != P ist? So gesehen ist doch kein Verfahren (außer one-time pad) sicher…

  4. #4 Thilo Kuessner
    28. April 2010

    P=NP hieße erstmal nur, daß man in polynomieller Zeit entschlüsseln könnte. Wie groß die Polynome sind, wäre dann eine ganz andere Frage. Man arbeitet ja nicht mit ‘beliebig großen’ Schlüsseln, sondern immer mit Schlüsseln einer bestimmten Größenordnung. da spielt es imho keine so große Rolle, ob die Entschlüsselungszeit polynomiell ist, sondern welche Werte sie für die gerade gebräuchliche Schlüssellänge annimmt. Siehe auch bohem’s Kommentar zu http://www.scienceblogs.de/mathlog/2009/03/kryptographie-xiii.php