1.1 Modelli di trasmissione Sincrono e Asincrono Introduzione C 1

4

C

1

Introduzione

In questo capitolo, dopo la presentazione dei modelli di trasmissione sincrono e asincrono, saranno analizzati alcuni attacchi DoS in ambiente multicast. A tale proposito si descriveranno due soluzioni diverse, che permettono di ovviare ad alcuni di questi attacchi: PRABS e CECInA.

1.1 Modelli di trasmissione Sincrono e Asincrono

I modelli di comunicazione si possono differenziare in base a dei parametri, quali la sincronia nelle comunicazioni, i guasti e la topologia del mezzo di comunicazione.

La sincronia di un modello è un attributo relativo alle assunzioni temporali per i processi e il canale di comunicazione. Esistono due modelli principali: il modello sincrono e il modello asincrono.

In un sistema sincrono si hanno delle assunzioni temporali che permettono di ridurre il non-determinismo del sistema, semplificando il lavoro dei progettisti delle applicazioni (essendo all’oscuro delle effettive caratteristiche di sincronia del sistema sottostante). Formalmente, si dice che un sistema è sincrono [10, 11] quando per esso valgono le seguenti proprietà:

• Esiste, ed è noto, un limite superiore δ sul ritardo di consegna dei messaggi;

5

• Ogni processo ha un clock locale con un tasso di deviazione1_{, rispetto al} tempo reale, conosciuto e limitato.

• Esistono limiti superiori conosciuti sul tempo richiesto da un processo per eseguire un passo d’elaborazione elementare.

In un sistema sincrono si possono inserire time-out dei messaggi, che forniscono degli utili meccanismi per individuare dei fallimenti e quindi comportano una maggiore affidabilità. Tuttavia non è semplice assicurare queste proprietà su un sistema di grosse dimensioni e soprattutto nel tempo.

In un sistema asincrono, al contrario di quello sincrono, non c’è limite sul ritardo di consegna dei messaggi, sulla deviazione dei clock o sul tempo necessario per eseguire un passo computazionale [10]. In sostanza un sistema asincrono è caratterizzato dal fatto di non fare nessun’assunzione temporale. Questo modello è quello maggiormente più usato, per ragioni diverse: ha una semplice semantica; le applicazioni realizzate su di esso sono più generali e trasportabili di quelle che considerano delle specifiche assunzioni temporali; le ipotesi del modello sincrono sono valide solo in modo probabilistico, visto che carichi di lavoro variabile e inaspettato2 sono causa di asincronia: è difficile assicurare le proprietà di sincronia in sistemi di larga scala e per molto tempo; le infrastrutture di rete e i sistemi operativi oggi più commerciali sono riconducibili a sistemi asincroni3 [10, 11].

I modelli sincrono e asincrono costituiscono gli estremi di uno spettro di possibilità, in cui si vanno ad inserire dei modelli intermedi, i cosiddetti modelli parzialmente sincroni. Quest’ultimi permettono di adattare maggiormente alla realtà i modelli sincroni. Si distinguono tra loro a seconda del livello di sincronia assunto. Ad esempio, possono avere clock sincronizzati ma ritardo di trasmissione

1 _{Meglio conosciuto come drift rate, che indica lo scostamento tra il clock locale e il tempo reale.} 2 _{Di cui sono soggetti soprattutto sistemi che coprono grandi aree geografiche.}

3 _{UDP, ad esempio, non è in grado di limitare superiormente il tempo di consegna di un pacchetto,} mentre la maggior parte dei sistemi operativi non sono in grado di assicurare variazioni limitate nelle velocità dei processi in esecuzione.

6

dei messaggi non limitata, oppure il ritardo dei messaggi è limitato ma sconosciuto [11]. Un tale modello tenderà, quindi, più verso la sincronia o l’asincronia in base alle assunzioni temporali che si faranno.

1.1.1 Limitazioni del servizio Best-Effort

Le comunicazioni in multicast devono fare i conti con il servizio best-effort [9] offerto dal protocollo IP di livello network, dove non è garantito l’arrivo di tutti i pacchetti, non si hanno garanzie sul ritardo di consegna di un pacchetto a destinazione e dove i pacchetti possono arrivare non ordinati. Inoltre, nel caso di comunicazioni sincronizzate, si possono verificare dei fallimenti di timing, in cui vengono violati i limiti temporali imposti sulle velocità di esecuzione o sulla deviazione del clock, oppure in cui un canale guasto trasporta messaggi in modo più lento o veloce rispetto alle sue specifiche. Per esempio, la consegna di un pacchetto potrebbe avvenire con un ritardo superiore alla soglia massima δ, ed il pacchetto stesso sarebbe quindi considerato come perso.

Esistono metodi per rendere la comunicazione più affidabile come la ritrasmissione dei pacchetti (non efficiente nel multicast) o l’introduzione di pacchetti ridondanti (IDA ne è un esempio).

1.1.2 Real-time

Il traffico tra mittente e destinatario può essere di tipo Real-time [9, 11]: trasmissione file audio e video, teleconferenza e multiconferenza, web tv e internet radio. Il real-time impone rigide costrizioni sul ritardo del pacchetto e sul packet jitter. Il packet jitter è la variabilità del ritardo, dalla sorgente al destinatario, di un pacchetto, all’interno dello stesso packet stream. Il real-time lavora bene in condizioni di banda abbondante, dove ritardi e jitter sono minimi. I dati devono essere riprodotti da parte del destinatario con lo stesso tempo con il

7

