ECC: Paradigmen der Elliptische-Kurven-Kryptographie

The Serpentine Course of a Paradigm Shift.

Im Beitrag über die Video-Abstrakts beim “Journal of Number Theory” (Doch kein Aprilscherz III) hatte ich den Artikel Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift erwähnt.

In dem Artikel geht es um die Geschichte von ECC (Elliptische-Kurven-Kryptographie), und auch um deren Einordnung unter Gender- und Konstruktivismus-Aspekten.
Zu den beiden letzteren Aspekten kommen noch zwei getrennte Beiträge, hier will ich nur kurz den Inhalt des Artikels referieren.

Research into number theoretic questions concerning elliptic curves was originally pursued mainly for aesthetic reasons.

beginnt der Artikel, darauf anspielend, daß elliptische Kurven lange “nur” ein zentrales Thema der Mathematik mit überwiegend inner-mathematischen Anwendungenwaren,

erwähnt dann die Einführung elliptischer Kurven in die Kryptographie 1985 durch Koblitz und Miller,

und zitiert aus der NSA-Ankündigung, Verschlüsselung im Internet in den nächsten Jahren auf ECC umzustellen.

Die Geschichte der ECC (und der Diskussionen über die Sicherheit von ECC) soll dann als eine “case study in the history of technology” untersucht werden, und die Autoren wollen klären, ob die Ideen der “Social Construction of Technology” zu einem besseren Verständnis der ECC-Geschichte beitragen können.

Offensichtlich sind in der Kryptographie Paradigmen wichtiger als anderswo. Die Autoren machen zunächst, um dies geklärt zu haben, 5 Paradigmen für die Kryptographie fest:

1. Security always at center stage,
2. From an art to science,
3. Tradition of vigorous debate,
4. Special institutions to ensure careful vetting,
5. Survival of the fittest.

Auf den nächsten 30 Seiten wird dann ein Abriß über 25 Jahre ECC gegeben, das liest man besser im Original.
Interessant (und spekulativ) ist am Ende ein Abschnitt über Historical what-ifs

One of the best ways to refute the technological determinist view of the history of cryptography that is implicit in the Ideal Model iis to ask some hypothetical questions of the form “What if…?”:
- What if in 1977 someone who had just written a Ph.D. thesis on elliptic curves had happened to read [...]
- What if the ideas described in §10 for finding discrete logs on an elliptic curve E over Fqm — Weil descent followed by index calculus on a jacobian group, or index calculus directly on E using points with x-coordinate in Fq as the factor base — had been proposed in the late 1980s or early 1990s? [...]
- What if pairing-based cryptography had been proposed just three or four years earlier [...]

Die Antwort der Autoren ist letztlich, daß die Geschichte der Kryptographie ganz anders hätte verlaufen können. (Ihre Antwort auf die erste Frage ist, daß sich RSA wahrscheinlich nicht durchgesetzt hätte. Man denkt natürlich, daß es besser gewesen wäre, solche Fragen von unabhängiger Seite diskutieren zu lassen – einer der Autoren ist ja Begründer von ECC und als solcher sicher nicht unvoreingenommen.)

Danach wird dann noch ‘narrative inversion’ erörtert, zunächst an einem hypothetischen politischen Beispiel

Take the hypothetical example of a country whose official version of its history is that the guiding principle of its foreign policy has been to “defend freedom.” Even though people in other countries might see an ever-widening chasm between this national myth and the reality, the narrative continues to be a centerpiece of the belief system of millions of people, who proclaim it with increasing fervor.

- auch hier stellt sich natürlich, unabhängig davon ob man inhaltlich zustimmt, die Frage, ob solche persönlichen Meinungsäußerungen nicht eher Zweifel an der Objektivität des Artikels wecken; ebenso wie bei der folgenden Polemik, der man viellicht inhaltlich zustimmen mag, die aber doch eigentlich nicht in eine wissenschaftliche Arbeit gehört:

In the world of scholarship as well, one often encounters narrative inversion.
Take, for example, the word science. Often the humanistic and social areas whose practitioners are the most insistent on using this word are those fields that have the worst track record in attempting to use scientific methodology. In the last century the term “social studies” was replaced by “social sciences,” and departments of government became departments of “political science.” Interestingly, the one profession in social studies that arguably uses a fair amount of scientific methodology and does it competently — history — has never insisted on changing its name to “historical science.”

Jedenfalls werden dann (auf Seite 32/33) unter der Überschrift “narrative inversion in cryptography” einige Thesen anderer Autoren (Bellare) zur Kryptographie kritisiert.

Auf den letzten 6 Seiten werden schließlich die Aspekte ‘Gender’ und ‘Social Construction of Technology’ besprochen, dazu in den nächsten beiden Beiträgen. (Nachtrag: Die Beiträge sind hier und hier.)

Das Fazit der Autoren ist jedenfalls:

Our examination of the history of ECC offers no support to those who wouldargue that technology follows an inevitable path that is independent of societalconstraints. Rather, the evidence points toward ways in which technology is socially constructed:

• path-dependence — the importance of timing, the role of happenstance;

• the role of the military in intervening at crucial stages to send the technologyin a different direction from that favored by market forces;

• closure — the need eventually to reach a consensus and stop most debate, evenif some basic questions remain unanswered;

• narrative inversion — a desire to use high-status terms such as “science” and”mathematical proof” that becomes more fervent even as the field is showing itselfagain and again to be as much an art as a science

Koblitz, A., Koblitz, N., & Menezes, A. (2009). Elliptic curve cryptography: The serpentine course of a paradigm shift Journal of Number Theory DOI: 10.1016/j.jnt.2009.01.006

