Prendere due piccioni con una fava: un nuovo schema di codifica rapido e solido

Il nostro mondo digitale è caratterizzato da un’enorme quantità di dati fondamentali e, che siano in transito o at-rest, desideriamo proteggerli e renderli disponibili in caso di perdite o danneggiamenti indesiderati. I codici di correzione errori (ECC, Error Correcting Codes) sono un importante strumento per la trasmissione e lo storage sicuri di dati su media e reti inaffidabili e sono ampiamente utilizzati in diversi contesti, da trasmissione di media digitali, reti cellulari e comunicazioni satellitari a cloud storage, dischi, DVD e RAM high-end.

Un ECC codifica i dati mediante l’aggiunta di ridondanza; i dati vengono visualizzati come un messaggio suddiviso in simboli e poi trasformati in una quantità ancora maggiore di simboli di codice, spesso aggiungendo semplicemente ulteriori simboli al messaggio. Nonostante alcuni simboli di codice vengano alterati o eliminati, di solito rimangono a disposizione abbastanza informazioni da consentire la decodifica e il ripristino del messaggio originale. La maggior parte degli ECC è progettata per garantire la protezione da un numero limitato di errori casuali; tuttavia, esistono importanti applicazioni degli ECC in cui un attacker può introdurre errori mirati a causare danni molto più gravi.

Gli ECC più comuni per la protezione da un simile danneggiamento conflittuale dei dati, quali ad esempio i codici Reed-Solomon, richiedono un’elaborazione eccessiva e notevoli sforzi per la decodifica. Una soluzione completamente opposta è invece rappresentata dai codici a fontana, come ad esempio i codici LT [1] e Raptor [2]. Questi producono un flusso di nuovi simboli di codice potenzialmente non collegati on-demand e decodificano i simboli man mano che vengono resi disponibili, fornendo una codifica e un ripristino del messaggio estremamente efficaci. I codici Raptor costituiscono i più avanzati codici a fontana standardizzati da IETF (RFC 5053 e 6330) e adottati in altri standard per supportare ampie aree di applicazione, quali servizi multimediali (ad esempio MBMS, DVB-H e IP-TV), streaming media o comunicazioni satellitari.

Tuttavia, all’enorme efficienza offerta corrisponde un limite in termini di qualità. I codici LT e Raptor sono progettati per funzionare in modo affidabile solo in caso di erasure casuali, in cui ciascun simbolo di codice viene singolarmente considerato perso con basse probabilità. Non appena si discostano da questa impostazione operativa innocua, non sono più in grado di garantire la decodifica. Anche una semplice erasure mirata può incrementare la probabilità di causare implicitamente errori e ritardi nella decodifica, in quanto potenziali attacker possono sfruttare la struttura del codice per selezionare le erasure che ostacolano del tutto il ripristino del messaggio.

In pratica, le erasure mirate possono essere applicate in modo semplice, ad esempio, se un router compromesso cancella in modo selettivo i simboli che lo attraversano. Lopes e Neves [3] hanno recentemente fornito una dimostrazione di un attacco simile a un applicazione TFTP per il trasferimento di file codificati mediante una versione standardizzata di Raptor. Hanno sfruttato alcune debolezze del codice per prevederne la struttura e calcolare in anticipo i modelli di erasure più dannosi. L’aspetto più allarmante è che le erasure selezionate sono indipendenti dai dati e nella maggior parte delle configurazioni sono costituite da pochissimi simboli di codice; ciò significa che nella maggior parte dei casi non consentono di recuperare il messaggio. L’attacco può essere eseguito alla velocità di linea ed è molto difficile da individuare, poiché viene eliminato un numero molto ridotto di simboli. È inoltre in grado di interrompere il trasferimento dei file in modo efficace anche se la codifica è autenticata o crittografata, ad esempio nel caso in cui il TFTP viene eseguito a un livello superiore del protocollo IPSec/ESP.

