Identificazione e Difesa contro l'Attacco Eclipse al Protocollo Chord

7 
 
1 
INTRODUZIONE 
 
 
 
 
 
 
 
Le reti overlay peer to peer completamente distribuite stanno attirando un crescente 
interesse per le loro caretteristiche di robustezza ai guasti e al fatto che non necessitano di 
un autorità centrale che la gestisca. Con la dicitura rete overlay intendiamo una rete logica 
costruita sopra la rete fisica: nel nostro ambito una rete overlay è un gruppo di host connessi 
ad una WAN (ad es. internet) che si organizzano in modo da poter comunicare l’uno con 
l’altro. Per rete completamente distribuita intendiamo una rete in cui non vi è alcuna 
gerarchia, dove cioè tutti i nodi hanno un ruolo identico. Possiamo dunque affermare che le 
reti peer to peer distribuite sono le reti peer to peer nel vero senso della termine. Il 
sottogruppo delle reti peer to peer distribuite e che sono anche strutturate, hanno spiccati 
vantaggi in termini di scalabilità nei confronti del tradizionale modello client-server e delle reti 
peer to peer distribuite ma non strutturate. Per rete overlay strutturata intendiamo una rete 
overlay in cui ogni nodo conosce almeno una parte della topologia della rete ma in modo tale 
che la propagazione dei messaggi avvenga in modo efficiente e quindi scalabile. Diffuse a 
partire circa dal 2001, le reti overlay distribuite e strutturate consentono di erogare un 
amplissimo spettro di servizi online a livello globale, dal momento che tali soluzioni peer to 
peer sono altamente scalabili e lo sono ben di più del modello client-server. Se in 
quest’ultimo caso il client è solo fruitore e il server è l’erogatore del servizio, nel caso peer to 
peer ogni utente è sia fruitore che erogatore del servizio. A seconda dell’applicazione che 
usa il substrato overlay, ogni utente può partecipare nell’erogazione del servizio attraverso il 
routing di messaggi, storage di contenuti, indicizzazione di contenuti, ecc. Poiché dunque 
ogni utente partecipa all’erogazione del servizio, questo implica seri problemi di sicurezza. 
Se una rete è libera di formarsi, poiché ogni host contribuisce a fornire informazioni di routing 
agli altri host e a instradare i messaggi, è chiaro che un host maligno può modificare a 
piacimento il proprio contributo all’overlay. Ciò rende le reti overlay distribuite assai
8 
 
vulnerabili a diversi tipi di attacchi. Essi possono essere suddivisi in tre categorie [1]:  
 
1) Attacco Sybil: una singola entità (l’attaccante) incrementa la propria presenza nel sistema 
creando nuove identità che poi impiega per operare nella rete. 
2) Attacco Eclipse: l’attaccante inquina le informazioni di routing dei nodi onesti in modo che 
questi inoltrino più messaggi possibili ai nodi controllati dall’attaccante anziché ai nodi 
corretti. 
3) Attacchi di routing e storage: con questa categoria si comprendono vari attacchi a livello 
applicativo, i quali sono facilitati dai precedenti due attacchi. 
 