quale sono stati registrati. Per questo il destinatario dovrà bufferizzare i pacchetti ricevuti per un breve periodo di tempo4 prima di iniziare la riproduzione, in modo da eliminare lo jitter.

Nel real-time non si può pensare che il destinatario stia in attesa un tempo troppo lungo. Se non si riesce a ricostruire il packet stream in tempo breve, le perdite occasionali causeranno dei buchi nella riproduzione audio/video, che possono essere parzialmente o completamente mascherati (dipende da come l’informazione è codificata e trasmessa, e da come il destinatario vuole mascherare la perdita5). La caratteristica principale è che dal momento in cui la riproduzione del file multimediale ha inizio, questa deve procedere in accordo ai tempi originali. Questo impone seri limiti sul ritardo per l’arrivo dei dati, che altrimenti sono considerati persi. La funzione del buffer sul ricevitore diventa quella di ammortizzare i problemi di sincronizzazione a breve termine e fornire, quindi, una certa tolleranza a piccoli malfunzionamenti di natura temporale. Per fare fronte a questi problemi vengono combinati anche metodi che prevedono un numero di sequenza per ogni pacchetto generato dal mittente, e una procedura di timestamp, in cui il mittente stampa in ogni pacchetto l’ora nella quale il pacchetto stesso è stato generato.

La trasmissione delle informazioni dovrà essere temporizzata. Si dovrà considerare, quindi, un’unità di trasmissione, per stabilire che l’invio di pacchetti consecutivi sia distanziato da un intervallo di tempo predefinito e conosciuto. Occorrerà a tal fine un’iniziale sincronizzazione, dove ogni ricevitore confronterà la sua ora locale con quella del mittente e ne registrerà la differenza. Quello che al ricevitore necessita è un valore δ tale che il clock del mittente e quello del destinatario non differiscano più di δ unità di tempo. Un’assunzione necessaria

4 _{Tipicamente da due a cinque secondi. Dipende soprattutto dal metodo di consegna e dal tipo di} rete.

8

dovrà essere che i clock interni del mittente e destinatario non fluttuino “troppo” durante una sessione [12].

Nel momento in cui il destinatario riceve un pacchetto, dovrà accertare che esso verifichi i limiti temporali necessari per assicurarsi che si tratti di un pacchetto legittimo. Un attaccante, infatti, potrebbe decidere di intercettare un pacchetto da un canale di comunicazione, modificarlo a piacimento e rispedirlo al destinatario. A tal fine il destinatario dovrà conoscere lo scheduling dei pacchetti inviati dalla fonte. Il pacchetto Pi deve essere ricevuto prima del pacchetto Pi+1, e per questo il ricevitore dovrà verificare una condizione di sicurezza. Sia Ti l’ora d’invio del pacchetto Pi secondo il clock del mittente e TArr(i) l’ora d’arrivo secondo il clock sincronizzato del ricevitore: la condizione sarà che TArr(i) + δ < Ti+1 [11, 12]. Quest’ultima condiziona il tasso di trasmissione dei pacchetti, costringendo il mittente ad inviarli più lentamente del ritardo di rete, poiché il pacchetto Pi+1 non può essere inviato prima che il destinatario abbia ricevuto il pacchetto Pi. Per ovviare a quest’inconveniente si può inserire un parametro di ritardo d, calcolato dal mittente in base al parametro δ e al ritardo massimo di rete tollerabile, che sarà comunicato al destinatario all’inizio della sessione. La condizione di sicurezza diventerà allora la seguente: TArr(i) + δ < Ti+d, rendendo la comunicazione tano più tollerabile quanto più il parametro d è grande.

1.2 Trasmissione Multicast

Il Multicast [13,14] è nato per la necessità di trasmettere dati (in particolare flussi multimediali, in analogia con la radio e televisioni trasmesse nell’etere) a diversi destinatari in rete, ma non a tutti. Su questo tipo di trasmissione si basano tutte quelle applicazioni che servono milioni d’utenti contemporaneamente. Nel multicast, una singola copia di pacchetti è inviata da uno o più mittenti ed instradata, attraverso i multicast router, ad ogni ricevente che appartenga ad uno stesso gruppo multicast. A differenza della trasmissione Broadcast, che prevede

9

che una sorgente invii pacchetti a tutti gli host presenti su un segmento di rete (una LAN), il multicast permette di inviare pacchetti ad un gruppo di destinazioni IP in un qualunque punto della rete. La trasmissione multicast richiede la gestione dei gruppi, di tipo dinamica: occorre un sistema che consenta di creare e distruggere gruppi e che permetta ai processi di entrare ed uscire da quest’ultimi [14]. In questo modo i router (responsabili della consegna dei pacchetti) vengono a conoscenza dei gruppi d’appartenenza dei loro host, comunicandoli ai router vicini, facendo in modo che le informazioni si propaghino.

Per permettere la trasmissione multicast la Internet Engineering Task Force (IETF) ha provveduto a definire una estensione dello IP, lo IP multicast. Mentre alla tradizionale trasmissione unicast sono assegnati gli indirizza della classi A, B e C, alla comunicazione multicast si assegnano gli indirizzi della classe D, dal 224.0.0.0 al 239.255.255.255.

Figura 1: Classi d’indirizzi IP.

Nel momento in cui un utente abbia intenzione di aggregarsi ad un certo gruppo di ricezione, associato ad un particolare indirizzo multicast, l’host abiliterà il livello IP a ricevere i datagram packets con il relativo indirizzo multicast.

