Slide 1

Développement d’une Développement d’une architecture de test architecture de test

dédiée aux puces dédiée aux puces cryptographiquescryptographiques

Présenté parPrésenté par

Amine MiledAmine Miled

Mohamed RouatbiMohamed Rouatbi

Projet du coursProjet du coursTests des systèmes électroniquesTests des systèmes électroniques

Projet du coursProjet du coursTests des systèmes électroniquesTests des systèmes électroniques

Mardi,12Mardi,12 Novembre Novembre

20062006

Mardi,12Mardi,12 Novembre Novembre

20062006

Slide 2

IntroductionIntroduction

But du projetBut du projet

Présentation de l’algorithme Présentation de l’algorithme

FROGBITFROGBIT

Objectif du projetObjectif du projet

Solution proposéeSolution proposée

Plan Plan

Slide 3

Introduction: Introduction: Cryptographie principes générauxCryptographie principes généraux

Importance de la cryptographieImportance de la cryptographie– Échanges des données Échanges des données

confidentielles et sensiblesconfidentielles et sensibles Rôle du système cryptographique[3]Rôle du système cryptographique[3]

– ConfidentialitéConfidentialité– IntégritéIntégrité– AuthentificationAuthentification– Non répudiationNon répudiation

Types de chiffrement Types de chiffrement – Symétrique Kc=KdSymétrique Kc=Kd– Non symétrique Kc /= KdNon symétrique Kc /= Kd– Par bloc Par bloc – Par flux « Par flux « streamstream » »

• Chiffrement d’un flux de données bit Chiffrement d’un flux de données bit par bitpar bit

• Utilisation d’un flux de clefsUtilisation d’un flux de clefs• ChaînageChaînage

+

Reg

E(Mi,Ki)Mi Ci

+

Reg

D(Ci,Ki)

MiCi

Slide 4

IntroductionIntroduction Besoin d’une puce cryptographiqueBesoin d’une puce cryptographique

– Augmentation exponentielle du volume Augmentation exponentielle du volume des donnéesdes données

– Accélération de la vitesse de transfertAccélération de la vitesse de transfert• Ligne 1 GigBitLigne 1 GigBit• Fibre optiqueFibre optique

– Minimisation de la taille tout en augmentant la vitesseMinimisation de la taille tout en augmentant la vitesse• Pour certains algorithmes Pour certains algorithmes • Taille < Taille ( cpu + mémoire) Taille < Taille ( cpu + mémoire) • Plus rapide: parallélismePlus rapide: parallélisme

Importance de la fiabilité de la puceImportance de la fiabilité de la puce– Nécessité d’une architecture de test intégré et mutuelNécessité d’une architecture de test intégré et mutuel– Vérification de la connectivité Vérification de la connectivité

AC: 3265

NIP: saveMyCash

OP: add 20$

@Q$%@#SDF

FGF$%W!@#

$%FFG%?FG

AC: 3265

NIP: saveMyCash

OP: add 20$

E(M,K) D(C,K)

Slide 5

But du projetBut du projet

Développement d’un système de:Développement d’un système de:– Vérification du bon fonctionnement des puces cryptographiquesVérification du bon fonctionnement des puces cryptographiques– Vérification de l’intégrité du lienVérification de l’intégrité du lien– Synchronisation des états initiaux (très important)Synchronisation des états initiaux (très important)– Vérification de l’intégrité des données transmisesVérification de l’intégrité des données transmises

Initialisation

Intégrité des données

Slide 6

2.FROGBIT : aperçue2.FROGBIT : aperçue

http://www.miseagrant.umich.edu/photos/ais/frogbit.html

Slide 7

FROGBITFROGBIT

C’est un algorithme de C’est un algorithme de chiffrement de flux chiffrement de flux symétriquesymétrique

Principales fonctionnalitésPrincipales fonctionnalités– Intégrité des donnéesIntégrité des données

• Un changement d’un seul bit Un changement d’un seul bit transmis => Changement de transmis => Changement de tout le reste du messagetout le reste du message

– Confidentialité Confidentialité • Permet le chiffrage en Permet le chiffrage en

utilisant deux flux de clef utilisant deux flux de clef Ki1 , Ki2Ki1 , Ki2

