Einführung von Zero Knowledge-Beweisen für Private Web Attestation mit Hardware von mehreren Anbietern

Vor einigen Wochen haben wir die Cryptographic Attestation of Personhood eingeführt, um CAPTCHAs durch USB-Sicherheitsschlüssel zu ersetzen. Heute haben wir zudem auch die Unterstützung für geräteinterne biometrische Hardware bekanntgegeben. Bei dieser Arbeit kam uns der Gedanke: Hardware-Attestierung, d. h. der Nachweis der Identität oder anderer Eigenschaften eines Nutzers mithilfe eines Geräts, könnte viel umfassendere Anwendungen haben als nur CAPTCHA-Alternativen und Nutzerauthentifizierung über WebAuthn. Warum sollte jemand ein Konto anlegen müssen, um seine Existenz zu beweisen, wenn sein eigenes vertrauenswürdiges Gerät dazu in der Lage ist?

Nachweise im WebAuthn-Standard lassen Websites wissen, dass Ihr Sicherheitsschlüssel authentisch ist. Das Programm wurde so konzipiert, dass es über gute Datenschutzmerkmale verfügt, die bereits in den von den Geräteherstellern zu befolgenden Richtlinien verankert sind. Die Informationen, die Ihr Sicherheitsschlüssel an Websites sendet, unterscheiden sich nicht von den Informationen unzähliger anderer Schlüssel. Und trotzdem – wir wollten es besser machen. Wenn wir den Nachweis aus der Authentifizierung herausnehmen, müssen wir uns nur vergewissern, dass Ihr Sicherheitsschlüssel authentisch ist, mehr nicht. Und dafür haben wir einen neuen Zero Knowledge-Beweis für den Browser entwickelt.

Dies ist Teil unserer Bemühungen, den Datenschutz im Internet zu erhöhen. Noch ist der Proof of Personhood (Nachweis der Personenidentität) nicht marktreif, aber Sie können bereits eine Demonstration der Technik in Aktion sehen. Wir wissen, dass die Lösung unter anderem mit YubiKeys funktioniert. Das Wichtigste ist aber: Wir stellen den Code open-source zur Verfügung, damit jeder davon profitieren und etwas dazu beitragen kann. Im Folgenden finden Sie weitere Einzelheiten und die nächsten Schritte.

Der WebAuthn-Nachweis identifiziert den Hersteller Ihres Hardware-Sicherheitsschlüssels gegenüber der Website, die den Nachweis wünscht. Die Technologie war für den Einsatz in geschlossenen Umgebungen gedacht, z. B. für Finanzinstitute und interne Dienste, bei denen bereits eine Beziehung zwischen Ihnen und der Website besteht. Da Sie beim Einloggen identifiziert werden, sind die Folgen im Hinblick auf den Datenschutz minimal. Im Gegensatz dazu erfährt jede offene Website, die wie beim Proof of Personhood einen Nachweis verwendet, die Marke und das Modell des von Ihnen verwendeten Schlüssels.

Marken- und Modellinformationen wirken auf den ersten Blick nicht besonders vertraulich, so wie es sich auch bei der Marke und dem Modell Ihres Autos nicht unbedingt um vertrauliche Informationen handelt. Es gibt viele 2015er Prius-Modelle auf der Straße. Wenn jemand weiß, dass Sie einen Prius fahren, kann er sie dadurch nicht leichter identifizieren. Aber in Zusammenhang mit Informationen wie dem Nutzer-Agenten, den Sprachpräferenzen, der Tageszeit usw. können diese Informationen dazu beitragen, ein Bild des Nutzers zu erstellen – so wie demografische Angaben, Größe, Gewicht und Kleidung zusammen mit der Marke und dem Modell eines Autos es leichter machen, ein bestimmtes Auto auf der Autobahn zu identifizieren. Daher öffnet sich im Browser ein Dialogfenster, wenn eine Website diesen Nachweis erhält. So soll Nutzern verständlich gemacht werden, dass die Website Informationen erhält, die zu ihrer Identifizierung beitragen können. Wir nehmen Datenschutz ernst und möchten keine Informationen erhalten, die Sie identifizieren könnten.

Beispiel einer Browser-Warnung.‌‌

