3.1 Comunicazione in Multi-Channel Multi-channel C 3

49

C

3

Multi-channel

Si presenterà il modello di comunicazione su canali multipli nella trasmissione multicast, in un ambiente ostile per i riceventi. Dopo la presentazione del problema e delle relative soluzioni, sarà fatta un’analisi dell’algoritmo in termini di complessità computazionale, confrontando i risultati con quelli di PRABS e CECInA.

3.1 Comunicazione in Multi-Channel

Siano p il numero di canali di comunicazione c1, …,cp utilizzati dal mittente per

inviare i pacchetti al destinatario. Di questi, un numero limitato l < p possono essere attaccati da un avversario. Sia, inoltre, m il numero dei canali sicuri per il destinatario tali che p = l + m. Sia n il numero dei simboli prodotti dalla codifica IDA del dato originale, inviati in n pacchetti costruiti attraverso il PMTR, e q il numero di pacchetti minimo necessario per la ricostruzione del dato, tale che n =

q + r. Di conseguenza, r misura la ridondanza dell’informazione.

Nel modello presentato, un avversario non è lasciato completamente libero di agire; se lo fosse, potrebbe eliminare tutti i messaggi, dai canali che controlla, prima che questi raggiungano la destinazione, rendendo invano ogni sforzo per ricostruire il dato originale.

Il mittente assocerà ad ogni canale un processo, per permettere, in questo modo, l’invio contemporaneo di p pacchetti: uno per canale.

50

In generale un avversario può osservare, modificare, ritardare ed eliminare dei pacchetti. Conosce il numero di canali in uso e ne controlla una parte. Può stare in ascolto di tutti i canali, anche se poi ha la capacità di attaccarne solo un numero limitato.

In Fig. 18 è mostrato un esempio, semplificativo, di quello che può accadere durante un attacco, dal punto di vista del ricevente, sia nel caso con un unico canale che nel multi-channel, in cui l’attaccante controlla un solo canale (il terzo). Nel seguito ci si concentrerà soprattutto sul pollution attack, nel quale un avversario può inquinare il messaggio inviato dal mittente, iniettando simboli corrotti nei canali che è riuscito a controllare.

51

3.2 Indizi d’attacco

A livello di trasporto, un pacchetto può essere visto come un record di campi diversi, ognuno con un tipo definito (int, string, char, …). Quando un pacchetto è ricevuto dal destinatario, sono eseguiti immediatamente dei controlli sul formato: questo ne determina la validità o invalidità (nel qual caso sarebbe immediatamente scartato). Per pacchetto falsificato (o corrotto) s’intende un pacchetto che supera i controlli precedenti, che ha i campi del tipo previsto ma con valori sbagliati, nel senso che il simbolo o gli shares contenuti nel pacchetto non verificano il test di autenticità. Nel caso contrario il pacchetto è autentico (o

legittimo).

Nel caso che la comunicazione fosse perfettamente sincronizzata, il destinatario verificherebbe, prima di tutto, se la condizione di temporizzazione è stata rispettata; se così non fosse, il pacchetto ricevuto “fuori tempo massimo” sarebbe da considerarsi perso e quindi non verrebbe preso in considerazione per l’autenticazione.

Nel caso di comunicazioni parzialmente sincronizzate, il destinatario dovrà verificare che siano stati rispettati i limiti temporali, introdotti all’inizio della sessione con il mittente, come ad esempio la sincronizzazione dei clock locali o il limite di tempo nella consegna dei messaggi; anche in questo caso, un pacchetto che non rispetta tali limiti, sarebbe da considerarsi corrotto.

Nell’ipotesi che la trasmissione dei pacchetti non avesse nessun limite temporale, fosse cioè asincrona, competerebbe esclusivamente al destinatario decidere quali canali siano da considerarsi attaccati. Questa decisione sarà presa dopo il riconoscimento d’espliciti indizi d’attacco:

1. Il destinatario riceve un signature o un payload packet falsificato;

2. Il destinatario riceve un payload packet da un canale diverso da quello previsto dallo scheduling;

52

3. Il destinatario riceve più pacchetti, differenti ma con il medesimo indice, dallo stesso canale.

Gli indizi d’attacco sono validi pure nel caso di trasmissioni sincronizzate, oltre alle condizioni temporali.

Per un canale è previsto, dallo scheduling, che si ricevano n/p pacchetti16. È ovvio che, se un canale subisce un attacco DoS, il numero dei pacchetti ricevuti cresce rispetto alle previsioni.

Un attacco DoS sulla memorizzazione, in cui un attaccante invierà falsi payload packets, avrà forti ripercussioni sul traffico in real-time di streaming audio/video. L’introduzione di pacchetti ridondanti, per fare fronte ad eventuali perdite, incrementa il ritardo di riproduzione dell’informazione, poiché il destinatario dovrà aspettare di ricevere l’intero gruppo di pacchetti prima di potere cominciare la riproduzione. Se a questo si aggiunge il tempo necessario per tentare di autenticare e quindi scoprire i pacchetti falsificati, è chiaro che, nel caso peggiore, il risultato della riproduzione del traffico real-time sarà incomprensibile, o quasi, al destinatario.

3.3 Modello di trasmissione

Si definirà, nel seguito, un modello che permetta di stabilire esplicitamente i limiti che sono necessari per descrivere lo scambio di messaggi tra mittente e destinatari che, per ipotesi, non presuppone nessun tipo di sincronia.

Il parametro di ridondanza r è scelto dal mittente, al momento della codifica IDA, in base alle previsioni di perdita o danneggiamento dei pacchetti dovuto al mezzo di comunicazione, o in base alla stima degli eventuali pacchetti che un attaccante ha la capacità di eliminare. Si può però ipotizzare, senza perdita di generalità, che

16 _{Sotto l’ipotesi che il numero dei pacchetti da inviare è distribuito equamente sui canali di} comunicazione.

53