Il multicast richiede l’uso del connection-less datagram transport protocol (UDP), che non prevede la ritrasmissione dei pacchetti (dato che non è previsto nessun meccanismo di acknowledgement, come nel TCP), nonché il loro ordine d’arrivo. L’UDP assicura che, nel caso di un numero elevato di riceventi, non si verifichino

10

fenomeni di “ACK implosion”6 o congestione delle risorse del mittente per la gestione dello stato delle trasmissioni verso tutti i destinatari. Poiché UDP non dà nessuna sicurezza nella consegna dei messaggi, si possono prevedere meccanismi di ridondanza delle informazioni (FEC).

Attraverso la rete configurata per il Multicast passa un flusso che è costante a prescindere dal numero d’utenti collegati. La quantità di banda passante è pari al bit-rate del contenuto audio/video oggetto dello streaming. Per ogni tratto di linea, quindi, una trasmissione multicast non impegna più risorse di rete come nel caso di una singola trasmissione unicast. Ciò riduce drasticamente il traffico di dati e lo spreco di risorse di rete. Il principale vantaggio della tecnica multicast consiste nella possibilità di far pervenire gli stessi dati a molti utenti, impiegando una larghezza di banda minore di quella che sarebbe impiegata da numerose singole connessioni unicast (una per ogni utente che deve ricevere i dati). In casi come questo, la trasmissione unicast rappresenta un notevole spreco di risorse. Infatti, ogni trasmissione unicast contiene gli stessi identici dati di tutte le altre connessioni unicast (a parte i segnali di controllo). Per esempio, se si intende trasmettere una videoconferenza (250 Kbit/sec) a cento singoli utenti, la larghezza di banda necessaria impiegando cento singole connessioni unicast raggiungerebbe i 25 Mbit/sec. Usando invece la tecnica multicast, la larghezza di banda impiegata non supera i 250 Kbit/s in ogni tratto di linea. Ciò consente di trasmettere più video conferenze senza bisogno di linee a larga e larghissima banda.

Si vedranno, nel seguito del documento, meccanismi che permettono una più sicura trasmissione in multicast anche in presenza d’attacchi da parte di un avversario.

6 _{Il mittente riceve numerosi acknowledgments simultaneamente, che non possono essere tutte} processate.

11

1.3 I codici a correzione di errore

Per rendere il Multicast sicuro contro la perdita d’informazioni che impediscono la ricostruzione del dato inviato dal mittente, si possono usare tecniche di correzione di errore FEC (Forward Errors Correction) [3,9]. Nei protocolli di rete, FEC può essere implementato usando gli erasure codes [1,4]. Il primo vantaggio nell’uso di questa tecnica è che si elimina la necessità di ritrasmissione dei pacchetti mancanti o danneggiati, inappropriata nel Multicast sia perché la rete potrebbe essere altamente asimmetrica (si pensi alle comunicazioni satellitari), sia perché la ritrasmissione dei pacchetti prevedrebbe l’uso di un acknowledgment (ACK) per ogni pacchetto ricevuto, impensabile in una situazione nella quale si hanno più destinatari, come nel Multicast.

Il principio di un erasure code è d’inviare informazioni ridondanti che permettano al destinatario la ricostruzione del dato, anche in presenza di un certo numero di pacchetti mancanti. Questo include una fase di codifica da parte del mittente, dove i pacchetti ridondanti sono costruiti dal dato originale, e una fase di decodifica eseguita dal destinatario, dove il dato originale è estratto, se possibile, dai pacchetti disponibili. Il mittente si occuperà di codificare con un erasure code un insieme di simboli ed inviarli su un erasure channel. Il destinatario può quindi recuperare un’esatta copia dell’informazione da un qualunque sottoinsieme dei simboli codificati. Un erasure code ha tipicamente un blocco codificato con un rapporto fisso, cioè, k simboli in ingresso sono usati per generare n-k simboli ridondanti per un totale di n simboli codificati, e il rapporto di codifica è k/n [1]. Nel mondo delle telecomunicazioni un blocco è normalmente composto da un piccolo numero di bits. Nelle comunicazioni tra computer, invece, la quantità d’informazione è molto più grande: un pacchetto di dati spesso è composto da centinaia o migliaia di bits. Questo cambia il modo in cui un erasure code può essere implementato [3].

12

Figura 2: Rappresentazione grafica del processo di Codifica e Decodifica.

Un erasure code è una buona tecnica per tollerare la perdita di pacchetti in un canale insicuro, tuttavia è esposto ad un pollution attack, in cui un avversario può iniettare invalidi simboli nel canale di comunicazione rendendo invalida anche la ricostruzione del dato [2]. Per questo, come si vedrà, dovrebbe essere integrato con metodologie che impongono l’autenticità.

Un esempio di codice a correzione d’errore è IDA (Information Dispersal Algorithm) [4], descritto di seguito.

1.3.1 IDA – Information Dispersal Algorithm

L’Information Dispersal Algorithm [4] è un’ottima tecnica per tollerare la perdita dei pacchetti. Un dato D di d caratteri è codificato in un insieme n = q + r di simboli. IDA permette di implementare efficientemente le procedure di codifica e decodifica. La complessità di codifica è O(d), mentre quella di decodifica è O(d(log q + r)), usando un’implementazione dell’algoritmo basato sulla trasformata di Fourier introdotto in [5].

13

Altri esempi di erasure codes sono Tornado, LT codes [1], i quali richiedono tempo lineare nella codifica e decodifica, e (k, n) threshold scheme [20]; questi sono però meno efficienti di IDA nell’uso dello spazio.

