Politecnico di Milano
Realizzazione di un componente per un
sistema dedicato:
codifica AES a 512 bit
Relatore: Prof. Fabrizio Ferrandi
Correlatore: Ing. Marco Domenico Santambrogio
Davide Pavoni
mat. 654619
Roberto Palazzo
mat. 653365
Sommario
• Cenni alla crittografia
• AES e applicazioni
• FPGA e sistemi dedicati
• Implementazione dell’IP Core
• Risultati Sperimentali
• Conclusioni e sviluppi futuri
22/07/2004
Davide Pavoni, Roberto Palazzo
2
Crittografia
• Algoritmi di Crittografia: tecniche di codifica delle informazioni
che permettono di renderle comprensibili solamente a chi conosce
la chiave.
Mittente
Testo
in chiaro
Cifratura
Chiave [K1]
Destinatario
Testo
cifrato
Decifratura
Testo in
chiaro
Chiave [K2]
• Simmetrici: stessa chiave segreta per cifrare e decifrare (K1=K2)
• Asimmetrici: due chiavi correlate, una pubblica e una privata
(K1≠K2)
22/07/2004
Davide Pavoni, Roberto Palazzo
3
Advanced Encryption Standard
• 1997 - National Institute of Standards and Technology (NIST)
indice una gara pubblica per sostituire il Data Encryption
Standard (DES).
• Requisiti:
• Cifrario a blocchi.
• Lunghezza della chiave tra 128 e 256 bit.
• Efficienza dell’implementazione hardware e software.
• Libero da brevetti.
• 2001 – NIST pubblica la specifica dell’algoritmo di Advanced
Encryption Standard (AES).
• Diventerà probabilmente lo standard de-facto mondiale per
proteggere le comunicazioni nei prossimi decenni.
22/07/2004
Davide Pavoni, Roberto Palazzo
4
Perché usare le FPGA
• L’aspetto negativo delle implementazioni hardware
tradizionali (ASIC) è la mancanza di flessibilità
• I dispositivi hardware programmabili come le Field
Programmable Gate Arrays (FPGA) sono una alternativa
interessante per l’implementazione di algoritmi crittografici
• Potenziali vantaggi utilizzo FPGA:
 Cambiare il tipo di algoritmo durante il funzionamento (es.
negoziazione SSL)
 Upgrade degli algoritmi (es. 802.11i)
 Compromesso tra velocità delle ASIC e implementazioni
software
 Efficienza di costo
22/07/2004
Davide Pavoni, Roberto Palazzo
5
FPGA
• Le FPGA sono dispositivi
hardware le cui funzioni non
sono fissate e possono essere
programmate dall’utente
Linee connessione
orizzontali
CLB
• Architettura ad array
simmetrici - Xilinx
• CLB – elementi funzionali
per costruire la logica
• IOB – interfacce tra i pin
esterni e logica interna
• Interconnessioni
Matrice
interruttori
Linee connessione Linee connessione
verticali
22/07/2004
Davide Pavoni, Roberto Palazzo
6
AES
• Caratteristiche
• Cifrario a blocchi a chiave simmetrica
 Blocchi da 128 bit
 Chiave da 128, 196, 256 bit
• le operazioni internamente sono eseguite su una matrice di 4x4
byte detta Stato
• Lavora iterando gli stessi passi (round)
• Ogni round (tranne l’ultimo) è la composizione di passi elementari
• SubBytes ( sostituzione mediante S-box )
• ShiftRows ( permutazione )
• MixColumns ( sostituzione che usa aritmetica su GF(28) )
• AddRound key ( XOR con chiave espansa )
22/07/2004
Davide Pavoni, Roberto Palazzo
7
AES: Espansione della chiave
KeyExpansion ( byte key[16], word w[44] )
begin
word temp
i=0
while (i<4)
w[i]=word ( key[4*i], key[4*i+1], key[4*i+2], key[4*i+3] )
i=i+1
end while
while (i<44)
temp=w[i-1]
if (i mod 4=0)
temp=SubWord ( RotWord (temp) ) xor Rcon [i/4]
w[i]=w[i-4] xor temp
i=i+1
end while
end
22/07/2004
Davide Pavoni, Roberto Palazzo
8
AES: Algoritmo
22/07/2004
Davide Pavoni, Roberto Palazzo
9
AES: SubBytes()
• SubBytes()
22/07/2004
Davide Pavoni, Roberto Palazzo
10
AES: ShiftRows()
• ShiftRows()
22/07/2004
Davide Pavoni, Roberto Palazzo
11
AES: MixColumns()
• MixColumns()
22/07/2004
Davide Pavoni, Roberto Palazzo
12
AES: AddRoundKey()
• AddRoundKey()
22/07/2004
Davide Pavoni, Roberto Palazzo
13
Macchina a stati AES 512
22/07/2004
Davide Pavoni, Roberto Palazzo
14
Architettura hardware
Bus PLB
(Core Connect)
PowerPC
AES512
Interrupt
Controller
22/07/2004
Davide Pavoni, Roberto Palazzo
15
Scelte Implementative
• La FPGA a disposizione non è in grado di contenere
completamente il componente che effettua la cifratura AES
a 128 bit.
 Soluzione mista hardware / software.
