Passa al contenuto principale

RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) (Uso Deterministico dell'Algoritmo di Firma Digitale (DSA) e dell'Algoritmo di Firma Digitale a Curva Ellittica (ECDSA))

  • Stato: Informational
  • Pubblicato: August 2013
  • Stream: INDEPENDENT
  • Errata: Nessun errata

Questo documento definisce una procedura deterministica per la generazione di firme digitali. Tali firme sono compatibili con l'Algoritmo di Firma Digitale (Digital Signature Algorithm, DSA) standard e l'Algoritmo di Firma Digitale a Curva Ellittica (Elliptic Curve Digital Signature Algorithm, ECDSA) e possono essere elaborate con verificatori non modificati, che non necessitano di essere a conoscenza della procedura qui descritta. Le firme deterministiche mantengono le caratteristiche di sicurezza crittografica associate alle firme digitali ma possono essere implementate più facilmente in vari ambienti, poiché non necessitano di accesso a una fonte di casualità di alta qualità.

Status of This Memo (Stato di questo Memorandum)​

Questo documento non è una specifica dello standard Internet Track; è pubblicato a scopo informativo.

Questo è un contributo alla serie RFC, indipendentemente da qualsiasi altro flusso RFC. L'RFC Editor ha scelto di pubblicare questo documento a propria discrezione e non rilascia alcuna dichiarazione sul suo valore per l'implementazione o il deployment. I documenti approvati per la pubblicazione dall'RFC Editor non sono candidati per alcun livello di standard Internet; vedere la Sezione 2 di RFC 5741.

Le informazioni sullo stato attuale di questo documento, eventuali errata e su come fornire feedback possono essere ottenute all'indirizzo http://www.rfc-editor.org/info/rfc6979.

Copyright (c) 2013 IETF Trust e le persone identificate come autori del documento. Tutti i diritti riservati.

Questo documento è soggetto a BCP 78 e alle Disposizioni Legali dell'IETF Trust relative ai Documenti IETF (http://trustee.ietf.org/license-info) in vigore alla data di pubblicazione di questo documento. Si prega di esaminare attentamente questi documenti, poiché descrivono i vostri diritti e le restrizioni relative a questo documento.

Contents​

1. Introduction (Introduzione)​

DSA [FIPS-186-4] ed ECDSA [X9.62] sono due schemi di firma digitale standard. Forniscono integrità dei dati e autenticità verificabile in vari protocolli.

Una caratteristica di DSA ed ECDSA è che devono produrre, per ogni generazione di firma, un valore casuale fresco (di seguito designato come k). Per una sicurezza efficace, k DEVE essere scelto casualmente e uniformemente da un insieme di interi modulari, utilizzando un processo crittograficamente sicuro. Anche lievi distorsioni in quel processo possono essere trasformate in attacchi agli schemi di firma.

La necessità di una fonte di casualità crittograficamente sicura si dimostra essere un ostacolo al deployment degli schemi di firma DSA ed ECDSA in alcune architetture in cui la generazione di numeri casuali sicuri è impegnativa, in particolare, sistemi embedded come le smartcard. In quei sistemi, l'algoritmo di firma RSA, utilizzato come specificato in Public-Key Cryptography Standards (PKCS) #1 [RFC3447] (con padding "type 1", non il Probabilistic Signature Scheme (PSS)) e ISO 9796-2 [ISO-9796-2], è spesso preferito, anche se è computazionalmente più costoso, perché RSA (con tali schemi di padding) è deterministico e quindi non richiede una fonte di casualità.

La natura randomizzata di DSA ed ECDSA rende anche le implementazioni più difficili da testare. I test automatici non possono rilevare in modo affidabile se l'implementazione utilizza una fonte di casualità di qualità sufficientemente alta. Questo rende il processo di implementazione più vulnerabile a fallimenti catastrofici, spesso scoperti dopo che il sistema è stato deployato e attaccato con successo.

