Apri il menu principale

In crittografia, l'Elliptic Curve Digital Signature Algorithm (ECDSA) offre una variante del Digital Signature Algorithm (DSA) usando la crittografia ellittica. Fu proposto la prima volta nel 1992 da Scott Vanstone. Nel 1998 è diventato uno standard ISO (ISO 14888), nel 1999 è stato accettato come standard ANSI (ANSI X9.62) mentre nel 2000 è diventato uno standard IEEE (IEEE P1363 2)[1].

Dimensioni della chiave e della firma in confronto al DSAModifica

Come in generale nella crittografia delle curve ellittiche, la dimensione in bit della chiave pubblica necessaria all'ECDSA è circa il doppio della dimensione del livello di sicurezza in bit. Per esempio, con un livello di sicurezza di 80 bit (un massimo di   operazioni necessarie ad un aggressore informatico per trovare la chiave privata) la dimensione di una chiave pubblica ECDSA sarebbe di 160 bit, laddove la dimensione della chiave pubblica DSA è di almeno 1024 bit. La dimensione della firma è la stessa per ECDSA e DSA:   bit, dove   è il livello di sicurezza misurato in bit; nell'esempio precedente (con   = 80 bit), la dimensione della chiave è di 320 bit.

Algoritmo di generazione della firmaModifica

Si supponga che Alice voglia mandare a Bob un messaggio protetto da firma digitale. Inizialmente devono accordarsi sui parametri della curva  . Oltre al campo e all'equazione della curva, è necessario  , un punto base di ordine primo sulla curva;   è l'ordine moltiplicativo del punto  .

Parametro
CURVE campo ed equazione della curva ellittica usata
G punto base della curva, un generatore della curva ellittica avente ordine primo grande n
n ordine intero di G, tale per cui  

Alice genera una coppia di chiavi consistente in una chiave privata  , scelta casualmente nell'intervallo   ed una chiave pubblica  . Si usa   per indicare la moltiplicazione di uno scalare per un punto della curva ellittica.

Al fine di generare una firma per il messaggio  , Alice segue questi passi:

  1. Computa  , dove HASH è una funzione crittografica di hash, come SHA-2.
  2. Sia   la stringa formata dai   bit più a sinistra di  , dove   è la lunghezza in bit del gruppo di ordine  .
  3. Seleziona casualmente in modo crittografico-sicuro un intero   dall'intervallo  .
  4. Calcola il punto della curva  .
  5. Calcola  . Se  , ritorna al passo 3.
  6. Calcola  . Se  , ritorna al passo 3.
  7. La firma è la coppia  .

Computando  , la stringa   risultante da   deve essere convertita ad intero. Si noti che   può essere più grande di   ma non più lunga.[2]

Come stabiliscono gli standard, è cruciale che vengano selezionati   diversi per firme diverse, altrimenti l'equazione al passo 6 può essere risolta per  , la chiave privata: date due firme   e  , l'impiegare la stessa   per due messaggi differenti   e   apre ad una vulnerabilità ad attacchi. Un aggressore può calcolare   e  , e poiché   (tutte le operazioni di questo paragrafo sono svolte in modulo  ) l'aggressore può trovare  . Dato che  , l'aggressore può ora calcolare la chiave privata  . Questa implementazione errata è stata sfruttata, per esempio, per estrarre la firma digitale usata nella console PlayStation 3.[3]

Un'altra situazione in cui la firma ECDSA può lasciare trapelare le chiavi private si ha quando   è generato da un random number generator difettoso. Una falla simile causò la perdita dei fondi di alcuni portafogli di bitcoin su piattaforma Android nell'agosto 2013.[4] Per assicurare che   sia unico per ogni messaggio si può bypassare completamente la generazione casuale e ottenere una firma in modo deterministico computando   dal messaggio e dalla chiave privata.[5]

Algoritmo di verifica della firmaModifica

Per autenticare la firma di Alice, Bob deve avere una copia della chiave pubblica  . Bob può verificare che   è un punto valido della curva nel modo seguente:

  1. Controlla che   non sia uguale all'elemento neutro  , e che le sue coordinate siano altrettanto valide.
  2. Controlla che   appartenga alla curva.
  3. Controlla che  .

