w/arc SHA: è ora di mandarlo in pensione?

Quando qualcosa scricchiola poi alla fine cede. In tema di sicurezza degli algoritmi per la firma digitale avevevamo avuto segnali inquietanti l’estate scorsa alla conferenza Crypto2004, che annunciavano ’la morte’ di SHA-0 e l’apparire di alcuni profondi problemi in MD5 (http://eprint.iacr.org/2004/199.pdf). I ricercatori Biham e Chen avevano annunciato nuovi risultati nella crittoanalisi di SHA-1, dimostrando di essere in grado di creare collisioni in una versione di SHA-1 che facesse solo 40 round invece degli 80 normalmente previsti.

Cosa significa ’creare una collisione’ su un algoritmo di hash?

Consideriamo le due proprietà base di un algoritmo di questo tipo: deve tradurre documenti diversi, anche solo leggermente, in hash completamente diversi; inoltre, deve essere impossibile ricostruire a partire dall’hash il documento originale. Queste caratteristiche vengono sfruttate, per esempio, per il controllo d’integrità e la firma digitale, firmando non l’intero documento ma solo il suo hash. Tuttavia, dal momento che, per esempio, SHA-1 trasforma un documento qualsiasi, di lunghezza arbitraria, in un hash di 160 bit, è evidente che esisteranno delle collisioni, ovvero coppie di documenti diversi che generano lo stesso hash. Tuttavia l’algoritmo deve garantire che sia infattibile, dato un documento specifico, trovarne un altro con lo stesso hash, oppure, equivalentemente, dato un hash, che sia impossibile generare un documento con tale impronta. Infattibile significa, come spesso accade in crittografia, che l’attacco non è impossibile ma solo improbabile, richiedendo (nel caso di SHA-1) 2^80 tentativi per riuscire.

Capirete quindi il mio disappunto quando, mesi fa, si scatenò su queste notizie un baccano infernale, tra i soliti esagerati che annunciavano la ’morte della firma digitale’, senza sapere assolutamente di cosa stessero parlando, e i minimizzatori che facevano notare come SHA-0 fosse un algoritmo in disuso, MD5 fosse soltanto ’ferito’ e comunque un algoritmo in fase di dismissione, e come l’attacco su SHA-1 fosse su una versione a ranghi ridotti, non sull’algoritmo completo.

Come sempre, la verità stava nel mezzo. Intanto, non è detto che la realizzazione di collisioni, nel senso dato dai crittologi alla parola, sia un attacco praticabile, o immediatamente pericoloso. In secondo luogo, in effetti, quelli di questa estate più che schianti erano degli scricchiolii. Ma è anche vero che sentendo qualcosa scricchiolare chiunque si allontanerebbe d’istinto per evitare brutte sorprese.

Puntualmente, qualche giorno fa tre crittologi cinesi hanno dimostrato che SHA-1 (nella sua versione integrale, non quella ’debole’ analizzata da Biham e Chen) è vulnerabile a un attacco che consente di determinare una collisione in meno operazioni di quelle teoriche: l’attacco cinese trova collisioni in 2^69 operazioni, dunque 2048 volte più velocemente del valore teorico di 2^80.

Veloce è un termine relativo: una stima indica che anche coinvolgendo centinaia di migliaia di computer tale calcolo potrebbe richiedere molti anni. Tuttavia, molti anni sono diversi da molte migliaia di anni: l’attacco, grazie ai cinesi, si è spostato dall’essere infattibile a difficile. Quindi, SHA-1 è mortalmente ferito e, anche se all’atto pratico nè oggi nè domani avremo problemi, dovrà essere rimpiazzato. Esistono delle versioni alternative, a 224, 256, 384 o 512 bit. E sicuramente dobbiamo lavorare alla creazione di alternative che non si basino su SHA e sugli stessi principi che abbiamo sempre usato: MD4, MD5 e SHA sono estremamente simili matematicamente, pertanto sono suscettibili ai cosiddetti ’class break’, ovvero a forme d’attacco trasversali che si potrebbero applicare a tutti questi algoritmi insieme.

Resta poi aperto il problema di come effettuare la transizione per tutti i documenti firmati utilizzando SHA-1 per cui si debba garantire la conservazione e l’integrità anche nel futuro. L’apposizione immediata di una firma (anche non del sottoscrittore originario) con marca temporale con un algoritmo diverso potrebbe consentire di tamponare la falla, in quanto dimostrerebbe l’esistenza del documento e della relativa firma (apposta con SHA-1) oggi, quando l’attacco cinese è materialmente non sfruttabile.

Tuttavia, questo problema è aperto, e ci dice che in fatto di reazioni ai possibili problemi negli algoritmi di firma abbiamo ancora molta strada da fare. Considerando che nel mondo della crittografia gli algoritmi scricchiolano un poco, e tendono a rompersi di schianto, sarebbe opportuno aprire una riflessione anche in campo legale su questo problema.