il mezzo di comunicazione non perda nessun messaggio. Il danneggiamento o lo smarrimento dei pacchetti può, infatti, essere inglobato nel caso in cui sia l’attaccante a provocarli; quest’ultimo potrebbe, infatti, oltre ad eliminare pacchetti dai canali, danneggiarli e renderli inutilizzabili per il destinatario. Quest’ultimo, per ipotesi, conosce il numero di pacchetti totali validi inviati dalla fonte, nonché la politica di scheduling. Il mittente non può individuare quali canali siano sotto il controllo di un attaccante, mentre il ricevente ha le capacità per identificarli, come si vedrà, attraverso degli espliciti indizi d’attacco.

Come discusso in precedenza, il servizio best-effort, offerto dal protocollo IP, non offre garanzie sulla consegna e sull’ordine d’arrivo dei pacchetti immessi nella rete. Questo, unitamente alle premesse considerazioni, induce ad esaminare un modello di trasmissione che tenga conto della presenza dell’attaccante, definendone i suoi limiti.

Il mittente si preoccuperà di spedire i pacchetti nei rispettivi canali, rispettando un preciso scheduling. In base al massimo ritardo di rete λ, i pacchetti inviati saranno ricevuti dal destinatario con una periodicità temporale limitata superiormente da λ. Tale valore dipende dal mezzo di comunicazione usato e, normalmente, il tempo di trasmissione tra due nodi, direttamente collegati, è conosciuto. Tra due pacchetti legittimi, l’attaccante ha la capacità di inviare al destinatario un numero di pacchetti invalidi katt; con l il numero dei canali attaccati, il traffico immesso

illecitamente sarà katt ·l/p ·n. Si definirà katt la capacità d’attacco dell’avversario.

Secondo questo valore, ed al numero di canali in cui l’avversario riesce ad infiltrarsi, l’attacco avrà una maggiore o minore intensità. Il ritardo di rete λ può essere espresso, di conseguenza, attraverso il parametro katt: un suo maggior

valore indicherà un più alto ritardo di rete.

Si può riassumere il modello di trasmissione nei seguenti punti:

• le comunicazioni tra il mittente e i destinatari seguono un modello asincrono;

54

• l’attaccante ha la capacità di danneggiare o distruggere al massimo r pacchetti, con r il numero di pacchetti ridondanti prodotti dal mittente in fase di codifica del dato originale con un erasure code;

• l’attaccante ha la capacità di iniettare, in ogni canale che è riuscito a controllare, katt pacchetti invalidi tra due pacchetti validi.

3.4 Casi d’attacco

L’avversario, per ipotesi, ha la capacità di eliminare al massimo r (cioè z-1) pacchetti validi dai canali che userà per l’attacco.

Si definiscono canali sicuri (cs), i canali in cui non è presente nessun indizio

d’attacco. Se il rapporto tra il numero di canali sicuri e il numero di quelli totali cs/p è maggiore o uguale a q/n, allora si avrà la certezza che sono necessari solo i

canali sicuri per la ricostruzione del dato originale. Si avrà, infatti, da cs/p ≥ q/n che (cs/p)·n ≥ q, a dimostrazione che dai canali sicuri arriverà il numero di simboli necessari per il ripristino dal dato.

Sotto tale condizione, il destinatario potrebbe essere portato ad eliminare tutti i payload packets in arrivo dai canali attaccati, annullando all’origine gli effetti di un attacco DoS. S’immagini, a tale proposito, una situazione in cui l’avversario riesce ad ottenere il controllo di l canali, con (p-l)/p < q/n; potrebbe inviare pacchetti corrotti su l' < l canali, ed aspettare un certo tempo t prima di inviare pacchetti corrotti anche sugli altri l – l' canali, creando una situazione iniziale in cui (p-l')/p ≥ q/n; il destinatario, dopo la verifica di quest’ultima condizione, eliminerà tutto il traffico proveniente dagli l' canali che subiscono l’attacco (compreso, quindi, un numero h di pacchetti legittimi), sino a quando non noterà indizi d’attacco su ulteriori l – l' canali. Si potrebbe verificare una situazione in cui n-h-r < q (tenendo conto degli r pacchetti che l’attaccante ha la possibilità di eliminare), che renderà impossibile la ricostruzione del dato originale. Il destinatario, infatti, si è reso involontariamente complice dell’avversario,

55

aiutandolo a superare il limite di r pacchetti eliminabili. Ecco perché non è conveniente al destinatario cancellare tutto il traffico proveniente da un canale attaccato.

Un pollution attack ha, fondamentalmente, due obiettivi diversi: (a) massimizzare i costi computazionali del destinatario; (b) saturare lo spazio di memorizzazione del destinatario.

Nel caso (a) l’attaccante dovrà iniettare solo signature packets falsi17 (signature flooding), la cui verifica, da parte del ricevente, richiede un tempo non trascurabile. Si è supposto, precedentemente, che l’attaccante non controlla tutti i canali. Di conseguenza il destinatario si troverà a verificare, nel peggiore dei casi, un numero di firme false proporzionate al numero di canali attaccati, prima di ricevere il corretto signature packet da un canale sicuro18. Nell’ipotesi che non ci siano ritardi di trasmissione dei pacchetti, il ricevente controllerà, alla peggio, (p–

cs)·katt firme corrotte19. Tutte le firme ricevute da quel momento in poi saranno

cancellate, senza essere nemmeno verificate. Si può, però, ottimizzare il controllo partendo dall’ipotesi, fatta in precedenza, che non tutti i canali sono attaccati: il destinatario, alla ricezione di un signature packet falsificato, eliminerà tutte le altre firme provenienti da quel canale, senza controllarle, poiché sa che riceverà sicuramente un signature packet corretto da un canale sicuro. In questa situazione, il numero di false firme controllate sarà, al massimo, p–cs.

È evidente che un attacco di questo tipo non otterrebbe successo, poiché il numero di firme false che il destinatario dovrà verificare è troppo basso perché provochi un DoS sulla macchina del ricevente.

S’ipotizzi che il modello di trasmissione preveda la perdita dei pacchetti per cause imputabili al mezzo di comunicazione. In questo caso il numero di signature packets immessi nella rete dovrà essere r+1. Nella situazione peggiore, tutte le

17 _{Questo è vero solo per CECInA, non per PRABS [2].}

18 _{Una copia del signature packet è inviata in ogni canale, indipendentemente dalla ridondanza r.} 19 _{Nel frattempo il destinatario avrà ricevuto almeno un signature packet legittimo da un canale} sicuro, rendendo superflua la verifica delle firme ricevute successivamente.

56

firme sui canali saranno o perse o distrutte dall’avversario, il quale si preoccuperà di ritardare la consegna dell’ultimo signature packet al ricevente. Quest’ultimo dovrà controllare tutte le firme iniettate nel frattempo dall’attaccante, memorizzando tutti i payload packets in arrivo (poiché non potrà verificarli sino alla ricezione della firma legittima).

Il costo per la verifica dei signature packets può essere espresso in modo probabilistico. Si assuma che la probabilità di perdere un pacchetto per cause imputabili al mezzo di comunicazione sia uguale alla probabilità che ha lo stesso pacchetto di essere eliminato da un avversario, cioè r/(n+r+1). La probabilità di non ricevere una firma da un canale sicuro è Psig(cs) = (r/(n+r+1))cs. Siano F il numero di signature packets invalidi ricevuti dal destinatario, mentre l = p – cs indica il numero di canali che subiscono un attacco DoS. Si può calcolare il costo medio per la verifica delle firme nel seguente modo:

Psig(cs)·(Costo Verifica Sign.)·(F+1) + (1–Psig(cs))·(Costo Verifica Sign.)·(l+1), dove il primo termine della somma indica il costo per la verifica delle firme di tutti i signature packets invalidi in arrivo nella probabilità che non si ricevano signature packets dai canali sicuri, mentre il secondo termine indica il costo per la verifica delle firme nella probabilità che si riceva almeno un signature packet da un canale sicuro.

Nel caso (b), l’attaccante tenterà di saturare lo spazio di memorizzazione del ricevente, iniettando solo payload packets falsi. Il destinatario controllerà tutti i pacchetti ricevuti dai canali, nel tentativo di riunire il numero di simboli necessari per ricostruire il dato inviato dal mittente. Ovviamente, i pacchetti invalidi o falsi non passeranno l’autenticazione e saranno eliminati. I metodi di controllo OHA e LRA permettono di effettuare la verifica dei payload packets senza il bisogno di ricostruire il rispettivo CWS, previa autenticazione della radice v0 del Merkle tree; questo garantisce una più veloce autenticazione e, di conseguenza, una minore memorizzazione dei pacchetti, mitigando l’attacco DoS perpetrato ai danni del

57

destinatario. Quest’ultimo avrà modo, attraverso gli indizi d’attacco, di capire quali canali siano insicuri. Ciò determinerà il valore del rapporto cs/p, che darà un’idea di quanto velocemente il destinatario raggiungerà la quota di q simboli, e quindi, dello spazio di memoria occupato:

1. Nel caso che i soli pacchetti provenienti dai canali sicuri siano sufficienti per ricostruire l’informazione inviata dal mittente (cs/p ≥ q/n), la ricezione e memorizzazione dei pacchetti sarà interrotta quando il destinatario avrà verificato i payload packets provenienti dai canali sicuri, che saranno minori o uguali20 a (cs/p)·n. Di conseguenza, il numero dei pacchetti falsi, iniettati nel frattempo dall’avversario, sarà al limite (p-cs)·n/p·katt. La

maggior parte di questi sarà eliminata immediatamente, a causa della precedente autenticazione dei relativi pacchetti legittimi, oppure dalla scoperta, dopo un tentativo d’autenticazione, che i pacchetti sono falsificati.

2. Nel caso che i payload packets provenienti dai soli canali sicuri non sono sufficienti per riunire almeno q simboli legittimi (cs/p < q/n), il numero di pacchetti corrotti memorizzati e, di conseguenza, controllati dal destinatario, saranno maggiori rispetto al caso precedente. Il caso peggiore occorre qualora l’attaccante abbia la possibilità di eliminare r payload packets legittimi dai canali sotto controllo; il ricevente sarebbe costretto a controllare tutti i pacchetti in arrivo, sino a quando l’ultimo payload packet legittimo non è consegnato. Il totale dei pacchetti memorizzati, in questo caso, sarà cs/p·n + (katt+1)·[((p-cs)/p)·n] – r.

58

3.5 Scheduling dei pacchetti

Occorrono, prima di definire un adeguato scheduling, delle premesse sui tipi di pacchetti e sul controllo che il destinatario andrà ad effettuare su di essi.

Non appena un pacchetto con indice i è autenticato dal destinatario, tutti quelli ricevuti successivamente, con lo stesso indice, saranno eliminati senza essere nemmeno controllati. La stessa sorte è riservata anche ai signature packets, dal momento in cui ne viene autenticato uno.

L’obiettivo del destinatario è di autenticare un numero q di simboli necessari per ricostruire il dato originale, memorizzando, e quindi controllando, il minor numero possibile di payload packets corrotti. Si può ottenere questo risultato velocizzando, per quanto possibile, l’autenticazione dei pacchetti validi. I metodi d’autenticazione OHA e LRA permettono d’ottenere un sensibile risparmio computazionale per il destinatario e una più veloce autenticazione dei simboli inclusi nei payload packets.

L’attaccante tenterà di eliminare il maggior numero possibile di pacchetti dai canali che è riuscito a controllare; con le ipotesi e i limiti fissatigli precedentemente, almeno q pacchetti legittimi saranno ricevuti dal destinatario. Si dovranno, inoltre, evitare condizioni d’attesa eccessiva per la verifica di un payload packet Pi: la miglior situazione si ha quando ogni Pi può essere

immediatamente autenticato dal destinatario, senza il bisogno di dovere attendere l’arrivo e l’autenticazione di quei payload packets, con indici minore di i, che trasportano con sé gli shares necessari per la verifica di Si. Lo scheduling

cercherà, per quanto possibile, di evitare il verificarsi di tali situazioni svantaggiose per il destinatario.

Il mittente non sa quali canali saranno bersaglio dell’attaccante; di conseguenza, dovrà favorire “l’autenticazione autonoma” dei pacchetti di uno stesso canale. Questo significa che, dato un payload packet Pi, tutti gli shares ad esso necessari per la verifica del simbolo Si sono stati precedentemente inviati nello stesso

59

canale, attraverso i pacchetti, necessari per Pi, di indice minore di i. Si eviterà, in questo modo, che un payload packet legittimo, inviato in un canale controllato dall’attaccante e quindi a rischio d’eliminazione e ritardi, possa essere causa d’attesa per la verifica di un pacchetto inviato su un canale diverso dal precedente. Considerando che i payload packets possono essere controllati e verificati solo dopo che il destinatario ha ricevuto un signature packet legittimo, il mittente invierà prima di tutto i signature packets, uno per canale (con la speranza che i pacchetti non incorrano in grossi ritardi di rete), poiché, in questo modo, darà al destinatario la possibilità di un’autenticazione immediata dei payload packets spediti, di conseguenza, subito dopo i signature packets. Inoltre, sarebbe preferibile che almeno uno dei z CWS packets raggiunga il destinatario da uno dei canali non controllati dall’attaccante21, in modo che la sua autenticazione non sia ritardata dal controllo dei pacchetti invalidi o falsificati immessi dall’avversario; occorre, a tal fine, fissare il numero dei canali p ≤ z: condizione, questa, che assicurerà l’arrivo di un CWS packet da uno dei canali sicuri. Da notare che sotto tale condizione la procedura d’autenticazione LRA, dopo l’arrivo di un CWS packet, è sempre applicabile al resto dei pacchetti.

Uno scheduling casuale dei pacchetti è legato alla scelta, altrettanto casuale (dal punto di vista del ricevente), dei canali attaccati da un avversario. Questo tipo di scheduling si dimostra conveniente solo in modo probabilistico. Si dovrà, quindi, cercare di rendere lo scheduling il più indipendente possibile dalla scelta, da parte dell’avversario, dei canali da attaccare, in modo che risulti soddisfacente per ogni insieme di canali attaccati.

Il metodo applicato per la riduzione del PMT suggerisce il tipo di scheduling conveniente per l’invio dei payload packets. La regola base della procedura di sfoltimento impone di lasciare intatti i primi z CWS packets, poiché questi pacchetti permettono di arrivare immediatamente all’autenticazione della radice v0

21 _{Un payload packet con CWS è importante per l’autenticazione dei restanti pacchetti in tempo} lineare, soprattutto dopo l’introduzione del PMTR.

60

del Merkle tree e, quindi, all’applicazione di LRA ai restanti pacchetti (che ne velocizzerà la loro autenticazione). Di conseguenza i CWS packets22, inviati dal mittente, dovranno essere distribuiti in modo che ne sia presente almeno uno per canale (nel caso che p ≤ z). Questo concetto può essere generalizzato; basti notare che il lemma 1 si basa su una condizione importante, che assicura l’autenticazione di tutti i payload packets arrivati a destinazione: i sottoalberi d’altezza l del Merkle tree, presi in considerazione dal mittente per ottenere il PMTR, devono rispettare la condizione z < 2l. Si prenda, per i nostri fini, un valore k, il più basso possibile, che assicuri il rispetto della condizione stessa: dovrà valere, cioè, z < 2k e z ≥ 2k-1. Da questo momento i payload packets saranno presi in esame a gruppi di 2k. Considerando che i payload packets legittimi sono n (cioè 2log n), i gruppi sono costruiti nel seguente modo (con K = 2k):

Gi = {PK· i, PK· i+1,…, PK· i+(K-1)} per i = 0,…,2log n – k.

I gruppi formatisi sono caratterizzati dalle seguenti proprietà:

a) il numero dei gruppi è uguale al numero di sottoalberi d’altezza k del Merkle tree;

b) ogni gruppo contiene tutti i pacchetti relativi ad uno stesso sottoalbero; c) i primi z pacchetti di ogni gruppo (sottoalbero) portano con sé l’insieme

completo dei witness rispetto al relativo sottoalbero (questa è una diretta conseguenza dello sfoltimento del PMT).

L’idea di formare dei gruppi ha il pregio di evidenziare le proprietà simili e ripetute per ogni insieme di pacchetti. Il problema di come immettere gli n payload packets nella rete è quindi trasformato nel problema, più semplice e intuitivo, di come suddividere i 2k pacchetti tra i p canali di comunicazione.

In riferimento alla Fig. 19, nella quale si hanno n = 16 payload packets (di cui z = 3 ridondanti), si sono formati 4 gruppi di 4 (22) pacchetti ciascuno, poiché il valore più basso che soddisfa la disequazione z < 2k è k = 2.

22 _{Dopo la riduzione del PMT, i CWS packets saranno P}

61

Figura 19: Merkle tree per n = 16 payload packets, di cui z = 3 ridondanti, divisi in 4 gruppi.

P0 = {0, S0, v16, v8, v4, v2} P1 = {1, S1, v15, v8, v4, v2} P2 = {2, S2, v18, v7, v4, v2} P3 = {3, S3, v17} P4 = {4, S4, v20, v10} P5 = {5, S5, v19, v10} P6 = {6, S6, v22, v9} P7 = {7, S7, v21} P8 = {8, S8, v24, v12, v6} P9 = {9, S9, v23, v12, v6} P10 = {10, S10, v26, v11, v6} P11 = {11, S11, v25} P12 = {12, S12, v28, v14} P13 = {13, S13, v27, v14} P14 = {14, S14, v30, v13} P15 = {15, S15, v29}

Figura 20: Pruned Packets Sfoltiti per il Merkle tree in Fig. 19, con z = 3.

Si noti (tabella di Fig. 20) come i primi 3 pacchetti (sottolineati) di ogni gruppo abbiano l’insieme completo dei witness rispetto ai relativi sottoalberi di radice v3,

v4, v5 e v6. Analizzando il gruppo G2 ci si rende conto di come il quarto (e ultimo) payload packet P11 abbia bisogno di uno qualsiasi dei primi tre pacchetti dello stesso insieme per la sua autenticazione23; poiché il numero di pacchetti

62

ridondanti è 3, si perderanno, per ipotesi, al massimo 2 payload packets dei 3 necessari a P11, che potrà essere di conseguenza verificato senza problemi. Lo stesso ragionamento è valido per i payload packets degli altri gruppi, e ciò implica che le regole di scheduling applicate a G2 valgono anche per i pacchetti degli altri gruppi.

