Hardware and embedded security - parte 4

Indice

1 Random Number Generators 6

1.1 Introduzione generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Numeri casuali nella crittografia . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 Ruolo dei numeri casuali nei sistemi crittografici . . . . . . . . . . . . . . 6

1.2.2 Requisiti fondamentali di un buon generatore casuale . . . . . . . . . . . 7

1.3 Entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.1 Definizione intuitiva di entropia . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.2 Entropia come sorgente di casualità . . . . . . . . . . . . . . . . . . . . . 7

1.4 Pseudo-Random Number Generators . . . . . . . . . . . . . . . . . . . . . 8

1.4.1 Definizione di PRNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.2 Seed e determinismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4.3 Obiettivi di un PRNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4.4 Periodicità dei PRNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.5 Linear Feedback Shift Register . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5.1 Definizione di LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5.2 Funzionamento generale di un LFSR . . . . . . . . . . . . . . . . . . . . . 10

1.5.3 Maximal length LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5.4 Primitive polynomial e taps . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.6 True Random Number Generators . . . . . . . . . . . . . . . . . . . . . . . 11

1.6.1 Definizione di TRNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.6.2 Physical TRNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6.3 Non-Physical TRNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.7 Hybrid Random Number Generators . . . . . . . . . . . . . . . . . . . . . 13

1.7.1 Concetto di Hybrid RNG . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.7.2 Reseeding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.7.3 Vantaggi dell’architettura ibrida . . . . . . . . . . . . . . . . . . . . . . . 14

1.8 Health Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.8.1 Funzione degli health tests . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.8.2 Repetition Count Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.8.3 Adaptive Proportion Test . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.9 Good TRNG Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.9.1 Entropy Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.9.2 Harvesting Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.9.3 Post-processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.9.4 Requisiti progettuali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Sources of Randomness in Digital Systems 16

2.1 Casualità nei circuiti digitali . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Clock Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.1 Clock ideale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1 2

2.2.2 Clock reale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.3 Cause del jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3 Componenti del jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.1 Random jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.2 Deterministic jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.3 Overall jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Metastability 19

3.1 Definizione generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Metastabilità nei circuiti digitali . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.1 Setup time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.2 Hold time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Risoluzione della metastabilità . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 Extraction of Randomness from Clock Jitter 20

4.1 Principio di estrazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2 Difficoltà pratica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5 TRNG Architecture Based on Ring Oscillators 21

5.1 Ring Oscillators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.2 Ruolo degli oscillatori nei TRNG . . . . . . . . . . . . . . . . . . . . . . . . 22

5.3 Process variations ed environmental variations . . . . . . . . . . . . . . . 22

5.3.1 Process variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.3.2 Environmental variations . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.4 Selection & Operation Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.5 Capture Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6 Jitter Accumulation 23

6.1 Necessità di accumulare jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.2 Tecniche per produrre clock sfasati . . . . . . . . . . . . . . . . . . . . . . . 23

6.2.1 Oscillatori multipli indipendenti . . . . . . . . . . . . . . . . . . . . . . . 23

6.2.2 Oscillatore multi-fase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

7 Multi-Ring Oscillator-Based TRNG 24

7.1 Principio di funzionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

8 Self-Timed Ring Oscillator-Based TRNG 25

8.1 Principio generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

9 Post-processing 25

9.1 Funzione del post-processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

9.2 Algorithmic post-processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

9.3 Cryptographic post-processing . . . . . . . . . . . . . . . . . . . . . . . . . 26

3

10Fibonacci-Galois Ring Oscillator Architecture 26

10.1 FiRO e GaRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

10.2 FiGaRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

10.2.1 Aggregazione e miglioramento dell’entropia . . . . . . . . . . . . . . . . . 27

10.2.2 Tolleranza ai guasti e resilienza strutturale . . . . . . . . . . . . . . . . . 27

11Transizione da pattern periodico a segnale caotico 27

11.1 Origine del comportamento caotico . . . . . . . . . . . . . . . . . . . . . . 27

11.2 Deterministic chaos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