È possibile trasformare DSA ed ECDSA in schemi deterministici utilizzando un processo deterministico per generare il valore "casuale" k. Quel processo DEVE soddisfare alcune caratteristiche crittografiche al fine di mantenere le proprietà di verificabilità e non falsificabilità attese dagli schemi di firma; vale a dire, per chiunque non conosca la chiave privata di firma, la mappatura dai messaggi di input ai valori k corrispondenti DEVE essere computazionalmente indistinguibile da ciò che una funzione scelta casualmente e uniformemente (dall'insieme dei messaggi all'insieme dei possibili valori k) restituirebbe.

Questo documento descrive tale procedura. Ha le seguenti caratteristiche:

  • Le firme prodotte rimangono completamente compatibili con DSA ed ECDSA standard. Le entità che verificano le firme non necessitano di essere modificate o addirittura di essere a conoscenza del processo utilizzato per generare k.

  • La generazione della coppia di chiavi non è alterata. Le chiavi private esistenti possono essere utilizzate con DSA ed ECDSA deterministici.

  • L'utilizzo di DSA ed ECDSA deterministici non implica alcun requisito di memorizzazione aggiuntivo di alcun valore segreto o pubblico.

  • DSA ed ECDSA deterministici possono essere applicati sugli stessi input di DSA ed ECDSA standard, vale a dire un valore hash calcolato sul messaggio che deve essere firmato, con una funzione hash crittograficamente sicura.

Alcune scelte relativamente arbitrarie sono state prese nella definizione di (EC)DSA deterministico come specificato in questo documento; questo è stato fatto al fine di renderlo il più universalmente applicabile possibile, in modo da massimizzare l'utilità dei vettori di test inclusi. Vedere la Sezione 3.6 per una discussione di alcune possibili varianti.

Va notato che la generazione della coppia di chiavi richiede ancora una fonte di casualità. Nei sistemi embedded dove la qualità della casualità è un problema, può spesso essere organizzato che la generazione della coppia di chiavi avvenga in condizioni più controllate (ad esempio, durante una procedura speciale di inizializzazione della smartcard o sotto il controllo fisico di agenti giurati) o la chiave potrebbe anche essere generata altrove e importata nel dispositivo. DSA ed ECDSA deterministici si occupano solo della necessità di casualità al momento della generazione della firma.

2. DSA and ECDSA Notations (Notazioni DSA ed ECDSA)​

In questa sezione, descriviamo succintamente DSA ed ECDSA e definiamo le nostre notazioni. Le specifiche complete per DSA ed ECDSA possono essere trovate in [FIPS-186-4] e [X9.62], rispettivamente.

2.1. Key Parameters (Parametri della Chiave)​

DSA ed ECDSA operano su un grande gruppo di dimensione prima, in cui l'operazione di gruppo è facile da calcolare, ma il logaritmo discreto è computazionalmente impraticabile con la tecnologia esistente e prevedibile. La definizione del gruppo è chiamata "parametri della chiave". I parametri della chiave possono essere condivisi tra diverse coppie di chiavi senza alcun effetto negativo sulla sicurezza; questo è il caso abituale con ECDSA in particolare.

DSA utilizza i seguenti parametri della chiave:

p: un grande numero primo (almeno 1024 bit)

q: un numero primo sufficientemente grande (almeno 160 bit) che è anche un divisore di p-1

g: un generatore per il sottogruppo moltiplicativo di ordine q degli interi modulo p

Il gruppo su cui sarà calcolato DSA consiste dei valori g^j mod p, dove ^ denota l'esponenziazione e j varia da 0 a q-1 (inclusi). La dimensione del gruppo è q.

ECDSA utilizza i seguenti parametri della chiave:

E: una curva ellittica, definita su un dato campo finito

q: un numero primo sufficientemente grande (almeno 160 bit) che è un divisore dell'ordine della curva

G: un punto di E, di ordine q

