D03 Crittografia a Chiave Segreta

7/29/2019 D03 Crittografia a Chiave Segreta

1/154

Crittografia a Chiave Segreta

(Secret Key Cryptography)

Luca Grilli


2/154

INTRODUZIONE



3/154

Introduzione

Si descriver il funzionamento degli algoritmi di

crittografia a chiave segreta

si vedranno in dettaglio gli algoritmi DES e IDEA

tali algoritmi non si applicano direttamente ad unmessaggio di lunghezza qualsiasi, ma ricevono in input

un blocco del messaggio di lunghezza fissa (64 bit nel caso di

DES e IDEA)

una chiave di lunghezza fissa (56 bit per DES e 128 bit perIDEA)

loutput un blocco cifrato (della stessa lunghezza del

blocco di input)

per tale ragione si parla di algoritmi di cifratura a blocchi


4/154

Introduzione

la cifratura di un messaggio di lunghezza qualsiasi

viene ricondotta alla cifratura dei singoli blocchi

il messaggio m viene scomposto in blocchi di lunghezza

fissa la cifratura del messaggio m viene ottenuta

combinando opportunamente le cifrature dei suoi

blocchi

In altri termini, possibile ottenere un algoritmodi cifratura simmetrica per messaggi di lunghezza

qualsiasi utilizzando come modulo base un

algoritmo di cifratura simmetrica a blocchi


5/154

CIFRATURA A BLOCCHISCHEMAGENERALE



6/154

Cifratura a blocchi introduzione

Lalgoritmo di cifratura converte un blocco di

testo in chiaro in un blocco di testo cifrato

la chiave Knon deve essere troppo corta

es. se Kha lunghezza 4 bit, sono sufficienti 24 = 64

tentativi per individuarla!

analogamente, la lunghezza (fissata) di un blocco

non deve essere troppo piccola es. se un blocco ha lunghezza 8 bit, ottenendo delle

coppie plaintext, ciphertext si potrebbe costruire unatabella di 28 = 256 coppie utilizzabile per la decifratura


7/154

Cifratura a blocchi introduzione

daltra parte, avere blocchi esageratamente lunghi

oltre a non essere necessario dal punto di vista dellasicurezza,

comporta una gestione pi complicata, e

pu degradare le prestazioni

64 bit una lunghezza ragionevole per un blocco

improbabile ottenere ordine di 264 coppie plaintext,ciphertext per costruire una tabella di decifratura, e

anche se fosse possibile, la sua memorizzazionerichiederebbe una spazio enorme 264 record da 64 bit,

come pure lordinamento per consentire ricercheefficienti


8/154

Cifratura a blocchi concetti generali

Il modo pi generale per cifrare un blocco da 64

bit definire una biiezione : {0, 1}64 {0, 1}64

memorizzare la definizione della biiezione in una

struttura dati impraticabile sono richiesti 64 264 bit, cio 270 bit

ad essere precisi ce ne vogliono un po di meno, trattandosi

di un biiezione, comunque almeno 269 bit sono richiesti

inoltre, cos facendo la chiave incorporata nellabiiezione

per rendere parametrica la biiezione rispetto la chiave

necessario memorizzare una biiezione per ogni possibile

chiave!


9/154


I sistemi di crittografia a chiave segreta sonoconcepiti per

usare una chiave ragionevolmente lunga

ad esempio 64 bit generare una biiezione che appare, a chi non conosce

la chiave, completamente random

cio, la biiezione sembra essere definita utilizzando un

generatore di numeri casuali loutput (i) di un input isi ottiene lanciando un dado a 64

facce o facendo 64 lanci di monete

avendo laccortezza di ripetere la procedura se il valoreottenuto per loutput (i) coincide con qualche (j) con j < i

(cio se (i) era gi stato assegnato ad un precedente input)


10/154


Se la biiezione fosse realmente random

un input iottenuto cambiando un qualunque bit di uninput i

sarebbe mappato in un output (i) tale che (i) e (i)risultano statisticamente indipendenti ad esempio, non pu succedere che il terzo bit delloutput

cambia sempre quando il dodicesimo bit dellinput cambia

Gli algoritmi crittografici sono pensati perdiffondere/spargere in tutti i bit delloutput ilvalore di ogni bit dellinput

ogni bit delloutput deve dipendere da tutti i bitdellinput e allo stesso modo


11/154

Sostituzione

Sostituzioni e permutazioni sono due

trasformazioni base applicabili ad un blocco di dati

Si assuma di dover cifrare un blocco di kbit

Una sostituzione specifica, per ciascuno dei 2k

possibili valori dellinput, i kbit delloutput

per specificare una sostituzione completamente

random sono necessari circa k2kbit

impraticabile implementare una sostituzione per

blocchi di 64 bit,

ma fattibile per blocchi di lunghezza di 8 bit


12/154

Permutazione

Una permutazione specifica, per ciascuna

delle kposizioni dei bit in input, la posizione

del corrispondente bit nelloutput

ad esempio, il bit in posizione 1 diventa il bit in

posizione 13nelloutput,

il bit in posizione 2 diventa il bit in posizione 61

nelloutput, e cos via

per specificare una permutazione

completamente random per un blocco di

lunghezza kbit sono necessari klog2kbit


13/154

Permutazione

per ciascuno dei kbit va specificata la sua

posizione nelloutput; ogni posizione richiede

log2kbit

ad esempio, essendo 2

6

= 64, sono necessari 6 = log264bit per specificare la nuova posizione che li-esimo bit in

input avr in output


14/154

Permutazione vs Sostituzione

Una permutazione un caso particolare di

sostituzione in cui ogni bit delloutput ottiene

il suo valore da esattamente un bit dellinput

per blocchi di 64 bit possibile specificare e

realizzare un permutatore

un modulo che riceve in input un blocco di 64 bit e

produce in output una data permutazione dei bit in

input


15/154

Cifrario a blocchi schema generale

Un algoritmo di cifratura a chiave segreta pufunzionare come segue

scompone il blocco in input in pezzi pi piccoli (blocchi da8 bit)

applica una sostituzione a ciascun pezzo da 8 bit la sostituzione dipender dal valore della chiave

gli output delle sostituzioni vengono riuniti in un unicoblocco (64 bit),

tale blocco viene permutato in un permutatore a 64 bit

che ha il compito di diffondere le modifiche eseguite nellesostituzioni

il processo viene ripetuto un certo numero di volteriportando loutput in ingresso


16/154

Esempio di cifrario a blocchi


17/154

Esempio di cifrario a blocchi

Ogni attraversamento del cifrario viene detto

round

con un solo round, un bit bxdi input pu influenzare

soltanto 8 bit bx1, bx2, , bx8delloutput poich bxha attraversato soltanto un blocco di sostituzione

in generale i bit bx1, bx2, , bx8 non sono consecutivi essendo

stati mescolati nel permutatore

alla fine del secondo round, assumendo che i bit bx1,bx2, , bx8 siano smistati in un diverso blocco di

sostituzione

il bit bxiniziale influenza tutti i bit in output


18/154

ALGORITMO DESDATA ENCRYPTION STANDARD



19/154

Data Encryption Standard (DES)

DES fu pubblicato nel 1977 dal National Bureau ofStandards

ora rinominato National Institute ofStandards andTechnology (NIST)

per usi commerciali e altre applicazioni del governostatunitense

progettato da IBM, si basa sul precedente cifrarioLucifered frutto della collaborazione con consulentidella NSA

DES usa una chiave di 56 bit, e mappa un blocco diinput da 64 bit in un blocco di output da 64 bit


20/154


la chiave in realt costituita da una sequenza di64 bit, ma un bit in ogni ottetto (il blocco da 64 bit formato da 8 sequenze di 8 bit dette ottetti) usato come odd paritysu ciascun ottetto

di fatto, soltanto 7bit in ogni ottetto sonoveramente significativi come chiave

DES efficiente se realizzato in hardware, ma

relativamente lento se implementato in software sebbene lessere difficilmente implementabile come

software non era un requisito specificato nel progetto,

molti sostengono che in realt era un fatto voluto,


21/154


forse per limitarne luso ad organizzazioni in grado di

realizzare sistemi hardware, o

forse perch rese pi facile controllare laccesso alla

tecnologia

ad ogni modo, laumento delle capacit di calcolo delle CPUrese possibile realizzare una versione software di DES