11.3 Estrazione del bitstream dal comportamento caotico . . . . . . . . . . . 28

12Entropy and Randomness Evaluation 28

12.1 Entropia di Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

12.2 Significato pratico dell’entropia . . . . . . . . . . . . . . . . . . . . . . . . . 29

12.3 Entropia nei sistemi caotici . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

13Periodic Collapse 29

13.1 Definizione di periodic collapse . . . . . . . . . . . . . . . . . . . . . . . . . 29

13.2 Perché il periodic collapse è pericoloso . . . . . . . . . . . . . . . . . . . . 30

14Mitigation Strategies for Periodic Collapse 30

14.1 Introduzione di interazioni non lineari . . . . . . . . . . . . . . . . . . . . . 30

14.2 Asimmetrie temporali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

14.3 Ottimizzazione dei feedback taps . . . . . . . . . . . . . . . . . . . . . . . . 30

14.4 Recupero del caos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

15Introduzione agli Error Correcting Codes 31

15.1 Concetto generale di Error Correcting Code . . . . . . . . . . . . . . . . . 31

15.2 Ridondanza informativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

15.3 Componenti hardware di un sistema ECC . . . . . . . . . . . . . . . . . . 32

15.3.1 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

15.3.2 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

15.3.3 Corrector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

15.4 Ambiti di utilizzo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

16Codici sistematici e non sistematici 33

16.1 Differenza generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

16.2 Codici sistematici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

16.3 Codici non sistematici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

16.4 Decodifica nei codici sistematici . . . . . . . . . . . . . . . . . . . . . . . . . 34

16.4.1 Syndrome Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

16.4.2 Syndrome Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

16.4.3 Corrector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4

16.5 Decodifica nei codici non sistematici . . . . . . . . . . . . . . . . . . . . . . 35

17Linear Parity Check Codes 35

17.1 Funzione di codifica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

17.2 Linearità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

17.3 Iniettività . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

17.4 Matrice generatrice G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

17.5 Condizione sulla matrice G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

18Codici LPC sistematici 37

18.1 Struttura della codeword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

18.2 Matrice generatrice sistematica . . . . . . . . . . . . . . . . . . . . . . . . . 37

18.3 Ruolo della matrice P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

19Distanza di Hamming e peso 38

19.1 Distanza di Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

19.2 Peso di una parola binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

19.3 Distanza minima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

19.4 Rilevazione e correzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

20Codici di Hamming SEC 39

20.1 Significato di SEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

20.2 Relazione tra data bits e check bits . . . . . . . . . . . . . . . . . . . . . . 39

20.3 Caso k = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

21Esempio completo: Hamming SEC (7,4) 40

21.1 Struttura del codice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

21.2 Calcolo dei check bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

21.3 Matrice P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

21.4 Matrice generatrice G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

21.5 Esempio di codifica con d = 1010 . . . . . . . . . . . . . . . . . . . . . . . 42

21.6 Calcolo tramite I e P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

22Parity Check Matrix 43

22.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

22.2 Relazione tra H e P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

