Zum Hauptinhalt springen

5. Hashing auf ein endliches Feld

Die Funktion hash_to_field hasht einen Byte-String msg beliebiger Länge auf ein oder mehrere Elemente eines Feldes F. Diese Funktion arbeitet in zwei Schritten: Sie hasht zunächst den Eingabe-Byte-String, um einen gleichmäßig zufälligen Byte-String zu erzeugen, und interpretiert dann diesen Byte-String als ein oder mehrere Elemente von F.

Für den ersten Schritt ruft hash_to_field eine Hilfsfunktion expand_message auf. Dieses Dokument definiert zwei Varianten von expand_message: eine geeignet für Hash-Funktionen wie SHA-2 [FIPS180-4] oder SHA-3 [FIPS202], und eine andere geeignet für erweiterbare Ausgabefunktionen wie SHAKE128 [FIPS202]. Sicherheitsüberlegungen für jede expand_message-Variante werden unten diskutiert (Abschnitte 5.3.1 und 5.3.2).

Implementierer DÜRFEN NICHT Rejection-Sampling verwenden, um ein gleichmäßig zufälliges Element von F zu erzeugen, um sicherzustellen, dass die hash_to_field-Funktion für eine Implementierung in konstanter Zeit geeignet ist. Der Grund dafür ist, dass Rejection-Sampling-Verfahren schwierig in konstanter Zeit zu implementieren sind, und spätere gut gemeinte "Optimierungen" eine Implementierung stillschweigend nicht-konstant-zeitig machen können. Dies bedeutet, dass jede auf Rejection-Sampling basierende hash_to_field-Funktion mit einer Implementierung in konstanter Zeit inkompatibel wäre.

Die hash_to_field-Funktion eignet sich auch zum sicheren Hashing auf Skalare. Zum Beispiel genügt es beim Hashing auf das Skalarfeld für eine elliptische Kurven-(Unter-)Gruppe mit Primzahlordnung r, hash_to_field mit dem Zielfeld GF(r) zu instanziieren.

Die hash_to_field-Funktion ist so konzipiert, dass sie von einem Zufallsorakel [MRH04] ununterscheidbar ist, wenn expand_message (Abschnitt 5.3) als Zufallsorakel modelliert wird (siehe Abschnitt 10.5 für Details zur Ununterscheidbarkeit). Die Gewährleistung der Ununterscheidbarkeit erfordert Sorgfalt; um zu verstehen warum, betrachten Sie eine Primzahl p, die nahe bei 3/4 * 2^256 liegt. Die Reduktion einer zufälligen 256-Bit-Ganzzahl modulo diesem p ergibt einen Wert, der mit einer Wahrscheinlichkeit von etwa 1/2 im Bereich [0, p / 3] liegt, was bedeutet, dass dieser Wert statistisch weit von gleichmäßig in [0, p - 1] entfernt ist.

Um Verzerrungen zu kontrollieren, verwendet hash_to_field stattdessen zufällige Ganzzahlen, deren Länge mindestens ceil(log2(p)) + k Bits beträgt, wobei k das Zielsicherheitsniveau für die Suite in Bits ist. Die Reduktion solcher Ganzzahlen mod p ergibt eine Verzerrung von höchstens 2^-k für jedes p; diese Verzerrung ist angemessen, wenn k-Bit-Sicherheit angestrebt wird. Für jede solche Ganzzahl verwendet hash_to_field expand_message, um L gleichmäßige Bytes zu erhalten, wobei:

L = ceil((ceil(log2(p)) + k) / 8)

Diese gleichmäßigen Bytes werden dann über OS2IP als Ganzzahl interpretiert. Zum Beispiel für eine 255-Bit-Primzahl p und k = 128-Bit-Sicherheit, L = ceil((255 + 128) / 8) = 48 Bytes.

Beachten Sie, dass k eine obere Grenze für das Sicherheitsniveau der entsprechenden Kurve ist. Siehe Abschnitt 10.8 für weitere Details und Abschnitt 8.9 für Richtlinien zur Wahl von k für eine gegebene Kurve.

5.1. Effizienzüberlegungen in Erweiterungsfeldern​