una 500-MIPS (Million Instruction Per Second) CPU pu cifrare ad

un tasso di circa 30 KB/s,

e forse pi, dipende dai dettagli architetturali della CPU e dalla

intelligenza dellimplementazione

un processore Intel Core i7 Extreme Edition i980EE ha una

capacit di calcolo di circa 150 MIPS pu cifrare ad un tasso dicirca 9 KB/s per cifrare 1 MB impiega circa 110 secondi

limplementazione software pertanto adeguata a molte

applicazioni


22/154

Perch chiavi da 56 bit?

La scelta di una chiave da 56 bit caus molte

controversie

prima che DES fu adottato, le persone al di fuori

della intelligence communitylamentavano che 56bit non offrivano una sicurezza adeguata

perch solo 56 dei 64 bit di una chiave DES sono

effettivamente usati nellalgoritmo? lo svantaggio di usare 8 bit della chiave per un controllo

di parit che ci rende DES molto meno sicuro (256

volte meno sicuro contro una ricerca esaustiva)


23/154


Qual il vantaggio di usare 8 bit per uncontrollo di parit?

una possibile risposta : per verificare che la

chiave non sia corrotta! ma questa spiegazione non regge!

se si considerassero 64 bit a caso invece della chiave,c una probabilit su 256 che il controllo di parit dia

esito positivo la probabilit che la chiave siacomunque errata troppo alta! inoltre avere una chiave corrotta non comporta un

problema di sicurezza, semplicemente lacifratura/decifratura non viene eseguita correttamente


24/154


chiaramente anche ridicolo sostenere che la

scelta di 56 bit stata fatta per risparmiare

memoria

La risposta ormai condivisa che il governo

statunitense abbia deliberatamente indebolito

la sicurezza di DES di una quantit appenasufficiente da consentire alla NSA di violarlo


25/154

Sulla violabilit di DES

Gli avanzamenti tecnologici dellindustria deisemiconduttori hanno reso ancora pi critico ilproblema della lunghezza della chiave di DES

la velocit dei chip e un po di furbizia permettono diviolare (individuare) le chiavi DES con approcci a forzabruta in tempi ragionevoli

forse una chiave a 64 bit sarebbe stata sicura perpochi anni in pi rispetto ad una chiave a 56 bit

il rapporto prestazioni/prezzo dellhardware cresce del40% per anno la lunghezza delle chiavi dovrebbeaumentare di 1 bit ogni 2 anni


26/154

Sulla violabilit di DES

assumendo che 56 bit erano appena sufficienti nel

1979 (quando DES fu standardizzato)

64 bit erano adeguati nel 1995, e

128 bit dovrebbero essere sufficienti fino al 2123


27/154

Quanto sicuro DES?

Se si dispone di un singolo blocco plaintext,ciphertext quanto difficile trovare la chiave? un approccio a forza bruta dovrebbe provare ordine di

256 1017chiavi se ogni tentativo richiede una singola istruzione sono

necessarie ordine di 1000 MIPS-year istruzioni

1 MIPS = 1 Milione di Istruzioni Per Secondo

1 MIPS-year = numero di istruzioni eseguite in un anno ad untasso pari a 1 MIPS

1 MIPS-year = 1MIPS (365 86400) secondi in un anno =

3,1536 1013 istruzioni

2

56

1017

103

MIPS-year


28/154

Quanto sicuro DES?

Anche nellipotesi pi scomoda per lavversario didisporre solo di testo cifrato

una ragionevole quantit di testo cifrato

un attacco a forza bruta pu essere ancora possibile

se ad esempio lavversario sa soltanto che il testo in chiaro ASCII a 7bit

ogni volta che prova una chiave deve verificare se sononulli tutti i bit nelle posizioni 8, 16, 24, , n8,

per ogni blocco di 64 bit, vanno esaminati solo 8 bit; i bit inposizione 8, 16, 24, 32, 40, 48, 56, 64

se almeno uno di questi bit vale 1 la chiave sicuramente errata

in caso contrario nulla si pu dire; la probabilit di errore pertanto 1 su 256 ossia la probabilit che tutti questi bit valgano 0


29/154

Quanto sicuro DES?

se lavversario esamina diversi blocchi, ad esempio 10,e verifica che si tratta sempre di ASCII a 7bit laprobabilit che la chiave scelta sia errata si riduce a 1su 2560

si noti che gli attuali chip commerciali cheimplementano DES non si prestano a ricercheesaustive della chiave, sono pensati per cifrare moltidati con una stessa chiave

il caricamento di una chiave unoperazione lenta seconfrontata con la velocit con la quale viene eseguita lacifratura dei dati

tuttavia sempre possibile costruire un chip ottimizzato adeseguire ricerche esaustive della chiave


30/154

Quanto sicuro DES?

Ovviamente possibile cifrare pi volte e con

diverse chiavi lo stesso blocco di dati

si parla di cifraturamultipla (multipleencryption)

Si ritiene che una cifratura con un triplo DES

256 volte pi difficile da violare

pu considerarsi sicura per il prossimo futuro


31/154

DES Struttura base


32/154

DES Struttura base

In estrema sintesi la cifratura di DES come segue

Linput di 64 bit sottoposto ad una permutazioneiniziale; un semplice mescolamento dei bit

La chiave da 56 bit viene usata per generare 16 per-roundchiavi da 48 bit; una chiave per ciascuno dei 16round

prendendo 48 differenti sottoinsiemi dei 56 bit della chiave

Ogni round riceve in input

loutput di 64 bit del round precedente

la chiave da 48 bit di quel round

e produce un output di 64 bit


33/154

DES Struttura base

Dopo il 16-esimo round, le due met delloutputdi 64 bit vengono scambiate e il risultato vienesottoposto ad unaltra permutazione

la permutazione finale, che linverso di quella iniziale La decifratura consiste esattamente nelleseguire

la cifratura DES allindietro

Per decifrare un blocco necessario:

applicare la permutazione iniziale; ci annulla leffettodella permutazione finale

generare le 16 chiavi di round, che andranno usate inordine inverso (prima K16lultima chiave generata)


34/154

DES Struttura base

eseguire 16 round esattamente come nella cifratura

il motivo per cui funziona sar illustrato quando si spiegher

cosa succede durante un round

dopo 16round di decifratura, le due met delloutput

di 64 bit vengono scambiate e il risultato viene

sottoposto ad unaltra permutazione

che annulla la permutazione iniziale

Per descrivere in dettaglio DES necessario illustrare le permutazioni iniziale e finale,

come le chiavi di round sono generate, e

cosa succede durante un round


35/154

Permutazioni dei dati

DES effettua una permutazione iniziale e una

permutazione finale dei dati che

NON migliorano la sua sicurezza!

forse sono state introdotte per rendere meno

efficienti le implementazioni software


36/154


Le permutazioni specificate in DES sonorappresentate nelle due tabelle

58 50 42 34 26 18 10 2

60 52 44 36 28 20 12 4

62 54 46 38 30 22 14 6

64 56 48 40 32 24 16 8

57 49 41 33 25 17 9 1

59 51 43 35 27 19 11 3

61 53 45 37 29 21 13 5

63 55 47 39 31 23 15 7

40 8 48 16 56 24 64 32

39 7 47 15 55 23 63 31

38 6 46 14 54 22 62 30

37 5 45 13 53 21 61 29

36 4 44 12 52 20 60 28

35 3 43 11 51 19 59 27

34 2 42 10 50 18 58 26

33 1 41 9 49 17 57 25

Initial Permutation (IP) Final Permutation (IP-1)


37/154


Le tabelle vanno interpretate nel seguente

modo

i numeri, da 1 a 64, riportati in tabella

rappresentano le posizioni dei bit in input allapermutazione

lordine (per righe da sx verso dx) dei numeri nella

tabella rappresenta la corrispondente posizionedei bit in output

ad esempio, la permutazione iniziale sposta il 58-esimo

bit in input nel primo bit in output, e

il 50-esimo bit in input nel secondo bit in output


38/154

Permutazione iniziale input e output

Non si tratta di una permutazione generata in modorandom nel senso che presenta delle regolarit evidenti

b1 b2 b3 b4 b5 b6 b7 b8

b9 b10 b11 b12 b13 b14 b15 b16

b17 b18 b19 b20 b21 b22 b23 b24

