==Phrack Inc.==

               Volume 0x0c, Issue 0x40, Phile #0x0a of 0x11


|=-----------------------------------------------------------------------=|
|=---------------------=[ Cryptanalyse du DPA-128 ]=---------------------=|
|=-----------------------------------------------------------------------=|
|=-----------------------------------------------------------------------=|
|=------------------=[          Par SysK             ]=------------------=|
|=------------------=[ <syskall_at_phreaker_dot_net> ]=------------------=|
|=--------------=[ 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 quelues 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 <iostream>
#include <fstream>
#include <openssl/rc4.h>
#include <NTL/ZZ.h>
#include <NTL/ZZ_p.h>
#include <NTL/mat_GF2.h>
#include <NTL/vec_GF2.h>
#include <NTL/GF2E.h>
#include <NTL/GF2XFactoring.h>
#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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#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<NBR_TESTS;i++)
    {
        for(j=0; j<4; j++)
        {
            rand = random();
            memcpy(buffer+4*j,&rand,4);
        }
        checksum128 (buffer, buffer, 16);
        if(!(hash32(buffer,16)%8))
            cmpt++;
    }
    proba = (float)cmpt/(float)NBR_TESTS;
    printf("[+] Probability is around %f\n",proba);
    return 0;
}
8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - -


--[ Annexe C - 2nd preimage attack on 32 bytes messages

8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - -
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#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 <file>\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<DPA_BLOCK_SIZE*2; i++)
        printf("%c",final_message[i]);
    return 0;
}
8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - -