Passa al contenuto principale

5. Hashing su un campo finito

La funzione hash_to_field esegue l'hashing di una stringa di byte msg di lunghezza arbitraria in uno o più elementi di un campo F. Questa funzione lavora in due passaggi: prima esegue l'hashing della stringa di byte di input per produrre una stringa di byte uniformemente casuale, quindi interpreta tale stringa di byte come uno o più elementi di F.

Per il primo passaggio, hash_to_field chiama una funzione ausiliaria expand_message. Questo documento definisce due varianti di expand_message: una appropriata per funzioni di hash come SHA-2 [FIPS180-4] o SHA-3 [FIPS202], e un'altra appropriata per funzioni a output estensibile come SHAKE128 [FIPS202]. Le considerazioni sulla sicurezza per ciascuna variante di expand_message sono discusse di seguito (Sezioni 5.3.1 e 5.3.2).

Gli implementatori NON DEVONO utilizzare il campionamento per rifiuto per generare un elemento di F uniformemente casuale, al fine di garantire che la funzione hash_to_field si presti a un'implementazione a tempo costante. La ragione è che le procedure di campionamento per rifiuto sono difficili da implementare a tempo costante e che le successive "ottimizzazioni" ben intenzionate possono rendere silenziosamente un'implementazione non a tempo costante. Ciò significa che qualsiasi funzione hash_to_field basata sul campionamento per rifiuto sarebbe incompatibile con un'implementazione a tempo costante.

La funzione hash_to_field è adatta anche per l'hashing sicuro in scalari. Ad esempio, quando si esegue l'hashing nel campo scalare per un (sotto)gruppo di curva ellittica di ordine primo r, è sufficiente istanziare hash_to_field con il campo di destinazione GF(r).

La funzione hash_to_field è progettata per essere indifferenziabile da un random oracle [MRH04] quando expand_message (Sezione 5.3) è modellato come un random oracle (vedere la Sezione 10.5 per ulteriori dettagli sulla sua indifferenziabilità). Garantire l'indifferenziabilità richiede cautela; per capire perché, si consideri un numero primo p che è vicino a 3/4 * 2^256. La riduzione di un intero casuale a 256 bit modulo tale p produce un valore che si trova nell'intervallo [0, p / 3] con una probabilità di circa 1/2, il che significa che questo valore è statisticamente lontano dall'essere uniforme in [0, p - 1].

Per controllare il bias, hash_to_field utilizza invece interi casuali la cui lunghezza è di almeno ceil(log2(p)) + k bit, dove k è il livello di sicurezza di destinazione per la suite in bit. La riduzione di tali interi mod p produce un bias di al massimo 2^-k per ogni p; questo bias è appropriato quando si mira a una sicurezza di k bit. Per ogni intero di questo tipo, hash_to_field utilizza expand_message per ottenere L byte uniformi, dove:

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

Questi byte uniformi vengono quindi interpretati come un intero tramite OS2IP. Ad esempio, per un numero primo p a 255 bit e una sicurezza k = 128 bit, L = ceil((255 + 128) / 8) = 48 byte.

Si noti che k è un limite superiore del livello di sicurezza per la curva corrispondente. Vedere la Sezione 10.8 per ulteriori dettagli e la Sezione 8.9 per consigli sulla scelta di k per una data curva.

5.1. Considerazioni sull'efficienza nei campi di estensione​

La funzione hash_to_field descritta in questa sezione è inefficiente per alcuni campi di estensione. Più precisamente, quando si esegue l'hashing in un elemento del campo di estensione GF(p^m), hash_to_field richiede l'espansione di msg in m * L byte (per L come definito sopra). Per i campi di estensione in cui log2(p) è significativamente più piccolo del livello di sicurezza k, questo approccio è inefficiente: richiede che expand_message produca circa m * log2(p) + m * k bit, mentre m * log2(p) + k byte sono sufficienti per generare un elemento di GF(p^m) con un bias di al massimo 2^-k. In tali casi, le applicazioni POSSONO utilizzare una funzione hash_to_field alternativa, a condizione che soddisfi i seguenti requisiti di sicurezza:

  • La funzione DEVE produrre uno o più elementi del campo che siano uniformemente casuali, ad eccezione di un bias di al massimo 2^-k.

  • La funzione NON DEVE utilizzare il campionamento per rifiuto.

  • La funzione DOVREBBE prestarsi a implementazioni "straight-line".

