freenet logo

Il progetto Freenet

freenet symbol

--- ricablare Internet ---

navigatore
donazioni
grazie a...
Ospitato da:
SourceForge
&
Dominio donato da:
Edward Alfert
Mousetracker.com

• Questo documento è disponibile in una versione più aggiornata in inglese qui.

Inglese

Il Protocollo di Freenet

Adam Langley

Il documento è ancora in via di elaborazione, quindi non prendetelo per oro colato.

Introduzione

Il protocollo di Freenet si basa sull'idea di messaggi che passano tra i nodi di una rete. I messaggi in questione contengono un nome, una serie di intestazioni e un campo opzionale di trailing. Quest'ultimo campo, se presente, trasporta i dati. I nodi dovrebbero agire sui messaggi in maniera consistente e, se così fosse, questo dovrebbe portare alla formazione di un network capace di adattamento.

Il fine ultimo di un network Freenet è di immagazzinare documenti e di permettere che essi siano recuperati successivamente mediante l'uso di una chiave, in maniera molto simile a quello che è ora possibile con protocolli come l'HTTP. Un network viene definito come una serie di Nodi che si passano messaggi tramite collegamenti Peer-to-Peer. Normalmente una macchina in questa rete farà girare il software che gli permette di agire come un nodo, collegandosi ad altre macchine che stanno facendo girare lo stesso programma per formare una rete distribuita di nodi indipendenti. Alcuni nodi saranno punti a cui avranno accesso gli utenti finali della rete, nodi in cui sarà possibile richiedere documenti e ottenerli in una forma umanamente leggibile. Questi nodi però comunicano tra loro e con nodi intermedi nello stesso modo: non ci sono client o server dedicati nella rete Freenet.

Il protocollo di Freenet è stato pensato per essere implementato su una rete a topologia complessa, in maniera non dissimile dall'IP (Internet Protocol). Ogni nodo "conosce" solo alcuni altri nodi che può raggiungere direttamente (in un certo senso i suoi "vicini"), ma ogni nodo può essere il vicino di ogni altro; non esiste una gerarchia dei nodi o ogni altro tipo di struttura. Ogni documento (oppure ogni altro messaggio come la richiesta di un documento) viene fatto circolare in Freenet attraverso tutta la rete, passando di vicino in vicino fino a raggiungere la sua destinazione. Nel passare un documento al proprio vicino, un nodo non si preoccupa di sapere se il vicino sia un altro nodo intermedio che gira l'informazione a sua volta ad un altro nodo, o un nodo-utente che presenterà il documento ad un utente finale. Tutto questo è intenzionale, ed è pensato per garantire l'anonimità sia del produttore dell'informazione che dell'utente che la cerca.

Ogni nodo conserva un una serie di documenti associati a chiavi. Insieme ad ogni documento immagazzina anche l'indirizzo di un altro nodo da cui ha ricevuto il documento (e possibilmente anche alcuni dati aggiuntivi circa il documento). Oltre a ciò un nodo potrebbe conservare chiavi di documenti che sono stati cancellati (in seguito alla mancanza di richieste del documento, a limiti di memoria del nod, ecc.), ma in questo caso conserverebbe un puntatore ad un altro nodo che potrebbe ancora avere i documenti in questione.

Per trovare un documento nella rete avendo la sua chiave, un utente manda un messaggio ad un nodo (probabilmente sulla stessa macchina su cui gira il programma client) richiedendo il documento e fornendo anche la chiave. Se sul nodo non è presente nessuna chiave, allora il nodo cerca la chiave "più simile" presente ("simile" nel senso che verrà descritto più avanti in questo documento) e passa la richiesta al nodo associato con quest'ultima, memorizzando l'operazione.

Il nodo a cui è stata passata la richiesta ripete il processo fino a che non viene trovata la chiave richiesta o fino a che gli hop compiuti sono in numero tale da indicare il fallimento della richiesta. Se un nodo viene visitato una seconda volta nel percorso di ricerca (e il nodo se ne accorge perché si ricorda di aver fatto circolare una richiesta per quella chiave una prima volta) allora il nodo interrompe il circolo vizioso, mandando un messaggio al nodo che gli ha fatto la seconda richiesta in cui gli comunica di passare la richiesta al successivo nodo in ordine di similitudine con la chiave richiesta.

Alla fine il documento viene trovato oppure viene superato il limite di hop e il nodo emette un risposta alla richiesta che viene fatta tornare fino all'utente originarioi lungo il percorso specificato dalla registrazione da parte dei nodi intermedi delle richeiste in attesa di risposta. I nodi intermedi possono decidere di memorizzare anch'essi il documento per ottimizzare future richieste dello stesso.

Lo stesso processo avviene sostanzialmente quando si cerca di inserire un documento nella rete, con il docuemnto che viene immagazzinato in ogni nodo lungo il percorso.

Quando viene creato un nuovo nodo nella sua memoria viene creata una cella "muta" ("dummy", ndt) con una chiave casuale per ogni nodo di cui la nuova macchina conosca l'esistenza. Nel momento in cui una richiesta viene effettuata sul nuovo nodo, una o più di queste celle sarà la più "simile" e questo determinerà a quali nodi la richiesta verrà passata prima.

Inizialmente, quindi, ogni nodo ha una gamma di chiavi puramente casuale per ogni altro nodo che conosce e questo significa che i nodi a cui manderà un certo set di dati dipenderà interamente da cosa saranno queste chiavi casuali. Siccome nodi differenti usano chiavi casuali differenti, però, all'inizio ogni nodo non concorderà con gli altri circa la localizzazione in cui cercare o mandare dati, data una certa chiave. I dati in un nuovo nodo Freenet saranno quindi distributii in maniera abbastanza casuale.

