5. Hashing auf einen endlichen Körper

Die Funktion hash_to_field hasht einen Bytestring msg beliebiger Länge auf ein oder mehrere Elemente eines Körpers F. Diese Funktion arbeitet in zwei Schritten: Zunächst hasht sie den Eingabe-Bytestring, um einen gleichverteilt zufälligen Bytestring zu erzeugen, und interpretiert diesen Bytestring anschließend 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 für Hashfunktionen wie SHA-2 [FIPS180-4] oder SHA-3 [FIPS202] geeignete und eine für Extendable-Output Functions wie SHAKE128 [FIPS202] geeignete. Die Sicherheitsüberlegungen zu den einzelnen expand_message-Varianten werden weiter unten behandelt (Abschnitte 5.3.1 und 5.3.2).

Implementierer DÜRFEN NICHT Rejection Sampling verwenden, um ein gleichverteilt zufälliges Element von F zu erzeugen, damit die Funktion hash_to_field für eine Implementierung in konstanter Zeit geeignet bleibt. Der Grund dafür ist, dass Rejection-Sampling-Verfahren schwer in konstanter Zeit zu implementieren sind und dass spätere – selbst gut gemeinte – „Optimierungen" eine Implementierung stillschweigend nicht mehr konstantzeitig machen können. Das bedeutet, dass jede auf Rejection Sampling beruhende hash_to_field-Funktion mit einer Implementierung in konstanter Zeit unvereinbar wäre.

Die Funktion hash_to_field eignet sich zudem für sicheres Hashing auf Skalare. Um beispielsweise auf den Skalarkörper einer elliptischen Kurven-(Unter-)Gruppe von Primzahlordnung r zu hashen, genügt es, hash_to_field mit dem Zielkörper GF(r) zu instanziieren.

Die Funktion hash_to_field ist so entworfen, dass sie von einem Zufallsorakel [MRH04] ununterscheidbar ist, wenn expand_message (Abschnitt 5.3) als Zufallsorakel modelliert wird (siehe Abschnitt 10.5 für Einzelheiten zu ihrer Ununterscheidbarkeit). Die Gewährleistung der Ununterscheidbarkeit erfordert Sorgfalt; um zu verstehen, warum, betrachte man eine Primzahl p nahe 3/4 * 2^256. Die Reduktion einer zufälligen 256-Bit-Ganzzahl modulo diesem p liefert mit einer Wahrscheinlichkeit von etwa 1/2 einen Wert im Intervall [0, p / 3], was bedeutet, dass dieser Wert statistisch weit von der Gleichverteilung auf [0, p - 1] entfernt ist.

Um die Verzerrung zu kontrollieren, verwendet hash_to_field stattdessen zufällige ganze Zahlen mit einer Länge von mindestens ceil(log2(p)) + k Bit, wobei k das angestrebte Sicherheitsniveau der Suite in Bit ist. Die Reduktion solcher ganzen Zahlen mod p ergibt für jedes p eine Verzerrung von höchstens 2^-k; diese Verzerrung ist angemessen, wenn eine Sicherheit von k Bit angestrebt wird. Für jede dieser ganzen Zahlen verwendet hash_to_field expand_message, um L gleichverteilte Bytes zu erhalten, wobei

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

Diese gleichverteilten Bytes werden anschließend mittels OS2IP als ganze Zahl interpretiert. Beispielsweise gilt für eine 255-Bit-Primzahl p und eine Sicherheit von k = 128 Bit: L = ceil((255 + 128) / 8) = 48 Byte.

Man beachte, dass k eine obere Schranke für das Sicherheitsniveau der jeweiligen Kurve darstellt. Siehe Abschnitt 10.8 für Einzelheiten und Abschnitt 8.9 für Empfehlungen zur Wahl von k für eine gegebene Kurve.

5.1. Effizienzüberlegungen in Erweiterungskörpern

Die in diesem Abschnitt beschriebene Funktion hash_to_field ist für manche Erweiterungskörper ineffizient. Konkret erfordert hash_to_field beim Hashing auf ein Element des Erweiterungskörpers GF(p^m), msg auf m * L Bytes zu expandieren (mit L wie oben definiert). Für Erweiterungskörper, bei denen log2(p) deutlich kleiner als das Sicherheitsniveau k ist, ist dieser Ansatz ineffizient: Er verlangt von expand_message die Erzeugung von etwa m * log2(p) + m * k Bit, obwohl m * log2(p) + k Byte 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, sofern diese die folgenden Sicherheitsanforderungen erfüllt:

• Die Funktion MUSS ein oder mehrere gleichverteilt zufällige Körperelemente erzeugen, bis auf eine Verzerrung von höchstens 2^-k.

• Die Funktion DARF NICHT Rejection Sampling verwenden.

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

