10. Sicherheitsüberlegungen

Sicherheitsüberlegungen

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

10.1. Eigenschaften der Codierungen

Jeder Codierungstyp (Abschnitt 3) nimmt einen beliebigen Bytestring entgegen und bildet ihn auf einen Kurvenpunkt ab, der gemäß einer vom Codierungstyp abhängigen Verteilung gezogen wird. Wichtig ist, dass die Verwendung einer nicht gleichmäßigen Codierung oder die direkte Auswertung einer der Abbildungen aus Abschnitt 6 eine Ausgabe erzeugt, die sich leicht von einem gleichverteilt zufälligen Punkt unterscheiden lässt. Anwendungen, die eine nicht gleichmäßige Codierung verwenden, SOLLTEN die Sicherheitsimplikationen dieser Ungleichmäßigkeit sorgfältig analysieren. Ist unklar, welche Codierung erforderlich ist, SOLLTEN Anwendungen eine gleichmäßige Codierung verwenden.

Beide in Abschnitt 3 angegebenen Codierungen können das neutrale Element der Gruppe G erzeugen. Die Wahrscheinlichkeit, dass eine der beiden Codierungsfunktionen bei zufälliger Eingabe das neutrale Element erzeugt, beträgt etwa 1/r, was für kryptografisch nutzbare elliptische Kurven vernachlässigbar ist. Darüber hinaus ist es rechnerisch nicht durchführbar, eine Eingabe für eine der beiden Codierungsfunktionen zu finden, deren zugehörige Ausgabe das neutrale Element ist. (Beide Eigenschaften gelten, wenn die Codierungsfunktionen mit einer hash_to_field-Funktion instanziiert werden, die alle Empfehlungen aus Abschnitt 5 einhält.) Protokolle, die diese Codierungsfunktionen verwenden, SOLLTEN KEINE Sonderfallbehandlung zur Erkennung und „Korrektur" des neutralen Elements hinzufügen.

Wird die Funktion hash_to_curve (Abschnitt 3) mit einer hash_to_field-Funktion instanziiert, die von einem Zufallsorakel ununterscheidbar ist (Abschnitt 5), so ist die resultierende Funktion von einem Zufallsorakel ununterscheidbar ([MRH04] [BCIMRT10] [FFSTV13] [LBB19] [H20]). In vielen Fällen kann eine solche Funktion sicher in kryptografischen Protokollen eingesetzt werden, deren Sicherheitsanalyse ein Zufallsorakel voraussetzt, das gleichverteilt zufällige Punkte auf einer elliptischen Kurve liefert. Wie Ristenpart et al. in [RSS11] erörtern, bleiben jedoch nicht alle Sicherheitsbeweise, die auf Zufallsorakeln beruhen, gültig, wenn diese Orakel durch ununterscheidbare Funktionalitäten ersetzt werden. Diese Einschränkung sollte bei der Analyse der Sicherheit von Protokollen berücksichtigt werden, die auf der Funktion hash_to_curve beruhen.

10.2. Hashing von Passwörtern

Beim Hashing von Passwörtern mittels einer beliebigen der in diesem Dokument beschriebenen Funktionen kann ein Angreifer, der die Ausgabe der Hashfunktion (oder möglicherweise einen beliebigen Zwischenwert, etwa die Ausgabe von hash_to_field) erfährt, in der Lage sein, einen Wörterbuchangriff durchzuführen. Zur Abwehr solcher Angriffe wird empfohlen, zunächst eine aufwendigere Schlüsselableitungsfunktion (beispielsweise PBKDF2 [RFC8018], scrypt [RFC7914] oder Argon2 [RFC9106]) auf das Passwort anzuwenden und anschließend die Ausgabe dieser Funktion auf die elliptische Zielkurve zu hashen. Um Kollisionsresistenz zu gewährleisten, sollte die der Schlüsselableitungsfunktion zugrunde liegende Hashfunktion gemäß den in Abschnitt 5.3.1 aufgeführten Empfehlungen gewählt werden.

10.3. Anforderungen an konstante Laufzeit