E’ evidente che l’attacco Sybil è un punto di partenza avvantaggiato per sferrare gli attacchi 
di tipo 2 e 3.  
Approfondiamo ora l’aggettivo “strutturato” delle reti overlay peer to peer strutturate. Il 
metodo più comune per realizzare una rete overlay distribuita e strutturata è la Distributed 
Hash Table (DHT). Una DHT è una hash table quindi possiamo idealizzarla come una tabella 
in cui ogni entry è composta da una chiave (è l’hash) e da un valore. La chiave di una entry 
di una hash table è l’hash del valore di quella entry. Lo scopo della chiave è quello di 
identificare univocamente il valore associato, in uno spazio matematico che sia indipendente 
dalla natura dei valori. In questo modo due valori non trattabili come numeri (ad es. due nomi 
di file) sono proiettati nell’unico spazio delle immagini della funzione hash usata per calcolare 
le relative chiavi. I valori di una hash table possono essere un qualunque tipo di dato: 
contenuti testuali e multimediali, indirizzi IP, username, ecc. Se poi tale stuttura dati è 
distribuita, significa che è divisa in parti - secondo qualche criterio - e ogni parte è 
memorizzata in un nodo diverso (host) dell’overlay. Il mapping tra un valore e il nodo che lo 
memorizza (nodo responsabile) è univocamente determinato dalla chiave di tale valore. A 
seconda di come è definita la DHT vi sono poi regole protocol-specific che definiscono il 
mapping chiave-nodo. Vediamo ora che funzionalità offre all’applicazione una DHT. In una 
DHT vi sono due primitive fondamentali: “put” e “get”. Con la prima l’applicazione di un nodo 
inserisce un nuovo valore nella DHT e il nodo che memorizza tale valore è il nodo 
responsabile della chiave di tale valore. Con la seconda, l’applicazione di un nodo, data una 
chiave, recupera il valore associato. Una variante di quest’ultima funzione è la funzione 
“route” che semplicemente permette ad un messaggio di giungere al nodo responsabile della 
chiave di destinazione del messaggio. In ogni caso, tutte e tre le operazioni menzionate 
implicano la propagazione di messaggi. Una DHT pertanto, offrendo le due primitive 
succitate, può essere il driver ideale per un vasto spettro di applicazioni distribuite. Tali 
funzionalità però sarebbero poco utili per gestire applicazioni di larga scala se una DHT non
9 
 
godesse delle seguenti due peculiarità: 
1) Scalabilità di memoria: ogni nodo memorizza un’informazione di routing molto piccola 
rispetto al numero di nodi dell’overlay e tipicamente ha un andamento logaritmico con il 
numero di nodi. 
2) Scalabilità di routing: l’overlay hop count medio dei messaggi è molto basso rispetto al 
numero di nodi e tipicamente ha un andamento logaritmico con il numero di nodi nel sistema. 
Possiamo dunque concludere che la DHT è uno strumento per servire applicazioni distribuite 
senza la necessità di una struttura gerarchica e in modo altamente scalabile. Le DHT 
consentono ad esempio il dispiegamento di servizi online serverless su scala globale. 
La mancanza di un’entità centrale supervisionante e l’elevata scalabilità di memoria rendono 
le DHT assai vulnerabili ad attacchi in cui le azioni maligne coinvolgono il routing (ad es. 
l’attacco Eclipse), in quanto i nodi si affidano a poche informazioni di routing per comunicare 
con il resto della rete e pertanto è facile per l’attaccante riuscire a popolare l’informazione di 
routing dei nodi vittima con riferimenti a nodi maligni. La mancanza di un’autorità 
supervisionante rende anche difficile il controllo degli accessi nel sistema e questo rende 
ancora più facili i suddetti attacchi sul routing. 
Ad oggi come esempi di sistemi reali che impiegano DHT vi sono applicazioni distribuite su 
scala globale che necessitano la memorizzazione e il recupero di informazioni in modo 
scalabile. Esempi di queste applicazioni sono alcuni overlay di file sharing (Trackerless 
BitTorrent, KAD, LimeWire), il sistema VoIP distribuito P2PSIP, diversi motori di ricerca ma 
anche botnet [1]. I protocolli Chord [2], CAN [3], Pastry [4], Tapestry [5] e Kademlia [6] sono 
esempi di protocolli overlay che consentono l’instaurazione di una rete peer to peer overlay 
completamente distribuita e strutturata, in cui la struttura è appunto una DHT.  
In [1] vi è una survey sulle principali difese contro gli attacchi comuni alle DHT e si conclude 
che per rendere sicure le DHT occorre un assegnamenro sicuro degli identificativi ID (chiavi) 
dei nodi, una bassa percentuale di nodi maligni e sparsi sullo spazio degli ID, replica dei dati 
e meccanismi di routing resilienti ai nodi dal comportamento scorretto. In ogni caso, il punto 
più importante è quello di avere un assegnamento degli ID sicuro, al fine di assicurare che la 
percentuale di nodi maligni sia bassa e che essi non possano scegliere i loro ID in modo da 
posizionarsi in determinati punti dello spazio degli ID.  
 
