Politecnico di Milano
Implementazione hardware dell’algoritmo
MD5, tramite EDK, per sistemi
riconfigurabili
Relatore: Prof. Fabrizio Ferrandi
Correlatore: Ing. Marco Domenico Santambrogio
Antonio Canclini
Matr. #657338
Maurizio Sala Matr. #659392
Sommario
• Introduzione:
• FPGA e introduzione all’hashing
• Descrizione algoritmo MD5
• Realizzazione VHDL
• Importazione in una architettura in EDK – Device
driver
• Prestazioni, test e simulazioni
• Conclusioni e lavori futuri
Antonio Canclini – Maurizio Sala
2
FPGA
• FPGA  Field Programmable Gate Array
• Utilizzo per test e prototipi
• Miglior compromesso tra costi e prestazioni, garantendo
buona flessibilità
Blocco di
input/output
Blocco logico
configurabile
Interconnessione
Antonio Canclini – Maurizio Sala
3
Crittografia e Hashing
• L’Hashing è una particolare tecnica di crittografia:
• Permette di garantire l’integrità dei dati
• Utilizzata nella firma digitale
• L’algoritmo MD5 è un esempio di funzione di hashing
Messaggio
di lunghezza
arbitraria
ALGORITMO
Antonio Canclini – Maurizio Sala
Message
digest
di n bit
4
Descrizione algoritmo MD5
• Riceve in ingresso una stringa di lunghezza arbitraria
e calcola un digest di 128 bit
• Strutturato in 5 passi, descritti nella specifica RFC 1321
Antonio Canclini – Maurizio Sala
5
Realizzazione in VHDL
• Ottimizzazione della frequenza di lavoro di
un’implementazione esistente dell’algoritmo MD5
Ricerca del percorso critico
OPERAZIONE CRITICA IN
TERMINI DI FREQUENZA
Antonio Canclini – Maurizio Sala
6
Realizzazione in VHDL
• La somma può essere eseguita in modo parallelo:
• Mediante l’utilizzo di più processi VHDL,
• e sincronizzando in modo opportuno le operazioni svolte
dai processi
add1 <= a + temp;
add3 <= add1 + add2;
add2 <= k + t(i);
Antonio Canclini – Maurizio Sala
7
Realizzazione in VHDL
• Implementazione dei 4 round dell’algoritmo MD5:
• I processi per il calcolo delle somme vengono replicati 4 volte
SEGNALE round :
MANTIENE
L’INFORMAZIONE
SUL ROUND IN
ESECUZIONE
SEGNALE nsw :
CONTATORE CHE
REGOLA
L’ESECUZIONE DI UN
ROUND
Antonio Canclini – Maurizio Sala
8
Realizzazione in VHDL
AGGIORNAMENTO
DEI SEGNALI PER IL
CONTROLLO DEL
FLUSSO
DI ESECUZIONE
PASSAGGIO DEI
VALORI DEI REGISTRI
DAL ROUND 3
AL ROUND 4
Antonio Canclini – Maurizio Sala
9
Importazione in una
architettura EDK
PROCESSORE
POWER-PC
BUS OPB
COMPONENTE
REALIZZATO
Antonio Canclini – Maurizio Sala
10
Importazione in una
architettura EDK
• Interfacciamento del componente sul bus OPB:
• In modalità slave
• Mediante il modulo PSelect
COMPONENTE REALIZZATO
PERIPHERAL SELECT: SI OCCUPA
DELLA DECODIFICA DEGLI
INDIRIZZI PRESENTI SUL BUS OPB
Antonio Canclini – Maurizio Sala
11
Importazione in una
architettura EDK
• Gestione della memoria mediante il meccanismo di
memory mapping
64 BYTE DI MEMORIA DEDICATI ALLA
PARTE DI MESSAGGIO DA ELABORARE
INDIRIZZO DI START, INDICA IL
COMPLETAMENTO DELLA FASE DI
INIZIALIZZAZIONE E L’INIZIO
DELL’ALGORITMO
INDIRIZZI DEDICATI AGLI MD BUFFER
Antonio Canclini – Maurizio Sala
12
Device driver
• Funzioni del driver:
• Accesso alla memoria (lettura/scrittura registri)
• Gestione interrupt
Antonio Canclini – Maurizio Sala
13
Prestazioni
• Confronto di prestazioni tra il componente esistente e
la nuova implementazione (rispetto al round 1)
• Prestazioni del componente realizzato:
Antonio Canclini – Maurizio Sala
14
Test e simulazioni
• Simulazione con Modelsim
• Utilizzo di un testbench
• Casi di test ufficiali
forniti nella specifica
RFC 1321
FINE ELABORAZIONE
COMUNICATA DAL
SEGNALE DI INTERRUPT
MESSAGE
DIGEST
Antonio Canclini – Maurizio Sala
15
Conclusioni e lavori futuri
• L’implementazione preesistente è stata migliorata
sia in termini di frequenza che dal punto di vista
dell’occupazione su scheda
• Lavori futuri: impiego del DMA (Direct Memory
Access) per aumentare la velocità di esecuzione
delle operazioni di accesso alla memoria
Antonio Canclini – Maurizio Sala
16