b25 b26 b27 b28 b29 b30 b31 b32b33 b34 b35 b36 b37 b38 b39 b40

b41 b42 b43 b44 b45 b46 b47 b48

b49 b50 b51 b52 b53 b54 b55 b56

b57 b58 b59 b60 b61 b62 b63 b64

b58 b50 b42 b34 b26 b18 b10 b2

b60 b52 b44 b36 b28 b20 b12 b4

b62 b54 b46 b38 b30 b22 b14 b6

b64 b56 b48 b40 b32 b24 b16 b8b57 b49 b41 b33 b25 b17 b9 b1

b59 b51 b43 b35 b27 b19 b11 b3

b61 b53 b45 b37 b29 b21 b13 b5

b63 b55 b47 b39 b31 b23 b15 b7

input output


39/154

Permutazione iniziale input e output

linput costituito da 8 ottetti

un ottetto un gruppo di 8 bit corrispondenti ad unariga della tabella

loutput costituito da 8 ottetti

i bit nel primo ottetto (prima riga) in input vengonodiffusi nellottavo bit di ogni ottetto (di ogni riga)

i bit nel secondo ottetto (seconda riga) in inputvengono diffusi nel settimo bit di ogni ottetto (di ogni

riga) i bit nelli-esimo ottetto vengono diffusi nel (9-i)-esimo

bit di ogni ottetto; i bit in posizione pari vanno nei primiquattro ottetti delloutput, mentre quelli in posizionidispari negli ultimi quattro


40/154

Perch permutare?

Le permutazioni iniziale e finale di DES non

contribuiscono alla sicurezza

si supponga per assurdo che siano fondamentali

allora chiamando EDS lalgoritmo ottenuto da DES

togliendo tali permutazioni

EDS deve essere pi facile da violare di DES supponiamo allora che nota una coppia plaintext,

ciphertext EDS sia pi facilmente violabile; cio sia pifacile calcolare la chiave KEDS

mostriamo allora che DES risulta violabile con la stessa

facilit


41/154

Perch permutare?

infatti, sia m, c una coppia plaintext, ciphertext diDES

si consideri allora la coppia m, c ove me csonoottenuti applicando la permutazione iniziale ad m e c

allora, la chiave KEDS che si ottiene violando EDS per la

coppia m, c coincide con la chiave KDES di DES per lacoppia m, c

EDSIP IP-1

DES

m m c c

KEDS(= KDES)


42/154

Generazione delle chiavi di round

DES genera

sedici chiavi di round da 48 bit a partire dalla chiave

principale Kdi 64 bit nominali, di cui solo 56 effettivi

i bit di parit di Knon vengono considerati denoteremo con K1, K2, , K16 le chiavi di round

il procedimento il seguente

viene prima effettuata una permutazione iniziale sui

56 bit effettivi di K

i 56 bit in output vengono divisi in due met C0 e D0 la permutazione illustrata nelle slide seguenti


43/154

Gen. chiavi Permutazione iniziale

il valore numerico di un elemento della tabellarappresenta la posizione del bit in input,

mentre lordine nella tabella rappresenta la posizionedel bit in output

ad esempio, il bit pi a sx nelloutput ottenuto estraendo il57-esimo bit della chiave K

i numeri 8, 16, 24, 32, 40, 48, 56, 64 non sono presentiperch corrispondono ai bit di parit della chiave

57 49 41 33 25 17 9

1 58 50 42 34 26 18

10 2 59 51 43 35 27

19 11 3 60 52 44 36

63 55 47 39 31 23 15

7 62 54 46 38 30 22

14 6 61 53 45 37 29

21 13 5 28 20 12 4

C0

D0


44/154


b1 b2 b3 b4 b5 b6 b7

b9 b10 b11 b12 b13 b14 b15

b17 b18 b19 b20 b21 b22 b23

b25 b26 b27 b28 b29 b30 b31

b33 b34 b35 b36 b37 b38 b39

b41 b42 b43 b44 b45 b46 b47

b49 b50 b51 b52 b53 b54 b55b57 b58 b59 b60 b61 b62 b63

b57 b49 b41 b33 b25 b17 b9

b1 b58 b50 b42 b34 b26 b18

b10 b2 b59 b51 b43 b35 b27

b19 b11 b3 b60 b52 b44 b36

b63 b55 b47 b39 b31 b23 b15

b7 b62 b54 b46 b38 b30 b22

b14 b6 b61 b53 b45 b37 b29b21 b13 b5 b28 b20 b12 b4

input output


45/154


La permutazione non random

nel senso che presenta delle regolarit evidenti

come nel caso delle permutazioni dei dati anche lepermutazioni iniziale e finale dei bit della chiave KNON contribuiscono alla sicurezza!


46/154

Generazione chiavi: i-esimo round

Le sedici chiavi vengono generate in sedici round

nelli-esimo round viene generata la chiave di round Ki

generazione di Ki: round i


47/154


i bit delle due met Ci-1Di-1 della (i-1)-esima chiave Ki-1vengono ruotati (traslazione ciclica) a sx

lentit della traslazione a sx dipende dal round

nei round 1, 2, 9 e 16 si ha una rotazione a sx di un solo bit; il

primo bit diventa lultimo bit a dx negli altri round si ha una rotazione a sx di due bit

la permutazione di Ciche produce la met sx di Kiillustrata sotto

si noti che i bit in posizione 9, 18, 22, e 25 sono scartati14 17 11 24 1 5

3 28 15 6 21 10

23 19 12 4 26 8

16 7 27 20 13 2

permutazione per ottenere

la met sx di Ki


48/154


la permutazione di Di-1 ruotato, cio di Di, che

produce la met dx di Ki illustrata sotto

si noti che i bit in posizione 35, 38, 43, e 54 sono

scartati; rimangono cos 24 bit anzich 28 ciascuna delle met di Ki di 24 bit

complessivamente Kiha una lunghezza di 48 bit

14 17 11 24 1 5

3 28 15 6 21 10

23 19 12 4 26 8

16 7 27 20 13 2

permutazione per ottenere

la met dx di Ki


49/154

Un round di DES

ENCRYPTION DECRYPTION


50/154

n-esimo round di DES

CIFRATURA (ENCRYPTION)

i 64 bit in input sono divisi in due met da 32 bit

Ln: met sx dopo l(n-1)-esimo round

Rn: met dx dopo l(n-1)-esimo round

loutput di 64 bit del round si ottiene

concatenando le due met

Ln+1

: met sx dopo ln-esimo round

Rn+1: met dx dopo ln-esimo round

Ln+1 semplicemente Rn


51/154


Rn+1 ottenuto come segue

Rn e Kn sono posti in input alla mangler function; la

mangler function viene anche detta funzione di Feistel

loutput della mangler function, mangler(Rn, K

n), una

quantit di 32 bit; si noti che Rn e Kn sono composti da

32 e 48 bit rispettivamente

loutput mangler(Rn, Kn) viene poi sommato (XOR)con Ln

il risultato ottenuto Rn+1 = mangler(Rn, Kn) Ln


52/154


si noti che ogni round di DES facilmente

invertibile

noti Ln+1, Rn+1 e Kn facile ottenere Ln e Rn

infatti, Rn = Ln+1, ed essendo Rn+1 = mangler(Rn, Kn) Ln risulta che

Rn+1 mangler(Rn, Kn) = Ln (si noti che xyy=x)

cio Ln = Rn+1mangler(Ln+1, Kn)

la mangler function non mai usata in sensoinverso

DES elegantemente progettato da essere invertibile

senza richiedere linvertibilit della mangler function


53/154


DECIFRATURA (DECRYPTION)

esaminando attentamente la figura,

si evince che la decifratura di fatto identica alla

cifratura,

tranne il fatto che le due met da 32 bit sono

invertite

in altre parole, fornendo Rn+1|Ln+1 in input al round n siottiene Rn|Ln in uscita


54/154

Mangler Function ofunzione di Feistel

Rn

n

n,7 n,8

Kn

Kn,1 Kn,2 Kn,7 Kn,8

+

SB2SB1 SB7 SB8

+

++

n+1

Rn+1

n,1 n,2

n+1,1 n+1,2 n+1,7 n+1,8


55/154

Mangler Function ofunzione di Feistel

La mangler function prende in input i 32 bit di Rn, o R per semplificare