Proposto agli inizi degli anni ’90 da Michael Rabin, IDA disperde un file D in n pezzi Di, 1 ≤ i ≤ n, permettendone la ricostruzione da un insieme qualsiasi di q pezzi, con q ≤ n. Il punto chiave è che ogni Di è grande |D|/q, dove |D| è la dimensione (in numero di caratteri) del dato D. Di conseguenza, il numero totale di caratteri prodotti dall’algoritmo è (n/q) ·|D|. Dal momento che si può scegliere n/q ~ 1, il metodo di dispersione è, in termini di spazio occupato dalle singole componenti, spazialmente efficiente, in quanto q messaggi di dimensione |D|/q contengono esattamente la stessa quantità d’informazioni del dato originale. Il metodo può essere visto come appartenente al campo dei codici a correzione di errore, in cui dei bits addizionali sono aggiunti al messaggio creando un blocco; dopo l’occorrenza di k errori nel blocco, il messaggio può ancora essere ricostruito. Questi k bits possono essere in qualsiasi posizione nel blocco.

Si assegna a D = b1,b2, …,bN (dove |D| = N) una sequenza di caratteri. Si assuma di volere disperdere D sotto la condizione che non più di r pezzi possono essere persi nella comunicazione. I caratteri bi sono considerati degli interi appartenenti ad un range [0…B]. Se, ad esempio, bi fosse di otto bits, si avrà 0 ≤ bi ≤ 255. Si sceglierà un opportuno7 _{intero q affinché n = q + r soddisfi la disequazione n/q} ≤ 1 + ε, per un appropriato ε > 0. Si sceglieranno, inoltre, n vettori ai = (ai1,…, aiq) di lunghezza q, in modo tale che un qualsiasi sottoinsieme di q differenti vettori siano linearmente indipendenti. Si dividerà adesso il dato D in sequenze di lunghezza q, nel seguente modo

D = (b1,……,bq), (bq+1,……,b2q), …, (bN-q+1,……,bN), indicando le sequenze

7 _{Il compromesso tra ridondanza delle informazioni e probabilità di decodifica sarà regolato dai} parametri q e n. Nel caso che n >> q si avrà un’alta ridondanza e di conseguenza una maggiore probabilità di decodifica.

14

S1 = (b1,……,bq); …; SN/q = (bN-q+1,……,bN).

Si costruiranno, infine, le n parti di D nel seguente modo: per i = 1,…, n Di = ci1, ci2, …, ciN/q

dove, per k = 1,…, N/q

cik = ai · Sk = ai1 · b(k –1)q+1 +……+ aiq · bkq.

In questo modo si sono disperse le informazioni Sj in n pacchetti Di di lunghezza |D|/q. La dimensione totale dei bits inviati sulla rete sarà, quindi, (n/q)·|D|.

Se almeno q pacchetti sono stati ricevuti correttamente, il destinatario potrà ricostruire il dato D nel seguente modo. Siano Dj, per j = 1, …,q, i pacchetti ricevuti dal destinatario degli n inviatogli dal mittente. Sia inoltre A la matrice quadrata q x q formata da q vettori aj, di indici corrispondenti ai pacchetti ricevuti, usati per la codifica. A sarà una matrice invertibile, dato che i vettori che la compongono sono linearmente indipendenti. Si può facilmente vedere che:

A · = .

Di conseguenza gli Sj originali potranno essere recuperati con l’operazione inversa: S1 = = A -1 · , per j = 1, …, N/q. a1 · S1 … aq · S1 b1 … bq b1 … bq a1 · S1 … aq · S1

15

1.4 Signature amortization

Le comunicazioni multicast sono state implementate per assicurare un’efficiente consegna di dati ad un gran numero d’utenti. Naturalmente, la sicurezza ha un ruolo importante in questo tipo di comunicazioni: confidenzialità, autenticità ed integrità dei messaggi scambiati tra i membri di un gruppo multicast, sono requisiti critici. Autenticità significa che quando un utente riceve un messaggio, egli ha la possibilità di assicurarsi sull’identità del mittente. In un contesto multicast, questo obiettivo è raggiungibile adottando tecniche di crittografia a chiave pubblica8, quando non è assunta nessuna sincronizzazione tra la sorgente e i riceventi [12]. Anche se mittente e ricevente sono capaci di identificarsi a vicenda, si vuole essere sicuri che il contenuto della loro comunicazione non sia alterato sia da errori di trasmissione sia da attacchi da parte di un avversario. L’integrità del messaggio inviato sulla rete è un punto cruciale, e sarà trattato nel seguito. La confidenzialità implica che solo utenti autorizzati possono comprendere (decifrare) un messaggio multicast.

Un destinatario di una trasmissione multicast, per difendersi contro avversari che iniettano pacchetti corrotti, deve avere la possibilità di verificare l’autenticità dei pacchetti ricevuti.

Un approccio per l’autenticazione, nella trasmissione multicast, è basato su tecniche di signature amortization [15, 16]. Questo schema divide lo stream multicast in blocchi di pacchetti sequenziali, ed autentica tutti i pacchetti in un blocco con una singola firma. Signature amortization è un ottimo approccio per l’autenticazione in multicast, perché distribuisce l’overhead di comunicazione e di calcolo della firma digitale su molti pacchetti. Il ricevente necessita della firma digitale per verificare l’autenticità dei pacchetti in un blocco, ma la trasmissione, nel modo più affidabile possibile, della firma richiede alcune considerazioni.

8 _{La crittografia a chiave simmetrica è un’ottima soluzione per comunicazioni point-to-point, ma} risulta inadeguata in un contesto multicast.

16

Firmare ogni singolo pacchetto di un messaggio è robusto in termini di perdita dei pacchetti, ma s’incorrerebbe in un alto overhead di comunicazione e computazione. D’altro canto includere pochi bytes, per la firma, in ogni pacchetto, è efficiente in termini di spazio ma non assicura robustezza contro la perdita dei pacchetti. Gli schemi proposti differiscono principalmente su come trovano soluzioni diverse a questi problemi.

Alcuni approcci fanno uso di hash graphs [12,18]. I protocolli hash graph costruiscono un grafo diretto, partendo dai pacchetti, dove ogni nodo contiene il valore hash del vicino nel suo arco in entrata. L’hash graph termina con un pacchetto firmato (signature packet) che autentica un gruppo di nodi del grafo. Se il signature packet non viene perso ed esiste un percorso da un particolare pacchetto sino alla firma, il ricevente autentica il pacchetto in questione attraversando il percorso di hash sino alla firma digitale, verificandola.

Il protocollo Hash graph è vulnerabile ad un attacco di tipo DoS, chiamato signature flooding. Un avversario può immettere nello stream delle firme invalide, che sovraccaricheranno le risorse computazionali del ricevente che proverà a verificare le firme.

Alcune ricerche appoggiano l’uso di erasure codes (come, ad esempio, IDA) per la signature amortization [15,16], ma queste tecniche sono esposte ad un pollution attack [2].

A tale proposito, prima di descrivere l’approccio usato in questo documento per realizzare la signature amortization, è bene definire i tipi d’attacchi DoS ai quali sono soggetti i destinatari delle comunicazioni multicast.

1.5 Attacchi DoS

Si definisce attacco Denial of Service una qualunque attività finalizzata alla negazione di un servizio ad un utente legittimo. Un attacco DoS si prefigge come obiettivo quello di ridurre o addirittura negare la disponibilità di una risorsa. Tale

17

manomissione può essere perseguita attraverso diverse strategie, inondando, ad esempio, la rete con informazioni inutili in modo da impedirne un uso normale. Gli attacchi DoS possono avere come obiettivo un singolo host o un’intera rete. È possibile distinguere un DoS in base a tre distinte modalità d’attacco: consumo di risorse limitate, alterazione o distruzione delle informazioni di configurazione, alterazione o distruzione fisica dei componenti di rete.

Un computer o una rete necessitano di determinate risorse per poter operare correttamente: tempo di CPU, memoria e spazio su dischi, strutture dati, accesso ad altri computer e reti, banda di rete. Un obiettivo molto frequente di un attacco DoS è la connessione alla rete; negando la connettività, ad esempio, si pregiudica il normale funzionamento del server, rendendo indisponibile il servizio per il quale è destinato. Tale obiettivo può essere perseguito anche attraverso il consumo di tutta la banda disponibile, generando un gran numero di pacchetti verso la vittima. L’operatività di un sistema di rete può essere compromessa, inoltre, riducendo tutte le altre risorse di cui il sistema dispone e che gli sono necessarie per operare. Le limitate risorse della CPU possono essere sfruttate per negare un servizio ad un utente: mandando in esecuzione un gran numero di processi che alternativamente richiedono l’uso del processore, si rende, di fatto, la macchina inutilizzabile per usi legittimi. Lo spazio sui dischi è ancora uno dei principali obiettivi di un attacker: in generale qualunque operazione che consenta di scrivere una grossa quantità di dati su disco può essere utilizzata per realizzare un attacco denial of service.

Di seguito ci si concentrerà sugli attacchi contro le risorse di computazione e memorizzazione cui sono soggetti i riceventi di una trasmissione multicast.

Si definisce polluted erasure channel [2,6] un modello di comunicazione in cui i simboli validi possono essere persi, e un avversario può iniettare simboli invalidi rivendicandoli come validi. Polluted erasure channels modella bene un ambiente multicast, in cui un avversario può osservare, iniettare, modificare, ritardare ed eliminare messaggi inviati nei canali di comunicazione.

18

In un signature flooding un avversario inonda di firme false un destinatario, con l’obiettivo di saturare le capacità di calcolo di quest’ultimo costringendolo alla verifica di un numero elevato di firme.

In un pollution attack un avversario può iniettare simboli invalidi in un multicast stream (injection attack), corrompendo il processo di decodifica del destinatario. Un erasure code è soggetto a questo tipo di attacco, poiché se il decoder riceve in input dei simboli invalidi, restituirà un’errata costruzione dell’informazione. Inoltre questo tipo d’attacco costringe il destinatario a memorizzare un gran numero di pacchetti causando, nel caso peggiore, un DoS sulle capacità di memorizzazione della macchina del ricevente.

Saranno presentati nel seguito dei distillation codes robusti contro questi tipi d’attacco.

1.6 PRABS

In [2] è presentato un codice di distillazione che assicura autenticità e correttezza, nel senso che il risultato del codice sarà sempre una ricostruzione valida del messaggio inviato dal mittente. S’introduce un algoritmo, PRABS (Pollution Resistant Authentication Block Streams), che permette al ricevente di un messaggio di resistere sia ad un pollution attack sia ad un signature flooding. Le comunicazioni tra il mittente ed i destinatari non formulano nessun’ipotesi di sincronia.

Secondo questo approccio, l’informazione D, prodotta dal mittente, e la sua firma Ds sono codificati con un erasure code (come, ad esempio, IDA) per produrre un insieme di simboli S = {S0,…,Sn-1}, dove n = q+r (r è il numero di simboli ridondanti). Per resistere ad un pollution attack, il codice di distillazione deve permettere, in fase di decodifica, di distillare i simboli validi, prodotti dall’erasure code, dall’insieme dei simboli invalidi. Tutto ciò è ottenuto, in fase di codifica