La linea guida nell’assegnazione dei payload packets ai canali dovrà essere, fermo restando l’assegnazione dei CWS packets d’ogni gruppo a diversi canali, quella di inviare, per quanto possibile, i pacchetti contigui sullo stesso canale, per una principale ragione: uno dei due pacchetti in questione può sfruttare l’autenticazione dell’altro per essere verificato con il metodo OHA, più veloce e computazionalmente migliore. Le due regole principali dello scheduling si possono riassumere così:

1. i CWS packets d’ogni gruppo (cioè i primi z payload packets d’ogni gruppo) devono essere inviati su canali diversi;

2. dopo l’invio dei primi z pacchetti d’ogni gruppo, i restanti saranno distribuiti assegnandoli ai canali dove è presente il rispettivo pacchetto contiguo.

Inoltre, la distribuzione dei pacchetti sui canali dovrà essere fatta cercando di assicurare una ripartizione più equa possibile degli n payload packets. Il motivo può essere spiegato ricorrendo ad un semplice esempio. Si supponga che il mittente debba spedire 32 payload packets su 4 canali, suddivisi nel seguente modo: 12 pacchetti sul primo canale, 6 sul secondo, 7 sul terzo e quarto canale. Se l’attaccante riuscisse ad infiltrarsi nel primo e secondo canale, inietterebbe in questi dei falsi pacchetti, ritardando l’autenticazione, da parte del destinatario, di 20 dei 32 payload packets legittimi, cioè il 62% degli n pacchetti. Questa situazione è favorevole all’attaccante, poiché gli darebbe il tempo di iniettare una maggiore quantità di pacchetti corrotti, aumentando le possibilità di successo di un attacco DoS. Analogamente, se l’attaccante controllasse il secondo e terzo canale, la situazione che si creerebbe sarebbe favorevole al destinatario. In

63

generale, per evitare il verificarsi della situazione peggiore, conviene non creare squilibri nella ripartizione dei pacchetti tra i canali.

Formulando delle ipotesi sul numero dei canali, si possono distinguere le seguenti situazioni:

1. Il numero di canali è minore dei pacchetti ridondanti (p < z): i primi z pacchetti d’ogni gruppo andranno distribuiti almeno uno per canale, cercando di inviare sullo stesso i payload packets contigui;

2. Il numero di canali è maggiore dei pacchetti ridondanti (p > z): i primi z pacchetti d’ogni gruppo andranno distribuiti su canali diversi;

3. Il numero di canali è uguale al numero dei pacchetti ridondanti (p = z): i primi z pacchetti d’ogni gruppo andranno distribuiti esattamente uno per canale.

I restanti 2k – z payload packets d’ogni gruppo saranno assegnati, mano a mano, ai canali con minore numero di pacchetti affidatogli sino a quel momento, tenendo presente che i pacchetti contigui dovranno essere consegnati allo stesso canale. Uno scheduling adeguato per i pacchetti di Fig. 20, nel caso di 2, 3 e 4 canali di comunicazione, è il seguente:

Da notare come i primi z pacchetti d’ogni gruppo stiano su canali diversi (tranne, ovviamente, nel caso di due canali), mentre i payload packets contigui sono affidati, quando possibile, allo stesso canale.

64

La situazione in cui z < p è la più sfavorevole per il destinatario; è in queste condizioni che può verificarsi il caso peggiore, in cui l’avversario sferra l’attacco contro tutti i canali che trasportano i CWS packets. Quest’ultimi saranno ritardati dall’avversario, obbligando il ricevente a memorizzare tutti i pacchetti in arrivo (legittimi e falsificati) sino alla ricezione di un CWS packet. Il ricevente, infatti, dopo la verifica di un legittimo signature packet, cercherà di verificare per prima i CWS packets, propagando poi l’autenticazione agli altri payload packets.

Sarà presentato, di seguito, l’algoritmo che descrive lo scheduling adottato dal mittente, sotto forma di pseudo-codice:

Procedure SCHEDULING

p = numero dei canali di comunicazione;

I0,…,Ip-1: p insiemi che conterranno temporaneamente i pacchetti;

k = minimo intero tale che 2k _{> z;}

Si formano gruppi Gi di K=2k pacchetti, con i ∈ [0,…,2log n – k];

for (i=0; i < 2log n – k_{; i++) {}

// Si considerano i K pacchetti del gruppo Gi = {PK· i, PK· i+1,…, PK· i+(K-1)};

// Si assegnano i primi z CWS packets d’ogni gruppo agli insiemi

if (p≥z) { // i primi z pacchetti di Gi sono minori dei p canali

j=0;

while ( j≤z-1 ) { // si assegna ogni pacchetto con CWS ad un

insieme PK· i+ j Æ Ij; j++;

} }

65

j=0; l=0;

while ( (p-j<z-2j) and (j<p) ) {

// si assegnano i pacchetti contigui allo stesso insieme, sino a quando

è possibile, in modo da avere almeno un CWS packet per insieme PK· i+ l Æ Ij; l++;

PK· i+ l Æ Ij; l++;

j++; }

if (j=p) {

// i p canali contengono una coppia di CWS packets contigui

ciascuno; si assegnano i restanti z-l pacchetti ripartendo dal primo insieme

j=0;

while (z-l>0 ) {

// l è relativo all’indice del prossimo pacchetto da assegnare

PK· i+ l Æ Ij; l++;

// i CWS packets contigui sullo stesso canale if (z-l>0 ) P_{K· i+ l} Æ Ij; l++;

j++ (modulo z); }

} else {

// si assegnano i restanti z - l pacchetti con CWS ai restanti z - l

insiemi

while (z-l>0 ) {

66 }

} }

if (z = 2k_{) RETURN;}

// Si assegnano i restanti K-z pacchetti {PK· i+z-1,…, PK· i+(K-1)}= Gi\z agli

insiemi; i pacchetti contigui sono associati ad uno stesso insieme

if (K·i+z-1) è dispari {

PK· i+z-1 Æ Id tale che PK· i+z- 2 ∈ Id;

}

// la precedente condizione assicura che rimangono un numero pari di

pacchetti dell’insieme Gi\z da assegnare agli insiemi