i 48 bit della chiave Kn, o Kper semplificare

e produce un output da 32 bit

che sommato ( XOR) con Ln permette di ottenere Rn+1 (ilprossimo R) la prima operazione lespansione di R, da 32 bit a 48

bit R scomposto in otto pezzi da 4 bit R = {r1, r2, , r8}

li-esimo pezzo riviene espanso a 6 bit aggiungendo intesta e in coda rispettivamente lultimo bit di ri-1 e il primobit di ri+1

r1 e r8 sono considerati adiacenti, cio r0 = r8 e r9 = r1


56/154

Espansione di R (Rn) a 48 bit

R a 32 bit

a 48 bit

chunk 1

di Respanso

chunk 2

di Respanso

chunk 3

di Respanso

chunk 4

di Respanso

chunk 5

di Respanso

chunk 6

di Respanso

chunk 7

di Respanso

chunk 8

di Respanso


57/154

Mangler Function S-box

la chiave K(Kn) viene scomposta in otto chunk(pezzi)

da 6 bit

li-esimo chunk di R (Rn) espanso viene sommato (XOR) alli-esimo chunk di K

loutput a 6 bit ottenuto viene sottoposto ad una

sostituzioneS-box che produce un output di 4 bit

ci sono in tutto otto S-box distinte; li-esima S-box elabora la

somma delli-esimo chunk di Ke di R

ogni S-box ha 64 possibili input e 16 possibili output

input diversi possono essere mappati nello stesso output

le S-box sono definite in modo tale che esattamente quattro

input distinti sono mappati in ciascun output possibile


58/154

Mangler Function S-box

ogni S-box pu riguardarsi come quattro S-box separate

aventi 4 bit sia in input che in output

i quattro bit in input corrispondono ai bit interni (dal

secondo al quinto) dellinput globale, e

i due bit esterni (primo e sesto) dellinput globale

servono a selezionare quale dei quattro output ottenuti

rappresenta loutput globale

Nelle slide seguenti sono illustrate la tabelle che

definiscono le otto S-box


59/154

Mangler function Funzione di Fiestel


60/154

Tabella di output di S-box 1

Loutput (a 4 bit) di S-box 1, specifica i primiquattro bit delloutput della mangler function

loutpout y1y2y3y4 espresso dai quattro bit riportatinelle varie celle della tabella

linputx1x2x3x4x5x6 espresso

dai quattro bit internix2x3x4x5 riportati nelle intestazionidelle colonne, e

dai due bit esternix1x6 riportati nelle intestazioni di righe


61/154

Tabelle di S-box 2, S-box 3 e S-box 4


62/154

Tabelle di S-box 5, S-box 6 e S-box 7


63/154

Tabella di S-box 8


64/154

Permutazione delloutput dellS-box

Gli otto output, da 4 bit, delle otto S-box sonoriuniti in un unico output a 32 bit che vienesottoposto ad una permutazione

tale permutazione aumenta il livello di sicurezzaperch le sostituzioni fatte in ciascuna S-box in unround di DES vengono diffuse negli input di pi S-boxnel round seguente

senza tale permutazione, un bit nella parte sx dellinput

influenzerebbe principalmente alcuni bit della parte sxdelloutput

la permutazione illustrata sotto; il primo bit in output siottiene da 16-esimo bit in input, e cos via


65/154

Chiavi deboli e semi-deboli

Ci sono sedici chiavi DES il cui utilizzo

sconsigliato

hanno delle propriet strane

tuttavia la probabilit di generarne unarandomicamente 16/256

anche sconsigliato usare chiavi DES aventi un

valore (interpretate come intero) pari a qualchemigliaia

un avversario potrebbe tentare una ricerca esaustiva a

partire da 0 incrementando ogni volta di 1


66/154


Le sedici chiavi sospette si ottengono combinando lequattro configurazioni base di C0 e D0 a) tutti 1 b) tutti 0 c) 1 e 0 alternati d) 0 e 1 alternati

quattro di queste corrispondono alle chiavi deboli

quelle che combinano le configurazioni a) e b)

le rimanenti dodici corrispondono alle chiavi semi-deboli

1111 1111 1111 1111

0000 0000 0000 0000

1010 1010 1010 1010

0101 0101 0101 0101

C0 D0

4 combinazioni

4 chiavi deboli 16 combinazioni

16 chiavi sospette


67/154


Due chiave sono inverse se cifrare con unaequivale a decifrare con laltra

E(K1, m) = D(K1-1, m)

E(K1

-1, m) = D(K1, m)

Ogni chiave debole coincide con la propriainversa

Linversa di una chiave semi-debole unaltrachiave semi-debole


68/154

Cosa c di speciale in DES?

DES un algoritmo semplice

ci induce a pensare che ognuno pu sviluppare

un algoritmo di cifratura a chiave segreta!

basta prendere i bit, fare qualche sostituzione, qualchemescolamento, ripetere pi volte ed ecco lalgoritmo!

in realt ci sono molti misteri da comprendere

come si giunti alle definizioni delle S-box?

stato provato che invertendo la S-box 3 con la S-box 7

DES un ordine di grandezza pi insicuro per alcuni

attacchi specifici


69/154

Segretezza del processo di progettazione

Il processo di progettazione di DES non fu reso pubblico non si sa se alcuni dettagliprogettuali/implementativi sono stati voluti per aumentare la sicurezza, o

sono puramente casuali, o sono stati apportati per renderlo vulnerabile a particolari

attacchi noti solo ai progettisti

Si dice che il processo di progettazione di DES fumantenuto segreto perch si basava su una attenta

analisi di molti tipi di attacchi crittografici DES fu progettato per resistere a molti tipi di attacchi

crittografici

rendere pubblico il processo di progettazione implicavadivulgare anche le varie tipologie di attacchi


70/154

ALGORITMO IDEAINTERNATIONAL DATA ENCRYPTION

ALGORITHM



71/154

International Data Encryption Algorithm (IDEA)

IDEA, originariamente chiamato IPES (ImprovedProposed Encryption Standard), fu pubblicato nel 1991

Fu progettato per consentire una implementazionesoftware computazionalmente efficiente

IDEA prende in input blocchi di testo in chiaro da 64 bite produce in output blocchi di testo cifrato da 64 bit

La chiave ha una lunghezza di 128 bit

IDEA per molti aspetti somiglia a DES

opera in pi round

entrambi hanno una complicata mangler function che non sottoposta al vincolo di invertibilit generalmenterichiesto per permettere la decifratura


72/154

International Data Encryption Algorithm (IDEA)

la mangler function viene sempre eseguita nella

stessa direzione sia in cifratura che in decifratura

DES e IDEA hanno entrambi la propriet che la cifratura

e la decifratura sono identiche tranne che per

lespansione della chiave

in DES, le stesse chiavi sono usate in ordine inverso

in IDEA, il legame tra le chiavi di cifratura e di

decifratura pi complesso


73/154

Struttura base di IDEA


74/154

Operazioni primitive

Ogni operazione primitiva in IDEA mappa

due quantit di 16 bit in input

in una quantit di 16 bit in output

mentre ogni S-box di DES mappa una quantit di 6 bit ininput in una di 4 bit in output

IDEA usa tre operazioni, tutte facilmente

calcolabili in software, per creare la biiezione che

specifica la cifratura tutte e tre le operazioni sono invertibili, cosa

importante per eseguire IDEA allindietro (decifratura)


75/154


Le tre operazioni primitive sono or-esclusivo (XOR ) bit a bit unaddizione (+) leggermente modificata (mod 216)

una moltiplicazione () leggermente modificata(mod (216 + 1))

X=x1x2x16

Y= y1y2y16

Z= z1z2z16

X=x1x2x16

Y= y1y2y16

Z= z1z2z16

X=x1x2x16

Y= y1y2y16

Z= z1z2z16


76/154


la ragione che non consente di utilizzare laddizione e lamoltiplicazione tradizionale che il risultato a 16 bit e

possono esserci situazioni di overflow dato che anche

gli input sono a 16 bit

laddizione in IDEA consista semplicemente in unasomma binaria in cui si trascura il riporto finale; ci

equivale a dire che si tratta di unaddizione mod216

la moltiplicazione in IDEA si ottiene calcolando prima il

risultato a 32 bit, e prendendo poi il resto delladivisione per 216 + 1; con un po di furbizia ci

