3. DSA ed ECDSA Deterministici
(EC)DSA deterministico è il processo di generazione di una firma (EC)DSA su un messaggio di input m utilizzando il processo standard di generazione della firma (EC)DSA (discusso nella sezione precedente), tranne per il fatto che il valore k, invece di essere generato casualmente, viene ottenuto attraverso il processo descritto in questa sezione.
Utilizziamo le notazioni descritte nella Sezione 2.
3.1. Blocchi di Costruzione
3.1.1. HMAC
HMAC [RFC2104] è una costruzione di un Codice di Autenticazione dei Messaggi (Message Authentication Code) utilizzando una funzione hash e una chiave segreta. Qui, utilizziamo HMAC con la stessa funzione hash H utilizzata per elaborare il messaggio di input prima della generazione o verifica della firma.
Denotiamo il processo di applicazione di HMAC con chiave K sui dati V come:
HMAC_K(V)
che restituisce una sequenza di bit di lunghezza hlen (la lunghezza di output della funzione hash sottostante H).
3.2. Generazione di k
Dato il messaggio di input m, viene applicato il seguente processo:
a. Elaborare m attraverso la funzione hash H, producendo:
h1 = H(m)
(h1 è una sequenza di hlen bit).
b. Impostare:
V = 0x01 0x01 0x01 ... 0x01
in modo tale che la lunghezza di V, in bit, sia uguale a 8*ceil(hlen/8). Ad esempio, su un sistema basato su ottetti, se H è SHA-256, allora V viene impostato a una sequenza di 32 ottetti di valore 1. Si noti che in questo passaggio e in tutti i passaggi successivi, utilizziamo la stessa funzione H utilizzata nel passaggio 'a' per elaborare il messaggio di input; questa scelta sarà discussa più in dettaglio nella Sezione 3.6.
c. Impostare:
K = 0x00 0x00 0x00 ... 0x00
in modo tale che la lunghezza di K, in bit, sia uguale a 8*ceil(hlen/8).
d. Impostare:
K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
dove || denota concatenazione. In altre parole, calcoliamo HMAC con chiave K, sulla concatenazione dei seguenti elementi, nell'ordine: il valore corrente di V, una sequenza di otto bit di valore 0, la codifica della chiave privata (EC)DSA x, e il messaggio hashato (possibilmente troncato ed esteso come specificato dalla trasformazione bits2octets). Il risultato HMAC è il nuovo valore di K. Si noti che la chiave privata x è nell'intervallo [1, q-1], quindi un input appropriato per int2octets, che produce rlen bit di output, cioè, un numero integrale di ottetti (rlen è un multiplo di 8).
e. Impostare:
V = HMAC_K(V)
f. Impostare:
K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
Si noti che l'"ottetto interno" è 0x01 questa volta.
g. Impostare:
V = HMAC_K(V)
h. Applicare il seguente algoritmo fino a quando non viene trovato un valore appropriato per k:
-
Impostare T alla sequenza vuota. La lunghezza di T (in bit) è denotata tlen; quindi, a quel punto, tlen = 0.
-
Mentre tlen < qlen, eseguire quanto segue:
V = HMAC_K(V)
T = T || V -
Calcolare:
k = bits2int(T)Se quel valore di k è nell'intervallo [1,q-1], ed è adatto per DSA o ECDSA (cioè, risulta in un valore r che non è 0; vedere Sezione 3.4), allora la generazione di k è terminata. Il valore ottenuto di k viene utilizzato in DSA o ECDSA. Altrimenti, calcolare:
K = HMAC_K(V || 0x00)
V = HMAC_K(V)e ripetere il ciclo (tentare di generare una nuova T, e così via).
Si prega di notare che quando k viene generato da T, il risultato di bits2int viene confrontato con q, non ridotto modulo q. Se il valore non è tra 1 e q-1, il processo si ripete. Eseguire una semplice riduzione modulare indurrebbe distorsioni che sarebbero dannose per la sicurezza della firma.
3.3. Descrizione Alternativa della Generazione di k
Il processo descritto nella sezione precedente è in realtà derivato dal generatore di numeri pseudocasuali "HMAC_DRBG", descritto in [SP800-90A] e nell'Appendice D di [X9.62]. Utilizzando la terminologia di [SP800-90A], la generazione di k può essere descritta come segue:
a. Istanziare HMAC_DRBG utilizzando HMAC, parametrizzato con la stessa funzione hash H utilizzata per elaborare il messaggio da firmare. I parametri di istanziazione sono:
requested_instantiation_security_strength Impostare questo parametro su qualsiasi valore che l'implementazione HMAC_DRBG accetterà quando H è utilizzata come funzione hash di base.
prediction_resistance_flag Impostare questo parametro su "false".
personalization_string Impostare questo parametro su "Null" (la sequenza di bit vuota).
entropy_input
Utilizzare int2octets(x) come stringa di entropia.
nonce
Utilizzare bits2octets(H(m)) come nonce.
Si noti che gli ultimi due parametri non sono di per sé parametri della funzione di istanziazione HMAC_DRBG; piuttosto, questi valori vengono richiesti dalla funzione interna Get_entropy_input durante l'istanziazione. Per (EC)DSA deterministico, vogliamo che HMAC_DRBG funzioni con la stringa di entropia e il nonce che specifichiamo, senza accedere a una fonte di entropia reale.
b. Generare un valore candidato per k richiedendo qlen bit da HMAC_DRBG e convertendo i bit risultanti in un intero utilizzando la trasformazione bits2int. Ripetere questo passaggio fino a ottenere un valore che è diverso da zero, minore di q e appropriato per (EC)DSA (vedere Sezione 3.4).
Si noti che istanziamo una nuova istanza HMAC_DRBG per ogni processo di generazione della firma. Non c'è "stringa di personalizzazione" né "input aggiuntivo" durante la generazione di bit. La funzione di reseeding di HMAC_DRBG non viene mai chiamata, né esternamente né come conseguenza dell'elaborazione interna di HMAC_DRBG.
Come mostrato sopra, utilizziamo la codifica della chiave privata come "stringa di entropia" e il messaggio hash (troncato ed esteso da bits2octets) come "nonce". In HMAC_DRBG, la stringa di entropia e il nonce sono semplicemente concatenati nel seed iniziale; quindi, la divisione tra "entropia" e "nonce" è piuttosto arbitraria. L'uso di qlen bit per ciascuno dovrebbe essere compatibile con la maggior parte dei requisiti di input delle implementazioni HMAC_DRBG.
3.4. Note di Utilizzo
Per DSA o ECDSA, il valore k viene utilizzato per calcolare la prima metà della firma, chiamata r (vedere Sezione 2.4). Gli standard DSA ed ECDSA richiedono che se r è zero, deve essere selezionato un nuovo k. In questa situazione, questo documento specifica che il valore k è "inappropriato" e il processo di generazione dovrebbe continuare a ciclare.
Questo evento è estremamente improbabile. In effetti, richiederebbe uno sforzo computazionale considerevole (simile a rompere la resistenza alla preimmagine della funzione hash) trovare una chiave privata e un messaggio che porterebbero a un valore zero per r. Incontrare un tale caso per puro caso è quindi considerato improbabile, e un attaccante non può forzarlo con messaggi accuratamente costruiti. In pratica, un tale percorso di codice non verrà attivato e può quindi essere implementato con un'ottimizzazione minima.
3.5. Motivazione
Il processo descritto nelle sezioni precedenti imita il processo di generazione di k "Approved" descritto nell'Appendice D di [X9.62] con il generatore di numeri pseudocasuali "HMAC_DRBG". La differenza principale è che utilizziamo la concatenazione della chiave privata x e del messaggio hash H(m) come seed per il generatore di numeri pseudocasuali (PRNG). Quando si utilizza un "livello di sicurezza" di n bit, HMAC_DRBG dovrebbe essere utilizzato con un'entropia del seed di almeno n+64 bit. Tuttavia, la chiave x dovrebbe anche essere stata generata con altrettanta entropia, e la lunghezza di x è qlen, che è almeno uguale a 2*n, quindi maggiore di n+64 (DSA ed ECDSA, come specificato dagli standard, richiedono qlen >= 160). Si può quindi sostenere che ECDSA deterministico soddisfa i requisiti di entropia dell'Appendice D di [X9.62].
Utilizziamo bits2octets(H(m)) invece di H(m) per facilitare l'integrazione. In effetti, molti sistemi di firma esistenti esternalizzano l'hashing dei messaggi; il motore di firma (che ha accesso alla chiave privata) riceve solo H(m). In alcune applicazioni dove la larghezza di banda dei dati è limitata, solo i primi qlen bit di H(m) vengono trasmessi al motore di firma, sulla base del fatto che la trasformazione bits2int ignorerebbe comunque i bit successivi. Eventualmente, in alcuni sistemi, l'H(m) troncato potrebbe essere ridotto modulo q esternamente, poiché questa è la prima cosa che (EC)DSA fa con il messaggio hash. Con la definizione di bits2octets, (EC)DSA deterministico può essere applicato con lo stesso input.
3.6. Varianti
Molte parti della specifica di (EC)DSA deterministico sono piuttosto arbitrarie, ma la scelta è stata fatta per ragioni di interoperabilità. Questa sezione discute alcune possibili varianti.
La funzione hash H utilizzata viene impiegata nel processo di generazione della firma per due scopi diversi: in primo luogo per elaborare il messaggio di input, e in secondo luogo come base per HMAC (che è esso stesso anche una funzione hash). In questo documento, specifichiamo l'uso della stessa funzione hash per entrambi gli scopi. Tuttavia, questo non è obbligatorio; è possibile utilizzare funzioni diverse per questi due ruoli. Lo svantaggio principale è che i vettori di test non possono coprire tutte le combinazioni; l'uso di una singola funzione hash semplifica i test di interoperabilità.
Le definizioni di int2octets e bits2octets portano a un output di rlen bit (cioè qlen arrotondato al multiplo successivo di 8), e producono effettivamente al massimo qlen bit di entropia quando utilizzate. Sarebbe possibile definire le stesse funzioni in modo che producano esattamente qlen bit; tuttavia, ciò renderebbe l'implementazione leggermente più complessa, poiché molti linguaggi di programmazione e framework tendono a lavorare con sequenze di ottetti piuttosto che sequenze di bit. D'altra parte, l'arrotondamento di qlen aggiunge al massimo 7 bit, il che è trascurabile nel contesto di un seed PRNG.
In questa specifica, stipuliamo un processo che cicla in casi speciali in cui k (ottenuto da T tramite bits2int) non è nell'intervallo appropriato, o porterebbe a generare un valore zero per r. Tuttavia, entrambi i casi non si verificano praticamente mai. L'ultimo caso (un r calcolato di zero) può verificarsi solo a causa di un bug software (ad esempio, i parametri della curva ellittica vengono corrotti durante l'esecuzione del programma). Le implementazioni possono quindi scegliere di trattare semplicemente tali casi come errori irrecuperabili e semplicemente interrompere il calcolo della firma, piuttosto che ciclare.