while (esiste una coppia (Pw,Pw+1) ∈ Gi\z da assegnare ) {

si sceglie It ∈ {I0,…,Ip-1} tale che |It|≤|Iu| per ogni u ∈

{0,...,p-1}\t

(Pw,Pw+1) Æ It;

}

Gli insiemi {I0,…,Ip-1} sono associati ai canali {c0,…,cp-1}: ai canali con

minore numero di pacchetti affidati sino a questo momento sono associati i pacchetti dell’insieme con cardinalità maggiore.

Ij Æ ch con |Ij|≥|Iu| per ogni u ∈ {0,...,p-1}\j e

con |ch|≤|cf| per ogni f ∈ {0,...,p-1}\h;

Si procede via via, con questa politica d’assegnamento, ad attribuire tutti i pacchetti nei canali, sino allo svuotamento di tutti gli insiemi.

// Sono svuotate le strutture dati usate per un gruppo di pacchetti }

67

Di seguito si assumerà, per semplicità, che il numero di payload packets inviati per canale sia n/p, ipotesi del tutto realistica se si tiene conto che i canali di comunicazione hanno pari probabilità di essere presi di mira dall’attaccante.

3.6 Analisi e Complessità

L’algoritmo CECInA riadattato per il multi-channel (che utilizza lo scheduling descritto in precedenza) e che fa uso della costruzione PMTR, di OHA e LRA per autenticare i pacchetti, sarà chiamato CECInA M-C.

La complessità di CECInA M-C è calcolata sulla base dell’implementazione di CECInA [6], tenendo presente che la verifica dei payload packets sarà fatta con i metodi OHA e LRA piuttosto che con la funzione Root.

Si confronterà CECInA M-C sia con CECInA che con PRABS, in termini di computazioni richieste, mettendo in risalto le differenze che caratterizzano le implementazioni degli algoritmi.

La tabella 1 introduce la complessità delle operazioni di base che implementano gli algoritmi di seguito analizzati. In particolare, si focalizza l’attenzione sul costo di IDA [5], della funzione hash (come MD5 [19]) e sul costo per la ricostruzione della radice del Merkle tree [17]. Quest’ultimo costo, con l’applicazione simultanea di OHA e LRA per la verifica dei pacchetti, si riduce in quello di Merkle tree Reduced, come vedremo. Si assuma che si usino hash di h bits e che il dato D sia di d bits, codificato con IDA di parametri n e r in simboli di d/n bits.

CODING DECODING

IDA O(d) O(d(log (n-r) + r))

HASH (H) O(d/n) O(2h/2)

Merkle tree O(H (n log n)) = O(d log n) O(H (n log n)) = O(d log n) M. t. Reduced O(Hash (n log n)) O(Hash (n/2 (log n)/2))

68

La tabella 2 descrive i costi computazionali richiesti da CECInA [6], PRABS [2] e CECInA M-C, in accordo con i costi delle singole operazioni derivate prima. Si assuma che la fase di decodifica usi firme di k bits; inoltre, sia N il numero di pacchetti (legittimi e falsificati) ricevuti dal destinatario, di cui F sono signature packets invalidi e Y sono payload packets falsificati (N = F + Y + n).

Si ricorda che l è il numero di canali (sui p totali) che subiscono l’attacco da parte di un avversario, cioè l = p – cs, e che il costo medio di LRA è C( (log n)/2 ) =

O(d/n + h·(log n)/2), mentre quello di OHA è O(d/n).

COMPLESSITÀ COMPUTAZIONALE