Di recente, abbiamo fornito una soluzione al problema sopra descritto. In collaborazione con Ari Juels, James Kelley e Roberto Tamassia, abbiamo dimostrato che è possibile progettare uno schema di codifica con crittografia migliorata, in grado di offrire sia efficienza pratica che elevati livelli di tolleranza agli errori mirati. Abbiamo attribuito alla nostra soluzione il nome di codici Falcon [4]; si tratta di una classe di ECC autenticati e basati su codici LT, che combina le qualità di entrambe le categorie di codici esistenti. In quasi tutti i casi, questi codici sono in grado di correggere eventuali danneggiamenti conflittuali dei simboli conservando al contempo le principali funzionalità dei codici LT standard, ovvero generazione dei simboli di codice e ripristino del messaggio in tempi sufficientemente rapidi da consentire ai simboli di rimanere intatti.

La nuova progettazione apporta ai codici LT due miglioramenti fondamentali. Innanzitutto viene utilizzata una chiave segreta per la codifica dei dati e il ripristino del messaggio. In secondo luogo, la struttura del codice è completamente protetta tramite una semplice combinazione creata da un potente generatore di numeri pseudo-casuali, che esegue la codifica in modo casuale e ne impedisce la previsione. È inoltre possibile utilizzare un linguaggio cifrato sicuro, per crittografare i simboli e impedire eventuali perdite, e un MAC (Media Access Control) per autenticare i simboli e impedire la propagazione di errori. Combinata in modo accurato con lo striping dei dati, la nuova codifica fornisce variabili scalabili in grado gestire messaggi di grandi dimensioni, ad esempio di diversi GB. Grazie all’utilizzo appropriato della crittografia al livello core di codifica LT, i codici Falcon si prestano inoltre a proteggere le estensioni dei codici Raptor che mantengono livelli di efficienza elevati (ad esempio velocità di throughput di 300 MB/s). Infine, per offrire un’efficienza ancora maggiore, i codici Falcon sono in grado di utilizzare al meglio eventuali moduli di sicurezza forniti dal canale di comunicazione (ad esempio il tunneling sui protocolli SSH o IPsec) per ridurre ulteriormente l’overhead richiesto.

Nel complesso, la generazione di simboli di codice rapida e immediata, in grado di garantire un ripristino veloce del messaggio in presenza di un numero limitato di danneggiamenti malevoli, è un’interessante proprietà che rende i codici Falcon piuttosto utili in molti scenari. Offrono livelli di sicurezza molto più solidi rispetto ai codici LT/Raptor, mantenendo al contempo la praticità grazie all’overhead limitato. Nello specifico, è comprovato che i codici Falcon sono in grado di potenziare le capacità dei codici Raptor in caso di attacchi di erasure mirati, come quelli illustrati da Lopes e Neves. Possono inoltre offrire livelli di sicurezza equiparabili a quelli forniti da codici tolleranti agli attacchi già esistenti, come ad esempio Reed-Solomon, ma con un’efficienza ancora superiore. In particolar modo, quando impiegati come sostituzione drop-in di codici personalizzati come quello impiegato da Shi et al [5] nel protocollo di sicurezza per il cloud storage,i codici Falcon evidenziano un incremento della velocità pari al 35%. Grazie alla progettazione innovativa, i codici Falcon offrono la combinazione ideale di sicurezza ed efficienza.

[1] M. Luby: LT Codes. IEEE Symposium on Foundations of Computer Science, 2002: 271.

[2] A. Shokrollahi: Raptor codes. IEEE Transactions on Information Theory, volume 52 n. 6, 2006, 2551-2567.

[3] J. Lopes, N. Neves: Stopping a Rapid Tornado with a Puff. IEEE Symposium on Security and Privacy, 2014: 509-523.

[4] A. Juels, J. Kelley, R. Tamassia, N. Triandopoulos: Falcon Codes: Fast, Authenticated LT Codes (Or: Making Rapid Tornadoes Unstoppable). ACM Conference on Computer and Communications Security, 2015: 1032-1047.

[5] E. Shi, E. Stefanov, C. Papamanthou: Practical Dynamic Proofs of Retrievability. ACM Conference on Computer and Communications Security, 2013: 325-336.

No Comments