Ad esempio, Pornin [P20] descrive un metodo di hashing in GF(9767^19) che soddisfa questi requisiti utilizzando meno bit di output di expand_message rispetto a quanto farebbe hash_to_field per questo campo.

5.2. Implementazione di hash_to_field​

La seguente procedura implementa hash_to_field.

Il parametro expand_message di questa funzione DEVE essere conforme ai requisiti forniti nella Sezione 5.3. La Sezione 3.1 tratta il metodo RICHIESTO per costruire DST, il tag di separazione di dominio. Si noti che hash_to_field può fallire (ABORT) se expand_message fallisce.

hash_to_field(msg, count)

Parametri:

  • DST, un tag di separazione di dominio (vedere la Sezione 3.1).
  • F, un campo finito di caratteristica p e ordine q = p^m.
  • p, la caratteristica di F (vedere immediatamente sopra).
  • m, il grado di estensione di F, m >= 1 (vedere immediatamente sopra).
  • L = ceil((ceil(log2(p)) + k) / 8), dove k è il parametro di sicurezza della suite (ad esempio, k = 128).
  • expand_message, una funzione che espande una stringa di byte e un tag di separazione di dominio in una stringa di byte uniformemente casuale (vedere la Sezione 5.3).

Input:

  • msg, una stringa di byte contenente il messaggio da sottoporre ad hashing.
  • count, il numero di elementi di F da produrre.

Output:

  • (u_0, ..., u_(count - 1)), un elenco di elementi del campo.

Passaggi:

  1. len_in_bytes = count * m * L
  2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
  3. per i che va da 0 a count - 1:
  4. per j che va da 0 a 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. ritorna (u_0, ..., u_(count - 1))

5.3. expand_message​

expand_message è una funzione che genera una stringa di byte uniformemente casuale. Accetta tre argomenti:

  1. msg, una stringa di byte contenente il messaggio da sottoporre ad hashing,

  2. DST, una stringa di byte che funge da tag di separazione di dominio, e

  3. len_in_bytes, il numero di byte da generare.

Questo documento definisce le seguenti due varianti di expand_message:

  • expand_message_xmd (Sezione 5.3.1) è adatta per l'uso con un'ampia gamma di funzioni di hash, tra cui SHA-2 [FIPS180-4], SHA-3 [FIPS202], BLAKE2 [RFC7693] e altre.

  • expand_message_xof (Sezione 5.3.2) è adatta per l'uso con funzioni a output estensibile (XOF), incluse le funzioni delle famiglie SHAKE [FIPS202] o BLAKE2X [BLAKE2X].

Queste varianti dovrebbero essere sufficienti per la stragrande maggioranza dei casi d'uso, ma sono possibili altre varianti; la Sezione 5.3.4 tratta i requisiti.

5.3.1. expand_message_xmd​

La funzione expand_message_xmd produce una stringa di byte uniformemente casuale utilizzando una funzione di hash crittografica H che produce b bit. Per sicurezza, H DEVE soddisfare i seguenti requisiti:

  • Il numero di bit prodotti da H DEVE essere b >= 2 * k, dove k è il livello di sicurezza di destinazione in bit, e b DEVE essere divisibile per 8. Il primo requisito garantisce la resistenza alle collisioni a k bit; il secondo garantisce l'uniformità dell'output di expand_message_xmd.

  • H PUÒ essere una funzione di hash Merkle-Damgaard come SHA-2. In questo caso, la sicurezza è assicurata quando la funzione di compressione sottostante è modellata come un random oracle [CDMP05]. (Vedere la Sezione 10.6 per ulteriori dettagli).

  • H PUÒ essere una funzione di hash basata su spugna come SHA-3 o BLAKE2. In questo caso, la sicurezza è assicurata quando la funzione interna è modellata come una trasformazione casuale o come una permutazione casuale [BDPV08].

  • In caso contrario, H DEVE essere una funzione di hash la cui indifferenziabilità da un random oracle [MRH04] è stata dimostrata sotto una ragionevole ipotesi crittografica.