Die in diesem Abschnitt beschriebene hash_to_field-Funktion ist für bestimmte Erweiterungsfelder ineffizient. Insbesondere beim Hashing auf ein Element des Erweiterungsfeldes GF(p^m) erfordert hash_to_field die Erweiterung von msg auf m * L Bytes (für L wie oben definiert). Für Erweiterungsfelder, bei denen log2(p) deutlich kleiner als das Sicherheitsniveau k ist, ist dieser Ansatz ineffizient: Er erfordert, dass expand_message etwa m * log2(p) + m * k Bits ausgibt, während m * log2(p) + k Bytes ausreichen, um ein Element von GF(p^m) mit einer Verzerrung von höchstens 2^-k zu erzeugen. In solchen Fällen KÖNNEN Anwendungen eine alternative hash_to_field-Funktion verwenden, vorausgesetzt, sie erfüllt die folgenden Sicherheitsanforderungen:

  • Die Funktion MUSS ein oder mehrere Feldelemente ausgeben, die gleichmäßig zufällig sind, mit Ausnahme einer Verzerrung von höchstens 2^-k.

  • Die Funktion DARF NICHT Rejection-Sampling verwenden.

  • Die Funktion SOLLTE für Straight-Line-Implementierungen geeignet sein.

Zum Beispiel beschreibt Pornin [P20] eine Methode zum Hashing auf GF(9767^19), die diese Anforderungen erfüllt und dabei weniger Ausgabebits von expand_message verwendet als hash_to_field für dieses Feld verwenden würde.

5.2. hash_to_field-Implementierung​

Das folgende Verfahren implementiert hash_to_field.

Der expand_message-Parameter für diese Funktion MUSS den in Abschnitt 5.3 angegebenen Anforderungen entsprechen. Abschnitt 3.1 behandelt die ERFORDERLICHE Methode zur Konstruktion von DST, dem Domänentrennungs-Tag. Beachten Sie, dass hash_to_field fehlschlagen kann (ABORT), wenn expand_message fehlschlägt.

hash_to_field(msg, count)

Parameter:

  • DST, ein Domänentrennungs-Tag (siehe Abschnitt 3.1).
  • F, ein endliches Feld der Charakteristik p und Ordnung q = p^m.
  • p, die Charakteristik von F (siehe unmittelbar oben).
  • m, der Erweiterungsgrad von F, m >= 1 (siehe unmittelbar oben).
  • L = ceil((ceil(log2(p)) + k) / 8), wobei k der Sicherheitsparameter der Suite ist (z. B. k = 128).
  • expand_message, eine Funktion, die einen Byte-String und ein Domänentrennungs-Tag auf einen gleichmäßig zufälligen Byte-String erweitert (siehe Abschnitt 5.3).

Eingabe:

  • msg, ein Byte-String, der die zu hashende Nachricht enthält.
  • count, die Anzahl der zu erzeugenden Elemente von F.

Ausgabe:

  • (u_0, ..., u_(count - 1)), eine Liste von Feldelementen.

Schritte:

  1. len_in_bytes = count * m * L
  2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
  3. für i in (0, ..., count - 1):
  4. für j in (0, ..., m - 1):
  5. elm_offset = L * (j + i * m)
  6. tv = substr(uniform_bytes, elm_offset, L)
  7. e_j = OS2IP(tv) mod p
  8. u_i = (e_0, ..., e_(m - 1))
  9. return (u_0, ..., u_(count - 1))

5.3. expand_message​

expand_message ist eine Funktion, die einen gleichmäßig zufälligen Byte-String erzeugt. Sie nimmt drei Argumente:

  1. msg, ein Byte-String, der die zu hashende Nachricht enthält,

  2. DST, ein Byte-String, der als Domänentrennungs-Tag fungiert, und

  3. len_in_bytes, die Anzahl der zu erzeugenden Bytes.

Dieses Dokument definiert die folgenden zwei Varianten von expand_message:

  • expand_message_xmd (Abschnitt 5.3.1) ist geeignet für die Verwendung mit einer breiten Palette von Hash-Funktionen, einschließlich SHA-2 [FIPS180-4], SHA-3 [FIPS202], BLAKE2 [RFC7693] und anderen.

  • expand_message_xof (Abschnitt 5.3.2) ist geeignet für die Verwendung mit erweiterbaren Ausgabefunktionen (XOFs), einschließlich Funktionen aus den SHAKE [FIPS202]- oder BLAKE2X [BLAKE2X]-Familien.

Diese Varianten sollten für die überwiegende Mehrheit der Anwendungsfälle ausreichen, aber andere Varianten sind möglich; Abschnitt 5.3.4 behandelt die Anforderungen.

5.3.1. expand_message_xmd​