fattibile in modo efficiente


77/154


la moltiplicazione mod (216 + 1) invertibile, nel sensoche ogni numeroxtra 1 e 216 ha un inverso y(cio un

numero tra 1 e 216 tale che la moltiplicazione per y

annulla leffetto della moltiplicazione perx: a

risulta ax y= a), poich 216

+ 1 un numero primo tuttavia c una piccola furbata, il numero 0, che pu

essere espresso con 16 bit, non avrebbe un inverso,

mentre il numero 216, presente nellinsieme delle classi

di resto modulo 216

+ 1, non esprimibile con 16 bit, entrambi i problemi sono risolti considerando 0

come la codifica di 216


78/154

Invertibilit delle operazioni primitive

Come possibile invertire le tre operazioni

primitive?

chiaramente non si tratta di uninversione che

permette di risalire ai due operandi a partire dalsolo risultato finale!

seXY=Z, non possibile risalire adXe ad Ya partiredal soloZ,

tuttavia, nellesecuzione allindietro di IDEA sarannonoti un operando e il risultato, diciamo Ye Z, e da

questi sar possibile ottenereX


79/154


Si consideri loperazione generica Xop Y=Z e sisupponga di conoscere YeZ,

allora per ciascuna delle tre operazioni primitive,

X ottenibile come segue

Inversione or-esclusivo (XOR ) bit a bit seXY=Z XYY=ZY X=ZY

rispetto alloperazione ogni numero linverso di sestesso; YY= 0


80/154


Inversione addizione (mod 216)(+) seX+ Y(mod 216) =Z

X+ Y+ (-Y)(mod 216) =Z+ (-Y) (mod 216) X=Z+ (-Y) (mod 216)

rispetto alloperazione + linverso di un numero Y il numero-Y(mod 216)

Inversione moltiplicazione (mod 216 + 1)() seXY(mod (216 + 1)) =Z XYY-1(mod (216 + 1)) =ZY-1(mod (216 + 1)) X=ZY-1(mod (216 + 1))

Y-1(mod (216 + 1)) ottenibile con il lalgoritmo di Euclide

b l d ll


81/154


Lunica parte di IDEA che non

necessariamente invertibile la mangler

function

La gestione del progetto di IDEA stata molto

ingegnosa per evitare la necessit di invertire

la mangler function

E i d ll hi i


82/154

Espansione delle chiavi

La chiave di 128 bit espansa in 52 chiavi da

16 bit, K1, K2, , K52

lespansione per la cifratura diversa da quella

per la decifratura cifratura e decifratura coinciderebbero se non

fosse per le chiavi che differiscono

sia per lordine,

sia per il valore delle chiavi usate nei round dispari

E i d ll hi ( if )


83/154

Espansione della chiave (cifratura)

La chiave di 128 bit espansa in 52 chiavi da16 bit, K1, K2, , K52

la procedura come segue

le prime otto chiavi K1, K

2, , K

8sono ottenute

spezzando la chiave da 128 bit in corrispondenza dei bitin posizione 161, 162, , 167

le successive otto chiavi K9, K10, , K16 sono generateallo stesso modo, ma partendo dal bit in posizione 25 e

tornando allinizio quando si arriva alla fine (scansioneciclica)

le successive otto chiavi sono generate considerando 25bit di offset in pi e cos via finch non si ottengono 52chiavi

E i d ll hi ( if )


84/154


si noti che in 6 fasi vengono generate 48 chiavi e in 7fasi 52 nellultima fase, la settima, sono generatesolo 4 chiavi

lultima fase inizia dal bit in posizione 23 e si estende

fino al bit in posizione 86 i bit in posizione da 1 a 22e da 87a 128 sono usati una volta in meno rispetto

quelli in posizione da 83 a 128

E i d ll hi ( if t )


85/154


generazione delle chiavi K1, K2, , K8

generazione delle chiavi K9, K10, , K16

E i d ll hi ( if t )


86/154


la generazione delle 52 chiavi di decifratura sarillustrata nel seguito

WARNING! nello standard IDEA c una piccola stranezza: le chiavi

K50 e K51 sono invertite!

probabilmente c stata una svista nella definizione

dello standard! se si desidera implementare IDEA necessario, dopo

aver generato le 52 chiavi di cifratura, provvedere ad

invertire K50 e K51

IDEA d


87/154

IDEA un round

IDEA esegue 17round

i round dispari sono diversi da quelli pari

in alcuni casi si parla di 8 round; due round vengono

considerati come un singolo round

linput di ogni round una quantitXa 64 bit separata

in quattro quantitXa,Xb,Xc,Xdda 16 bit

cioX=Xa |Xb |Xc |Xd

ad ogni round linputXa |Xb |Xc |Xdviene combinatocon alcune delle 52 chiavi per ottenere in output una

versione aggiornata diXa |Xb |Xc |Xd i round dispari usano quattro delle 52 chiavi Ki: Ka, Kb, Kc, Kd

i round pari usano due delle 52 chiavi Ki: Ke, Kf

IDEA d


88/154

IDEA un round

Ad esempio nel round 1, Ka, Kb, Kc, Kd= K1, K2, K3, K4 nel round 2, Ke, Kf= K5, K6 nel round 3, Ka, Kb, Kc, Kd= K7, K8, K9, K10 nel round 4, Ke, Kf= K11, K12

in un round dispari gli input sono

Xa,Xb,Xc,Xd Ka, Kb, Kc, Kd

in un round pari gli input sono

Xa,Xb,Xc,Xd K

e

, Kf

R d di i


89/154

Round dispari

Il round dispari semplice XaXaKa XdXdKd X

c

Xb

+ Kb

XbXc + Kc

R d di i


90/154

Round dispari

Si osservi che un round dispari facilmente invertibile il vecchioXa si ottiene moltiplicando () il nuovoXa per

linverso moltiplicativo mod (216 + 1) di Ka analogamente si procede conXd

il vecchioXb si ottiene sommando al nuovoXclinversoadditivo di Kb, cio sottraendo Kb

analogamente si procede conXc

in fase di decifratura il round dispari analogo alla cifratura, tranne il fatto di

dover considerare per ogni chiave il suo inversomatematico (rispetto le relative operazioni)

ci annulla le operazioni fatte nella fase di cifratura

R d i


91/154

Round pari

Il round pari pi complicato

gli input sono Xa,Xb,Xc,Xd e Ke, Kf

prima vengono calcolate due quantit (a 16 bit)

Yin eZin

poi viene applicata una funzione, la mangler

function, che

prende in input Yin,Zin, Ke e Kf, e

produce in output due quantit (a 16 bit) YouteZout

in fine, vengono calcolati

i nuovi valori diXa,Xb,Xc,Xdcombinando

i loro vecchi valori con YouteZout

Round pari


92/154

Round pari

In particolare, si hanno le seguenti relazioni Yin =XaXb Zin =XcXd Y

out

= ((Ke

Yin

) +Zin

)Kf

Zout= (KeYin) + Yout

i nuovi valori diXa,Xb,Xc,Xd sono

XaXaYout XbXbYout XcXcZout XdXdZout

Round pari


93/154

Round pari

Inversione del round pari


94/154


linversione del round pari veramente ingegnosa il round pari coincide con il suo inverso

la decifratura di un round pari usa le stesse chiavie non il loro inverso matematico

nella decifratura dei round dispari si considerava un setdi chiavi ottenuto facendo linverso matematico dellechiavi di cifratura

il round pari prende in input

Xa,Xb,Xc,Xd e Ke, Kf

e produce in output

Xa,Xb,Xc,Xd cio i nuovi valori diXa,Xb,Xc,Xd



95/154


risulta che (sar mostrato dopo) se gli input del round pari sonoXa,Xb,Xc,Xd, e

le chiavi rimangono le stesse,

loutput Xa

,Xb

,Xc

,Xd

Xa Xb Xc Xd

Xa

Xb

Xc

Xd

KeKf

round 2nENCRYPTION

Xa Xb Xc Xd

Xa

Xb

Xc

Xd

round 2nDECRYPTION

Inversione del round pari prova


96/154


Mostreremo che inserendo in input al round pariXa,Xb,Xc,Xd, e

considerando le stesse chiavi Ke, Kf

