==Phrack Inc.== Volume 0x0c, Issue 0x40, Phile #0x0a of 0x11 |=-----------------------------------------------------------------------=| |=---------------------=[ Cryptanalyse du DPA-128 ]=---------------------=| |=-----------------------------------------------------------------------=| |=-----------------------------------------------------------------------=| |=------------------=[ Par SysK ]=------------------=| |=------------------=[ ]=------------------=| |=--------------=[ Traduit par TboWan pour arsouyes.org ]=--------------=| |=-----------------------------------------------------------------------=| --[ Sommaire 1 - Introduction 2 - Quelques mots sur le chiffrement par blocs 3 - Survol de la cryptanalyse des chiffrements par blocs 4 - Description du DPA-128 de Veins 4.1 - Bugs dans l'implementation 4.2 - Faiblesses dans la conception 5 - Casser la version linéarisée 6 - Sur la non linéarité de l'addition modulo n sur GF(2) 7 - Exploiter les clefs faibles 7.1 - Jouer avec un chiffrement jouet 7.2 - Généralisation et complexité attendue 7.3 - Cardinalité de |W 8 - Casser les fonctions de hash sans clef basé sur DPA 8.1 - Introduction aux fonction de hashage 8.2 - Algorithme DPAsum() 8.3 - Faiblesses dans la conception/implémentation 8.4 - Une attaque par (2ème) préimage 9 - Conclusion --[ 1 - Introduction Pendant que la scène du cracking s'est agrandie avec la cryptologie grâce à l'évolution des schémas de protections des binaires, la scène du hack n'a majoritairement pas bougé. Ceci est grandement justifié par le fait qu'il n'y avait globalement aucun besoin réel. En fait, il est fort connu que si un hacker doit déchiffrer un fichier, alors, il va pirater la box de son propriétaire, backdoorer le système et ensuite l'utiliser pour voler la clef. Un cracker qui doit casser un schéma de protection n'aura pas la même approche : il va en général essayer de le comprendre complètement pour trouver et exploiter une faiblesse de conception et/ou d'implémentation. Bien que l'évolution de l'industrie de la sécurité de ces dernières années ait légèrement changé la situation vis à vis de la communauté du hack, de nos jours, il y a encore trop de gens qui manquent de connaissances dans cette science. Ce qui est pénible, c'est la diffusion de légendes urbaines et de hoax par quelques paranoïaques parmis eux. Par exemple, n'avez vous jamais endendu de gens clamer que les agences gouvernementales ont cassé RSA ou AES ? Une question bien plus intelligente aurait été : Que signifie "casser" ? Un bon exemple de réaction paranoïaque peut être trouvé dans l'article de M11t0n [FakeP63]. L'auteur qui est probablement compétent en hacking promeut l'utilisation "d'algorithmes cryptographiques artisanaux" au lieu des algorithmes standardisés comme 3DES. L'argument correspondant est que puisque ces "experts sécurité" manquent de compétence en programmation, alors, ils ne sont pas capables de développer des outils appropriés pour des chiffrement exotiques. Bien que je sois d'accord au moins partiellement avec eux sur les capacités de programmation, je ne peux pas être d'accord avec la thèse principale. En fait, en admettant que certain outils publics soient suffisants pour casser une protection basée sur 3DES, alors ça veut dire que des erreurs de conception et/ou d'implémentation ont été commises puisque, d'après l'état de l'art, 3DES reste non-cassé. Le cryptosystème était faible depuis le début et utiliser de la "cryptographie artisanale" ne la rendra que plus faible encore. Il est donc extrêmement important de comprendre la cryptographie et de faire confiance aux standards. Dans une édition précédente de phrack (Phrack 62), Veins exposait à la communauté hacking un bloque de chiffrement "artisanal" appellé DPA (Dynamic Polyalphabetic Algorithms) [DPA128]. Dans ce papier, nous allons analyser ce chiffrement et démontrer qu'il n'est pas sans faiblesses - au moins dans une perspective de cryptanalyse - rentrant parfaitement dans le cadre de nos propos. --[ 2 - Quelques mots sur le chiffrement par blocs Voici un petit extrait de l'exellant HAK [MenVan] : "Un chiffrement pas blocs est une fonction qui fait correspondre des blocs de n bits du texte clair vers des blocs de n bits du texte chiffré; n est appellé la taille du bloc. Il peut être vu comme un simple chiffrement par substitution avec une frande taille de caractères. La fonction est parametrée par une clef K sur k bits, prenant ses valeurs dans un sous ensemble |K (l'espace des clefs) de l'ensemble Vk de tous les vecteurs de k bits. Il est généralement admis que la clef est choisie aléatoirement. L'utilisation de blocs de texte clair et chiffré de mêmes tailles évite l'expansion de données." Assez clair n'est-ce pas ? :> Donc, quel est l'objet d'un tel cryptosystème ? Évidement puisque nous traitons de chiffrement, cette classe d'algorithme fournis la confidentialité. Sa construction les rend particulièrement adaptés pour des applications comme le chiffrement de gros volumes (fichiers ou Disques durs par exemples). Utilisés dans des modes spéciaux comme CBC (comme dans OpenSSL), ils peuvent alors aussi fournir du chiffrement de flux. Par exemple, nous utilisons AES-CBC dans les protocols WPA2, SSL et SSH. Remarque : Quand ils sont utilisés en conjonction avec d'autres méchanismes, les chiffrements par blocs fournissent aussi des services comme l'authentification ou l'intégrité (cf. partie 8 de ce papier). Un point important est la compréhension de l'utilité de la cryptologie. Pendant que la crytpographie essaye de concevoir les meilleurs algorithmes, c'est à dire sûrs et rapides, la cryptanalyse permet une évaluation de la sécurité de ces algorithmes. Au plus on prouve qu'un algorithme à des faiblesses, moins ont devrait lui faire confiance. --[ 3 - Survol de la cryptanalyse des chiffrements par blocs La cryptanalyse du chiffrement par blocs a significativement évolué dans les années 90 avec l'apparition de quelques méthodes fondamentales comme les méthodes différentielles [BiSha90] et linéaires [Matsui92]. En plus de certaines méthodes plus récentes comme l'attaque boomerang de Wagner ou la cryptanalyse par Khi-deux de Vaudenay [Vaud], elles constituent l'ensemble de ce qu'on appelle les attaques statistiques sur les chiffrements par blocs, par opposition aux attaques algébriques très récentes et toujours controversées (voir [CourtAlg] pour plus d'informations). Aujourd'hui, l'évolution de la cryptanalyse des chiffrements par blocs tend à se stabiliser elle-même. Cependant, un cryptographe a toujours complètement besoin d'acquérir une connaissance profonde de ces attaques pour pouvoir concevoir des chiffrements. En lisant le papier de Phrack, nous pensons - en fait, on peut avoir tord - que l'auteur a surtout basé sa conception sur les tests statistiques. Bien qu'ils soient évidement nécessaires, ils ne peuvent pas être suffisants. Chaque composant doit être prudement choisi. Nous avons identifié quelques faiblesses et pensons qu'il doit en rester quelques autres. --[ 4 - Description du DPA-128 de Veins DPA-128 est un chiffrement par blocs de 16 rounds fournissant un chiffrement par blocs de 128 bits en utilisant une clef de n bits. Chaque round de chiffrement est composé de 3 fonctions qui sont rbytechain(), rbitshift() et S_E(). Donc, pour chaque bloc en entrée, on applique la fonction E() 16 fois (une par round) : void E (unsigned char *key, unsigned char *block, unsigned int shift) { rbytechain (block); rbitshift (block, shift); S_E (key, block, shift); } où : - block est l'entrée de 128 bits - shift est le paramètre de 32 bits dépendant de la sous-clef du round - key est la sousclefde 128 bits du round En conséquence, la description mathématique de ce chffrement est la suivante : f: |P x |K ----> |C où : - |P est l'ensemble de tous les textes clairs - |K est l'ensemble de toutes les clefs - |C est l'ensemble de tous les textes chiffrés Pour p dans |P, k dans |K et c dans |C, nous avons c = f(p,c) avec f = E'E...E'E = E'16 et ' représentant la composition de fonctions. Nous allons maintenant décrire chaque fonction. Puisque nous aurons parfois besoin de mathématiques pour le faire, nous admettons que le lecteur est familié avec l'algèbre de base ;> rbytechain() est dércite par la fonction C suivante : void rbytechain(unsigned char *block) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] ^= block[(i + 1) % DPA_BLOCK_SIZE]; return; } où : - block est l'entrée de 128 bits - DPA_BLOCK_SIZE vaut 16 Une telle opération sur les octets est appellée un "linear mixing" et son but est de fournir la diffusion de l'information (d'après la théorie de l'information de Shannon très connue). Mathématiquement, ce n'est rien de plus qu'une application linéaire entre deux espaces de vecteurs GF(2) [NDT : Gallois Field, corps fini en français, ici, il contient 2 éléments] de dimention 128. En fait, si U et V sont des vecteurs sur GF(2) représentant respectivement l'entrée et la sortie de rbytechain(), alors, V = M.U où M est la matrice 128x128 sur GF(2) de l'application linéaire où les coefficients de la matrices sont triviaux à trouver. Regardons maintenant rbitshift(). Sa version en code C est la suivante : void rbitshift(unsigned char *block, unsigned int shift) { unsigned int i; unsigned int div; unsigned int mod; unsigned int rel; unsigned char mask; unsigned char remainder; unsigned char sblock[DPA_BLOCK_SIZE]; if (shift) { mask = 0; shift %= 128; div = shift / 8; mod = shift % 8; rel = DPA_BLOCK_SIZE - div; for (i = 0; i < mod; ++i) mask |= (1 << i); for (i = 0; i < DPA_BLOCK_SIZE; ++i) { remainder = ((block[(rel + i - 1) % DPA_BLOCK_SIZE]) & mask) << (8 - mod); sblock[i] = ((block[(rel + i) % DPA_BLOCK_SIZE]) >> mod) | remainder; } } memcpy(block, sblock, DPA_BLOCK_SIZE); } où : - block est l'entrée de 128 bits - DPA_BLOCK_SIZE vaut 16 - shift est dérivé à partir de la sous clef du round Veins le décrit dans son papier comme un décallage en fonction de la clef (en fait, ça doit être une "rotation" en fonction de la clef puisque nous voulons pouvoir déchiffrer le texte chiffré ;)). Une lecture prudente du code et quelques tests ont confirmé que ce n'était pas une erreur (au plus, un bug détaillé plus loins dans ce papier), nous pouvons donc le décrire comme une application linéaire entre deux espaces de vecteurs GF(2) de dimention 128. En fait, si V et W sont des vecteurs sur GF(2) représentant respectivement l'entrée et la sortie de rbitshift(), alors : W = M'.V où M' est la matrice 128x128 sur GF(2) de l'application linéaire où, contrairement à la fonction précédente, les coefficients de la matrices sont inconnus à une probabilité de 1/128 par round. Une telle fonction fournis aussi la diffusion de l'information. Enfin, la dernière opération S_E() est décrite par ce code C : void S_E (unsigned char *key, unsigned char *block, unsigned int s) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] = (key[i] + block[i] + s) % 256; return; } où : - block est l'entrée de 128 bits - DPA_BLOCK_SIZE vaut 16 - s est le paramètre de permutation décrite dans la fonction précédente - key est la sous clef du round L'idée principale du papier de veins est le concept de "substitution polyalphabetique", dont l'implémentation est sensée être dans la fonction S_E(). En lisant le code, il apparait que ce n'est rien de plus qu'une fonction de mélange avec la clefs sur GF(2^8). Remarque : Nous verrons plus tard l'importance de l'opération mathématique "somme" sur GF(2^8). En regardant la gestion de la clef, chaque round du chiffrement utilise une première sousclef de 128 bits et une autre de 32bits appellée "shift" dérivée de la première. Le pseudo-code suivant décrit cette opération : skey(0) = checksum128(master_key) for i = 0, nbr_round-2: skey(i+1) = checksum128(skey(i)) skey(0) = skey(15) for i = 0, nbr_round-1: shift(nbr_round-1 - i) = hash32(skey(i)) où skey(i) est la ième sousclef. Il n'est pas nécessaire d'expliciter checksum128() et hash32(), le lecteur à juste à se souvenir de ceci : qu'importe les faiblesses qu'il puisse y avoir dans ces fonctions, nous les considèrerons comme des vraies fonctions de hash à sens unique fournissant une entropie parfaite. En conclusion, le chiffrement étudié est proche d'un SPN (Substitution - Permutation Network) qui est une contruction très générique et bien connue (AES en est un exemple). --[ 4.1 - Bugs dans l'implementation Bien que veins lui-même reconnait honnètement que ce chiffrement peut être faible et "décourage fortement son utilisation" (pour le citer [DPA128]), certaines personnes pourrait néanmoins décider de l'utiliser comme primitive pour chiffrer des données personnelles et/ou sensibles comme alternative au chiffrements "déjà-cassés-par-la-NSA" [NSA2007]. Malheureusement pour ces personnes théoriques, nous avons pu identifier un bug menant à un fonctionnement potentiel incorrect du cryptosystème (avec une probabilité non-négligeable). Nous avons vu plus tôt que le squelette du code de décallage binaire était le suivant : /* bitshift.c */ void {r,l}bitshift(unsigned char *block, unsigned int shift) { [...] // SysK : local vars declaration unsigned char sblock[DPA_BLOCK_SIZE]; if (shift) { [...] // SysK : sblock initialization } memcpy(block, sblock, DPA_BLOCK_SIZE); } Clairement, si "shift" vaut 0, alors, "bloc" est remplis avec le contenu de la pile ! Évidement, dans un tel cas, le cryptosystème ne peut pas fonctionner. Puisque "shift" est un entier, un tel événement a lieu au moins à la probabilité théorique de 1/2^32 par round. Étudions maintenant la fonction de génération du décallage (c'est à dire de "shift") : /* hash32.c */ /* * Cette fonction calcule une sortie de 32 bits avec une entrée de taile * variable. Il n'est pas important d'avoir une chouette distribution et * peu de collision car elle est utilisée sur la sortie de checksum128() * (voir checksum128.c). Il y a cependant une condition, la fonction ne * doit pas considérer \0 comme terminaison de la clef. */ unsigned long hash32(unsigned char *k, unsigned int length) { unsigned long h; for (h = 0; *k && length; ++k, --length) h = 13 * h + *k; return (h); } Comme dit dans le commentaire du code C, hash32() est la fonction qui produit le décallage. Bien que l'auteur soit prudent et admette que la distribution de la sortie puisse ne pas être complètement uniforme (une probabilité pas exactement égale pour chaque valeur d'octet d'apparaître), il est évident qu'un gros biais n'est pas désirable (Cf 7.3). Cependant qu'arrive-t-il si le premier octet pointé par k est 0 ? Puisque la boucle s'arrete pour k égal à 0, alors h va être égal à 13*0 + 0 = 0. En admettant que la sous-clef soit vraiment aléatoire, un tel événement ne devrait arriver qu'avec une probablité de 1/256 (au lieu de 1/2^32). Puisque la sortie de hash32() est un entier comme dit dans le commentaire, c'est clairement un bug. On pourrait être tentés de penser que cette erreur d'implémentation mène à une faiblesse, mais un court regard au code nous dit que : struct s_dpa_sub_key { unsigned char key[DPA_KEY_SIZE]; unsigned char shift; }; typedef struct s_dpa_sub_key DPA_SUB_KEY; Donc, puisque shift est un objet de type caractère, la présence de "*k &&" dans le code ne change rien au fait que le crytposystème va échouer avec une probabilité de 1/256 par round. Puisque le bug apparait indépendament à chaque round, la probabilité d'échec est encore plus grande : p("fail") = 1 - p("ok") = 1 - Mul( p("ok in round i") ) = 1 - (255/256)^16 = 0.0607... où i est un élément de [0, (nbr_rounds - 1)] Ce n'est pas si loin de 1/16 :-) Remarque : On verra plus tard que le cas spécial où shift vaut 0 fait partie d'une classe générale de clefs faibles permettant potentiellement à un attaquant de casser le cryptosystème. La chasse aux faiblesses et aux bugs dans l'implémentation de primitives cryptographiques est le travail courant de certains reverse engineers puisque ça permet parfois de casser l'implémentation d'algorithmes qui sont considérés comme théoriquements sûrs. Bien que ces faiblesses concernent principalement des primitives asymétriques de signatures digitales ou de génération/négociation de clefs, elles peuvent être appliquées dans certains cas spécifiques au monde du chiffrement par blocs. À partir de maintenant, nous considèreront ce bug ennuyeux dans bitshift() comme étant corrigé. --[ 4.2 - Faiblesses dans la conception Quand il concoit un chiffrement par blocs, un cryptographe doit être très prudent sur tous les détails de l'algorithme. Dans la section suivante, nous décrivons quelques erreurs de conception et expliquons pourquoi dans certains cas, elles peuvent réduire la sécurité du chiffrement. a) Nous avons vu plus tôt que la fonction E() était appliquée à chaque round. Cependant, une telle construction n'est pas parfaite pour le première round. Puisque rbytechain() est une application linéaire n'impliquant pas la clef, elle ne devrait pas être utilisée comme première opération sur le buffer d'entrée puisque ses effets peuvent être entièrement éliminés. Donc, si un cryptanalyste veux attaquer le composant bitshift() du premier round, il a juste à appliquer lbytechain() (la fonction inverse de rbytechain()) sur le vecteur d'entrée. Il aurait donc été une meilleure idée de mettre le mélange avec la clef en première opération. b) L'opération rbitshift() n'a besoin que des 7 premiers bits du caractère de décallage tandis que S_E les utilises tous. Il est aussi généralement considéré comme mauvaise idée d'utiliser la même clef pour diverses opérations. c) Si, pous une raison, l'attaquant a la capcité de ravir la deuxième (pas la première) sous-clef, alors ça implique qu'il puisse compromettre toutes les clefs. Bien sûr, la clef maîtresse restera inconnue à cause du sens unique de checksum128() mais nous n'en auront pas besoin pour chiffrer et déchiffrer des données. d) Dans la fonction bitshift(), une boucle est particulièrement intéressante : for (i = 0; i < mod; ++i) mask |= (1 << i); Ce qui est intéressant est que le temps d'exécution de la boucle dépend du "mod", qui est dérivé de la clef. Donc, nous concluons que cette boucle permettra probablement une "side channel attack" contre le chiffrement. Merci à X de nous l'avoir montré ;> Dans le monde de la sécurité informatique, il est très bien connu qu'une simple et minuscule erreur puisse mener à la corruption totale d'un système d'information. En cryptographie, la même règle s'applique. --[ 5 - Casser la version linéarisée Même si on regrette la non-justification de l'utilisation de l'opération d'addition, ce n'est pas le pire choix en lui-même. Que se serait-il passé si le mélange de la clef avait été fait avec une opération de xor sur GF(2^8) comme c'est le cas dans DES et AES par exemple ? Pour mesurer l'importance des considérations algébriques dans la sécurité d'un chiffrement par blocs, amusons-nous un peu avec une version linéarisée du chiffrement. C'est à dire, en remplacant la fonction S_E() avec la fonction S_E2() suivante : void S_E2 (unsigned char *key, unsigned char *block, unsigned int s) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] = (key[i] ^ block[i] ^ s) % 256; [1] // + est remplacé par xor return; } Si X, Y et K sont des vecteurs sur GF(2^8) représentant respectivement l'entrée, la sortie de S_E2() et la clef du round, alors, Y = X xor K. Remarque, K = sK xor shift. Nous utilisons K dans un but de simplification. Considérons maintenant le round complet, nous avons : V = M.U [a] (rbytechain) W = M'.V [b] (rbitshift) Y = W xor K [c] (S_E2) L'algèbre linéaire nous permet de composer les applications rbytechain() et rbitshift() puisque les dimenstion de M et M' correspondent, mais W dans [b] est un vecteur sur GF(2) tandis que W dans [c] est clairement dans GF(2^8). Cependant, à cause de l'utilisation du XOR dans [c], Y, W et K peuvent aussi êtres des vecteurs sur GF(2). Donc, S_E2() est une application affine de GF(2) entre deux espaces vectoriels de dimension 128. Nous avons alors : Y = M'.M.U xor K L'utilisation de cryptanalyse différentielle va nous aider à nous débarraser de la clef. Considérons des couples (U0,Y0 = E(U0)) et (U1,Y1 = E(U1)), alors : DELTA(Y) = Y0 xor Y1 = (M'.M.U0 xor K) xor (M'.M.U1 xor K) = (M'.M.U0 xor M'.M.U1) xor K xor K (commutativité & associativité de xor) = (M'.M).(U0 xor U1) (distributivité) = (M'.M).DELTA(U) Un tel résultat nous montre que quels que soient sK et shift, il y a toujours une correspondance linéaire qui lie une entrée différentielle à la sortie différentielle correspondante. La généralisation aux 16 rounds en utilisant des multiplications de matrices est évidente. Donc, nous avons prouvé qu'il existe une matrice Mf de 128x128 sur GF(2) telle que DELTA(Y) = Mf.DELTA(X) pour la version linéarisée du chiffrement. Alors, en admettant que nous connessions un couple (U0,Y0) et Mf, nous pouvons chiffrer n'importe quelle entrée U. En fait, Y xor Y0 = Mf.(U xor U0) et donc, Y = (Mf.(U xor U0)) xor Y0. Remarque 1 : Cette attaque ne nous donne aucune connaissance de la sous-clef et du shift, mais ces choses sont sans intéret. Le but d'une attaque n'est pas la clef elle-même mais plus la capaciter de chiffrer/déchiffrer un ensemble de textes clairs/chiffrés. En plus, en prenant en compte la gestion des clefs, si nous avons vraiment besoin de retrouver la clef maîtresse, ça serait assez casse-couille étant donné que checksum128() est une fonction à sens unique ;-) Remarque 2 : Évidement, pour pouvoir déchiffrer n'importe quelle sortie, nous devons calculer Mf^-1 qui est l'inverse de Mf. C'est quelque chose de plus intéressant n'est-ce pas ? :-) À cause de rbitshift(), nous ne pouvons pas déterminer les coefficients de Mf en utilisant une multiplication de matrices. Une recherche exaustive est bien sûr impossible à cause de l'énorme complexité (2^16384), cependant, les trouver est équivalent de résoudre un système de 128 équations (1 équation par ligne de Mf) de 128 variables (une par colonne) dans GF(2). Pour construire un tel système, nous avons besoin de 128 couples de textes (clair,chiffré). L'attaque décrite a été implémentée en utilisant la chouette librairie NTL ([SHOUP]) et peut être trouvée en annexe A du papier. $ g++ break_linear.cpp bitshift.o bytechain.o key.c hash32.o checksum128.o -o break_linear -lntl -lcrypto -I include $ ./break_linear [+] Generating the plaintexts / ciphertexts [+] NTL stuff ! [+] Calculation of Mf [+] Let's make a test ! [+] Well done boy :> Remarque : Parfois, NTL détecte une relation linéaire entre des entrées choisies (DELTA_X) et va refuser de fonctionner. En fait, pour pouvoir résoudre les 128 systèmes, nous avons besoin d'une situation où les vecteurs sont indépendants. Si ce n'est pas le cas, alors, évidement, det(M) = 0 (avec une probabilité 1/2). Puisque les entrées sont choisies aléatoirement, réessayez simplement jusqu'à ce que ça fonctionne :-) $ ./break_linear [+] Generating the plaintexts / ciphertexts [+] NTL stuff ! det(M) = 0 En conclusion, nous avons vu que la linéarité sur GF(2) de l'opération xor nous a permis d'écrire une relation affine entre deux éléments de GF(2)^128 dans la fonction S_E2() et donc de casser aisément la version linéarisée en utilisant une attaque par 128 clairs connus. L'utilisation de la non linéarité est cruciale dans la conception. Heureusement pour DPA-128, Veins a choisi l'addition modulo 256 comme mélange avec la clef qui n'est naturellement pas linéaire sur GF(2). --[ 6 - Sur la non linéarité de l'addition modulo n sur GF(2) Les fonctions bitshift() et bytechain() peuvent être décrites en utilisatn une matrice sur GF(2), il est donc intéressant d'utiliser ce corps pour des calculs algébriques. La différence entre les lois d'addition et du xor dans GF(2^n) sont dans la propagation de la retenue : w(i) + k(i) = w(i) xor k(i) xor carry(i) où w(i), k(i) et carry(i) sont des éléments de GF(2). On note w(i) comme ième bits de w et garderons cette notation jusqu'à la fin. carry(i), écrit c(i) par simplification est définie récursivement : c(i+1) = w(i).k(i) xor w(i).c(i) xor k(i).c(i) avec c(0) = 0 En utilisant cette notation, il serait donc possible de déterminer un ensemble de relations sur GF(2) entre des bits d'entrées/sorties que l'attaquant contrôlerait en utilisant une attaque par clair connu et les bits de la sous-clef (que l'attaquant essaye de deviner). Cependant, retrouver les bits de la sous-clef ne sera pas si facile. En fait, pour les déterminer, nous devons nous débarasser de la retenue en la remplacant par des polynomes à plusieurs variables où les inconnues sont des monomes d'un grand ordre. Remarque 1 : À cause de la récusrivité de la retennue, l'ordre des monomes augmente avec le nombre de bits d'entrées par round ainsi qu'avec le nombre de round. Remarque 2 : Évidement, nous ne pouvons pas utiliser de bits d'entrées/sorties intermédiaires dans nos équations. C'est parce qu'au contraire des bits de la sous-clef, ils sont dépendants de l'entrée. Nous pouvons donc exprimer le cryptosystème comme un système de polynomes sur plusieurs variables sur GF(2). Résoudre un tel système est NP-difficile. Il existe des méthodes pour des systèmes d'ordres raisonables comme les bases de groebner et des techniques de relinéarisation mais l'ordre de notre système semble bien trop grand. Cependant, pour un ensemble particulier de clefs, qu'on appelles clefs faibles, il est possible de déterminer les sous-clefs assez facilement en nous débarassant de la complexité introduite par la retenue. --[ 7 - Exploiter les clefs faibles Commencons par définir une clef faible, d'après wikipedia : "En cryptologie, une clé faible est une clé telle que son utilisation dans une procédure de chiffrement produit un comportement indésirable. Les clés faibles sont généralement peu nombreuses par rapport à l'ensemble des clés possibles. De ce fait, la probabilité d'obtenir une clé faible avec des chiffrements modernes étant très petite (lors d'une génération de clé aléatoire) il est peu probable que cela induise un problème de sécurité. Toutefois, on considère qu'il n'est pas souhaitable qu'un chiffrement ait des clés faibles." [NDT : http://fr.wikipedia.org/wiki/Cl%C3%A9_faible_%28cryptographie%29] En fait, nous avons identifié un ensemble particulier |W de |K nous permettant de gérer assez facilement le problème de la retenue. Une clef "k" fait partie de |W si et seulement si pour chaque round, le paramètre shift est un multiple de 8. Le lecteur comprendra plus tard pourquoi. Nous allons d'abord présenter l'attaque sur une version réduite de DPA par simplicité et généraliser plus tard à la version complète. --[ 7.1 - Jouer avec un chiffrement jouet Notre chiffrement jouet est un DPA avec 2 rounds. En plus, le chiffrement prend en entrée 4*8 bits au lieu de 16*8 = 128 bits ce qui veut dire que DPA_BLOCK_SIZE = 4. Nous avons aussi fait une petite modification dans l'opération bytechain(). Souvenons nous de la fonction bytechain() : void rbytechain(unsigned char *block) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] ^= block[(i + 1) % DPA_BLOCK_SIZE]; return; } Puisque block est à la fois entrée ET sortie de la fonction, nous avons, pour DPA_BLOCK_SIZE = 4 : V(0) = U(0) xor U(1) V(1) = U(1) xor U(2) V(2) = U(2) xor U(3) V(3) = U(3) xor V(0) = U(0) xor U(1) xor U(3) Où V(x) est le xème octet Donc, avec nos modifications : V(0) = U(0) xor U(1) V(1) = U(1) xor U(2) V(2) = U(2) xor U(3) V(3) = U(3) xor U(0) Concernant la notation mathématique (subissez votre ascii !@#) : - U,V,W,Y la notation des vecteurs de la section 5 reste. - Xj(i) est le ième bits du vecteurs Xj où j est le jème round. - Vecteur U0 est équivalent à P où P est le texte clair. - m est le shift du round 0 - n est le shift du round 1 - xor sera écrit "+" puisque nous sommes dans GF(2). - Tous les calculs d'indices seront fait sur l'anneau ZZ_32 Comment avons-nous choisi |W ? Utiliser l'algèbre dans GF(2) implique de devoir gérer la retenue. Cependant, si k est une clef faible (fait partie de |W), alors, on peut organiser les calculs pour que ça ne soit plus pénible. Soit i le bits le plus faible d'un octet d'entrée. Donc, pour chaque i, élément de {0,8,16,24}, nous avons : u0(i) = p(i) v0(i) = p(i) + p(i+8) w0(i+m) = v0(i) y0(i) = w0(i) + k0(i) + C0(i) y0(i+m) = w0(i+m) + k0(i+m) + C0(i+m) y0(i+m) = p(i) + p(i+8) + k0(i+m) + C0(i+m) /* carry(0) = 0 */ y0(i+m) = p(i) + p(i+8) + k0(i+m) u1(i) = y0(i) v1(i) = y0(i) + y0(i+8) w1(i+n) = v1(i) y1(i) = w1(i) + k1(i) + C1(i) y1(i+n) = w1(i+n) + k1(i+n) + C1(i+n) y1(i+n) = y0(i) + y0(i+8) + k1(i+n) + C1(i+n) y1(i+n+m) = y0(i+m) + y0(i+m+8) + k1(i+n+m) + C1(i+n+m) /* carry(0) = 0 */ y1(i+n+m) = p(i) + p(i+8) + k0(i+m) + p(i+8) + p(i+16) + k0(i+m+8) + k1(i+n+m) y1(i+n+m) = p(i) + k0(i+m) + p(i+16) + k0(i+m+8) + k1(i+n+m) Comme dit plus haut, i est élément de {0,8,16,24}, on peut donc écrire : y1(n+m) = p(0) + k0(m) + p(16) + k0(m+8) + k1(n+m) y1(8+n+m) = p(8) + k0(8+m) + p(24) + k0(m+16) + k1(8+n+m) y1(16+n+m) = p(16) + k0(16+m) + p(0) + k0(m+24) + k1(16+n+m) y1(24+n+m) = p(24) + k0(24+m) + p(8) + k0(m) + k1(24+n+m) Dans le cas d'une attaque par clair connu, l'attaquant a la connaissance d'un ensemble de couples (P,Y1). Donc, considérant le système précédant, K0 et K1 sont les inconnues. Nous avons ici un système clairement sous-défini puisqu'il est composé de 4 équations et de 4^2 inconnues. Il nous fournira les relations entre chaque bits faible de Y et le bits faible de K0 et K1. Remarque 1 : n,m sont inconnus. Une approche triviale de les déterminer a une complexité de (2^4)^2 = 2^8. Bien que ça semble une bonne idée, rappellons au lecteur que nous considéront un chiffrement avec moins de rounds ! En fait, appliquer la même idée aux 16 rounds nous coutera (2^4)^16 = 2^64! Une telle complexité est casse-couille, même de nos jours :-) Une bien meilleur approche est de deviner (n+m) puisque ça coûte 2^4 quel que soit le nombre de rounds. Ça nous permettra d'écrire des relations entre certains bits d'entrées et de sorties. Nous n'avons pas besoin de connaître exactement m et n. La connaissance des variables intermédiaires k0(x+m) et k1(y+n+m) est suffisante. Remarque 2 : Un système sous-défini fourni beaucoup de solutions. Nous pouvons donc choisir arbitrairement 4 variables et les fixer avec des valeurs de notre choix. Bien sur, nous devons bien les choisir pour pouvoir résoudre le système avec les variables restantes. Par exemple, k0(m), k0(m+8) et k1(n+m) n'est pas une bonne idée à cause de la première équation. Cependant, fixer tous les k0(x+m) sera une bonne idée car ça nous donnera automatiquement les k1(y+n+m) correspondantes. Allons plus loins. Soit i faisant partie de {1,9,17,25}. On peut écrire : u0(i) = p(i) v0(i) = p(i) + p(i+8) w0(i+m) = v0(i) y0(i) = w0(i) + k0(i) + w0(i-1)*k0(i-1) y0(i+m) = w0(i+m) + k0(i+m) + w0(i+m-1)*k0(i+m-1) y0(i+m) = p(i) + p(i+8) + k0(i+m) + w0(i+m-1)*k0(i+m-1) y0(i+m) = p(i) + p(i+8) + k0(i+m) + (p(i-1) + p(i-1+8))*k0(i+m-1) u1(i) = y0(i) v1(i) = y0(i) + y0(i+8) w1(i+n) = v1(i) y1(i) = w1(i) + k1(i) + C1(i) y1(i) = w1(i) + k1(i) + w1(i-1)*k1(i-1) y1(i+n) = w1(i+n) + k1(i+n) + w1(i-1+n)*k1(i-1+n) y1(i+n) = y0(i) + y0(i+8) + k1(i+n) + (y0(i-1) + y0(i+8-1)) * k1(i-1+n) y1(i+n+m) = y0(i+m) + y0(i+m+8) + k1(i+m+n) + (y0(i+m-1) + y0(i+m+8-1)) * k1(i+m+n-1) y1(i+n+m) = p(i) + p(i+8) + k0(i+m) + (p(i-1) + p(i-1+8)) * k0(i+m-1) + p(i+8) + p(i+16) + k0(i+m+8) + (p(i+8-1) + p(i-1+16)) * k0(i+m-1+8) + k1(i+n+m) + k1(i+m+n-1) * [p(i-1) + p(i+8-1) + k0(i+m-1)] + k1(i+m+n-1) * [p(i-1+8) + p(i+16-1) + k0(i+m-1+8)] y1(i+n+m) = p(i) + k0(i+m) + (p(i-1) + p(i-1+8)) * k0(i+m-1) + p(i+16) + k0(i+m+8) + (p(i+8-1) + p(i-1+16)) * k0(i+m-1+8) + k1(i+n+m) + k1(i+m+n-1)*[p(i-1) + k0(i+m-1)] + k1(i+m+n-1)*[p(i-1+16) + k0(i+m-1+8)] Grâce aux solutions du système précédent, nous connaissons les variables k0(i+m+n-1+x) et k1(i+m-1+y). Donc, on peut réduire les équations précédentes à : A(i) = k0(i+m) + k0(i+m+8) + k1(i+n+m) (alpha) Où A(i) est une valeur connue pour l'attaquant. Remarque 1 : Cette équation représente le même système que trouvé dans le cas où i est le bits le plus faible ! Toutes les remarques précédentes restent valables. Remarque 2 : Si nous n'avions pas eu connaissance des bits k0(i+m+n-1+x) et k1(i+m-1+y), alors, le nombre de variables aurait grandis sérieusement. En plus, nous aurions du travailler avec quelques monomes de degré 2 :-/. Nous pouvons donc conjecturer que l'équation alpha va rester vraie pour chaque i dans {a,a+8,a+16,a+24} avec 0 <= a < 8. --[ 7.2 - Généralisation et complexité attendue Occupons nous maintenant de la réelle fonction bytechain(). Comme dit plus haut et pour DPA_BLOCK_SIZE = 4, nous avons : V(0) = U(0) xor U(1) V(1) = U(1) xor U(2) V(2) = U(2) xor U(3) V(3) = U(0) xor U(1) xor U(3) C'est assez pénible puisque le dernier octet N'EST PAS calculé comme V(0), V(1) et V(2). À cause de la rotation impliquée, nous ne seront pas capables de connaitre quand le bit manipulé fait partie de V(3) ou pas. Donc, nous devons utiliser les formules générales suivantes : V(i) = U(i) + U(i+1) + a(i).U(i+2) où a(i) = 1 pour i = 24 à 31 Pour i dans {0,8,16,24} on a : u0(i) = p(i) v0(i) = p(i) + p(i+8) + a0(i).p(i+16) w0(i+m) = v0(i) y0(i) = w0(i) + k0(i) + C0(i) y0(i+m) = w0(i+m) + k0(i+m) + C0(i+m) y0(i+m) = p(i) + p(i+8) + a0(i).p(i+16) + k0(i+m) + C0(i+m) /*carry(0) = 0 */ y0(i+m) = p(i) + p(i+8) + a0(i).p(i+16) + k0(i+m) Donc, au deuxième round : u1(i) = y0(i) v1(i) = y0(i) + y0(i+8) + a1(i).y0(i+16) w1(i+n) = v1(i) y1(i) = w1(i) + k1(i) + C1(i) y1(i+n) = w1(i+n) + k1(i+n) + C1(i+n) y1(i+n) = y0(i) + y0(i+8) + a1(i).y0(i+16) + k1(i+n) + C1(i+n) y1(i+n+m) = y0(i+m) + y0(i+m+8) + a1(i+m).y0(i+m+16) + k1(i+n+m) y1(i+n+m) = p(i) + p(i+8) + a0(i).p(i+16) + k0(i+m) + p(i+8) + p(i+16) + a0(i).p(i+24) + k0(i+m+8) + a1(i+m).[p(i+16) + p(i+24) + a0(i).p(i) + k0(i+m+16)] + k1(i+n+m) y1(i+n+m) = p(i) + a0(i).p(i+16) + k0(i+m) + p(i+16) + a0(i).p(i+24) + k0(i+m+8) + a1(i+m).[p(i+16) + p(i+24) + a0(i).p(i) + k0(i+m+16)] + k1(i+n+m) a0(i) n'est pas un problème puisque nous le connaissons. C'est cohérent avec le fait que la première opération du chiffrement est bytechain() qui est inversible pour l'attaquant. Cependant, le problème se trouve dans les variables a1(i+m). Deviner a1(i+m) est en hors de question car ça nous coûterait une complexité de (2^4)^15 = 2^60 pour les 16 rounds ! La solution est de considérer a1(i+m) comme un autre ensemble de 4 variables. On peut aussi ajouter l'équation au système : a1(m) + a1(m+8) + a1(m+16) + a1(m+24) = 1 Cette équation restera vraie pour les autres bits. Donc, quelle est la complexité globale ? Évidement, avec DPA_BLOCK_SIZE = 16, chaque système est composé de 16+1 équation de 16+1 variables (nous avons fixé les autres). Donc, la complexité de cette résolution est de log(17^3) / log(2) ~ 2^13. Nous résoudrons 8 systèmes puisqu'il y a 8 bits par octet. Donc, la complexité globale est à peu près (2^13)*8 = 2^16. Remarque : Nous n'avons pas pris en compte le calcule des équations car il est admis qu'elles sont obtenues en utilisant un programme de calcul formel comme pari-gp ou magma. --[ 7.3 - Cardinalité de |W Quelle est la probabilité de choisir une clef faible ? Nous avons vu que notre critère de clef faible est que pour chaque round, le paramètre de rotation doit être multiple de 8. Évidement, ça arrive avec une probabilité théorique de 16 / 128 = 1/8 par round. Puisque nous considérons que les sous-clefs sont aléatoires, la génération des paramètres de rotations sont indépendants, ce qui signifie que la probabilité générale est de (1/16)^16 = 1/2^64. Bien qu'une probabilité de 1/2^64 signifie un (énorme) ensemble de 2^64 clefs faibles, dans la vie réelle, il y a très peu de chance d'en choisir une . En fait, vous avez sans doutes plus de chance de gagner à la loterie ;) Cependant, deux faits doivent être remarqués : - Nous avons présenté un ensemble de clefs faibles, mais il y en a encore d'autres ! - Nous avons montré une autre faiblesse dans la conception du DPA-128 Remarque : Une probabilité de 1/8 par round est purement théorique puisqu'elle suppose une distribution uniforme de la sortie de hash32(). Il ne serait pas si surprenant que ça soit différent en pratique. Donc, nous avons fait un petit teste pour calculer la réelle probabilité (Annexe B). $ gcc test.hash32.c checksum128.o hash32.o -o test.hash32 -O3 -fomit-frame-pointer $ time ./test.hash32 [+] Probability is 0.125204 real 0m14.654s user 0m14.649s sys 0m0.000s $ gp -q ? (1/0.125204) ^ 16 274226068900783.2739747241633 ? log(274226068900783.2739747241633) / log(2) 47.96235905375676878381741198 ? Ce résultat nous montre clairement que la probabilité qu'un décallage soit multiple de 8 est autour de 1/2^2.99 ~ 1/8 par round, qu'on peut assimiler à la probabilité théorique car la différence est trop petite pour être significative. Pour améliorer notre mesure, nous avons utilisé checksum128() comme entrée de hash32(). En plus, nous avons essayé de tester hash32 sans le bug "*k &&" mentionné plus haut. Tous ces tests ont donnés des résultats similaires, ce qui signifie que ce bug n'est pas important en pratique et que checksum128() ne semble pas particulièrement biaisé. C'est un bon point pour DPA :-D --[ 8 - Casser les fonctions de hash sans clef basé sur DPA Dans son papier, Veins a aussi expliqué comment une fonction de hash peut être construite à partir de DPA. Nous allons analyser le schéma proposé et montrer comment le casser complètement. --[ 8.1 - Introduction aux fonctions de hashage Citant encore une fois l'excellent HAC [MenVan] : "Une fonction de hashage est une fonction h qui a, au minimum, les deux propriétés suivantes : 1. Compression - h fait correspondre à une entrée x de taille arbitraire, une sortie h(x) de taille fixée n. 2. facile à calculer - soit h et une entrée x, h(x) est facile à calculer. En cryptographie, il y a essentiellement deux familles de fonctions de hash : 1. Les MAC (Message Authentication Codes). Elles utilisent des clefs et fournissent autant l'authentification (de la source) et l'intégrité du message. 2. Les MDC (Modification Detection Code), parfois appellées MIC. Elles n'utilisent pas de clef et ne fournissent que l'intégrité. Nous nous concentrerons sur cette famille de fonction. quand il conçoit sa fonction de hashage, le cryptographe veut généralement qu'elle respecte ces trois propriétés : - résistance de la préimage. Pour tout y, il ne devrait pas être possible de trouver un (x c'est à dire impossible de le calculer) tel que h(x) = y. Une telle propriété implique que la fonction ne peut pas être inversible. - résistance de la 2ème préimage. Pour tout x, ils ne devrait pas être possible de trouver un x' tel que h(x) = h(x') quand x et x' sont différents. - résistance aux collisions. Il ne devrait pas être possible de trouver un x et un x' (l'un différent de l'autre) tel que h(x) = h(x'). Remarque 1 : Les propriétés 1 et 2 sont essentielles quand on parle d'intégrité de binaires. Remarque 2 : Les attaques publiées au sujet de MD5 et SHA-0/SHA-1 concernaient la troisième propriété. Bien qu'il soit vrai que trouver des collisions sur une fonction de hash est assez pour que la communauté de crytpo la considère comme non-sûre (et mène parfois vers un nouveau standard [NIST2007]), pour la pluspart des usages, ça reste suffisant. Il y a beaucoup de manières de concevoir des fonctions MDC. Certaines fonctions sont basées sur MD4 comme les fonctions MD5 et SHA* qui se fient énormément sur l'algèbre booléenne et les opérations sur GF(2^32), certaines sont basées sur des problèmes NP comme RSA et en fin, d'autres sont basées sur des chiffrements par blocs. La troisième catégorie est particulièrement intéressante puisque la sécurité des fonctions de hash peut être réduite à celle des chiffrements par blocs sous-jacents. Ça n'est bien sûr vrai qu'avec une bonne conception. --[ 8.2 - Algorithme DPAsum() La fonction de hash basée sur DPA se trouve dans les fonctions DPA_sum() et DPA_sum_write_to_file() qui se trouvent respectivement dans sum.c et data.c. Détaillons-les un peu en pseudo-code : Soit M le message à hasher, soit M(i) le ième bloc de 128bits du message. Soit N = DPA_BLOCK_SIZE * i + j la taille en octets du message où i et j sont des entiers tels que i = N / DPA_BLOCK_SIZE et 0 <= j < 16. Soit C un tableau de 128 bits éléments où les résultats de calculs intermédiaires sont stockés. Le dernier élément de ce tableau est le hash du message. func DPA_sum(K0,M,C): K0 = key("deadbeef"); IV = "0123456789abcdef"; C(0) = E( IV , K0); C(1) = E( IV xor M(0) , K0); FOR a = 1 to i-1: C(a+1) = E( C(a) xor M(a) , K0); if j == 0: C(i+1) = E( C(i) xor 000...000 , K0) else C(i+1) = E( C(i) xor PAD( M(i) ); C(i+2) = E( C(i+1) xor 000...00S , K0) /* s = 16-j */ return; func DPA_sum_write_to_file(C, file): write(file,C(last_element)); return; --[ 8.3 - Faiblesses dans la conception/implémentation Nous avons remarqué quelques erreurs d'implémentations dans le code : a) En utilisant l'algorithme du calcul du hash, chaque élément du tableau C est défini récursivement, mais C(0) n'est jamais utilisé dans les calculs. Ça n'impacte pas la sécurité en elle-même mais est un peu étrange et pourrait nous faire penser que la fonction n'a pas été conçue avant d'être programmée. b) Quand la taille de M n'est pas un multiple de DPA_BLOCK_SIZE (j n'est pas égal à 0), alors l'algorithme calcule le dernier élément avec un masque de xor où le dernier octet donne des informations sur la taille du message original. Cependant, ce qui est inclu dans le padding n'est pas la taille du message en lui-même mais plus la taille du padding. Si nous prenons l'exemple de la construction Merkle-Damgard bien connue sur laquelle sont basées les fonctions MD{4,5} et SHA-{0,1}, alors, la longueur du message était initialement ajoutée pour éviter les attaques par collisions avec des messages de taille différentes. Donc, dans le cas de DPASum(), ajouter j au message n'est pas suffisant car il restera possible de faire des collisions avec des messages de tailles (DPA_BLOCK_SIZE*a + j) et (DPA_BLOCK_SIZE*b + j) où évidement, a et b sont différents. Remarque : Le fait que le IV et la clef maitresse soit fixé initialement n'est pas un problème en lui-même puisque nous parlons ici de MDC. --[ 8.4 - Une attaque par (2ème) préimage À cause de propriétés de construction de la fonction de hash, une fois avec un message X, il est trivial de créer un message X' tel que h(X) = h(X'). C'est ce qu'on appelle construire une attaque par 2èùe préimage. Nous avons créé un programme rapide et dégeu pour l'illustrer (Annexe C). Il prend un message de 32 octets en entrée et produit un autre de 32 octets avec le même hash : $ cat to.hack | hexdump -C 00000000 58 41 4c 4b 58 43 4c 4b 53 44 4c 46 4b 53 44 46 |XALKXCLKSDLFKSDF| 00000010 58 4c 4b 58 43 4c 4b 53 44 4c 46 4b 53 44 46 0a |XLKXCLKSDLFKSDF.| 00000020 $ ./dpa -s to.hack 6327b5becaab3e5c61a00430e375b734 $ gcc break_hash.c *.o -o break_hash -I ./include $ ./break_hash to.hack > hacked $ ./dpa -s hacked 6327b5becaab3e5c61a00430e375b734 $ cat hacked | hexdump -C 00000000 43 4f 4d 50 4c 45 54 45 4c 59 42 52 4f 4b 45 4e |COMPLETELYBROKEN| 00000010 3e bf de 93 d7 17 7e 1d 2a c7 c6 70 66 bb eb a3 |>.....~.*..pf...| 00000020 Chouette non ? :-) Nous avons été capable d'écrire des données arbitraires dans les premiers 16 octets et d'ensuite calculer les 16 octets suivants pour que le fichier "hacké" ait le même hash. Mais comment avont nous pu faire une chose si diabolique ? Admettant que la taille des deux messages est de 32 bytes, alors : h(Mi) = E(E(Mi(0) xor IV,K0) xor Mi(1),K0) Donc, il est évident que : h(M1) = h(M2) est équivalent à : E(E(M1(0) xor IV,K0) xor M1(1),K0) = E(E(M2(0) xor IV,K0) xor M2(1),K0) Qui peut être réduit en : E(M1(0) xor IV,K0) xor M1(1) = E(M2(0) xor IV,K0) xor M2(1) Ce qui nous donne ensuite : M2(1) = E(M2(0) xor IV,K0) xor E(M1(0) xor IV,K0) xor M1(1) [A] Puisque M1,IV,K0 sont des paramètres connus, alors, pour un M2(0) choisi, [A] nous donne M2(1) tel que h(M1) = h(M2). Remarque 1 : En fait, un tel résultat peut être facilement généralisé aux messages sur n octets. En particulier, l'attaquant peut mettre n'importe quoi dans son message est "le corriger" en utilisant les derniers blocs (si n>= 32). Remarque 2 : Bien sûr, construire une attaque de préimage est aussi très facile. Nous avons mentionné précédement que nous avion, pour un message de 32 octets : h(Mi) = E(E(Mi(0) xor IV,K0) xor Mi(1),K0) Donc, Mi(1) = E^-1(h(Mi),K0) xor E(Mi(0) xor IV,K0) [B] L'équation [B] nous dis comment générer Mi(1) pour avoir h(Mi) en sortie. Il ne semble pas que ça soit vraiment une fonction de hash à sens unique ? ;-) Construire une fonction de hash à partir d'un chiffrement par bloc est un problème bien connu en cryptographie qui n'implique pas seulementla sécurité du chiffrement sous-jacent. On devrait plus se fier sur les algorithmes bien connus et énorméments analysés pour ce buts plutôt que tenter de concevoir les siens. --[ 9 - Conclusion Nous avons mis en évidence quelques faiblesses de ce chiffrement et avons aussi été capables de casser totalement la fonction de hash proposée basée sur DPA. Dans son papier, Veins a implicitement mis les bases d'une discutions sur laquelle nous voulons donner notre opinion. Nous affirmons qu'il est nécessaire de comprendre correctement la cryptologie. Le but de ce papier était de montrer les faits, rien de plus. Être hacker ou pas, paranoïaque ou simplement prudent, les règles sont les mêmes pour tout le monde dans ce domaine : rien de doit être fait sans réflexions. --[ 10 - Remerciements Les gens de #TF crypto pour les discussions amicales et intelligentes et surtout X pour m'avoir donner tous ces indices. J'ai appris beaucoup de vous :-) Mes amis de #K40r1 pour ces années de fun ;-) Salut à tous :) Enfin, mais pas des moindes, ma GF [NDT : Girl Friend, mais si je traduit, la blague disparait] avec sa gentillesse avec ses caractéristiques primaires :> (Cependant, si elle trouve la blague dans la dernière phrase, je suis mort :|) --[ 11 - Bibliography [DPA128] A Polyalphabetic Substitution Cipher, Veins, Phrack 62. [FakeP63] Keeping 0day Safe, m1lt0n, Phrack(.nl) 63. [MenVan] Handbook of Applied Cryptography, Menezes, Oorschot & Vanstone. [Knud99] Correlation in RC6, L. Knudsen & W. Meier. [CrypTo] Two balls ownz one, http://fr.wikipedia.org/wiki/Cryptorchidie [Vaud] An Experiment on DES - Statistical Cryptanalysis, S. Vaudenay. [Ryabko] Adaptative chi-square test and its application to some cryptographic problems, B. Ryabko. [CourtAlg] How Fast can be Algebraic Attacks on Block Ciphers ?, Courtois. [BiSha90] Differential Cryptanalysis of DES-like Cryptosystems, E. Biham & A. Shamir, Advances in Cryptology - CRYPTO 1990. [Matsui92] A new method for known plaintext attack of FEAL cipher, Matsui & A. Yamagishi, EUROCRYPT 1992. [NSA2007] Just kidding ;-) [SHOUP] NTL library, V. Shoup, http://www.shoup.net/ntl/ [NIST2007] NIST, http://www.csrc.nist.gov/pki/HashWorkshop/index.html, 2007 --[ Annexe A - Breaking the linearised version 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* Crappy C/C++ source. I'm in a hurry for the paper redaction so don't * blame me toooooo much please ! :> */ #include #include #include #include #include #include #include #include #include #include "dpa.h" using namespace NTL; void S_E2 (unsigned char *key, unsigned char *block, unsigned int s) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) { block[i] ^= (key[i] ^ s) % 256; } return; } void E2 (unsigned char *key, unsigned char *block, unsigned int shift) { rbytechain (block); rbitshift (block, shift); S_E2 (key, block, shift); } void DPA_ecb_encrypt (DPA_KEY * key, unsigned char * src, unsigned char * dst) { int j; memcpy (dst, src, DPA_BLOCK_SIZE); for (j = 0; j < 16; j++) E2 (key->subkey[j].key, dst, key->subkey[j].shift); return; } void affichage(unsigned char *chaine) { int i; for(i=0; i<16; i++) printf("%.2x",(unsigned char )chaine[i]); printf("\n"); } unsigned char test_p[] = "ABCD_ABCD_12____"; unsigned char test_c1[16]; unsigned char test_c2[16]; DPA_KEY key; RC4_KEY rc4_key; struct vect { unsigned char plaintxt[16]; unsigned char ciphertxt[16]; }; struct vect toto[128]; unsigned char src1[16], src2[16]; unsigned char block1[16], block2[16]; int main() { /* Key */ unsigned char str_key[] = " _323DFF?FF4cxsdé&"; DPA_set_key (&key, str_key, DPA_KEY_SIZE); /* Init our RANDOM generator */ char time_key[16]; snprintf(time_key, 16, "%d%d",(int)time(NULL), (int)time(NULL)); RC4_set_key(&rc4_key, strlen(time_key), (unsigned char *)time_key); /* Let's crypt 16 plaintexts */ printf("[+] Generating the plaintexts / ciphertexts\n"); int i=0; int a=0; for(; i<128; i++) { RC4(&rc4_key, 16, src1, src1); // Input is nearly random :) DPA_ecb_encrypt (&key, src1, block1); RC4(&rc4_key, 16, src2, src2); // Input is nearly random :) DPA_ecb_encrypt (&key, src2, block2); for(a=0;a<16; a++) { toto[i].plaintxt[a] = src1[a] ^ src2[a]; toto[i].ciphertxt[a] = block1[a] ^ block2[a]; } } /* Now the NTL stuff */ printf("[+] NTL stuff !\n"); vec_GF2 m2(INIT_SIZE,128); vec_GF2 B(INIT_SIZE,128); mat_GF2 M(INIT_SIZE,128,128); mat_GF2 Mf(INIT_SIZE,128,128); // The final matrix ! clear(Mf); clear(M); clear(m2); clear(B); /* Lets fill M correctly */ int k=0; int j=0; for(k=0; k<128; k++) // each row ! { for(i=0; i<16; i++) { for(j=0; j<8; j++) M.put(i*8+j,k,(toto[k].plaintxt[i] >> j)&0x1); } } GF2 d; determinant(d,M); /* if !det then it means the vector were linearly linked :'( */ if(IsZero(d)) { std::cout << "det(M) = 0\n" ; exit(1); } /* Let's solve the 128 system :) */ printf("[+] Calculation of Mf\n"); for(k=0; k<16; k++) { for(j=0; j<8; j++) { for(i=0; i<128; i++) { B.put(i,(toto[i].ciphertxt[k] >> j)&0x1); } solve(d, m2, M, B); #ifdef __debug__ std::cout << "m2 is " << m2 << "\n"; #endif int b=0; for(;b<128;b++) Mf.put(k*8+j,b,m2.get(b)); } } #ifdef __debug__ std::cout << "Mf = " << Mf << "\n"; #endif /* Now that we have Mf, let's make a test ;) */ printf("[+] Let's make a test !\n"); bzero(test_c1, 16); bzero(test_c2, 16); char DELTA_X[16]; char DELTA_Y[16]; bzero(DELTA_X, 16); bzero(DELTA_Y, 16); DPA_ecb_encrypt (&key, test_p, test_c1); // DELTA_X ! unsigned char U0[] = "ABCDEFGHABCDEFG1"; unsigned char Y0[16]; DPA_ecb_encrypt (&key, U0, Y0); for(i=0; i<16; i++) { DELTA_X[i] = test_p[i] ^ U0[i]; } // DELTA_Y ! vec_GF2 X(INIT_SIZE,128); vec_GF2 Y(INIT_SIZE,128); clear(X); clear(Y); for(k=0; k<16; k++) { for(j=0; j<8; j++) { X.put(k*8+j,(DELTA_X[k] >> j)&0x1); } } Y = Mf * X; #ifdef __debug__ std::cout << "X = " << X << "\n"; std::cout << "Y = " << Y << "\n"; #endif GF2 z; for(k=0; k<16; k++) { for(j=0; j<8; j++) { z = Y.get(k*8+j); if(IsOne(z)) DELTA_Y[k] |= (1 << j); } } // test_c2 ! for(i=0; i<16; i++) test_c2[i] = DELTA_Y[i] ^ Y0[i]; /* Compare the two vectors */ if(!memcmp(test_c1,test_c2,16)) printf("\t=> Well done boy :>\n"); else printf("\t=> Hell !@#\n"); #ifdef __debug__ affichage(test_c1); affichage(test_c2); #endif return 0; } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - --[ Annexe B - Probability evaluation of (hash32()%8 == 0) 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - #include #include #include #include #define NBR_TESTS 0xFFFFF int main() { int i = 0, j = 0; char buffer[16]; int cmpt = 0; int rand = (time_t)time(NULL); float proba = 0; srandom(rand); for(;i #include #include #include #include #include #include "dpa.h" void E2 (unsigned char *key, unsigned char *block, unsigned int shift) { rbytechain (block); rbitshift (block, shift); S_E (key, block, shift); } void DPA_ecb_encrypt (DPA_KEY * key, unsigned char * src, unsigned char * dst) { int j; memcpy (dst, src, DPA_BLOCK_SIZE); for (j = 0; j < 16; j++) E2 (key->subkey[j].key, dst, key->subkey[j].shift); return; } void affichage(unsigned char *chaine) { int i; for(i=0; i<16; i++) printf("%.2x",(unsigned char )chaine[i]); printf("\n"); } int main(int argc, char **argv) { DPA_KEY key; unsigned char str_key[] = "deadbeef"; unsigned char IV[] = "0123456789abcdef"; unsigned char evil_payload[] = "COMPLETELYBROKEN"; unsigned char D0[16],D1[16]; unsigned char final_message[32]; int fd_r = 0; int i = 0; if(argc < 2) { printf("Usage : %s \n",argv[0]); exit(EXIT_FAILURE); } DPA_set_key (&key, str_key,8); if((fd_r = open(argv[1], O_RDONLY)) < 0) { printf("[+] Fuck !@#\n"); exit(EXIT_FAILURE); } if(read(fd_r, D0, 16) != DPA_BLOCK_SIZE) { printf("Too short !@#\n"); exit(EXIT_FAILURE); } if(read(fd_r, D1, 16) != DPA_BLOCK_SIZE) { printf("Too short 2 !@#\n"); exit(EXIT_FAILURE); } close(fd_r); memcpy(final_message, evil_payload, DPA_BLOCK_SIZE); blockchain(evil_payload, IV); DPA_ecb_encrypt (&key, evil_payload, evil_payload); blockchain(D0,IV); DPA_ecb_encrypt (&key, D0, D0); blockchain(D0,D1); blockchain(evil_payload, D0); memcpy(final_message+DPA_BLOCK_SIZE, evil_payload, DPA_BLOCK_SIZE); for(i=0; i