Mano a mano però che i documenti saranno inseriti dallo stesso nodo, inizieranno a raggrupparsi con oggetti le cui chiavi sono simili, dato che per essi verranno utilizzate le stesse regole di trasferimento. Più importante ancora di questo è che mano a mano che dati e richieste da differenti nodi si incrociano, questi ultimi iniziaeranno a scambiarsi informazioni anche sui raggruppamenti (cluster, ndt) di dati simili.

Il risultato di tutto questo dovrebbe essere una rete che si autorganizza in una struttura distribuita e clusterizzata in cui i nodi tendono a conservare dati "simili" vicini. Probabilmetne si verranno a creare molti di questi raggruppamenti nella rete nel suo complesso, dato che ogni documento viene replicato molte volte nella rete stessa, in relazione a quanto viene richiesto. È una sorta di "rottura spontanea della simmetria" in cui uno stato inizialmente simmetrico (tutti i nodi uguali con chiave casuali diverse per ognuno) porta ad una situazione molto asimmetrica, con nodi che si vanno a specializzare in dati con chiavi "simili".

Ci sono forze che tendono a favorire il raggruppamento di dati (la similitudine condivisa dai dati si diffonde nella rete) e forze che tendono a separare i cluster (memorizzazione locale di dati utilizzati spesso). Queste forze saranno diverse a secodna di quanto un cero documento viene utilizzato, cosicché informazioni poco utilizzate tenderanno a rimanere solo su pochi nodi che si sono specializzati nel fornire quel tipo di dati, mentre informazioni molto utilizzate saranno distribuite ampiamente nella rete.

Una cosa importante da capire è che le chiavi sono in realtà hashes, e quindi quando si parla di similitudine tra le chiavi non si parla di similitudini semantiche. Di conseguenza non esisterà correlazione tra similitudine tra chiavi e popolarità simile dei dati se avessero dei significati in termini semantici; in questo modo si evitano colli di bottiglia causati da soggetti molto popolari.

Chiavi

Ci sono diversi tipi di chiavi in Freenet. Ogni chiave codifica il proprio tipo negli ultimi due bytes. Tipi diversi di chiave hanno porprietà differenti: alcune sono infalsificabili, altre aggiornabili. I dati che vengono inseriti in Freenet di solito sono inseriti in più documenti in modo che sia possibile sfruttare più di un tipo di chiave. Le chiavi sono spiegate in dettaglio nella sezione Chiavi.

Timeouts

Essendo Freenet una rete distribuita, essa deve fare fronte alla possibilità della caduta di alcuni nodi. I timeout fanno parte di questa possibilità di gestione. Il lasso di tempo in secondi per il quale un nodo dovrebbe aspettare una risposta è una funzione dell'opzione HopsToLive del messaggio. È definito come (mean * numero_di_hops) + (1.28 * sd * radice_quadrata_degli_hops), con mean e sd uguali a 12.

Esempio di Catena

Per capire un pò meglio il funzionamento di tutto questo potrebbe essre utile dare un occhiata all'immagine riportata qui sotto.

A diagram of 5 nodes

Nella figura viene riportata una piccola rete di prova di nodi Freenet. Per convenzione il nodo A sarà un nodo "client", cioè quello da cui partira la catena di collegamenti.

Le linee del diagramma sono nel formato:

A->B Nome HTK Depth (Profondità)
in cui A e B sono i nomi dei nodi e Nome è il nome del messaggio. Prima di tutto un richiesta di dati semplici:
A->B HandshakeRequest 1 1
B->A HandshakeReply 1 1
A->B DataRequest 10 3
B->C HandshakeRequest 1 1
C->B HandshakeReply 1 1
B->C DataRequest 9 4
C->A HandshakeRequest 1 1
A->C HandshakeReply 1 1
C->A DataRequest 8 5
A->C RequestFailed
C->D HandshakeRequest 1 1
D->C HandshakeReply 1 1
C->D DataRequest 7 5
D->C DataReply 5 2
C->B DataReply 4 3
B->A DataReply 3 4
Un bel pò di messaggi, ma tutti quei messaggi di negoziazione (handshakes, ndt) sono un poco ridondanti, quindi li leviamo per capire meglio la situazione.
A->B DataRequest 10 3
B->C DataRequest 9 4
C->A DataRequest 8 5
A->C RequestFailed
C->D DataRequest 7 5
D->C DataReply 5 2
C->B DataReply 4 3
B->A DataReply 3 4
D->C StoreData 5 2
C->B StoreData 4 3
B->A StoreData 3 4
     
Così va meglio. Ora possiamo vedere che la richiesta è passata attraverso il nodo B, C e D e che D infine aveva i dati richiesti. Notare che C ha cercato di inoltrare la richiesta verso A, ma che A conoscendo la ID unica del documento cercato non ha creato un circolo vizioso.

Il Datastore

Problemi Ci sono varie cose che un buon design del Datastore dei Dati può risolvere. Buone idee nel design dovrebbe essere giudicate dal confronto con le risposte a queste possibilità.
  • Il datastore dovrebbe essere in grado di trovare rapidamente le informazioni relative a una certa chiave.
  • Il datastore dovrebbe essere in grado di trovare rapidamente la chiave più "simile" a sua conoscenza di una certa chiave.
  • Il datastore dovrebbe essere in grado di tener traccia della popolarità relativa dei vari documenti e quindi sapere quale documento cancellare in caso di pressioni legate a limiti di spazio o altro.
  • Il datastore dovrebbe essere ragionevolmente resistente ad attacchi di tipo flood.