si ottengono in outputXa,Xb,Xc,Xd tali che Xa =Xa Xb =Xb Xc =Xc Xd=Xd

Prova

daX

a =XaYoute daX

b =XbYout Yin =XaXb = (XaYout) (XbYout) =XaXb = Yin daXc =XcZoute daXd=XdZout Zin =XcXd= (XcZout) (XdZout) =XcXd=Zin



97/154


gli input della mangler function sono gli stessi Yout= Yout e Zout=Zout Xa =XaYout= (XaYout) Yout=

=XaYoutYout=Xa Xb =XbYout= (XbYout) Yout=

=XbYoutYout=Xb Xc =XcZout= (XcZout) Zout=

=XcZoutZout=Xc Xd=XdZout= (XdZout) Zout=

=XdZoutZout=Xd

Calcolo chiavi di decifratura


98/154


IDEA stato progettato in modo tale che lo stessocodice (o hardware) pu effettuare sia la cifraturache la decifratura

scegliendo in modo opportuno (diversamente) le 52

chiavi espanse per la cifratura e per la decifratura

si possono scegliere la chiavi inverse (di decifratura) inmodo tale che la procedura di cifratura, cos come ,esegue anche la decifratura

lidea base di prendere le inverse (dal punto di vistamatematico) delle chiavi di cifratura e usarle in ordineopposto



99/154


Si considerino le 52 chiavi usate in cifratura K1, K2, ,K52 nei round dispari sono state usate quattro chiavi mentre

nei round pari solo due round 1 K1, K2, K3, K4 round 3 K7, K8, K9, K10 round 17 K49, K50, K51, K52

quindi le prime quattro chiavi da usare nel primo round didecifratura devono essere

K1 : inverso matematico di K49; trattandosi di una moltiplicazione() K1 deve essere linverso moltiplicativo di K49 mod (216 + 1) K2 : inverso additivo di K50; cio -K50 K3 : inverso additivo di K51 ; cio -K51 K4 : inverso moltiplicativo di K52



100/154


considerando la seguente notazione im(Ki): inverso moltiplicativo di Kimod (2

16 + 1)

ia(Ki): inverso additivo di Kimod 216

le 52 chiavi di decifratura Kisono

round 1: K1, K2, K3,K4 = im(K49), ia(K50), ia(K51), im(K52)

round 2: K5, K6= K47, K48 round 3: K7, K8, K9,K10 = im(K43), ia(K44), ia(K45), im(K46)

round 4: K11, K12= K41, K42

round 17: K49, K50, K51,K52 = im(K1), ia(K2), ia(K3), im(K4)

Architettura hardware/software


101/154

Architettura hardware/software

Da quanto detto, una possibile architettura diun sistema hardware/software per IDEA laseguente

5216 bit

input

plaintext or ciphertext

output

ciphertext or plaintextENCRYPTION

KEY EXP

K E/D

K*

128 bit

64 bit 64 bit

E/D true K* = K1

, K2

, , K52E/D false K* = K1, K2, , K52

Funziona IDEA?


102/154

Funziona IDEA?

Si mostrato che nota la chiave di cifratura ladecifratura consente di risalire al testo in chiaro

Riguardo il livello di sicurezza offerto da IDEA non esistono prove formali che stabiliscono in modo

chiaro quanto IDEA sia sicuro

si assume che sia sicuro semplicemente perch ancora

nessuno ha reso pubblico un modo per violarlo

chiaramente, tentare di violare IDEA con un approccio

esaustivo richiede attualmente una quantit smisurata

di risorse di calcolo/tempo


103/154

ALGORITMO AES

ADVANCED ENCRYPTION STANDARD


Advanced Encryption Standard (AES)


104/154

Advanced Encryption Standard (AES)

AES fu introdotto perch DES aveva una chiave troppo corta

3DES (triplo DES) era troppo lento

IDEA era protetto da un brevetto, era in parte

sospetto e lento

Il NIST si impegn a sviluppare un nuovo standard

non si trattava di un problema solo tecnico, ma

anche di un problema politico alcuni rami del governo avevano ostacolato il pi possibile la

diffusione e lesportazione della crittografia sicura

il fatto che il governo appoggiasse NIST era visto conscetticismo; molti non si fidavano

Un po di storia


105/154

Un po di storia

Il NIST voleva realmente creare un nuovostandard di sicurezza eccellente

cio efficiente, flessibile, sicuro e free (non protetto),

ma quale poteva essere il modo migliore per farlo?

da un lato NIST doveva essere parte integrante del processo

di progettazione

poich si trattava di uno sforzo ingente e sembrava che

nessun altro avesse le competenze tecniche e lenergia per

compierlo

dallaltro proporre un cifrario sviluppato, segretamente, dalla

NSA non avrebbe funzionato; nessuno si sarebbe fidato, ci

potevano essere delle trapdoor

Un po di storia


106/154

Un po di storia

Nel 1997 il NIST annunci una gara per laselezione di un nuovo standard di cifratura

destinato a proteggere informazioni governativesensibili

la gara era aperta ad ogni persona/gruppo in qualsiasiparte del mondo

furono specificati i requisiti del cifrario incluso unadocumentazione che spiegasse le ragioni delle scelte

progettuali per molti anni si tennero delle conferenze per la

presentazione di proposte,

che venivano sottoposte a cicli di revisione eseguiti dacrittografi esperti e motivati

Un po di storia


107/154

Un po di storia

Dopo molti anni di studio e discussioni, il NISTscelse lalgoritmo Rijndael

proposto da due crittografi belgi Joan Daemen eVincet Rijmen

Rijndael prevede diverse lunghezze per i blocchi eper la chiave

128, 160, 192, 224, e 256 bit

la lunghezza di un blocco e quella della chiave possonodifferire

Il 26 Novembre 2001, viene emanato AES

una standardizzazione di Rijndael

Un po di storia


108/154

Un po di storia

Lo standard AES fissa la lunghezza dei blocchi a 128 bit

la chiave pu essere di 128, di 192 o di 256 bit

si parla di AES-128, AES-192 e AES-256

Nel seguito si descriver Rijndael

specificando di volta in volta i parametri di AES

Rijndael somiglia a DES e a IDEA

ci sono pi round che strapazzano un blocco di testoin chiaro per ottenere il corrispondente cifrato, e

c un algoritmo per lespansione della chiave; a partiredalla chiave segreta genera le chiavi da usare nei vari

round

Rijndael/AES parametri


109/154


Rijndael ha una struttura flessibile grazie allusodi due parametri indipendenti, e di un terzo

parametro derivato dai primi due

Nbdimensione di un blocco: numero di parole (word)da 32 bit (colonne da 4 ottetti) in un blocco da cifrare

in AES Nb = 4, un blocco ha lunghezza 128 bit4 parole da32 bit; 4 colonne da 4 ottetti

ottetto

Nb



110/154


Nkdimensione della chiave: numero di parole(word) da 32 bit (colonne da 4 ottetti) in una

chiave di cifratura

in AES-128 Nk= 4

in AES-192 Nk= 6

in AES-256 Nk= 8

in Rijndael Nkpu essere un qualsiasi intero tra 4 e 8

ottetto

NK



111/154


Nrnumero di round: questo parametro dipendeda Nb e da Nk pi lunga la chiave pi round sono necessari per

rendere la violazione della cifratura difficile quanto un

attacco a forza bruta sulla chiave il numero di round deve aumentare allaumentare della

lunghezza di un blocco (e della chiave); ogni bit deltesto in chiaro (e della chiave) deve influenzare (inmodo complesso) ciascun bit del testo cifrato

Rijndael specifica che Nr= 6 + max(Nb, Nk) in AES-128 Nr= 10 in AES-192 Nr= 12 in AES-256 Nr= 14

Array di stato


112/154

Array di stato

Rijndael mantiene un array di statorettangolare

ogni elemento dellarray un ottetto

complessivamente ci sono Nb colonne da 4 ottetti lo stato iniziale ottenuto popolando larray, colonna

per colonna, mediante le Nb colonne da 4 ottetti che

costituiscono il blocco di input

durante gli Nrround lo stato viene modificato

il blocco di output dellalgoritmo si ottiene leggendo

colonna per colonna lo stato finale

Array di stato


113/154

Array di stato

Prima del round 1, tra i vari round, e dopo ilround Nrviene eseguito

lor-esclusivo ( XOR) del contenuto dellarray di