Implementierungen aller Funktionen dieses Dokuments in konstanter Zeit werden für alle Einsatzzwecke NACHDRÜCKLICH EMPFOHLEN, um Informationsabflüsse über Seitenkanäle zu vermeiden. Besonders wichtig ist die Verwendung einer Implementierung in konstanter Zeit, wenn die Eingaben einer Codierung geheime Werte sind; in solchen Fällen sind Implementierungen in konstanter Zeit zur Gewährleistung der Sicherheit gegen Timing-Angriffe ERFORDERLICH (beispielsweise [VR20]). Sind Implementierungen in konstanter Zeit erforderlich, so müssen alle Basisoperationen und Hilfsfunktionen in konstanter Zeit implementiert sein, wie in Abschnitt 4 erörtert. In manchen Anwendungen (beispielsweise eingebetteten Systemen) können Informationsabflüsse über andere Seitenkanäle (beispielsweise Stromverbrauchs- oder elektromagnetische Kanäle) relevant sein. Die Abwehr solcher Abflüsse liegt außerhalb des Rahmens dieses Dokuments, da die Art des Abflusses und die geeignete Abwehrmaßnahme von der Anwendung abhängen.

10.4. encode_to_curve: Ausgabeverteilung und Ununterscheidbarkeit

Die Funktion encode_to_curve (Abschnitt 3) liefert Punkte, die gemäß einer Verteilung gezogen werden, die statistisch weit von der Gleichverteilung entfernt ist. Diese Verteilung ist näherungsweise wie folgt beschränkt: Erstens umfasst sie mindestens ein Achtel der Punkte von G, und zweitens variiert die Wahrscheinlichkeit der Punkte in der Verteilung höchstens um den Faktor vier. Diese Schranken gelten, wenn encode_to_curve mit einer beliebigen der map_to_curve-Funktionen aus Abschnitt 6 instanziiert wird.

Die obigen Schranken sind aus mehreren Arbeiten der Literatur abgeleitet. Konkret:

Shallue und van de Woestijne [SW06] sowie Fouque und Tibouchi [FT12] leiten Schranken für die Shallue-van-de-Woestijne-Abbildung (Abschnitt 6.6.1) her.
Fouque und Tibouchi [FT10] sowie Tibouchi [T14] leiten Schranken für die vereinfachte SWU-Abbildung (Abschnitte 6.6.2 und 6.6.3) her.
Bernstein et al. [BHKL13] leiten Schranken für die Elligator-2-Abbildung (Abschnitte 6.7.1 und 6.8.2) her.

Die Ununterscheidbarkeit von encode_to_curve folgt aus einem Argument, das dem von Brier et al. [BCIMRT10] angegebenen ähnelt; wir skizzieren dieses Argument kurz wie folgt. Man betrachte ein ideales Zufallsorakel Hc(), das gemäß der von der von encode_to_curve aufgerufenen map_to_curve-Funktion induzierten Verteilung zieht, und nehme der Einfachheit halber an, dass die elliptische Zielkurve den Kofaktor 1 besitzt (ein ähnliches Argument gilt für von 1 verschiedene Kofaktoren). Die Ununterscheidbarkeit gilt, sofern es möglich ist, das „interne" Zufallsorakel von encode_to_curve, nämlich hash_to_field, effizient zu simulieren. Der Simulator arbeitet 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 (ist msg identisch mit einer früheren Anfrage, so gibt der Simulator einfach den Wert zurück, den er als Antwort auf diese Anfrage geliefert hatte). Anschließend berechnet der Simulator die möglichen Urbilder von P unter map_to_curve, d. h. die Elemente u von F mit map_to_curve(u) == P (Tibouchi [T14] zeigt, dass dies für die Shallue-van-de-Woestijne- und die vereinfachte SWU-Abbildung effizient möglich ist, und Bernstein et al. zeigen dasselbe für Elligator 2). Der Simulator wählt zufällig eines dieser Urbilder aus und gibt diesen Wert als simulierte Ausgabe des „internen" Zufallsorakels zurück. Nach Annahme zieht Hc() gemäß der von map_to_curve auf einem gleichverteilt zufälligen Eingabeelement von F induzierten Verteilung; dieser Wert ist somit gleichverteilt zufällig und induziert den korrekten Punkt P, wenn er an map_to_curve übergeben wird.

10.5. Sicherheit von hash_to_field