Beispielsweise beschreibt Pornin [P20] eine Methode zum Hashing auf GF(9767^19), die diese Anforderungen erfüllt und dabei weniger Ausgabebits von expand_message benötigt, als hash_to_field für diesen Körper benötigen würde.

5.2. Implementierung von hash_to_field

Die folgende Prozedur implementiert hash_to_field.

Der Parameter expand_message dieser Funktion MUSS den in Abschnitt 5.3 angegebenen Anforderungen entsprechen. Abschnitt 3.1 beschreibt die ERFORDERLICHE Methode zur Konstruktion von DST, dem Domänentrennungs-Tag. Man beachte, dass hash_to_field fehlschlagen (ABORT) kann, wenn expand_message fehlschlägt.

hash_to_field(msg, count)

Parameters:
- DST, a domain separation tag (see Section 3.1).
- F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above).
- L = ceil((ceil(log2(p)) + k) / 8), where k is the security
  parameter of the suite (e.g., k = 128).
- expand_message, a function that expands a byte string and
  domain separation tag into a uniformly random byte string
  (see Section 5.3).

Input:
- msg, a byte string containing the message to hash.
- count, the number of elements of F to output.

Output:
- (u_0, ..., u_(count - 1)), a list of field elements.

Steps:
1. len_in_bytes = count * m * L
2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
3. for i in (0, ..., count - 1):
4.   for 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 gleichverteilt zufälligen Bytestring erzeugt. Sie nimmt drei Argumente entgegen:

1. msg, einen Bytestring, der die zu hashende Nachricht enthält,

2. DST, einen Bytestring, der als Domänentrennungs-Tag fungiert, und

3. len_in_bytes, die Anzahl der zu erzeugenden Bytes.

Dieses Dokument definiert die folgenden beiden Varianten von expand_message:

• expand_message_xmd (Abschnitt 5.3.1) eignet sich für eine breite Palette von Hashfunktionen, insbesondere SHA-2 [FIPS180-4], SHA-3 [FIPS202], BLAKE2 [RFC7693] und andere.

• expand_message_xof (Abschnitt 5.3.2) eignet sich für Extendable-Output Functions (XOFs), insbesondere Funktionen der SHAKE-Familie [FIPS202] oder BLAKE2X [BLAKE2X].

Diese Varianten dürften für die überwiegende Mehrheit der Anwendungsfälle ausreichen, weitere Varianten sind jedoch möglich; Abschnitt 5.3.4 legt die entsprechenden Anforderungen dar.

5.3.1. expand_message_xmd

Die Funktion expand_message_xmd erzeugt einen gleichverteilt zufälligen Bytestring mithilfe einer kryptografischen Hashfunktion H, die b Bit ausgibt. Aus Sicherheitsgründen MUSS H die folgenden Anforderungen erfüllen:

• Die Anzahl der von H erzeugten Bit MUSS b >= 2 * k erfüllen, wobei k das angestrebte Sicherheitsniveau in Bit ist, und b MUSS durch 8 teilbar sein. Die erste Anforderung gewährleistet Kollisionsresistenz von k Bit; die zweite gewährleistet die Gleichverteilung der Ausgabe von expand_message_xmd.

• H KANN eine Hashfunktion vom Merkle-Damgård-Typ wie SHA-2 sein. In diesem Fall ist die Sicherheit gewährleistet, wenn die zugrunde liegende Kompressionsfunktion als Zufallsorakel modelliert wird [CDMP05]. (Siehe Abschnitt 10.6 für eine Erörterung.)

• H KANN eine Schwamm-Hashfunktion wie SHA-3 oder BLAKE2 sein. In diesem Fall ist die Sicherheit gewährleistet, wenn die interne Funktion als zufällige Transformation oder als zufällige Permutation modelliert wird [BDPV08].

• Andernfalls MUSS H eine Hashfunktion sein, deren Ununterscheidbarkeit von einem Zufallsorakel [MRH04] unter einer vernünftigen kryptografischen Annahme bewiesen wurde.

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

Es wird angenommen, dass die Hashfunktion H arbeitet, indem sie wiederholt Datenblöcke fester Länge aufnimmt. Die Bitlänge dieser Blöcke wird als Eingabeblockgröße (s) bezeichnet. 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.

Die folgende Prozedur implementiert expand_message_xmd.

expand_message_xmd(msg, DST, len_in_bytes)

Parameters:
- H, a hash function (see requirements above).
- b_in_bytes, b / 8 for b the output size of H in bits.
  For example, for b = 256, b_in_bytes = 32.
- s_in_bytes, the input block size of H, measured in bytes (see
  discussion above). For example, for SHA-256, s_in_bytes = 64.

Input:
- msg, a byte string.
- DST, a byte string of at most 255 bytes.
  See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes,
  not greater than the lesser of (255 * b_in_bytes) or 2^16-1.

Output:
- uniform_bytes, a byte string.

Steps:
1.  ell = ceil(len_in_bytes / b_in_bytes)
2.  ABORT if ell > 255 or len_in_bytes > 65535 or 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.  for 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)

Man beachte, dass der String Z_pad (Schritt 6) msg vorangestellt wird, bevor b_0 berechnet wird (Schritt 7). Dies ist aus Sicherheitsgründen erforderlich, wenn H ein Hash vom Merkle-Damgård-Typ ist, beispielsweise SHA-2 (siehe Abschnitt 10.6). Das Hashen dieser zusätzlichen Daten bedeutet, dass die Kosten für die Berechnung von b_0 höher sind als die Kosten der bloßen Berechnung von H(msg). In den meisten Kontexten ist dieser Mehraufwand vernachlässigbar, da die Kosten der Auswertung von H weit unter den übrigen Kosten des Hashings auf eine Kurve liegen.

Es ist jedoch möglich, diesen Mehraufwand vollständig zu vermeiden, indem man ausnutzt, dass Z_pad nur von H und nicht von den Argumenten von expand_message_xmd abhängt. Dazu berechnet und speichert man zunächst vorab den internen Zustand von H nach Aufnahme von Z_pad. Anschließend initialisiert man H bei der Berechnung von b_0 aus dem gespeicherten Zustand. Weitere Einzelheiten sind implementierungsabhängig und liegen außerhalb des Rahmens dieses Dokuments.

5.3.2. expand_message_xof

Die Funktion expand_message_xof erzeugt einen gleichverteilt zufälligen Bytestring mithilfe einer Extendable-Output Function (XOF) H. Aus Sicherheitsgründen MUSS H die folgenden Kriterien erfüllen:

• Die Kollisionsresistenz von H MUSS mindestens k Bit betragen.

• H MUSS eine XOF sein, deren Ununterscheidbarkeit von einem Zufallsorakel unter einer vernünftigen kryptografischen Annahme bewiesen wurde.

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

Die folgende Prozedur implementiert expand_message_xof.

expand_message_xof(msg, DST, len_in_bytes)

Parameters:
- H(m, d), an extendable-output function that processes
  input message m and returns d bytes.

Input:
- msg, a byte string.
- DST, a byte string of at most 255 bytes.
  See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes.

Output:
- uniform_bytes, a byte string.

Steps:
1. ABORT if len_in_bytes > 65535 or 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 mit mehr als 255 Byte

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

• Für expand_message_xmd unter Verwendung der Hashfunktion H wird DST berechnet als

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

• Für expand_message_xof unter Verwendung der Extendable-Output Function H wird DST berechnet als

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

Dabei ist a_very_long_DST das DST mit einer Länge von mehr als 255 Byte, „H2C-OVERSIZE-DST-" ein 17 Byte langes ASCII-String-Literal und k das angestrebte Sicherheitsniveau in Bit.

5.3.4. Definition weiterer 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 beweisen; siehe Abschnitt 10.5 für weitere Informationen.

Darüber hinaus gilt für expand_message-Varianten:

• Sie MÜSSEN eine Kollisionsresistenz bieten, die dem Sicherheitsniveau der elliptischen Zielkurve entspricht.

• Sie MÜSSEN auf Primitiven aufbauen, die für den Einsatz in Anwendungen entworfen wurden, welche kryptografische Zufälligkeit erfordern. Beispielsweise ist eine sichere Stromchiffre eine geeignete Primitive, ein Pseudozufallszahlengenerator vom Typ Mersenne Twister [MT98] hingegen nicht.

• Sie DÜRFEN NICHT Rejection Sampling verwenden.

• Sie MÜSSEN für verschiedene Eingaben (msg, DST, length) unabhängige Werte liefern. Die Erfüllung dieser Anforderung ist subtil. Als vereinfachtes Beispiel ist das Hashen von msg || DST ungeeignet, denn in diesem Fall würden verschiedene Paare (msg, DST), deren Verkettungen gleich sind, dieselbe Ausgabe liefern (etwa ("AB", "CDEF") und ("ABC", "DEF")). Die in diesem Dokument definierten Varianten verwenden eine suffixfreie Codierung von DST, um dieses Problem zu vermeiden.

• Sie 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. Verwendet die expand_message-Variante beispielsweise eine Hashfunktion H, so MUSS eine Codierung von DST der Eingabe jedes H-Aufrufs entweder vorangestellt oder angehängt werden. Das Anhängen von DST als Suffix ist der EMPFOHLENE Ansatz.

• Sie SOLLTEN msg genau einmal lesen, aus Effizienzgründen bei langem msg.

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