19

dell’algoritmo proposto, unendo ogni simbolo con un witness9{W0,…,Wn-1}, dove Wi = WITNESS(Si ,S). Quando il destinatario riceve un pacchetto Pi = <i,Si , Wi >, lo verifica usando una funzione RECOVER(Pi) che produce un intero ai. Il destinatario raggruppa i pacchetti cosi ricevuti in base alla funzione RECOVER,

producendo degli insiemi Q0,…,Qu-1 di pacchetti, con la proprietà che Pi, Pj ∈ Qc, con c ∈ [0, u-1], se e solo se RECOVER(Pi) = RECOVER(Pj). Si noti che per fare questo non è necessario determinare se un dato simbolo è valido. La funzione

WITNESS è fatta in modo tale che è impossibile in tempo polinomiale, per un

attaccante, trovare un pacchetto invalido P' tale che RECOVER(P') = RECOVER(Pi), con Pi un pacchetto valido. Di conseguenza, uno degli insiemi Q0,…,Qu-1 conterrà solo i pacchetti validi generati dalla legittima sorgente. Il destinatario, quindi, eseguirà l’erasure decoding per ogni insieme Qc (con cardinalità |Qc| ≥ q) per produrre D e Ds. Solo uno degli insiemi corrisponderà al legittimo gruppo di pacchetti e solo questo passerà con successo il controllo d’autenticazione. Per implementare la funzione WITNESS, che soddisfi le proprietà sopra descritte, in [2]

è proposto un Merkle hash tree [17]. Questo significa che l’approccio descritto ha un overhead di una firma per blocco (prodotto dall’erasure code), più log n hash per pacchetto.

Il principale svantaggio di questo metodo è che, poiché la verifica della firma è effettuata solo per quegli insiemi la cui cardinalità è almeno q, nel caso peggiore questo richiede: (a) memorizzare tutti i pacchetti ricevuti; (b) incorrere in un costo computazionale per la ricostruzione di un pacchetto per ogni insieme Q, con |Q| ≥ q.

9 _{Un’informazione aggiuntiva incapsulata, insieme al relativo simbolo, nei pacchetti prima di} essere inviati. Il witness è usato per assicurare l’autenticità del simbolo.

20

1.7 CECInA

L’algoritmo di codifica/decodifica proposto di seguito permette di mitigare gli attacchi DoS di un ricevente. In base al tipo d’attacco, consente inoltre di diminuire o la complessità d’elaborazione o la memorizzazione delle informazioni. In particolare, CECInA (Computationally Efficient Countermeasure for Injection Attacks) [6] è particolarmente efficiente quando è usato in combinazione con il Merkle tree Purgato (PMT), un’ottimizzazione del Merkle tree che ne permette di diminuire l’implicita ridondanza introdotta dalla sua rappresentazione.

Prima di introdurre la descrizione per la costruzione del Merkle tree, si darà qualche notazione preliminare.

Come nel caso di PRABS, le comunicazioni tra il mittente ed i destinatari non assumono nessun’ipotesi di sincronia.

Una funzione pseudo-casuale è un efficiente algoritmo che dato un seme di h bits, y, e un argomento x, ritorna una stringa di h bits denotata fy(x), tale che è impossibile distinguere il risultato di fy da quello di una accurata funzione casuale. Si assuma che H(•) sia una funzione pseudo-casuale, one-way e quindi difficile da invertire [7]. Per i nostri scopi, la funzione hash SHA-1 [8], dove h = 160, può essere considerata una buona sostituta di una funzione pseudo-casuale.

Per tollerare la perdita dei dati è previsto l’uso di IDA che, data un’informazione D di d bits, produce un insieme di n = q + r simboli, con la proprietà che D può essere ricostruita da un insieme qualsiasi di q simboli. Di seguito, senza perdita di generalità, si assuma che n = 2t _{con t ≥ 1.}

21 1.7.1 Il Merkle tree

Per ammortizzare la firma su un insieme n di pacchetti occorre uno schema che permetta di consegnare tutti i pacchetti e di verificarli efficientemente. Per fare ciò, il Merkle tree rappresenta un’allettante soluzione.

Il Merkle tree è un albero binario completo che mappa un insieme di nodi in un insieme di stringhe di grandezza fissa. Le foglie dell’albero contengono l’informazione (cioè gli n simboli), mentre il valore dei nodi interni (denotati con α(•)) è l’hash della concatenazione del valore dei suoi due figli. Per costruire il Merkle tree, il mittente considera come foglie gli n simboli e da questi costruisce l’albero in accordo con le seguenti regole:

• α(vi) = H(α(v2i+1)| α(v2i+2)) per i = 0,…, n-2; • α(vi) = H(Si–n +1) per i = n-1,….,2n-2,

dove | rappresenta la concatenazione di due stringhe e H(•) l’applicazione della funzione pseudo-casuale. I nodi sono numerati dalla radice verso il basso, da sinistra verso destra, come in Fig. 3.

22

Di seguito, ci si riferirà con il termine share per indicare uno degli n-1 nodi interni (cioè nodi senza foglie) dell’albero.

Per consegnare un simbolo, il mittente spedisce un pacchetto contenente un numero di sequenza, il simbolo, e tutte le informazioni necessarie (witness) affinché il destinatario possa verificare l’autenticità del pacchetto attraverso la radice del Merkle tree. Si chiamerà questo pacchetto, contenente log n nodi interni, augmented packet (AP). In riferimento all’albero di Fig. 3, gli augmented packet sono rappresentati nella colonna sinistra della tabella di Fig. 4.