Die in Abschnitt 5 definierte Funktion hash_to_field ist von einem Zufallsorakel [MRH04] ununterscheidbar, wenn expand_message (Abschnitt 5.3) als Zufallsorakel modelliert wird. Da Beweise der Ununterscheidbarkeit komponierbar sind, gilt dies weiterhin, wenn expand_message als ununterscheidbar von einem Zufallsorakel bewiesen wird, relativ zu einer als Zufallsorakel modellierten zugrunde liegenden Primitive. Bei Befolgung der Empfehlungen aus Abschnitt 5.3 erfüllen beide in diesem Abschnitt definierten expand_message-Varianten diese Anforderung (siehe auch Abschnitt 10.6).

Wir skizzieren das Ununterscheidbarkeitsargument für hash_to_field nur ganz knapp. Man beachte, dass jede von hash_to_field zurückgegebene ganze Zahl mod p (d. h. jedes Element der Vektordarstellung von F) Mitglied einer Äquivalenzklasse von etwa 2^k ganzen Zahlen der Länge log2(p) + k Bit ist, die alle modulo p gleich sind. Für jede von hash_to_field zurückgegebene ganze Zahl mod p zieht der Simulator zufällig ein Mitglied dieser Äquivalenzklasse und erzeugt den von I2OSP zurückgegebenen Bytestring. (Man beachte, dass dies im Wesentlichen die Umkehrung der hash_to_field-Prozedur ist.)

10.6. Sicherheit von expand_message_xmd

Die in Abschnitt 5.3.1 definierte Funktion expand_message_xmd ist von einem Zufallsorakel [MRH04] ununterscheidbar, wenn eine der folgenden Bedingungen erfüllt ist:

H ist von einem Zufallsorakel ununterscheidbar,
H ist eine Schwamm-Hashfunktion, deren interne Funktion als zufällige Transformation oder zufällige Permutation modelliert wird [BDPV08], oder
H ist eine Hashfunktion vom Merkle-Damgård-Typ, deren Kompressionsfunktion als Zufallsorakel modelliert wird [CDMP05].

Für die Fälle (1) und (2) folgt die Ununterscheidbarkeit von expand_message_xmd unmittelbar aus der Ununterscheidbarkeit von H.

Für Fall (3), d. h. wenn H eine Hashfunktion vom Merkle-Damgård-Typ ist, folgt die Ununterscheidbarkeit aus [CDMP05], Satz 5. Insbesondere berechnet expand_message_xmd b_0, indem der Nachricht ein Block aus Nullen sowie Zusatzinformationen (Länge, Zähler und DST) vorangestellt werden. Anschließend ist jeder der Ausgabeblöcke b_i, i >= 1 in expand_message_xmd das Ergebnis des Aufrufs von H auf eine eindeutige und präfixfreie Codierung 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 besitzt (aufgrund der Aufnahme des Zählerbytes I2OSP(i, 1)).

