5. Hashing su un campo finito

La funzione hash_to_field esegue l'hash di una stringa di byte msg di lunghezza arbitraria in uno o più elementi di un campo F. Questa funzione opera in due passi: in primo luogo esegue l'hash della stringa di input per produrre una stringa di byte uniformemente casuale, quindi interpreta questa stringa di byte come uno o più elementi di F.

Per il primo passo, hash_to_field chiama una funzione ausiliaria expand_message. Questo documento definisce due varianti di expand_message: una adatta per funzioni di hash come SHA-2 [FIPS180-4] o SHA-3 [FIPS202], e un'altra adatta per funzioni a output estendibile (XOF) come SHAKE128 [FIPS202]. Le considerazioni di 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 uniformemente casuale di F, per garantire che la funzione hash_to_field sia idonea a un'implementazione in tempo costante. Il motivo è che le procedure di campionamento per rifiuto sono difficili da implementare in tempo costante, e successive "ottimizzazioni" benintenzionate potrebbero silenziosamente rendere un'implementazione non in tempo costante. Ciò significa che qualsiasi funzione hash_to_field basata sul campionamento per rifiuto sarebbe incompatibile con l'implementazione in tempo costante.

La funzione hash_to_field è inoltre adatta per eseguire in modo sicuro l'hash verso scalari. Ad esempio, quando si esegue l'hash verso il campo scalare per un (sotto)gruppo di curva ellittica di ordine primo r, è sufficiente istanziare hash_to_field con 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) è modellata come un random oracle (si veda la Sezione 10.5 per i dettagli sulla sua indifferenziabilità). Garantire l'indifferenziabilità richiede attenzione; per capirne il motivo, si consideri un primo p vicino a 3/4 * 2^256. Ridurre un intero casuale a 256 bit modulo questo p produce un valore nell'intervallo [0, p / 3] con probabilità pari a circa 1/2, il che significa che questo valore è statisticamente lontano dall'uniforme in [0, p - 1].

Per controllare il bias, hash_to_field utilizza invece interi casuali la cui lunghezza è almeno ceil(log2(p)) + k bit, dove k è il livello di sicurezza target della suite in bit. Ridurre tali interi modulo p dà un bias al massimo di 2^-k per qualsiasi p; questo bias è appropriato quando si mira a una sicurezza a k bit. Per ciascun intero, hash_to_field utilizza expand_message per ottenere L byte uniformi, dove

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

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

Si noti che k è un limite superiore al livello di sicurezza per la curva corrispondente. Si veda la Sezione 10.8 per maggiori dettagli e la Sezione 8.9 per le linee guida sulla scelta di k per una data curva.

5.1. Considerazioni di efficienza nei campi di estensione

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

• La funzione DEVE emettere uno o più elementi di campo che siano uniformemente casuali eccetto per un bias al massimo di 2^-k.

• La funzione NON DEVE utilizzare il campionamento per rifiuto.

• La funzione DOVREBBE essere idonea a implementazioni straight-line.

Ad esempio, Pornin [P20] descrive un metodo per l'hash verso GF(9767^19) che soddisfa questi requisiti utilizzando meno bit di output da expand_message rispetto a quanto farebbe hash_to_field per quel campo.

5.2. Implementazione di hash_to_field

La seguente procedura implementa hash_to_field.

Il parametro expand_message di questa funzione DEVE conformarsi ai requisiti dati nella Sezione 5.3. La Sezione 3.1 discute il metodo RICHIESTO per costruire DST, il tag di separazione dei domini. Si noti che hash_to_field può fallire (ABORT) se expand_message fallisce.

hash_to_field(msg, count)

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

Input:
- msg, una stringa di byte contenente il messaggio da sottoporre a hash.
- count, il numero di elementi di F da emettere.

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

Passi:
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 è una funzione che genera una stringa di byte uniformemente casuale. Prende tre argomenti:

1. msg, una stringa di byte contenente il messaggio da sottoporre a hash,

2. DST, una stringa di byte che funge da tag di separazione dei domini, 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 all'uso con un'ampia gamma di funzioni di hash, incluse SHA-2 [FIPS180-4], SHA-3 [FIPS202], BLAKE2 [RFC7693] e altre.

• expand_message_xof (Sezione 5.3.2) è adatta all'uso con funzioni a output estendibile (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 discute 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 emette b bit. Per la sicurezza, H DEVE soddisfare i seguenti requisiti:

• Il numero di bit emessi da H DEVE essere b >= 2 * k, dove k è il livello di sicurezza target 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 di Merkle-Damgård come SHA-2. In questo caso, la sicurezza vale quando la funzione di compressione sottostante è modellata come un random oracle [CDMP05]. (Si veda la Sezione 10.6 per la discussione.)

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

• Altrimenti, H DEVE essere una funzione di hash che è stata dimostrata indifferenziabile da un random oracle [MRH04] 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 sia SHA-256 sia SHA3-256 sarebbero scelte appropriate.

Si assume che la funzione di hash H operi 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 la 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 (vedi requisiti sopra).
- b_in_bytes, b / 8 per b la dimensione di 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
  (vedi 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.
  Vedi sotto per informazioni sull'uso di DST più lunghi.
- len_in_bytes, la lunghezza dell'output richiesto in byte,
  non superiore al minore tra (255 * b_in_bytes) o 2^16-1.

Output:
- uniform_bytes, una stringa di byte.

Passi:
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.  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)

Si noti che la stringa Z_pad (passo 6) è prefissata a msg prima di calcolare b_0 (passo 7). Ciò è necessario per la sicurezza quando H è una hash di Merkle-Damgård, ad esempio SHA-2 (si veda la Sezione 10.6). Eseguire l'hash di questi dati aggiuntivi significa che il costo di calcolo di b_0 è maggiore del costo di calcolare semplicemente H(msg). Nella maggior parte dei casi, questo overhead è trascurabile, poiché il costo di valutazione di H è molto inferiore agli altri costi coinvolti nell'hash verso una curva.

È tuttavia possibile evitare del tutto questo overhead approfittando del fatto che Z_pad dipende solo da H, e non dagli argomenti di expand_message_xmd. A tale scopo, si precalcola e si salva prima lo stato interno di H dopo aver ingerito Z_pad. Quindi, quando si calcola b_0, si inizializza H utilizzando lo stato salvato. Ulteriori 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 estendibile (XOF) H. Per la sicurezza, H DEVE soddisfare i seguenti criteri:

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

• H DEVE essere un XOF che è stato dimostrato indifferenziabile da un random oracle sotto una ragionevole ipotesi crittografica.

La famiglia di XOF SHAKE [FIPS202] è una scelta tipica e RACCOMANDATA. Ad esempio, per la 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 estendibile che elabora
  il messaggio m e restituisce d byte.

Input:
- msg, una stringa di byte.
- DST, una stringa di byte di al massimo 255 byte.
  Vedi sotto per informazioni sull'uso di DST più lunghi.
- len_in_bytes, la lunghezza dell'output richiesto in byte.

Output:
- uniform_bytes, una stringa di byte.

Passi:
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. return 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 dei domini di al massimo 255 byte. Se le applicazioni richiedono un tag di separazione dei domini più lungo di 255 byte, ad esempio a causa di requisiti imposti da un protocollo chiamante, gli implementatori DEVONO calcolare un tag di separazione dei domini breve tramite hash, nel modo seguente:

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

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

• Per expand_message_xof che utilizza la funzione a output estendibile H, DST è 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-" è un letterale stringa ASCII di 17 byte, e k è il livello di sicurezza target 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 modella 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; si veda la Sezione 10.5 per maggiori informazioni.

Inoltre, le varianti di expand_message:

• DEVONO fornire resistenza alle collisioni commisurata al livello di sicurezza della curva ellittica target.

• DEVONO essere costruite su primitive progettate per l'uso in applicazioni che richiedono casualità crittografica. Ad esempio, un cifrario a flusso sicuro è una primitiva appropriata, mentre un generatore di numeri pseudo-casuali Mersenne twister [MT98] non lo è.

• NON DEVONO utilizzare il campionamento per rifiuto.

• DEVONO fornire valori indipendenti per input distinti (msg, DST, lunghezza). Soddisfare questo requisito è sottile. Come esempio semplificato, eseguire l'hash di msg || DST non funziona, perché in questo caso coppie distinte (msg, DST) la cui concatenazione è uguale restituiranno lo stesso output (es. ("AB", "CDEF") e ("ABC", "DEF")). Le varianti definite in questo documento utilizzano una codifica di DST priva di suffissi per evitare questo problema.

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

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

Inoltre, ciascuna variante di expand_message DEVE specificare un EXP_TAG unico che identifica quella variante in un Suite ID. Si veda la Sezione 8.10 per maggiori informazioni.