10. Sicherheitsüberlegungen

Dieser Abschnitt enthält zusätzliche Sicherheitsüberlegungen zu den in diesem Dokument beschriebenen Hash-to-Curve-Mechanismen.

10.1. Eigenschaften der Kodierungen

Jeder Kodierungstyp (Abschnitt 3) akzeptiert eine beliebige Byte-Zeichenkette und bildet sie auf einen Punkt auf der Kurve ab, der aus einer Verteilung gezogen wird, die vom Kodierungstyp abhängt. Es ist wichtig zu beachten, dass die Verwendung einer nicht-uniformen Kodierung oder die direkte Auswertung einer der Abbildungen aus Abschnitt 6 eine Ausgabe erzeugt, die leicht von einem gleichmäßig verteilten zufälligen Punkt unterscheidbar ist. Anwendungen, die eine nicht-uniforme Kodierung verwenden, SOLLTEN die Sicherheitsimplikationen der Nicht-Uniformität sorgfältig analysieren. Wenn die erforderliche Kodierung nicht klar ist, SOLLTEN Anwendungen eine uniforme Kodierung verwenden.

Beide in Abschnitt 3 angegebenen Kodierungen können das Identitätselement der Gruppe G erzeugen. Die Wahrscheinlichkeit, dass eine der beiden Kodierungsfunktionen das Identitätselement für eine zufällige Eingabe erzeugt, beträgt etwa 1/r, was für kryptographisch nützliche elliptische Kurven vernachlässigbar ist. Darüber hinaus ist es rechnerisch nicht durchführbar, eine Eingabe für eine der beiden Kodierungsfunktionen zu finden, deren entsprechende Ausgabe das Identitätselement ist. (Beide Eigenschaften gelten, wenn die Kodierungsfunktionen mit einer hash_to_field-Funktion instanziiert werden, die alle Richtlinien in Abschnitt 5 befolgt.) Protokolle, die diese Kodierungsfunktionen verwenden, SOLLTEN KEINE Sonderfälle hinzufügen, um das Identitätselement zu erkennen und zu „korrigieren".

Wenn die hash_to_curve-Funktion (Abschnitt 3) mit einer hash_to_field-Funktion instanziiert wird, die von einem Random Oracle nicht unterscheidbar ist (Abschnitt 5), ist die resultierende Funktion von einem Random Oracle nicht unterscheidbar ([MRH04] [BCIMRT10] [FFSTV13] [LBB19] [H20]). In vielen Fällen kann eine solche Funktion sicher in kryptographischen Protokollen verwendet werden, deren Sicherheitsanalyse ein Random Oracle annimmt, das gleichmäßig verteilte zufällige Punkte auf einer elliptischen Kurve erzeugt. Wie Ristenpart et al. in [RSS11] diskutieren, bleiben jedoch nicht alle Sicherheitsbeweise, die auf Random Oracles beruhen, gültig, wenn diese Oracles durch nicht unterscheidbare Funktionalitäten ersetzt werden. Diese Einschränkung sollte bei der Analyse der Sicherheit von Protokollen berücksichtigt werden, die auf der hash_to_curve-Funktion beruhen.

10.2. Hashing von Passwörtern

Beim Hashen von Passwörtern mit einer der in diesem Dokument beschriebenen Funktionen kann ein Angreifer, der die Ausgabe der Hash-Funktion (oder möglicherweise einen Zwischenwert, z.B. die Ausgabe von hash_to_field) erfährt, in der Lage sein, einen Wörterbuchangriff durchzuführen. Um solche Angriffe abzuschwächen, wird empfohlen, zunächst eine kostspieligere Schlüsselableitungsfunktion (z.B. PBKDF2 [RFC8017], scrypt [RFC7914] oder Argon2 [RFC9106]) auf das Passwort anzuwenden und dann die Ausgabe dieser Funktion auf die elliptische Zielkurve zu hashen. Für Kollisionsresistenz sollte der der Schlüsselableitungsfunktion zugrundeliegende Hash gemäß den in Abschnitt 5.3.1 aufgeführten Richtlinien gewählt werden.

10.3. Anforderungen an konstante Zeit