Die Funktion expand_message_xmd erzeugt einen gleichmäßig zufälligen Byte-String unter Verwendung einer kryptografischen Hash-Funktion H, die b Bits ausgibt. Für die Sicherheit MUSS H die folgenden Anforderungen erfüllen:

  • Die Anzahl der von H ausgegebenen Bits MUSS b >= 2 * k sein, wobei k das Zielsicherheitsniveau in Bits ist, und b MUSS durch 8 teilbar sein. Die erste Anforderung gewährleistet k-Bit-Kollisionsresistenz; die zweite gewährleistet die Gleichmäßigkeit der Ausgabe von expand_message_xmd.

  • H KANN eine Merkle-Damgaard-Hash-Funktion wie SHA-2 sein. In diesem Fall gilt die Sicherheit, wenn die zugrunde liegende Kompressionsfunktion als Zufallsorakel modelliert wird [CDMP05]. (Siehe Abschnitt 10.6 zur Diskussion.)

  • H KANN eine schwammbasierte Hash-Funktion wie SHA-3 oder BLAKE2 sein. In diesem Fall gilt die Sicherheit, wenn die innere Funktion als zufällige Transformation oder als zufällige Permutation modelliert wird [BDPV08].

  • Andernfalls MUSS H eine Hash-Funktion sein, die nachweislich von einem Zufallsorakel [MRH04] unter einer vernünftigen kryptografischen Annahme ununterscheidbar ist.

SHA-2 [FIPS180-4] und SHA-3 [FIPS202] sind typische und EMPFOHLENE Wahlen. Als Beispiel wäre für das 128-Bit-Sicherheitsniveau b >= 256 Bits und entweder SHA-256 oder SHA3-256 eine geeignete Wahl.

Die Hash-Funktion H arbeitet, indem sie wiederholt Datenblöcke fester Länge aufnimmt. Die Länge dieser Blöcke in Bits wird als Eingabeblockgröße (s) bezeichnet. Als Beispiele: s = 1024 für SHA-512 [FIPS180-4] und s = 576 für SHA3-512 [FIPS202]. Für die Korrektheit erfordert H b <= s.

Das folgende Verfahren implementiert expand_message_xmd.

expand_message_xmd(msg, DST, len_in_bytes)

Parameter:

  • H, eine Hash-Funktion (siehe Anforderungen oben).
  • b_in_bytes, b / 8 für b die Ausgabegröße von H in Bits. Zum Beispiel für b = 256, b_in_bytes = 32.
  • s_in_bytes, die Eingabeblockgröße von H, gemessen in Bytes (siehe Diskussion oben). Zum Beispiel für SHA-256, s_in_bytes = 64.

Eingabe:

  • msg, ein Byte-String.
  • DST, ein Byte-String von höchstens 255 Bytes. Siehe unten für Informationen zur Verwendung längerer DSTs.
  • len_in_bytes, die Länge der angeforderten Ausgabe in Bytes, nicht größer als das Minimum von (255 * b_in_bytes) oder 2^16-1.

Ausgabe:

  • uniform_bytes, ein Byte-String.

Schritte:

  1. ell = ceil(len_in_bytes / b_in_bytes)
  2. ABORT wenn ell > 255 oder len_in_bytes > 65535 oder len(DST) > 255
  3. DST_prime = DST || I2OSP(len(DST), 1)
  4. Z_pad = I2OSP(0, s_in_bytes)
  5. l_i_b_str = I2OSP(len_in_bytes, 2)
  6. msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
  7. b_0 = H(msg_prime)
  8. b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
  9. für i in (2, ..., ell):
  10. b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
  11. uniform_bytes = b_1 || ... || b_ell
  12. return substr(uniform_bytes, 0, len_in_bytes)

Beachten Sie, dass der String Z_pad (Schritt 6) msg vorangestellt wird, bevor b_0 berechnet wird (Schritt 7). Dies ist für die Sicherheit notwendig, wenn H ein Merkle-Damgaard-Hash ist, z. B. SHA-2 (siehe Abschnitt 10.6). Das Hashing dieser zusätzlichen Daten bedeutet, dass die Kosten für die Berechnung von b_0 höher sind als die Kosten für die einfache Berechnung von H(msg). In den meisten Fällen ist dieser Overhead vernachlässigbar, da die Kosten für die Auswertung von H viel geringer sind als die anderen Kosten, die beim Hashing auf eine Kurve anfallen.

Es ist jedoch möglich, diesen Overhead vollständig zu vermeiden, indem man die Tatsache ausnutzt, dass Z_pad nur von H abhängt und nicht von den Argumenten von expand_message_xmd. Dazu berechnen Sie zunächst den internen Zustand von H nach der Aufnahme von Z_pad vor und speichern ihn. Dann initialisieren Sie bei der Berechnung von b_0 H mit dem gespeicherten Zustand. Weitere Details sind implementierungsabhängig und liegen außerhalb des Umfangs dieses Dokuments.

5.3.2. expand_message_xof​

Die Funktion expand_message_xof erzeugt einen gleichmäßig zufälligen Byte-String unter Verwendung einer erweiterbaren Ausgabefunktion (XOF) H. Für die Sicherheit MUSS H die folgenden Kriterien erfüllen:

  • Die Kollisionsresistenz von H MUSS mindestens k Bits betragen.

  • H MUSS eine XOF sein, die nachweislich von einem Zufallsorakel unter einer vernünftigen kryptografischen Annahme ununterscheidbar ist.