Il combine deux techniques Il combine deux techniques de cryptographie classiquesde cryptographie classiques– Permutation Permutation – SubstitutionSubstitution

Slide 8

FROGBIT ArchitectureFROGBIT Architecture

L’implémentation Hardware de FROBIT est composé de 4 entitésL’implémentation Hardware de FROBIT est composé de 4 entités– RLE_Ecrypt «RLE_Ecrypt «Run Length Encoding »Run Length Encoding »

• Cryptage des donnéesCryptage des données• Génération d’une chaîne de dépendance interne SiGénération d’une chaîne de dépendance interne Si• Calcule de la redondance dans SiCalcule de la redondance dans Si

– Nombre de répétition de la même valeur 1 ou 0 Nombre de répétition de la même valeur 1 ou 0 » Inspiré du domaine de compression de donnéeInspiré du domaine de compression de donnée

– DrawDraw• Construit un chiffre pseudo aléatoire entre 0-9 à partir deConstruit un chiffre pseudo aléatoire entre 0-9 à partir de

– K1i, k2i, Si K1i, k2i, Si

– Algo_SELECTAlgo_SELECT• Permet de générer sous certaines conditions un nombre aléatoirePermet de générer sous certaines conditions un nombre aléatoire

entre 0 - 9entre 0 - 9– Contient 40 registres pour sauver les indexes de permutations Contient 40 registres pour sauver les indexes de permutations

– Key_generatorKey_generator• Contient 10 LFSRs qui servent à la génération des chaînes de clefs Contient 10 LFSRs qui servent à la génération des chaînes de clefs

Ki1, Ki2.Ki1, Ki2.

Slide 9

FROGBIT digramme FROGBIT digramme globalglobal

Slide 10

FROGBIT initialisation et FROGBIT initialisation et testtest Lacune de la version précédente de FROGBIT:Lacune de la version précédente de FROGBIT:

– Pas de mécanisme d’initialisation des registres internes Pas de mécanisme d’initialisation des registres internes – Après le reset l’état initial est sauvegardé physiquementAprès le reset l’état initial est sauvegardé physiquement

• L’ajout de tel mécanisme permettrait :L’ajout de tel mécanisme permettrait :– Augmentation de l’espace des clefs Augmentation de l’espace des clefs

» Les états initiaux font partir de la clé Les états initiaux font partir de la clé

– Pas de méthode de self testPas de méthode de self test– Pas de test sur le bon fonctionnement de la puce distante.Pas de test sur le bon fonctionnement de la puce distante.

• Permet d’annuler la transaction dés le débutPermet d’annuler la transaction dés le début

– Pas de méthode de test d’intégrité du lienPas de méthode de test d’intégrité du lien• Vérification de l’intégrité physique du lien Vérification de l’intégrité physique du lien • Vérification de l’existence d’un agent tierce qui altère les donnéesVérification de l’existence d’un agent tierce qui altère les données

– Pas de mécanisme de vérification de signatures pour assurer Pas de mécanisme de vérification de signatures pour assurer l’intégrité des données après le transfertl’intégrité des données après le transfert

Slide 11

Conflit Testabilité Conflit Testabilité confidentialitéconfidentialité

NIST: National Institute of Standards and TechnologyNIST: National Institute of Standards and Technology FIPS : Federal Information Processing Standards FIPS : Federal Information Processing Standards Les exigences de sécurité :Les exigences de sécurité :

– FIPS 140-2: security requirement for cryptographic Modules [4]FIPS 140-2: security requirement for cryptographic Modules [4]– Aucun accès est possible :Aucun accès est possible :

• Au flux partiellement cryptéAu flux partiellement crypté• A La clef cryptographique A La clef cryptographique

– Une faute doit être rapidement détectée Une faute doit être rapidement détectée DFT : Contrôlabilité, DFT : Contrôlabilité, ObservabilitéObservabilité !! !! JTAG, Chaine de scan == possibilité de dévoiler [1]JTAG, Chaine de scan == possibilité de dévoiler [1]

– Les clefs en utilisant Scan Based Side Channel AttackLes clefs en utilisant Scan Based Side Channel Attack– Même si les clefs sont dans des registres non scannablesMême si les clefs sont dans des registres non scannables