Implementierungen aller Funktionen in diesem Dokument in konstanter Zeit werden für alle Verwendungen DRINGEND EMPFOHLEN, um Informationslecks über Seitenkanäle zu vermeiden. Es ist besonders wichtig, eine Implementierung in konstanter Zeit zu verwenden, wenn die Eingaben einer Kodierung geheime Werte sind; in solchen Fällen sind Implementierungen in konstanter Zeit für die Sicherheit gegen Timing-Angriffe ERFORDERLICH (z.B. [VR20]). Wenn Implementierungen in konstanter Zeit erforderlich sind, müssen alle grundlegenden Operationen und Hilfsfunktionen in konstanter Zeit implementiert werden, wie in Abschnitt 4 diskutiert. In einigen Anwendungen (z.B. eingebetteten Systemen) können Lecks über andere Seitenkanäle (z.B. Leistungs- oder elektromagnetische Seitenkanäle) relevant sein. Der Schutz gegen solche Lecks liegt außerhalb des Umfangs dieses Dokuments, da die Art des Lecks und der angemessene Schutz von der Anwendung abhängen.

10.4. encode_to_curve: Ausgabeverteilung und Nicht-Unterscheidbarkeit

Die encode_to_curve-Funktion (Abschnitt 3) gibt Punkte zurück, die aus einer Verteilung gezogen werden, die statistisch weit von der Gleichverteilung entfernt ist. Diese Verteilung ist ungefähr wie folgt begrenzt: Erstens umfasst sie mindestens ein Achtel der Punkte von G, und zweitens variiert die Wahrscheinlichkeit von Punkten in der Verteilung um höchstens einen Faktor vier. Diese Grenzen gelten, wenn encode_to_curve mit einer der map_to_curve-Funktionen aus Abschnitt 6 instanziiert wird.

Die obigen Grenzen werden aus mehreren Arbeiten in der Literatur abgeleitet. Insbesondere:

• Shallue und van de Woestijne [SW06] und Fouque und Tibouchi [FT12] leiten Grenzen für die Shallue-van de Woestijne-Abbildung ab (Abschnitt 6.6.1).

• Fouque und Tibouchi [FT10] und Tibouchi [T14] leiten Grenzen für die vereinfachte SWU-Abbildung ab (Abschnitte 6.6.2 und 6.6.3).

• Bernstein et al. [BHKL13] leiten Grenzen für die Elligator 2-Abbildung ab (Abschnitte 6.7.1 und 6.8.2).

Die Nicht-Unterscheidbarkeit von encode_to_curve folgt aus einem ähnlichen Argument wie dem von Brier et al. [BCIMRT10] gegebenen; wir skizzieren dieses Argument kurz wie folgt. Betrachten Sie ein ideales Random Oracle Hc(), das aus der durch die map_to_curve-Funktion induzierten Verteilung zieht, die von encode_to_curve aufgerufen wird, und nehmen Sie zur Vereinfachung an, dass die elliptische Zielkurve den Cofaktor 1 hat (ein ähnliches Argument gilt für nicht-unitäre Cofaktoren). Nicht-Unterscheidbarkeit gilt, wenn es möglich ist, das „interne" Random Oracle in encode_to_curve, nämlich hash_to_field, effizient zu simulieren. Der Simulator funktioniert wie folgt: Bei einer neuen Anfrage msg fragt der Simulator Hc(msg) ab und erhält einen Punkt P im Bild von map_to_curve (wenn msg mit einer früheren Anfrage identisch ist, gibt der Simulator einfach den Wert zurück, den er als Antwort auf diese Anfrage gegeben hat). Der Simulator berechnet dann die möglichen Urbilder von P unter map_to_curve, d.h. die Elemente u von F, so dass map_to_curve(u) == P (Tibouchi [T14] zeigt, dass dies effizient für die Shallue-van de Woestijne- und vereinfachte SWU-Abbildungen durchgeführt werden kann, und Bernstein et al. zeigen dasselbe für Elligator 2). Der Simulator wählt eines dieser Urbilder zufällig aus und gibt diesen Wert als simulierte Ausgabe des „internen" Random Oracle zurück. Per Annahme zieht Hc() aus der durch map_to_curve auf einem gleichmäßig verteilten zufälligen Eingabeelement von F induzierten Verteilung, sodass dieser Wert gleichmäßig verteilt zufällig ist und den richtigen Punkt P induziert, wenn er durch map_to_curve geleitet wird.

10.5. Sicherheit von hash_to_field

Die hash_to_field-Funktion, definiert in Abschnitt 5, ist von einem Random Oracle nicht unterscheidbar [MRH04], wenn expand_message (Abschnitt 5.3) als Random Oracle modelliert wird. Da Nicht-Unterscheidbarkeitsbeweise komponierbar sind, gilt dies auch, wenn expand_message in Bezug auf ein zugrundeliegendes Primitiv, das als Random Oracle modelliert wird, als von einem Random Oracle nicht unterscheidbar nachgewiesen wird. Gemäß den Richtlinien in Abschnitt 5.3 erfüllen beide in diesem Abschnitt definierten Varianten von expand_message diese Anforderung (siehe auch Abschnitt 10.6).