Die Informationen sind ein Nachweis dafür, dass der Hersteller Ihres Sicherheitsschlüssels diesen Schlüssel auch wirklich hergestellt hat. Es handelt sich dabei um eine digitale Signatur über einen privaten Schlüssel, die auf Ihrem Sicherheitsschlüssel in einer sicheren Enklave gespeichert ist, zusammen mit einer Zertifikatskette, die zum Hersteller führt. Anhand dieser Ketten sieht jeder Server, dass der Hardware-Sicherheitsschlüssel authentisch ist. Alles, was wir für den Cryptographic Attestation of Personhood benötigen, ist ein einziges Bit: Es beweist, dass Sie einen vertrauenswürdigen Hardware-Sicherheitsschlüssel besitzen – Einzelheiten zu Hersteller oder Modell werden nicht preisgegeben.

In der Vergangenheit wurden Nachweise in Umgebungen verwendet, in denen nur einige wenige Hersteller akzeptiert wurden. Große Finanzinstitute zum Beispiel sind verständlicherweise sehr vorsichtig. In diesem Umfeld ist die Angabe des Herstellers notwendig. Bei einem anbieteroffenen Design wollen wir keinen bestimmten Hersteller bevorzugen, sondern nur wissen, dass die Schlüssel vertrauenswürdig sind.

Die Vertrauenswürdigkeit wird durch den FIDO MetaData-Dienst) bestimmt. Dabei handelt es sich um einen Dienst der FIDO2-Allianz, die Stammzertifikate für die Hersteller verwaltet. Wenn diese Schlüssel kompromittiert sind, werden sie im FIDO-System als solches aufgeführt. Wir können diese Roots mit automatisierten Skripten herunterladen und sie in die Versionen unserer Software einfügen. So bleiben wir immer auf dem neuesten Stand, sollten neue Hersteller auftauchen oder ältere Geräte kompromittiert werden (z. B., weil Angreifer die Schlüssel extrahieren oder die Schlüssel falsch gehandhabt werden).

Das FIDO-Konsortium schreibt vor, dass nicht weniger als 100.000 Geräte einen gemeinsamen Nachweis teilen müssen. So legt es eine Untergrenze für die Anonymität der Geräte fest und minimiert die Auswirkungen der Datenerfassung. Leider ist dies nicht immer gelungen. Manche Hersteller haben möglicherweise nicht das nötige Volumen für diese Mengengröße – und Nutzer sollten nicht in Scharen zu den größten Herstellern wechseln müssen, nur um ihre Privatsphäre zu schützen. Zwar regelt die Cloudflare-Datenschutzrichtlinie bereits, wie wir diese privaten Informationen verwenden, doch am liebsten würden wir den Hersteller Ihres Schlüssels gar nicht erst kennen. Genau wie wir bereits Cookies entfernt haben, die wir nicht mehr benötigen; und Daten protokollieren, die Kunden zum Debuggen ihrer Firewall-Regeln benötigen, ohne die Daten selbst sehen zu können. Wir suchen immer nach Möglichkeiten, die Menge der von uns gesammelten Informationen zu reduzieren.

Aber gleichzeitig müssen wir sicherstellen, dass das Gerät, das auf unsere Anfrage antwortet, ein echter Sicherheitsschlüssel ist und keine Bot-betriebene Software-Emulation. Es ist uns zwar gleichgültig, um welchen Schlüssel es sich genau handelt, aber dennoch möchten wir wissen, ob es sich tatsächlich um einen Schlüssel handelt, der unseren Sicherheitsanforderungen entspricht und nicht kompromittiert wurde. Im Wesentlichen möchten wir die Legitimität der Anmeldeinformationen bestätigen, ohne mehr darüber zu erfahren. Das Problem der anonymen Anmeldeinformation ist nicht neu. Es wurden schon viele Lösungen vorgeschlagen und einige werden sogar eingesetzt.

Die Herausforderung dabei: Diese Schemata erfordern in der Regel, dass die Hardware oder Software, die die Anmeldeinformationen implementiert, für das spezifische Schema konzipiert wurde. Wir können die Hersteller nicht einfach davon überzeugen, in ein paar Monaten neue Funktionen hinzuzufügen, geschweige denn alle Hardware-Authentifizierungs-Sicherheitsschlüssel der Welt zu ersetzen. Stattdessen müssen wir nach Lösungen suchen, die mit der bereits vorhandenen Hardware funktionieren.

Auf den ersten Blick stehen wir vor einer unmöglichen Aufgabe. Wie kann ich zeigen, dass ich etwas weiß, ohne zu verraten, was es ist? Und trotzdem ist es manchmal möglich. Wenn ich behaupte, den Schlüssel zu einem Briefkasten zu haben, können Sie einen Brief in diesen Briefkasten legen, weggehen und mich dann bitten, den Brief zu lesen. Wenn ich behaupte, Ihre Telefonnummer zu kennen, können Sie mich um einen Anruf bitten. Ein solcher Beweis wird als Zero Knowledge-Beweis (Zero Knowledge Proof – ZKP) bezeichnet, also ein Null-Wissen-Beweis.