Il contributo di questa tesi è quello di risolvere il problema di quello che probabilmente è 
l’attacco più devastante nelle reti overlay distribuite, ossia l’attacco Eclipse. In questa tesi 
affrontiamo il problema di identificare e di contrastare l’attacco Eclipse nel caso specifico di 
rete overlay distribuita strutturata attraverso il protocollo Chord. Quest’ultimo è il protocollo 
overlay che implementa la DHT che ha finora destato il maggior interesse da parte della
10 
 
comunità scientifica. 
La tesi è costituita dai seguenti capitoli: nel capitolo 2 viene offerta una panoramica della 
situazione corrente di quanto è stato fatto finora per contrastare l’attacco Eclipse alle reti 
overlay distribuite. Nel capitolo 3 viene descritto il protocollo Chord, nel capitolo 4 vengono 
chiariti alcuni termini e notazioni che verrano poi usate nel resto del testo, viene spiegato 
come abbiamo implemetato l’attacco Elipse in Chord, l’ambiente sperimentale e i valori 
comuni in tutte le simulazioni. Il capitolo 5 espone la nostra soluzione e i risultati per quanto 
riguarda l’identificazione dell’attacco Eclipse in Chord. Il capitolo 6 presenta le nostre 
proposte e i risultati sulle difese contro l’attacco Eclipse al protocollo Chord. Infine nel 
capitolo 7 vi sono le conclusioni di tutto il lavoro svolto.
11 
 
2 
STATO DELL’ARTE 
 
 
 
 
 
 
 
Una rete overlay è una rete logica sopra una rete fisica in cui i nodi si organizzano creando 
link virtuali fra loro, quindi, ogni nodo è collegato ad un gruppo di nodi che usualmente 
chiamiamo vicini (neighbors). Se l’attaccante controlla una frazione sufficiente dei vicini di un 
nodo onesto, allora può provocare l’attacco “eclisse” (Eclipse attack) nel senso che il nodo 
vittima avrà una visione ridotta o addirittura nulla degli altri nodi onesti. Questo tipo di attacco 
è anche noto in letteratura come “routing table poisoning” (avvelenamento della routing 
table). Un attacco Eclipse può essere usato per lanciare poi attacchi a livello applicativo, che 
nel contesto delle DHT (Distributed Hash Table) sono gli attacchi di routing e storage, tesi a 
corrompere l’applicazione distribuita che usufruisce del DHT corrotto. 
Sit e Morris [7] sono stati i primi a studiare questo attacco nel contesto delle DHT. Hanno 
affermato che sistemi in cui non esistono speciali esigenze di controllo sui vicini sono 
totalmente vulnerabili a questo tipo di attacco. Il modo più facile per sfruttare questa 
debolezza consiste gli aggiornamenti di routing incorretti. Per esempio, come spiegato in [1], 
i livelli più alti della routing table del protocollo overlay Pastry necessitano un prefisso 
comune di poche cifre. Ciò incrementa il numero di identificatori di nodo validi che un 
attaccante può fornire nei messaggi di routing table update. Questo, al contrario, è più 
facilmente evitabile in sistemi che impongono forti vincoli di routing table, come ad esempio 
in Chord, in cui ogni entry della routing table dev’essere il successore di un determinato 
identificativo nello spazio delle chiavi. Se non vi sono difese opportune, l’attacco Eclipse può 
far sì che la frazione di entry maligne della routing table dei nodi onesti tenda a uno, dato che 
il numero di entry maligne può aumentare ad ogni aggiornamento. Altro possibile metodo per 
realizzare un’eclisse è la sovversione del meccanismo di misura della relazione di vicinanza 
nella rete. Per esempio in [8] mostrano che un attaccante può ridurre la sua distanza di rete 
underlay usando un nodo vicino al nodo vittima per inoltrare una “spoofed response” di
12 
 