Wir skizzieren sehr kurz das Nicht-Unterscheidbarkeitsargument für hash_to_field. Beachten Sie, dass jede ganze Zahl mod p, die hash_to_field zurückgibt (d.h. jedes Element der Vektordarstellung von F), Mitglied einer Äquivalenzklasse von ungefähr 2^k ganzen Zahlen der Länge log2(p) + k Bits ist, die alle modulo p gleich sind. Für jede ganze Zahl mod p, die hash_to_field zurückgibt, zieht der Simulator ein Mitglied dieser Äquivalenzklasse zufällig und erzeugt die von I2OSP zurückgegebene Byte-Zeichenkette. (Beachten Sie, dass dies im Wesentlichen die Umkehrung der hash_to_field-Prozedur ist.)

10.6. Sicherheit von expand_message_xmd

Die expand_message_xmd-Funktion, definiert in Abschnitt 5.3.1, ist von einem Random Oracle nicht unterscheidbar [MRH04], wenn eine der folgenden Bedingungen erfüllt ist:

1. H ist von einem Random Oracle nicht unterscheidbar,

2. H ist eine Schwamm-basierte Hash-Funktion, deren interne Funktion als zufällige Transformation oder zufällige Permutation modelliert wird [BDPV08], oder

3. H ist eine Merkle-Damgaard-Hash-Funktion, deren Kompressionsfunktion als Random Oracle modelliert wird [CDMP05].

Für die Fälle (1) und (2) folgt die Nicht-Unterscheidbarkeit von expand_message_xmd direkt aus der Nicht-Unterscheidbarkeit von H.

Für Fall (3), d.h. wenn H eine Merkle-Damgaard-Hash-Funktion ist, folgt die Nicht-Unterscheidbarkeit aus [CDMP05], Theorem 5. Insbesondere berechnet expand_message_xmd b_0, indem der Nachricht ein Block von Nullen plus Hilfsinformationen (Länge, Zähler und DST) vorangestellt wird. Dann ist jeder der Ausgabeblöcke b_i, i >= 1 in expand_message_xmd das Ergebnis des Aufrufs von H auf einer eindeutigen und präfixfreien Kodierung von b_0. Dies gilt erstens, weil die Länge der Eingabe all dieser Aufrufe gleich und durch die Wahl von H und DST festgelegt ist, und zweitens, weil jede dieser Eingaben ein eindeutiges Suffix hat (aufgrund der Einbeziehung des Zähler-Bytes I2OSP(i, 1)).

Der wesentliche Unterschied zwischen der in [CDMP05] diskutierten Konstruktion und expand_message_xmd besteht darin, dass letztere einen Zähler hasht, der zu strxor(b_0, b_(i - 1)) hinzugefügt wird (Schritt 10 von Abschnitt 5.3.1), anstatt zu b_0. Dieser Ansatz erhöht die Hamming-Distanz zwischen den Eingaben verschiedener Aufrufe von H, was die Wahrscheinlichkeit verringert, dass Nicht-Idealitäten in H die Verteilung der Werte b_i beeinflussen.

Wir stellen fest, dass expand_message_xmd verwendet werden kann, um eine nicht unterscheidbare Mehrzweck-Funktionalität mit variabler Ausgabelänge basierend auf jeder Hash-Funktion zu instanziieren, die eines der obigen Kriterien erfüllt. Anwendungen, die expand_message_xmd außerhalb von hash_to_field verwenden, sollten die Bereichstrennung gewährleisten, indem sie einen unterschiedlichen Wert für DST wählen.

10.7. Bereichstrennung für expand_message-Varianten

Wie in Abschnitt 2.2.5 diskutiert, besteht der Zweck der Bereichstrennung darin, sicherzustellen, dass Sicherheitsanalysen kryptographischer Protokolle, die mehrere unabhängige Random Oracles abfragen, selbst dann gültig bleiben, wenn alle diese Random Oracles auf der Grundlage einer einzigen zugrundeliegenden Funktion H instanziiert werden.

Die expand_message-Varianten in diesem Dokument (Abschnitt 5.3) gewährleisten Bereichstrennung, indem sie ein suffixfrei kodiertes Domain-Separation-Tag DST_prime zu allen Zeichenketten hinzufügen, die von H, einem zugrundeliegenden Hash oder einer erweiterbaren Ausgabefunktion, gehasht werden. (Es wird erwartet, dass andere expand_message-Varianten, die den Richtlinien von Abschnitt 5.3.4 folgen, sich ähnlich verhalten, diese sollten jedoch einzeln analysiert werden.) Für die Sicherheit sollten Anwendungen, die dieselbe Funktion H außerhalb von expand_message verwenden, Bereichstrennung zwischen diesen Verwendungen von H und expand_message durchsetzen, und sie sollten all diese von Verwendungen von H in anderen Anwendungen trennen.

