Appendice A - Protocolli Anti Collisione

Sono protocolli che evitano la “collisione” tra comunicazioni di diversi tag verso uno stesso reader. Esistono due grandi famiglie: i protocolli deterministici e quelli probabilistici.

Protocolli Deterministici (Tree-Walking) 

• Sono basati su di un albero di ricerca binario che rappresenta tutti gli identificatori statici (di lunghezza l) dei tag.

• Un nodo alla profondità d in questo albero può essere unicamente identifificato da un prefisso binario b₁b₂…b_d

• Il reader inizia dalla radice dell’albero ed esegue una ricerca in profondità: al nodo b₁b₂…b_d, il reader interrogherà tutti i tag il cui numero seriale appartiene a questo prefisso, gli altri restano silenti.

• I tag replicano con i d + 1-st bit del loro numero seriale.

• Se due tag trasmettono due diversi bit, il protocollo eseguirà una doppia ricerca in profondità, prima alla ricerca dei tag che hanno risposto con '0', poi nel sottoalbero dei tag che hanno risposto con '1'.

• Se i tag rispondono con lo stesso bit, invece, il protocollo eseguirà una sola ricerca in profondità nel sottoalbero indicato dal bit trasmesso.

• Quando un algoritmo raggiunge una foglia, ha trovato un tag.

Figura 9: Esempio di  albero di ricerca binario

Il protocollo deterministico più usato è il "Singulation Tree-Walking" che si basa proprio sui concetti sopra esposti. Esso, infatti, esegue una visita in profondità dell'albero esaminando bit a bit i valori degli identificativi dei tag.

Figura 10: Ricerca nell'albero dell'identificativo 001

Nella figura di sopra l'albero di profondità 3 ha 2³ = 8 foglie, ognuna delle quali rappresenta l’identificativo ID di un tag. Supponiamo che i tag presenti, nel momento in cui il reader vuole effettuare una lettura, siano quelli indicati dalle foglie rappresentate con i cerchi rossi ovvero i tag con ID '001', '011' e '110'. In corsivo, sono denotati i prefissi associati ai sottoalberi. Il primo tag che la procedura Tree-walking raggiungerà sarà quello il cui ID è '001'. Nei nodi evidenziati con un cerchio tratteggiato, vale a dire la radice dell'albero e la radice del sottoalbero dei tag con prefisso '0', si verificano delle collisioni dovute alla trasmissione del bit da parte dei tag. Infatti, alla radice dell'albero, il protocollo riceverà due bit '0' ed un bit '1'. A causa di questo verrà eseguita prima una ricerca nel sottoalbero di sinistra, ma nel nodo il cui prefisso è '0', l'algoritmo vedrà arrivare un'altra volta un bit '0' ed un bit '1'. Seguendo sempre e prima il sottoalbero di sinistra, il protocollo recupererà il tag con ID '001'. Successivamente, eseguendo altre due ricerche in profondità, ma nei sottoalberi di destra, il protocollo raggiungerà gli altri due tag.

Con i protocolli deterministici un’attaccante non ha problemi a tracciare il tag poiché l’identificatore è statico. La soluzione più semplice è di rinnovare l’identificatiore ogni volta che il tag è riconosciuto da un reader, ma, ovviamente, questo comporterebbe una ristrutturazione dell'albero di ricerca.

Protocolli probabilistici (Aloha)

• L’accesso al canale di comunicazione è diviso in “time slots”.

• Il numero di slots è scelto dal reader che informa i tag che essi hanno n slots per rispondere.

• Ogni tag, casualmente, sceglie uno tra gli n slots e risponde non appena questo arriva.

• Se n non è sufficientemente grande, può esserci una collisione.

• Per recuperare le informazioni perse, il reader interroga i tag una volta in più. Può "zittire" i tag che non sono coinvolti nella collisione indicando i time slots che hanno usato per trasmettere.

Con protocolli probabilistici, l’attaccante può tracciare il tag se risponde sempre durante lo stesso time slot. È necessario un PRNG crittograficamente sicuro che dia, ad ogni sessione, un time slot casuale ad uno stesso tag.

Esempi di Protocolli di comunicazione

Protocolli adatti per Tag di Classe 1

L’idea alla base è che ogni volta che un tag viene interrogato, le informazioni inviate vengono rinnovate con l’aiuto del reader.

Sono resistenti alla tracciabilità solo con limitati modelli di avversari. Questi protocolli non soddisfano da un punto di vista accademico, ma sono comunque utili nella pratica poiché riducono le capacità degli attaccanti.

Figura 11: Un protocollo per tag di classe 1: modifica dei dati

Protocolli adatti per Tag di Classe 2

È basato su una challenge-response. Quando un tag viene interrogato, manda indietro un’informazione che permette al sistema di recuperare il suo identificatore. Questa informazione viene aggiornata ogni volta che un tag viene interrogato. Inoltre essa può essere vista come uno pseudonimo.

Figura 12: Un protocollo per tag di classe 2

Protocolli basati su crittografia

Ovviamente esistono anche altri sistemi di comunicazione, molti di questi sono stati creati usando degli standard comuni di crittografia (Hash, AES). Di seguito ne verranno indicati due tra i più famosi. Tutti questi protocolli hanno una complessità lineare nell’ordine di identificazione del tag.

In base al rapporto sistema / tag presenti, l’identificazione richiede complessità asintotiche diverse:

• One system / one tag (eg. Chiave di accensione auto): Identificare un tag richiede O(1) operazioni

• One system / n tag (eg. biblioteca): Identificare un tag richiedes O(n) operationi (ricerca esaustiva) ed identificare l’intero sistema richiede O(n²) operazioni

Protocollo Weis, Sarma, Rivest e Engels

Il tag invia al reader un valore che è pari all’hash del suo ID e di un dato valore b che sia tag che reader dovrebbero conoscere. Tale sistema viene anche definito come Hash-Lock.

Figura 13: Protocollo di Weis, Sarma, Rivest e Engels

Protocollo di Feldhofer, Dominikus, Wolkerstorfer

È un esempio di Challenge-Response:

• Il reader sceglie un valore a che viene inviato al tag. Il tag gli assocerà un secondo valore b e cifrerà entrambi usando AES con una chiave a 128 bit nota anche al reader.

• Il tag manderà il risultato della cifratura al lettore il quale, sapendo sia la chiave K che a, riuscirà ad ottenere b. Successivamente re-cifrerà sia a che b, ma in ordine inverso, ed invierà il risultato al tag il quale dovrà verificare se i valori di a e b siano quelli giusti semplicemente decifrando il nuovo messaggio[16].

Figura 14: Protocollo di Feldhofer, Dominikus, Wolkerstorfer

Silent Tree-Walking

Weis ed altri hanno notato che la minaccia proveniente dagli eavesdroppers passivi deriva soprattutto dalla loro capacità di intercettare i segnali trasmessi dal reader. Infatti, anche se un reader può leggere soltanto i tag ad esso vicino a causa del loro corto raggio di azione (per esempio 3 metri ), il canale reader-to-tag o "forward channel"  trasmette un segnale abbastanza forte con un raggio d’azione lungo centinaia di metri. Il canale tag-to-reader o "backward channel", invece, è più debole e può essere controllato dagli eavesdroppers soltanto all'interno di un più ridotto campo di azione. In generale, si suppone che gli eavesdroppers possano controllare, senza essere scoperti, solo il forward channel. Questa situazione è illustrato nella figura sottostante: 

Figura 15: Range di azione di Tag, Reader ed eavesdropper

Pertanto per un eaveasdropper è più facile catturare i segnali che vanno dal reader al tag che quelli dal tag al reader. Ciò è sfavorevole in quanto gli ID raccolti dal protocollo di singulation Tree-Walking possono essere dedotti semplicemente ascoltando i segnali del lettore.

Weis mostra come cifrare le trasmissioni del reader in modo che un eavesdropper passivo non possa ottenere gli identificativi dei tag letti. Tale variante del protocollo deterministico Tree-Walking è nota come Silent Tree-Walking.

Il reader attraverso il backward channel potrà sentire le risposte del tag, mentre l’eavesdropper no. In questo modo il lettore e il tag condividono un segreto ovvero il valore del bit. Se non ci sono collisioni, il lettore può chiedere semplicemente il bit seguente, poiché tutti i tag hanno lo stesso valore per il bit precedente. Se invece si verifica una collisione, il lettore deve specificare quale parte dell’insieme dei tag deve continuare. Poiché abbiamo presupposto che i codici identificativi dei tag abbiano un prefisso comune, il reader può ottenerlo sul backward channel. Il prefisso comune e segreto può essere usato per nascondere il valore della parte unica dell'ID. Supponiamo di avere due tag i cui valori ID siano rispettivamente e _. Il reader riceverà b₁ da entrambi i tag e poi scoprirà una collisione sul bit successivo. Poiché b₁ è segreto, in quanto non è svelato all’eavesdropper, il reader può inviare sia che per individuare il tag desiderato senza rivelare altri bit.

Figura 16: Esempio di Silent Tree-Walking

Nella figura di sopra i valori dei due tag sono rispettivamente 01 e 00. Il reader riceve 0 da entrambi i tag. Poiché la lettura di questo primo bit non produce alcuna collisione, se ne deduce che i tag presentano lo stesso valore in tale bit. Questo valore rappresenta il segreto condiviso da lettore e i tag. A questo punto il reader chiede ai due tag il bit successivo e su di esso scopre una collisione. Poiché 0 è segreto, il reader per identificare il tag 01, invia “L'ultimo bit ricevuto” “Tag 01” = 0 1 = 1. Pertanto il tag 01 prosegue nell’esecuzione del protocollo, mentre il tag 00, ombreggiato, si ferma.

Un eavesdropper entro il raggio d’azione del backward channel può ovviamente ottenere l’intero ID. Lo schema silent tree-walking effettivamente protegge il forward channel da eventuali eavesdropper con una piccola complessità aggiuntiva: la sua prestazione è identica al protocollo tree walking standard, in quanto un tag è selezionato quando ha trasmesso per intero sul backward channel il suo ID.

I reader possono approfittare dell'asimmetria tra backward e forward channel per trasmettere altri valori sensibili. Supponiamo che un reader debba trasmettere il valore v ad un certo tag. Quest’ultimo può generare un valore casuale r come one-time-pad e trasmetterlo in chiaro sul backward channel. Il reader può ora inviare v r sul forward channel. Se gli eavesdroppers sono al di fuori del backward channel, essi potranno captare solo v r e v sarà un’informazione teoricamente sicura [22].