« vorheriger Beitrag  · nächster Beitrag »

19.04.10 · 00:00 Uhr

Kryptographie XIV

Kategorie: Technik  ·  Kommentare: 4

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

 

Autor: Thilo· 4 Kommentare· Permalink· Trackback-URL

Tags: ECC· Koblitz· Kryptographie· Menezez· RSA· Sicherheit· Zahlentheorie