Analisi Statica di Circuiti per la Sicurezza
candidato: Riccardo Bresciani
relatore: Prof. Luca Fanucci
Corso di Laurea Specialistica in Ingegneria Elettronica Nuovo Ordinamento
Anno Accademico 2010–2011
18 Luglio 2011
DÉLÉG ATI ONGÉNÉRA LE P OU R L’AR M E M ENT La DGA,
partenaire des armées pour bâtir la défense de demain
�������������������������������������� ��������� ������ ������
&
Stage presso LSV (ENS-Cachan), sotto la supervisione di Jean Goubalt-Larrecq (LSV, ENS Cachan & CNRS & INRIA), in collaborazione con David Lubicz (IRMAR, Université de Rennes 1 & DGA) e Nicolas Guillermin (DGA).
Motivazione
(I)Lo scopo di questo lavoro
Identificare una metodologia volta a verificare proprietà di sicurezza in dispositivi elettronici tramite analisi del relativo codice VHDL. L’elettronica pervade la quotidianità ed è diventata fondamentale per una vasta gamma di attività, incluse quelle che richiedono garanzie che i dispositivi utilizzati siano adeguati in termini di sicurezza.
Esempi controllo di accesso chiavi hardware smart card decoder Sky lettori dvd . . .
Motivazione
(II)Prestazioniººº
applicazioni più impegnative richiedono una maggiore complessità;
maggior numero di componenti ed interconnessioni;
maggior numero di LoC.
Affidabilit຺º
fondamentale in applicazioni critiche;
diversi tipi di affidabilità.
Time-to-market»»»
efficienza di sviluppo;
gli errori costano. La complessità circuitale è in continuo aumento. . .
Metodi formali
(I)L’utilizzo di metodi formali permette di rispondere a queste necessità.
Unsistema formaleè costituito da
proposizioni: siamo interessati alle
proposizioni derivabili (teoremi), tramite
regole di inferenza, a partire da un
insieme di proposizioni assunte come
vere (assiomi).
Dato un sistema del quale si vogliano studiare le proprietà, lo studio tramite metodi formali parte dalla costruzione di
unmodellodel sistema: ragionando su di
esso vengono inferite le proprietà del modello, e quindi del sistema — se il modello è adeguato.
Metodi formali
(II)La descrizione di un dispositivo in VHDL è a tutti gli effetti un suo modello e quindi possiamo ragionare su di esso (o su un modello ad esso equivalente per gli aspetti di interesse).
Perché usare modelli è cosa buona e giusta
Un modello è fondamentale per: identificare i requisiti del sistema;
aiutare l’utente a comprendere le funzionalità del sistema; simulare il sistema;
verificare formalmente il sistema; sintetizzare automaticamente il sistema.
Metodi formali
(III)Storicamente ci sono stati molti preconcetti contro i metodi formali, che tuttavia sono in fase di superamento.
Perché usare metodi formali è cosa buona e giusta: due esempi
bug dell’Ariane 5 — perdita: circa 500 M$;
bug nella FPU del processore Pentium — perdita: circa 475 M$.
“I test mostrano la presenza di errori, non la loro assenza.” [E.W.Dijkstra]
L’applicazione di metodi formalidimostrache il sistema implementa
Processo di design con VHDL
L’importanza della verifica formale in elettronica
Elevata — il 70% delle risorse sono spese nella verifica.
Specifica Documentazione Cattura Verifica Implementazione Codice VHDL
Sviluppo test bench Sintesi Layout Simulazione funzionale Simulazione temporale Fabbricazione ASIC Verifica formale delle proprietà di sicurezza sul codice VHDL
Mai fatto finora
Utilizziamo un approccio
Il dispositivo
INTERNI OUTPUT INPUT • Privato • Pubblico • Da determinareDistinguiamo dati e canali inpubblicieprivati; i canali sono
interconnessi da gate che possono cambiare il tipo di dato che li attraversa.
Richiediamo che dati privati non vengano mai trasmessi su canali pubblici.
Un parallelismo con i protocolli crittografici
L’analisi del dispositivo deve dimostrare che i dati confidenziali contenuti al suo interno non vengano rivelati ad un avversario.
Lo scenario
L’avversario può interagire in qualunque modo (lecito) con il dispositivo al fine di violarne la sicurezza:
può leggere ed inviare dati sui terminali pubblici;
non ha alcun accesso ai terminali privati, né alle connessioni interne (inviolabilità fisica);
ogni blocco che utilizziamo risponde alle sue specifiche; l’avversario può processare le informazioni ottenute per ampliare la propria conoscenza;
nessuna informazione dal comportamento fisico del dispositivo. Questo è esattamente lo scenario che si presenta nella verifica di protocolli crittografici.
Il modello di Dolev-Yao
L’avversario ha il completo controllo della rete
L’avversario ha infinite risorse computazionali
Le primitive di sicurezza sono perfette
I protocolli ammettono qualunque numero di partecipanti e sessioni I messaggi possono essere di qualunque dimensione
Il
π-calculus e ProVerif
È conveniente ricorrere all’algebra dei processi per esprimere il
modello VHDL del dispositivo da analizzare.−→π-calculus
Lavoriamo con un modello del dispositivo, equivalente per quanto concerne gli aspetti di sicurezza e con il vantaggio di permetterci l’utilizzo di strumenti progettati per la verifica di protocolli criptografici.
ProVerif
A partire da una descrizione del protocollo, ProVerif traccia le possibili evoluzioni della conoscenza di un avversario.
Lo scopo è determinare se esista la possibilità che questa possa raggiungere un livello sufficiente a violare la sicurezza del protocollo.
Input
processi (π-calculus)
Proposizioni di Horn
Internamente ProVerif converte il modelloπ-calculus inproposizioni
di Horn; da questo insieme di assiomi vengono derivati nuovi teoremi:
la derivazione di un teorema che contraddica i requisiti di sicurezza è la prova che questi non vengono rispettati.
Proposizioni di Horn
VN
i=1Pi ⇒ Q
ProVerif usa proposizioni di Horn costruite con i seguenti predicati: attacker(x) afferma che l’avversario conosce x;
message(m, c) afferma che il messaggio m è sul canale c.
Esempio
Verifica con ProVerif
Vediamo il dispositivo come un insieme di black box interconnesse: più facile da capire a livello funzionale;
ci vogliono meno risorse computazionali per la verifica;
qualora si voglia una verifica ad un livello più basso, è comunque sensato subordinarla ad una verifica a livello funzionale;
se si dispone di una serie di blocchi già verificati, non c’è bisogno di verificarli per ogni nuovo design;
ci sono blocchi proprietari (IP blocks) che vengono forniti come netlist e non possono essere verificati a livello più basso.
I dettagli dell’estrazione del modelloπ-calculus da VHDL sono nel
Sezionare Spider Pig
Anatomia di una black boxCi vogliono gli attrezzi adeguati se vogliamo esaminarla. . . La scelta non è triviale:
ProVerifnon basta — ci mette troppo∗
;
∗Dopo giorni uno perde (ragionevolmente) le speranze e killa il processo. . .
AVISPA(verifica protocolli crittografici) non supporta teorie equazionali;
SPASS(theorem prover) ci mette
troppo∗;
Prover9(theorem prover) ci mette
troppo∗
;
H1(theorem prover) — non testato;
Spider Pig, Spider Pig
Does whatever a Spider Pig does. Can he swing
from a web? No, he can’t,
he’s a pig. Look out,
he’s a Spider Pig.
MACE4(model finder)riesce a
trovare un “modello”;
Termine fuorviante!
Paradox(model finder) — non testato.
Sistema di tipi
Il modello trovato da MACE4 può essere interpretato come un
sistema di tipi.
Ehm, ovvero?
rq♣♠ è un sistema di tipi, in quanto ogni seme identifica una
caratteristica comune a diverse carte.
Nel nostro caso ci serve per verificare lacoerenza del sistema:
assegnando un tipo a ciascun dato e a ciascun canale vogliamo assicurarci che dati di un certo tipo transitino solo su canali di tipologia appropriata.
Rosso rq
Dati e canalirossisono privati e
devono essere protetti, in quanto la compromissione della loro sicurezza implica il mancato rispetto delle specifiche.
Nero ♣♠
Dati e canali neri sono pubblici e dunque sono (possono essere) accessibili all’avversario; dati rossi non possono transitarvi.
Un gioco di carte
Ci sono carte a seme rossorqe nero ♣♠, sia con dorso rossoche
con dorso nero .
Il giocatore ha solo carte a dorso nero e seme nero (♣♠/) e può
interagire con dei corrieri che ritirano una carta e la passano ad un mazziere.
Ciascun mazziere ritira una o più carte e, obbedendo a delle regole sul seme delle carte, passa una carta con il dorso di un certo colore ed un certo seme ad un altro mazziere o ad un corriere che la porta
al giocatore solo nel caso abbia il dorso nero (rq♣♠/) e la distrugge
altrimenti (rq♣♠/).
Se la carta ricevuta ha seme rosso (rq/) il giocatore ha vinto.
La similitudine
Dati privati: seme rossorq
Dati pubblici: seme nero ♣♠
Canali privati: dorso rosso
Canali pubblici: dorso nero
Modello: regole del gioco Terminali del dispositivo: corrieri Gate interni: mazzieri
Verifica con MACE4
MACE4 è in grado di analizzare sistemi di proposizioni logiche; noi
usiamo proposizioni di Horn costruite∗
con i seguenti predicati:
∗Per costruirle abbiamo sviluppato anche il tool������(Translation Assistant: Clauses over Nets). value
Il predicato value(Cxxx,x) afferma che un termine di tipo x è sul canale Cxxx.
mknows
Il predicato mknows(x) afferma che l’avversario è a conoscenza dei termini di tipo x.
Li utilizziamo per dichiarare, rispettivamente: i valori iniziali;
le transizioni;
le mappature delle porte; suggerimenti per MACE4.
inferenza di nuovi termini; le funzioni utilizzabili; i canali pubblici; obiettivi di sicurezza.
Interpretazione dei risultati
(I)Il modello che otteniamo individua i vincoli da rispettare per ciascun dato e canale, ovvero di quale tipo debbano essere affinché gli obiettivi di sicurezza siano raggiunti.
Tavole di funzioni
Possiamo distinguere tra funzioni che preservano il tipo. . .
invertible: ♣♠ rq
♣♠ rq
concat: ♣♠ rq
♣♠ ♣♠ rq
rq rq rq
. . . e quelle che invece lo alterano:
xor: ♣♠ rq
♣♠ ♣♠ rq
Interpretazione dei risultati
(II)Tavole dei predicati: mknows(x)
mknows: ♣♠ rq value:
♣♠ rq
Dalle tavole si evince che il sistema viene compromesso ogni qualvolta l’avversario entri in possesso di un termine privato.
Chiaramente il transito di un dato privato su canale pubblico causa la compromissione del sistema.
I dettagli dell’estrazione di proposizioni di Horn da VHDL sono nel capitolo 7.
Conclusione
(I)Laprogrammazione hardwaresi colloca nell’intersezione tra il campo
dell’elettronica e quello dell’informatica, dove la distinzione è decisamente labile: ad oggi il suo utilizzo è estensivo, vista la complessità dei dispositivi moderni.
Questa pratica pone delle problematiche di verifica e test non triviali:
lo scopo di questo lavoro è stato laverifica formale di aspetti di
sicurezza nel design VHDL, finalizzata ad assicurare che un circuito
contenente dati confidenziali ne assicuri la corretta tenuta.
All’interno di un circuito abbiamo categorizzato dati e canali indue
classidistinte, distinguendo tra quanto debba essere mantenuto
privato e quanto possa essere accessibile ad un avversario senza compromettere le specifiche di sicurezza.
Conclusione
(II)Abbiamo delineatodue metodologie, che utilizzano software di
verifica esistenti adattandone le modalità di utilizzo alle nostre esigenze, e mostrato come la parte manuale possa essere automatizzata.
La prima metodologia ricrea uno scenario simile a quello del modello
di Dolev-Yao: trattiamo un dispositivo elettronico come unprotocollo
crittografico. Questo ci permette di utilizzareProVerifuna volta
stabilita una procedura di derivazione di un modelloπ-calculusdel
dispositivo a partire dalla sua descrizione VHDL.
La seconda metodologia usa il model finderMACE4per individuare
unsistema di tipiche, se rispettato, garantisce il rispetto degli obiettivi di sicurezza prefissati; l’utilizzo di MACE4 ha richiesto di stabilire una procedura per derivare una descrizione del dispositivo sotto forma di
Analisi Statica di Circuiti per la Sicurezza
candidato: Riccardo Bresciani relatore: Prof. Luca Fanucci
Grazie per la vostra attenzione
Domande?
DÉLÉG ATI ONGÉNÉRA LE P OU R L’AR M E M ENT La DGA,
partenaire des armées pour bâtir la défense de demain
�������������������������������������� ��������� ������ ������
&
Stage presso LSV (ENS-Cachan), sotto la supervisione di Jean Goubalt-Larrecq (LSV, ENS Cachan & CNRS & INRIA), in collaborazione con David Lubicz (IRMAR, Université de Rennes 1 & DGA) e Nicolas Guillermin (DGA).