BIST très approprié [2]BIST très approprié [2]– Permet la génération des vecteurs et l’analyse des résultat de l’intérieur du Permet la génération des vecteurs et l’analyse des résultat de l’intérieur du

module cryptographique.module cryptographique.

Slide 12

BIST Modes OpérationnelBIST Modes Opérationnel Mode Offline :Mode Offline :

– Génération pseudo-aléatoirement: clef + donné Génération pseudo-aléatoirement: clef + donné – Commence toujours par une Commence toujours par une mise à zéromise à zéro de tous les registres de tous les registres

• Sinon Possibilité d’analyser des valeurs dans les registres depuis la Sinon Possibilité d’analyser des valeurs dans les registres depuis la dernière mise en marche.dernière mise en marche.

LFSR à longueur ajustableLFSR à longueur ajustable– Test des petites modules requière moins de vecteurs que les grand Test des petites modules requière moins de vecteurs que les grand

modules.modules.– Solution utilisation d’un grand LFSR primitive avec des point de Solution utilisation d’un grand LFSR primitive avec des point de

rupture.rupture. Exécution de l’algorithme Exécution de l’algorithme Comparaison des résultatsComparaison des résultats

– Comparaison de signature grâce à un LFSR à la sortieComparaison de signature grâce à un LFSR à la sortie Surface additionnelle 19.5 %Surface additionnelle 19.5 %

Slide 13

Test OffLineTest OffLine

FrogbitLFSR_K_M LFSR_sign

Dem

ux

Mi

SiCi

Sel

Gen_Mi

Gen_Ki

Signature

Slide 14

LFSR ReconfigurableLFSR Reconfigurable

C1

Cut_x

Cn

Slide 15

Module Key_generatorModule Key_generator

LFSR

1LF

SR

2LF

SR

10

Test_mode SI

D_prime (3:0)

Stream_id (1:0)

Algo_select Sorties

SI

Reg_low

Test_mode

Initialisation des LFSR

Test_mode = 0 => LFSR mode scan

Test_mode = 1 => LFSR mode normal

Key_generator

So

Slide 16

Problèmes de testabilitéProblèmes de testabilité

LFSR1

LFSR2

LFSR3

LFSR10

LFSR9

Key_generator

Si

So_to_cntr

- Test integrite de registres 001100110011

Slide 17

Test de tous les Test de tous les générateursgénérateurs

LFSR1

LFSR2

LFSR3

LFSR10

LFSR9

Key_generator

Di_prime

4

Di_prime

4

VDD

enable

K1i

K2i

Slide 18

BIST BIST OpérationnelOpérationnel

Mode Online/Concurrentiel:Mode Online/Concurrentiel:– Détection des défauts pendant le Détection des défauts pendant le

fonctionnement normal.fonctionnement normal.– Redondance : multiplication de certain modulesRedondance : multiplication de certain modules– Vérification concurrente et validation des sorties Vérification concurrente et validation des sorties

de chaque module par le contrôleur du BISTde chaque module par le contrôleur du BIST• Dépassement des valeurs limitesDépassement des valeurs limites

• Incohérence lié à l’algorithme Incohérence lié à l’algorithme

– Coût 86 % plus de surfaceCoût 86 % plus de surface

Slide 19

Système de vérification du bon fonctionnement de la puce et de la connectivitéSystème de vérification du bon fonctionnement de la puce et de la connectivité

Principe d’interopérabilité

•Développement d’un système d’initialisation de tous les registres et des LFSR

Puce 1Puce 1

Puce 2Puce 2

Signature 1Signature 1

Signature 2Signature 2

ClefClef

ComparateurComparateur

Slide 20

Solution proposéeSolution proposée

Vérification des signatures Vérification des signatures

BILBO (Mode LFSR/MISR)BILBO (Mode LFSR/MISR)

** Connectivité ?** Connectivité ?

** Fonctionnement des puces ?** Fonctionnement des puces ? •Vérification de l’intégrité des données.

•Initialisation à travers le LFSR et le BILBO (mode Scan)

LFSRLFSR Module Module

11BILBOBILBO