SHA-2 [FIPS180-4] e SHA-3 [FIPS202] sono scelte tipiche e RACCOMANDATE. Ad esempio, per il livello di sicurezza a 128 bit, b >= 256 bit e SHA-256 o SHA3-256 sarebbe una scelta appropriata.

Si presume che la funzione di hash H funzioni ingerendo ripetutamente blocchi di dati di lunghezza fissa. La lunghezza in bit di questi blocchi è chiamata dimensione del blocco di input (s). Ad esempio, s = 1024 per SHA-512 [FIPS180-4] e s = 576 per SHA3-512 [FIPS202]. Per correttezza, H richiede b <= s.

La seguente procedura implementa expand_message_xmd.

expand_message_xmd(msg, DST, len_in_bytes)

Parametri:

  • H, una funzione di hash (vedere i requisiti sopra).
  • b_in_bytes, b / 8 dove b è la dimensione dell'output di H in bit. Ad esempio, per b = 256, b_in_bytes = 32.
  • s_in_bytes, la dimensione del blocco di input di H, misurata in byte (vedere la discussione sopra). Ad esempio, per SHA-256, s_in_bytes = 64.

Input:

  • msg, una stringa di byte.
  • DST, una stringa di byte di al massimo 255 byte. Vedere sotto per ulteriori informazioni sull'uso di DST più lunghi.
  • len_in_bytes, la lunghezza dell'output richiesto in byte, non superiore al minimo tra (255 * b_in_bytes) o 2^16-1.

Output:

  • uniform_bytes, una stringa di byte.

Passaggi:

  1. ell = ceil(len_in_bytes / b_in_bytes)
  2. ABORT se ell > 255 o len_in_bytes > 65535 o 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. per i che va da 2 a ell:
  10. b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
  11. uniform_bytes = b_1 || ... || b_ell
  12. ritorna substr(uniform_bytes, 0, len_in_bytes)

Si noti che la stringa Z_pad (passaggio 6) viene anteposta a msg prima di calcolare b_0 (passaggio 7). Ciò è necessario per la sicurezza quando H è un hash Merkle-Damgaard, ad esempio SHA-2 (vedere la Sezione 10.6). L'hashing di questi dati aggiuntivi significa che il costo di calcolo di b_0 è superiore al costo del semplice calcolo di H(msg). Nella maggior parte dei contesti, questo sovraccarico è trascurabile, poiché il costo di valutazione di H è molto inferiore ad altri costi coinvolti nell'hashing in una curva.

È possibile, tuttavia, evitare interamente questo sovraccarico sfruttando il fatto che Z_pad dipende solo da H e non dagli argomenti di expand_message_xmd. Per fare ciò, pre-calcolare prima e salvare lo stato interno di H dopo aver ingerito Z_pad. Quindi, durante il calcolo di b_0, inizializzare H utilizzando lo stato salvato. Altri dettagli dipendono dall'implementazione e vanno oltre lo scopo di questo documento.

5.3.2. expand_message_xof​

La funzione expand_message_xof produce una stringa di byte uniformemente casuale utilizzando una funzione a output estensibile (XOF) H. Per sicurezza, H DEVE soddisfare i seguenti criteri:

  • La resistenza alle collisioni di H DEVE essere di almeno k bit.

  • H DEVE essere una XOF la cui indifferenziabilità da un random oracle è stata dimostrata sotto una ragionevole ipotesi crittografica.