stato, con i prossimi 4Nb ottetti della chiave espansa

gli ottetti della chiave espansa vengono letti per

colonna in modo da formare un matrice di Nb colonne

da 4 ottetti ciascuna

i primi Nr1 round comprendono una sequenza di

operazioni identiche, mentre il round Nrne

omette una

Struttura base di Rijndael


114/154

Struttura base di Rijndael

Espansione della chiave


115/154


La chiave segreta di Rijndael un bloccoformato da 4Nkottetti

Lalgoritmo di espansione della chiave

scandisce la chiave in modo da ottenere Nkcolonne da 4 ottetti,

poi espande la matrice ottenuta introducendo

delle colonne (da 4 ottetti) aggiuntive, lespansione si arresta quando si hanno

complessivamente (Nr+ 1)Nb colonne

lesatta quantit di chiavi espanse



116/154


la procedura di espansione usa lo stesso tipo dioperazioni primitive usate durante i round

Numerazioni

righe, colonne, e chiavi di round sono numerate apartire 0

i round sono invece numerati a partire da 1



117/154


Rijndael utilizza quattro operazioni primitive1. or-esclusivo (XOR )

in cui sono coinvolte le chiavi espanse

2. sostituzione di byte, chiamata S-box

si tratta di una sostituzione ottetto-per-ottetto (byte-per-

byte) definita da una specifica tabella

per ciascuno dei possibili 256 byte in input viene specificato

il corrispondente byte in output tra i 256 possibili

per la rappresentazione della tabella fa comodo usare la

notazione esadecimale; ad esempio FCrappresenta il 252-

esimo byte

la tabella pu essere visualizzata come una matrice 1616

Rijndael Sbox


118/154

Rijndael Sbox

Esempio

il 97-esimo byte il numero

61HEX in esadecimale,quindi mappato nel byte

nella riga 6 e colonna 1che EFHEXche corrisponde

al 239-esimo byte

in binario si ha che

(1100001)2= (97)10 mappato in

(11101111)2 = (239)10



119/154


3. scorrimento circolare di ottetti (byte) di una riga o diuna colonna pari a un qualche numero di celle

4. mescolamento colonne, MixColumn: sostituzione diuna colonna di 4ottetti con unaltra colonna di 4ottetti MixColumn pu essere implementata con una singola tabella

contenente 256 colonne di 4 ottetti

ciascuno dei 4 ottetti in una colonna di input usato comeun indice per recuperare una colonna dalla tabella

ogni colonna recuperata dalla tabella ruotata (scorrimento

verticale circolare dallalto in basso) verticalmente in modotale che il suo ottetto in cima sia posto nella stessa rigadellottetto di input;

e le quattro colonne ruotate sono sommate XOR () perprodurre la colonna di output

MixColumn mediante tabella di lookup


120/154

p

4 ottetti di unacolonna di input

scorrimento della colonna per

allinearla allottetto di input ad

da cui stata derivata

4 ottetti di unacolonna di output

MixColumn tabella di lookup


121/154

p

Esempio

Allottetto 2b corrisponde la colonna

di 4 ottetti che si trova allincrocio della

riga 2 e della colonna b, cio la

colonna56

2b

28

7d



122/154

p p

Lor-esclusivo (XOR ) chiaramente invertibile coincide con il suo inverso:XYY=X

Linversa della S-box si ottiene considerandosemplicemente una tabella diversa

cio la tabella inversa

Linversa dello scorrimento circolare di una riga ocolonna si ottiene semplicemente eseguendo lo

stesso scorrimento, ma in direzione opposta Linversa di MixColumn, detta InvMixColumn,

esattamente come MixColumn, ma con unatabella di lookup diversa

Rijndael S-box inversa


123/154

j

InvMixColumn tabella di lookup


124/154

p

Decifratura di Rijndael


125/154

j

Il cifrario inverso di Rijndael pu pertantoimplementarsi applicando

le inverse delle operazioni primitive,

eseguite in sequenza opposta rispetto quella di cifratura

Tuttavia, si pu mostrare che, grazie alle propriet matematiche di cui gode Rijndael,

il cifrario inverso ha una struttura molto simile al cifrariodiretto, ma con operazioni invertite, e con le chiavi di

round non soltanto in ordine inverso, ma con InvMixColumn applicato a tutte tranne la prima e

lultima colonna



126/154

p

Lespansione delle chiavi inizia con la chiave segreta organizzata come Nk

colonne di 4 ottetti, e

iterativamente genera le prossime Nkcolonne della

chiave espansa



127/154

p

Per generare li-esimo insieme di Nkcolonne iinizia da 1; lo 0-esimo insieme la chiave segreta

serve soltanto l(i-1)-esimo insieme di colonne

la prima colonna (colonna 0) del nuovo insieme siottiene mediante

uno scorrimento circolare verticale di una cella

dellultima colonna dell(i-1)-esimo insieme, e

applicando la S-box ad ogni ottetto, e

sommando in XOR () una costante Cicon lottetto 0(che sta in cima)

Espansione della chiave (Nk 6)


128/154

p ( k )

le rimanenti colonne sono generate a turno sommando in XOR la precedente colonna con,

la corrispondente colonna del precedente (i-1)-esimo

insieme

Valori delle costanti Ci


129/154

i

1 2 4 8 10 20 40 80 1b 36

6c d8 ab 4d 9a 2f 5e bc 63 c6

97 35 6a d4 B3 7d fa ef c5 (91)

i= 1 to 10

i= 11 to 20

i= 21 to 30

Espansione della chiave (Nk > 6)


130/154

p ( k )

c uneccezione nel procedimento di espansionedella chiave,

se Nk> 6, allora necessario uno step aggiuntivo

per generare la colonna 4

necessario applicare la S-box ad ogni ottetto

lespansione della chiave termina non appena (Nr

+ 1)Nb colonne di chiavi espanse sono generate

Espansione della chiaveNk > 6


131/154

p k

Rijndael round


132/154

j

Ogni round di Rijndael una sequenza identica di treoperazioni:

1. Ogni ottetto della matrice di stato viene sottopostoalla S-box

2. Scorrimenti circolari La riga 1 dello stato viene fatta scorrere a sx di una colonna

La riga 2 dello stato viene fatta scorrere a sx di 2 + Nb/8colonne (2 se Nb< 8, 3 altrimenti)

La riga 3 dello stato viene fatta scorrere a sx di 3 + Nb/7colonne (3 se Nb< 7, 4 altrimenti)

(in AES si semplifica in scorrimento a sx di icolonne della riga i)

3. Ogni colonna dello stato viene sottoposta allaMixColumn; il round Nromette questa operazione

Rijndael round invertito


133/154

j

Essendo ogni operazione invertibile la decifratura pu effettuarsi applicando in ordine

inverso linversa (in senso matematico) di ognioperazione, e

usando le chiavi di round in ordine inverso

Tuttavia la decifratura pu avere la stessastruttura della cifratura necessario usare le chiavi di round in ordine

opposto, e

applicare InvMixColumn ad ogni colonna delle chiaviespanse tranne quelle del round iniziale e finale

Rijndael round invertito


134/154

Ogni round invertito di Rijndael una sequenzaidentica di tre operazioni:

1. Ogni ottetto della matrice di stato viene sottopostoalla S-box

2. Scorrimenti circolari La riga 1 dello stato viene fatta scorrere a dx di una

colonna

La riga 2 dello stato viene fatta scorrere a dx di 2 + Nb/8colonne (2 se Nb< 8, 3 altrimenti)

La riga 3 dello stato viene fatta scorrere a dx di 3 + Nb/7colonne (3 se Nb< 7, 4 altrimenti)

(in AES si semplifica in scorrimento a dx di icolonne della riga i)

3. Ogni colonna dello stato viene sottoposta alla

InvMixColumn; il round Nromette questa operazione


135/154

CIFRARI A FLUSSO E RC4


Cifrari a blocchi vs cifrari a flusso


136/154

Un cifrario a blocchi elabora un blocco dielementi in ingresso per volta produce un blocco di uscita per ciascun blocco di

ingresso

il testo in chiaro deve essere preliminarmente suddivisoin blocchi il testo cifrato si ottiene combinando i vari blocchi cifrati DES, IDEA e AES sono esempi di cifrari a blocchi simmetrici