Ein klassisches Beispiel für einen Zero Knowledge-Beweis: Sie möchten jemandem zeigen, dass Sie wissen, wo sich Walter in „Wo ist Walter“ befindet. Sie könnten mit dem Finger auf Walter auf der Seite zeigen, aber das würde der Person genau verraten, wo Walter ist. Sie könnten die Seite aber auch mit einem großen Stück Papier abdecken, das ein kleines Loch hat, auf dem nur Walter zu sehen ist. Dann weiß Ihr Gegenüber, dass Walter sich irgendwo auf der Seite befindet, kann aber nicht herausfinden, wo. Der andere wüsste dann, dass Sie wissen, wo Walter ist, aber er selbst wüsste nicht, wo Walter ist.

Manchmal ist das Auffinden von Walter gar nicht das Problem (Quelle: https://commons.wikimedia.org/wiki/File:Where%E2%80%99s_Wally_World_Record_(5846729480).jpg)‌‌

Kryptographen haben zahlreiche Zero Knowledge-Beweise entwickelt und ebenso viele Möglichkeiten, sie miteinander zu verbinden. Das zentrale Verbindungselement ist eine Festlegung (commitment), eine Art kryptografischer Briefumschlag. Eine Festlegung verhindert die Manipulation des Wertes, der bei der Herstellung hineingelegt wurde, und kann später geöffnet werden, um den Inhalt preiszugeben. Wir verwenden Festlegungen auch in der Offline-Welt. Ein Zauberkünstler versiegelt ein Stück Papier in einem Umschlag, um dem Publikum zu versichern, dass er es nicht berühren oder manipulieren kann. Später lässt er jemanden den Umschlag öffnen, um seine Vorhersage zu enthüllen. Bei einer stillen Auktion geben die Teilnehmer versiegelte Umschläge mit Geboten ab. Diese werden dann gemeinsam geöffnet, sodass niemand sein Gebot anpassen kann, nachdem er sieht, was andere geboten haben.

Ein sehr einfaches kryptographisches Protokoll, das Festlegungen verwendet, ist das Werfen von Münzen. Angenommen, Alice und Bob wollen eine Münze werfen, aber einer von ihnen hat ein paar doppelköpfige Münzen und der andere ist geschickt genug, eine Münze so zu werfen, dass sie jedes Mal auf der gewünschten Seite landet. Es gibt nur eine Möglichkeit, einen fairen Wurf zu erzielen. Beide müssen auf eine Art und Weise beteiligt sein, die Schummeln verhindert. Wenn aber jeder von ihnen eine Münze wirft und die Ergebnisse tauscht, könnte derjenige, der als Letzter an der Reihe ist, so tun, als hätte er das gewünschte Ergebnis erhalten.

Die Verwendung eines Schemas für Festlegungen löst dieses Problem. Anstatt dass Alice und Bob ihre Ergebnisse laut aussprechen, teilen sie Festlegungen zu den Ergebnissen mit. Dann decken sie die Festlegungen auf. Da sie die Festlegungen mitgeteilt haben, kann keiner von ihnen vorgeben, aufgrund des Erfahrenen ein anderes Ergebnis erzielt zu haben. Dies würde beim Aufdecken der Festlegungen nämlich erkannt werden.

Festlegungen sind wie Drähte, die Zero Knowledge-Beweise miteinander verbinden und aus einfachen Beweisen größere und kompliziertere machen. Durch den Nachweis, dass ein Wert in einer Festlegung zwei verschiedene Eigenschaften mit verschiedenen Zero-Knowledge-Beweisen hat, können wir beweisen, dass beide Eigenschaften für den Wert gelten. So können wir Beweise für Aussagen nehmen wie „der Wert in einer Festlegung ist eine Summe von Werten in zwei anderen Festlegungen“ und „der Wert in einer Festlegung erscheint in einer Liste“ und sie zu viel komplizierteren und nützlicheren Aussagen verknüpfen.  Dann wissen wir, wie wir Aussagen beweisen wie "diese Festlegung ist dann und nur dann eine Festlegung, wenn diese beiden anderen Festlegungen eine sind" und "diese Festlegung ist eine Festlegung, wenn eine dieser beiden Festlegungen eine ist", also haben wir die Bausteine, um jede Aussage zu beweisen. Diese allgemeinen Techniken können einen Zero-Knowledge-Beweis für jede beliebige Aussage liefern, auch wenn der Prozess standardmäßig recht langsam und kompliziert verläuft.

Beim Cryptographic Attestation of Personhood sendet der Server eine Nachricht an den Browser. Die Nachricht wird als Beweis ihrer Authentizität von der Hardware signiert. So wie eine Unterschrift auf Papier sicherstellt, dass diese Person das Dokument gesehen und unterschrieben hat, so bestätigt eine digitale Unterschrift die Identität des Unterzeichners.  Bei unserem Zero-Knowledge-Beweis sendet der Client statt der Signatur einen Beweis, dass die Signatur mit einem Schlüssel aus einer vom Server bereitgestellten Liste erzeugt wurde.

Da wir nur den Nachweis an den Server senden, erfährt der Server lediglich, dass der Nachweis existiert, nicht aber, welcher Hardware-Sicherheitsschlüssel ihn erzeugt hat. Dies garantiert den Datenschutz, denn die Informationen zur Identifizierung des Sicherheitsschlüssels verlassen den Browser nicht. Wir müssen jedoch sicherstellen, dass Beweisführung und Verifizierung effizient genug sind, um sie in großem Maßstab durchzuführen. Nur dann verfügen wir über eine einsatzfähige Lösung.

Wir haben eine große Anzahl potenzieller Verfahren untersucht, darunter auch SNARKS. Leider erwiesen sich der Umfang des Codes, die Anforderungen an die Toolchain und die Komplexität des SNARKS-Nachweises als nicht tragfähig. Die Sicherheit von SNARKS beruht auf komplizierteren Annahmen als das Schema, für das wir uns letztendlich entschieden haben. Auf diesem Gebiet wird natürlich aktiv geforscht, und die beste Technologie von heute ist nicht unbedingt die beste Technologie der Zukunft.

Für die von uns unterstützten Hardware-Sicherheitsschlüssel wurde die digitale Signatur im Nachweis mit dem Elliptic Curve Digital Signature Algorithm (ECDSA) erstellt. ECDSA selbst ähnelt vielen der von uns verwendeten Zero Knowledge-Beweisen. Es beginnt damit, dass der Signierer einen Punkt \(R=kG\) auf einer elliptischen Kurve für einen Zufallswert x berechnet. Dann nimmt der Signierer die \(x\)-Koordinate des Punktes (geschrieben als \(r\)), seinen privaten Schlüssel sowie den Hash der Nachricht und berechnet einen Wert \(s\). Das Paar \((r, s)\) ist die Signatur. Der Verifizierer verwendet \(r\) und \(s\) sowie den öffentlichen Schlüssel, um \(r\) neu zu berechnen, und überprüft dann, ob die \(x\)-Koordinate mit \(r\) übereinstimmt.

Leider beinhaltet die übliche Beweisgleichung einige Operationen, bei denen Werte von einer Form in eine andere umgewandelt werden müssen. Diese Operationen sind bei einem Zero Knowledge-Beweis komplex, teuer und erfordern viele Schritte. Wir mussten diese Einschränkung umgehen, damit unser System funktioniert. Wir möchten ECDSA in ein Schema umwandeln, mit dem wir arbeiten können. Daher sendet unser Beweiser stattdessen \(r\) und legt sich auf einen Wert \(z\) fest, der aus \(r\) und \(s\) berechnet wird – das vereinfacht die Verifizierungsgleichung. Jeder kann eine ECDSA-Signatur nehmen und sie in eine Signatur für unser angepasstes Schema umwandeln und umgekehrt, ohne geheimes Wissen zu verwenden, also ist dieses Verfahren genauso sicher wie ECDSA.

Da die Aussage, die wir beweisen wollen, aus zwei Teilen besteht – „die Nachricht wurde mit einem Schlüssel signiert“ und „der Schlüssel steht auf der Liste“ – ist es naheliegend, das Problem des Beweisverfahrens für diese Aussage in zwei Teile aufzuteilen. Zunächst weist der Prüfer nach, dass der Schlüssel innerhalb einer Festlegung die Nachricht signiert hat; und dann weist er nach, dass der festgelegte Schlüssel in einer Liste enthalten ist. Der Verifizierer prüft ebenfalls diese beiden Teile und – wenn beide Teile funktionieren – zeigt er an, dass der Beweis gültig ist.

Um zu beweisen, dass die Signatur unter einem Schlüssel verifiziert werden kann, mussten wir einen Beweis dafür verwenden, dass ein Punkt einer elliptischen Kurve eine bekannte Potenz eines anderen ist. Dieser Beweis ist ein ziemlich standardmäßiger Zero Knowledge-Beweis, aber einige der Schritte selbst erfordern Zero Knowledge-Protokolle, um zu beweisen, dass die Punkte korrekt addiert und die Rechnungen korrekt durchgeführt wurden. Dieser Nachweis dauert bei der Generierung und Verifizierung von Nachweisen am längsten. Sobald dieser Beweis verifiziert ist, weiß der Verifizierer, dass die Nachricht mit dem festgelegten öffentlichen Schlüssel signiert wurde.

Im nächsten Schritt muss der Beweiser ermitteln, wo sein Schlüssel auf der Liste liegt, und dann beweisen, dass sich sein Schlüssel in der Liste befindet. Hierfür verwenden wir den Zero Knowledge-Beweis, der von Groth und Kohlweiss entwickelt wurde. Der Beweis legt sich zuerst auf die Binärentwicklung der Position der Festlegung auf der Liste fest. Der Beweiser beweist dann, dass die Binärentwicklung aus Bits besteht und liefert einige zusätzliche Informationen darüber, wie er dies bewiesen hat. Mit den zusätzlichen Informationen und den Beweisen können beide Seiten Polynome berechnen, die zu Null evaluieren, wenn die Festlegung auf einen Wert in der Liste erfolgt. Dieser Code ist für eine so komplexe Aufgabe erstaunlich kurz.

Indem wir ein Polynom auswerten, zeigen wir, dass der von uns festgelegte Wert eine Null ist.

Der Verifizierer prüft dann mit dem Groth-Kohlweiss-Beweis, ob sich der festgelegte Schlüssel auf der Liste befindet. Anschließend stellt er sicher, dass die signierte Nachricht korrekt ist. Dies ist ein sehr effizienter Beweis, auch wenn die Liste größer wird: Die Arbeit, die pro Listenelement geleistet wird, ist eine Multiplikation. Wenn alles übereinstimmt, wissen wir, dass die Signatur von einem ausreichend sicheren Sicherheitsschlüssel generiert wurde, mehr erfahren wir nicht. Wenn die Informationen nicht übereinstimmen, wissen wir, dass etwas nicht in Ordnung ist.

We turned statements about ECDSA signatures into statements about points on the P-256 elliptic curve, and then into statements about arithmetic in the field that P-256 is defined over. These statements are easiest to prove if we have a group with a size matching the size of a field, and so we had to find one. This posed an interesting challenge as it’s the reverse of how we normally do things in cryptography. If you’d like to see how we solved it read on, otherwise skip ahead.

Wir haben Aussagen über ECDSA-Signaturen in Aussagen über Punkte auf der elliptischen Kurve P-256 umgewandelt, und dann in Aussagen über die Arithmetik in dem Körper, über den P-256 definiert ist. Diese Aussagen sind am einfachsten zu beweisen, wenn wir eine Gruppe mit einer Größe haben, die der Größe eines Körpers entspricht, und so mussten wir eine finden. Das war eine interessante Herausforderung, denn es ist das Gegenteil von dem, was wir normalerweise in der Kryptographie tun. Wenn Sie wissen wollen, wie wir die Aufgabe gelöst haben, lesen Sie weiter, ansonsten können Sie diese Passage überspringen.

Meistens beginnen wir in der Elliptische-Kurven-Kryptografie mit einem praktischen Basiskörper und suchen nach elliptischen Kurven mit Primzahl- oder annähernder Primzahlordnung, die über die richtigen Eigenschaften für unsere Anwendung verfügt. Auf diese Weise können wir Primzahlen mit Eigenschaften auswählen, die für Computer-Hardware geeignet sind. Wenn wir Kurven benötigen, die für das Pairing geeignet sind, suchen wir typischerweise am Computer nach Kurven, deren Parameter durch bekannte Polynome gegeben sind.

Aber in diesem Fall brauchten wir eine Kurve mit einer bestimmten Anzahl von Punkten, und so müssten wir zum Bestimmen dieser Kurven eine ziemlich fortgeschrittene zahlentheoretische Maschinerie verwenden. Vor allem diesem Schritt ist es zu verdanken, dass unser Zero Knowledge-Nachweis so effizient geworden ist.

Elliptische Kurven sind besonders gut über komplexen Zahlen. Eine elliptische Kurve ist isomorph zu einem Torus. Alle komplexen Kurven sind isomorph zu Tori über komplexen Zahlen, aber einige haben mehr als nur ein Loch.

Verschiedene elliptische Kurven unterscheiden sich dadurch, wie dick oder dünn die beiden Seiten um den Torus sind. Wenn wir uns vorstellen, dass wir um die Löcher im Torus herum schneiden, sehen wir: Wir können einen Torus erhalten, wenn wir ein Rechteck nehmen und die Seiten zusammenkleben. Ein anschauliches Video zeigt, wie das funktioniert: Torus zusammenkleben.

Anstatt ein Rechteck zu nehmen und es zusammenzukleben, können wir uns vorstellen, die gesamte Ebene zu nehmen und sie dann so zu falten, dass jedes Rechteck in einer Linie liegt. Dabei richten sich die Ecken dieser Rechtecke alle über dem Ursprung aus. Die Ecken bilden einen so genannten Verband, und wir können immer so skalieren und rotieren, dass einer der Generatoren des Verbandes 1 ist.

So gesehen wird die Addition komplexer Zahlen zur Addition auf dem Torus, so wie die Addition der ganzen Zahlen modulo 2 eine Addition ganzer Zahlen ist, die dann mod 2 reduziert wird. Aber bei elliptischen Kurven sind wir algebraische Gleichungen für Addition und Multiplikation und auch für die Kurven selbst gewohnt. Wie interagiert dieses analytische Bild mit dem algebraischen?

Mit viel klassischer komplexer Geometrie stellen wir fest, dass sie eng miteinander verwandt sind. Der Ring der komplexwertigen Funktionen auf dem Verband wird durch die Weierstraß-\(\mathcal{P}\)-Funktion und ihre Ableitung erzeugt. Diese erfüllen eine algebraische Gleichung der Form \(y^2=x^3+ax+b\), und die Parameter \(a\) und \(b\) sind Funktionen der Verbandparameter. Daraus ergeben sich die klassischen Formeln für die algebraische Addition von Punkten auf elliptischen Kurven.

Einer der Parameter ist die \(j\)-Funktion, eine rechnerisch sinnvollere Funktion als \(\tau\). Die \(j\)-Funktion ist eine Funktion der elliptischen Kurve: Werte von \(\tau\), die zum gleichen Verband führen, ergeben die gleiche \(j\)-Funktion, während sie unterschiedliche \(a\) und \(b\) haben können.  Es gibt viele Ausdrücke für \(j\), einer davon ist

https://dlmf.nist.gov/23.15#E7

Angenommen, wir nehmen den Verband \(\{1, i\}\). Wenn wir diesen Verband mit i multiplizieren, erhalten wir wieder \(\{i, -1\}\), was dieselbe Menge von Punkten erzeugt. Dies ist eine Ausnahme und kann nur geschehen, wenn die Zahl, mit der wir multiplizieren, eine quadratische Gleichung erfüllt. Die Elemente des Verbandes sind dann eng mit den Lösungen dieser quadratischen Gleichung verbunden.

Zu einem solchen Verband gehört eine Diskriminante: die Diskriminante, die dem quadratischen Körper des Beispiels zugeordnet ist. Für unser Beispiel mit \(i\) ist die Diskriminante \(-4\), die Diskriminante der quadratischen Gleichung \(x^2+1\). Würde man stattdessen \(\sqrt{-5}\) nehmen und den Verband \(\{1, \sqrt{-5}\}\) betrachten, wäre die Diskriminante \(-20\), die Diskriminante von \(x^2-5\). Beachten Sie, dass es verschiedene Definitionen der Diskriminante gibt, die das Vorzeichen ändern und verschiedene Potenzen von \(2\) hinzufügen.

Abbildungen von elliptischen Kurven auf sich selbst werden als Endomorphismen bezeichnet. Die meisten elliptischen Kurven haben nur Multiplikation mit ganzen Zahlen als Endomorphismen. Einige Kurven haben jedoch zusätzliche Endomorphismen. Wenn wir beispielsweise den Verband \(\{1, i\}\) zu einer elliptischen Kurve machen, erhalten wir \(y^2=x^3+x\). Jetzt hat diese Kurve einen zusätzlichen Endomorphismus: Wenn ich \(y\) zu \(iy\) und \(x\) zu \(-x\) mache, erhalte ich einen Punkt, der die Kurvengleichung \((-iy)^2=(-x)^3-x\) erfüllt. Wenn man diese Abbildung zweimal durchführt, hat man denselben Effekt wie bei der Umkehrung eines Punktes, und es ist kein Zufall, dass die zweimalige Multiplikation mit \(i\) eine komplexe Zahl \(z\) zu \(-z\) macht. Dieser zusätzliche Endomorphismus und die Multiplikation mit i erfüllen also die gleiche Gleichung. Ein zusätzlicher Endomorphismus wird als komplexe Multiplikation bezeichnet, da er mit einer komplexen Zahl multipliziert wird. Wenn der Verband, aus dem eine elliptische Kurve stammt, eine komplexe Multiplikation hat, hat auch die elliptische Kurve eine komplexe Multiplikation und umgekehrt.

Jede Menge mathematischer Objekte bringt Fragen mit sich, elliptische Kurven mit komplexer Multiplikation sind da keine Ausnahme. Wir können fragen, wie viele elliptische Kurven mit komplexer Multiplikation es für eine bestimmte Diskriminante gibt. Wie wächst diese Zahl, wenn die Diskriminante wächst? Einige dieser Fragen sind trotz jahrelanger Forschung und Computerexperimenten auch heute noch offen. Entscheidend für die Herangehensweise ist eine Verbindung zwischen Verbänden und Arithmetik.

Anfang des 19. Jahrhunderts studierte Gauss binäre quadratische Formen, Gleichungen der Form \(ax^2+bxy+cy^2\). Solche Formen werden als äquivalent bezeichnet, wenn es eine Substitution mit ganzzahligen Koeffizienten für x und y gibt, die den einen in den anderen überführt. Dies ist ein Kerngedanke und zusätzlich zu Algorithmen zur Reduktion einer binären quadratischen Form zeigte Gauß, dass es ein Kompositionsgesetz gibt, das binäre quadratische Formen einer gegebenen Diskriminante zu einer Gruppe macht.

Spätere Zahlentheoretiker entwickelten das Konzept eines Ideals, das quadratische Formen mit dem Scheitern der Faktorisierung verbindet, eindeutig zu sein. \(x^2+5y^2\) und \(2x^2+2xy+3y^2\) sind beide quadratische Formen der Diskriminante \(-20\), und dies hängt mit dem Scheitern der eindeutigen Faktorisierung in \(\mathbb{Z}[\sqrt{-5}]\) zusammen.

Wenn wir binäre quadratische Formen als die Längen von Vektoren in einer Ebene betrachten, ergibt jeder Verband eine binäre quadratische Form bis zur Äquivalenz. Die elliptischen Kurven mit komplexer Multiplikation mit einer gegebenen Diskriminante entsprechen also den Klassen der binären quadratischen Formen mit einer gegebenen Diskriminante, die an die Arithmetik im quadratischen Zahlkörper anschließt. Drei sehr unterschiedliche Fragen haben also alle die gleiche Antwort.

Nimmt man eine elliptische Kurve mit ganzzahligen Koeffizienten und betrachtet sie über einer Primzahl, so erhält sie einen zusätzlichen Endomorphismus: den Frobenius-Endomorphismus, der \(x \rightarrow x^p\) und \(y \rightarrow y^p\) macht. Dieser Endomorphismus erfüllt eine quadratische Gleichung, und der lineare Ausdruck dieser quadratischen Gleichung ist die Anzahl der Punkte minus \(p+1\).

Wenn die elliptische Kurve eine komplexe Multiplikation aufweist, gibt es einen weiteren Endomorphismus, nämlich den, den wir durch die komplexe Multiplikation erhalten. Eine elliptische Kurve kann jedoch nur einen zusätzlichen Endomorphismus haben, es sei denn, sie ist supersingulär. Supersinguläre Kurven sind sehr selten. Der Frobenius-Endomorphismus und der Endomorphismus aus der komplexen Multiplikation müssen also identisch sein. Da wir mit der komplexen Multiplikation begonnen haben, kennen wir die quadratische Gleichung, die der Frobenius erfüllen muss, und damit die Anzahl der Punkte.

Hiermit endet unsere Erzählung: Um eine elliptische Kurve mit einer gegebenen Ordnung zu finden, muss man ganzzahlige Lösungen der Gleichung \(t^2+Dy^2=4N\) für kleines D finden und \(p=N-t+1\) sein lassen, um zu sehen, ob es eine Primzahl ist. Dann faktorisieren wir das Hilbert-Klassenpolynom von \(D\) über \(p\) und nehmen eine der Wurzeln modulo \(p\) als \(j\)-Funktion unserer elliptischen Kurve. Möglicherweise müssen wir eine quadratische Drehung vornehmen, um die richtige Anzahl von Punkten zu erhalten, da t nur bis zum Vorzeichen identifiziert wird.

The results of our labor

Damit hatten wir die Kurve, die wir für den effizienten Beweis von Relationen über dem Basiskörper von P-256 benötigten. All diese Mathematik führt zu einem Skript, das in wenigen Minuten ausgeführt werden kann und die Kurve mit der von uns gewünschten Reihenfolge erzeugt.

Nach all dieser Mühe und viel zusätzlicher Entwicklungsarbeit, die nötig ist, um den Beweis durch Optimierung kleiner Teile noch schneller laufen zu lassen, können wir einen Beweis in ein paar Sekunden erzeugen und ihn in ein paar hundert Millisekunden verifizieren. Dies ist schnell genug für den praktischen Einsatz und bedeutet, dass Websites die Sicherheit von Sicherheitsschlüsseln ohne negative Auswirkungen auf Datenschutz verifizieren können.

Eine Website, die unsere Technik verwendet, erfährt nur, ob die Signatur von einem Token erzeugt wurde, dessen Nachweisschlüssel in der von ihr bereitgestellten Liste enthalten ist oder nicht. Anders als bei der direkten Nutzung von WebAuthn erhalten sie keine genaueren Informationen, auch wenn der Hersteller den Satz versehentlich zu klein gewählt hat. Anstatt die Daten unserer Nutzer mit richtlinienbasierten Ansätzen zu schützen, haben wir die störenden Informationen entfernt.

Unsere Demonstration zeigt: Wir haben eine funktionierende Datenschutzverbesserung, die auf einem Zero Knowledge-Beweis basiert. Wir werden ihn weiter verbessern und fügen weitere Performance- und Sicherheitsmerkmale hinzu. Aber unsere Aufgabe ist erst dann erledigt, wenn wir eine datenschutzfreundliche WebAuthn-Erweiterung entwickelt haben, die in jedem Browser funktioniert und dem Nutzer die Sicherheit gibt, dass seine Daten das Gerät nicht verlassen.

Was wir jetzt haben, ist eine Demonstration dessen, was möglich ist: die Verwendung von Zero Knowledge-Beweisen, um den WebAuthn-Nachweis in ein System zu verwandeln, das jeden Hersteller von vornherein gleich behandelt, die Daten der Nutzer schützt und von jeder Website genutzt werden kann. Die Datenschutzherausforderungen, die durch den Einsatz von Nachweisen auf breiter Ebene entstehen, sind lösbar.

Ein hochwertiges, zuverlässiges System besteht aus viel mehr als nur den kryptografischen Kernerkenntnissen. Damit die Nutzererfahrung nicht durch Warnungen über die Informationen gestört wird, die unser Zero Knowledge-Beweis verwirft, brauchen wir mehr Integration mit dem Browser. Wir brauchen auch einen sicheren Weg für Nutzer von Geräten, die nicht auf unserer Liste stehen, um ihren Schlüssel an uns zu senden und zu zeigen, dass er vertrauenswürdig ist, sowie einen Weg, um sicherzustellen, dass die Liste nicht zum Finden bestimmter Schlüssel missbraucht wird.

Darüber hinaus ist diese Verifizierung aufwendiger als die älteren Verifizierungsmethoden, sodass Server, die sie implementieren, eine Ratenbegrenzung und andere Schutzmaßnahmen gegen Missbrauch einbauen müssen. SNARKS wäre hier ein großer Vorteil, allerdings auf Kosten des Codeumfangs für die Demonstration. Um diese Verbesserungen in ein Kernstück des Web-Ökosystems zu integrieren, müssen wir mit Nutzern, Browsern und anderen Beteiligten eine gemeinsame Lösung finden. Wenn Sie zu diesem Prozess beitragen möchten, würden wir gerne unter ask-research@cloudflare.com von Ihnen hören.

Unser Cryptographic Attestation of Personhood bietet Nutzern eine einfachere Möglichkeit, zu beweisen, dass sie eine Person sind; und es ist eine Alternative, die Daten besser schützt als viele andere CAPTCHA-Alternativen oder -Anbieter. Doch wir waren mit dem Stand der Technik nicht zufrieden und sahen eine Möglichkeit, fortschrittliche Kryptographietechniken anzuwenden, um den Datenschutz für unsere Nutzer zu verbessern. Unsere Arbeit zeigt, dass Zero Knowledge-Beweise den Datenschutz von Protokollen der realen Welt verbessern können.