Politecnico di MilanoPolitecnico di Milano

Realizzazione di un componente per un Realizzazione di un componente per un sistema dedicato:sistema dedicato:

codifica AES a 512 bitcodifica AES a 512 bitRelatore: Prof. Fabrizio Ferrandi

Correlatore: Ing. Marco Domenico Santambrogio

Davide Pavoni mat. 654619Roberto Palazzo mat. 653365

22/07/2004 Davide Pavoni, Roberto Palazzo 2

SommarioSommario

• 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 3

• Algoritmi di Crittografia: tecniche di codifica delle informazioni che permettono di renderle comprensibili solamente a chi conosce la chiave.

• Simmetrici: stessa chiave segreta per cifrare e decifrare (K1=K2)• Asimmetrici: due chiavi correlate, una pubblica e una privata

(K1≠K2)

CrittografiaCrittografia

Cifratura Decifratura

Mittente DestinatarioTesto

in chiaro

Testo cifrato

Testo in chiaro

Chiave [K1] Chiave [K2]

22/07/2004 Davide Pavoni, Roberto Palazzo 4

Advanced Encryption Advanced Encryption StandardStandard

•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 5

Perché usare le FPGAPerché 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 6

FPGAFPGA

• Le FPGA sono dispositivi hardware le cui funzioni non sono fissate e possono essere programmate dall’utente

• Architettura ad array simmetrici - Xilinx• CLB – elementi funzionali

per costruire la logica• IOB – interfacce tra i pin

esterni e logica interna• Interconnessioni

CLB

Linee connessione verticali

Linee connessione

Linee connessione orizzontali

Matrice interruttori

22/07/2004 Davide Pavoni, Roberto Palazzo 7

AESAES•Caratteristiche

• Cifrario a blocchi a chiave simmetricaBlocchi 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 8

AES: Espansione della AES: Espansione della chiavechiave

KeyExpansion ( byte key[16], word w[44] )begin

word tempi=0while (i<4)

w[i]=word ( key[4*i], key[4*i+1], key[4*i+2], key[4*i+3] )i=i+1

end whilewhile (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 tempi=i+1

end whileend

22/07/2004 Davide Pavoni, Roberto Palazzo 9

AES: Algoritmo AES: Algoritmo

22/07/2004 Davide Pavoni, Roberto Palazzo 10

AES: SubBytes()AES: SubBytes()

• SubBytes()

22/07/2004 Davide Pavoni, Roberto Palazzo 11

AES: ShiftRows()AES: ShiftRows()

• ShiftRows()

22/07/2004 Davide Pavoni, Roberto Palazzo 12

AES: MixColumns()AES: MixColumns()

• MixColumns()

22/07/2004 Davide Pavoni, Roberto Palazzo 13

AES: AddRoundKey()AES: AddRoundKey()

• AddRoundKey()

22/07/2004 Davide Pavoni, Roberto Palazzo 14

Macchina a stati AES 512Macchina a stati AES 512

22/07/2004 Davide Pavoni, Roberto Palazzo 15

Architettura hardwareArchitettura hardware

PowerPC

AES512

Interrupt Controller

Bus PLB(Core Connect)

22/07/2004 Davide Pavoni, Roberto Palazzo 16

Scelte ImplementativeScelte 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 17

Struttura IP CoreStruttura IP Core

22/07/2004 Davide Pavoni, Roberto Palazzo 18

Memory MapMemory Map

• Registri user logic

• Registri IPIF

22/07/2004 Davide Pavoni, Roberto Palazzo 19

DriverDriver

• 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 20

Risultati SperimentaliRisultati 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/sNOTA: 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 21

Risultati Sperimentali (2)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 22

Conclusioni e Sviluppi futuriConclusioni e Sviluppi futuri

• Disponendo di una FPGA più capiente è possibile incrementare le prestazioni inserendo nell’AES Core 16 ROM contenenti le S-Box. • 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 23

FINE PRESENTAZIONE

22/07/2004 Davide Pavoni, Roberto Palazzo 24

AES: CifraturaAES: Cifratura

Cipher ( byte in[16], byte out[16], word w[44] )begin

byte state[4, 4]state=inAddRoundKey ( state, w[0, 3] )for round=1 step 1 to 9SubBytes ( state )ShiftRows ( state )MixColumns ( state )AddRoundKey ( state, w[4*round, 4*(round+1)-1] )end forSubBytes ( state )ShiftRows ( state )AddRoundKey ( state, w[4*round, 4*(round+1)-1] )out=state

end

Chiave espansaBlocco in uscita

Blocco in ingresso

22/07/2004 Davide Pavoni, Roberto Palazzo 25

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

• ISR (IP Interrupt Status Register)

Gestione Interrupt

22/07/2004 Davide Pavoni, Roberto Palazzo 26

AES512_userlogicAES512_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 27

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