22.3 Matrice H del codice (7,4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

22.4 Equazioni di controllo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

23Rappresentazione degli errori 44

23.1 Parola corretta e parola ricevuta . . . . . . . . . . . . . . . . . . . . . . . . 44

23.2 Error vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

23.3 Esempio di errore su d4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5

24Sindrome di errore 46

24.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

24.2 Interpretazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

24.3 La sindrome dipende solo dall’errore . . . . . . . . . . . . . . . . . . . . . . 46

24.4 Esempio con errore su d4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

25Implementazione hardware del codice Hamming (7,4) 47

25.1 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

25.2 Syndrome generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

25.3 Syndrome decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

25.4 Ottimizzazione sui check bits . . . . . . . . . . . . . . . . . . . . . . . . . . 49

25.5 Corrector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

25.6 Decoder-corrector completo . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

25.7 Circuito completo di codifica e decodifica . . . . . . . . . . . . . . . . . . 50

26Costruzione della PCM per codici Hamming SEC 50

26.1 Regola generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

26.2 Caso sistematico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

26.3 Esempio Hamming (12,8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

27Miscorrection nei codici SEC 51

27.1 Limite dei codici SEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

27.2 Esempio di miscorrection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

27.3 Necessità di aumentare dmin . . . . . . . . . . . . . . . . . . . . . . . . . . 52

28Codici SEC/DED 52

28.1 Significato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

28.2 Hamming SEC/DED (8,4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

28.3 Nuova matrice H e sindrome . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

28.4 Errore singolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

28.5 Errore doppio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

28.6 Regola operativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

28.7 Limite del SEC/DED classico . . . . . . . . . . . . . . . . . . . . . . . . . . 54

29Codice Hsiao SEC/DED 54

29.1 Obiettivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

29.2 Colonne a peso dispari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

29.3 Errore singolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

29.4 Errore doppio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

29.5 Riduzione del ritardo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

29.6 Matrice H del codice Hsiao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

29.7 Circuito Hsiao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6

1 Random Number Generators

1.1 Introduzione generale

I Random Number Generators, abbreviati in RNG, sono sistemi hardware o software

progettati per produrre sequenze di numeri che devono apparire casuali. Nel contesto della

Hardware & Embedded Security, la generazione di numeri casuali è fondamentale perché

molti meccanismi crittografici dipendono direttamente dalla qualità della casualità utilizzata.

Un numero casuale debole, prevedibile o statisticamente sbilanciato può compromettere l’intero

sistema. Anche se l’algoritmo crittografico è sicuro, una cattiva generazione di chiavi, vettori di

inizializzazione o parametri segreti può renderlo vulnerabile.

Nei sistemi embedded e nei circuiti digitali, generare vera casualità è complesso perché l’hardware

digitale è progettato per essere stabile, deterministico e prevedibile. Per ottenere casualità

bisogna quindi sfruttare fenomeni fisici inevitabili, come rumore, jitter, metastabilità e variazioni

ambientali.

1.2 Numeri casuali nella crittografia

1.2.1 Ruolo dei numeri casuali nei sistemi crittografici

I numeri casuali vengono utilizzati in molti punti critici della crittografia, ad esempio:

• nel keystream del one-time pad;

• nella secret key dell’algoritmo DES;

• nella scelta dei numeri primi e in RSA;

p q

• nelle session keys;

• nella private key del Digital Signature Algorithm, o DSA;

• negli Initialization Vectors, abbreviati in IVs, usati nei cifrari.

In tutti questi casi, la sicurezza dipende dal fatto che i valori generati siano difficili da prevedere.

Se un attaccante riesce a prevedere il keystream di un one-time pad, può recuperare il messaggio.

Se riesce a prevedere i numeri primi usati in RSA, può compromettere la chiave privata. Se riesce

a prevedere una session key, può decifrare comunicazioni protette.

La casualità è quindi legata direttamente a segretezza, imprevedibilità e robustezza crit-

tografica. 7

1.2.2 Requisiti fondamentali di un buon generatore casuale

Un generatore di numeri casuali usato in crittografia deve rispettare due requisiti principali.

Buone proprietà statistiche La sequenza prodotta deve avere una distribuzione il più

possibile uniforme. Ogni possibile valore deve avere la stessa probabilità di comparire.

Se una sequenza è sbilanciata, certi valori compaiono più spesso di altri e un attaccante può

sfruttare questa informazione per ridurre lo spazio di ricerca. Per esempio, se un bit vale 1

molto più spesso di la sequenza non è veramente uniforme e può essere vulnerabile ad attacchi

0,

statistici.

Una buona distribuzione non garantisce da sola la sicurezza, ma è una condizione necessaria.

Imprevedibilità La sequenza deve essere imprevedibile. Un attaccante non deve poter cal-

colare valori futuri o precedenti osservando una parte della sequenza già generata.

Questo requisito è essenziale quando i numeri casuali vengono usati per chiavi segrete, parametri

privati o nonce. Una sequenza può sembrare casuale dal punto di vista statistico, ma essere

prevedibile se ge