Il gruppo su cui sarà calcolato ECDSA consiste dei punti della curva jG (moltiplicazione del punto G per l'intero j) dove j varia da 0 a q-1. G è tale che qG = 0 (il "punto all'infinito" sulla curva E). La dimensione del gruppo è q. Si noti che queste notazioni differiscono leggermente da quelle descritte in [X9.62]; le usiamo al fine di corrispondere a quelle utilizzate per DSA.

2.2. Key Pairs (Coppie di Chiavi)​

Una chiave privata DSA o ECDSA è un intero x preso modulo q. Gli standard pertinenti prescrivono che x NON DOVRÀ essere 0; quindi, x è un intero nell'intervallo [1, q-1].

Una chiave pubblica DSA o ECDSA è calcolata dalla chiave privata x e dai parametri della chiave:

  • Per DSA, la chiave pubblica è l'intero: y = g^x mod p

  • Per ECDSA, la chiave pubblica è il punto della curva: U = xG

2.3. Integer Conversions (Conversioni di Interi)​

Sia qlen la lunghezza binaria di q. qlen è il più piccolo intero tale che q è minore di 2^qlen. Questa è la dimensione della rappresentazione binaria di q senza un bit di segno (si noti che q, essendo un grande numero primo, è dispari, evitando così qualsiasi ambiguità sulla lunghezza di qualsiasi intero uguale a una potenza di 2). Definiamo cinque funzioni di conversione, che operano su stringhe di bit, ottetti e interi modulo q. qlen è il parametro principale per queste conversioni.

Nelle seguenti sottosezioni, utilizziamo altre due lunghezze, chiamate blen e rlen. rlen è uguale a qlen, arrotondato per eccesso al successivo multiplo di 8 (se qlen è già un multiplo di 8, allora rlen è uguale a qlen; altrimenti, rlen è leggermente più grande, fino a qlen+7). Si noti che rlen non è correlato al valore r, la prima metà di una firma generata. blen è la lunghezza (in bit) di una sequenza di input di bit e può variare tra le chiamate. blen può essere inferiore, uguale o maggiore di qlen.

2.3.1. Bits and Octets (Bit e Ottetti)​

Formalmente, tutte le operazioni sono definite su sequenze di bit. Una sequenza è ordinata; il primo bit si dice essere il più a sinistra, mentre l'ultimo bit è il più a destra.

Sulla maggior parte dei sistemi software, i bit sono raggruppati in ottetti (sequenze di otto bit). I dati binari, ad esempio, l'output di una funzione hash, sono disponibili come sequenza di ottetti. Quando applicabile, consideriamo che i bit all'interno di un ottetto siano ordinati dal più significativo al meno significativo: il primo bit (più a sinistra) all'interno di un ottetto ha valore numerico 128, mentre l'ultimo (più a destra) ha valore numerico 1.

2.3.2. Bit String to Integer (Stringa di Bit a Intero)​

La trasformazione bits2int prende come input una sequenza di blen bit e restituisce un intero non negativo che è minore di 2^qlen. Consiste dei seguenti passaggi:

  1. La sequenza viene prima troncata o espansa alla lunghezza qlen:

    • se qlen < blen, allora vengono mantenuti i qlen bit più a sinistra, e i bit successivi vengono scartati;

    • altrimenti, vengono aggiunti blen-qlen bit (di valore zero) alla sinistra della sequenza (cioè, prima dei bit di input nell'ordine della sequenza).

  2. La sequenza risultante viene quindi convertita in un valore intero utilizzando la convenzione big-endian: se i bit di input sono chiamati b_0 (più a sinistra) a b_(qlen-1) (più a destra), allora il valore risultante è:

    b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0

La trasformazione bits2int può anche essere descritta nel modo seguente: la sequenza di bit di input (di lunghezza blen) viene trasformata in un intero utilizzando la convenzione big-endian. Quindi, se blen è maggiore di qlen, l'intero risultante viene diviso per due elevato alla potenza blen-qlen (divisione euclidea: il resto viene scartato); in molte implementazioni software di aritmetica su grandi interi, quella divisione è equivalente a uno "shift a destra" di blen-qlen bit.

2.3.4. Bit String to Octet String (Stringa di Bit a Stringa di Ottetti)​

La trasformazione bits2octets prende come input una sequenza di blen bit e restituisce una sequenza di rlen bit. Consiste dei seguenti passaggi:

  1. La sequenza di input b viene convertita in un valore intero z1 attraverso la trasformazione bits2int:

    z1 = bits2int(b)

  2. z1 viene ridotto modulo q, producendo z2 (un intero tra 0 e q-1, inclusi):

    z2 = z1 mod q

    Si noti che poiché z1 è minore di 2^qlen, quella riduzione modulare può essere implementata con una semplice sottrazione condizionale: z2 = z1-q se quel valore è non negativo; altrimenti, z2 = z1.

  3. z2 viene trasformato in una sequenza di ottetti (una sequenza di rlen bit) applicando int2octets.

2.3.5. Usage (Utilizzo)​

Vale la pena notare che int2octets non è l'inverso di bits2int, nemmeno per sequenze di input di lunghezza qlen: int2octets aggiungerà alcuni bit a sinistra, mentre bits2int scarterà alcuni bit a destra. int2octets è l'inverso di bits2int solo quando qlen è un multiplo di 8 e le sequenze di bit hanno già lunghezza qlen.

bits2int viene utilizzato durante la generazione e la verifica della firma in DSA ed ECDSA standard per trasformare un valore hash (calcolato sul messaggio di input) in un intero modulo q. Cioè, l'intero ottenuto attraverso bits2int viene ulteriormente ridotto modulo q; poiché quell'intero è minore di 2^qlen, quella riduzione può essere eseguita con al massimo una sottrazione.

int2octets è definito con il nome "Integer-to-OctetString" nella Sezione 2.3.7 di SEC 1 [SEC1]. Viene utilizzato nella specifica della codifica di una chiave privata ECDSA (x) all'interno di una struttura basata su ASN.1.

bits2octets non viene utilizzato in DSA o ECDSA standard. Lo useremo nella specifica di (EC)DSA deterministico.

2.4. Signature Generation (Generazione della Firma)​

La generazione della firma utilizza una funzione hash crittografica H e un messaggio di input m. Il messaggio viene prima elaborato da H, producendo il valore H(m), che è una sequenza di bit di lunghezza hlen. Normalmente, H viene scelta in modo tale che la sua lunghezza di output hlen sia approssimativamente uguale a qlen, poiché la sicurezza complessiva dello schema di firma dipenderà dal più piccolo tra hlen e qlen; tuttavia, gli standard pertinenti supportano tutte le combinazioni di hlen e qlen.

Vengono quindi applicati i seguenti passaggi:

  1. H(m) viene trasformato in un intero modulo q utilizzando la trasformazione bits2int e una riduzione modulare aggiuntiva:

    h = bits2int(H(m)) mod q

    Come è stato notato nella descrizione di bits2octets, la riduzione modulare aggiuntiva non è più di una sottrazione condizionale.

  2. Viene generato un valore casuale modulo q, denominato k. Quel valore NON DOVRÀ essere 0; quindi, si trova nell'intervallo [1, q-1]. La maggior parte del resto di questo documento ruoterà intorno al processo utilizzato per generare k. In DSA o ECDSA standard, k DOVREBBE essere selezionato attraverso una selezione casuale che sceglie un valore tra i q-1 valori possibili con probabilità uniforme.

  3. Un valore r (modulo q) viene calcolato da k e dai parametri della chiave:

    • Per DSA:

      r = g^k mod p mod q

      (L'esponenziazione viene eseguita modulo p, producendo un numero tra 0 e p-1, che viene quindi ulteriormente ridotto modulo q.)

    • Per ECDSA: viene calcolato il punto kG; la sua coordinata X (un membro del campo su cui E è definito) viene convertita in un intero, che viene ridotto modulo q, producendo r.

    Se r risulta essere zero, DOVREBBE essere selezionato un nuovo k e r calcolato nuovamente (questo è un evento assolutamente improbabile).

  4. Il valore s (modulo q) viene calcolato:

    s = (h+x*r)/k mod q

    La coppia (r, s) è la firma. Come una firma debba essere codificata non è coperto dagli standard DSA ed ECDSA stessi; un modo comune è utilizzare una struttura ASN.1 codificata in DER (una SEQUENCE di due INTEGER, per r e s, in quell'ordine).

3. Deterministic DSA and ECDSA (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.2. Generation of k (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:

  1. Impostare T alla sequenza vuota. La lunghezza di T (in bit) è denotata tlen; quindi, a quel punto, tlen = 0.

  2. Mentre tlen < qlen, eseguire quanto segue:

    V = HMAC_K(V)
    T = T || V

  3. 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. Alternate Description of the Generation of k (Descrizione Alternativa della Generazione di k)​

This compatibility page redirects readers to 3.3. Alternate Description of the Generation of k (Descrizione Alternativa della Generazione di k).

3.4. Usage Notes (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. Rationale (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. Variants (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.

4. Security Considerations (Considerazioni sulla Sicurezza)​

La corretta implementazione e utilizzo di un algoritmo di firma crittografica richiedono di tenere in considerazione molti parametri. In particolare, la generazione, la memorizzazione, il controllo degli accessi e lo smaltimento della chiave privata sono operazioni sensibili, che questo documento non affronta in alcun modo. (EC)DSA deterministico mostra come ottenere le caratteristiche di sicurezza di uno schema di firma DSA o ECDSA standard rimuovendo la necessità di una fonte di casualità forte, o addirittura di qualsiasi fonte di casualità, durante la generazione della firma.

La generazione della chiave privata, tuttavia, richiede assolutamente una tale fonte fortemente casuale. In situazioni in cui (EC)DSA deterministico deve essere utilizzato a causa della mancanza di una fonte appropriata di casualità, si DEVE assumere che la chiave privata sia stata generata esternamente e importata nel sistema di generazione della firma o sia stata generata in un contesto in cui la casualità era disponibile. Ad esempio, si può immaginare una smartcard che genera la sua chiave privata mentre è ancora in fabbrica in condizioni ambientali controllate, ma per la quale la generazione di dati casuali non può essere garantita una volta deployata sul campo, quando è fisicamente nelle mani di potenziali attaccanti.

Sia la rimozione del requisito di fonte casuale che la capacità di testare un'implementazione rispetto ai vettori di test migliorano la sicurezza delle implementazioni di firmatari DSA ed ECDSA, in quanto aiutano a evitare condizioni di fallimento difficili da testare. Gli schemi di firma deterministici possono anche aiutare in altre situazioni, ad esempio, per evitare duplicati spurii, quando lo stesso elemento di dati viene firmato più volte con la stessa chiave: con uno schema di firma deterministico, viene generata la stessa firma ogni volta, rendendo molto più facile il rilevamento dei duplicati.

Al contrario, la mancanza di randomizzazione può avere effetti negativi in alcuni protocolli avanzati, ad esempio, relativi all'anonimato in alcuni schemi di voto. Come regola generale, DSA o ECDSA deterministico può essere utilizzato al posto del genuino DSA o ECDSA, senza problemi di sicurezza aggiuntivi, se il protocollo complessivo tollererebbe un altro schema di firma deterministico, in particolare RSA come specificato in PKCS #1 [RFC3447] (con padding "type 1", non PSS) o ISO 9796-2 [ISO-9796-2]. L'elenco dei protocolli in cui DSA o ECDSA deterministico è appropriato include Transport Layer Security (TLS) [RFC5246], il Secure SHell (SSH) Protocol [RFC4251], Cryptographic Message Syntax (CMS) [RFC5652] e derivati, infrastrutture a chiave pubblica X.509 [RFC5280], e molti altri.

La costruzione descritta in questo documento è nota come "derandomizzazione". Questo è stato proposto per vari schemi di firma. La sicurezza si basa sul fatto che la generazione di k sia indistinguibile dall'output di un oracolo casuale. In termini approssimativi, HMAC_DRBG è sicuro in quel ruolo finché HMAC si comporta come una PRF (Funzione Pseudocasuale). Per dettagli sulla sicurezza di HMAC e HMAC_DRBG, si prega di fare riferimento a [H2008] e [B2006]. Per un trattamento più formale della derandomizzazione, vedere [LN2009].

Un problema residuo con (EC)DSA deterministico, come presentato in questo documento, è il "doppio uso" della chiave privata x, sia come chiave privata nell'algoritmo di generazione della firma stesso sia come input per l'oracolo pseudocasuale basato su HMAC_DRBG per produrre il valore k. Questo richiede che HMAC_DRBG continui a essere un oracolo casuale, anche quando la chiave pubblica (che è calcolata da x) è anch'essa nota. Data la mancanza di struttura comune tra HMAC e logaritmi discreti, questa sembra un'assunzione ragionevole.

Gli attacchi side-channel sono una considerazione importante ogni volta che un attaccante può misurare accuratamente aspetti di un'implementazione come la quantità di tempo necessaria per eseguire un'operazione di firma o l'energia consumata in ogni punto di un'operazione di firma. Il determinismo degli algoritmi descritti in questa nota può essere utile a un attaccante in alcune forme di attacchi side-channel, quindi le implementazioni DOVREBBERO utilizzare misure difensive per evitare di far trapelare la chiave privata attraverso un canale laterale.

5. Intellectual Property Status (Stato della Proprietà Intellettuale)​

A nostra conoscenza, (EC)DSA deterministico non è coperto da alcun brevetto attivo. L'articolo [BDLSY2011] indica due pubblicazioni indipendenti dell'idea di derandomizzazione da parte di Barwood e Wigley, entrambe all'inizio del 1997, e anche una domanda di brevetto da parte di Naccache, M'Raihi e Levy-dit-Vehel pochi mesi dopo [NML1997], ma la domanda è stata ritirata nel 2003. Non siamo a conoscenza di altri brevetti sull'argomento.

Appendix A. Examples (Esempi)​

A.1.2. Generation of k (Generazione di k)​

In questo esempio, utilizziamo la funzione hash SHA-256 [FIPS-180-4]. Il messaggio di input è la codifica UTF-8 della stringa "sample" (6 ottetti, cioè, 48 bit).

Il messaggio di input hashato h1 = SHA-256(m) è:

h1
   AF 2B DB E1 AA 9B 6E C1 E2 AD E1 D6 94 F4 1F C7
   1A 83 1D 02 68 E9 89 15 62 11 3D 8A 62 AD D1 BF

(32 ottetti; ogni valore di ottetto è elencato in notazione esadecimale).

Convertiamo la chiave privata x in una sequenza di ottetti utilizzando la trasformazione int2octets:

int2octets(x)
   00 9A 4D 67 92 29 5A 7F 73 0F C3 F2 B4 9C BC 0F
   62 E8 62 27 2F

Nota: Sebbene il valore specifico di x si adatterebbe numericamente in 160 bit, cioè, 20 ottetti, codifichiamo ancora x in 21 ottetti, perché la lunghezza di codifica è guidata dalla lunghezza di q, che è 163 bit.

Tronchiamo e/o espandiamo anche il messaggio hashato utilizzando bits2octets:

bits2octets(h1)
   01 79 5E DF 0D 54 DB 76 0F 15 6D 0D AC 04 C0 32
   2B 3A 20 42 24

I passaggi da b a g (vedere Sezione 3.2) calcolano quindi i valori per le variabili K e V. Queste variabili sono sequenze di 256 bit (la lunghezza di output della funzione hash, arrotondata per eccesso a un multiplo di 8). Riproduciamo qui i valori successivi:

V dopo il passaggio b:
   01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
   01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01

K dopo il passaggio c:
   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

K dopo il passaggio d:
   09 99 9A 9B FE F9 72 D3 34 69 11 88 3F AD 79 51
   D2 3F 2C 8B 47 F4 20 22 2D 11 71 EE EE AC 5A B8

V dopo il passaggio e:
   D5 F4 03 0F 75 5E E8 6A A1 0B BA 8C 09 DF 11 4F
   F6 B6 11 1C 23 85 00 D1 3C 73 43 A8 C0 1B EC F7

K dopo il passaggio f:
   0C F2 FE 96 D5 61 9C 9E F5 3C B7 41 7D 49 D3 7E
   A6 8A 4F FE D0 D7 E6 23 E3 86 89 28 99 11 BD 57

V dopo il passaggio g:
   78 34 57 C1 CF 31 48 A8 F2 A9 AE 73 ED 47 2F A9
   8E D9 CD 92 5D 8E 96 4C E0 76 4D EF 3F 84 2B 9A

Nel passaggio h, eseguiamo il ciclo finale. Poiché utilizziamo HMAC con SHA-256, che produce 256 bit di output, e abbiamo bisogno solo di 163 bit per T, una singola invocazione HMAC produce il seguente T:

T (primo tentativo)
   93 05 A4 6D E7 FF 8E B1 07 19 4D EB D3 FD 48 AA
   20 D5 E7 65 6C BE 0E A6 9D 2A 8D 4E 7C 67 31 4A

che, quando convertito in un intero con bits2int, produce un primo candidato per k:

k1 = 0x4982D236F3FFC758838CA6F5E9FEA455106AF3B2B

Poiché quel valore è maggiore di q-1, dobbiamo ripetere il ciclo. Questo comporta prima il calcolo di nuovi valori per K e V:

nuovo K
   75 CB 5C 05 B2 A7 8C 3D 81 DF 12 D7 4D 7B E0 A0
   E9 4A B1 98 15 78 1D 4D 8E 29 02 A7 9D 0A 66 99

nuovo V
   DC B9 CA 12 61 07 A9 C2 7C E7 7B A5 8E A8 71 C8
   C9 12 D8 35 EA DD C3 05 F2 44 5D 88 F6 6C 4C 43

poi un nuovo T:

T (secondo tentativo)
   C7 0C 78 60 8A 3B 5B E9 28 9B E9 0E F6 E8 1A 9E
   2C 15 16 D5 75 1D 2F 75 F5 00 33 E4 5F 73 BD EB

e un nuovo candidato per k:

k2 = 0x63863C30451DADF4944DF4877B740D4F160A8B6AB

Poiché k2 è anche maggiore di q-1, ripetiamo nuovamente il ciclo:

nuovo K (2)
   0A 5A 64 B9 9C 05 95 20 10 36 86 CB 6F 36 BC FC
   A7 88 EB 3B CF 69 BA 66 A5 BB 08 0B 05 93 BA 53

nuovo V (2)
   0B 3B 19 68 11 B1 9F 6C 6F 72 9C 43 F3 5B CF 0D
   FD 72 5F 17 CA 34 30 E8 72 14 53 E5 55 50 A1 8F

T (terzo tentativo)
   47 5E 80 E9 92 14 05 67 FC C3 A5 0D AB 90 FE 84
   BC D7 BB 03 63 8E 9C 46 56 A0 6F 37 F6 50 8A 7C

e otteniamo finalmente un valore accettabile per k:

k = 0x23AF4074C90A02B3FE61D286D5C87F425E6BDD81B

A.2. Test Vectors (Vettori di Test)​

Nelle sezioni seguenti, forniamo vettori di test per varie dimensioni di chiave e funzioni hash, sia per DSA che per ECDSA.

Tutti i numeri sono forniti in notazione esadecimale. Ogni firma consiste di due interi, chiamati r e s; molte implementazioni codificheranno questi interi in una singola struttura ASN.1 o con qualche altra convenzione di codifica, che è al di fuori dell'ambito di questo documento. Mostriamo anche il valore k utilizzato internamente.

Per ogni chiave, elenchiamo dieci firme, corrispondenti a due messaggi di input distinti, e cinque delle funzioni SHA [FIPS-180-4]: SHA-1, SHA-224, SHA-256, SHA-384 e SHA-512. I due messaggi di input sono la codifica UTF-8 delle stringhe "sample" e "test" (senza le virgolette), di lunghezza 48 e 32 bit, rispettivamente.

Gli esempi ECDSA utilizzano le curve standard descritte in [FIPS-186-4].

A.3. Sample Code (Codice di Esempio)​

Un'implementazione di riferimento completa del processo di generazione deterministica di k descritto in questo documento è disponibile dal sito web dell'autore. Questa implementazione è rilasciata sotto licenza MIT ed è fornita a scopo educativo e di verifica. L'implementazione include sia la generazione di k che test completi rispetto a tutti i vettori di test forniti in questo documento.

Il codice dimostra come implementare correttamente:

  • Le trasformazioni bits2int, int2octets e bits2octets
  • Il processo di generazione di k utilizzando HMAC_DRBG
  • L'integrazione con gli algoritmi di firma DSA ed ECDSA esistenti

Le implementazioni DOVREBBERO essere testate rispetto ai vettori di test forniti per verificare la correttezza. L'implementazione di riferimento può essere utilizzata come base per l'integrazione in sistemi crittografici esistenti.