PRABS [2] O( (N–r)(d/n + h log n) + ((N–n/n–r)+1) d(log(n–r)+r) + (N/n–r)k2 ₎

CECInA [6] O( Fk2 _{+ (N–F–r)(d/n + h log n) + d(log(n–r)+1) )}

CECInA M-C O( (l+1)k2 _{+ ((N–F–r)/2)(d/n + C((log n)/2)) + d log (n-r) + dr )}

Tabella 2: Complessità computazionale di PRABS, CECInA, CECInA M-C.

Il numero di pacchetti falsificati iniettati dall’attaccante è, al massimo, N' =

l/p·n·katt, con katt la capacità d’attacco dell’avversario. Di conseguenza, la

complessità di CECInA M-C può essere rivista in questi termini, ottenendo la seguente formula:

O( (l+1)k2 + ((N'+n–r)/2)(d/n + C((log n)/2)) + d log (n-r) + dr ).

In tabella 3 sono riportate le operazioni logiche richieste da CECInA M-C, PRABS e CECInA. In particolare, per PRABS il ricevente deve calcolare, per ogni payload packet in arrivo, la corrispondente radice del Merkle tree, che richiede log n operazioni. Successivamente applica l’algoritmo di decodifica IDA a questi pacchetti, verificandone, alla fine, la firma.

Per CECInA, il ricevente controlla prima la firma auto-verificabile; nel caso peggiore questo richiede la verifica di tutti i signature packets invalidi iniettati

69

dall’attaccante. Dopodiché il ricevente verifica il pacchetto che trasporta il suo CWS, propagando la sua autenticazione agli altri payload packets.

Il numero d’operazioni richieste da CECInA M-C è inferiore a quelle di CECInA per due principali ragioni: (a) il numero di firme verificate scende drasticamente, come visto nel paragrafo 3.4; (b) i metodi OHA e LRA permettono di risparmiare circa la metà dei calcoli della funzione hash rispetto all’applicazione di Root [6].

OPERAZIONI LOGICHE

PRABS [2] _{N (log n) Hash + ⎣(N/(n – r))⎦ IDA + ⎣(N/(n – r))⎦ Sig. ver.} CECInA [6] (F+1) Sign. ver. + (Y+n) (log n) Hash + IDA CECInA M-C (l+1) Sign. Ver. + (Y+n)/2 (log n)/2 Hash + IDA

Tabella 3: Costo operazioni logiche di PRABS, CECInA e CECInA M-C.

In [21] sono stati eseguiti dei test su un Athlon XP 2400+, con 512 MB di RAM, con sistema operativo Linux Mandrake 10. I risultati sono espressi in cicli di clocks. In tabella 4 è descritto il costo della codifica IDA al variare del numero dei pacchetti n e della ridondanza r (ripetendo l’algoritmo 100 volte). La Fig. 21 ne rappresenta graficamente i costi.

n Ridondanza 7% Rid. 20% Rid. 27% Rid. 33% Rid. 40%

32 4,14E+09 4,60E+09 4,76E+09 4,87E+09 4,88E+09

64 9,71E+09 1,19E+10 1,19E+10 1,27E+10 1,37E+10

128 2,50E+10 3,45E+10 3,78E+10 4,02E+10 4,19E+10

256 6,83E+10 1,07E+11 1,22E+11 1,32E+11 1,39E+11

512 2,20E+11 3,89E+11 4,51E+11 4,96E+11 5,24E+11

70 0,00E+00 1,00E+11 2,00E+11 3,00E+11 4,00E+11 5,00E+11 6,00E+11 0 200 400 600 n C lock cycl es Ridondanza 7% Ridondanza 20% Ridondanza 27% Ridondanza 33% Ridondanza 40%

Figura 21: Grafico relativo ai costi di Tabella 4.

Analogamente, nella tabella 5 sono riassunti i costi per il ripristino dell’informazione con IDA, mentre in Fig. 22 ne è data una rappresentazione grafica. Si noti come i costi diminuiscono all’aumentare della ridondanza.

n Ridondanza 7% Rid. 20% Rid. 27% Rid. 33% Rid. 40%

32 1,55E+09 1,34E+09 1,24E+09 1,13E+09 1,02E+09 64 3,19E+09 2,77E+09 2,54E+09 2,31E+09 2,09E+09 128 6,99E+09 5,85E+09 5,40E+09 4,83E+09 4,38E+09 256 1,55E+10 1,30E+10 1,18E+10 1,08E+10 9,65E+09 512 3,51E+10 2,91E+10 2,62E+10 2,34E+10 2,07E+10

Tabella 5: Ripristino informazione con IDA, in cicli di clocks.

0,00E+00 5,00E+09 1,00E+10 1,50E+10 2,00E+10 2,50E+10 3,00E+10 3,50E+10 4,00E+10 0 100 200 300 400 500 600 n Clock cycles Ridondanza 7% Ridondanza 20% Ridondanza 27% Ridondanza 33% Ridondanza 40%

71

Sempre in [21] sono stati eseguiti dei test sulla verifica della firma utilizzando l’algoritmo di crittografia RSA, con chiave di 1024 bits. Il costo necessario è di 3,54E+05 cicli di clocks.

Inoltre, è stato valutato il costo dell’algoritmo MD5 [19] per pacchetti di dati grandi 1024 bits, che è risultato essere di 4,89E+06 cicli di clocks.

Utilizzando le informazioni acquisite sinora, si possono estrapolare i costi di CECInA, PRABS e CECInA M-C sulla base del numero d’operazioni richieste dagli algoritmi (tabella 3). La Fig. 23 mostra graficamente le complessità dei metodi descritti sinora nel caso che l’attaccante inietti solo payload packets falsificati, assumendo d’avere n = 512 payload packets con una ridondanza del 27% (vale a dire r = 137). La funzione hash usata è MD5. Per CECInA M-C il numero di canali l che subiscono l’attacco è il 60% dei canali totali p.

Il grafico mostra bene il risparmio ottenuto con CECInA M-C, conseguito anche grazie alla costruzione dei pacchetti attraverso il PMTR. Si noti che quest’ultimo è indipendente dall’algoritmo usato e che, quindi, può essere adoperato anche in altri algoritmi.

La Fig. 24 mostra le complessità degli algoritmi nel caso che l’attaccante inietti solo signature packets invalidi. Si noti come il costo di CECInA e CECInA M-C diminuisca drasticamente rispetto al caso precedente, per via della separazione, in pacchetti distinti, dei dati da ricostruire e della loro firma; in PRABS, invece, il dato è codificato insieme alla sua firma.

In particolare, in Fig. 25 è mostrato, con maggiore dettaglio, la differenza di complessità tra CECInA e CECInA M-C nel caso che l’avversario inietti solo signature packets invalidi.

72 4,00E+09 5,40E+10 1,04E+11 1,54E+11 2,04E+11 2,54E+11 3,04E+11 3,54E+11 0 1000 2000 3000 4000 5000 6000 7000

Invalid Payload Packets

Clock cycles

PRABS CECInA CECInA M-C

Figura 23: Complessità computazionale per n = 512 payload packets e r = 137.

3,00E+09 5,30E+10 1,03E+11 1,53E+11 2,03E+11 2,53E+11 3,03E+11 3,53E+11 0 1000 2000 3000 4000 5000 6000 7000

Invalid Signature Packets

C lock cycl es PRABS CECInA CECInA M-C

73 5,00E+09 1,00E+10 1,50E+10 2,00E+10 2,50E+10 3,00E+10 0 1000 2000 3000 4000 5000 6000 7000

Invalid Signature Packets

Clock cycles

CECInA CECInA M-C

Figura 25: Confronto tra CECInA e CECInA M-C.

In precedenza si è ipotizzato che la perdita dei pacchetti è dovuta esclusivamente all’attaccante. Sotto tale condizione, l’invio di un signature packet per canale, anche nel caso che il numero dei canali sia minore dei pacchetti ridondanti (p < r), assicura che il destinatario riceva correttamente almeno una firma legittima. S’ipotizzi adesso che il mezzo di comunicazione sia soggetto ad una certa perdita d’informazioni. Ad esempio, in sistemi di trasmissione dati su fibre ottiche ad alta velocità, il BER (Bit Error Rate) è stato calcolato essere inferiore a 10-13. Ne consegue che una contromisura, per evitare la perdita di dati necessari alla ricostruzione di un’informazione, è inevitabile anche per i signature packets: almeno r + 1 copie devono essere immesse nella rete, premesso che r possono essere distrutti da un attaccante o persi per cause imputabili al mezzo di trasmissione. Alla luce di queste nuove condizioni, la situazione peggiore per il ricevente, dal punto di vista computazionale, si verifica in concomitanza dei seguenti fattori:

a) i signature packets inviati sui canali sicuri si perdono o arrivano danneggiati;

74

b) l’attaccante elimina r firme dai canali che subiscono l’attacco, lasciando inalterato un solo signature packet Pi = < v0' > (con v0' la firma della radice del PMTR);

c) l’attaccante ritarda la consegna al destinatario del signature packet Pi, iniettando nel frattempo F signature packets falsificati.