heartbeat message. In [9] viene affermato che le misure di prossimità possono anche essere 
sovvertite mediante vari meccanismi malevoli, ad esempio nel caso in cui l’attaccante 
controlla una grande infrastruttura di rete come un ISP oppure una grande società. Occorre 
anche notare che se non è possibile inquinare le misure di prossimità, allora tali relazioni di 
vicinanza possono essere un aiuto per contrastare l’attacco Eclipse [8]. Altro scenario di 
attacco di prossimità nelle DHT consiste nel mettere tanti nodi maligni nelle vicinanze dei 
nodi vittima, in modo che possano infiltrarsi il più possibile nelle routing table di questi ultimi.  
Una difesa all’attacco Eclipse si ritiene che abbia pieno successo se la frazione di entry 
maligne della tabella di routing di un nodo onesto è simile alla frazione f dei nodi maligni 
presente nel sistema. La ragione di ciò è che f è la frazione di entry maligne che ci si aspetta 
in un campione di nodi, nell’ipotesi che gli identificatori dei nodi siano generati in modo 
random uniforme. In ogni caso, l’instradamento di un messaggio usando un singolo path ha 
difficilmente successo. Per esempio, se f = 0.25 (frazione di nodi maligni nella rete) e la 
lunghezza del path è 5, la probabilità di avere instradamento con successo è (1 - 0.25)
5 
=
 
0.24, che è inaccettabile nella maggioranza delle applicazioni. Perciò, in molte proposte di 
difesa, i protocolli di aggiornamento della routing table sono accompagnati con alcune forme 
d’instradamento ridondanti.  
Il modello di attacco più usato dalle soluzioni proposte vedono i nodi maligni collidere fra loro 
e cercano di massimizzare l’inquinamento delle informazioni di routing dei nodi onesti, 
fornendo sempre informazioni di routing maligne. Comunque, questo non è necessariamente 
l’unico scenario. Per esempio, l’avversario può provare a attaccare solo un sottoinsieme dei 
nodi, una chiave particolare, oppure una particolare entry della routing table. L’attaccante 
può anche solo provare a disseminare moderatamente l’inquinamento, attaccando nodi in 
modo sequenziale e comportandosi quasi sempre in modo corretto. Nessuna delle soluzioni 
proposte sono state pensate contro questi comportamenti insidiosi. In [9] gli autori discutono 
gli attacchi localizzati, i quali richiedono che un nodo onesto sia circondato dai nodi maligni in 
termini di distanza di rete. Essi concludono che difendersi contro tali attacchi rimane un 
problema aperto. Dalla revisione della letteratura della sicurezza in reti overlay peer to peer, 
emerge che la migliore difesa base all’attacco Eclipse consiste nel vincolare gli identificatori 
dei nodi che possono essere usati nella tabella di routing come è già naturale in Chord. 
Questo è valido solo se gli identificatori dei nodi sono random e stabili (cioè in una rete non 
dinamica), e i nodi maligni sono uniformemente sparsi nello spazio degli identificatori. Per 
raggiungere questi condizioni, l’approccio più semplice è l’impiego di nodi con identificatori 
stabili distribuiti da un’autorità fidata. In alternativa, in [11] propongono un approccio basato 
sul churn, causando ogni volta che un nodo entra nella rete il riassegnamento degli 
identificatori dei nodi già presenti. Il prezzo da pagare è che sfruttando le proprietà degli
13 
 