Un cifrario a flusso elabora continuamente gli

elementi in ingresso produce in uscita un flusso di elementi cifrati

gli elementi cifrati vengono prodotti singolarmente, uno allavolta, man mano che la cifratura procede

Cifrari a blocchi vs cifrari a flusso


137/154

Sebbene i cifrari a blocchi siano molto picomuni, in alcune applicazioni i cifrari a flussosono pi adatti

applicazioni che richiedono la cifratura/decifratura di

un flusso di dati ad esempio le trasmissioni di stream audio/video

di seguito sar esaminato il cifrario a flusso pipopolare: RC4

preliminarmente sar discussa la struttura generale diun cifrario a flusso

Struttura di un cifrario a flusso


138/154

Un tipico cifrario a flusso cifra il testo in chiaro unbyte per volta

sebbene possa essere progettato per agire su unitpi grandi di un byte

pseudo-random

stream gener.

pseudo-random

stream gener.

K K

plaintext

stream

plaintext

stream

ciphertext

stream

ENCRYPTION DECRYPTION

keystream keystream

Struttura di un cifrario a flusso


139/154

La chiave segreta K(di lunghezza finita) lingresso di un generatore pseudo-casuale dibit

che produce un flusso (di lunghezza arbitraria) di

byte apparentemente casuale, chiamato chiave diflusso (keystream)

la chiave di flusso un flusso

impredicibile se non si conosce la chiave, maviene generato in modo deterministico a partiredalla chiave

non presenta regolarit statistiche

Cifratura


140/154

Il keystream combinato un byte alla voltacon il flusso del testo in chiaro mediante un

or-esclusivo (XOR ) bit a bit

il risultato di questo processo il flusso cifrato ad esempio, se

pi= 11001100 li-esimo byte del flusso del testo in

chiaro, e

ki= 01101100 li-esimo byte del keystream, allora

ci=piki= 10100000 li-esimo byte del flusso deltesto cifrato

Decifratura


141/154

La decifratura richiede luso della stessasequenza pseudo-casuale (keystream)

combinata un byte alla volta con il testo cifrato

mediante or-esclusivo (EX-OR ) bit a bit ad esempio, se

ci=piki= 10100000 li-esimo byte del flusso deltesto cifrato, e

ki= 01101100 li-esimo byte del keystream, allora

pi= ciki= (piki)ki=pi (kiki) =pi= 11001100 li-esimo byte del flusso del testo in chiaro

Osservazioni


142/154

Pi casuale laspetto del keystream, pi randomizzato il testo cifrato

rendendo la crittoanalisi pi difficile

Pertanto il keystream

dovrebbe avere un periodo grande

la funzione deterministica che genera il keystream, a partiredalla chiave segreta, per forza di cose periodica

dovrebbe approssimare il pi possibile un flusso

casuale ad esempio, 0 e 1 dovrebbero essere equamente presenti

riguardando il keystream come una sequenza di byte, tutti i256possibili byte dovrebbero apparire disordinatamente econ una frequenza uniforme

Osservazioni


143/154

Come nei cifrari a blocchi, necessario che lachiave sia sufficientemente lunga per

proteggersi dagli attacchi a forza bruta

preferibile una lunghezza della chiave di almeno128 bit

Cifrari a flusso vs cifrari a blocchi


144/154

Se un cifrario a flusso correttamente progettato pu essere sicuro tanto quanto un cifrario a blocchi

a parit di lunghezza della chiave segreta

Il vantaggio principale di un cifrario a flusso che

quasi sempre pi veloce, vedi tabella, ed

facilmente implementabile

spesso bastano poche linee di codice, vedi descrizione RC4



145/154

Confronto delle velocit di cifrari simmetrici suun Pentium II

Cifrario Lunghezza della chiave Velocit variabile (Mbps)

DES 56 9

3DES 168 3

RC2 variabile 0,9

RC4 variabile 45



146/154

Il vantaggio di un cifrario a blocchi che la chiavesegreta riutilizzabile per pi comunicazioni

se due testi in chiaro sono cifrati con la stessa chiave

segreta, usando un cifrario a flusso, la crittoanalisi

spesso molto semplice

se i due flussi di testo cifrato sono sommati in XOR () il flusso risultante lo XOR dei flussi di testo inchiaro

se i testi in chiaro sono stringhe testuali, numeri di carta di

credito o altri flussi di byte con propriet note lacrittoanalisi pu aver successo

Algoritmo RC4


147/154

RC4 un cifrario a flusso con dimensione della chiave variabile,

con funzionamento orientato al byte

fu progettato nel 1987 da Ron Rivest RSA Security

Si basa sulluso di una permutazione casuale

dagli studi sembra che il periodo del cifrario siasuperire a 10100

viene usato

negli standard SSL/TLS (Secure Socket Layer/Transport LayerSecurity)

nel protocollo WEP (Wired Equivalent Privacy)

nel protocollo WPA (WiFi Protected Access)

Algoritmo RC4


148/154

Lalgoritmo RC4 molto semplice da spiegare;basta spiegare come viene generato il

keystream

lalgoritmo mantiene un array di statomonodimensionale S contenente 256 byte

S[0], S[1], , S[255] sono i 256 byte

ogni elemento/byte S[i] rappresenta un numero da 1

a 255

una chiave di lunghezza variabile da 1 a 256 byte

(da 8 a 2048 bit) viene usata per inizializzare il

contenuto dellarray di stato

Algoritmo RC4


149/154

S contiene in ogni momento una delle 256!permutazioni dei numeri da 0 a 255

per la cifratura/decifratura viene generato un byte

kselezionando da S uno dei 255 elementi in

maniera sistematica

subito dopo la generazione del byte k, gli elementi

di S vengono permutati

lalgoritmo prosegue alternando le ultime due fasi(generazione di ke permutazione) finch il flusso

in input non termina

RC4 inizializzazione


150/154

gli elementi di S vengono impostati uguali ai valori da0 a 255 in ordine crescente

S[0] = 0, S[1] = 1, , S[255] = 255

un vettore temporaneo T, della stessa lunghezza di S,viene usato per memorizzare temporaneamente lachiave K

se la lunghezza di K 256 byte Kviene trasferita in T altrimenti, Kviene copiata pi volte in Tfino a riempirlo

/* Inizializzazione */for i = 0 to 255 do {

S[i] = i;

T[i] = K[imodkeylen]; // keylen: lunghezza di S

}

RC4 permutazione iniziale


151/154

successivamente si user Tper produrre lapermutazione iniziale

si scandisce S e per ciascun S[i], si scambia S[i] con unaltro elemento di S scelto in modo sistematico in base,tra laltro, al contenuto di T[i]

poich la sola operazione su S lo scambio, il soloeffetto una permutazione

S contiene ancora tutti i numeri da 0 a 255

/* Permutazione iniziale di S */j = 0;

for i = 0 to 255 do {

j = (j + S[i] + T[i])mod256;

scambia(S[i], S[j]);

}

RC4 generazione del flusso


152/154

Una volta che S inizializzato, la chiavesegreta K(quindi anche larray T) non vienepi utilizzata

il keystream viene generato facendo una

scansione ciclica di S ciascun elemento S[i] viene scambiato con un altro byte

di S a secondo di uno schema che dipende dallaconfigurazione corrente di S

dopodich, viene generato un singolo byte kdelkeystream sempre in base alla configurazione correntedi S

RC4 generazione del flusso


153/154

/* Generazione del flusso */

i, j = 0;while (true) {

i = (i + 1)mod256;

j = (j + S[i])mod256;

scambia(S[i], S[j]);

t = (S[i] + S[j])mod256;k = S[t];

}

Bibliografia


154/154

[KPS02] C. Kaufman, R. Perlman, M. Speciner. NetworkSecurityPrivate Communication in a Public World.Prentice Hall.

[PFL08] C. P. Pfleeger, S. L. Pfleeger. Sicurezza inInformatica. Pearson, Prentice Hall.

[STA07] W. Stallings. Sicurezza delle reti. Pearson,Prentice Hall.

[Wiki-it] http://it.wikipedia.org/wiki/

[Wiki-en] http://en.wikipedia.org/wiki/

[ISECOM] Institute for Security and OpenMethodologies

D03 Crittografia a Chiave Segreta

Documents

Transcript of D03 Crittografia a Chiave Segreta