Die SHAKE-XOF-Familie [FIPS202] ist eine typische und EMPFOHLENE Wahl. Als Beispiel wäre für 128-Bit-Sicherheit SHAKE128 eine geeignete Wahl.

Das folgende Verfahren implementiert expand_message_xof.

expand_message_xof(msg, DST, len_in_bytes)

Parameter:

  • H(m, d), eine erweiterbare Ausgabefunktion, die die Eingabenachricht m verarbeitet und d Bytes zurückgibt.

Eingabe:

  • msg, ein Byte-String.
  • DST, ein Byte-String von höchstens 255 Bytes. Siehe unten für Informationen zur Verwendung längerer DSTs.
  • len_in_bytes, die Länge der angeforderten Ausgabe in Bytes.

Ausgabe:

  • uniform_bytes, ein Byte-String.

Schritte:

  1. ABORT wenn len_in_bytes > 65535 oder len(DST) > 255
  2. DST_prime = DST || I2OSP(len(DST), 1)
  3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime
  4. uniform_bytes = H(msg_prime, len_in_bytes)
  5. return uniform_bytes

5.3.3. Verwendung von DSTs länger als 255 Bytes​

Die in diesem Abschnitt definierten expand_message-Varianten akzeptieren Domänentrennungs-Tags von höchstens 255 Bytes. Wenn Anwendungen ein Domänentrennungs-Tag von mehr als 255 Bytes benötigen, z. B. aufgrund von Anforderungen eines aufrufenden Protokolls, MÜSSEN Implementierer ein kurzes Domänentrennungs-Tag durch Hashing berechnen, wie folgt:

  • Für expand_message_xmd mit Hash-Funktion H wird DST wie folgt berechnet:

    DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)

  • Für expand_message_xof mit erweiterbarer Ausgabefunktion H wird DST wie folgt berechnet:

    DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST, ceil(2 * k / 8))

Hier ist a_very_long_DST das DST, dessen Länge größer als 255 Bytes ist, "H2C-OVERSIZE-DST-" ist ein 17-Byte-ASCII-String-Literal, und k ist das Zielsicherheitsniveau in Bits.

5.3.4. Definition anderer expand_message-Varianten​

Bei der Definition einer neuen expand_message-Variante ist die wichtigste Überlegung, dass hash_to_field expand_message als Zufallsorakel modelliert. Daher SOLLTEN Implementierer die Ununterscheidbarkeit von einem Zufallsorakel unter einer geeigneten Annahme über die zugrunde liegenden kryptografischen Primitive nachweisen; siehe Abschnitt 10.5 für weitere Informationen.

Darüber hinaus expand_message-Varianten:

  • MÜSSEN Kollisionsresistenz bieten, die dem Sicherheitsniveau der Ziel-elliptischen Kurve entspricht.

  • MÜSSEN auf Primitiven aufbauen, die für die Verwendung in Anwendungen entwickelt wurden, die kryptografische Zufälligkeit erfordern. Als Beispiele ist eine sichere Stream-Cipher eine geeignete Primitive, während ein Mersenne-Twister-Pseudozufallszahlengenerator [MT98] es nicht ist.

  • DÜRFEN NICHT Rejection-Sampling verwenden.

  • MÜSSEN unabhängige Werte für unterschiedliche (msg, DST, Länge)-Eingaben liefern. Diese Anforderung zu erfüllen ist subtil. Als vereinfachtes Beispiel funktioniert das Hashing von msg || DST nicht, da in diesem Fall unterschiedliche (msg, DST)-Paare, deren Verkettungen gleich sind, dieselbe Ausgabe zurückgeben (z. B. ("AB", "CDEF") und ("ABC", "DEF")). Die in diesem Dokument definierten Varianten verwenden eine suffix-freie Kodierung von DST, um dieses Problem zu vermeiden.

  • MÜSSEN das Domänentrennungs-Tag DST verwenden, um sicherzustellen, dass Aufrufe kryptografischer Primitive innerhalb von expand_message domänengetrennt von Aufrufen außerhalb von expand_message sind. Wenn beispielsweise die expand_message-Variante eine Hash-Funktion H verwendet, MUSS eine Kodierung von DST entweder als Präfix oder als Suffix der Eingabe für jeden Aufruf von H hinzugefügt werden. Das Hinzufügen von DST als Suffix ist der EMPFOHLENE Ansatz.

  • SOLLTEN msg genau einmal lesen, aus Effizienzgründen, wenn msg lang ist.

Darüber hinaus MUSS jede expand_message-Variante ein eindeutiges EXP_TAG angeben, das diese Variante in einer Suite-ID identifiziert. Siehe Abschnitt 8.10 für weitere Informationen.

Letztes Update am