Dopo, Bob farà quanto segue:

  1. Verifica che   e   siano interi appartenenti a . In caso contrario, la firma non è valida.
  2. Computa  , dove HASH è la stessa funzione usate nel processo di generazione della firma.
  3. Sia   la stringa formata dai   bit più a sinistra di  .
  4. Calcola  .
  5. Calcola    .
  6. Calcola il punto della curva .
  7. La firma è valida se  , altrimenti non è accettata.

Si noti che usando lo Shamir's trick, una somma di due moltiplicazioni scalari   può essere calcolata in tempo inferiore a quello necessario allo svolgimento indipendente delle due moltiplicazioni scalari.[6]

Correttezza dell'algoritmoModifica

Il corretto funzionamento dell'algoritmo di verifica non è banale. Si denoti con   il punto della curva calcolato al passo 6 della verifica,

 

Sostituendo la definizione della chiave pubblica  ,

 

La moltiplicazione di un punto della curva ellittica per uno scalare gode della proprietà distributiva,

 

Espandendo la definizione di   e   dal passo 5 dell'algoritmo di verifica,

 

Raccogliendo  ,

 

Espandendo la definizione di   dal passo 6 dell'algoritmo di generazione della firma,

 

Dato che l'inverso dell'inverso è uguale all'elemento originale, e il prodotto fra l'inverso di un elemento e l'elemento stesso è l'identità, l'espressione si può così semplificare

 

Dalla definizione di  , questo è il passo 6 dell'algoritmo di verifica.

Questo però mostra solo che un messaggio firmato correttamente supererà la verifica; sono necessarie molte altre proprietà per un algoritmo di firma sicuro.

SicurezzaModifica

Nel dicembre 2010, un gruppo che si fa chiamare fail0verflow annunciò di aver scoperto la chiave privata ECDSA usata da Sony per firmare i software della console Playstation 3. Tuttavia, questo attacco funzionò perché Sony non implementò correttamente l'algoritmo,   era statico invece che casuale. Come è sottolineato nella precedente sezione Algoritmo di generazione della firma, ciò rende risolvibile   ed inutile l'intero algoritmo.[7]

Il 29 marzo del 2011, due ricercatori pubblicarono un documento IACR[8] dimostrando che è possibile recuperare una chiave privata TLS di un server usando OpenSSL il quale esegue un'autenticazione ECDSA su un campo binario attraverso un timing attack.[9] La vulnerabilità ha ricevuto un fix nella release OpenSSL 1.0.0e.[10]

Nell'agosto 2013, è stato reso pubblico che alcune implementazioni della classe Java SecureRandom talvolta generavano collisioni nel valore  . Come discusso sopra, questo ha permesso la risoluzione delle chiavi private, di conseguenza ciò ha aperto alla possibilità di rubare bitcoin dalle app Wallet Android, le quali erano basate su ECDSA per l'autenticazione delle transazioni.[11]

Questo problema può essere risolto da una generazione deterministica di  , come descritto da RFC 6979.

NoteModifica

  1. ^ Crittosistemi basati su curve ellittiche, su www.di.unisa.it. URL consultato il 17 gennaio 2017.
  2. ^ NIST FIPS 186-4, July 2013, pp. 19 and 26
  3. ^ Console Hacking 2010 - PS3 Epic Fail Archiviato il 15 dicembre 2014 in Internet Archive., page 123–128
  4. ^ Android Security Vulnerability, su bitcoin.org. URL consultato il 24 febbraio 2015.
  5. ^ RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), su tools.ietf.org. URL consultato il 24 febbraio 2015.
  6. ^ The Double-Base Number System in Elliptic Curve Cryptography (PDF), su lirmm.fr. URL consultato il 22 aprile 2014.
  7. ^ Mike Bendel, Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access (Exophase.com), 29 dicembre 2010. URL consultato il 5 gennaio 2011.
  8. ^ Cryptology ePrint Archive: Report 2011/232, su eprint.iacr.org. URL consultato il 24 febbraio 2015.
  9. ^ Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack
  10. ^ ChangeLog, OpenSSL Project. URL consultato il 22 aprile 2014.
  11. ^ 12 Aug 2013 at 00:43, Richard Chirgwin tweet_btn(), Android bug batters Bitcoin wallets, su theregister.co.uk. URL consultato il 17 gennaio 2017.

BibliografiaModifica

Voci correlateModifica

Collegamenti esterniModifica