Il ricevente, in questa situazione, memorizza tutti i payload packets in arrivo, poiché non potrà verificarli sino alla ricezione della firma Pi. Il controllo d’ogni signature packet falsificato determinerà un incremento computazionale rispetto al caso ipotizzato in precedenza. Il numero d’operazioni logiche richieste da CECInA M-C sarà, in questo caso:

(F+1) Sign. ver. + (Y+n)/2 (log n)/2 Hash + IDA.

In Fig. 26 il grafico mostra (in scala logaritmica) la complessità del metodo con riferimento al numero d’operazioni logiche richieste in più da quest’ultima ipotesi. 1,00E+09 1,00E+10 1,00E+11 1,00E+12 0 1000 2000 3000 4000 5000 6000 7000

Invalid Signature Packets

Clock cycles

PRABS CECInA CECInA M-C (F+1)

75

L’incremento del numero dei cicli di clocks di CECInA M-C in Fig. 26 varia dal 6% al 50% (all’aumentare delle firme invalide iniettate) rispetto alla situazione descritta in Fig. 25, mantenendosi comunque su valori molto inferiori rispetto agli altri due algoritmi considerati; questo perché il peso maggiore della complessità dell’algoritmo è dato dalla ricostruzione della radice del Merkle tree per ogni payload packet in arrivo.

Il costo per la verifica dei signature packets deve essere espresso, di conseguenza ai casi appena trattati, in modo probabilistico. Si assuma che la probabilità di perdere un pacchetto per cause imputabili al mezzo di comunicazione sia uguale alla probabilità che ha lo stesso pacchetto di essere eliminato da un avversario, cioè r/(n+r+1). La probabilità di non ricevere una firma da un canale sicuro è

Psig(cs) = (r/(n+r+1))cs. Il costo medio per la verifica delle firme (in breve SVM) è il seguente:

SVM = Psig(cs)·(Costo Ver. Sign.)·(F+1) + (1–Psig(cs))·(Costo Ver. Sign.)·(l+1), dove il primo termine della somma indica il costo per la verifica delle firme di tutti i signature packets invalidi in arrivo nella probabilità che non si ricevano signature packets dai canali sicuri, mentre il secondo termine indica il costo per la verifica delle firme nella probabilità che si riceva almeno un signature packet da un canale sicuro.

Di conseguenza il numero d’operazioni logiche richieste da CECInA M-C varierà nel seguente modo:

SVM + (Y+n)/2 (log n)/2 Hash + IDA.

In Fig. 27 è stato confrontato quest’ultimo caso con quello in cui l’algoritmo verifica F+1 signature packets invalidi. Si è assunto che siano attaccati circa il 60% dei canali totali p. Si noti come CECInA M-C adottando il costo medio per la verifica delle firme (SVM) sia molto vicino a CECInA M-C in cui si controllano

76 5,50E+09 6,00E+09 6,50E+09 7,00E+09 7,50E+09 8,00E+09 8,50E+09 9,00E+09 0 1000 2000 3000 4000 5000 6000 7000

Invalid Signature Packets

C

lock cycl

es

CECInA M-C (F+1) CECInA M-C (SVM)

Figura 27: Confronto tra CECInA M-C con SVM e F+1.

I vantaggi introdotti dallo scheduling proposto si notano nel momento in cui il destinatario subisce un injection attack con payload packets falsificati. Per il destinatario è importante ricevere almeno un CWS packet per l’autenticazione di tutti gli altri pacchetti.

Nell’ipotesi che non venga adottata nessuna forma di scheduling per l’invio dei payload packets nella rete, si potrebbe verificare la seguente situazione:

1. I CWS packets sono inviati sullo stesso canale, attaccato da un avversario; 2. L’avversario elimina tutti i CWS packets tranne uno, ritardando la

ricezione di quest’ultimo al destinatario;

3. Il ricevente non può autenticare i payload packets che riceve senza avere autenticato almeno un CWS packet, poiché i tempi di verifica crescerebbero notevolmente (diventano polinomiali, come discusso in precedenza); di conseguenza è costretto a memorizzare tutti i pacchetti in arrivo sino alla ricezione di un legittimo CWS packet.

Lo scheduling esclude che si verifichi la situazione appena descritta, assicurando al ricevente la ricezione di un CWS packet già all’inizio delle comunicazioni (a

77

parte eventuali ritardi di rete). Indipendentemente dallo scheduling adottato, i signature packets sono sempre inviati su canali distinti.

Ipotizziamo che il mittente usi uno scheduling banale come, ad esempio, quello di suddividere gli n payload packets in gruppi di n/p pacchetti, cominciando da quello con indice minore e procedendo in ordine crescente, assegnando successivamente ogni gruppo ad un canale. Per esempio, in una situazione in cui si devono distribuire n = 16 payload packets su p = 3 canali con una ridondanza r = 2 (z = r + 1), uno scheduling banale è illustrato in tabella 6, mentre la tabella 7 illustra lo scheduling adoperato in CECInA M-C.

I CWS packets dell’esempio sono P0, P1 e P2. Con lo scheduling banale i CWS packets sono inviati sullo stesso canale. Se quest’ultimo è attaccato da un avversario, l’autenticazione degli altri payload packets sarà ritardata, per i motivi già descritti. Inoltre, il ricevente è soggetto ad un attacco DoS sulla memorizzazione. Gli effetti dell’attacco, in CECInA M-C, sono comunque ammortizzati dal fatto che dai canali sicuri il destinatario riceve payload packets legittimi, che contribuiranno al raggiungimento della soglia q di pacchetti necessari per la ricostruzione del dato. Al raggiungimento della soglia, la memorizzazione dei pacchetti relativi al dato da ripristinare sarà interrotta, annullando, di fatto, l’attacco DoS in corso.

1° can. 2° can. 3° can.

P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15

1° can. 2° can. 3° can.

P0 P4 P10 P11 P12 P1 P5 P9 P14 P15 P2 P3 P6 P7 P8 P13

Tabella 7: Scheduling adottato da CECInA M-C. Tabella 6: Scheduling banale.