Augmented packets Pruned packets

AP0 = {0, S0, v8, v4, v2} AP1 = {1, S1, v7, v4, v2} AP2 = {2, S2, v10, v3, v2} AP3 = {3, S3, v9, v3, v2} AP4 = {4, S4, v12, v6, v1} AP5 = {5, S5, v11, v6, v1} AP6 = {6, S6, v14, v5, v1} AP7 = {7, S7, v13, v5, v1} P0 = {0, S0, v8, v4, v2} P1 = {1, S1, v7} P2 = {2, S2, v10, v3} P3 = {3, S3, v9} P4 = {4, S4, v1, v12, v6} P5 = {5, S5, v11} P6 = {6, S6, v14, v5} P7 = {7, S7, v13}

Figura 4: Augmented e Pruned packets per il Merkle tree in Fig. 3.

Nell’esempio di Fig. 4, la procedura d’autenticazione è la seguente: si assuma che il destinatario abbia ricevuto e autenticato la radice v0 dell’albero. Per permettere l’autenticazione di un pacchetto, diciamo il pacchetto zero, il mittente invia AP0 = {0, S0, v8,v4, v2}. Il destinatario: (a) calcola il valore v0' = H(H(H(H(S0)|v8)|v4)|v2) (che è la radice dell’albero, se il pacchetto è legittimo); (b) controlla il valore v0' con il valore firmato, ricevuto e verificato, v0. Se il controllo ha successo, il pacchetto AP0 è autenticato, insieme al simbolo S0 e tutti i valori v2, v4, v8. Se il controllo fallisce allora il pacchetto viene scartato. Si noti che finché la radice v0 non è autenticata, gli augmented packets ricevuti non possono essere verificati.

23 1.7.2 PMT – Pruned Merkle tree

Nel seguito si diminuirà la ridondanza introdotta dagli augmented packets.

L’idea è questa: si assuma che non ci siano pacchetti persi; i nodi interni hanno bisogno di essere inviati una sola volta, in accordo con il protocollo che abilita il ricevente a ricostruire correttamente ed efficientemente il Merkle tree. Appena ricevuti tutti i pacchetti, infatti, il destinatario sarà in grado di ricostruire il Merkle tree e procedere con l’autenticazione. Questa è però un’ipotesi non realistica, per due ragioni: (a) l’attaccante ha la capacità di distruggere dei pacchetti; (b) il canale di comunicazione, per sua natura, può perdere dei pacchetti.

Per modellare la perdita di pacchetti introduciamo, quindi, il parametro z, che descrive il numero di pacchetti che si possono perdere durante le trasmissioni, mentre si assicura che almeno un pacchetto possa raggiungere la destinazione (quindi si avrà z = r + 1).

Si assegneranno i nodi del Merkle tree seguendo un modello leftmost. Dato uno share vi, indichiamo con Di (i ≥ 1) l’insieme di pacchetti Pj tale che Pj dovrebbe ospitare lo share vi in accordo con la rappresentazione del Merkle tree. Con riferimento alla Fig. 3, lo share v2 ha D2 = {P0, P1, P2, P3}. Da notare che se vi è al livello j, allora |Di| = 2t-j, con t l’altezza del Merkle tree.

Il mittente include un Merkle share vi nel pacchetto Pj in accordo con il metodo leftmost; dovranno valere entrambe le seguenti condizioni:

(a) Pj ∈ Di è il pacchetto che dovrebbe ospitare lo share nel suo AP;

(b) deve valere la disuguaglianza j – minI {Di} ≤ z, dove minI {Di} indica l’indice minimo dei pacchetti contenuti in Di.

La condizione (b) assicura che, con lo share vk ancora da assegnare, esso è affidato al pacchetto Pj solo se vk è stato già assegnato al pacchetto Pi, con i < j e Pi, Pj ∈ Dk.

La regola dell’assegnamento leftmost induce quello che chiameremo un Pruned Merkle tree (PMT) [6] e permette, anche in presenza di un pollution attack, di

24

ricostruire efficientemente l’insieme completo dei witness (Complete Witness Set – CWS) di ogni legittimo pacchetto.

Con questa costruzione si è diminuito il numero di shares replicati inviati nella rete: ogni share, infatti, necessario a η pacchetti per ricostruire il rispettivo CWS è stato replicato, nella rappresentazione PMT, in min {η, z} pacchetti. Inoltre, ogni nodo vj necessario in un pacchetto Pi per incrementare il suo CWS, è trasportato o dal pacchetto stesso o da esattamente z pacchetti di indice minore di i.

In [6] è anche dimostrato come nel sottoalbero di radice v1 ci sono esattamente z pacchetti che contengono il loro CWS: i primi z. Questa è una diretta conseguenza della costruzione del PMT con il metodo leftmost.

1.7.3 Firma auto-verificabile

È una tecnica che permette alla firma della radice del Merkle tree di essere auto-verificabile [6]. Quando il destinatario riceve un pacchetto firmato (Pscs) può decidere se è una firma legittima (che fornisce la corretta radice del Merkle tree) oppure no. Come algoritmo di crittografia può essere usato RSA.

