relatore :Prof.LucaFanucci candidato :RiccardoBresciani AnalisiStaticadiCircuitiperlaSicurezza Motivazione Motivazione Metodiformali

(1)

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 . . .

Introduzione Verifica con ProVerif e MACE4 Conclusione

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. . . http://xkcd.com/730/

Metodi formali

(I)

L’utilizzo di metodi formali permette di rispondere a queste necessità. Un sistema 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 un modello del sistema: ragionando su di esso vengono inferite le proprietà del modello, e quindi del sistema — se il modello è adeguato.

(2)

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 formali dimostra che il sistema implementa correttamente una data specifica. −→ Analisi statica

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 originale

Il dispositivo

INTERNI OUTPUT INPUT • Privato • Pubblico • _{Da determinare}

Distinguiamo dati e canali in pubblici e privati; 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.

(3)

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 logiche (proposizioni di Horn)

Proposizioni di Horn

Internamente ProVerif converte il modelloπ-calculus in proposizioni 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

(4)

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 capitolo 6.

Sezionare Spider Pig

Anatomia di una black box

Ci 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 la coerenza 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

(5)

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 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)

La programmazione hardware si 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 la verifica 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 in due classi distinte, distinguendo tra quanto debba essere mantenuto privato e quanto possa essere accessibile ad un avversario senza compromettere le specifiche di sicurezza.

(6)

Conclusione

(II)

Abbiamo delineato due 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 un protocollo crittografico. Questo ci permette di utilizzare ProVerif una volta stabilita una procedura di derivazione di un modelloπ-calculus del dispositivo a partire dalla sua descrizione VHDL.

La seconda metodologia usa il model finder MACE4 per individuare un sistema di tipi che, 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 proposizioni di Horn.

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).