Der wesentliche Unterschied zwischen der in [CDMP05] erörterten Konstruktion und expand_message_xmd besteht darin, dass Letztere einen an strxor(b_0, b_(i - 1)) angehängten Zähler hasht ({#hashtofield-expand-xmd}, Schritt 10) statt an b_0. Dieser Ansatz vergrößert den Hamming-Abstand zwischen den Eingaben der verschiedenen H-Aufrufe, was die Wahrscheinlichkeit verringert, dass Nichtidealitäten von H die Verteilung der b_i-Werte beeinflussen.

Wir weisen darauf hin, dass expand_message_xmd zur Instanziierung einer ununterscheidbaren Allzweckfunktionalität mit variabler Ausgabelänge verwendet werden kann, aufbauend auf einer beliebigen Hashfunktion, die eines der obigen Kriterien erfüllt. Anwendungen, die expand_message_xmd außerhalb von hash_to_field verwenden, sollten die Domänentrennung durch Wahl eines eigenen Werts für DST sicherstellen.

10.7. Domänentrennung für expand_message-Varianten

Wie in Abschnitt 2.2.5 erörtert, besteht das Ziel der Domänentrennung darin sicherzustellen, dass die Sicherheitsanalysen kryptografischer Protokolle, die mehrere unabhängige Zufallsorakel abfragen, auch dann gültig bleiben, wenn all diese Zufallsorakel aus einer einzigen zugrunde liegenden Funktion H instanziiert werden.

Die expand_message-Varianten dieses Dokuments (Abschnitt 5.3) gewährleisten die Domänentrennung, indem sie allen von H – einer zugrunde liegenden Hashfunktion oder Extendable-Output Function – gehashten Strings ein suffixfrei codiertes Domänentrennungs-Tag DST_prime anfügen. (Andere expand_message-Varianten, die den Empfehlungen aus Abschnitt 5.3.4 folgen, sollten sich ähnlich verhalten, sie sollten jedoch im Einzelfall analysiert werden.) Aus Sicherheitsgründen sollten Anwendungen, die dieselbe Funktion H außerhalb von expand_message verwenden, eine Domänentrennung zwischen diesen H-Verwendungen und expand_message erzwingen und sollten die Gesamtheit dieser Verwendungen von H-Verwendungen in anderen Anwendungen trennen.

Dieser Abschnitt schlägt vier Methoden zur Erzwingung der Domänentrennung gegenüber expand_message-Varianten vor, erläutert, wie jede Methode diese Trennung erreicht, und führt die Situationen auf, in denen jede geeignet ist. Diese Methoden teilen eine allgemeine Struktur: Der Anwendungsentwickler legt ein von DST_prime verschiedenes Tag DST_ext fest und ergänzt die H-Aufrufe um DST_ext. Jede Methode ergänzt die H-Aufrufe auf unterschiedliche Weise, und jede kann zusätzliche Anforderungen an DST_ext stellen.

Diese Methoden können zur Instanziierung mehrerer domänengetrennter Funktionen (beispielsweise H1 und H2) verwendet werden, indem für jede unterschiedliche DST_ext-Werte gewählt werden (beispielsweise DST_ext1, DST_ext2).

(Domänentrennung nur per Suffix.) Diese Methode eignet sich zur Domänentrennung von H-Aufrufen gegenüber denen von expand_message_xmd oder expand_message_xof. Sie ist nicht geeignet, um expand_message von HMAC-H [RFC2104] zu trennen; hierfür siehe Methode 4.

Zur Instanziierung einer nur per Suffix domänengetrennten Funktion Hso berechne man

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

   DST_ext sollte suffixfrei codiert werden (beispielsweise durch
   Anhängen eines Bytes, das die Länge von DST_ext codiert), um das
   Auffinden verschiedener Paare (msg, DST_ext) mit gleichem
   Hashwert undurchführbar zu machen.

   Diese Methode gewährleistet die Domänentrennung, da alle
   verschiedenen H-Aufrufe verschiedene Suffixe besitzen, weil
   DST_ext von DST_prime verschieden ist.

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

   Zur Instanziierung einer per Präfix-Suffix domänengetrennten
   Funktion Hps berechne man

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

   DST_ext sollte präfixfrei codiert werden (beispielsweise durch
   Voranstellen eines Bytes, das die Länge von DST_ext codiert), um
   das Auffinden verschiedener Paare (msg, DST_ext) mit gleichem
   Hashwert undurchführbar zu machen.

   Diese Methode gewährleistet die Domänentrennung, da das Anhängen
   des Bytes I2OSP(0, 1) sicherstellt, dass die H-Eingaben innerhalb
   von Hps von jenen innerhalb von expand_message verschieden sind.
   Konkret codiert 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 stets an die H-Aufrufe innerhalb von
   expand_message angehängt.

3. (Domänentrennung nur per Präfix.) Diese Methode eignet sich nur zur Domänentrennung von H-Aufrufen gegenüber denen von expand_message_xmd. Sie gewährleistet keine Domänentrennung für expand_message_xof oder HMAC-H.

   Zur Instanziierung einer nur per Präfix domänengetrennten
   Funktion Hpo berechne man

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

   Damit diese Methode die Domänentrennung gewährleistet, sollte
   DST_ext eine Länge von mindestens b Bit besitzen, wobei b die
   Anzahl der von der Hashfunktion H erzeugten Bit ist.  Darüber
   hinaus muss mindestens eines der ersten b Bit ungleich null sein.
   Schließlich sollte DST_ext präfixfrei codiert werden
   (beispielsweise durch Voranstellen eines Bytes, das die Länge von
   DST_ext codiert), um das Auffinden verschiedener Paare
   (msg, DST_ext) mit gleichem Hashwert undurchführbar zu machen.

   Diese Methode gewährleistet die Domänentrennung wie folgt.
   Erstens ist DST_ext, da es unter seinen ersten b Bit mindestens
   ein Bit ungleich null enthält, garantiert vom Wert Z_pad
   verschieden (Abschnitt 5.3.1, Schritt 4), was sicherstellt, dass
   alle H-Eingaben von der zur Erzeugung von b_0 in
   expand_message_xmd verwendeten Eingabe verschieden sind.
   Zweitens ist DST_ext, da es eine Länge von mindestens b Bit
   besitzt, mit an Sicherheit grenzender Wahrscheinlichkeit von den
   Werten b_0 und strxor(b_0, b_(i - 1)) verschieden, und folglich
   sind alle H-Eingaben mit hoher Wahrscheinlichkeit von den zur
   Erzeugung von b_i, i >= 1 verwendeten Eingaben verschieden.

4. (XMD-HMAC-Domänentrennung.) Diese Methode eignet sich zur Domänentrennung von H-Aufrufen innerhalb von HMAC-H (d. h. HMAC [RFC2104], instanziiert mit der Hashfunktion H) gegenüber denen von expand_message_xmd. Sie gilt ebenso für HKDF-H (d. h. HKDF [RFC5869], instanziiert mit der Hashfunktion H), wie nachfolgend erörtert.

   Konkret gilt diese Methode, wenn HMAC-H mit einem nicht geheimen
   Schlüssel verwendet wird, um ein auf einer Hashfunktion H
   beruhendes Zufallsorakel zu instanziieren (man beachte, dass
   expand_message_xmd ebenfalls zu diesem Zweck verwendet werden
   kann; siehe Abschnitt 10.6).  Bei Verwendung von HMAC-H mit einem
   geheimen Schlüssel hoher Entropie ist eine Domänentrennung nicht
   erforderlich; siehe die Erörterung weiter unten.

   Zur Wahl eines nicht geheimen HMAC-Schlüssels DST_key, der die
   Domänentrennung gegenüber expand_message_xmd gewährleistet,
   berechne man

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

   Anschließend berechne man zur Instanziierung des Zufallsorakels
   Hro mittels HMAC-H

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

   Das abschließende Nullbyte von DST_key_preimage stellt sicher,
   dass dieser Wert von den H-Eingaben innerhalb von
   expand_message_xmd verschieden ist (da all diese Eingaben
   DST_prime als Suffix besitzen, das, wie oben erörtert, nicht auf
   ein Nullbyte enden kann).  Dies gewährleistet die
   Domänentrennung, da mit überwältigender Wahrscheinlichkeit alle
   H-Eingaben innerhalb von HMAC-H unter Verwendung des Schlüssels
   DST_key Präfixe besitzen, 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 Zufallsorakel durch
   Festlegung eines geheimen Schlüssels hoher Entropie
   instanziieren, ist eine Domänentrennung gegenüber
   expand_message_xmd nicht erforderlich.  Dies liegt daran, dass –
   ähnlich wie im obigen Fall – alle H-Eingaben innerhalb von
   HMAC-H unter Verwendung dieses geheimen Schlüssels mit an
   Sicherheit grenzender Wahrscheinlichkeit Präfixe besitzen, die
   von allen H-Eingaben 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 die
   Domänentrennung für HKDF-Extract nach demselben Argument wie für
   HMAC-H unter Verwendung von DST_key.  Nimmt man darüber hinaus
   an, dass das an HKDF-Extract übergebene Input Keying Material
   (IKM) eine hinreichend hohe Entropie aufweist (etwa dem
   Sicherheitsparameter entsprechend), so ist der HKDF-Expand-
   Schritt nach demselben Argument domänengetrennt wie HMAC-H mit
   einem geheimen Schlüssel hoher Entropie (da ein
   pseudozufälliger Schlüssel genau das ist).

10.8. Angestrebte Sicherheitsniveaus

Jede Cipher Suite spezifiziert ein angestrebtes Sicherheitsniveau (in Bit) für die zugrunde liegende Kurve. Dieser Parameter stellt sicher, dass die entsprechende Instanziierung von hash_to_field konservativ und korrekt ist. Wir betonen, dass dieser Parameter lediglich eine obere Schranke für das Sicherheitsniveau der Kurve darstellt und weder eine Garantie noch eine Bestätigung ihrer Eignung für eine bestimmte Anwendung ist. Mathematische und kryptografische Fortschritte können das effektive Sicherheitsniveau jeder beliebigen Kurve verringern.