Module Module

22BILBOBILBO

SignatuSignatu

rere

Puce Puce mode mode

récepterécepte

urur

Slide 21Connection entre Key_generator et RLE_EncryptionConnection entre Key_generator et RLE_Encryption

Test_mode Test_mode

RLE_Encryption

Key_generator

C1_1, C2_1

MIS

R_k

ey_g

enara

tor

MIS

R_R

LE_E

ncry

ptio

n

Si So

Q(5:0)

Q(9:0)

Sortie Sortie

C1_2, C2_2

Slide 22

MISRMISR

Polynome caractéristique

+

SI

C1

C2

P(X)=1+X+X7

SI

C1

C2

P(X)=1+X3+X1

0

+

MISR

2 et 3

MISR

1 et 4

Polynome caractéristique

Slide 23

Test_mode Test_mode

RLE_Encryption

Key_generator

Architecture globaleArchitecture globale

Test_modeTest_mode

Test_mode SI

C1_1, C2_1C1_2, C2_2

C1_3, C2_3C1_4, C2_4So

Q_1(5:0)

Q_2(9:0)

Q_3(9:0)

Q_4(5:0)

Algo_select

draw

Slide 24

Localisation des fautesLocalisation des fautes

Comment localiser le module fautif sans divulgué Comment localiser le module fautif sans divulgué des donnés sensibles:des donnés sensibles:– Ajout de quatre sorties pour identifier le module fautif: Ajout de quatre sorties pour identifier le module fautif:

• 0000 : aucun module fautif 0000 : aucun module fautif

• 0001 : module 1 fautif0001 : module 1 fautif

FROGBIT

BIST_CNTR

e1

e2

e3

e4

Off_line_bist_done

Mi

Next_bit

Si

Ci

Crypt_done

So

Slide 25

Controleur

Test_mode Test_mode

RLE_Encryption

Key_generator

Architecture globale avec controleurArchitecture globale avec controleur

Test_modeTest_mode

Algo_select

draw

Test_mode SI

C1_1, C2_1C1_2, C2_2

C1_3, C2_3C1_4, C2_4So

Slide 26

RLE_Encryption

Key_generator

Algo_select

draw

Controleur

Test_mode Test_mode

Test_modeTest_mode

Test_mode SI

C1_1, C2_1C1_2, C2_2

C1_3, C2_3C1_4, C2_4So

RécapitulationRécapitulation

Slide 27

LFSRLFSRModule 1Module 1 BILBOBILBO

Module 2Module 2BILBOBILBO

SignatureSignature

Puce mode Puce mode récepteur

récepteur

Solution finaleSolution finale

Slide 28

CaractéristiquesCaractéristiques

Nombre de registres ajoutés: 34Nombre de registres ajoutés: 34

Nombre de MISR ajoutés : 4Nombre de MISR ajoutés : 4

Nombre de mux ajoutés : 5, Nombre de mux ajoutés : 5,

indépendemment de leur tailleindépendemment de leur taille

Slide 29

LacunesLacunes

Vecteurs de testes bien déterminer pour passer a travers les 10 Vecteurs de testes bien déterminer pour passer a travers les 10 LFSRsLFSRs

Un checkBoard Test pour la RAM de 3 * 256 bits.Un checkBoard Test pour la RAM de 3 * 256 bits. Un test pour la ROMUn test pour la ROM Rajout de la logique pour les valeurs limiteRajout de la logique pour les valeurs limite

– Par exemple: Di   Par exemple: Di   > 9> 9 Il y pas moins de savoir le/les vecteur(s) de teste qui détecte(nt) Il y pas moins de savoir le/les vecteur(s) de teste qui détecte(nt)

une faute quelconque dans un module quelconque une faute quelconque dans un module quelconque Pas de mécanisme pour se prémunir des attaques de type :Pas de mécanisme pour se prémunir des attaques de type :

– Analyse différentielle de consommation de puissance [11]Analyse différentielle de consommation de puissance [11]– Probing attack: surtout un niveau des LFSRsProbing attack: surtout un niveau des LFSRs