La famiglia XOF SHAKE [FIPS202] è una scelta tipica e RACCOMANDATA. Ad esempio, per una sicurezza a 128 bit, SHAKE128 sarebbe una scelta appropriata.

La seguente procedura implementa expand_message_xof.

expand_message_xof(msg, DST, len_in_bytes)

Parametri:

  • H(m, d), una funzione a output estensibile che elabora il messaggio di input m e restituisce d byte.

Input:

  • msg, una stringa di byte.
  • DST, una stringa di byte di al massimo 255 byte. Vedere sotto per ulteriori informazioni sull'uso di DST più lunghi.
  • len_in_bytes, la lunghezza dell'output richiesto in byte.

Output:

  • uniform_bytes, una stringa di byte.

Passaggi:

  1. ABORT se len_in_bytes > 65535 o 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. ritorna uniform_bytes

5.3.3. Uso di DST più lunghi di 255 byte​

Le varianti di expand_message definite in questa sezione accettano tag di separazione di dominio di al massimo 255 byte. Se le applicazioni richiedono un tag di separazione di dominio superiore a 255 byte, ad esempio a causa dei requisiti imposti da un protocollo chiamante, gli implementatori DEVONO calcolare un tag di separazione di dominio breve tramite hashing, come segue:

  • Per expand_message_xmd che utilizza la funzione di hash H, DST viene calcolato come:

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

  • Per expand_message_xof che utilizza la funzione a output estensibile H, DST viene calcolato come:

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

Qui, a_very_long_DST è il DST la cui lunghezza è superiore a 255 byte, "H2C-OVERSIZE-DST-" è una stringa letterale ASCII di 17 byte e k è il livello di sicurezza di destinazione in bit.

5.3.4. Definizione di altre varianti di expand_message​

Quando si definisce una nuova variante di expand_message, la considerazione più importante è che hash_to_field modelli expand_message come un random oracle. Pertanto, gli implementatori DOVREBBERO dimostrare l'indifferenziabilità da un random oracle sotto un'ipotesi appropriata sulle primitive crittografiche sottostanti; vedere la Sezione 10.5 per ulteriori informazioni.

Inoltre, le varianti di expand_message:

  • DEVONO fornire una resistenza alle collisioni proporzionata al livello di sicurezza della curva ellittica di destinazione.

  • DEVONO essere costruite su primitive progettate per essere utilizzate in applicazioni che richiedono casualità crittografica. Ad esempio, una cifratura a flusso sicura è una primitiva appropriata, mentre un generatore di numeri pseudocasuali Mersenne twister [MT98] non lo è.

  • NON DEVONO utilizzare il campionamento per rifiuto.

  • DEVONO fornire valori indipendenti per input (msg, DST, lunghezza) distinti. Soddisfare questo requisito è sottile. Ad esempio semplificato, l'hashing msg || DST non funziona, perché in questo caso coppie (msg, DST) distinte le cui concatenazioni sono uguali restituiranno lo stesso output (ad esempio, ("AB", "CDEF") e ("ABC", "DEF")). Le varianti definite in questo documento utilizzano una codifica di DST senza suffisso per evitare questo problema.

  • DEVONO utilizzare il tag di separazione di dominio DST per garantire che le invocazioni di primitive crittografiche all'interno di expand_message siano separate dal dominio dalle invocazioni all'esterno di expand_message. Ad esempio, se la variante di expand_message utilizza una funzione di hash H, una codifica di DST DEVE essere aggiunta come prefisso o come suffisso all'input di ogni invocazione di H. L'aggiunta di DST come suffisso è l'approccio RACCOMANDATO.

  • DOVREBBERO leggere msg esattamente una volta, per ragioni di efficienza quando msg è lungo.

Inoltre, ogni variante di expand_message DEVE specificare un EXP_TAG univoco che identifichi tale variante in un ID suite. Vedere la Sezione 8.10 per ulteriori informazioni.

Ultimo aggiornamento il