identificatori dei nodi come unico criterio per selezionare le entry da inserire nella routing 
table, si impedisce l’ottimizzazione delle prestazioni come la selezione dei vicini in termini di 
rete underlay. L’ottimizzazione di network proximity può essere facilmente implementata in 
sistemi come Pastry perché impongono deboli requisiti di geometria overlay alle entry della 
routing table. La conseguenza è che tanti nodi soddisferanno i requisiti degli identificatori 
(geometria overlay), e dunque le misure di rete possono essere utili per selezionare i migliori 
vicini underlay. Il problema di ciò è che i nodi maligni possono facilmente popolare le routing 
table dei nodi onesti, per mezzo di azioni maligne sui protocolli di routing table update 
oppure sul sistema di misura di prossimità. In [12] viene mostrato che avendo 15% di nodi 
maligni nella rete overlay corrisponde ad avere approssimativamente 80% di entry maligne 
nelle tabelle di routing del protocollo Pastry. La maggiore parte della letteratura sull’attacco 
Eclipse è mirata a difese che tentano di preservare le prestazioni della rete su routing table 
basate su quelle di Pastry. In questi casi, l’approccio più comune è l’uso ridondante degli 
entry della routing table [8], in cui è ci si aspetta che alcune entry saranno oneste e sufficienti 
per permettere un routing ridondante con successo. In [12] invece gli autori propongono di 
costringere periodicamente ogni nodo di uscire dalla rete overlay e a rientrare con un nuovo 
identificatore, e con due nuove tabelle di routing, una delle quali sarà ottimizzata, finché il 
nodo non esegue la nuova join prevista. Questo è simile all’approccio di [11]. Altra soluzione 
per contrastare l’attacco Eclipse è quello di controllare il numero di link entranti (grado di 
ingresso) e uscenti per nodo (grado di uscita). Il ragionamento è che il grado di ingresso dei 
nodi maligni è in media superiore al grado dei nodi onesti poiché questi ultimi si ritrovano, 
inconsapevolmente, a puntare a molti nodi collusi anziché a nodi non collusi. L’approccio 
secondo [10] ha il vantaggio di essere completamente decentralizzato, ma impone un basso 
limite di grado di uscita, il quale corrisponde ad un aumento del tempo di lookup in assenza 
di attacco. Si evince quindi, che difendersi dall’attacco Eclipse implica un trade-off tra 
prestazioni e complessità. In [9] vengono affrontati diversi problemi sulla sicurezza di reti 
P2P strutturate, quale è il protocollo Chord, e nel nostro ambito di attacco Eclipse, ci 
interessano le soluzioni di mantenimento sicuro delle informazioni di routing e l’inoltro sicuro 
dei messaggi. Per il primo aspetto si osserva che, se è un protocollo prevede una routing 
table che rispetti determinate regole di geometria overlay, allora il nodo rifiuta le informazioni 
di routing update che sembrano non rispettare tali regole. Poiché questo mantenimento 
sicuro della routing table è verosimilmente non perfetto - ci sono ancora entry maligne – 
viene allora proposta una possibile soluzione per l’inoltro sicuro dei messaggi. La difesa 
proposta è di tipo reattivo: prima c’è un test e poi, se necessaria, la reazione. Il test è un test 
a soglia e consiste nel misurare quanto il nodo che ha ricevuto un messaggio è 
verosimilmente il vero destinatario. La reazione è un routing ridondante. Queste soluzioni in
14 
 