Dieser Abschnitt schlägt vier Methoden vor, um Bereichstrennung von den expand_message-Varianten durchzusetzen, erklärt, wie jede Methode Bereichstrennung erreicht, und listet die Situationen auf, in denen jede angemessen ist. Diese Methoden teilen eine High-Level-Struktur: Der Anwendungsdesigner legt ein von DST_prime verschiedenes Tag DST_ext fest und erweitert die Aufrufe von H um DST_ext. Jede Methode erweitert die Aufrufe von H unterschiedlich, und jede kann zusätzliche Anforderungen an DST_ext stellen.

Diese Methoden können verwendet werden, um mehrere bereichsgetrennte Funktionen (z.B. H1 und H2) zu instanziieren, indem unterschiedliche DST_ext-Werte für jede ausgewählt werden (z.B. DST_ext1, DST_ext2).

1. (Bereichstrennung nur durch Suffix.) Diese Methode ist nützlich beim Bereichstrennen von Aufrufen von H von expand_message_xmd oder expand_message_xof. Sie ist nicht geeignet für die Bereichstrennung von expand_message von HMAC-H [RFC2104]; zu diesem Zweck siehe Methode 4.

   Um eine nur durch Suffix bereichsgetrennte Funktion Hso zu instanziieren, berechnen Sie:

   Hso(msg) = H(msg || DST_ext)

   DST_ext sollte suffixfrei kodiert werden (z.B. durch Hinzufügen eines Bytes, das die Länge von DST_ext kodiert), um es unmöglich zu machen, unterschiedliche Paare (msg, DST_ext) zu finden, die auf denselben Wert hashen.

   Diese Methode gewährleistet Bereichstrennung, weil alle unterschiedlichen Aufrufe von H unterschiedliche Suffixe haben, da DST_ext von DST_prime verschieden ist.

2. (Präfix-Suffix-Bereichstrennung.) Diese Methode kann in denselben Fällen wie die Methode nur durch Suffix verwendet werden.

   Um eine durch Präfix-Suffix bereichsgetrennte Funktion Hps zu instanziieren, berechnen Sie:

   Hps(msg) = H(DST_ext || msg || I2OSP(0, 1))

   DST_ext sollte präfixfrei kodiert werden (z.B. durch Hinzufügen eines Ein-Byte-Präfixes, das die Länge von DST_ext kodiert), um es unmöglich zu machen, unterschiedliche Paare (msg, DST_ext) zu finden, die auf denselben Wert hashen.

   Diese Methode gewährleistet Bereichstrennung, weil das Hinzufügen des Bytes I2OSP(0, 1) sicherstellt, dass die Eingaben von H innerhalb von Hps von denen innerhalb von expand_message verschieden sind. Insbesondere kodiert das letzte Byte von DST_prime die Länge von DST, die ungleich null sein muss (Abschnitt 3.1, Anforderung 2), und DST_prime wird immer an die Aufrufe von H innerhalb von expand_message angehängt.

3. (Bereichstrennung nur durch Präfix.) Diese Methode ist nur nützlich für die Bereichstrennung von Aufrufen von H von expand_message_xmd. Sie ermöglicht keine Bereichstrennung für expand_message_xof oder HMAC-H.

   Um eine nur durch Präfix bereichsgetrennte Funktion Hpo zu instanziieren, berechnen Sie:

   Hpo(msg) = H(DST_ext || msg)

   Damit diese Methode Bereichstrennung gewährleistet, sollte DST_ext mindestens b Bits lang sein, wobei b die Anzahl der von der Hash-Funktion H erzeugten Bits ist. Darüber hinaus muss mindestens eines der ersten b Bits ungleich null sein. Schließlich sollte DST_ext präfixfrei kodiert werden (z.B. durch Hinzufügen eines Ein-Byte-Präfixes, das die Länge von DST_ext kodiert), um es unmöglich zu machen, unterschiedliche Paare (msg, DST_ext) zu finden, die auf denselben Wert hashen.

   Diese Methode gewährleistet Bereichstrennung wie folgt. Erstens, da DST_ext mindestens ein Nicht-Null-Bit unter den ersten b Bits enthält, ist sie garantiert von dem Wert Z_pad verschieden (Abschnitt 5.3.1, Schritt 4), was garantiert, dass alle Eingaben von H von der Eingabe verschieden sind, die zum Erzeugen von b_0 in expand_message_xmd verwendet wird. Zweitens, da DST_ext mindestens b Bits lang ist, ist sie mit sehr hoher Wahrscheinlichkeit von den Werten b_0 und strxor(b_0, b_(i - 1)) verschieden, und folglich sind alle Eingaben von H mit hoher Wahrscheinlichkeit von den Eingaben verschieden, die zum Erzeugen von b_i, i >= 1, verwendet werden.