Metastrutture dei Documenti

Tabella di hash

Anzitutto, alcuni problemi possono essere risolti in maniera semplice. Per trovare rapidamente un documento data una chiave si può utilizzare un hash table. Dal momento che sì scelto di andare verso documenti mantenuti in strutture multiple perché mantengano dei riferimenti ai livelli superiori ha senso che gli oggetti stiano in delle dlists.

A diagram of a hash table

Si ricaverà un hash dalla chiave per ottenere un indice per l'inserimento nell'hash table. A partire da questo sarà possibile effettuare una ricerca lineare della lista sino a che non si trovi il documento desiderato ( o sino ad incontrare un null, nel qual caso non si possiede il documento ). La tabella hash dovrebbe essere lunga abbastanza e le entries, una parola per ciascuna di esse, abbastanza piccole, in modo da velocizzare la ricerca.

COC List

Per farsi un'idea di come anche i documenti più richiesti debbano essere ordinati. In cima alla lista ci sono i più scaricati. Da un certo punto in poi della lista c'è uno spazio nel quale i documenti sono semplici riferimenti. Se i nuovi documenti vengono inseriti al di sopra di questo confine, i più vecchi finiscono al di sotto (e quindi i dati vengono cancellati - liberando spazio per i nuovi).

A diagram of the COC list

Questo parte chiarisce come i documenti risalgano la COC list. Una possibilità è semplicemente spostare un documento in cima alla lista quando viene richiesto -- tendenzialmente ciascun oggetto dovrebbe disporsi col passare del tempo nella posizione più corretta. Questo apre però la possibilità ad un attacco tipo flood. Un attaccante può semplicemente inserire e richiedere in continuazione facendo così finire tutti gli altri documenti fuori dallo spazio di immagazzinamento. Comunque nessuna forma di storing dei dati può arrestare un flood continuo e molto veloce. Questo sistema inoltre non tiene conto della dimensione dei dati. Un documento da un 1MB potrebbe eliminarne molti altri più piccoli ed un documento da un 1MB dovrebbe essere molto richiesto per compiere la stessa distanza di uno più piccolo. Da ciò nasce l'esigenza di comprimere i file prima di metterli in rete ( dal momento che non possono essere compressi dopo la cifratura ).

Invece di inserire semplicemente un documento in cima alla pila si potrebbe usare un sistema più complicato. A ciascun documento viene asseganto un peso ed in base a quest'ultimo avviene l'ordinamento. Ad esempio: peso = x * (dimensioni_doc / spazio_storage) + y * (numero_di_richieste_doc / numero_totale_richieste ). Dove x e y sono configurabili dall'utente.

Questo fa sì che l'organizzazione dello spazio muti più lentamente e così anche i documenti si muoveranno su è giù per la pila più lentamente, invece di saltare immediatamente in cima. Questo non significa che una lista sia in assoluto la struttura migliore per una COC. I pesi dovrebbero essere ricalcolati per tutte le risorse ad intervalli regolari dal momento che il numero_totale_richieste cambia nel tempo, e possibilmente la COC dovrebbe essere riorganizzata ogni volta che un documento viene richiesto. Mantenere la COC come una lista renderebbe completamente inutile un hash sort (un algoritmo che invece sembrava una buona idea) e rallenterebbe il quick-sort (un altro buon candidato). Per far sì che il tempo di un accesso casuale alle risorse resti basso, ed anche la quantità di dati da maneggiare, un vettore nella forma appare essere la miglior struttura per questo tipo di sistema.

Il diagramma di un array di puntatori

Rimane un punto dove i documenti non contengono dati, ma adesso abbiamo a che fare con un vettore, non con una lista. Il vettore dovrebbe essere ordinato secondo il peso di ciascun documento. Questo sistema è molto più flessibile, e permette che il peso venga influenzato da altri valori (come chi ha firmato il documento).

Trovare documenti vicini

Nè una tabella hash o una COC lista/vettore sono molto adatti a questo compito. Dove il concetto di vicinanza è definito dalla relazione che lega le chiavi. Comunque con le attuali chiavi ad una dimensione la vicinanza può essere definita tra 2 chiavi, invece che solamente tra 3 come emergeva dal report di Ian. Questa situazione muta completamente con chiavi di dimensioni diverse. Purtroppo nello studio per ottenere una routable searching potremmo dover utilizzare tipi di chiavi per i quali questo sistema non funziona. Attualmente sia i nodi java che Whiterose usano questa particolarità per cui se dovessimo cambiare saranno cazzi.

L'idea è sfruttare questa caratteristica per ordinare 2 chiavi e costruire un albero binario. Alla sinistra di ogni documento c'è un ramo contenente i documenti con una chiave più piccola, alla destra gli altri.

Il diagramma di una struttura ad albero

Cercare per esempio una chiave, 8, in questo struttura ad albero risulta sufficientemente veloce. Poiché è un albero binario la ricerca risulta logaritmica -- molto più veloce di una lineare su qualsiasi altro tipo di struttura.

