S Ecurit E Des Chiffres Sym Etriques En Bloc
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationSécurité des chiffres symétriques en blocBruno MARTIN,Université de Nice - Sophia AntipolisBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc1
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationRappels de probabilitésBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc2
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationProbabilitésEnsemble fondamental : S ensemble fini dont les élémentssont des événements élémentaires assimilables à la réalisationd’une expérienceEvénement : sous-ensemble de S ; est l’événement vide etS l’événement certainDeux événements sont en exclusion mutuelle ssi leurintersection est videBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc3
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationDistribution de probabilités, V.A.X S [0, 1] fonction distribution de probabilités si :1 événement A X , Pr (A) 02si A B , Pr (A B) Pr (A) Pr (B)3Pr(S) 1X : S R une V.A. discrète si l’événement x X est l’ensemble{s S : X (s) x} ; la proba associée est :XPr (X x) Pr (s)s S:X (s) xExempleUne paire de D6, V.A. maximum des valeurs. Pr (X 3) Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc5364
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationProbabilité conditionnelle et indépendancePr (A B) Pr (A B)PR(B)A, B 2 événements indép. ssi Pr (A B) Pr (A).Pr (B) ;si Pr (B) 6 0, A, B indép. Pr (A B) Pr (A)Formule de Bayes :Pr(A B) Pr (B A) Pr (B)Pr (A B) Pr (A)Pr (B A)et si Pr (B) 6 0, on aPr (A B) Bruno MARTIN, Université de Nice - Sophia AntipolisPr (A)Pr (B A)Pr (B)Sécurité des chiffres symétriques en bloc5
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationCryptanalyse différentielleBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc6
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationP1 . P16clairmélange avec la clé de tourS11S12S13S14tour 1mélange avec la clé de tourS21S22S23S24tour 2mélange avec la clé de tourS31S32S33S34tour 3mélange avec la clé de tourtour 4S41S42S43S44mélange avec la clé de tourC1 .cryptoBruno MARTIN, Université de Nice - Sophia Antipolis. C16Sécurité des chiffres symétriques en bloc7
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationPrésentation du chiffre utiliséRéseau de substitution/permutation simplifié. Entrée : 16 bits :fonctionnement en 4 tours. Chaque tour consiste enun mélange avec la clé : xor entre la clé de tour et le blocd’entrée du tour. Opération répétée à l’issue du dernier tour.une substitution. 16 bits scindés en 4 sous-blocs qui entrent dans4 boı̂tes-S identiques à 4 4. (MSB à gauche)in0out E142D31425F6B7 88 39 A BA 6 CC5D9E0F7une transposition définie par la i e sortie de la j e boı̂te-S est reliéeà la j e entrée de la i e boı̂te-SDéchiffrement obtenu en faisant «remonter» le cryptogramme.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc8
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes 0011111100100110100010010111110111000e4d12fb8Bruno MARTIN, Université de Nice - Sophia � des chiffres symétriques en bloc9
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationBref historiqueInventée à la fin des années 1980 par Biham et Shamir [1] avecdes applications -peu fructueuses- à la cryptanalyse de DES.DES conçu pour résister à la cryptanalyse différentielle ?chiffres de la même époque vulnérables, p.e. FEAL.Présentation de la cryptanalyse différentielle de [2].Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc10
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationPrincipe de l’attaqueExploite proba d’apparition d’occurrences de différences entre desclairs et d’occurrences de différences entre des chiffrés en entrée dudernier tour du chiffre.Entrées X [X1 . . . Xn ] sorties Y [Y1 . . . Yn ] ; on étudie X X 0 X 00 (2 entrées) et Y Y 0 Y 00 (2 sorties).Chiffre idéal : Pr( Y X ) doit valoir 1/2n .Cryptanalyse exploite les apparitions d’un Y particulier pour un certain X avec forte proba pD . ( X , Y ) différentiel.Attaque à clair choisi. Choisir des paires d’entrées X 0 , X 00 X tqle X considéré mène avec une forte proba à un Y particulier.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc11
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationPrincipe de l’attaqueTrouver les ( X , Y ) les plus probablesexaminer les propriétés des boı̂tes-S et construire lescaractéristiques différentiellesconsidérer les X et Y des boı̂tes-S pour trouver les plusfréquentescombiner l’information sur les boı̂tes-S pour construire uneapproximation globaleBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc12
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationAnalyse d’une boı̂te-S -1-On examine tous les ( X , Y ) et on cherche la probad’apparition de Y étant donné X . Revient à énumérer 16valeurs pour X 0 , X 00 étant fixé pour la valeur de X recherchée.Exempleon cherche les valeurs de Y pour chaque paire (X 0 , X 0 X )pour les valeurs X 1011, 1000, 0100 (resp en hexa B, 8 et 4).Celles qui apparaı̂ssent avec le plus d’écart sont Y 0010 pour X 1011 (8/16), Y 1011 pour X 1000 (4/16) et Y 1011 pour X 0100 (4/16).Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc13
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes 111 Y X 1011 X 1000 X o MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc14
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationAnalyse d’une boı̂te-S 2Boı̂te-S parfaite, toutes ces proba 1/16.Construire table des différentiels qui résume les possibilités.Chaque case représente le nombre d’occurrences de Y étantdonnée X . Valeur max pour X B et Y 2.Autrement dit, la proba pour que Y 2 pour une paire d’entréesdont la différence vaut X B est de 1/2. Le minimum est 0atteint pour un grand nombre de paires.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc15
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationTable des différentiels Y 2650060024000022000Bruno MARTIN, Université de Nice - Sophia urité des chiffres symétriques en blocE0020002020400222F000402242002000016
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationPropriétésLa somme de tous les éléments par ligne ou colonne vaut 2n 16.Tous les éléments sont pairs (la différence est symétrique).Si X 0, il doit en être de même pour Y .Si la boı̂te-S était parfaite, tous les éléments du tableau devraientêtre égaux à 1, ce qui n’est pas possible.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc17
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationInfluence de la clé sur un différentielW1 W2 W3 W4K1 K2 K3K4X1 X2 X3 X44x4 boîte-SY1 Y2 Y3 Y4X entrée boı̂te-S (on oublie l’influence de la clé) et Y sortie.Si on prend en compte l’influence de la clé à l’entrée, Il fautconsidérer W comme étant l’entrée de la boı̂te-S de clé K .Pour un différentiel Wi Wi0 Wi00 on aWi0 Wi00 (Xi0 Ki ) (Xi00 Ki ) Xi0 XI00 X carKi Ki 0.Les bits de la clé n’ont pas d’influence sur les différentiels.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc18
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationConstruire la caractéristique différentielle du chiffreUne fois obtenue la table des différentiels des boı̂tes-S, il fautconstruire la caractéristique différentielle du chiffre parconcaténation des paires de différences adéquates entre lesboı̂tes-S.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc19
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationExempleOn utilise les paires de différences suivantes :S12S23S32S33: X: X: X: X B Y 2 4 Y 6 2 Y 5 2 Y 5probaprobaprobaproba8/166/166/166/16La différence sur l’entrée du chiffre est P [0000 1011 0000 0000] et, à l’entrée du dernier tour, U4 [0000 0110 0000 0110] avec comme proba (6/16)2 étantdonné U3 qui a comme proba 6/16 étant donné U2 de proba8/16 étant donné P. Sachant qu’on a entré P, la proba d’avoir U4 [0000 0110 0000 0110](1)est le produit des probas précédentes :(6/16)2 (6/16)(8/16) 27/1024. (On suppose l’indépendance).Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc20
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisation!P [0000 1011 0000 0000]S11S12S13S14tour 1!Y [0010]!X [0100]S21S22S23S24tour 2!Y [0110]!X [0010]S31!X [0010]S32S33!Y [0101]!U4,5.!U4,8S41tour 3!U4,13.!U4,16S42K5,5S34!Y [0101].S43K5,8Bruno MARTIN, Université de Nice - Sophia Antipolistour 4S44K5,13.K5,16Sécurité des chiffres symétriques en bloc21
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationRetrouver des bits de la cléAvec la caractéristique différentielle de R 1 tours d’un chiffre à R tourset une proba suffisante, on tente de retrouver des bits de la dernière cléde tour (ici K5 ). Ils sont déterminés par les 2 dernières boı̂tes-S dudernier tour et les bits obtenus par la caractéristique différentielle.Il faut effectuer une cryptanalyse exhaustive partielle du dernier tour :pour toutes les valeurs possibles des bits cherchés de la dernière clé detour, on xor avec les bits correspondants du chiffré et on les fait passer àl’envers dans les deux boı̂tes-S concernées pour obtenir les entrées desboı̂tes-S au dernier tour.On effectue cette opération pour un grand nombre de couplesclairs/cryptos et on compte le nombre de fois où la caractéristiquedifférentielle est vérifiée.La clé qui satisfait l’expression le plus souvent est la plus vraissemblable.Les autres bits de la clé sont déterminés par une recherche exhaustive.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc21
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationRécupération des clésBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc22
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationSur l’exempleLa caractéristique différentielle affecte les entrées de S42 et S44 .Pour tous les couples clair/crypto, on cherche les 256 valeurspossibles des bits de K5 concernés : [K5,5 . . . K5,8 , K5,13 . . . K5,16 ].Pour chaque valeur, on compte le nombre de fois où (1) estsatisfaite en calculant les valeur de[ U4,5 . . . U4,8 , U4,13 . . . U4,16 ].On compte, pour chaque clé, le nombre de fois où (1) est satisfaiteet on choisit la clé qui a maximisé cette valeur.Expérimentation : avec 5000 couples, en appliquant la technique,la clé la plus vraissemblable est (en hexadécimal) 24.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc23
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationComplexité de l’attaqueMesure la quantité de données requise pour réussir cette attaque :ND clairs.Il est généralement compliqué de déterminer le nombre de clairschoisis nécessaires. Cependant, expérimentalement, on évalueND c/pDoù pD est la probabilité de la caractéristique différentielle desR 1 tours et c une petite constante.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc24
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationCas du DESDans [1], il est dit qu’un DES limité à 6 tours peut être attaquéavec succès en 0,3 s avec 240 clairs.Le DES à 16 tours nécessite 258 étapes de calcul (ce qui estsupérieur à la recherche exhaustive).Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc25
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationEt la cryptanalyse linéaire ?Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc26
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationCryptanalyse linéaireSchéma général comparable à la cryptanalyse différentielleattaque des S-boxes en cherchant des relations linéaires ouaffines qui s’écartent d’une distribution uniforme.relation linéaire(/affine) entre un sous-ens des entrées et unsous-ens des sortiesProblème : combiner ces relations (utilisation du pilling-uplemma de Matsui [4])Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc27
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationPrincipe de la peau d’oignonOutil de base pour concaténer les approximations linéaires des boı̂tes-S.Soient X1 et X2 2 VA binaires, l’expression linéaireX1 X2 0 X1 X2 et l’expressionaffine X1 X2 1 X1 6 X2 . Pr (Xi 0) piLes distributions de proba sont :.Pr (Xi 1) 1 piLes deux VA sont supposées indépendantes et p1 p2i j 0 p1 (1 p2 )i 0, j 1Pr (X1 i, X2 j) (1 p)pi 1, j 0 1 2 (1 p1 )(1 p2 )i j 1Pr (X1 X2 0) Pr (X1 X2 ) p1 p2 (1 p1 )(1 p2 ) si pi 1/2 εi , εi représente le biais de chaque Xi et ε1,2X1 X2 0.Bruno MARTIN, Université de Nice - Sophia Antipolis11 2ε1 ε2 ε1,222le biais deSécurité des chiffres symétriques en bloc28
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationGénéralisation à plusieurs VALa propriété précédente se généralise à plusieurs variables.LemmeSoient X1 , . . . , Xn n VA binaires indépendantes. 1Q 2n 1 ni 1 εi2Pr (X1 . . . Xn 0) 12 ε1,2,.,nObservons que si pi 0 (resp. 1) pour tout i, alorsPr (X1 . . . Xn 0) (resp. 1) et si un seul des pi 1/2,Pr (X1 . . . Xn 0) 1/2.Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc29
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationApplication au DESPlus efficace que la cryptanalyse différentielle : au départ, onavait besoin de 247 couples (P, C ), améliorations successivesjusqu’à 243 .DES pas robuste à une cryptanalyse linéairePour en savoir plus sur la cryptanalyse linéaire, voir [4], [2] ou[5], [3].Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc30
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisation(S)-AESBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc31
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationPclair (16 bits)AK0Add round keyNSNibble substitutionSRShift RowMCMix columnsAK1Add round keyNSNibble substitutionSRShift RowAK2CAdd round keyclé (16 bits)w[0,1]Expand keyw[2,3]w[4,5]chiffré (16 bits)Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc32
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationState matrix & nibbles1 nibble mot de 4 bits (E/S des composants de SAES)b0 b1 b2 b3 b8 b9 b10 b11SS0,1 0,0b4 b5 b6 b7 b12 b13 b15 b15S1,0 S1,1représentation de la clé :k0 k1 . . . k7 k8 . . . k15 {z } {z }w [0]w [1]Bruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc33
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationOpérations dans GF (16) ' F2 /x 4 x 1m(x) x 4 x 1 est un irréductible de F2θéléments : nibble b0 b1 b2 b3 b0 x 3 b1 x 2 b2 x b3addition : par addition des coefficients : (x 3 x 1) (x 2 1)multiplication : produit des polynômesmod m(x)codage octet : dans extension quadratiqueGF (16) ' F2 [z]/z 2 1attention ! z 2 1 non inversible dans GF (16)Rappel : trouver l’inverse d’un élément : Euclide étendu surpolynômes (x 1, m) (x 3 x 2 x)(x 1) 1 · mBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc34
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationInverses dans 0101xx 1x2x2 1x2 xx2 x 1x3x3 1x3 xBruno MARTIN, Université de Nice - Sophia Antipolis1x3 1x3 x2 xx3 x2 1x3 x 1x2 x 1x2 xx3 x2 x 1xx3 2cSécurité des chiffres symétriques en bloc35
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationBoı̂te S utilisée dans Nibble substitutioni 00011011009d6c01412e10a80f111001 0100b1101 00015 0110 001031100 11107b0 b1 b2 b3 nibble : {z} {z}:ligne colonne001010100000001111S01 011011010100110111000001 0001 S 0100 01004 4 1100 11101100 1111c fBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc36
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationRetrouver la boı̂te S algébriquement1initialiser la boı̂te S avec les nibbles rangés en tableau 1Dligne à ligne2convertir chaque nibble en polynôme3inverser chaque nibbble dans F164associer à l’inverse son polynôme dans F2 [y ]/y 4 1 N(y )5calculer a(y )N(y ) b(y ) mod y 4 1 avec a y 3 y 1 etb y3 1Normalement S(0011) 1011 S(3) bBruno MARTIN, Université de Nice - Sophia AntipolisSécurité des chiffres symétriques en bloc37
Rappels sur les probabilitésCryptanalyse différentielle(S)-AESModes d’utilisationAutres transformationsShift row : transposition bits nibble : b0 b1 b2 b3 7 b2 b3 b0 b1 .4 44 47 c ff cMix columns : modification de la représ. pol. des colonnes deN .; on associe c(z) Ni z Nj F2 [z]/z 2 1 ;l’état iNj .calculer c(z).(x 2 z 1) mod z 2 1.ExemplePour 4f 0100 1111 7 c(z) x 2 z x 3 x 2 x 1 :(x 3 x 2 1)z (x 3 x 2 ) Nk z N 1101 1100 carz 2 1, x 4 x 1 et x
Rappels sur les probabilit es Cryptanalyse diff erentielle (S)-AES Modes d’utilisation Analyse d’une boˆıte-S -1-On examine tous les ( X, Y) et on cherche la proba d’apparition de Y etant donn e X. Revient a enum erer 16 valeurs pour X0, X00 etant fix e pour la valeur de X recherch ee. Exemple
Comment Adapter une Politique de S ecurit e pour les Entit es du CNRS. Politique de S ecurit e . – Approche générale de la gestion de la sécurité des SI – Guide de choix des mesures préventives – Recommandations sur la sécurité des réseaux. . – La classification des informations pour ne protéger
Tai Chi, short for T'ai Chi Ch'uan, is a Chinese martial art, which has been created to increase wisdom and bravery. The term Tai Chi encompasses . The physical techniques of Tai Chi are described in the Tai Chi classics "The Essence of T'ai Chi Ch'uan", a set of writings by traditional masters.
CHI, CHIE 2, 4 CH, CHN, CHI, CHIU, CHIE 68 7 Service Kit Catalogue 2021 50/60 Hz, CHI Models B and C, CHIE model A CHI, CHIE 2, 4 50/60 Hz, CHI Models B and C, CHIE model A Bearing Shaft seal Pos. Description/kit No 96960884 153 Ball bear
CHI, CHIE 2, 4 CH, CHN, CHI, CHIU, CHIE 50/60 Hz, CHI Models B and C, CHIE model A CHI, CHIE 2, 4 50/60 Hz, CHI Models B and C, CHIE model A Bearing Shaft seal Pos. Description/kit No 96960884 153 Ball bearing 1 154 Ball bearing 1 157b O-ring 1 Pos. Pump type All models Kit
trien9 khai thirc hien cac noi dung danh gia cua Chi sor PAPI, trong do phan cong cu the trach nhiem cua co quan, don vi chu tri thuc hien timg tieu chi, tieu chi thanh phan cua Chi so PAPI. Voi vai tro la co quan thuong true giup UBND tinh trien khai cac nhiem vu lien quan denr Chi sor PAPI
Crosstab & Chi-Square Test in SPSS The chi-square test for independence, also called Pearson's chi-square test or the chi-square test of association, is used to discover if there is a relationship between two categorical variables. Assumptions When we choose to analyze our data using a chi-square test for independence, we need to make
70136_BI.indd 26 03/09/2013 6:43 PM. 1. Tribe 2. . CHI Bonus: When you flip a card, you may pay 1 CHI crystal to add the CHI bonus to any connected battle power. 1. Stam 2. Krachten: Instinct Snelheid Moed Spierkracht 3. CHI bonus: Als je een kaart omdraait, mag je 1 CHI kristal betalen om de CHI bonus toe te voegen aan een daarmee verbonden .
The origins of Tai Chi philosophy 27 Tai chi chuan—the origins in a nutshell 29 Chang Sanfeng 29 Chen Wangting 30 Tai chi chuan Classics 31 The role of tai chi chuan in Anan-Do method 31 So, you are a beginner? 33 Why would you want to learn tai chi chuan, anyway? 34 How it works 35 Soft or tense 35