4. (XMD-HMAC-Bereichstrennung.) Diese Methode ist nützlich für die Bereichstrennung von Aufrufen von H innerhalb von HMAC-H (d.h. HMAC [RFC2104] instanziiert mit der Hash-Funktion H) von expand_message_xmd. Sie gilt auch für HKDF-H (d.h. HKDF [RFC5869] instanziiert mit der Hash-Funktion H), wie unten diskutiert.

   Insbesondere gilt diese Methode, wenn HMAC-H mit einem nicht-geheimen Schlüssel verwendet wird, um ein Random Oracle basierend auf einer Hash-Funktion H zu instanziieren (beachten Sie, dass expand_message_xmd auch zu diesem Zweck verwendet werden kann; siehe Abschnitt 10.6). Bei Verwendung von HMAC-H mit einem geheimen Schlüssel mit hoher Entropie ist Bereichstrennung nicht erforderlich; siehe die Diskussion unten.

   Um einen nicht-geheimen HMAC-Schlüssel DST_key zu wählen, der Bereichstrennung von expand_message_xmd gewährleistet, berechnen Sie:

   DST_key_preimage = "DERIVE-HMAC-KEY-" || DST_ext || I2OSP(0, 1) DST_key = H(DST_key_preimage)

   Um dann das Random Oracle Hro unter Verwendung von HMAC-H zu instanziieren, berechnen Sie:

   Hro(msg) = HMAC-H(DST_key, msg)

   Das finale Null-Byte in DST_key_preimage gewährleistet, dass dieser Wert von den Eingaben von H innerhalb von expand_message_xmd verschieden ist (da alle diese Eingaben das Suffix DST_prime haben, das nicht auf einem Null-Byte enden kann, wie oben diskutiert). Dies gewährleistet Bereichstrennung, weil mit überwältigender Wahrscheinlichkeit alle Eingaben von H innerhalb von HMAC-H unter Verwendung des Schlüssels DST_key Präfixe haben, die von den Werten Z_pad, b_0 und strxor(b_0, b_(i - 1)) innerhalb von expand_message_xmd verschieden sind.

   Für Verwendungen von HMAC-H, die ein privates Random Oracle instanziieren, indem ein geheimer Schlüssel mit hoher Entropie festgelegt wird, ist Bereichstrennung von expand_message_xmd nicht erforderlich. Der Grund ist, dass ähnlich wie im obigen Fall alle Eingaben von H innerhalb von HMAC-H unter Verwendung dieses geheimen Schlüssels mit sehr hoher Wahrscheinlichkeit Präfixe haben, die von allen Eingaben von H innerhalb von expand_message_xmd verschieden sind.

   Schließlich kann diese Methode mit HKDF-H [RFC5869] verwendet werden, indem die Salt-Eingabe von HKDF-Extract auf DST_key gesetzt wird, berechnet wie oben. Dies gewährleistet Bereichstrennung für HKDF-Extract durch dasselbe Argument wie für HMAC-H unter Verwendung von DST_key. Darüber hinaus gewährleistet der HKDF-Expand-Schritt, vorausgesetzt, dass das an HKDF-Extract bereitgestellte Input Key Material (IKM) ausreichend hohe Entropie besitzt (sagen wir, proportional zum Sicherheitsparameter), Bereichstrennung durch dasselbe Argument wie für HMAC-H mit einem geheimen Schlüssel mit hoher Entropie (da ein pseudo-zufälliger Schlüssel genau das ist).

10.8. Zielsicherheitsniveaus

Jede kryptographische Suite spezifiziert ein Zielsicherheitsniveau (in Bits) für die zugrundeliegende Kurve. Dieser Parameter stellt sicher, dass die entsprechende hash_to_field-Instanziierung konservativ und korrekt ist. Wir betonen, dass dieser Parameter nur eine obere Schranke für das Sicherheitsniveau der Kurve ist und weder eine Garantie noch eine Bestätigung ihrer Eignung für eine bestimmte Anwendung darstellt. Mathematische und kryptographische Fortschritte können das effektive Sicherheitsniveau jeder Kurve verringern.