Il mittente firma la radice v0 (di lunghezza h, dove h = |H(v1|v2)|) del Merkle tree, producendo una stringa Vs lunga k bits, mentre solo h bits sono significativi. Assumendo che 2h ≤ k, si può firmare la seguente stringa: (v0|v0), ottenendo Vz. La lunghezza di Vz è ancora di k bits. Si noti che l’applicazione dell’algoritmo di verifica della firma ha la stessa complessità sia che venga applicato su Vs che su Vz. Sia Vz' il risultato della verifica di Vz. Per Vz' è richiesto che valga anche la seguente uguaglianza: Vz'[1-h] = Vz'[h+1-2h], cioè i primi [1–h] bits sono uguali agli [h+1–2h] bits. Se l’uguaglianza è verificata si avranno due risultati: (1) si è calcolata la corretta radice v0 del Merkle tree; (2) la radice è stata autenticata con la sola verifica della firma.

25

Questa tecnica evita al mittente di inviare, oltre al messaggio firmato, il messaggio stesso, per l’eventuale confronto. Il ricevente, dal canto suo, eviterà di memorizzare pacchetti in più.

1.7.4 CECInA – Codifica e Decodifica

CECInA è basato sull’ammortamento della firma; in particolare, dato uno stream d’informazioni, questo è suddiviso in blocchi di dati e la firma è suddivisa tra tutti i blocchi. In seguito, un blocco D è codificato con un erasure code in un insieme di simboli S = {S0,…,Sn-1}, dove n = q+r, per tollerare la perdita d’informazioni durante la trasmissione.

Per ogni i ∈ [0, n-1] sia Wi la sequenza di witness assegnata al simbolo Si ottenuta usando la costruzione del PMT. Inoltre, sia v0 la radice del PMT costruito sull’insieme S, mentre v0' è la firma di v0|v0 che, come già si è discusso in precedenza, è auto-verificabile.

L’algoritmo di Codifica produce un insieme di n + r + 1 pacchetti P0,…,Pn+r. Per ogni i ∈ [0, n-1], il pacchetto Pi è Pi = <i, Si, Wi>, mentre per ogni j ∈ [n, n+r], il pacchetto Pj è Pj = < v0' >. In pratica, i primi n pacchetti (chiamati payload packets) contengono il simbolo ed i rispettivi witness, mentre gli ultimi r+1 (chiamati signature packets) contengono repliche della firma v0'. Lo schema dell’algoritmo di codifica è mostrato in Fig. 5.

26

Figura 5: Algoritmo di Codifica di CECInA.

L’algoritmo di decodifica fa uso della funzione Root(S, W) la quale, dato un simbolo S ed un CWS W per S, ritorna un valore v'. Quest’ultimo sarà successivamente confrontato con la firma ricevuta in precedenza ed, eventualmente, autenticato come la legittima radice v0. Il pacchetto che contiene sia il simbolo S che il CWS W sarà autenticato di conseguenza.

La funzione Verify(v') controlla l’autenticità della firma auto-verificabile v' contenuta in un signature packet; restituisce la coppia <b, v> dove b = True se il test ha successo, nel qual caso v è la radice del PMT calcolato dal mittente. Altrimenti restituirà b = False.

L’algoritmo di decodifica è eseguito dal destinatario ogni volta che riceve un nuovo pacchetto. L’autenticazione di un pacchetto implica l’autenticazione sia del simbolo che trasporta sia degli shares che contiene. Quest’ultimi sono inseriti in un insieme M, per essere utilizzati nell’aggiornamento di quei payload packets che non trasportano il CWS per il relativo simbolo da autenticare.

Il destinatario, dopo l’identificazione della corretta radice del PMT calcolato dal mittente, prenderà in considerazione prima i pacchetti con CWS e con numero di sequenza minore, propagando successivamente l’autenticazione anche agli altri pacchetti in arrivo.

27

Si osservi che, se fosse usato un metodo diverso dal leftmost per la costruzione dei pacchetti, si rischierebbe d’incorrere in addizionali costi computazionali per la verifica dei payload packets. S’ipotizzi, per esempio (in riferimento ai pacchetti di Fig. 4), che, usando un metodo di costruzione diverso, l’insieme dei witness che forma il CWS di P0 = {0, S0, v8, v4, v2} sia suddiviso su P0 e P1: P0 = {0, S0, v8, v4}, P1 = {1, S1, v2, v7}. Si assuma, adesso, che l’attaccante inietti Y = 2y invalidi payload packets della forma Pi0 = {0, Si0, vi8, vi4} e Pi1 = {1, Si1, vi2, vi7} per ogni i ∈ [1, y]. Il destinatario non può autenticare nessun pacchetto sino a quando non ha autenticato gli shares v1 e v2, i quali possono essere ottenuti solo dopo la corretta verifica di P0 e P1. Di conseguenza, per produrre il CWS per P0 (oppure per P1), il destinatario dovrebbe combinare gli shares contenuti in tutti i pacchetti {P0, P10,…, Py0} con gli shares contenuti nei pacchetti {P1, P11,…, Py1}. Nel caso peggiore questo controllo ha una complessità quadratica nel numero di pacchetti invalidi.

Quest’attacco non è possibile con la regola di costruzione leftmost poiché P0 contiene il suo CWS, ed ogni pacchetto confida, per il suo CWS, sui pacchetti con numero di sequenza minore.

L’algoritmo presentato evita, grazie al concetto della firma auto-verificabile, che un destinatario sia bersaglio, allo stesso tempo, di un DoS sulle capacità di computazione e memorizzazione [6].

Nel capitolo 3 si introdurrà un meccanismo di trasmissione dei dati basato su più canali di comunicazione (Multi-Channel). Si descriverà il modello sia dal punto di vista del destinatario sia da quello di un eventuale attaccante, definendone le regole e i limiti che ne permettono un uso ottimo.