Trovare la chiave più vicina a partire da un albero di documenti è abbastanza veloce, ma trovare chiavi molto esterne potrebbe diventare un poco oneroso. È però possibile costruire una lista di documenti ordinati in base alla chiave (i documenti possono venir inseriti in questa lista attraverso l'albero, il che rende l'inserimento un'operazione piuttosto veloce). In questo modo trovare una lista di chiavi, anche molto esterne, diventa semplice: si tratta di muoversi tra il nodo e la lista. Si tratta di un espediente per ottimizzare velocità e spazio; richiede due puntatori in più per ogni documento.

Il formato dei messaggi

Il formato di un messaggio è semplice. Tutti i messaggi devono transitare sopra un clean channel. Cioè questo non deve cambiare i dati in nessuna maniera. Se il presentation layer non può fare questo è necessario codificare/decodificare i dati in modo che questa operazione venga simulata ( come per le email la codifica base64 ).

I messaggi sono divisi in righe. Il new line è espresso da un singolo carattere di fine riga, le linee sono codificare in UTF-8.

La prima riga è il tipo di messaggio. Seguono una serie di campi chiavi-valore con = come separatore. Quindi c'è un marcatore che segnala la presenza di un trailing feild. Il marcatore può essere sia EndMessage o Data. Nell'ultimo caso il messaggio è seguito da trailing feild. Se c'è un trailing feild deve essere presente un campo numerico detto DataLength che ne indichi le dimensioni in bytes. Segue l'esempio di un messaggio costruito correttamente.

      DataReply
UniqueID=C24300FB7BEA06E3
Depth=a
HopsToLive=2c
Source=tcp/127.0.0.1:2386
DataLength=131
Data
 'Twas brillig, and the slithy toves
Did gyre and gimble in the wabe:
All mimsy were the borogoves
And the mome raths outgrabe.
     

Il messaggio è di tipo DataReply e c'è un trailing feild. Il tipo del valore abbinato ad una chiave viene definito dal nome della chiave. Dove il tipo è numerico il valore è sempre espresso in notazione esadecimale, come si vede per il campo HopsToLive. Gli indirizzi vengono espressi nella forma transport/address. Il solo protocollo di trasporto accettato per il momento è tcp e gli indirizzi IP vengono espressi nella forma ip:porta, come mostrato nel campo Source. Il numero di porta non è opzionale, dal momento che in Freenet non c'è una porta di default.

Grammar format

Segue una specifica più precisa per il formato dei pacchetti descritti sopra.

    OCTET = < 0x00..0xFF >
    CHAR = < 0x20..0xFF >
    ALPHA = < 0x40..0x59, 0x60..0x79 >
    DIGIT = < 0x30..0x39 >
    LF = < 0x0A >

    NewLine = LF
    SubFieldName = ALPHA *(ALPHA or DIGIT)
    FieldName = SubFieldName *(``.'' SubFieldname)
    FieldValue = *CHAR
    MessageType = FieldName NewLine
    HeaderField = FieldName ``='' FieldValue NewLine
    EndMessage = ``EndMessagè' NewLine
    TrailingName = ``Datà' NewLine
    Payload = *OCTET
    MessagePacket = MessageType
                    1*HeaderField
                    EndMessage or (TrailingName Payload)
     

Headers

Ci sono diversi campi che compaiono in diversi tipi di messaggi. Il loro significato generale è spiegato qui di seguito, ma è possibile che cambi a seconda del tipo di messaggio.

UniqueID

Contiene 64 bit che identificano il messaggio associato. Quando effettuiamo il forward di un messaggio, quest'ultimo eredita lo UniqueID. Questo serve ad evitare la formazione di loops all'interno della rete. Il campo UniqueID viene riempito con un valore casuale dal nodo che genera la catena. In un dato momento ciascuna catena di messaggi viene identificata da un proprio UniqueID, anche se questo potrebbe non essere vero col passare del tempo.

HopsToLive

È un campo numerico e si comporta come il TTL dei datagrammi IP. Ogni nodo che rigira il messaggio diminuisce di 1 l'HTL. Se un messaggio ha HTL pari ad 1 non può essere forwardato ed esiste un comportamente speciale previsto per questo casi. Ricevere un messaggio con HTL pari a 0 genera un errore.

Depth

Il campo Depth viene utilizzata per tracciare quanto un messaggio si è allontanato dalla propria origine. In qualche modo è l'inverso del HTL, in quanto è un valore numerico che viene incrementato ogni volta che il messaggio viene forwardato. La principile differenza sta nel trattamento dei cicli. Quando una richiesta raggiunge un nodo che era già stato visitato, quest'ultimo avvisa il nodo immediatamente prima di questa condizione, e questo nodo sceglie un'altra destinazione a cui passare la richiesta originale. Per ciascuno di questi due hops, HTL viene modificato, ma la Depth no.

KeepAlive

Il campo KeepAlive può contenere il valore true o false. Se viene omesso il nodo assume che sia true. Se invece è false il nodo che spedisce il messaggio dovrebbe chiudere la connessione dopo l'invio del messaggio.

Source

Identifica la sorgente del messaggio. I messaggi dovrebbero sempre avere un campo source, se possibile. Dal momento che Freenet utilizza un protocollo basato su messaggi i nodi possono chiudere le connessioni inattive, nella maggior parte dei casi, e riconnettersi con la sorgente quando risponde. Il campo source è nel formato dell'indirizzo e dovrebbe contenere un indirizzo al quale il nodo possa connetersi. Nel caso del TCP dovrebbe anche avere il numero di porta a cui connetersi. Un nodo non dovrebbe mai inserire un IP differente da quello da cui sta effettivamente spedendo, e le porte dovrebbero essere oltre la 1024. Tutti questi test sono a carico dei nodi stessi.

Alcuni nodi non possono specificare una sorgente perché non vogliono essere ricontattati, o sono dietro ad un firewall che blocca le connessioni in entrata. Questi nodi dovrebbero omettere il campo Source ed intraprendere delle azioni particolari. Datosi che due messaggi non possono buttare giù la stessa connessione nello stesso momento, questi nodi sono soliti aprire una nuova connessione per ciascun messaggio tale da generare molto traffico in risposta. Se un nodo rivece un certo numero di messaggi che cervano di buttare guì la stessa connessione li dovrebbe inseire in una cosa, o a sua discrezione anche ignorarli. Questo connessioni non possono essere essere chiuse semplicemente perché non sono più attive, ma vengono di solito terminate da un messaggio KeepAlive=false.

Storable

Iniziano con la stringa Storable, sono delle stringhe di testo in formato libero. Quando immagazzina un documento un nodo deve anche mantenere tutti i campi Storable ed i messaggi di DataReplay generati dovranno a loro volta contenerli tutti.

Alcuni campi vengono interpretati dai nodi (ad esempio Storable.Public-key viene utilizzato da alcuni tipi di chiavi).

Tipi di Messaggi

HandshakeRequest

Il messaggio HandshakeRequest dovrebbe essere mandato dopo la connessione. Permette ai nodi di testare se un altro sia attivo o meno e se le versioni del protocollo coincidano.

Quando un nodo invia un HandshakeRequest deve generare uno UniqueID casuale, L'HTL e Depth devono essere ad 1. Il campo Source dovrebbe essere riempito.

Quando un nodo riceve un HandshakeRequest deve rispondere con un HandshakeReply.

HandshakeReply

Un HandshakeReply viene spedito in risposta ad un HandshakeRequest.

Lo UniqueID viene ereditato dal HandshakeRequest, HTL e Depth dovrebbero essere posti ad 1. Tre campi extra - Version, Build e Revision dovrebbero essere inzializzati con i valori di ciascun nodo. Attualmente i valori si trovano all'inizio di Core.java.

Se si riceve un HandshakeReply non desiderato (ad esempio senza aver inviato una richiesta) non bisogna rispondere ed ignorarlo oppure salvare da qualche parte l'indirizzo di provenienza.

DataRequest e InsertRequest

Questi due messaggi sono molto simili saranno trattati insieme. In questi messaggi deve essere presente un campo SearchKey con una una chiave espressa in esadecimale. Quando riceve il nodo dovrebbe cercare all'interno del suo data store un documento corrispondente a quella chiave. Se esiste replica con un messaggio di DataReply con il documento nel body.

Se il documento non viene trovato si dovrebbe inoltrare la richiesta. Se il messaggio scade ( HTL giunge a 0 dopo il decremento ), viene spedito il messaggio appropriato. Nel caso di una DataRequest un messaggio di TimeOut, nel caso di un InsertRequest un InsertReply.

Nel caso che si risponda con un InsertRequest si dovrebbe registrare il fatto ed attendere un messaggio DataInsert con lo stesso UniqueID contenuto nel documento relativo alla SearchKey.

DataReply and DataInsert

Di nuovo questi messaggi sono simili e quindi verranno trattati insieme. Questi messaggi sono gli unici che possiedono dei trailing feilds, e per entrambi sono campi obbligatori. Quando si inoltrano questi messaggi si dovrebbe mantenere in cache il trailing feild e inserirlo nel proprio data store.

Dal momento che hanno dei trailing feilds devono anche contenere un campo DataLength, ed avranno di solito un campo Storable che si deve mantenere in cache.

Il campo SearchKey non è utilizzato, oppure i nodi devono riconoscere la chiave dal confronto tra gli UniqueID delle precedenti InsertReply o DataRequest. Se un nodo "dimentica" lo UniqueID potrebbe mantenere in cache i dati.

QueryRestarted

Questo messaggio indica che un nodo ha rifatto una richiesta e dunque si deve rinizializzare il timeout.

Cryptographic Link Layer

Lo scambio di chiavi avviene attualmente utilizzando il Diffie-Hellman ( Applied Cryptography, capitolo 22 ). Ciò che segue è ripreso da Applied Cryptography.

La parte matematica è semplice. Primo, Alice e Bob si accordano su un numero primo molto grande, n, e su un g tale che g ed n siano primi tra di loro. Questi due interi non devono essere segreti; Alice e Bob possono concordare i loro valori anche su di un canale insicuro. Può anche essere condiviso tra un gruppo di utenti. Non ha importanza.

Quindi, il protocollo diventa qualcosa del genere

  • Alice sceglie un intero x piuttosto grande ed in maniera casuale e lo spedisce a Bob: X = gx mod n
  • Bob sceglie un intero y piuttosto grande ed in maniera casuale e lo invia ad Alice: Y = gy mod n
  • Alice calcola: k = Yx mod n
  • Bob calcola: k' = Xy mod n

Sia k che k' sono uguali a gxy mod n. Nessuno ascoltanto il canale di comunicazione può calcolare il valore; i soli termini noti sono n, g, X e Y. A meno di riuscire a calcolare il logaritmo discreto e recuperare x e y, non è possibile risolvere il problema. Dunque k è la chiave segreta che sia Alice che Bob possono calcolare indipendentemente.

Freenet usa un n predefinito a 1024 bit, un numero primo definito nello standard per IPSec

FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
FFFFFFFF FFFFFFFF
   

Il genratore (g) è 2. Quando spedisci, calcoli un hash, ecc... MPI (multi-precision-integers) vengono definiti come da specifiche dell'OpenPGP.

MPIs

Gli interi Multi-precision( anche detti MPIs) sono interi senza segno usati per manipolare numeri interi molti grandi come quelli usati nei procedimenti crittografici.

Un MPI si compone di 2 parti: una sclare di 2 ottetti che rappresenta la lunghezza in bits del MPI seguito da una stringa di ottetti che contiene il valore vero e proprio.

Questi ottetti formano un numero in formato big-endian; un numero big-endian può essere trasformato in un MPI anteponendo ad esso un prefisso con la lunghezza appropriata.

Per esempio:

La stringa di ottetti [00 01 01] è un MPI con valore 1. La stringa [00 09 01 FF] è un MPI con valore 511. Le dimensioni di un MPI si calcola con la fromula ((MPI.length + 7) / 8) + 2 ottetti. Il campo lenght rappresenta la lunghezza partendo dal bit più significativo che non sia a zero. Dunque, l'MPI [00 02 01] non è corretto. Dovrebbe essere [00 01 01].

Block Cipher Key Generation

Si calcola un valore hash(SHA1) di e e k(dove k è in formato MPI). e è un array di m ottetti di 0x00, inizialmente m = 1. Ciascun passaggio della funzione hash genera 20 ottetti di dati per la chiave. La lunghezza della chiave dipende dal cifrario a blocchi utilizzato ( attualemente Rijndael). Per generera più dati èsufficiente incrementare m, rigenerare e ficalcolare l'hash. Per esempio:

Hash [0 k] per i primi 20 bytes (e = [0] poiché m = 1)
Hash [0 0 k] per i successivi 20 bytes (m = 2)
Hash [0 0 0 k] per i successivi 20 bytes (m = 3)

Ora entrambi le parti possiedono la chiave condivisa per scambiarsi dati in PCFB mode.

PCFB Mode

PCFB mode significa Periodic Cipher Feedback Mode. Ciascuna direzione viene trattata come un oggetto differente. Il codice è lo stesso ma abbiamo due insiemi di dati, uno per la trasmissione, l'altro per ricezione. Di seguito viene descritto solo una parte, ma il processo è valido per entrambe. Il vantaggio del PCFB è poter spedire un solo byte alla volta.

Viene creato un feedback register, a[]. Nel codice Java viene chiamato feedback_register[]. Il registro ha le stesse dimensioni del blocco utilizzato per cifrare. Si riempie a[] con una seire di bytes casuali e lo si trasmette all'altra parte. Questo diviene il vettore d'inizializzazione (IV). L'altra parte inserisce questi dati nel proprio a[], quindi entrambe le parti cifrano a[], rimpiazzando il vecchio valore con il nuovo cifrato.

Per trasmettere un byte verrà effettuato un XOR con un byte preso da a[] e quindi rimpiazzato il byte in a[] con byte cifrato. Per riempire il buffer di trasmissione t[] a partire da un testo p[] in chiaro effetueremo:

for (i = 0; i < BLOCKSIZE; i++) t[i] = a[i] = p[i] XOR a[i];

L'altra parte può ora decifrare t[] effettuando un XOR con a[], e quindi rimpiazzare a[] con t[]. In altre parole, entrambe le parti inseriscono i dati cifrati nel feedback register, a[]. Entrambi necessitano di un puntatore (i nel codice sopra illustrato) che indichi la posizione nel registro.

Dopo che si è trasmesso un blocco è necessario ricifrare il registro a[], per ottenere quello nuovo. Si noti che il cifrario a blocchi viene utilizzato sempre in modalità di cifratura sia per nella fase di cifratura che di decifratura. Si procede quindi con la ricifratura di a[].

Sommario PCFB

Spedire dati

  • Creare un buffer, detto feedback register di lunghezza uguale al blocco utilizzato dal cifrario simmetrico utilizzato in PCFB mode.
  • Creare un vettore di inizializzazione contenente valori casuali, IV, e spedirlo all'altra parte, quindi cifrarlo ed inserire il risultato nel feedback register.
  • Per trasmettere un byte effettuare XOR di un byte del plantext con un byte del feedback register, quindi inserire il byte risultante nel feedback register al posto del bytes usato per l'XOR.
  • Trasmettere il byte.
  • Quando ogni byte nel buffer è stato spedito (e sostituito dal corrispondente byte cifrato), cifrare il feedback register, per ottenere un nuovo registro per la trasmissione.

Receiving

  • Ricevuto il vettore d'inizializzazione dall'altra parte, cifrarlo, ed inserire il risultato nel feedback register
  • Quando un ciphertext viene ricevuto dall'altra parte, effettuare l'XOR con un byte del feedback register per ottenere un byte in chiaro. Quindi porre il byte cifrato nel feedback register.
  • Quando l'intero feedback register è stato utilizzato, ricifrare e porre il risultato nuovamente nel feedback register, ottenendo così un nuove registro per la ricezione.

Chiavi

Cancer

Le chiavi forniscono un modo per fermare i nodi maligni che rispondono con dati errari. Perché questo funzioni ogni nodo deve controllare i dati che riceve. La catena di nodi che costituiscono una sorta di tunnel per la comunicazione necessitano di un qualche sistema per segnalare che qualcuno a trovato un nodo maligno.

Per questo vengono utilizzati dei bytes di controllo. Ciascun tipo di chiave effettua il controllo in maniera diversa, ma in generale si utilizzano due messaggi. CB_OK indica che i nodi precedenti ritengono i dati validi CB_RESTART il contrario ed impone la replica della richiesta.

Quando riceve CB_RESTARTED un nodo dovrebbe arrestare il processo di tunneling verso gli altri ed attendere che venga spedito un nuovo messaggio. Dovrebbe inoltre notificare un CB_RESTARTED ai nodi precedenti il più in fretta possibile.

CHK (Content Hash Key)

Un CHK è semplicemente un hash SHA1 di un documento e quindi un nodo può controllare che il documento restituito sia quello giusto calcolando l'hash e confrondandolo con la chiave.

Questa chiave è il succo dei dati presenti in Freenet. Una CHK è unica per definizione e prova l'integrità del contenuto dei file. Un cancer node che sporca i dati sotto una CHK viene immediatamente scoperto dal prossimo nodo o dal client. Le CHK riducono inoltre la ridondanza dei dati poiché agli stessi dati corrisponderà una stessa CHK e la collisione sarà individuata all'inserimento.

Però è possibile controllare l'hash solo se si possiede l'intero documento. Questo è buono per piccoli documenti, ma per i più grandi potrebbe essere un inutile spreco di banda effettuare il download dell'intero documento solo per provare che non sia stato alterato.

Una CHK progressiva permette di controllare il documento ad ogni passo, dunque eventuali problemi possono essere scoperti nel momento in cui si incontra il blocco di dati errato.

FIXME - CITE HERE

La lunghezza di un blocco è contenuta nell'header Storable.PartSize. Quando arriva uno stream di dati effettuiamo le seguenti operazioni.

  • check_hash assume il valore della CHK. Poi per ciascun blocco
  • Leggiamo nel campo PartSize il numero di bytes di dati, e diciamo questa parte block_data. Per l'ultimo blocco potrebbe non esserci una quantità di dati pari a PartSize. In questo caso leggiamo comunque i bytes rimasti e poniamo PartSize a quel valore.
  • Leggiamo in un hash. Nel caso di un SHA1 questo significa 20 bytes (160 bits), e lo chiamiano temp_hash
  • Leggiamo un byte, il byte di controllo. Se è 0x00 (CB_OK) allora procediamo. Se è 0x01 (CB_RESTARTED) allora un nodo precedente ha riscontrato un errore. Usciamo dal tunnel mode e ritorniamo nel message parsing mode. Attendiamo un messaggio QueryRestarted.
  • Effettuiamo l'hash di block_data e temp_hash e poniamo che l'hash sia uguale check_hash. Se così è procediamo. Altrimenti spediamo 0x01 come byte di controllo a tutti i nodi client insieme ad una QueryRestarted. Il nodo che ha spedito i dati può essere visto come un nodo maligno.
  • Copiare temp_hash in check_hash

SVKs, SSKs e KSKs

SVKs (Signature Verification Keys), SSKs (SVK Subspace Keys) e KSKs (Keyword Signed Keys) sono tutte basate sulla crittografia a chiave pubblica e saranno trattate insieme. Attualmente Freenet utilizza il DSA per queste operazioni.

Dal punto di vista del protocollo, una KSK è un insieme ristretto in una più generica chiave SVK. SVK corrisponde al valore 0x0201 e KSK 0x0202. Una KSK si differenzia per il fatto che la coppia di chiavi viene generata da una stringa e quindi rimpiazza le chiavi KHK.

Le SSK sono semplicemente la rappresentazione client-side di una SVK più il nome del documento. Ciò che permettono di fare è creare un semplice sotto insieme in Freenet con chiavi predicibili, ma conservando il controllo sull'inserimento.

Quando si irceve un DtaReply per una di queste chiavi è nbecessario controllare il campo Storable.Public-key per produrre questa chiave.

I dati sono in un unica parte delle dimensioni di DataLength. Al termine viene inserito un carattere di controllo. Prossimamente le dimensioni di queste chiavi saranno limitate. Una volta ricevuti i dati, è necessario aggiornare un hash SHA1 di quest'ultimi. Ponendo di avere DataLength-1 bytes, generiamo l'hash. Quindi controlliamo la firma in Storable.Signature usando Storable.Public-key. Questo contiene dei valori in formato MPI senza i 2 bytes che segnalano la lunghezza, ed espressi in esadecimale (es. a3bc32...). La lunghezza non è indicata perché è nota e coincide con la lunghezza della stringa. Storable.Signature contiene 2 MPI separati da un punto. Nel sistema di firma DSS vi sono un r ed un s. SVK e KSK hanno dei moduli di default comuni differenti. Vengono detti GruppoA (per le KSK) e GruppoB (per le SVK).

Gruppo A:

p =
b9850e5e9607d50d000000000000000000000000000000000
00000002cdc65f1e9a7dccb571627333dd0520bf0deb206d7
c2937330a7d6e73cec4928b172c7e8ea04cc075d18db1340d
ac2065cbce69c5ff20b4bca2d89d2932204149a3b6811be27
458e7d2518edf9bf4417acb1e79243fe6ae1eac68cef6d655

q =
cfabfbd9fa4661010d9d11d0c381bb574da72667

g =
2668d2935bdd27dad0a1f469c69c6f7e7bd5a3ea73adc6bc0
a781c0a276993a0cdbb575635423744dd2e2fbd7e962ac5b4
b79632f030ddef166c53cb002f692e2fd927f17e3e6bd404f
573207557972c630c01e6cc8b37fb348ad2686f4b4e3e681d
9ced93cde9f30a2f17380204274141dce60c6151ef1b7acd0
39ab1227fcd     
     

Gruppo B:

p =
c9381f278f7312c7fffffffffffffffffffffffffffffffff
fffffffa8a6d5db1ab21047302cf6076102e67559e1569484
6e3c7ceb4e18b6c652aedcfb337af057bdc12dcfc452d3ae4
cfc5c3b7586804d4983bd5370db5512cf313e9a2c9c138c60
2901135c4cfbcbe92d29fe744831f63e3273908c4f62f2129      

q =
c88fa2a0b1e70ba3876a35140fddce3c683706ad      
    
g =
65d3ccb70df16dc08822be40736bf951383f6c03ddfd51c1a
41627fafb2b7f74a1e65ade0ab9f7c189c497cfb6fe6e9e7b
a4160d7fd15bae68bff0e4a96f412e85924bcc89fee431406
13afd124f425f891a2d3022f0a0444692e510fc5310360a21
e3f729ab93f2ad81b0bbe27d86bc65cf385036969ede2473e
     

Solo per le SVK potrebbe esserci un campo Storable.Group che sovrascriva i valori di default. Questo contiene tre MPI (senza lunghezza, ed in esadecimale) che divengono p,q e g nel DSS. Sono separati da punti.

Se il byte di controllo è CB_RESTARTED significa che un nodo precedente ha segnalato che i dati contengono degli errori. Quindi si torna in message mode e si attende un QueryRestarted. Se il byte di controllo è a CB_OK e le firme vengono verificate correttamente, si spedisce un CB_OK al prossimo nodo della sessione tunnellata. Se CB_OK è corretto, ma la firma è sbagliata, si ferma la trasmissione e si spedisce un CB_RESTARTED, quindi si ripete la richiesta. Non si dovrebbe più contattare il nodo che ha provocato l'errore.

Generare chiavi KSK e SVK

  • Per le KSK è sufficiente effettuare l'hash con SHA1 della chiave di descrizione in formato UTF-8 per ottenere 160 bit da utilizzare come chiave privata, x. Il resto della procedura è analogo alle chive SVK.
  • Generare la chiave pubblica y = gx mod p
  • Solo per le SVK Se un nome di documento è gia presente, calcoliamo l'hash con SHA1 and add the stor\-able Storable.- Document-name with that value.
  • Si calcoli l'hask della chiave pubblica in formato MPI binario. Se si tratta di una chiave SVK ed è presente un nome di documento calcoliamo l'hash anche di quest'ultimo e verrà inserito nella chive stessa.
  • Si cifri la parte dati. Per una SVK generiamo una chiave casuale. Per una KSK usiamo come input per l'algoritmo di generazione dei bytes presi da tasiera in formato UTF-8.
  • Firmiano l'hash dei dati cifrati con DSA, producendo r ed s.
  • Solo per le SVKÈ possibile utilizzare un gruppo DSA apposito. Vedi sopra. Se si utilizza un gruppo apposito è necessario inizializzare Storable.Group come indicato precedentemente. Altrimenti si usi il gruppo B
  • Solo per le KSKSi usi il gruppo A per calcolare la firma.
  • Aggiungere Storable.Signature contenente r ed s in formato MPI esadecimale.
  • Aggiungere il tipo alla chiave che si è calcolata. Per SVK è 0x0201, per KSK è 0x0202.
  • Aggiungere un byte null (0x00) ai dati cifrati come byte di controllo CB_OK per indicare la validità del pacchetto.
  • Insert the data under that key, with the storables accumulated, and the encrypted data. Note that document encryption should proceed as outlined in the document-encryption (end-to-end) specs.

Glossario

  • Vicinanza Una relazione tra 3 chiavi nella quale si afferma che "A è più vicina a B di quanto lo sia a C". Dal momento che questo tipo di confronto viene utilizzato per indirizzare le richieste è importante che tutti i nodi usino la stessa relazione per le diverse chiavi.
  • Clustering L'effetto per cui i dati con chaivi vicine ( secondo le relazione di vicinanza scelta ) vengono ordinate negli stessi nodi della rete. Il clistering è fondamentale per rendere le richieste veloci e scalabili. Ma è anche dannoso: se la vicinanza tra le chiavi riflette una qualche similitudine all'interno del contenuto del documento ( ad esempio potrebbe accadere per chiavi calcolate su testo in chiaro in inglese ), troppi documenti di una stesso genere verrebbero centralizzati su pochi nodi, rendendo il sistema vulnerabile.
  • Document Dei dati uniti ad una chiave. A chuck of data linked to a key. Inserting data into Freenet may lead to the insertion (or updating) of more than one document.
  • Tunneling Il sistema che si usa per inoltrare i messaggi prima di averli ricevuti completamante. È molto importanti riuscire a ridurre la latenza.
  • DSA The Digital Signature Algorithm\refcite{2. Una variante degli algoritmi di firma di Schnorr and ElGamal.

Riferimenti

[1] Gennaro, R and Rohatgi, P; ``How to Sign Digital Streams'', Advances in Cryptology -- CRYPTO '97, 1997.

[2] U.S. National Institute of Standards and Technology, NIST FIPS PUB 186, ``Digital Signature Standard'', U.S. Department of Commerce, May 1994

Il materiale contenuto in questo sito è distribuito sotto la Gnu Documentation License , disponibile anche qui in italiano.