Kommentare

  1. #1 Wb
    21. April 2010

    Schwierige Überlegungen, das Web hätte, auch was die geschäftsbasierten Anwendungen betrifft, mit symmetrischer Verschlüsselung funktioniert.

    Zur ideologischen Untermauerung des Vortrags der dritten Seite hat der Webbaer ansonsten durchaus eine pos. Einstellung, gesellschaftlich wichtige Erfindungen gehen oft Hand in Hand, die “Was wenn”-Fragen bieten sich an, der “Art”-Aspekt der Sache bleibt dagegen ein wenig unklar.

    Assymmetrische Verschlüsselung hat eine wichtige politische Bedeutung.

    Schwieriger Text, sehr interessant,
    MFG
    Wb

  2. #2 Thilo Kuessner
    21. April 2010

    das Web hätte, auch was die geschäftsbasierten Anwendungen betrifft, mit symmetrischer Verschlüsselung funktioniert.

    Das ist definitiv nicht wahr. ‘Symmetrische Verschlüsselung’ bedeutet, daß auch der Schlüssel übers Netz übertragen wird. (Bei ‘asymmetrischer Verschlüsselung’ muß dder Schlüssel nicht übertragen werden.) Bei symmetrischer Verschlüsselung könnte ein Hacker, der die verschlüsselte Nachricht abfängt, genausogut auch den Schlüssel abfangen.

    Ich zitiere mal aus der Wikipedia:
    “Der große Nachteil symmetrischer Verfahren liegt in der Nutzung ein- und desselben Schlüssels zur Ver- und Entschlüsselung, d. h. neben der verschlüsselten Information muss auch der Schlüssel übermittelt werden. Das Problem beim Einsatz symmetrischer Verfahren ist, dass der Schlüssel über einen sicheren Kanal übertragen werden muss, denn die Sicherheit des Verfahrens hängt von der Geheimhaltung des Schlüssels ab. Früher wurde der Schlüssel typischerweise durch einen Boten persönlich überbracht. Seit den 1970er Jahren werden zum Schlüsselaustausch asymmetrische Verschlüsselungsverfahren (zum Beispiel basierend auf dem Diffie-Hellman-Algorithmus) eingesetzt, um den symmetrischen Schlüssel selbst zu verschlüsseln und ihn so über einen unsicheren Kanal übertragen zu können. Bei der Kommunikation können mit dieser Hybriden Verschlüsselung also die Vorteile (beispielsweise die höhere Geschwindigkeit) der symmetrischen Verschlüsselung ausgenutzt werden, während der Schlüssel durch die asymmetrische Verschlüsselung vor dem Zugriff eines Angreifers geschützt wird.”

    Assymmetrische Verschlüsselung hat eine wichtige politische Bedeutung.

    Da verwechseln Sie vielleicht irgendwas. Mit den Diskussion bzgl. staatlicher Überwachung, Datenspeicherung etc. hat diese Frage jedenfalls nichts zu tun.

    (Oben im Text geht es übrigens ausschließlich um asymmetrische Verfahren, konkret um den ‘Wettbewerb’ zwischen RSA und ECC.)

  3. #3 Wb
    21. April 2010

    @Thilo
    Der Schlüssel kann eben auch webfremd übertragen werden und wäre auch ganz vermutlich webfremd übertragen worden um Webgeschäfte zu ermöglichen.

    Der Wb verwechselt zu Punkt 2 gar nüscht, sondern merkt (“nur”) an.
    Der Wb hat aber idT gewisse Kenntnismängel ECC betreffend, verstand aber das hypothetische politische Beispiel als in eine Richtung gehend, die auch RSA unterstützt.

    Sie dürfen gerne die in diesem Zusammenhang relevanten Unterschiede erläutern, die “narrativer” Art zu sein scheinen; vermutlich sind wichtige Aspekte (auf Seite des Wb natürlich :-) unerkannt geblieben.

    Vielen Dank für diesen interessanten Blogeintrag!

    MFG
    Wb

  4. #4 Thilo Kuessner
    21. April 2010

    Der Schlüssel kann eben auch webfremd übertragen werden und wäre auch ganz vermutlich webfremd übertragen worden um Webgeschäfte zu ermöglichen.

    In der Praxis würde das heißen: jedesmal wenn Sie Kunde bei irgendeinem Warenhaus, Reisebüro, Online-Buchhändler,… werden wollen, müßten Sie sich vorher eine TAN-Liste “webfremd” (per Brief) zuschicken lassen. Spontankäufe im Internet wären unmöglich.

  5. #5 Wb
    21. April 2010

    Wir haben auch im Web letztlich immer an einer Stelle ein (übrigens oft ziemlich fehlerhaft funktionierendes) Identitätsfeststellungsverfahren (vgl. auch Postident, andere Postdienstleister bieten Vergleichbares an), das fehlerhaft sein kann, d.h. ein “Springen” (zwischen mathematischem Modell bzw. zu diesem und der Realität) ist ohnehin erforderlich im Web, was sogar – in gewisser Hinsicht – für die symmetrische Verschlüsselung spricht.

    Auch bspw. Ihre Person wurde seitens der SB-Redaktion vermutlich (physikalisch, vor Ort und so :-) festgestellt.
    TAN-Listen und ähnliches sind “webtechnisch” nur eine zweite Sicherheitsschicht auf einer autorisierten (nach zuvor erfolgter Authentifikation natürlich) liegenden ersten.

    Aber gu-ut, man kommt langsam vom Thema weg, Webphilosophie ist jedenfalls ein spannendes Thema,
    MFG
    Wb

  6. #6 Thilo Kuessner
    21. April 2010

    Lesen Sie sich doch einfach erstmal die Wikipedia-Artikel zu symmetrischer und asymmetrischer Verschlüsselung durch, bevor Sie hier irgendwelche völlig aus der Luft gegriffenen Behauptungen aufstellen.
    Es geht einfach darum: bei asymmetrischer Verschlüsselung können verschlüsselte Daten direkt übers Netz übertragen werden – ohne daß man vorher den Schlüssel auf anderem Wege (d.h. durch Brief) übermittelt hat.
    Es geht NICHT darum, ob man sich erst identifizieren muß oder nicht, sondern um die “abhörsichere” Übertragung der Daten (ob das nun personenbezogene oder irgendwelche anderen sind).

  7. #7 Wb
    21. April 2010

    Der Wb hat die bdzgl. Wikipedia-Artikel geschrieben! – Nein im Ernst, Sie können auch bei webfremder Übertragung des Schlüssels, in diesem Fall symmetrisch, Daten sicher von A nach B übertragen, ansonsten (oder vielleicht besser: “überhaupt”) wiederholen Sie Bekanntes.

    Aber bevors sich wieder aufheizt,
    Ade,
    Wb

  8. #8 Thilo Kuessner
    21. April 2010

    Sie können auch bei webfremder Übertragung des Schlüssels, in diesem Fall symmetrisch, Daten sicher von A nach B übertragen,

    Ja, das können Sie, indem Sie die Daten per Brief schicken. Hab ich verstanden. Es dauert dann nur ein paar Tage länger, aber sonst ist es kein Problem.

  9. #9 Wb
    21. April 2010

    Es wurde halt die Schnittstelle “Realität-IT” ein wenig besprochen, selbstverständlich sind assysmmetrische Verfahren ausgesprochen hilfreich, auch wenn eben letztlich nicht zur Realität “gesprungen” wird oder werden soll, also keine ID-Kontrolle stattfindet.

    Bei vielen Anforderungslagen ist eine physikalische Identifizierung nicht vonnöten, gerade in problematischen und “totalitären” Systemen ist die Hauptanforderung nicht die Sicherstellung der physikalischen Identität des Nutzers, sondern die Sicherstellung der Eindeutigkeit der Nutzer als Teilnehmer.

    So sollten die Beiträge des kleinen Bären verstanden worden sein, hier entsteht ein nicht zu unterschätzender zivilisatorischer Nutzen, hier könnte ein Anschluss gefunden werden an die Vorträge/Argumentationen der dritten Seite.

    Wobei eben die Herausstellung der ECC-Kryptologie vs. RSA seitens des Wb noch ungefressen blieb.
    Aber vermutlich ein Nebenaspekt, da narrative Erläuterungen doch eigentlich für alle assymmetrischen Systeme greifen könnten.

    MFG
    Wb

  10. #10 Thilo Kuessner
    21. April 2010

    Es geht bei asymmetrischen Verfahren gerade NICHT um die ‘physikalische Identifizierung’, sondern um einen automatisierten sicheren Schlüsselaustausch OHNE daß der Teilnehmer sich erst außerhalb des Netzes legitimiert haben muß. Ihre Argumente sind also Argumente GEGEN symmetrische Verfahren.

  11. #11 Tom
    21. April 2010

    @Thilo

    Neben dem Internet gibt es noch ein weiteres Netzwerk welches viel mehr Benutzer hat. Nämlich das Telefon/Handynetz. Dieses funktioniert. Und unsere Handynetze basieren auf symmetrischer Kryptographie.
    Das ist ein enormer Verwaltungsaufwand. Und funktionieren tut es wohl nur, weil es ein kommerzielles Netz ist. Der Verwaltungsaufwand ist natürlich wesentlich höher. Bei solch einer Lösung benötigt man auch eine trusted Third Party. Mit dieser mit jeder Benutzer einmal einen Key austauschen.
    Bild:
    http://dl.dropbox.com/u/9637/Screen%20shot%202010-04-21%20at%208.24.37%20PM.png

    Wenn jetzt Alice und Bob sicher kommunizieren wollen, müssen sie mit Hilfe dieser Partei einen einen symmetrischen Schlüssel austauschen.

    Die Trusted Party ist natürlich ein “Single point of failure”. Assymetrische Kryptographie mit Zertifikaten funktioniert deshalb natürlich viel besser. Andererseits ist das System der DNS Server auch ein single point of failure und es funktoniert trotzdem.

    Das alles lässt sich ziemlich gut in dem Buch “IT-Sicherheit” von Frau Eckert nachlesen.
    http://de.wikipedia.org/wiki/Claudia_Eckert

    Sicherheit im Web würde wohl also auch mit symmetrischer kryptographie funktionieren.

    Trotzdem bin ich natürlich deiner Meinung, dass assymetrische Kryptographie ein tolle Sache ist.

  12. #12 Tom
    21. April 2010

    Ich beziehe mich übrigends lediglich auf diesen Abschnitt:

    ##########
    WB
    das Web hätte, auch was die geschäftsbasierten Anwendungen betrifft, mit symmetrischer Verschlüsselung funktioniert.

    Thilo:
    Das ist definitiv nicht wahr. ‘Symmetrische Verschlüsselung’ bedeutet, daß auch der Schlüssel übers Netz übertragen wird. (Bei ‘asymmetrischer Verschlüsselung’ muß dder Schlüssel nicht übertragen werden.) Bei symmetrischer Verschlüsselung könnte ein Hacker, der die verschlüsselte Nachricht abfängt, genausogut auch den Schlüssel abfangen.
    #############

    Und ich glaube übrigends auch, dass WB mal den Wikipedia Artikel lesen sollte :)
    Trotzdem bin ich der Meinung, dass das Web wohl auch mit symmetrischer Verschlüsselung funktionieren würde. Die “normalen” internet Nutzer müssten sich lediglich einmal irgendwo einen Schlüssel kaufen. Schwieriger als einen Handyvertrag zu unterschreiben dürfte es nicht sein.

  13. #13 Tom
    21. April 2010

    Okay, noch eine Ergänzung. Selbstverständlich gibt es mit asymetrischer Kryptographie Dinge, welche sich NIE mit der Symmetrischen machen lassen. Signaturen zum Beispiel. Ich bezog mich nun aber lediglich auf das Vertraulichkeitskriterium.

  14. #14 Thilo Kuessner
    22. April 2010

    @ Tom:
    Wenn ich es richtig verstehe, tauscht der Handynutzer mit dem Netzanbieter einmal einen (im Handy implementierten) Schlüssel aus.
    Bei wem sollte man als Webnutzer den einen Schlüssel erwerben? Sinnvollerweise wohl bei der Firma, die den Browser zur Verfügung stellt? Problem ist nur, daß man Browser kostenlos aus dem Netz herunterlädt und es keinen Browser-Vertrag gibt, bei dessen Unterzeichung der Händler einem den Schlüssel aushändigen könnte :-)

    Gibt es eigentlich Untersuchungen, ob Handy-Kommunikation genauso abhörsicher ist wie Online-Einkäufe übers Internet?

  15. #15 rolak
    22. April 2010

    GSM ist =»nicht sicher.

  16. #16 Tom
    22. April 2010

    Die GSM ist soweit ich weiß nicht mehr sicher, UMTS schon.
    Das Problem bei GSM ist wohl aber lediglich, dass der dort verwendete Algorithmus nicht so sicher ist auch auch noch manchmal schlecht implementiert ist.
    Eine gute Quelle konnte ich jetzt auf die Schnelle aber nicht finden.

    Dei Computer könnte man das so einsetzen, dass eine Art “Sim-karte” mit dem Schlüssel wie beim Handy eingesteckt wird. Diese Karte wird von der Trusted third Party zur Verfügung gestellt. Das könnte der Internetprovider oder auch jede andere Firma sein. Sobald der Benutzer solch eine Karte hat kann er mit allen anderen Benutzern sicher kommunizieren.

    Es besteht dann natürlich die Gefahr, dass jemand den Schlüssel des Benutzers klaut/austauscht. Dieses Problem besteht bei der asymmetrischen Kryptographie aber auch. Diese ist ebenfalls angreifbar, indem man zum Beispiel bei einem Rechner die öffentlichen Schlüssel austauscht.

    Das im Mobilfunk aber solch ein unnötig kompliziertes System dahinter steckt, liegt wohl allein daran, dass kommerzielle Interessen dahinter stehen. Wer hätte im Internet schon ein Interesse solch ein kostenintensives System zu aufzuziehen, wenn es auch wesentlich günstiger geht.

  17. #17 Tom
    22. April 2010

    #####
    Thilo:
    Wenn ich es richtig verstehe, tauscht der Handynutzer mit dem Netzanbieter einmal einen (im Handy implementierten) Schlüssel aus.
    ####

    Der Schlüssel ist auf der Sim-Karte.

  18. #18 mju
    24. April 2010

    Tom: Okay, noch eine Ergänzung. Selbstverständlich gibt es mit asymetrischer Kryptographie Dinge, welche sich NIE mit der Symmetrischen machen lassen. Signaturen zum Beispiel. Ich bezog mich nun aber lediglich auf das Vertraulichkeitskriterium.

    Es gibt aber MACs:
    http://de.wikipedia.org/wiki/Message_Authentication_Code

    Das ist quasi eine Art Signatur für symmetrische Verschlüsselungsverfahren. (Natürlich mit dem Nachteil, dass beide Seiten vorher einen gemeinsamen Schlüssel ausgetauscht haben und somit nur diese die “Signatur” auch verifizieren können.)

    Thilo: Ja, das können Sie, indem Sie die Daten per Brief schicken. Hab ich verstanden. Es dauert dann nur ein paar Tage länger, aber sonst ist es kein Problem.

    Oder per SMS, dauert nur ein paar Minuten. Handys gibt’s schon länger als Webshops.

    Thilo: Bei wem sollte man als Webnutzer den einen Schlüssel erwerben? Sinnvollerweise wohl bei der Firma, die den Browser zur Verfügung stellt?

    Nein. Bei den Firmen, die im Moment die Zertifikate für SSL ausstellen. Verisign, Thawte und Co. Technisch dürfte es auch nicht viel aufwendiger sein, wenn sich der Browser erst ein “Ticket” holt, bevor er eine verschlüsselte Verbindung aufbaut. Dafür müsste man sich zwar erst einmal bei einem “Trust Center” anmelden und die Daten fest im Browser speichern, aber technisch machbar ist das. Kerberos ( http://web.mit.edu/kerberos/#what_is) funktioniert meines Wissens so ähnlich, und kommt auch komplett mit symmetrischer Verschlüsselung aus.

    (Noch eine letzte Anmerkung: Schlüsseltausch und asymmetrische Kryptographie sind eigentlich zwei völlig unterschiedliche Dinge, die nur zufällig mit den gleichen Techniken gelöst werden können. Für Webshops braucht man eigentlich nur den Schlüsseltausch, oder hat schon mal jemand hier bei Verisign angerufen, um deren Zertifikat zu überprüfen?)

  19. #19 Thilo
    25. April 2010

    Oder per SMS, dauert nur ein paar Minuten.

    Also mich würde es schon ziemlich nerven, wenn man beim Einkauf im Internet immer erst eine Bestätigungs-SMS abwarten muß, bevor man seine Bestellung aufgibt. Auch wenn es nur ein paar Minuten dauert.

  20. #20 mju
    27. April 2010

    Thilo: Also mich würde es schon ziemlich nerven, wenn man beim Einkauf im Internet immer erst eine Bestätigungs-SMS abwarten muß, bevor man seine Bestellung aufgibt. Auch wenn es nur ein paar Minuten dauert.

    Klar. Aber es wäre technisch machbar, ohne dass man asymmetrische Kryptographie benötigt, das war mein Punkt. (Und wenn es nur um Schlüsseltausch ginge, wie im ursprünglichen Argument, benötigte man das auch nur einmal pro Webshop. Ob man auf eine Email zur Bestätigung einer Anmeldung wartet oder auf eine SMS ist dann auch egal, das dürfte etwa gleich schnell sein.)

  21. #21 derari
    28. April 2010

    “Aber es wäre technisch machbar”
    Technische Machbarkeit ist aber nicht das einzige Qualitätskriterium. Die Entwicklung eines solchen Systems wäre teuer und die Benutzung abschreckender.
    Als Folge daraus hätten sich diese Dienstleister nicht so schnell entwickeln können.
    Außerdem müssen die Schlüssel lang sein. Und nehmen wir an, es gäbe eine Technologie, die die Daten automatisch vom Handy zum Rechner überträgt, müssten die Schlüssel immernoch regelmäßig erneuert werden. Der aktuelle WLAN-Standard WPA2 ist nur deshalb sicher, weil alle 15min ein neuer Schlüssel benutzt wird.
    Dazu müsste auch die Handyverbindung sicher verschlüsselt werden. Das ginge dann nur per Post, man müsste als zB jeden Tag eine 20stellige TAN in sein Handy eingeben, um im Internet sicher zu surfen.