[9] vengono descritte per il solo caso del protocollo Pastry ma sono estensibili ad altri 
protocolli come ad esempio Chord. Il test consiste nel misurare la densità di nodi (nello 
spazio delle chiavi) di un certo numero di nodi attorno al nodo destinazione per compararla 
con la densità attorno al nodo sorgente. Poiché quella dei nodi maligni è inferiore di quella 
dei nodi onesti, il nodo sorgente può dedurre da questo test se il messaggio è finito su nodi 
maligni o no. Questo meccanismo è simile a quanto noi facciamo in Chord: la densità del 
nodo sorgente la stimiamo come media delle distanze fra le entry della successor list, mentre 
come densità al nodo destinazione prendiamo il campione dato dalla distanza fra la chiave di 
destinazione del messaggio e il nodo su cui è terminato. Non si può fare altrimenti, infatti il 
nodo sorgente non può fare stime di densità della destinazione in quanto non ne conosce il 
neighborhood. E anche se glielo chiedesse con messaggi appositi, un nodo maligno può 
sempre fornire informazioni ingannevoli. La reazione presentata in [9], invece, consiste nel 
mandare copie dello stesso messaggio finché non si raggiunge un nodo avente la 
destinazione nel proprio neighborhood. A quel punto si sfrutta l’informazione dettagliata che 
tale nodo ha sulla regione dello spazio delle chiavi attorno alla destinazione (root) per 
assicurare che tutte le destinazioni replica (replica roots) ricevano un copia del messaggio. 
Sarebbe interessante vedere i risultati in Chord, tuttavia siamo di fronte ad un sistema 
ridondante, il quale raggiunge sì ottimi risultati (almeno in Pastry) ma con un overhead 
potenzialmente elevato. Inoltre l'attacco in esame su Pastry è anche assai meno devastante 
dell'attacco Eclipse in Chord, in quanto la probabilità di routing corretto è ben inferiore 
nell'ultimo caso a parità di percentuale di nodi maligni, come dimostrato dai grafici. Infine, 
come avevamo accennato, sappiamo che la difesa ideale all’attacco Eclipse garantisce che 
la probabilità che un entry della tabella sia maligna è equivalente alla frazione f di nodi 
maligni nella rete overlay. Questo significa che le tecniche fino ad oggi proposte non sono 
sufficienti a garantire il funzionamento appropriato delle DHTs in caso di attacco Eclipse a 
meno che non siano combinate con altri meccanismi come il routing ridondante. Finora 
abbiamo fatto una rapida overview di come è stato affrontato il problema dell’attacco Eclipse 
nelle reti overlay peer to peer in generale. Nel caso specifico del protocollo Chord vi è ad 
oggi sorprendentemente poco in letteratura. In [13] viene presentata una soluzione per 
aumentare la probabilità di successo delle query Chord in presenza di nodi che 
semplicemente eliminano ogni messaggio dati che ricevono. Questo non è propriamente un 
attacco Eclipse poiché in quest'ultimo l'azione maligna è il routing modificato dei maligni su 
tutti i messaggi (controllo e dati) e non la semplice eliminazione dei messaggi dati. Come 
dimostrano anche i risultati numerici dell'attacco di data dropping, l'attacco Eclipse è ben 
peggiore, quindi il contesto di partenza di [13] è molto più favorevole rispetto al nostro caso. 
La soluzione proposta è quella di memorizzare presso ogni nodo dei path ciclici appresi
15 
 
dall'osservazione del path che viene appositamente inserito nei messaggi. Un ciclo è infatti 
esente dai maligni per il semplice fatto che è un path che torna al nodo in questione, quindi 
non può aver incontrato nessun maligno. Di conseguenza, ad ogni lookup, prima di invocare 
il Chord routing, si sceglie come next hop il nodo che fra tutti i cicli conosciuti dal nodo 
precede più da vicino la chiave di destinazione del messaggio e che allo stesso tempo è 
presente nella finger table o nella successor list. Se una tale nodo non viene trovato, il 
messaggio è inoltrato alla finger o al successor scelti in base al normale Chord lookup. 
Questa potrebbe essere una soluzione interessante anche contro l'attacco Eclipse, tuttavia, 
come già detto, è stata sperimentata sull'attacco di data dropping anziché sull’attacco 
Eclipse.