Suddivisione dell’algoritmo AES in 2 parti:
• Espansione della chiave eseguita dal PowerPC.
• Operazione più lenta, ma una tantum.
• Cifratura effettuata in hardware
• in ingresso di blocchi di 128 bit di dati e
chiave espansa.
22/07/2004
Davide Pavoni, Roberto Palazzo
16
Struttura IP Core
22/07/2004
Davide Pavoni, Roberto Palazzo
17
Memory Map
• Registri
user logic
• Registri IPIF
22/07/2004
Davide Pavoni, Roberto Palazzo
18
Driver
• Per utilizzare l’IP Core all’interno dell’architettura hardware è
necessario scrivere del software che lo gestisce.
• L’IP Core è di tipo slave-only quindi è il PowerPc che effettua
operazioni di I/O puntando agli indirizzi di memoria che
corrispondono ai registri dell’IP Core secondo la memory map.
• E’ stato creato un driver di basso livello in linguaggio C:
• Scrittura dei dati in ingresso e chiave espansa.
• Lettura dei dati in uscita.
• Abilitare / disabilitare sollevazione interrupt.
• Routine gestione interrupt (con contatore numero chiamate).
22/07/2004
Davide Pavoni, Roberto Palazzo
19
Risultati Sperimentali
•
Verifica del funzionamento in laboratorio di Micro Architetture
•
Il PowerPC esegue un software di test, appositamente scritto per
testare l’IP Core, articolato in 2 fasi:
1. Interrupt disabilitati per valutare correttezza risultati.
2. Interrupt abilitati per cifrare uno stream di dati e valutazione
prestazioni.
•
Risultati sperimentali:
•
Frequenza di clock del sistema = 100 MHz
Velocità misurata AES512:
14.6 Megabit/s
NOTA: comprende overhead dovuti a lettura / scrittura dei registri.
Dalle simulazioni si è verificato che l’Aes Core lavora a
67 Megabit/s
22/07/2004
Davide Pavoni, Roberto Palazzo
20
Risultati Sperimentali (2)
• Confronto con un’ implementazione software
• Realizzato un software in C tale da implementare
esattamente lo stesso algoritmo implementato in hardware
dall’IP Core.
• Piattaforma di Test: Pentium4 - 2.6Ghz - 512 Mb Ram - Win XP
Velocità Misurata: 878 Kilobit/s
22/07/2004
Davide Pavoni, Roberto Palazzo
21
Conclusioni e Sviluppi futuri
• Disponendo di una FPGA più capiente è possibile incrementare le
prestazioni inserendo nell’AES Core 16 ROM contenenti le SBox.
• SubBytes() eseguita in 1 ciclo di clock contro i 16 attuali.
• La velocità dell’AES Core incrementa di circa 5 volte.
• Prestazione realizzazione Hardware vs. Software
• Utilizzo dell’IP Core come coprocessore crittografico.
• FPGA rappresentano un buon compromesso in termini di
costi/prestazioni.
• La riconfigurabilità delle FPGA favorisce la transizione verso il
nuovo standard AES.
22/07/2004
Davide Pavoni, Roberto Palazzo
22
FINE PRESENTAZIONE
22/07/2004
Davide Pavoni, Roberto Palazzo
23
AES: Cifratura
Blocco in ingresso
Cipher ( byte in[16], byte out[16], word w[44] )
begin
byte state[4, 4]
Blocco in uscita
Chiave espansa
state=in
AddRoundKey ( state, w[0, 3] )
for round=1 step 1 to 9
SubBytes ( state )
ShiftRows ( state )
MixColumns ( state )
AddRoundKey ( state, w[4*round, 4*(round+1)-1] )
end for
SubBytes ( state )
ShiftRows ( state )
AddRoundKey ( state, w[4*round, 4*(round+1)-1] )
out=state
end
22/07/2004
Davide Pavoni, Roberto Palazzo
24
IPIF
• IPIF (IP Interface): interfaccia con il bus PLB che si occupa della
gestione di tutti i vari segnali e protocolli necessari per la
comunicazione.
• L’IPIF ha un’interfaccia con la AES512_userlogic detta IPIC
(IP InterConnect).
• Registri
• MIR (Module Identification Register)
• SW RST (Software Reset Register)
• GIE (Global Interrupt Enable Register)
• IER (IP Interrupt Enable Register)
Gestione Interrupt
• ISR (IP Interrupt Status Register)
22/07/2004
Davide Pavoni, Roberto Palazzo
25
AES512_userlogic
• Realizza le funzioni vere e
proprie dell’IP Core.
• Comunicazione con l’IPIF
attraverso i segnali
dell’interfaccia IPIC.
• Registri
• 16 da 32 bit che contengono i
512 bit in ingresso.
• 16 da 32 bit che contengono i
512 bit in uscita.
• 44 da 32 bit che contengono la
chiave espansa.
• Macchina a stati che comanda
l’AES Core per cifrare i 512 bit di
dati.
22/07/2004
Davide Pavoni, Roberto Palazzo
26
AES Core
• Unità funzionale di base che effettua la cifratura di blocchi di 128 bit di
dati fornendo in ingresso direttamente la chiave espansa.
• La chiave espansa w_in è di 1408 bit (44 x 32 bit)
22/07/2004
Davide Pavoni, Roberto Palazzo
27