Utilisation d’une chaine de scan avec un Scrambler Utilisation d’une chaine de scan avec un Scrambler [5][5]– Crypter/Permuter les bits en sortie de la chaine de scanCrypter/Permuter les bits en sortie de la chaine de scan– Utilisation d’une fonction de hachage à sens uniqueUtilisation d’une fonction de hachage à sens unique

Slide 30

ConclusionConclusion

Notre objectif est de:Notre objectif est de:

Développer cette architecture de test non seulement de la puce mais Développer cette architecture de test non seulement de la puce mais

du système émission/réception.du système émission/réception.

Revoire les caractéristiques du circuits: Principalement la surface et la Revoire les caractéristiques du circuits: Principalement la surface et la

fréquence, et voire l’impact de l’architecture de test sur ces derniers.fréquence, et voire l’impact de l’architecture de test sur ces derniers.

Slide 31

RéférencesRéférences[1] Bo Yang, Kaijie Wu et RAmesh Karri, Scan Based Side Channel Attack on Data Encryption [1] Bo Yang, Kaijie Wu et RAmesh Karri, Scan Based Side Channel Attack on Data Encryption

Standard 2004Standard 2004

[2] R. Zimmermann, A. Curiger, H. Bonnenberg, H. Kaeslin, N. Felber et W.Fichtner, A 177 [2] R. Zimmermann, A. Curiger, H. Bonnenberg, H. Kaeslin, N. Felber et W.Fichtner, A 177 Mbit/s VLSI Implementation of the International Data Encryption Algorithm 1993Mbit/s VLSI Implementation of the International Data Encryption Algorithm 1993

[3] Wenbo Mao, Modern Cryptography Theory and Practice, Publishing Partener HP 2003[3] Wenbo Mao, Modern Cryptography Theory and Practice, Publishing Partener HP 2003

[4] U.S Department Of Commerce/ National Institute of Standards and Technology, Federal [4] U.S Department Of Commerce/ National Institute of Standards and Technology, Federal Information Processing Standards Publication 11 Janvier 1994Information Processing Standards Publication 11 Janvier 1994

[5] David Hely, Marie-Lise Flottes, F[5] David Hely, Marie-Lise Flottes, Frédéric Bacel , Bruno Rouzeyre, Nicolos Bérard et Michel rédéric Bacel , Bruno Rouzeyre, Nicolos Bérard et Michel Renovell, Scan Design and Secure Chip 2002Renovell, Scan Design and Secure Chip 2002

[6] E. Biham et A. Shamir, Differential Fault Analysis of Secret Key Cryptosystems, CRYPTO 97 [6] E. Biham et A. Shamir, Differential Fault Analysis of Secret Key Cryptosystems, CRYPTO 97 pp 156-171, 1997pp 156-171, 1997

[7] D. Boneh, R. DeMillo et R. Lipton, On the importance of checking cryptographic protocols [7] D. Boneh, R. DeMillo et R. Lipton, On the importance of checking cryptographic protocols for faultsfor faults

2001 2001

[8] D. Mueller, United states Patent 0087284 : Method of protecting a circuit arrangement for [8] D. Mueller, United states Patent 0087284 : Method of protecting a circuit arrangement for processing data 2002processing data 2002

[9] E. Hess, N. Janssen, B. Meyer et T. Schutze, Information Leakage Attacks Against Smartcard [9] E. Hess, N. Janssen, B. Meyer et T. Schutze, Information Leakage Attacks Against Smartcard

Implementations of Cryptographic Algorithms and Countermeasure: Survey” Eurosmart Implementations of Cryptographic Algorithms and Countermeasure: Survey” Eurosmart ConferenceConference

pp 55-64 2002pp 55-64 2002

[10] Michael L. Bushnell et Vishwani D. Agrawal, Essentials Of Electronics Testing For digital [10] Michael L. Bushnell et Vishwani D. Agrawal, Essentials Of Electronics Testing For digital Memory and Mixed-Signal VLSI circuits, Bishop 2000Memory and Mixed-Signal VLSI circuits, Bishop 2000

[11] P. Kocher, J. Jaffe, B. Jun , Differential Power Analysis Advances in croptology CRYPTO’99[11] P. Kocher, J. Jaffe, B. Jun , Differential Power Analysis Advances in croptology CRYPTO’99