Smanuel These
Smanuel These
cryptographiques
Stéphane Manuel
THÈSE
par
Stéphane Manuel
Composition du jury
Je voudrais aussi remer ier parti ulièrement Claude Carlet que j'ai eu le plaisir
d'avoir omme enseignant à l'université Paris 8 et grâ e à qui j'ai pu dé ouvrir la
ryptographie.
Finalement, mes derniers remer iements sont pour elle qui partage ma vie depuis
bientt 17 ans, mon épouse Nathalie, qui m'a toujours soutenu dans toutes les hoses
que j'ai entreprises et sans qui ette thèse n'aurait probablement jamais vu le jour.
i
ii
Je dédie ette thèse à
Dieu,
ma femme,
mon ls et mes frères,
ma famille et mes amis.
iii
iv
Table des matières
Chapitre 1
Introdu tion
1-1 Prin ipe des fon tions de ha hage . . . . . . . . . . . . . . . . . 3
1-3.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chapitre 2
Constru tions lassiques et leur sé urité
2-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
di ile . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
v
Table des matières
Chapitre 3
Présentation des fon tions SHA-0 et SHA-1
3-1 Prin ipe de fon tionnement . . . . . . . . . . . . . . . . . . . . . 33
Chapitre 4
Prin ipe des ryptanalyses de SHA-0 et SHA-1
4-1 Cryptanalyses diérentielles des fon tions de ha hage ryptogra-
phiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
registres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
vi
Chapitre 5
Cryptanalyses pratiques
5-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5-6.3 Boomerangs . . . . . . . . . . . . . . . . . . . . . . . . . 83
Chapitre 6
A élération de la ryptanalyse de SHA-0
6-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Chapitre 7
Amélioration de la ara téristique linéaire
7-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
vii
Table des matières
Chapitre 8
Évaluation Statistique du omportement des ollisions lo ales
8-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Chapitre 9
Les fon tions XOR-Hash et FSB
9-1 La fon tion XOR-Hash . . . . . . . . . . . . . . . . . . . . . . . 129
viii
Partie IV Con lusions et perspe tives
Chapitre 10
Con lusions et perspe tives
Bibliographie 145
Table des gures 155
Liste des tableaux 159
Bibliographie 163
ix
Table des matières
x
Première partie
1
1
Introdu tion
Sommaire
1-1 Prin ipe des fon tions de ha hage . . . . . . . . ... 3
1-2 Domaines d'utilisation des fon tions de ha hage ryp-
tographiques . . . . . . . . . . . . . . . . . . . . . ... 5
1-3 Fon tions de ha hage ryptographiques . . . . . ... 6
1-3.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . 6
1-3.2 Propriétés lassiques . . . . . . . . . . . . . . . . . . . 7
1-4 Bref historique des fon tions de ha hage ryptogra-
phiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Tables de ha hage. Une table de ha hage (Hash Table ) est une stru ture de
données permettant d'asso ier une valeur à une lé. Cette stru ture se présente le
plus souvent sous la forme d'un tableau et permet d'ee tuer des re her hes en temps
quasi onstant. L'a ès à une valeur se fait au moyen d'une adresse permettant de
déterminer la lo alisation d'un élément quel onque dans le tableau. Cette adresse est
obtenue en appliquant une fon tion de ha hage à une lé. La valeur asso iée à ette
lé est alors sto kée dans la ase orrespondante du tableau. La fon tion de ha hage
transforme don une lé de re her he en adresse permettant d'obtenir dire tement
la valeur re her hée.
3
Chapitre 1. Introdu tion
b b
b b b b
b b b b b b b b b b b b b b b b b b b b b b b bb b b
b bb b b b b b b bb bb
bb b b bb bbb
bb b b bb
b b b b b b b
bb b b b bb b
b b b b bb bb b b bbb b
bb b b bb
b
0101001010...
Dans le adre des tables de ha hage, la fon tion de ha hage utilisée peut être
inversible (il est possible de retrouver une lé à partir d'une adresse). De plus, l'exis-
ten e de ollisions (deux lés aboutissant à une même adresse), bien que demandant
un traitement parti ulier, n'invalide pas la stru ture. Le fait d'autoriser es deux
omportements, diéren ie fondamentalement les fon tions de ha hage qui sont uti-
lisées dans les tables de ha hage, des fon tions de ha hage ryptographiques.
4
1-2. Domaines d'utilisation des fon tions de ha hage ryptographiques
onstitue l'élément prin ipal pris en onsidération lors de la on eption d'une telle
fon tion. Les propriétés ryptographiques que l'on exige des fon tions de ha hage
varient selon les domaines où elles sont employées.
Intégrité des données. Il s'agit de la fon tionnalité prin ipale demandée à une
fon tion de ha hage ryptographique. Elle permet de vérier que des données n'ont
pas été altérées depuis leur réation ou lors de leur transmission. Le moindre han-
gement dans les données doit, ave une très grande probabilité, aboutir à l'obtention
d'empreintes diérentes. Historiquement, les premières fon tions proposées pour as-
surer ette fon tionnalité étaient fondées sur la théorie des odes et étaient nommées
odes de déte tion de manipulations (MDC pour Manipulation Dete tion Codes ).
Signature éle tronique. Les s hémas de signature éle tronique sont sans au un
doute l'appli ation la plus importante des fon tions de ha hage ryptographiques.
Une signature éle tronique est un équivalent éle tronique d'une signature é rite. Elle
permet de plus, de déte ter si l'information signée a été altérée après sa signature.
Les algorithmes utilisés pour signer des données né essitent des al uls importants et
sont don relativement lents omparativement aux vitesses d'exé ution des fon tions
de ha hage. Aussi, an d'a élérer les pro édures de signature et de véri ation de si-
gnature, on utilise une fon tion de ha hage ryptographique pour al uler l'empreinte
des données à signer et appliquer l'algorithme de signature à ette empreinte.
Prote tion de mots de passe. Une autre des appli ations ourantes des fon tions
de ha hage ryptographiques est la prote tion de mots de passe. Un mot de passe
est une haîne de ara tères utilisée pour authentier l'identité d'un utilisateur ou
autoriser l'a ès aux ressour es d'un système informatique. Il est né essaire de proté-
ger les mots de passe an de les sto ker. Une solution ourante onsiste à ne sto ker
que leur empreinte al ulée en appliquant une fon tion de ha hage ryptographique
à une ombinaison du mot de passe et d'un sel (Salt ).
5
Chapitre 1. Introdu tion
Proto oles d'engagement. Les fon tions de ha hage ryptographiques sont aussi
employées dans les proto oles d'engagement. Un proto ole d'engagement onsiste à
permettre à une partie de s'engager sur une valeur sans divulguer au une informa-
tion sur elle- i ; la valeur engagée étant révélée ultérieurement. Ces proto oles sont
utilisés pour lier des parties à des valeurs d'engagement de façon à e qu'au une des
parties ne puisse tirer à posteriori un avantage inapproprié sur les autres.
1-3.1 Dénition
Une fon tion de ha hage prend omme argument une haîne de bits de longueur
arbitraire nie (le message) et restitue en sortie une haîne de bits de longueur xée :
l'empreinte (ou ha hé), appelée aussi parfois ondensat ou simplement ha hé. Nous
pouvons dé rire une telle fon tion de la façon suivante :
6
1-3. Fon tions de ha hage ryptographiques
La notation {0, 1}∗ désigne l'ensemble des haînes de bits de longueur arbitraire nie
et la
n
notation {0, 1} désigne l'ensemble des haînes de bits de longueur exa tement
n. Cette dénition prend en ompte les deux aspe ts fondamentaux exigés de toute
fon tion de ha hage ( ryptographique ou non) : elle doit permettre d'une part d'ob-
tenir une empreinte de taille réduite et d'autre part être rapide à al uler. Il s'agit
d'une dénition des fon tions de ha hage selon un point de vue algorithmique.
Bellare et Rogaway [BR93℄ ont introduit en 1993 un objet théorique dénommé
ora le aléatoire (Random Ora le ). Un ora le aléatoire est un objet de type boîte
noire, qui répond à haque requête issue de son ensemble de départ par une réponse
aléatoire hoisie uniformément dans son ensemble d'arrivée. Pour un ensemble Dom
et un ensemble ni Rng un ora le aléatoire est déni par une ma hine de Turing
a eptant des entrées X ∈ Dom :
Un ora le aléatoire est dit onsistant, s'il donne systématiquement une réponse
identique pour une même question posée. De plus, on distingue usuellement les ora les
aléatoires à entrée de longueur xe (Fixed Input Length ) qui orrespondent à une
fon tion de
1 idéale, et les ora les aléatoires à entrée de longueur variable
ompression
(Variable Input Length ) qui orrespondent à une fon tion de ha hage idéale.
Un ora le aléatoire onstitue une fon tion de ha hage ryptographique parfaite.
Il vérie toutes les propriétés exigées des fon tions de ha hage ryptographiques. Il
s'agit d'une fon tion aléatoire pour laquelle il n'existe pas d'attaques stri tement
meilleures que les attaques génériques.
1
Nous développerons les fon tions de ompression dans le hapitre onsa ré à la onstru tion
7
Chapitre 1. Introdu tion
8
1-3. Fon tions de ha hage ryptographiques
? 6= ? ? 6= ?
h h h h h
Fig. 1-2 Cette gure illustre les diérents obje tifs d'un adversaire souhaitant
mettre en défaut les propriétés de résistan e aux ollisions, de résistan e au al ul
d'anté édent et de résistan e au al ul de se ond anté édent. Les parties grisées
orrespondent aux éléments qui sont imposés et les points d'interrogation gurent
les messages que doit produire l'adversaire.
domaines d'appli ation né essitent que la fon tion utilisée soit de plus indistinguable
d'une fon tion aléatoire. C'est le as par exemple pour la dérivation de lé et la
génération de nombre pseudo-aléatoires. On parlera alors de fon tion pseudo-aléatoire
(Pseudo Random Fun tion ) pour ara tériser le fait que la sortie de ette fon tion
ne peut être distinguée de elle d'une fon tion purement aléatoire. Le tableau1-1
établit une orrespondan e entre es propriétés et ertains domaines d'utilisation
des fon tions de ha hage ryptographiques introduits pré édemment.
Domaines Propriétés
Col P re Sec P RF
Tab. 1-1 Tableau de orrespondan e entre les propriétés des fon tions de ha hage
ryptographiques et les domaines d'utilisation. Les notations Col, P re, Sec et P RF
désignent respe tivement la résistan e aux ollisions, au al ul d'anté édent, au al ul
de se ond anté édent et le ara tère pseudo-aléatoire. La présen e d'une roix indique
le fait qu'un adversaire mettant en défaut la propriété orrespondante peut être
dire tement utilisé pour invalider l'utilisation de la fon tion dans le domaine. Les
domaines de l'authenti ation de message et des proto oles d'engagement ne sont
pas présent dans e tableau ar les propriétés qui leur orrespondent varient en
fon tion des onstru tions utilisées.
9
Chapitre 1. Introdu tion
On nomme fon tion de ha hage à sens unique (One Way Hash Fun tion ) ou fon -
tion de ha hage à sens unique faible (Weak One Way Hash Fun tion ), une fon tion
de ha hage satisfaisant les propriétés 1.1 et 1.2. On nomme fon tion de ha hage ré-
sistante aux ollisions (CollisionResistant Hash Fun tion ) ou fon tion de ha hage à
sens unique forte (Strong One Way Hash Fun tion ), une fon tion de ha hage satis-
faisant les propriétés 1.1 et 1.3.
Dénitions formelles. Les propriétés que nous avons énon ées ne onstituent pas
des dénitions d'un point de vue rigoureusement formel. Dans es propriétés, nous
utilisons la notion de résistan e optimale. En eet, nous pouvons asso ier à ha une
de es trois propriétés une attaque générique. Notons n la taille, exprimée en nombre
de bits, de la sortie d'une fon tion de ha hage. Pour la résistan e aux ollisions, le
paradoxe des anniversaires montre que l'on peut trouver une ollision ave une om-
plexité de l'ordre de O(2
n/2 ) appels à la fon tion. En e qui on erne la résistan e
au al ul d'anté édent et la résistan e au al ul de se ond anté édent, une re her he
exhaustive de omplexité O(2n ) appels à la fon tion permet d'obtenir l'objet dé-
siré. Ces deux attaques, que nous détaillerons se tion 2-5, sont dites génériques ar
elles fon tionnent quelle que soit la fon tion de ha hage onsidérée. Une fon tion
résiste alors de façon optimale, et est don qualiée de résistante, si au une attaque
stri tement meilleure que l'attaque générique orrespondante n'est onnue.
10
1-4. Bref historique des fon tions de ha hage ryptographiques
11
Chapitre 1. Introdu tion
12
2
Sommaire
2-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . 13
2-2 Fon tion de ompression . . . . . . . . . . . . . . . . . 15
2-2.1 Fon tions de ompression fondées sur un algorithme
de hirement par blo . . . . . . . . . . . . . . . . . . 15
2-2.2 Fon tions de ompression fondées sur un problème ré-
puté di ile . . . . . . . . . . . . . . . . . . . . . . . . 17
2-3 Extenseur de domaine . . . . . . . . . . . . . . . . . . 18
2-3.1 Algorithme de Merkle-Damgård . . . . . . . . . . . . . 18
2-3.2 Autres extenseurs de domaine . . . . . . . . . . . . . . 22
2-4 Autres onstru tions . . . . . . . . . . . . . . . . . . . 23
2-5 Sé urité des onstru tions . . . . . . . . . . . . . . . . 25
2-5.1 Attaques génériques . . . . . . . . . . . . . . . . . . . . 25
2-5.2 Attaques spé iques . . . . . . . . . . . . . . . . . . . . 26
2-5.3 Modèle de l'indiérentiabilité . . . . . . . . . . . . . . 28
13
Chapitre 2. Constru tions lassiques et leur sé urité
Fig. 2-1 Ha hage itératif. Le message est dé oupé en éléments de taille xe qui
sont traités itérativement.
le plus di ile à on evoir. La prin ipale di ulté repose sur le ompromis né essaire
entre vitesse d'exé ution et sé urité. Une fois la fon tion de ompression onstruite,
on applique l'extenseur de domaine qui doit lui-même ne pas introduire de faiblesse
supplémentaire. L'algorithme d'extension de domaine le plus populaire est ertaine-
ment l'algorithme de Merkle-Damgård [Mer89, Dam89℄. Cependant, ave l'intensi-
ation de la re her he sur les fon tions de ha hage ryptographiques, de nouvelles
propositions d'extenseurs de domaine ont vu le jour, parmi lesquelles on peut iter les
éponges ryptographiques [BDP06℄. Bien qu'elles soient les plus utilisées en pratique,
les fon tions itératives ne onstituent pas la seule option possible. D'autres prin ipes
de onstru tions ont été proposés dont les arbres de Merkle [Mer79b℄.
Une attaque ontre une fon tion de ha hage ryptographique est un algorithme
dont le but est de violer une des propriétés de sé urité revendiquée par ette fon tion.
Dans le monde de la ryptologie, il existe diérentes notions pour dénir les attaques.
Une façon de distinguer les types d'attaque onsiste à onsidérer la quantité d'infor-
mation disponible pour un adversaire. Selon e point de vue, nous pouvons diviser les
attaques en deux atégories. Les attaques génériques traitent la fon tion de ha hage
omme une boîte noire (Bla k Box ), et sont indépendantes du type de onstru tion
sur lequel repose la fon tion de ha hage. Par opposition, les attaques spé iques
onsidèrent la fon tion de ha hage omme une boîte blan he (White Box ). Les at-
taques spé iques tirent partie de stru tures parti ulières à l'algorithme utilisé pour
onstruire la fon tion de ha hage. Plusieurs attaques spé iques relatives à l'utilisa-
tion d'un extenseur de domaine et plus parti ulièrement à l'algorithme de Merkle-
Damgård ont été mises en éviden e. Ces attaques permettent de distinguer trivia-
lement une fon tion de ha hage itérative d'une fon tion de ha hage parfaite (ora le
aléatoire). La notion d'indiérentiabilité introduite par Maurer et al. [MRH04℄ en
2004 permet de prendre en ompte l'impa t de l'extenseur de domaine sur la sé urité
d'une fon tion de ha hage.
Dans e hapitre, nous ommen erons par présenter les diérents prin ipes utili-
sés pour la onstru tions de fon tions de ompression avant de détailler l'algorithme
14
2-2. Fon tion de ompression
15
Chapitre 2. Constru tions lassiques et leur sé urité
M Hi M
Hi M Hi
E E E
onstru tion est l'AES [FIPS-AES℄ (Advaned En ryption Standard ) qui a su édé
au DES [FIPS-DES℄ (Data En ryption Standard ) en 2001. La taille des blo s utilisés
par l'AES est de 128 bits (64 pour le DES). Cette taille se révèle insusante pour
résister à l'attaque générique par ollision au vu des ritères de sé urité a tuels. Ces
ritères imposent aux fon tions de ha hage ryptographiques des tailles d'empreinte
de 224/256 bits en ar hite ture 32 bits et 384/512 bits en ar hite ture 64 bits (selon
le ré ent appel d'ore du NIST).
16
2-2. Fon tion de ompression
ISO/IEC 10118-3.
Comme nous l'avons souligné, il est di ile d'évaluer la sé urité des fon tions de
ompression ad ho . Jusqu'en 2005 et bien qu'en ore très employée dans l'industrie, la
fon tion MD5 avait déjà fait l'objet de diérentes attaques [Ber92, DBB91, DBB93,
Dob96a, Dob96b℄. Mais le standard SHA-1 était en ore onsidéré omme sûr. Les
ryptanalyses menées ontre sa version préliminaire SHA-0 [CJ98, BC04℄ ne semblant
pas être dire tement transposables à la version normalisée. Cependant, l'introdu tion
de nouvelles méthodes de ryptanalyses initiée par Wang et al. [WFL04, WLF05,
WYY05a, WYY05b, WYY05 , WYY05d, WY05℄ devaient sonner le glas de pans
entiers des fon tions de ha hage de la famille MD-SHA. Une part importante des
travaux de re her he présentés dans ette thèse on ernant les fon tions SHA-0 et
SHA-1 s'appuient sur es nouvelles méthodes de ryptanalyse. Ces méthodes se sont
montrées si e a es que le NIST a dé idé de lan er une ompétition pour dénir un
nouveau standard de ha hage ryptographique. On peut remarquer que malgré et
in ident, les fon tions ad ho sont toujours très populaires.
17
Chapitre 2. Constru tions lassiques et leur sé urité
problèmes puissent voir le jour dans un avenir pro he. Cela met théoriquement es
fon tions à l'abri d'attaques dévastatri es telles qu'ont pu les onnaître ertaines des
onstru tions ad ho les plus populaires.
Des fon tions de ha hage ryptographiques dont la sé urité repose sur de tels
problèmes ont été proposées [BM97, CJ98, BAC08, AFG08, ADL08℄. Paradoxale-
ment, ertaines d'entre elles ont subit des attaques peu après leur publi ation. En
eet, les fon tions fondées sur es problèmes sont en général peu performantes par
rapport aux fon tions ad ho , e qui a pu onduire ertains on epteurs à proposer
des paramètres sous-dimensionnés. De plus, la dénition des problèmes réputés di-
iles induit souvent qu'ils le sont pour une instan e du problème tirée aléatoirement.
On parle aussi parfois de di ulté en moyenne, e qui désigne le fait que la plupart
des instan es d'un problème sont di iles à résoudre. Cependant il peut aussi exis-
ter des instan es fa iles même pour un problème di ile. Il est malen ontreusement
arrivé que ertaines fon tions de ha hage proposées utilisaient des paramètres onsti-
tuant une instan e fa ile d'un problème. Enn, la onstru tion hoisie pour mettre
en oeuvre le problème algorithmique peut avoir des onséquen es sur la qualité de la
rédu tion de sé urité. Cependant, les quelques é he s de fon tions de ha hage fondées
sur des problèmes réputés di iles ne remettent pas en ause la validité du prin ipe.
18
2-3. Extenseur de domaine
Message à hacher
Message rembourré
x1 x2 xt xt+1
H0 h(x)
f f f f
H1 H2 Ht
H0 = 0n {n bits à 0}
i=1
while i ≤ t + 1 do
Hi = f (Hi−1 k xi )
end while
L'empreinte du message x est alors h(x) = Ht+1 = f (Ht k xt+1 ).
19
Chapitre 2. Constru tions lassiques et leur sé urité
H : K × D → R,
dirons que (Θ, h) est une famille de fon tions de ompression prenant en entrée des
haînes de bits de taille ℓ′ (n).
Pour une famille de fon tions de ha hage H = (Θ, h), un adversaire A et un para-
mètre de sé urité n, nous dénissons l'expérien e suivante :
20
2-3. Extenseur de domaine
tout adversaire probabiliste A polynomial en temps, il existe une fon tion négligeable
g telle que
P r[CollA,H (n) = 1] ≤ g(n)
Nous pouvons dès lors énon er le théorème de Merkle-Damgård :
21
Chapitre 2. Constru tions lassiques et leur sé urité
Il en dé oule que si la famille F est résistante aux ollisions, alors la famille H est
résistante aux ollisions.
Il est important de noter que la ré iproque de e théorème est fausse. Il est tout à
fait possible d'envisager l'existen e de fon tions de ha hage résistantes aux ollisions
onstruites à partir de fon tions de ompression qui ne soient pas résistantes aux
ollisions et dont le domaine est étendu ave l'algorithme de Merkle-Damgård.
22
2-4. Autres onstru tions
Message Haché
p p p p
c
Absorption Essorage
fondée sur une transformation de longueur xe p (plus pré isément une permuta-
tion) à la pla e d'une fon tion de ompression. Une fon tion éponge prend omme
argument en entrée une haîne de bits de longueur variable et produit en sortie une
haîne de bits de longueur arbitraire.
Cette onstru tion opère sur un état onstitué de b=r+c bits, où le nombre r
est appelé taux de bits (Bitrate ) et le nombre la apa ité (Capa ity ). Le message
à traiter est tout d'abord rembourré et dé oupé en blo s de r bits. La onstru tion
éponge pro ède alors en deux étapes :
La apa ité c détermine le niveau de sé urité sus eptible d'être atteint par la fon tion
de ha hage. Une illustration graphique du prin ipe des éponges ryptographiques se
trouve gure 2-4.
Les arguments de sé urité de e type de onstru tion sont fondés sur le modèle
de l'indiérentiabilité (Indierentiability Framework ) qui a été introduit par Maurer
et al. [MRH04℄ et que nous dé rivons se tion 2-5.3. Les auteurs ont montré dans
[BDP08a℄ que si la fon tion p est modélisée en tant que permutation aléatoire ou
en tant qu'ora le aléatoire, la onstru tion éponge est indiérentiable d'un ora le
aléatoire monolithique.
23
Chapitre 2. Constru tions lassiques et leur sé urité
Root Hash
Message
Arbres de Merkle. Les arbres de Merkle ont été introduits par Ralph Merkle en
1979 [Mer79b℄, dans le but de onstruire un s héma de signature éle tronique fondé
sur les fon tions de ha hage. Mais des primitives ryptographiques plus e a es,
fondées sur la théorie des nombres (RSA, DSA, ECC), ont rendu obsolète les arbres
de Merkle pour e domaine d'utilisation. Le prin ipe des arbres de Merkle onsiste à
onstruire un arbre de ha hage à partir d'une fon tion de ha hage et de données. Les
feuilles de l'arbre sont les empreintes des diérents blo s de données ; les noeuds de
l'arbre sont onstitués par les empreintes de leur ls respe tifs. Au sommet de l'arbre,
on trouve l'empreinte ra ine (Root Hash ). Une illustration graphique du prin ipe des
arbres de Merkle se trouve gure 2-5. La plupart des implémentations d'arbre de
Merkle utilisent des arbres binaires, mais le prin ipe peut être étendu aux arbres
q -aires.
Les arbres de Merkle sont intensivement employés dans les réseaux pair à pair
(Peer-to-Peer Networks ). Avant de ommen er le télé hargement d'un hier, l'em-
preinte ra ine est obtenue d'une sour e de onan e : par exemple, le site internet
fournisseur de l'appli ation pair à pair. Lorsque l'empreinte ra ine a été obtenue,
l'arbre de ha hage peut être reçu et vérié à partir de n'importe laquelle des sour es
du réseau. Cet arbre permet de vérier l'intégrité des données au fur et à mesure
de la transmission des diérentes parties d'un hier. Il sut de onnaître le noeud
se situant à la hauteur orrespondante dans l'arbre, pour vérier une sous-bran he
de l'arbre ou un fragment de hier. Un autre avantage des arbres de Merkle réside
dans leur nature parallélisable.
24
2-5. Sé urité des onstru tions
#E1 × #E2
P ≈ 1 − exp .
2n
1
P ≈1− = 0, 63.
e
La omplexité algorithmique d'une telle attaque est don de l'ordre de O(2n/2 ) éva-
luations de la fon tion de ha hage.
Une fon tion de ha hage ryptographique est onsidérée omme assée dès lors
que l'on peut produire une attaque par ollision possédant une omplexité inférieure
à l'attaque du paradoxe des anniversaires.
Attaques par for e brute. Ce type d'attaque on erne les propriétés de résis-
tan e à la re her he d'anté édent et de se ond anté édent. Soit h une fon tion de
∗
ha hage de {0, 1} vers {0, 1}n . L'adversaire tire aléatoirement un message, al ule
son empreinte et vérie si elle- i orrespond à l'empreinte désirée. Si la fon tion de
ha hage se omporte omme une fon tion pseudo-aléatoire, la probabilité de su ès
n
est égale à 1/2 . La probabilité de su ès d'une telle attaque peut être améliorée
en augmentant le nombre de messages tirés. Si l'adversaire al ule l'empreinte de 2n
messages diérents, la probabilité de su ès est approximativement égale à 0, 63.
En pratique, e type d'attaque est parallélisable. De plus, un adversaire peut
onstruire ette attaque simultanément pour un sous-ensemble d'empreintes pos-
sibles, ave pour obje tif de ne trouver qu'un seul anté édent. La omplexité de
l'attaque est alors réduite par la taille du sous-ensemble visé.
De la même façon que pour l'attaque par paradoxe des anniversaires, une fon tion
de ha hage est onsidérée omme assée dès lors qu'il existe une attaque par re her he
d'anté édent, ou de se ond anté édent, possédant une omplexité meilleure que O(2n )
évaluations de la fon tion de ha hage.
25
Chapitre 2. Constru tions lassiques et leur sé urité
doxe des anniversaires nous indique qu'il y a une forte probabilité que deux d'entre
eux onstituent une ollision pour g. Finalement, on obtient une ollision pour la
n+m
fon tion hg ave un oût inférieur à O(2 2 ) évaluations de ette fon tion. Une
illustration de l'attaque des multi- ollisions est proposée gure 2-6.
26
2-5. Sé urité des onstru tions
M1 M2 Mm/2
n H0 H1 H2 Hm/2
′
M1′ M2′ Mm/2
g h
M1 M1′
M2 M2′ M2 M2′
′ ′
Mm/2 Mm/2 Mm/2
Le prin ipe de ette attaque s'appuie sur des messages extensibles (Expandable
Messages ) qui sont des ensembles de messages de longueurs diérentes. Ils sont utili-
sés pour onstruire des messages de taille variable onduisant à une même variable de
haînage avant insertion du blo ontenant le odage de la longueur. On peut onsi-
dérer un message extensible omme une multi- ollision où les messages possèdent un
nombre de blo s diérent, mais onduisent tous à une même variable de haînage.
La omplexité totale est égale à O(k × 2n/2 + 1 + 2n−k+1 ). Le premier terme est
dû à la génération du message extensible, le se ond dé rit la omplexité né essaire
pour trouver un lien entre le message extensible et une des variables de haînage du
message original.
27
Chapitre 2. Constru tions lassiques et leur sé urité
Message initial
Valeur commune de
variable de chaînage
Message extensible
a ompli une étape de pré- al ul, sur une ertaine valeur onstituée par l'empreinte
d'un message publié à posteriori. Plus tard, l'adversaire produit pour tout message,
un suxe on ordant ave et engagement. Le prin ipe de ette attaque repose sur
une stru ture de données pré- al ulée qui permet à 2k séquen es de blo s de mes-
sage de onverger de façon itérative vers la même empreinte. Pour une fon tion de
ha hage fondée sur l'algorithme de Merkle-Damgård, le oût de ette attaque est
n+k
+2 n−k ) (en ligne) évaluations de la fon tion de
de O(2 2 ) (en pré- al ul) et de O(2
ompression.
Lors de l'attaque, l'adversaire s'engage sur une empreinte publique e obtenue à
partir d'un fon tion de ha hage itérative h fondée sur une fon tion de ompression f.
Après la phase d'engagement, un hallenge est proposé sous la forme d'un préxe P
sur lequel l'adversaire ne possède au un ontrle. Il doit alors produire un suxe S
tel que h(P ||S) = e. La valeur e est hoisie spé iquement par l'adversaire après une
phase de pré- al ul. Ce pré- al ul onsiste à enregistrer des variables de haînage à
partir desquelles l'adversaire sait pouvoir atteindre la valeur e. La stru ture de don-
nées utilisée pour enregistrer les variables de haînage est un arbre binaire onstruit à
l'aide d'un algorithme de re her he de ollision. En utilisant par exemple le paradoxe
des anniversaires, on peut réer une stru ture en diamant ave 2k+1 − 2 variables
n+k
+2
de haînage intermédiaires, pour un oût de l'ordre de O(2 2 ) évaluations de la
fon tion de ompression f. Une illustration de la stru ture en diamant est donnée
gure 2-8.
Dans la phase en ligne de l'attaque, l'adversaire re her he de façon exhaustive
un suxe S′ tel que h(P ||S ′ ) forme une ollision ave une des variables de haînage
intermédiaires. Cette étape requiert de tester de l'ordre de O(2
n−k ) valeurs pour S′.
Une fois ette ollision trouvée, l'adversaire peut obtenir à partir de la stru ture en
diamant un message Q, et onstruire le suxe S = S ′ ||Q, de taille k+1 blo s, tel
que h(P ||S) = e.
Andreeva et al.[ABD09, ABF08℄ ont proposé plusieurs extensions et généralisa-
tions pour ette attaque.
28
2-5. Sé urité des onstru tions
e
IV HP 2k
S′ Q
P S
modèle, on donne à toutes les parties impliquées dans le proto ole, y ompris l'ad-
versaire, un a ès à une vraie fon tion aléatoire. Mais une telle fon tion n'existe pas
en pratique. Aussi, lors de la mise en oeuvre du proto ole, ette fon tion aléatoire est
instan iée sous la forme d'une fon tion de ha hage idéale. Les preuves formelles obte-
nues dans le modèle de l'ora le aléatoire indiquent qu'il n'existe pas de défaut stru -
turel dans le design du proto ole. Cependant, de ré ents résultats [CGH98, Nil02℄
montrent qu'il est théoriquement possible de onstruire des as pathologiques qui
sont sûrs dans e modèle mais omplètement non-sûrs dans le modèle standard. Mal-
gré ela, le modèle de l'ora le aléatoire reste un outil essentiel pour le design de
proto oles.
Des her heurs se sont intéressés à l'appli ation du modèle de l'ora le aléatoire
au design de fon tions de ha hage, et plus parti ulièrement aux fon tions de ha hage
itératives. C'est le as de Coron et al. [CDM05℄ qui se sont pen hés sur l'algorithme
de Merkle-Damgård. Pour e faire, ils ont utilisé le modèle de l'indiérentiabilité
(Indierentiability Framework ) introduit par Maurer et al. [MRH04℄ en 2004.
De par sa nature, une fon tion de ha hage itérative est trivialement distinguable
d'un ora le aléatoire, en utilisant par exemple une attaque par extension (dé rite
dans la hapitre suivant). Ce i est dû au fait qu'un ora le aléatoire est une stru ture
monolithique, onstituée d'un seul blo , ontrairement à une fon tion de ha hage
itérative. L'obje tif du modèle de l'indiérentiabilité onsiste don à ontourner e
problème à l'aide d'un simulateur. De façon informelle, pour prouver l'indiéren-
tiabilité d'une onstru tion C fondée sur une primitive idéale F par rapport à un
ora le aléatoire R, S . La fon tion du simulateur S onsiste
on utilise un simulateur
à simuler le omportement de la C , tout en maintenant une onsistan e
onstru tion
ave l'ora le aléatoire R. Dès lors qu'il n'existe pas de distingueur D apable de
distinguer
F R
les sorties des ouples (C , F ) et (R, S ), la onstru tion C est dites in-
diérentiable d'un ora le aléatoire. Une illustration graphique du prin ipe du modèle
de l'indiérentiabilité se trouve gure 2-9.
29
Chapitre 2. Constru tions lassiques et leur sé urité
Simulateur
CF F
R
SR
Distingueur
D
Fig. 2-9 Modèle de l'indiérentiabilité. Les boîtes grisées représentent des primi-
tives idéales, les boîtes vides des algorithmes.
pas de faiblesse stru turelle supplémentaire, lorsqu'il est appliqué à une fon tion de
ompression idéale. Bien qu'introduite ré emment, l'indiérentiabilité est aujourd'hui
une des propriétés formelles que se doivent de posséder les fon tions de ha hage
ryptographiques itératives.
30
Deuxième partie
31
3
Sommaire
3-1 Prin ipe de fon tionnement . . . . . . . . . . . . . . . 33
3-1.1 Extenseur de domaine . . . . . . . . . . . . . . . . . . 33
3-1.2 Fon tion de ompression . . . . . . . . . . . . . . . . . 34
3-2 Sé urité de la fon tion SHA-0 . . . . . . . . . . . . . 36
3-3 Sé urité de la fon tion SHA-1 . . . . . . . . . . . . . 37
Les fon tions de ha hage ryptographiques SHA-0 et SHA-1 ont toutes deux été
rées par l'agen e nationale de sé urité améri aine (National Se urity Agen y ) et
publiées par le NIST en tant que standard fédéral de traitement de l'information
(FederalInformation Pro essing Standard ). Le premier standard baptisé SHA (Se-
ure Hash Standard ) fut adopté en 1993. Cependant en 1995, la NSA demanda une
modi ation de la pro édure d'expansion de message. Cette nouvelle version hérita
de l'appellation SHA-1, et l'an ien standard fût rebaptisé SHA-0.
Dans e hapitre, nous allons dé rire le prin ipe de fon tionnement ommun
aux deux fon tions de ha hage SHA-0 et SHA-1, nous donnerons ensuite un bref
historique de l'évolution de la sé urité de es fon tions relativement aux attaques
par ollisions.
33
Chapitre 3. Présentation des fon tions SHA-0 et SHA-1
A B C D E
Rembourrage (Padding ).
Le rembourrage utilisé pour les fon tions SHA-0 et SHA-1 onsiste à ajouter un
1 après le dernier bit du message puis à ajouter autant de 0 que né essaire an
d'obtenir un nombre entier de blo s de 512 bits, ave la ondition supplémentaire
que les 64 derniers bits du dernier blo ontiennent la représentation binaire de la
taille du message exprimée en nombre de bits. Cette taille est don limitée à un
maximum de 264 − 1 bits. En plus de fournir un nombre entier de blo s de 512 bits
à la fon tion de ompression, e rembourrage permet de garantir qu'au un message
ne puisse onstituer le préxe d'un autre message.
où la notation ⊞ dénote une addition modulo 232 mot de 32 bits par mot de 32 bits.
La fon tion E se fonde sur un état interne mis à jour selon un s héma de Feistel
asymétrique généralisé. Une représentation graphique de ette fon tion se trouve
gure 3-1.
Elle est omposée de 80 pas (4 rondes de 20 pas), haque pas utilise un mot de 32
bitsWi (soit un total de 80 × 32 = 2560 bits) pour mettre à jour 5 registres internes
(A, B, C, D, E) de 32 bits ha un. Étant donné que plus de bits de message que
disponibles sont né essaires, une pro édure d'expansion ré ursive est utilisée pour
générer les bits surnuméraires. La diéren e entre les fon tions SHA-0 et SHA-1
réside dans ette pro édure d'expansion.
Expansion de message.
Tout d'abord, le blo de message ourant Mt est dé oupé en 16 mots de 32
bits numérotés de 0 à 15 : W0 , . . . , W15 . Ces 16 mots sont ensuite étendus selon les
formules suivantes :
34
3-1. Prin ipe de fon tionnement
Ai Bi Ci Di Ei
fi Ki
≪ 30
≪5 Wi−1
Fig. 3-1 Fon tion de mise à jour des registres ommune à SHA-0 et SHA-1.
Tab. 3-2 Fon tions booléènes et onstantes utilisées dans SHA-0 et SHA-1.
où la notation ≪1 signie une permutation ir ulaire de 1 bit vers la gau he. Nous
verrons dans la partie onsa rée aux ryptanalyses de SHA-0 et SHA-1 que ette
modi ation, d'apparen e mineure, a un impa t majeur sur la sé urité et déterminant
sur es ryptanalyses.
Ai+1 = (Ai ≪ 5) + fi (Bi , Ci , Di ) + Ei + Ki + Wi ,
Bi+1 = Ai ,
P ASi+1 : Ci+1 = Bi ≫ 2,
Di+1 = Ci ,
Ei+1 = Di .
où les Ki sont des onstantes de ronde prédéterminées et les fi des fon tions booléènes
dénies table 3-2.
35
Chapitre 3. Présentation des fon tions SHA-0 et SHA-1
Remarque.
On remarque que pour un pas i, les états de tous les registres ne sont que des
opies ir ulairement permutées de diérents états du registre A. On peut don
onsidérer uniquement l'évolution des états du seul registre A pour haque pas. En
onséquen e, il est possible de ré rire la fon tion de mise à jour des registres sous la
forme suivante :
Nous serons amenés dans la suite, à favoriser l'une ou l'autre forme d'é riture de la
fon tion de mise à jour des registres dans l'obje tif de hoisir la plus laire façon de
présenter l'information.
36
3-3. Sé urité de la fon tion SHA-1
37
Chapitre 3. Présentation des fon tions SHA-0 et SHA-1
38
4
Sommaire
4-1 Cryptanalyses diérentielles des fon tions de ha-
hage ryptographiques . . . . . . . . . . . . . . . . . 39
4-2 Modèle des ollisions lo ales . . . . . . . . . . . . . . 40
4-2.1 Approximation linéaire de la fon tion de mise à jour
des registres . . . . . . . . . . . . . . . . . . . . . . . . 40
4-2.2 Fon tion de mise à jour des registres standard . . . . . 45
4-3 Chemin diérentiel . . . . . . . . . . . . . . . . . . . . 46
4-3.1 Ve teur de perturbations . . . . . . . . . . . . . . . . . 46
4-3.2 Masque de perturbations . . . . . . . . . . . . . . . . . 47
4-3.3 Cara téristique linéaire (Linear Chara teristi ). . . . . 48
4-4 Mise en oeuvre du modèle . . . . . . . . . . . . . . . 48
4-4.1 Appro he probabiliste . . . . . . . . . . . . . . . . . . . 49
4-4.2 Appro he déterministe . . . . . . . . . . . . . . . . . . 50
4-4.3 Hypothèse d'indépendan e . . . . . . . . . . . . . . . . 50
4-4.4 Évaluation du omportement d'une ollision lo ale . . 51
39
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
Ai+1 = Ai ≪ 5 ⊕ Bi ⊕ Ci ⊕ Di ⊕ Ei ⊕ Ki ⊕ Wi ,
Bi+1 = Ai ,
P ASi+1 : Ci+1 = Bi ≪ 30,
Di+1 = Ci ,
Ei+1 = Di ,
soit :
40
4-2. Modèle des ollisions lo ales
La se onde hypothèse onsidère que l'on peut intervenir sur les mots de message
étendu Wi indépendamment du pro essus d'expansion dont ils sont issus. Cela permet
d'appliquer simplement, une perturbation à un bit j d'un mot Wi−1 quel que soit le
pas onsidéré i de la fon tion de ompression.
Une fois la perturbation initiale introduite, l'obje tif est alors d'en neutraliser les
eets sur les états des registres. Pour e faire, on pro ède à l'introdu tion de nou-
velles perturbations hoisies spé iquement (des orre tions) sur les mots de message
expansés des pas suivants (Wi , Wi+1 , . . .).
Nous allons à présent détailler pas à pas un exemple de ollision lo ale. Dans une
première appro he, nous emploierons la des ription de la fon tion de mise à jour des
registres utilisant la notation (A, B, C, D, E).
j
Nous introduisons la notationXi an d'indiquer que le bit j du mot de 32 bits X
a subi une perturbation au pas i. Nous hoisissons de dénir la numérotation des
bits d'un mot en ommençant par ae ter le numéro 0 au bit de poids faible, puis
en in rémentant jusqu'au numéro 31 pour le bit de poids fort. Nous remarquons que
les permutations ir ulaires induisent seulement un dépla ement de la position d'un
bit perturbé. On a pour 0 ≤ n ≤ 31 :
Xi ≪ n = Xi ≫ (32 − n)
et
j j+n
Xi ≪ n = Xi ≪ n,
j j−n
Xi ≫ n = Xi ≫ n.
De plus, es permutations n'altèrent pas la dire tion des perturbations. Cette re-
marque est vraie pour des perturbations onsidérées de façon indépendante. Cepen-
dant, ertaines te hniques utilisées lors des ryptanalyses peuvent introduire des per-
turbations altérant plusieurs bits onsé utifs ave des ontraintes spé iques (te h-
niques de ompression de bits par exemple). Dans es as, les permutations ir ulaires
peuvent interagir ave es ontraintes. Elles doivent alors faire l'objet d'un traitement
parti ulier.
41
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
Pas i :
Au pas i, nous introduisons une perturbation
en omplémentant à 1 le bit j de Wi−1 . Nous
obtenons :
j Ai−1 Bi−1 Ci−1 Di−1 Ei−1
Ai = (Ai−1 ≪ 5) ⊕ Bi−1 ⊕ Ci−1 ⊕ Di−1 ⊕
j
Ei−1 ⊕ Wi−1 ⊕ Ki , Ki
Bi = Ai−1 , ≪ 30
Pas i + 1 :
La perturbation du bit j du registre Ai devrait
être réper utée au pas i + 1 sur le bit j + 5 de
Ai+1 ainsi que sur le bit j de Bi+1 . Or on Ai Bi Ci Di Ei
obtient :
j j+5
Ai+1 = (Ai ≪ 5) ⊕ Bi ⊕ Ci ⊕ Di ⊕ Ei ⊕ Wi ⊕ Ki+1
Ki+1 , ≪ 30
j j
Bi+1 = Ai , ≪5 Wi
Ci+1 = Bi ≪ 30,
Di+1 = Ci ,
Ei+1 = Di . Ai+1 Bi+1 Ci+1 Di+1 Ei+1
En omplémentant à 1 le bit j + 5 de Wi
on orrige la perturbation réée par le terme
j
(Ai ≪ 5) et don Ai+1 n'est pas altéré.
Pas i + 2 :
Au pas i + 2, la perturbation du bit j de Bi+1
se transmet au bit j + 30 de Ci+2 . On a :
j
Ai+1 Bi+1 Ci+1 Di+1 Ei+1
Ai+2 = (Ai+1 ≪ 5) ⊕ Bi+1 ⊕ Ci+1 ⊕ Di+1 ⊕
j
Ei+1 ⊕ Wi+1 ⊕ Ki+2 , Ki+2
≪ 30
Bi+2 = Ai+1 ,
j+30 j ≪5 Wi+1
Ci+2 = Bi+1 ≪ 30,
Di+2 = Ci+1 ,
Ei+2 = Di+1 . Ai+2 Bi+2 Ci+2 Di+2 Ei+2
De la même façon qu'au pas i + 1, on orrige
j
la perturbation introduite par le terme Bi+1
en omplémentant à 1 le bit j de Wi+1 .
42
4-2. Modèle des ollisions lo ales
Pas i + 3 :
La perturbation du bit j +30 de Ci+2 se trans-
met au bit j + 30 de Di+3 . On a : Ai+2 Bi+2 Ci+2 Di+2 Ei+2
j+30
Ai+3 = (Ai+2 ≪ 5) ⊕ Bi+2 ⊕ Ci+2 ⊕ Di+2 ⊕
j+30 Ki+3
Ei+2 ⊕ Wi+2 ⊕ Ki+3 , ≪ 30
Bi+3 = Ai+2 , ≪5 Wi+2
Ci+3 = Bi+2 ≪ 30,
j+30 j+30
Di+3 = Ci+2 ,
Ei+3 = Di+2 . Ai+3 Bi+3 Ci+3 Di+3 Ei+3
j
On orrige la perturbation issue du terme Ci+2
en omplémentant à 1 le bit j + 30 de Wi+2 .
Pas i + 4 :
On a :
j+30
Ai+4 = (Ai+3 ≪ 5) ⊕ Bi+3 ⊕ Ci+3 ⊕ Di+3 ⊕ Ai+3 Bi+3 Ci+3 Di+3 Ei+3
j+30
Ei+3 ⊕ Wi+3 ⊕ Ki+4 ,
Ki+4
Bi+4 = Ai+3 ,
≪ 30
Ci+4 = Bi+3 ≪ 30,
≪5 Wi+3
Di+4 = Ci+3 ,
j+30 j+30
Ei+4 = Di+3 .
La perturbation du bit j +30 de Di+3 se trans- Ai+4 Bi+4 Ci+4 Di+4 Ei+4
met au bit j + 30 de Ei+4 . La orre tion de
j+30
Di+3 s'ee tue en omplémentant à 1 le bit
j + 30 de Wi+3 .
Pas i + 5 :
On a : Ai+4 Bi+4 Ci+4 Di+4 Ei+4
Ai+5 = (Ai+4 ≪ 5) ⊕ Bi+4 ⊕ Ci+4 ⊕ Di+4 ⊕
j+30 j+30 Ki+5
Ei+4 ⊕ Wi+4 ⊕ Ki+5 , ≪ 30
Bi+5 = Ai+4 ,
≪5 Wi+4
Ci+5 = Bi+4 ≪ 30,
Di+5 = Ci+4 ,
Ei+5 = Di+4 .
Ai+5 Bi+5 Ci+5 Di+5 Ei+5
La dernière orre tion onsiste à omplémen-
ter à 1 le bit j + 30 de Wi+4 .
43
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
Pas i + 6 : Ki+6
≪ 30
Au pas i + 6, les états des registres sont les
mêmes que s'il n'y avait pas eu de perturba- ≪5 Wi+5
tion. La perturbation initiale a été entièrement
orrigée par les perturbations suivantes.
Ai+6 Bi+6 Ci+6 Di+6 Ei+6
On peut aussi dé rire le déroulement d'une ollision lo ale en fon tion du seul
registre A :
j j
Ai = (Ai−1 ≪ 5) ⊕ Ai−2 ⊕ Ai−3 ≫ 2 ⊕ Ai−4 ≫ 2 ⊕ Ai−5 ≫ 2 ⊕ Ki ⊕ Wi−1
j+5 j+5
Ai+1 = (Ai ≪ 5) ⊕ Ai−1 ⊕ Ai−2 ≫ 2 ⊕ Ai−3 ≫ 2 ⊕ Ai−4 ≫ 2 ⊕ Ki+1 ⊕ Wi
j j
Ai+2 = (Ai+1 ≪ 5) ⊕ Ai ⊕ Ai−1 ≫ 2 ⊕ Ai−2 ≫ 2 ⊕ Ai−3 ≫ 2 ⊕ Ki+2 ⊕ Wi+1
j + 30 j + 30
Ai+3 = (Ai+2 ≪ 5) ⊕ Ai+1 ⊕ Ai ≫ 2 ⊕ Ai−1 ≫ 2 ⊕ Ai−2 ≫ 2 ⊕ Ki+3 ⊕ Wi+2
j + 30 j + 30
Ai+4 = (Ai+3 ≪ 5) ⊕ Ai+2 ⊕ Ai+1 ≫ 2 ⊕ Ai ≫ 2 ⊕ Ai−1 ≫ 2 ⊕ Ki+4 ⊕ Wi+3
j + 30 j + 30
Ai+5 = (Ai+4 ≪ 5) ⊕ Ai+3 ⊕ Ai+2 ≫ 2 ⊕ Ai+1 ≫ 2 ⊕ Ai ≫ 2 ⊕ Ki+5 ⊕ Wi+4
44
4-2. Modèle des ollisions lo ales
45
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
Ei = Di−1 .
ave
fi = IF pour i ∈ {1, . . . , 20} (ronde 1),
fi = XOR pour i ∈ {21, . . . , 40} ∪ {61, . . . , 80} (rondes 2 et 4),
fi = M AJ pour i ∈ {41, . . . , 60} (ronde 3).
On peut tout d'abord remarquer que pour les rondes 2 et 4, la fon tion fi utilisée étant
la fon tion XOR, on se ramène à la version linéaire de la fon tion de mise à jour des
registres. En onséquen e, pour la version standard de la fon tion de mise à jour des
registres, le omportement que nous avons détaillé ne sera ae té que par l'addition
modulo 232 pour es deux rondes. Pour les rondes 1 et 3, les fon tions utilisées sont
respe tivement la fon tion IF et la fon tion M AJ et es deux fon tions ne sont pas
linéaires. Elles possèdent la parti ularité de pouvoir absorber une perturbation : une
perturbation présente sur un bit d'un de leurs arguments peut ne pas être réper utée
sur la sortie de la fon tion. Ce omportement est sus eptible d'altérer le hemin
diérentiel de telle sorte qu'il soit impossible d'obtenir une ollision lo ale : nous
parlerons alors de hemin diérentiel impossible. De plus, si l'on onsidère la dire tion
d'une perturbation, ha une de es trois fon tions est sus eptible de modier la
dire tion d'une perturbation, e qui peut invalider les mé anismes de ompensation
des perturbations.
46
4-3. Chemin diérentiel
V = (V0 , . . . , V79 ),
j
(2 )x si et seulement si on initie
une perturbation lo ale sur
Cette ondition n'est né essaire que dans le as où l'on re her he une ollision sur une
seule itération de la fon tion de ompression. Si l'on souhaite aboutir à une quasi-
ollision, par exemple dans le but d'utiliser la te hnique des ollisions multiples, on
peut s'aran hir de ette ontrainte.
P = (P0 , . . . , P79 ),
ave pour i = 0, . . . , 79,
Pi = Vi ⊕ (Vi−1 ≪ 5) ⊕ Vi−2 ⊕ (Vi−3 ≫ 2) ⊕ (Vi−4 ≫ 2) ⊕ (Vi−5 ≫ 2).
47
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
On remarque que pour les inq indi es négatifs il s'agit de perturbations vir-
tuelles. Bien qu'au une perturbation ne puisse réellement exister avant le premier
pas de la fon tion de ompression, on prend en ompte les indi es négatifs pour la
onstru tion du masque de perturbations. Des oordonnées non nulles sur les inq
premiers Pi seront alors interprétées omme des orre tions de perturbations vir-
tuelles. Dans la littérature onsa rée, e phénomène est dénommé ollisions lo ales
tronquées (Trun ated Lo al Collisions ). Compte tenu de ette remarque, il est fa ile
de voir que la donnée des oordonnées (V0 , . . . , V15 ) dénit omplètement le masque
de perturbations.
48
4-4. Mise en oeuvre du modèle
j
P r[IF (X, Y, Z) = IF (X, Y, Z)] = 1/2,
j
P r[IF (X, Y, Z) = IF (X, Y , Z)] = 1/2,
j
P r[IF (X, Y, Z) = IF (X, Y, Z)] = 1/2,
j j
P r[IF (X, Y, Z) = IF (X, Y , Z)] = 1/2,
j j
P r[IF (X, Y, Z) = IF (X, Y, Z)] = 1/2,
j j
P r[IF (X, Y, Z) = IF (X, Y , Z)] = 0,
j j j
P r[IF (X, Y, Z) = IF (X, Y , Z)] = 1/2.
Et le omportement de la fon tion XOR, quant à lui s'é rit :
j
P r[XOR(X, Y, Z) = XOR(X, Y, Z)] = 0,
j
P r[XOR(X, Y, Z) = XOR(X, Y , Z)] = 0,
j
P r[XOR(X, Y, Z) = XOR(X, Y, Z)] = 0,
j j
P r[XOR(X, Y, Z) = XOR(X, Y , Z)] = 1,
j j
P r[XOR(X, Y, Z) = XOR(X, Y, Z)] = 1,
j j
P r[XOR(X, Y, Z) = XOR(X, Y , Z)] = 1,
j j j
P r[XOR(X, Y, Z) = XOR(X, Y , Z)] = 0.
On remarque que es probabilités re ouvrent tous les as possibles ar nous avons
aaire à des fon tions qui n'entrela ent pas les bits (fon tions bit à bit). La fon tion
IF se omporte omme la fon tion XOR ave une probabilité égale à 1/2 sauf pour
le as où X et Y sont modiés simultanément sur la même position de bit. Alors, la
fon tion IF ne se omportera jamais omme la fon tion XOR, e qui onstitue un
exemple de hemin diérentiel impossible.
Le prin ipe d'une attaque diérentielle fondée sur une appro he probabiliste
onsistera don à éviter les hemins diérentiels impossibles et à évaluer la probabi-
lité de bon omportement pour ha une des fon tions IF et M AJ , et pour haque
ollision lo ale dénie par le ve teur de perturbations. Une fois e travail réalisé, on
peut évaluer la omplexité de l'attaque omme une fon tion de l'inverse du produit
de toutes es probabilités.
49
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
if (x, y, z) = if (¬x, y, z) si y = z,
= ¬if (¬x, y, z) si y = ¬z,
= if (x, ¬y, z) si x = 0,
= ¬if (x, ¬y, z) si x = 1,
= if (x, y, ¬z) si x = 1,
= ¬if (x, y, ¬z) si x = 0,
6= if (x, ¬y, ¬z) dans tous les as.
Le prin ipe d'une attaque diérentielle fondée sur l'appro he déterministe onsiste
don à énumérer toutes les onditions susantes pour que les fon tions de rondes
aient un omportement en adéquation ave le modèle de ollision lo ale. On évalue
alors la omplexité de l'attaque omme une fon tion du nombre total de onditions
à vérier.
50
4-4. Mise en oeuvre du modèle
j j
Ai+1 = (Ai ≪ 5) + IF (Ai−1 , Ai−2 ≫ 2 , Ai−3 ≫ 2) + Ai−4 ≫ 2 + Ki + Wi
j+5 j+5
Ai+2 = (Ai+1 ≪ 5) + IF (Ai , Ai−1 ≫ 2 , Ai−2 ≫ 2) + Ai−3 ≫ 2 + Ki+1 + Wi+1
j j
Ai+3 = (Ai+2 ≪ 5) + IF (Ai+1 , Ai ≫ 2 , Ai−1 ≫ 2) + Ai−2 ≫ 2 + Ki+2 + Wi+2
j + 30 j + 30
Ai+4 = (Ai+3 ≪ 5) + IF (Ai+2 , Ai+1 ≫ 2 , Ai ≫ 2) + Ai−1 ≫ 2 + Ki+3 + Wi+3
j + 30 j + 30
Ai+5 = (Ai+4 ≪ 5) + IF (Ai+3 , Ai+2 ≫ 2 , Ai+1 ≫ 2) + Ai ≫ 2 + Ki+4 + Wi+4
j + 30 j + 30
Ai+6 = (Ai+5 ≪ 5) + IF (Ai+4 , Ai+3 ≫ 2 , Ai+2 ≫ 2) + Ai+1 ≫ 2 + Ki+5 + Wi+5
1. Pour que la première des 6 équations que nous venons d'é rire soit vériée, il
sut que la transmission de la perturbation introduite au mot Wi se fasse sans
retenue. Cette ondition est vériée ave une probabilité égale à 1/2 si l'on
onsidère l'angle probabiliste et orrespond à la ondition ai+1,j = wi,j selon
le point de vue déterministe.
3. La troisième équation voit l'apparition de l'a tion de la fon tion de ronde. Pour
que ette équation soit vraie, il sut que dans un premier temps la perturbation
présente sur le registre Ai+1 ne soit pas absorbée par la fon tion de ronde. Puis
dans un se ond temps, la perturbation issue de la sortie de la fon tion IF et
la orre tion introduite par le mot Wi+2 doivent se ompenser. Si nous nous
ramenons aux des riptions du omportement de la fon tion IF données aux
se tions pré édentes, nous onstatons que dans le as qui nous intéresse (il
existe une perturbation sur un bit du premier argument de la fon tion), d'un
point de vue probabiliste la fon tion se omportera de façon identique à la
51
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
fon tion XOR ave une probabilité égale à 1/2. Du point de vue déterministe,
si la ondition ai,j+30 6= ai−1,j+30 est vériée alors la perturbation ne sera pas
absorbée. Cependant, la fon tion IF peut préserver ou inverser la dire tion de
la perturbation e qui peut ompromettre la ompensation des perturbations,
même si une ontrainte onsistant à imposer que la orre tion introduite sur
le bit j de Wi+2 soit de dire tion opposée à la dire tion de la perturbation
introduite sur le bit j de Wi est utilisée. Il existe alors deux solutions pour
traiter le problème :
ne pas imposer de ontrainte sur la dire tion de la perturbation du bit j
de Wi+2 et onsidérer une probabilité supplémentaire de 1/2 pour que la
fon tion IF préserve la dire tion,
imposer la wi+2,j = ¬wi,j
ontrainte et transformer la ondition déterministe
en ai,j+30 6 ai−1,j+30 = 1.
=
Finalement, la troisième équation est vériée ave une probabilité égale à 1/4
ou si la double ondition ai,j+30 6= ai−1,j+30 = 1 est vériée.
Type -------------------------o------
0 1 2, . . . , 30 31
IF 5 (5) 5 (5) 5 (5) 4 (4)
XOR 4 (4) 2 (2) 4 (4) 3 (3)
M AJ 4 (4) 2 (2) 4 (4) 4 (4)
On peut remarquer que les appro hes que nous avons hoisi de qualier de proba-
biliste et déterministe se rejoignent, les onditions utilisées dans l'appro he détermi-
niste possédant une ertaine probabilité d'être vériées, égale à 1/2 dans l'hypothèse
où les bits des diérents états des registres sont onsidérés omme étant aléatoires.
52
4-4. Mise en oeuvre du modèle
53
Chapitre 4. Prin ipe des ryptanalyses de SHA-0 et SHA-1
54
5
Cryptanalyses pratiques
Sommaire
5-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . 55
5-2 Opérateur de diéren e . . . . . . . . . . . . . . . . . 56
5-2.1 Diéren e binaire . . . . . . . . . . . . . . . . . . . . . 56
5-2.2 Diéren e binaire signée . . . . . . . . . . . . . . . . . 57
5-2.3 Diéren e généralisée . . . . . . . . . . . . . . . . . . . 58
5-3 Cara téristique linéaire . . . . . . . . . . . . . . . . . 58
5-3.1 Contraintes et as pathologiques . . . . . . . . . . . . . 59
5-3.2 Re her he de ve teurs de perturbations pour SHA-0 . . 60
5-3.3 Ve teurs de perturbations pour SHA-1 . . . . . . . . . 62
5-3.4 Instantiation du ve teur de perturbation . . . . . . . . 64
5-4 Cara téristique non-linéaire . . . . . . . . . . . . . . . 65
5-4.1 Appro he de Wang et al. . . . . . . . . . . . . . . . . . 66
5-4.2 Appro he de De Cannière et al. . . . . . . . . . . . . . 69
5-5 Te hnique des blo s multiples . . . . . . . . . . . . . 72
5-5.1 Prin ipe de la te hnique des blo s multiples. . . . . . . 73
5-5.2 Attaque de Biham et al. . . . . . . . . . . . . . . . . . 74
5-5.3 Forme a tuelle . . . . . . . . . . . . . . . . . . . . . . . 76
5-5.4 Attaque de Wang et al. . . . . . . . . . . . . . . . . . . 76
5-6 Te hniques d'a élération de re her he de messages 77
5-6.1 Bits neutres . . . . . . . . . . . . . . . . . . . . . . . . 78
5-6.2 Modi ations de message . . . . . . . . . . . . . . . . . 81
5-6.3 Boomerangs . . . . . . . . . . . . . . . . . . . . . . . . 83
55
Chapitre 5. Cryptanalyses pratiques
Nous présentons es opérateurs se tion 5-2. L'étape suivante onsiste à trouver une
ara téristique linéaire sus eptible de onduire de façon e a e à une ollision. La
re her he d'une telle ara téristique se fonde sur l'obtention de bons ve teurs de per-
turbations. Cet aspe t est une première fois abordé se tion 5-3 puis développé dans
le hapitre 7. Il s'avère ependant, que les ve teurs de perturbations les plus promet-
teurs induisent des ollisions tronquées. Un nouvel outil s'est alors révélé né essaire
an d'adapter la ryptanalyse à es ve teurs. Pour e faire, la notion de ara téris-
tique non-linéaire a été introduite. Nous présentons ette notion se tion 5-4. Ave le
développement de es outils, la te hnique des blo s multiples a pu être utilisée an
d'améliorer l'attaque. Nous dé rivons deux as d'utilisation de ette te hnique dans
la se tion 5-5.
Une fois l'opérateur de diéren e déni, la ara téristique linéaire trouvée et
la ara téristique non-linéaire onstruite, la dernière étape onsiste à re her her un
ouple de messages formant une ollision. Des te hniques d'a élération de re her he
ont été développées an de mener e a ement ette re her he, nous les dé rivons
se tion 5-6.
∆⊕ (X, Y ) = X ⊕ Y.
La diéren e binaire est une diéren e simple qui fournit peu d'information. Cepen-
dant dans leur arti le, Chabaud et Joux ont introduit la notion de dire tion pour
une diéren e, elle- i peut être montante ou des endante. Pour un ouple de
′
message expansés (W, W ) ave W′ =W ⊕ 2j , la diéren e est dite montante si le bit
j de W est égal à 0, des endante sinon. Ces deux notions fournissent une information
supplémentaire au ryptanalyste et prégurent la diéren e binaire signée.
56
5-2. Opérateur de diéren e
Dans le adre d'une ryptanalyse diérentielle les deux valeurs à onsidérer sont
souvent notées x et x′ . Nous emploierons dès lors la notation δx pour désigner δ(x, x′ ).
Nous pouvons à présent dénir la diéren e binaire signée de la façon suivante :
Cet exemple illustre lairement la apa ité de la fon tion if à absorber une diéren e
(δif (x, y, z) =0 si y = z ), à en préserver la dire tion (δif (x, y, z) = +δx si y = ¬z =
1) ou à en inverser la dire tion (δif (x, y, z) = −δx si y = ¬z = 0).
La diéren e binaire signée s'intègre don parfaitement à l'appro he déterministe
en intégrant l'information supplémentaire liée au signe de la diérentielle introduite.
Le ryptanalyste possède ave et outil un ontrle relatif sur le déroulement du
hemin diérentiel.
57
Chapitre 5. Cryptanalyses pratiques
(x, x′ ) (0, 0) (1, 0) (0, 1) (1, 1) (x, x′ ) (0, 0) (1, 0) (0, 1) (1, 1)
? X X X X 3 X X - -
- X - - X 5 X - X -
x - X X - 7 X X X -
0 X - - - A - X - X
u - X - - B X X - X
n - - X - C - - X X
1 - - - X D X - X X
# - - - - E - X X X
Fig. 5-1 Notations utilisées dans [DCR06℄ pour représenter les diérents états
possibles pour un ouple de bits x et x′ .
58
5-3. Cara téristique linéaire
pas ∇ Ai ∇W i
... ...
i−1 -------------------------------- --------------------------------
i -------------------------------- ------------------------------u-
i+1 ------------------------------u- -------------------------n------
i+2 -------------------------------- ------------------------------n-
i+3 -------------------------------- x-------------------------------
i+4 -------------------------------- x-------------------------------
i+5 -------------------------------- x-------------------------------
i+6 -------------------------------- --------------------------------
... ...
Fig. 5-2 Cara téristique linéaire orrespondant à une ollision lo ale initiée au pas
i et à la position j = 1. La olonne de droite représente les diérents états des mots
de message expansés. Elle rend ompte du fait que la ollision insérée est de dire tion
des endante selon la terminologie de [CJ98℄, de signe négatif selon la terminologie
asso iée à la diéren e binaire signée. La olonne de gau he représente les diérents
états du registre A.
59
Chapitre 5. Cryptanalyses pratiques
devaient êtres évitées, ar leur prise en harge né essite l'utilisation d'une ara téris-
tique non-linéaire qui a été introduite postérieurement à es attaques. An d'éviter
les ollisions tronquées, une ontrainte supplémentaire est imposée au ve teur de
perturbations.
La relation de ré urren e réé un entrela ement des ollisions lo ales. Cet en-
trela ement peut onduire dans ertains as à des omportements parti uliers, par
exemple un hemin diérentiel impossible. Nous désignons es as parti uliers par le
terme de as pathologiques. Un ertain nombre de as pathologiques ont été iden-
tiés dans la littérature. Les premiers ont été exhibés par Chabaud et Joux dans
leur arti le de 1998. Ils on ernent les ollisions lo ales onsé utives se déroulant lors
de la ronde IF et de la ronde M AJ . En eet, deux ollisions lo ales onsé utives
positionnées sur le même bit se déroulant dans une de es deux rondes onduisent
à un hemin diérentiel impossible. Pour la fon tion IF , ela a onduit les auteurs
à imposer au ve teur de perturbations de ne pas présenter deux ollisions lo ales
onsé utives lors des 16 premiers pas de la fon tion de mise à jour des registres.
Remarquons, que ette ontrainte héritée des premières attaques ontre la fon tion
SHA-0, est devenue aduque ave l'utilisation des ara téristiques non-linéaires. Pour
la fon tion M AJ , le problème est résolu en imposant des dire tions opposées aux
perturbations onsé utives apparaissant entre les pas 36 et 55. Nous avons mené
une évaluation statistique des probabilités de bon omportement des ollisions lo-
ales dans [Man10℄. Cette étude a fait apparaître de nouveaux as pathologiques
jusqu'alors non répertoriés.
Un autre as pathologique est l'eet de propagation de la retenue (Carry Ee t )
qui permet de ompresser ou d'étendre des ollisions lo ales adja entes (démar-
rant au même pas sur des positions de bits onsé utives). Cet eet peut faire l'objet
d'un ontrle de l'attaquant. Il est d'ailleurs un des éléments prin ipaux mis en
oeuvre an de onstruire la ara téristique non-linéaire utilisée dans [WYY05d℄.
60
5-3. Cara téristique linéaire
01000100100100111011 00110000111110000000
00000011000000110110 00000110001011011000
10000000000011000000 11011000000110001011
00101100100000000001 11010011101000010001
11100000000000110000 00110110000001100010
61
Chapitre 5. Cryptanalyses pratiques
sée. La omplexité de l'attaque asso iée est évaluée à 239 évaluations de la fon tion
de ompression.
01000001000000000100 11001101011101000000
00101000101001011001 11000010101010010100
62
5-3. Cara téristique linéaire
Fig. 5-7 Illustration de la diusion des positions des ollisions lo ales pour la
fon tion SHA-1. Cette gure orrespond à l'insertion d'une unique perturbation sur
le premier bit du premier mot du message.
Cette appro he onsiste à dénir une fenêtre au sein de laquelle les possibilités de
positionnement des perturbations initiales sont limitées aux positions de bit 0 et 1.
Cette restri tion est dire tement issue du fait que la meilleure probabilité théorique
de bon omportement pour une ollision lo ale est attendue à la position 1. La taille
de l'espa e de re her he est alors égale à 65 × 232 . Le même prin ipe de restri tion de
l'espa e de re her he est utilisée dans les travaux de Yajima et al. [YIN08℄, ave une
extension à la position de bit 31. La taille de l'espa e de re her he onsidéré étant
alors égale à 65 × 248 .
Nous avons proposé dans [Man09, Man10℄ un nouvel algorithme de re her he
fondé sur l'utilisation d'une fenêtre d'information et d'un ompromis diérent. Ce
ompromis onsiste à relâ her les ontraintes imposées sur les positions de bit où sont
insérées les ollisions lo ales, pour la rempla er par une ontrainte sur le nombre de
ollisions lo ales autorisées dans la fenêtre d'information. Cet algorithme détaillé au
hapitre 7 se tion 7-2, fournit de bons résultats et est à l'origine de la lassi ation
des ve teurs de perturbations e a es.
63
Chapitre 5. Cryptanalyses pratiques
5-3.3.4 Remarques
Contrairement à la façon dont nous avions pro édé pour les ve teurs de pertur-
bations pour SHA-0, nous ne présentons pas i i les diérents ve teurs proposés pour
les ryptanalyses. Dans le hapitre 7 onsa ré à l'amélioration de la ara téristique
linéaire, nous présentons un travail de synthèse qui établit une lassi ation des
ve teurs de perturbations et fournit une étude omparative des diérents ve teurs
proposés dans la littérature. Ces travaux ont fait l'objet d'une présentation lors de
la onféren e WCC 2009 [Man09℄.
Nous remarquons de plus, que les méthodes d'évaluations publiées à e jour
prennent en ompte de façon limitée les possibles intera tions liés à l'en hevêtre-
ment des ollisions lo ales. Nous avons mené dans le adre de ette thèse un ertain
nombre d'expérimentations sur es intera tions. Ces expérimentations ont mis à jour
un ertain nombre de omportements qui onduisent à réévaluer les heuristiques uti-
lisées jusqu'i i pour la re her he de ve teurs de perturbations. Une partie de es
expérimentations est publiée dans [Man10℄ et présentée au hapitre 8.
Enn une dernière remarque porte sur le fait que l'évaluation des ve teurs de per-
turbations peut ne pas onstituer à elle seule une mesure susante pour mener à bien
une ryptanalyse. En eet, les outils utilisés pour onstruire une ryptanalyse ontre
SHA-0 ou SHA-1 peuvent se omporter diéremment pour des ve teurs possédant
une même évaluation. Nous avons été onfrontés à e problème lors de la re her he
de ollision pour SHA-0 que nous avons réalisée ave Thomas Peyrin [MP08℄. Lors de
la onstru tion de la ara téristique non-linéaire, des ve teurs équivalents en terme
d'évaluation onduisaient à des ara téristiques non-linéaires de pertinen es dié-
rentes.
64
5-4. Cara téristique non-linéaire
un ouple de message (M, M ′ ) andidat pour une re her he de ollision doit vérier
plusieurs niveaux de ontraintes linéaires :
une diéren e binaire relativement au masque de perturbations M ′ = M ⊕ P,
une diéren e binaire signée pour spé ier la dire tion de ertaines ollisions
lo ales an d'éviter de possibles as pathologiques,
des équations liant ertains bits des mots de message expansés pour permettre
un bon omportement des ollisions lo ales.
Ces ontraintes apparaissent sur les mots de message expansés, mais l'expansion
étant linéaire, on peut fa ilement se ramener à un système d'équation devant être
vérié par le ouple (M, M ′ ). L'impa t de es équations est plus parti ulièrement
per eptible lors de l'utilisation d'une ara téristique non-linéaire qui doit expressé-
ment tenir ompte de es équations. Les te hniques d'a élération de re her he qui
utilisent des diéren es auxiliaires, omme les boomerangs, doivent aussi s'assurer
d'être ompatibles ave es équations.
L'ensemble des ryptanalyses de SHA-0 et de SHA-1 publiées à e jour impose
uniformément la même dire tion pour l'ensemble des ollisions lo ales, à l'ex eption
des as pathologiques identiés. Cependant, les travaux menés lors de ette thèse
onduisent à re onsidérer e hoix uniforme des dire tions. Nous reviendrons sur e
point au hapitre 8.
65
Chapitre 5. Cryptanalyses pratiques
Cette propriété appliquée à un mot binaire, permet d'étendre une perturbation sur
un bit d'indi e j à des bits d'indi es supérieurs sans modier la valeur arithmétique
asso iée à e mot. Soit X un mot de 32 bits, posons :
X ′ = X + 24 , et
X = X − 2 − 25 − 26 + 27 .
′′ 4
66
5-4. Cara téristique non-linéaire
diéren e, ou bien ompresser plusieurs diéren es en une seule. C'est sur ette
observation que repose le prin ipe de la ompression de bits.
Voi i un autre exemple d'appli ation de ette propriété. Soient X, Y et Z trois
mots de 32 bits, et posons W = X + Y + Z. Soient X ′, Y ′ et Z′ dénis de la façon
suivante :
X ′ = X + 26 ,
Y ′ = Y + 26 ,
Z ′ = Z − 27 ,
On obtient alors :
X ′ + Y ′ + Z ′ = W = X + Y + Z.
Si nous onsidérons que ette équation reète le même type d'équations vériées
par la fon tion de mise à jour des registres, nous pouvons formuler ette équa-
tion diéremment. Les trois diérentielles ∆± (X, X ′ ) = [+6], ∆± (Y, Y ′ ) = [+6]
et ∆± (Z, Z ′ ) = [−7] se sont ompensées. On a don orrigé une perturbation des-
endante sur la position de bit 6 de Z par la ombinaison de deux perturbations
montantes sur la position de bit 7 de X et de Y .
La ombinaison de la diéren e binaire signée et de l'eet de propagation de
la retenue permet de mieux visualiser la propagation des perturbations dans les
registres, et ore aussi des possibilités supplémentaires (extension ou ompression de
diéren es) pour ontrler es perturbations.
[+2,−10,−12,−17,−18,+19] [+10,−11,+12,+13,−14,−17,...,−26,+27]
A3 = (A2 ≪ 5) +
[−2,−7,−8,+9,−32]
IF ( A1 , A0 ≪ 30, B0 ≪ 30)+
[+2,+7,−32]
(C0 ≪ 30) + W2 + Ki
[+2, −10, −12, +17] =[−10, −12, +17] + IF ([−2, −7, −8, +9, −32])+
[+2, +7, −32]
67
Chapitre 5. Cryptanalyses pratiques
ait un sens d'un point de vue arithmétique, la diéren e en sortie de la fon tion IF
doit valoir [−7, ±32], e qui orrespond au omportement suivant :
1. absorber les valeurs −2, −8 et +9 de la diéren e [−2, −7, −8, +9, −32],
2. préserver le signe de la valeur −7,
3. préserver la valeur −32, mais sans for ément en onserver le signe.
Le omportement 1 sera a quis dès lors que les b0,4 = a0,4 , b0,10 = a0,10
onditions
et b0,10 = a0,11 portant sur les bits des valeurs initiales B0 et A0 seront vériées. Le
omportement 2 né essite quant à lui que les équations a0,9 = 1 et b0,9 = 0 soient
vraies. Le omportement 3 impose la ondition b0,2 = ¬a0,2 . Cet exemple illustre le
fait que la fon tion IF permet, au prix de onditions supplémentaires, d'intervenir
dire tement sur la propagation des diéren es au sein des registres.
Ave l'aide des outils que nous venons de présenter, Wang et al. sont parvenus à
onstruire la ara téristique non-linéaire présentée table 5-1.
Conditions
Registres 31 - 24 23 - 16 15 - 8 7 - 0
A0 - - - -- - - - 1 - 1100 - 1 - -1- -1 -1 10 - - - - - -
B0 - - - -- - - - -------- - - - - - aa0 - - - - a - ā-
A1 1- - -- - - - 0a0011a0 aa1 - 10a0 11 - - - - 1-
A2 0-0-- - - - - - 011111 111111 - 1 0010a - - -
A3 1-1--aaa aa0 - 0011 0010101 - - 010100-
A4 1- - --a - 0 11111000 - - 1111 - 0 110011 - -
A5 0- - -- - - 0 - 0001001 00100 - 0 - 01 - 01 - - -
A6 - - - -- - - 0 - 1011110 010 - 100 - - 0 - - 100-
A7 0- - -- - - 1 a1011111 0100 - - 00 0 - - - - 10-
A8 - - - -- - - - 10000000 00000 - 11 1- - -1- --
A9 1- - -- - - - - - - 00000 0011001 - - - - -0- --
A10 - - - -- - - - - - - 11111 1111111 - - - - - - - 0-
A11 0- - -- - - - -------- - - - - - -0- - - - -1- --
A12 0- - -- - - - -------- -------- 0- - -0- --
A13 - - - -- - - - -------- -------- 1 - - - 0 - 0-
A14 1- - -- - - - -------- -------- - - - -1- --
A15 0- - -- - - - -------- -------- - - - - 1 - 1-
A16 1- - -- - - - -------- -------- - - - -0- --
A17 0- - -- - - - -------- -------- - - - - - - 1-
A18 1- - -- - - - -------- -------- - - - - - - --
A19 - - - -- - - - -------- -------- - - - - - - --
A20 - - - -- - - - -------- -------- - - - - - - --
Tab. 5-1 Conditions sur les bits de l'état interne orrespondant à la ara téristique
non-linéaire utilisée dans [WYY05d℄. La notation a (respe tivement ā) indique que la
valeur du bit orrespondant est égale (respe tivement opposée) à la valeur du même
bit du registre immédiatement pré édent.
68
5-4. Cara téristique non-linéaire
Les deux ara téristiques non-linéaires données par Wang et al. ne sont valables
que pour les deux ve teurs de perturbations que les auteurs ont hoisis. Or il existe
d'autres ve teurs plus intéressants : les ve teurs onduisant à l'obtention d'une quasi-
ollision qui peuvent être utilisés en ombinaison ave la te hnique des blo s mul-
tiples. En eet, bien que la ollision exhibée pour SHA-0 utilise deux blo s de mes-
sage, elle ne onstitue pas une utilisation de la te hnique des blo s multiples, le
premier blo ne servant qu'à obtenir une variable de haînage vériant un ertain
nombre de onditions imposées par la ara téristique non-linéaire. L'in onvénient
majeur des te hniques utilisées par Wang et al. réside dans le fait que leurs ara té-
ristiques non-linéaires (pour SHA-0 et SHA-1) ont été obtenues à la main, e qui rend
fastidieuse une répétition du pro essus pour de nouveaux ve teurs de perturbations.
Diérentes appro hes ont été menées an d'automatiser la onstru tion des ara -
téristiques non-linéaires, nous pouvons iter les travaux de Sugita et al. [SKP07℄ ou de
Yajima et al. [YSN07℄. Cependant, l'algorithme qui produit a tuellement les meilleurs
résultats repose sur les travaux de De Cannière et Re hberger [DCR06℄. L'utilisation
de générateurs automatiques de ara téristiques non-linéaires a onduit à l'obtention
de ollisions pour des versions réduites à 64 pas [DCR06℄, 70 pas [DCM07, JP07℄ et
tout dernièrement à 72 et 73 pas [Gre10℄ de la fon tion SHA-1.
Nous nous bornerons dans e do ument à donner les prin ipes qui gouvernent
l'utilisation de es générateurs de ara téristiques non-linéaires. En eet, d'une part
le travail de re her he ee tué pendant ette thèse s'est plutt onsa ré à l'améliora-
tion de la partie ara téristique linéaire (présentée au hapitre 7), et d'autre part une
présentation omplète de l'implémentation réalisée par Thomas Peyrin est disponible
dans sa thèse [Pey08℄. Le prin ipe essentiel de l'outil de De Cannière et Re hberger
onsiste à appréhender les hemins diérentiels andidats sous la forme d'une a-
ra téristique diérentielle généralisée an de onstruire un arbre de re her he. Puis
et arbre est par ouru, en utilisant des outils de re her he en profondeur (Ba ktra k
sear h ), pour onstruire un hemin diérentiel valide. L'eort de al ul né essaire à
l'obtention d'une ollision est alors évalué en dénombrant le nombre moyen de noeuds
à par ourir.
La première étape onsiste don à modéliser ette ara téristique. Nous avons
abordé et aspe t se tion 5-2.3 en présentant la diéren e généralisée. Soient deux
mots X et X ′, (X, X ′ ) par la notation X ⋆ . Un ouple X ⋆
nous désignerons le ouple
se onforme à une ara téristique diérentielle ∇X si la diéren e entre X et X est
′
⋆
l'une des diéren es possibles dénies par ∇X (X ∈ ∇X ). Un hemin diérentiel
pour la fon tion de ompression de SHA-0 ou de SHA-1, est don onstitué d'un
ensemble de ara téristiques diérentielles ∇A−4 , ∇A−3 , . . . , ∇A80 pour les états des
registres et d'un ensemble de ara téristiques diérentielles ∇W0 , . . . , ∇W79 pour les
mots de message expansés. Une paire de messages se onforme au hemin diérentiel
jusqu'au pas i si :
(
A⋆−4 ∈ ∇A−4 , . . . , A⋆i ∈ ∇Ai
(5-1)
W0⋆ ∈ ∇W0 , . . . , Wi−1
⋆
∈ ∇Wi−1
Dès lors qu'un hoix de ve teur de perturbations a été fait et qu'une ara téris-
tique linéaire a été établie, il devient né essaire de onstruire un hemin diérentiel
pour l'attaque. Cependant, ela n'est pas susant : il faut aussi s'assurer que e
69
Chapitre 5. Cryptanalyses pratiques
hemin diérentiel onduit à une attaque ee tive. Cela nous amène à la se onde
étape de développement de l'outil qui onsiste à évaluer la probabilité de su ès d'un
hemin diérentiel donné. Dans e but, De Cannière et Re hberger ont introduit
deux nouvelles notions désignées sous les termes de probabilité in ontrlée (Un on-
troled Probability ) et de probabilité ontrlée (Controled Probability ) dont voi i les
dénitions :
Ces dénitions permettent d'évaluer la probabilité qu'un hemin diérentiel soit va-
lide.
An de pouvoir estimer l'eort en terme de al ul, une nouvelle dénition est
né essaire pour mesurer le nombre de degrés de liberté laissés au message.
où n désigne le pas auquel on souhaite obtenir une ollision : n < 80 pour une version
réduite, n = 80 pour la version normalisée de SHA-0 ou SHA-1. Le nombre total de
noeuds par ourus est alors égal à :
n
X
N (n) = N (i).
i=0
70
5-4. Cara téristique non-linéaire
An d'illustrer l'utilisation de es prin ipes, nous présentons dans les tableaux
5-2 et 5-3 le hemin diérentiel orrespondant au premier blo de l'attaque que nous
avons menée ave Thomas Peyrin ontre la fon tion SHA-0 [MP08℄. Nous donnons
pour haque pas le nombre de degrés de liberté F (i), le logarithme en base 2 de la
valeur de la probabilité ontrlée Pc (i) et du nombre moyen de noeuds visités N (i).
-4 : 00001111010010111000011111000011
-3 : 01000000110010010101000111011000
-2 : 01100010111010110111001111111010
-1 : 11101111110011011010101110001001
00 : 01100111010001010010001100000001 0100111001001011000001010n0010u1 0 0.00 -10.00
01 : 1110110111111111100111011n1111u0 0100000011011011010100001n000000 0 0.00 -10.00
02 : 01100111011111111101n10101101010 1111011000011110100111011n011011 0 0.00 -10.00
03 : 001101010010100n00001100n0uuuuu0 0011100010101001011100100u000101 0 0.00 -10.00
04 : 111100000nu000001010110001110000 u110010001000000010100000u0101n1 0 0.00 -10.00
05 : 00111n00000010011000100000u0n1u1 n0010100110010000101010010100000 0 0.00 -10.00
06 : 10110101110110110000101u100u1001 n010001011110100001111000u000100 0 0.00 -10.00
07 : 100unnnnnnnnn0100nu0100101u11001 00010010111101000101011001011010 0 0.00 -10.00
08 : 1000011100001n000n100u0n010nn001 0101101001110001000110001n0001u1 0 0.00 -10.00
09 : 0010000000000010un00nu1u1un01100 n101000101000111100101100u1110n0 0 0.00 -10.00
10 : 11100110100101000nu01u10un00n100 01111010011000100100011100011000 0 0.00 -10.00
11 : 011110001110001101nuu10101000101 0111000100110111010110011u1110u0 0 0.00 -10.00
12 : 01001101011010000010u0000n110000 10110111110101-----1-----u000001 10 -4.00 -10.00
13 : 010110011100000----010-0-01001u0 101001010----------------n0000u1 16 -1.00 -4.00
14 : 10111100--------------1--110u011 01101-0----0--1----0---0-1-011u0 16 -2.00 11.00
15 : 10100------------------0-1-u0100 n0101-0----0--1----0---0-1-11000 16 -2.00 25.00
16 : --01-----------------------n0011 010001110----------------00101n0 0 0.00 39.00
17 : -----------------------------1n- n1000-0----1--1----1---0-u-10011 0 -2.00 39.00
18 : 1----------------------------0-- 01000-0----1--1----0---0-0-011u0 0 0.00 37.00
19 : -------------------------------- n00110100----------------0001011 0 0.00 37.00
20 : -------------------------------- n0110-0----1-------0-----0-000u1 0 -1.00 37.00
21 : ------------------------------n- u1100-1------------------u-10111 0 0.00 36.00
22 : -------------------------------- 00001-1------------------0-00110 0 -2.00 36.00
23 : ------------------------------n- n1011-1----0-------0-----u-11001 0 0.00 34.00
24 : -------------------------------- u0000-0------------------1-11100 0 -2.00 34.00
25 : ------------------------------n- 01101-1------------------u-10111 0 0.00 32.00
26 : -------------------------------- u1010-1----0-------1-----0-011u0 0 -1.00 32.00
27 : -------------------------------- 01001-1------------------0-01110 0 0.00 31.00
28 : -------------------------------- u0000-0------------------1-11011 0 0.00 31.00
29 : -------------------------------- u0111-0------------------0-00010 0 0.00 31.00
30 : -------------------------------- 01101-1------------------1-10010 0 0.00 31.00
31 : -------------------------------- 10110-1------------------0-01001 0 0.00 31.00
32 : -------------------------------- 00111-1------------------1-00100 0 0.00 31.00
33 : -------------------------------- 01011-1------------------1-11101 0 0.00 31.00
34 : -------------------------------- 00010-0------------------0-010u0 0 -1.00 31.00
35 : ------------------------------u- 10001-0------------------n-10110 0 0.00 30.00
36 : -------------------------------- 11100-0------------------0-000u1 0 -1.00 30.00
37 : -------------------------------- n0010-0------------------0-001u0 0 -1.00 29.00
38 : ------------------------------u- n1101-0------------------n-11110 0 0.00 28.00
39 : -------------------------------- n1100-1------------------0-001n0 0 -1.00 28.00
40 : -------------------------------- n1111-0------------------0-10000 0 -1.00 27.00
··· ··· ··· ··· ···
Tab. 5-2 Exemple de hemin diérentiel obtenu à l'aide d'un outil automatisé
de génération de ara téristique non-linéaire. Le ontenu du tableau orrespond à
la première partie (pas 1 à 40) du hemin diérentiel du premier blo utilisé par
l'attaque publié dans [MP08℄.
71
Chapitre 5. Cryptanalyses pratiques
Tab. 5-3 Exemple de hemin diérentiel obtenu à l'aide d'un outil automatisé
de génération de ara téristique non-linéaire. Le ontenu du tableau orrespond à
la se onde partie (pas 41 à 80) du hemin diérentiel du premier blo utilisé par
l'attaque publié dans [MP08℄.
72
5-5. Te hnique des blo s multiples
onstru tion dite de Davies-Meyer. Pour les fon tions SHA-0 et SHA-1, le rebou lage
utilisé onsiste à ee tuer une somme modulo 232 de l'état initial des 5 registres ave
leur état nal (A0 + A80 , B0 + B80 , C0 + C80 , D0 + D80 , E0 + E80 ). Paradoxalement,
bien que onçu pour améliorer la résistan e au al ul d'anté édent, le rebou lage des
fon tions SHA-0 et SHA-1 est mis à prot par les ryptanalystes lors des attaques
par ollisions. Les diérentes appli ations de la te hnique des blo s multiples à es
fon tions illustrent parfaitement la faiblesse de e rebou lage.
Nous introduirons tout d'abord le prin ipe général de la te hnique des blo s mul-
tiples avant de détailler le premier exemple d'appli ation de ette te hnique à la
fon tion SHA-0 dû à Biham et al. [BCJ05℄. Nous dé rirons ensuite omment une
utilisation appropriée du rebou lage en ombinaison ave l'utilisation d'une ara té-
ristique non-linéaire onstitue aujourd'hui l'appro he lassique pour les attaques par
ollisions ontre SHA-0 et SHA-1. Finalement, nous formulerons une remarque sur
le as des ryptanalyses proposées par Wang et al. [WYY05b, WYY05d℄.
wH (h(M ) ⊕ h(M ′ )) ≪ n,
h(V, M ) = h(V ′ , M ′ )
73
Chapitre 5. Cryptanalyses pratiques
IV V V′
M M′ M M′
h h h h
Puis dans la se onde étape, à re her her une pseudo- ollision parti ulière orrespon-
dant à la se onde itération de la fon tion de ompression :
Une fois la quasi- ollision et la pseudo- ollision obtenues pour la fon tion de om-
pression, il sut de on aténer les deux blo s pour onstruire deux messages qui
forment une ollision pour la fon tion de ha hage :
Cette te hnique, illustrée gure 5-9, fait à présent partie intégrante de l'éventail des
outils à la disposition des ryptanalystes.
74
5-5. Te hnique des blo s multiples
M1 M2
f f
H1
H2
IV
H1′
f f
M1′ M2′
les 5 premières étapes de la fon tion de ronde IF (au sein desquelles s'expriment
les diéren es sur la variable de haînage d'entrée) peuvent induire, de part le
ara tère non-linéaire de ette fon tion, un omportement identique pour deux
diéren es d'entrée diérentes.
Forts de es observations, les auteurs de ette attaque ont onstruit un graphe orienté
dont les noeuds représentent les diéren es présentes dans les variables de haînage
et les arêtes les ara téristiques linéaires qui joignent les diéren es d'entrée aux
diéren es de sortie en prenant en ompte le rebou lage. La re her he d'un hemin
e a e dans e graphe à onduit à l'obtention d'une ollision onstituée de quatre
blo s de message et fondée sur quatre ara téristiques linéaires diérentes. La -
gure 5-10 illustre la te hnique des blo s multiples telle qu'utilisée dans l'arti le de
Biham et al.
La te hnique des blo s multiples mise en oeuvre par Biham et al., n'est pas
transposable en l'état à la fon tion SHA-1. En eet, an de onstruire un hemin
diérentiel passant par plusieurs blo s, il est né essaire de onstruire un graphe
onnexe. Pour la fon tion SHA-0, les perturbations sont ontenues sur la position de
bit 1, e qui induit un nombre limité de sommets (nous avons 5 registres et don 25 =
32 sommets diérents). Pour la fon tion SHA-1, la permutation ir ulaire ajoutée à
la fon tion d'expansion étale les positions de bits où se situent les perturbations,
augmentant exponentiellement le nombre de sommets, et rendant beau oup plus
di ile l'obtention d'un graphe susamment onnexe et onduisant à une attaque
ave une bonne omplexité.
Remarque. Le prin ipe de la te hnique des blo s multiples n'a été mis en oeuvre
pour la ryptanalyse de SHA-0 et SHA-1 qu'à partir du moment ou les ara téris-
tiques non-linéaire de la fon tion IF ont pu être exploitées. En eet, 'est l'utilisation
adéquate de la non-linéarité qui autorise l'emploi de ve teurs de perturbations plus
performants mais aboutissant seulement à des quasi- ollisions. Dans le adre d'une
attaque linéaire, la te hnique des blo s multiples ne permet pas d'améliorer la om-
75
Chapitre 5. Cryptanalyses pratiques
∆=0
Fig. 5-10 Prin ipe de mise en oeuvre de la te hnique des blo s multiples utilisée
par Biham et al. dans [BCJ05℄.
76
5-6. Te hniques d'a élération de re her he de messages
∆M 1
∆0H ∆S ∆1H
=0 = +d = +d
N L1 L
∆M 2
∆1H ∆S ∆2H
= +d = −d =0
N L2 L
Fig. 5-11 Te hnique des blo s multiples utilisée en pratique pour la re her he de
ollisions pour les fon tions SHA-0 et SHA-1.
77
Chapitre 5. Cryptanalyses pratiques
∆M = 0
∆H ∆H
=0 =0
∆M 6= 0
∆H ∆H
=0 =0
NL L
Fig. 5-12 Illustration du point de vue des diéren es de la ollision pour SHA-0
présentée dans [WYY05d℄.
que l'on peut onsidérer que le al ul du oût du hemin diérentiel débute à un pas
ultérieur au pas 16. En eet, es te hniques permettent de générer de façon e a e
des paires de messages se onformant, ave une probabilité pro he de 1, au hemin
diérentiel pour des pas supérieur à 16.
La première méthode d'a élération de re her he utilisée fut proposée par Biham
et Chen en 2004 [BC04℄ sous la forme des bits neutres. Puis en 2005, Wang et al.
[WYY05b℄ employèrent une te hnique dite de modi ation de message que les auteurs
appliquèrent ave su ès à plusieurs autres fon tions de ha hage. En 2007, Joux
et Peyrin [JP07℄ adaptèrent l'attaque boomerang de Wagner [Wag99℄, initialement
destinée à la ryptanalyse des s hémas de hirement par blo , aux fon tions de
ha hage. Nous présentons dans e hapitre ha une de es trois méthodes.
Prin ipe des bits neutres. Le prin ipe de l'a élérateur de re her he proposé
par Biham et Chen se fonde sur la notion de onformité qui est dénie dans leur
arti le de la façon suivante :
78
5-6. Te hniques d'a élération de re her he de messages
Cette notion peut être fa ilement étendue aux ensembles au moyen des dénitions
suivantes :
1. Le
′
ouple (M, M ) se onforme à αr .
2. Le ouple (M, M ′ ) possède un ensemble 2-neutre susamment grand. Les au-
teurs ont mesuré expérimentalement qu'environ 1/8 des sous-ensembles de bits
de l'ensemble 2-neutre sont des ensembles neutres.
79
Chapitre 5. Cryptanalyses pratiques
80
Y
p= pi .
i=1
Si les inq dernières oordonnées du ve teur de perturbations sont nulles alors p est
la probabilité d'obtenir une ollision, sinon 'est la probabilité d'obtenir une quasi-
ollision.
Pour un ouple de message se onformant à αr on note :
80
Y
p(r) = pi .
i=r+1
Constru tion d'un ensemble 2-neutre. La onstru tion d'un ensemble 2-neutre
se déroule en deux étapes : on onstruit tout d'abord un ensemble de bits neutres,
puis on identie dans et ensemble les paires neutres an d'obtenir un sous-ensemble
2-neutre.
(M ⊕ ei , M ′ ⊕ ei ) ∀i ∈ {1, . . . , 512}.
80
5-6. Te hniques d'a élération de re her he de messages
possible relativement au ouple (M, M ′ ). Biham et Chen pré isent que si trou-
ver la lique maximale d'un graphe est en général un problème NP- omplet,
dans le adre de ette attaque, trouver une lique susamment grande (i.e.
possédant au moins k(r) sommets) n'est pas di ile ar de nombreux sommets
sont onne tés à tous les autres.
81
Chapitre 5. Cryptanalyses pratiques
d'appli ation des modi ations de message se déroule pas à pas. Il en dé oule que
les modi ations de message utilisées à un ertain pas ne doivent pas perturber
les éventuelles modi ations et onditions vériées par les états des registres pré é-
dents. On doit de plus vérier que haque modi ation de message s'a orde ave
le système d'équations linéaires hérité de la onstru tion et de l'instan iation de la
ara téristique linéaire. La onstru tion et la mise en oeuvre de es modi ations de
message prend généralement pla e après qu'un hemin diérentiel omplet (ve teur
de perturbations et ara téristique non-linéaire) ait été obtenu.
Modi ation de message simple. Les modi ations de message simples inter-
viennent seulement lors des 16 premiers pas de la fon tion de mise à jour des registres,
qui sont les pas pour lesquels l'attaquant possède un ontrle dire t sur les mots de
message. Ces modi ations se résument en général à la modi ation d'un bit du mot
de message orrespondant à la même position de bit pour le registre. Pour modier
la valeur du bit ai,j (bit de position j du registre Ai ), on peut re al uler la valeur du
mot de message Wi−1 = Wi−1 + 2 .
j
On peut assez fa ilement s'assurer que l'ensemble des modi ations de message
simples permettent de orriger les onditions imposées aux états des registres des
16 premiers pas ave une probabilité de su ès égale à 1. Une méthode triviale per-
mettant de s'assurer de vérier l'ensemble des onditions sur les registres Ai pour
1 ≤ i ≤ 16 onsiste à utiliser la pro édure suivante :
Modi ation de message avan ée. Les modi ations de message avan ées visent
à orriger des onditions non vériées par les bits des registres pour les pas supérieurs
ou égaux à 16 où les mots de message utilisés ne sont plus sous le ontrle dire t du
ryptanalyste, mais issus du pro essus d'expansion. Ces modi ations sont beau oup
plus omplexes à onstruire. Leur utilisation repose le plus souvent sur la modi a-
tion simultanée de plusieurs bits de message et s'appuient aussi sur la diusion des
modi ations sur les états des registres.
Par exemple, an de s'assurer de la ondition a21,4 = a20,4 que l'on peut trouver
dans le hemin diérentiel présenté dans [WYY05b℄, Naito et al. ont proposé la
modi ation de message avan ée qui onsiste à ajouter les onditions supplémentaires
suivantes :
a6,6 = m5,6 ,
m6,11 6= m5,6 ,
m7,6 = m5,6 ,
a7,4 = 0, a8,4 = 1,
m10,4 6= m5,6
82
5-6. Te hniques d'a élération de re her he de messages
M5 = M5 ⊕ 25 ,
M6 = M6 ⊕ 210 ,
M7 = M7 ⊕ 25 ,
M10 = M10 ⊕ 23 .
À la diéren e des modi ations de message simples, des al uls de retenues in-
terviennent dans les modi ations de message avan ées, il existe don une probabilité
que es modi ations é houent.
Con lusion. Les modi ations de message avan ées permettent de satisfaire des
onditions sur les états des registres à des pas supérieurs au pas 16. Elles sont don
sus eptibles d'induire une amélioration de la omplexité de l'attaque, dès lors que leur
probabilité d'é houer est petite. Des modi ations de message ont été proposées pour
orriger des onditions à hauteur du pas 24 pour SHA-0 [NSS06℄ et du pas 25 pour
SHA-1 [WYY05 ℄. Cependant, es modi ations sont onstruites pour un hemin
diérentiel donné et dépendent fortement du ve teur de perturbations hoisi. De plus,
les modi ation publiées à e jour ont été établies à la main e qui rend fastidieuse
leur utilisation en tant que te hnique d'a élération de re her he générique. Elles
onsomment aussi un grand nombre de degrés de liberté.
5-6.3 Boomerangs
L'attaque boomerang, introduite par Wagner [Wag99℄, est une attaque adapta-
tive utilisant des textes lairs et hirés (Adaptive hosen plaintext and iphertext
atta k ). Elle fut développée ensuite par Kelsey et al. [KKS00℄ en attaque à lair hoisi
(Choosen plaintext atta k ) et rebaptisée attaque boomerang ampliée. L'appli ation
des attaques boomerang ampliées aux fon tions de ha hage, et plus parti ulièrement
à la fon tion SHA-1, est due à Antoine Joux et Thomas Peyrin [JP07℄.
83
Chapitre 5. Cryptanalyses pratiques
qui fon tionne pour des diérentielles ayant des probabilités inférieures mais aussi
pour des diérentielles tronquées. Nous avons don les diérentielles suivantes :
Y0 ⊕ Y1 = ∆ 1 , Y2 ⊕ Y0 = ∆ 0 , Y3 ⊕ Y1 = ∆ 0 et don Y2 ⊕ Y3 = ∆ 1 .
6. Et omme Y2 ⊕ Y3 = ∆1 , nous avons une paire valide pour e0 qui se propage
pour donner X2 ⊕ X3 = ∆0 .
84
5-6. Te hniques d'a élération de re her he de messages
X1 X3 X2i+1 X2j+1
X0 X2 X2i X2j
∆0 ∆0 ∆0 ∆0
e0 e0 e0 e0
e0 e0 e0 e0
∆0 ∆0
Y1 Y3 Y2i+1 Y2j+1
∆1 ∆0 ∆1 ∆1 ∆0 ∆1
Y0 Y2 Y2i Y2j
e1 e1 e1 e1
e1 e1 e1 e1
∆1 ∆1
∆1 ∆1
Z1 Z3 Z2i+1 Z2j+1
Z0 Z2 Z2i Z2j
Fig. 5-13 Attaque boomerang et attaque boomerang ampliée pour les s hémas de
hirement par blo . Le sens des è hes indique le sens hirement/dé hirement.
Appli ation aux fon tions de ha hage L'appli ation de l'attaque boomerang
ampliée aux fon tions de ha hage onsiste à ombiner à la diérentielle prin ipale
plusieurs diérentielles partielles, dites diérentielles auxiliaires. Ces diérentielles
auxiliaires onstituent des diérentielles qui possèdent un bon omportement sur un
nombre limité de pas de la fon tion de mise à jour des registres.
Nous allons à présent dé rire le prin ipe d'appli ation de l'attaque boomerang
ampliée pour les fon tions SHA-0 et SHA-1. Dans leur arti le, Joux et Peyrin [JP07℄
indiquent que ette te hnique onstitue une généralisation des te hniques de bits
neutres et de modi ations de message. Nous hoisissons i i de nous pla er dans le
ontexte d'une utilisation des boomerangs en tant que bits neutres, ar 'est elle
que nous avons utilisée ave su ès lors de la ryptanalyse que nous avons menée
ontre la fon tion SHA-0 [MP08℄.
Considérons une re her he de ollision, les premières étapes de l'attaque nous
ont permis de onstruire un hemin diérentiel, que nous qualierons de prin ipal, et
d'obtenir une diérentielle ∇P , à partir de laquelle nous pouvons déduire la diéren e
∆P w appliquée en entrée au ouple de messages (par simpli ité, et sans perte de
généralité, nous onsidérerons que toutes les diéren es utilisent le ou ex lusif bit
à bit). Dans les notations que nous emploierons, l'indi e w indique une diéren e
on ernant les mots de message, l'indi e a indique une diéren e on ernant l'état
des registres. Nous possédons aussi pour les états des registres, une diéren e en
entrée ∆Ea et une diéren e en sortie ∆P a . Ces diéren es pourront être nulles dans
le as d'une re her he de ollision sur un seul blo , ou égale à des valeurs parti ulières
dans le as où la te hnique des blo s multiples est employée. Nous re her hons alors
les paires de messages (M, M ′ ) ave M ′ = M ⊕ ∆P w pour lesquelles la diéren e de
85
Chapitre 5. Cryptanalyses pratiques
sortie ∆P a est atteinte, e qui se produit ave la probabilité p∇P pour haque paire
andidate.
An d'illustrer le prin ipe de l'attaque boomerang, nous supposons que nous
avons à notre disposition une diérentielle auxiliaire ∇A pour laquelle la diéren e
appliquée aux messages vaut ∆Aw et la diéren e observée sur l'état interne vaut
∆Aa . Une diérentielle auxiliaire se ara térise de plus par sa portée s, 'est à dire
le pas auquel la diéren e ∆Aa est destinée à être obtenue. Pour une paire de message
(M, M ′ ) ave M ′ = M ⊕ ∆Aw , la diéren e ∆Aa est atteinte à la portée s ave la
probabilité p∇A pour haque paire andidate. On peut remarquer que la diérentielle
prin ipale ∇P onstitue une diérentielle auxiliaire de portée 80.
Nous divisons l'ensemble des 80 pas de la fon tion de mise à jour des registres en
deux parties, la division étant positionnée sur le pas s orrespondant à la portée de
la diérentielle auxiliaire. Nous notons ∆Sa la diéren e attendue sur l'état interne
au pas s. (M, M ′ = M ⊕ ∆P w ) onduise
La probabilité qu'une paire de messages
à un état interne vériant la diéren e ∆Sa au pas s est notée pS . La probabilité
qu'à partir d'une diéren e ∆Sa sur l'état interne au pas s, une paire de message
(M, M ′ = M ⊕ ∆P w ) onduise à une diéren e ∆P a sur l'état interne au pas 80 est
notée pF . En supposant les étapes indépendantes, nous avons p∇P = pS × pF .
Une appli ation de la te hnique des boomerangs ampliées se déroule alors de la
façon suivante :
Con lusion Les diérentielles auxiliaires employées dans les attaques boomerangs
onstituent une généralisation des deux te hniques d'a élération de re her he pré-
édentes. Elles peuvent être utilisées de façon similaire aux bits neutres an de mul-
tiplier les instan es de paires de message onformes, ou bien de façon similaire au
86
5-6. Te hniques d'a élération de re her he de messages
H′ H′
H ∆Ea H ∆Ea
∆Sa ∆Sa
M1′ M2′
M1 M2
∆Aw
∆P w ∆Aw ∆P w
∆P a ∆P a
H1′ H2′
H1 H2
Fig. 5-14 Attaque boomerang ampliée appliquée aux fon tions SHA-0 et SHA-1.
modi ations de message an de modier des paires de message pour amener des
onditions portant sur des bits de registres à être vériées. Elles onstituent à e
jour, la te hnique d'a élération de re her he la plus e a e pour la ryptanalyse
des fon tions SHA-0 et SHA-1.
87
Chapitre 5. Cryptanalyses pratiques
88
6
A élération de la ryptanalyse de
SHA-0
Sommaire
6-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . 89
6-2 Nouveau ve teur de perturbations . . . . . . . . . . . 90
6-3 Utilisation des boomerangs . . . . . . . . . . . . . . . 90
6-4 Cara téristique non-linéaire . . . . . . . . . . . . . . . 96
6-5 Con lusion . . . . . . . . . . . . . . . . . . . . . . . . . 97
Finalement, la meilleure attaque publiée à e jour est issue d'un travail ommun
ave Thomas Peyrin [MP08℄, et possède une omplexité de l'ordre de 233 évalua-
89
Chapitre 6. A élération de la ryptanalyse de SHA-0
tions de la fon tion de ompression. C'est ette attaque que nous présentons dans e
hapitre.
2
L'arti le de Wang et al. fait mention de 14 onditions ependant le nombre exa t de onditions
90
6-3. Utilisation des boomerangs
Pas 1 to 20
ve teur 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0
♯ onditions - - - - - - - - - - - - - - - - 2 0 2 1
Pas 21 to 40
ve teur 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
♯ onditions 1 0 2 0 2 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1
Pas 41 to 60
ve teur 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1
♯ onditions 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 2 1 2 2
Pas 61 to 80
ve teur 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0
♯ onditions 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0
Tab. 6-1 Nouveau ve teur de perturbations pour SHA-0, ave le nombre de ondi-
tions pour haque pas (les onditions des 16 premiers ne sont pas prises en ompte).
le hemin diérentiel prin ipal. Les deux diérentielles auxiliaires que nous avons
utilisées sont notées AP1 et AP2 :
la diérentielle auxiliaire AP1 présente peu de ontraintes et possède une portée
faible,
la se onde diérentielle AP2 né essite de plus nombreuses ontraintes, mais
possède une portée supérieure.
Un ompromis a été fait entre es deux types de diérentielles an d'obtenir le
meilleur ensemble possible de hemins auxiliaires sans toutefois trop ontraindre le
hemin diérentiel prin ipal, e qui pourrait avoir omme eet de faire é houer le
pro essus de génération de la ara téristique non-linéaire.
91
Chapitre 6. A élération de la ryptanalyse de SHA-0
pas ∇ Ai ∇W i
... ...
i−1 ----------------------------b--- --------------------------------
i ----------------------------b--- ------------------------------a-
i+1 ------------------------------a- -------------------------a------
i+2 0------------------------------- --------------------------------
i+3 1------------------------------- --------------------------------
i+4 -------------------------------- --------------------------------
i+5 -------------------------------- a-------------------------------
i+6 -------------------------------- --------------------------------
... ...
Fig. 6-1 Cara téristique orrespondant à une ollision lo ale non-linéaire initiée au
pas i et de diérentielle ∆ =< 21 , 26 , 0, 0, 0, 231 >. La olonne de droite représente
les diérents états des mots de message expansés. La olonne de gau he représente
les diérents états du registre A et pré ise les ontraintes né essaires pour que la
ollision lo ale non-linéaire soit vériée. Un - indique qu'il n'y a pas de ontrainte,
une lettre indique une valeur binaire et une lettre surlignée son omplément.
Constru tion des diérentielles auxiliaire AP1 et AP2 . Le prin ipe d'une dif-
férentielle auxiliaire onsiste à onstruire, au moyen de ollisions lo ales non-linéaires,
un hemin diérentiel partiel onduisant à une ollision à un pas déterminé. Étant
donné que pour ette attaque nous avons hoisi de nous pla er dans le ontexte d'une
utilisation des diérentielles auxiliaires en tant que bits neutres, nous souhaitons que
es diérentielles possèdent la plus grande portée possible. Cependant e hemin doit
obéir à un ertain nombre de ontraintes :
An de béné ier du pro essus de ompensation hérité de l'expansion de mes-
sage de SHA-0, nous avons hoisi de positionner les ollisions lo ales non-
linéaires d'une même diérentielle auxiliaire sur la même position de bit.
Pour une ollision lo ale non-linéaire débutant au pas i, des onditions doivent
être vériées (et don imposées) sur des bits du registre Ai+2 . Nous n'autorisons
92
6-3. Utilisation des boomerangs
don l'apparition de ollision lo ale non-linéaire que sur les mots W0 , . . . , W14 ,
ar au delà il n'est théoriquement plus possible de s'assurer d'une probabilité
égale à 1 pour la diérentielle auxiliaire.
Finalement, le nombre de andidat possible est égal à 815 = 245 . En pratique, nous im-
posons une ondition supplémentaire sur le nombre de ollisions lo ales non-linéaire
que nous avons limité à 5 pour notre re her he. En eet si e nombre est trop élevé,
trop de degrés de liberté sont dépensés. Pour haque andidat, on applique la formule
de ré urren e de l'expansion de message et on mesure la portée orrespondant à e
andidat en identiant le pas où la première diéren e in ontrlée apparaît. Parmi
les andidats obtenus, nous avons retenus deux diérentielles.
Pla ement des diérentielles auxiliaires. Une fois les diérentielles auxiliaires
établies, nous disposons de plusieurs stratégies pour leur pla ement. La première de
es stratégies onsiste à utiliser les diérentielles auxiliaires en suivant la méthode de
Biham et Chen pour les bits neutres. Dès qu'une paire de message se onforme à la
diérentielle prin ipale jusqu'à la portée orrespondant à une diérentielle auxiliaire,
on tente de multiplier les instan es en essayant de pla er ette diérentielle auxiliaire.
Cependant, ette stratégie est peu produ tive ar elle né essite de trouver des posi-
tions de bit pour lesquelles les onditions de la diérentielle auxiliaire sont vériées.
Une stratégie plus intéressante onsiste à lier le pla ement des diérentielles auxi-
liaires à la génération de ara téristique non-linéaire. Deux hoix sont alors possibles,
selon que l'on pla e les diérentielles auxiliaires avant ou après la génération de la
ara téristique non-linéaire. Si on pla e les diérentielles auxiliaires après l'établis-
sement de ette ara téristique, la probabilité de trouver des positions satisfaisantes
est meilleure qu'ave la méthode de Biham et Chen. Mais le nombre de degrés de
liberté pour le pla ement est limité par le nombre de bits non- ontraints lors de la
génération de la ara téristique non-linéaire. Le hoix qui laisse le plus grand nombre
de degrés de libertés, et qui est don sus eptible de onduire à la meilleure a élé-
93
Chapitre 6. A élération de la ryptanalyse de SHA-0
i Ai Wi
00 : --------------------------------
01 : -------------------------------- --------------------------------
02 : -------------------------------- --------------------------------
03 : -------------------------------- --------------------------------
04 : -------------------------------- --------------------------------
05 : ---------------------------b---- --------------------------------
06 : ---------------------------b---- -----------------------------a--
07 : -----------------------------a-- ------------------------a-------
08 : -------------------------------0 --------------------------------
09 : -------------------------------1 --------------------------------
10 : -------------------------------- --------------------------------
11 : -------------------------------- -------------------------------a
12 : -------------------------------- --------------------------------
13 : -------------------------------- --------------------------------
14 : -------------------------------- --------------------------------
15 : -------------------------------- --------------------------------
Fig. 6-3 Cara téristique asso iée à la diérentielle auxiliaire AP1 positionnée sur
la position de bit j = 1. Cette diérentielle possède une seule ollision lo ale non-
linéaire de la forme ∆ =< 2j , 2j+5 , 0, 0, 0, 2j+30 > initiée au pas 7. La olonne de
droite représente les diérents états des mots de message expansés. La olonne de
gau he représente les diérents états du registre A et pré ise les ontraintes né es-
saires pour que la ollision lo ale non-linéaire soit vériée. Un - indique qu'il n'y
a pas de ontrainte, une lettre indique une valeur binaire et une lettre surlignée son
omplément.
94
6-3. Utilisation des boomerangs
i Ai Wi
-1 : ---------------------------d----
00 : ---------------------------d---- -----------------------------a--
01 : ---------------------------e-a-- ------------------------a-------
02 : ---------------------------e---1 -----------------------------b--
03 : -----------------------------b-0 ------------------------b------a
04 : -------------------------------0 -------------------------------a
05 : -------------------------------0 -------------------------------a
06 : -------------------------------- -------------------------------b
07 : -------------------------------- -------------------------------b
08 : -------------------------------- --------------------------------
09 : ---------------------------f---- --------------------------------
10 : ---------------------------f---- ----------------------------- --
11 : ----------------------------- -- ------------------------ -------
12 : -------------------------------0 --------------------------------
13 : -------------------------------0 --------------------------------
14 : -------------------------------- -------------------------------
15 : -------------------------------- -------------------------------
Fig. 6-5 Cara téristique asso iée à la diérentielle auxiliaire AP2 positionnée sur
la position de bit j = 1. Cette diérentielle possède une ollision lo ale non-linéaire
de la forme ∆ =< 2j , 2j+5 , 0, 2j+30 , 2j+30 , 2j+30 > initiée au pas 1, et deux ollisions
lo ales non-linéaires de la forme ∆ =< 2 , 2
j j+5 , 0, 0, 2j+30 , 2j+30 > initiées aux pas
3 et 11. La olonne de droite représente les diérents états des mots de message
expansés. La olonne de gau he représente les diérents états du registre A et pré ise
les ontraintes né essaires pour que la ollision lo ale non-linéaire soit vériée. Un
- indique qu'il n'y a pas de ontrainte, une lettre indique une valeur binaire et une
lettre surlignée son omplément.
95
Chapitre 6. A élération de la ryptanalyse de SHA-0
Tab. 6-2 Type des diérentielles auxiliaires utilisées lors de la ryptanalyse et leurs
positions respe tives.
ration de re her he, onsiste à pla er les diérentielles auxiliaires avant de tenter de
générer une ara téristique non-linéaire. Cependant, la perte de degrés de libertés
induite par le pla ement des diérentielles auxiliaires peut rendre l'établissement de
la ara téristique non-linéaire di ile voire même impossible.
C'est ette dernière stratégie que nous avons mise en oeuvre pour notre attaque.
Le tableau 6-2 ré apitule pour haque blo le nombre de diérentielles auxiliaires
utilisées, leur type et leur position de bit. Le nombre supérieur de diérentielles AP2
pour le premier blo tient à la valeur de la variable de haînage initiale dénie pour
la fon tion SHA-0 qui est fortement stru turée. Il s'avère que ette stru ture prote
au ryptanalyste ar elle permet d'introduire plus de hemins diérentiels auxiliaires.
96
6-5. Con lusion
97
Chapitre 6. A élération de la ryptanalyse de SHA-0
i ∇ Ai ∇W i
-4 : 00001111010010111000011111000011
-3 : 01000000110010010101000111011000
-2 : 01100010111010110111001111111010
-1 : 11101111110011011010101110001001
00 : 01100111010001010010001100000001 0100111001001011000001010n0010u1
01 : 1110110111111111100111011n1111u0 0100000011011011010100001n000000
02 : 01100111011111111101n10101101010 1111011000011110100111011n011011
03 : 001101010010100n00001100n0uuuuu0 0011100010101001011100100u000101
04 : 111100000nu000001010110001110000 u110010001000000010100000u0101n1
05 : 00111n00000010011000100000u0n1u1 n0010100110010000101010010100000
06 : 10110101110110110000101u100u1001 n010001011110100001111000u000100
07 : 100unnnnnnnnn0100nu0100101u11001 00010010111101000101011001011010
08 : 1000011100001n000n100u0n010nn001 0101101001110001000110001n0001u1
09 : 0010000000000010un00nu1u1un01100 n101000101000111100101100u1110n0
10 : 11100110100101000nu01u10un00n100 01111010011000100100011100011000
11 : 011110001110001101nuu10101000101 0111000100110111010110011u1110u0
12 : 01001101011010000010u0000n110000 10110111110101-----1-----u000001
13 : 010110011100000----010-0-01001u0 101001010----------------n0000u1
14 : 10111100--------------1--110u011 01101-0----0--1----0---0-1-011u0
15 : 10100------------------0-1-u0100 n0101-0----0--1----0---0-1-11000
16 : --01-----------------------n0011 010001110----------------00101n0
17 : -----------------------------1n- n1000-0----1--1----1---0-u-10011
18 : 1----------------------------0-- 01000-0----1--1----0---0-0-011u0
19 : -------------------------------- n00110100----------------0001011
20 : -------------------------------- n0110-0----1-------0-----0-000u1
21 : ------------------------------n- u1100-1------------------u-10111
22 : -------------------------------- 00001-1------------------0-00110
23 : ------------------------------n- n1011-1----0-------0-----u-11001
24 : -------------------------------- u0000-0------------------1-11100
25 : ------------------------------n- 01101-1------------------u-10111
26 : -------------------------------- u1010-1----0-------1-----0-011u0
27 : -------------------------------- 01001-1------------------0-01110
28 : -------------------------------- u0000-0------------------1-11011
29 : -------------------------------- u0111-0------------------0-00010
30 : -------------------------------- 01101-1------------------1-10010
31 : -------------------------------- 10110-1------------------0-01001
32 : -------------------------------- 00111-1------------------1-00100
33 : -------------------------------- 01011-1------------------1-11101
34 : -------------------------------- 00010-0------------------0-010u0
35 : ------------------------------u- 10001-0------------------n-10110
36 : -------------------------------- 11100-0------------------0-000u1
37 : -------------------------------- n0010-0------------------0-001u0
38 : ------------------------------u- n1101-0------------------n-11110
39 : -------------------------------- n1100-1------------------0-001n0
40 : -------------------------------- n1111-0------------------0-10000
··· ···
Tab. 6-3 Chemin diérentiel omplet pour le premier blo , pas 1 à 40.
98
6-5. Con lusion
i ∇ Ai ∇W i
··· ···
41 : -------------------------------- n0010-1------------------0-11010
42 : -------------------------------- n0100-0------------------1-110u1
43 : ------------------------------u- 00000-1------------------n-01010
44 : -------------------------------- 00011-0------------------0-100n0
45 : -------------------------------- n0111-1------------------1-10110
46 : -------------------------------- n0111-1------------------0-00010
47 : -------------------------------- u0010-1------------------1-00000
48 : -------------------------------- 01101-0------------------0-010n0
49 : ------------------------------n- 11111-1------------------u-10011
50 : -------------------------------- 01000-1------------------0-100u0
51 : -------------------------------- u1110-1------------------0-10010
52 : -------------------------------- n1101-1------------------1-11110
53 : -------------------------------- n0001-1------------------1-001u0
54 : ------------------------------u- 11011-0------------------n-11110
55 : -------------------------------- 10001-0------------------0-000n0
56 : -------------------------------- n0111-1------------------0-001n1
57 : ------------------------------n- n0110-1------------------u-11101
58 : -------------------------------- u1110-1------------------1-11001
59 : ------------------------------n- u1110-0------------------u-010u1
60 : ------------------------------u- n1111-1------------------n-100n1
61 : -------------------------------- 01010-0------------------0-010n1
62 : -------------------------------- 01111-1------------------1-11111
63 : -------------------------------- 10011-1------------------0-00010
64 : -------------------------------- n1000-0------------------0-10110
65 : -------------------------------- 01000-0------------------1-00011
66 : -------------------------------- 01000-0------------------0-101u1
67 : ------------------------------u- 01001-0------------------n-01001
68 : -------------------------------- 10001-0------------------0-100u0
69 : -------------------------------- u0010-1------------------1-11000
70 : -------------------------------- u1010-0------------------1-011n1
71 : ------------------------------n- u0101-0------------------u-01101
72 : -------------------------------- 00011-1------------------0-100u0
73 : -------------------------------- n1010-1------------------0-11000
74 : -------------------------------- n1100-0------------------0-10010
75 : -------------------------------- u1110-1------------------1-110n1
76 : ------------------------------n- 11011-1------------------u-00100
77 : -------------------------------- 00111-0------------------1-000n1
78 : -------------------------------- n0011-0------------------1-11101
79 : -------------------------------- u0101-0------------------1-01000
80 : --------------------------------
Tab. 6-4 Chemin diérentiel omplet pour le premier blo , pas 41 à 80.
99
Chapitre 6. A élération de la ryptanalyse de SHA-0
i ∇ Ai ∇W i
-4 : 111011010000101010001110101010u1
-3 : 01000110011100010110101100101000
-2 : 10010000011011111010001110100111
-1 : 11100110001011011100010100001001
00 : 01011110101010111100001100111101 1001101001110110110011110u1100n0
01 : u0111011010011100010111unn1010n1 0000010010111001100101010u111101
02 : 11010011001110011011u000110u0111 1110111000100100001000100n111101
03 : 111001111000010u000unnnnnn000100 1001101001000110011001001n110101
04 : u0100101unn01010000u100011110110 u011100001000000000010101u1101u0
05 : n000un001000011u00100000000nn0n0 u0111000011000000000011000010010
06 : nnn0010001011110011100n1nu1u011u u000101101111110100001011u101010
07 : 10nuuuuuuuuuuuuu11100n00un0u1001 11100001011111111111011000111100
08 : 0001111100000000unnn11010001n001 1010001011110001101110001u1001n1
09 : 00000111111111111110001n111un111 u100101000000111100110010n1101u0
10 : 1110110110111111110100nu111uu011 00000010111100001010011111001011
11 : 00111110010001010011011uu0n000u0 1111011101100100111010101n1110n0
12 : 010001101000111000111111nuu1u011 001101111111-------------n111010
13 : 101010000000----0--------01111u0 01010--------------------u0000u1
14 : 00110001-----------------1010010 10010------0----1--------00110n1
15 : 10011--------------------10101n0 n0110------0----1--------0111110
16 : 0-------------------------011000 10000--------------------11010u1
17 : 1-----------------------------n- u1000------1----1--------u100111
18 : 0------------------------------- 01100------1----0--------01111u0
19 : -------------------------------- n1010--------------------1110100
20 : -------------------------------- u1000------1-------------10000n1
21 : ------------------------------n- n1101--------------------u010011
22 : -------------------------------- 11101--------------------1100010
23 : ------------------------------n- u1011------0-------------u110101
24 : -------------------------------- n1001--------------------0010110
25 : ------------------------------u- 00010--------------------n001011
26 : -------------------------------- u0001------1-------------01110u0
27 : -------------------------------- 10111--------------------0011001
28 : -------------------------------- n1110--------------------1101001
29 : -------------------------------- u0000--------------------0010100
30 : -------------------------------- 01000--------------------0001001
31 : -------------------------------- 01011--------------------1000101
32 : -------------------------------- 00101--------------------1010111
33 : -------------------------------- 11000--------------------0010001
34 : -------------------------------- 01110--------------------00000n0
35 : ------------------------------n- 10101--------------------u101001
36 : -------------------------------- 10011--------------------10110u1
37 : -------------------------------- n1000--------------------01100u0
38 : ------------------------------u- n1001--------------------n010100
39 : -------------------------------- n0001--------------------11000n0
40 : -------------------------------- u0101--------------------1001001
··· ···
Tab. 6-5 Chemin diérentiel omplet pour le se ond blo , pas 1 à 40.
100
6-5. Con lusion
i ∇ Ai ∇W i
··· ···
41 : -------------------------------- n0100--------------------0010111
42 : -------------------------------- u0000--------------------01100u1
43 : ------------------------------u- 00111--------------------n101101
44 : -------------------------------- 10001--------------------01011n0
45 : -------------------------------- n0011--------------------1010000
46 : -------------------------------- n0011--------------------1100111
47 : -------------------------------- n0011--------------------0011000
48 : -------------------------------- 11101--------------------10011u0
49 : ------------------------------u- 01010--------------------n001000
50 : -------------------------------- 01110--------------------11100n0
51 : -------------------------------- n0111--------------------0111000
52 : -------------------------------- n0001--------------------1101011
53 : -------------------------------- n0100--------------------11100u0
54 : ------------------------------u- 11000--------------------n000010
55 : -------------------------------- 00111--------------------00001n0
56 : -------------------------------- u1100--------------------10001u0
57 : ------------------------------u- u0001--------------------n110000
58 : -------------------------------- n1000--------------------1101011
59 : ------------------------------u- u1111--------------------n0000u1
60 : ------------------------------u- n0010--------------------n0100n0
61 : -------------------------------- 01100--------------------10100n1
62 : -------------------------------- 11001--------------------0101000
63 : -------------------------------- 01100--------------------0000100
64 : -------------------------------- n0011--------------------0101001
65 : -------------------------------- 00101--------------------0101000
66 : -------------------------------- 01011--------------------11101n0
67 : ------------------------------n- 11111--------------------u100000
68 : -------------------------------- 11110--------------------10100n1
69 : -------------------------------- n0100--------------------1010011
70 : -------------------------------- n0010--------------------00011n0
71 : ------------------------------n- n0100--------------------u100001
72 : -------------------------------- 10011--------------------10101u1
73 : -------------------------------- n1001--------------------0010111
74 : -------------------------------- n0101--------------------1101110
75 : -------------------------------- u1111--------------------11001n1
76 : ------------------------------n- 01100--------------------u111110
77 : -------------------------------- 00001--------------------11010n0
78 : -------------------------------- n0111--------------------1101000
79 : -------------------------------- n0001--------------------0110011
80 : --------------------------------
Tab. 6-6 Chemin diérentiel omplet pour le se ond blo , pas 41 à 80.
101
Chapitre 6. A élération de la ryptanalyse de SHA-0
M1 M1′ M2 M2′
W0 0x4643450b 0x46434549 0x9a74 f70 0x9a74 f32
W1 0x41d35081 0x41d350 1 0x04f9957d 0x04f9953d
W2 0xfe16dd9b 0xfe16dddb 0xee26223d 0xee26227d
W3 0x3ba36244 0x3ba36204 0x9a06e4b5 0x9a06e4f5
W4 0xe6424055 0x66424017 0xb8408af6 0x38408ab4
W5 0x16 a44a0 0x96 a44a0 0xb8608612 0x38608612
W6 0x20f62444 0xa0f62404 0x8b7e0fea 0x0b7e0faa
W7 0x10f7465a 0x10f7465a 0xe17e363 0xe17e363
W8 0x5a711887 0x5a7118 5 0xa2f1b8e5 0xa2f1b8a7
W9 0x51479678 0xd147963a 0x a079936 0x4a079974
W10 0x726a0718 0x726a0718 0x02f2a7 b 0x02f2a7 b
W11 0x703f5bfb 0x703f5bb9 0xf724e838 0xf724e87a
W12 0xb7d61841 0xb7d61801 0x37ff 03a 0x37ff 07a
W13 0xa5280003 0xa5280041 0x53aa8 43 0x53aa8 01
W14 0x6b08d26e 0x6b08d26 0x90811819 0x9081181b
W15 0x2e4df0d8 0xae4df0d8 0x312d423e 0xb12d423e
Empreinte nale
A2 B2 C2 D2 E2
0x6f84b892 0x1f9f2aae 0x0dbab75 0x0afe56f5 0xa7974 90
Tab. 6-7 Exemple d'une paire de messages pour une ollision sur 2 blo s :
H(M1 , M2 ) = H(M1′ , M2′ ) = A2 ||B2 ||C2 ||D2 ||E2 , obtenue onformément au hemin
diérentiel présenté dans les tableaux 6-3, 6-4, 6-5 et 6-6.
102
7
Sommaire
7-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . 103
7-2 Algorithme de re her he de ve teur de perturbations104
7-2.1 Des ription de l'algorithme . . . . . . . . . . . . . . . . 104
7-2.2 Résultats expérimentaux . . . . . . . . . . . . . . . . . 107
7-3 Classi ation des ve teurs de perturbations . . . . . 108
7-3.1 Relation d'équivalen e . . . . . . . . . . . . . . . . . . 108
7-3.2 Nouvelle Notation . . . . . . . . . . . . . . . . . . . . . 109
7-4 Fon tion d'évaluation . . . . . . . . . . . . . . . . . . . 112
7-4.1 Fon tions de oût . . . . . . . . . . . . . . . . . . . . . 113
7-4.2 De l'e a ité à la omplexité . . . . . . . . . . . . . . 115
103
Chapitre 7. Amélioration de la ara téristique linéaire
| {z }
Wi , . . . , Wi+79
nous dénirons la lassi ation des ve teurs de perturbations que nous proposons.
Puis, nous lorons e hapitre par une revue des fon tions d'évaluation que nous
avons utilisées lors de nos expérimentations et dis uterons de leur adéquation ave
la omplexité d'une attaque par ollision ontre SHA-1.
104
7-2. Algorithme de re her he de ve teur de perturbations
W0 , . . . , W15 W0 , . . . , W15
Dans l'arti le de Wang et al., les perturbations ne pouvaient être introduites qu'aux
positions de bit 0 et 1. Le hoix de es deux positions étant dû au fait que la meilleure
probabilité théorique de bon omportement est obtenue pour la position de bit 1.
Cependant, Yajima et al. [YIN08, YIN09℄ utilisent une version étendue de et algo-
rithme autorisant l'insertion de perturbations sur la position de bit 31. Les tailles
des sous-espa es de re her he de es deux appro hes sont alors égales à 65 × 232 pour
la version de l'algorithme utilisée par l'équipe de Wang et 65 × 248 pour l'équipe de
Yajima. Le ompromis hoisi onsiste don à limiter les zones possibles pour l'inser-
tion de perturbations, le nombre de perturbations insérées pouvant varier de 1 à 32
pour la version de Wang, de 1 à 48 pour la version de Yajima.
Notre appro he onsidère un ompromis diérent illustré gure 7-2. Nous hoi-
sissons de limiter le nombre de perturbations sus eptibles d'être introduites mais
relâ hons la ontrainte de la position de bit où es perturbations sont autorisées. En
d'autres termes, nous limitons le poids de Hamming, noté w, de notre fenêtre d'in-
formation mais permettons aux perturbations d'apparaître n'importe où dans ette
fenêtre. La taille de notre sous-espa e de re her he est alors une fon tion de
w égale
w
à 65 × 512 . Le poids de Hamming de la fenêtre d'information onstitue le premier
paramètre utilisé par notre algorithme de re her he. L'utilisation d'un ompromis
diérent permet à notre algorithme d'explorer des régions de l'espa e de re her he
qui ne sont ouvertes ni par le sous-espa e de Wang et al., ni par le sous-espa e
étendu de Yajima et al.
105
Chapitre 7. Amélioration de la ara téristique linéaire
Certains des algorithmes présents dans la littérature ont utilisé une fon tion de
oût fondée sur le poids de Hamming des 60 dernières oordonnées du ve teur de
perturbations. C'est par exemple le as de l'appro he de Jutla and Patthak [JP05℄ qui
ont aussi démontré que le poids de Hamming minimal al ulé à partir des 60 dernières
oordonnées d'un ve teur de perturbations est égal à 25. Leur fon tion de oût est
dénie par le produit du poids de Hamming d'un ve teur andidat par une valeur
égale à la moyenne des probabilités théoriques de bon omportement d'une ollision
lo ale. Paradoxalement, bien que ette estimation puisse paraître assez grossière, les
ve teurs proposés dans leur arti le s'avèrent être parti ulièrement intéressants.
106
7-2. Algorithme de re her he de ve teur de perturbations
al. pré isent qu'ils utilisent leur propre algorithme pour re her her de bons ve teurs
de perturbations. Cependant, et algorithme et l'heuristique d'évaluation asso iée ne
sont détaillés dans au un de leurs arti les.
Pour les besoins de notre algorithme, nous avons été amenés à onstruire deux
fon tions de oûts ad ho . Ces fon tions seront expli itées dans la se tion 7-4.
107
Chapitre 7. Amélioration de la ara téristique linéaire
0 -------------------------------- --------------------------------
1 -------------------------------- o-------------------------------
2 -------------------------------- --------------------------------
3 -------------------------------- o-------------------------------
4 -------------------------------- --------------------------------
5 -------------------------------- --------------------------------
6 -------------------------------- --------------------------------
7 -------------------------------- --------------------------------
8 -------------------------------- --------------------------------
9 -------------------------------- --------------------------------
10 -------------------------------- --------------------------------
11 -------------------------------- --------------------------------
12 -------------------------------- --------------------------------
13 -------------------------------- --------------------------------
14 -------------------------------- --------------------------------
15 -------------------------------o -------------------------------o
Tab. 7-1 Fenêtres d'information onduisant aux ve teurs de perturbations les plus
e a es.
Il est intéressant de remarquer que ertaines des observations que nous avons
réalisées avaient été évoquées dans la littérature. Wang et al. [WYY05d℄ ont énon é
que diérents hoix de position de bit produisaient des ve teurs de perturbations
onstituants des opies d'autres ve teurs ave le même poids de Hamming. Rijmen
et Oswald [RO05℄ ont noté que les ve teurs obtenus grâ e à leur algorithme, désignés
sous le terme de mots de odes dans leur arti le, possédaient un grand nombre de
mots Wi en ommun. Jutla et Patthak [JP05℄ ont indiqué que le premier mot de ode
proposé dans leur arti le avait déjà été signalé par Wang et al. De la même façon,
Pramstaller et al. [PRR05℄ ont souligné que leur ve teur était le même que elui utilisé
par Wang et al. à une permutation des indi es prêt. Cependant, au une publi ation
antérieure à notre arti le [Man08℄ n'expliquait, ni ne proposait un modèle apable
de prendre en ompte es observations. L'interprétation des faits expérimentaux que
nous avons observés nous a onduit à on lure que les ve teurs de perturbations
e a es pouvaient être lassiés. Nous présentons ette lassi ation dans la se tion
suivante.
108
7-3. Classi ation des ve teurs de perturbations
les uns des autres. De la même façon, les 65 ve teurs de perturbations omposant
un message expansé étendu ne dièrent qu'à partir de l'indi e i (−64 ≤ i ≤ 0) d'où
les messages expansés valides débutent. En se fondant sur es deux propriétés, nous
pouvons dénir une relation d'équivalen e.
109
Chapitre 7. Amélioration de la ara téristique linéaire
-------------------------------- 0
-oo----------------------------- 1 0
-------------------------------- 2 1 0
-o-o---------------------------- 0 3 2 1
o------------------------------- 1 4 3 2
o------------------------------- 2 5 4 3
o-o----------------------------- 3 6 5 4
-o------------------------------ 4 0 7 6 5
-------------------------------- 5 1 8 7 6
-oo----------------------------- 6 2 9 8 7
o------------------------------- 7 3 10 9 8
o------------------------------- 8 4 0 11 10 9
o------------------------------- 9 5 1 12 11 10
-------------------------------- 10 6 2 0 13 12 11
-------------------------------- 11 7 3 1 14 13 12
-o------------------------------ 12 8 4 2 15 14 13
-------------------------------- 13 9 5 3 16 15 14
o-o----------------------------- 14 10 6 4 17 16 15 0
o------------------------------- 15 11 7 5 18 17 16 1
o-o----------------------------- 16 12 8 6 19 18 17 2
-------------------------------- 17 13 9 7 20 19 18 3
o------------------------------- 18 14 10 8 21 20 19 4
-------------------------------- 19 15 11 9 22 21 20 5
oo------------------------------ 20 16 12 10 23 22 21 6
-------------------------------- 21 17 13 11 24 23 22 7
o------------------------------- 22 18 14 12 25 24 23 8
o------------------------------- 23 19 15 13 26 25 24 9
-o------------------------------ 24 20 16 14 27 26 25 10
-------------------------------- 25 21 17 15 28 27 26 11
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
-------------------------------- 61 57 53 51 64 63 62 47
-------------------------------- 62 58 54 52 65 64 63 48
-------------------------------- 63 59 55 53 66 65 64 49
-------------------------------o 64 60 56 54 67 66 65 50
-------------------------------- 65 61 57 55 68 67 66 51
-------------------------------- 66 62 58 56 69 68 67 52
------------------------------o- 67 63 59 57 70 69 68 53
-------------------------------- 68 64 60 58 71 70 69 54
-------------------------------- 69 65 61 59 72 71 70 55
-----------------------------o-- 70 66 62 60 73 72 71 56
-------------------------------- 71 67 63 61 74 73 72 57
------------------------------o- 72 68 64 62 75 74 73 58
----------------------------o--- 73 69 65 63 76 75 74 59
-------------------------------- 74 70 66 64 77 76 75 60
-------------------------------- 75 71 67 65 78 77 76 61
---------------------------o---- 76 72 68 66 79 78 77 62
-------------------------------- 77 73 69 67 79 78 63
----------------------------o-o- 78 74 70 68 79 64
--------------------------o----- 79 75 71 69 65
-----------------------------oo- 76 72 70 66
-------------------------------- 77 73 71 67
-------------------------o------ 78 74 72 68
----------------------------o--- 79 75 73 69
--------------------------o-o--- 76 74 70
------------------------o------- 77 75 71
----------------------------o--- 78 76 72
-------------------------------- 79 77 73
-----------------------o----o--- 78 74
-------------------------------- 79 75
------------------------o-o----- 76
----------------------o--------- 77
-------------------------oo--o-- 78
-------------------------------- 79
110
7-3. Classi ation des ve teurs de perturbations
oo-o---------------------------- 0
o------------------------------- 1
ooo----------------------------- 2
o-o----------------------------- 3
---o---------------------------- 4
o------------------------------- 5 0
ooo----------------------------- 6 1
--o----------------------------- 7 2
oo-o---------------------------- 8 3
o------------------------------- 9 4
ooo----------------------------- 10 5
o-o----------------------------- 11 0 6
---o---------------------------- 12 1 7
o------------------------------- 13 2 8
ooo----------------------------- 14 3 9
--o----------------------------- 15 4 10
oo------------------------------ 16 5 11
o------------------------------- 17 6 12
-oo----------------------------- 18 7 13
o------------------------------- 19 8 14
oo------------------------------ 20 9 15
o------------------------------- 21 10 16
o-o----------------------------- 22 11 17
o------------------------------- 23 12 18
ooo----------------------------- 24 13 19
-------------------------------- 25 14 20
. . . .
. . . .
. . . .
-------------------------------- 61 51 57
-------------------------------- 62 52 58
-------------------------------- 63 53 59
-------------------------------- 64 54 60
-------------------------------- 65 55 61
-------------------------------- 66 56 62
-------------------------------- 67 57 63
-------------------------------- 68 58 64
-------------------------------- 69 59 65
-------------------------------- 70 60 66
-------------------------------o 71 61 67
-------------------------------- 72 62 68
-------------------------------- 73 63 69
------------------------------o- 74 64 70
-------------------------------o 75 65 71
-------------------------------- 76 66 72
-----------------------------o-- 77 67 73
------------------------------o- 78 68 74
------------------------------o- 79 69 75
----------------------------o--- 70 76
-----------------------------o-- 71 77
-------------------------------- 72 78
---------------------------o--o- 73 79
----------------------------o--- 74
----------------------------o-o- 75
--------------------------o----- 76
---------------------------o-oo- 77
-------------------------------- 78
--------------------------o--o-o 79
111
Chapitre 7. Amélioration de la ara téristique linéaire
58 pas I(43, 2)
80 pas I(49, 2)
Rijmen & Oswald CT-RSA 2005 [RO05℄
Codeword1 I(45, 1)
Codeword2 I(41, 1)
Codeword3 I(39, 1)
Jutla & Patthak ePrint 2005 [JP05℄
Codeword1 I(52, 0)
Codeword2 II(52, 0)
Codeword3 I(51, 0)
Pramstaller et al. IMA 2005 [PRR05℄ I(50, 2)
De Cannière & Re hberger ASIACRYPT 2006 [DCR06℄ I(35, 2)
De Cannière et al. SAC 2007 [DCM07℄ II(46, 2)
Yajima et al. ASIACCS 2008 [YIN08℄ II(56, 2)
Bien que des ve teurs de perturbations d'une même lasse soient par dénition
équivalents, l'e a ité de es ve teurs peut varier dans de grandes proportions. Nous
dé rivons les fon tions de oût que nous avons dénies pour réaliser l'évaluation de
l'e a ité des ve teurs de perturbations dans la se tion suivante.
112
7-4. Fon tion d'évaluation
Nous allons à présent, dé rire les deux fon tions de oût que nous avons utilisées
lors de nos expérimentations.
7-4.1.1 Rationale
Pour onstruire nos fon tions de oût, nous nous sommes appuyés sur un ertain
nombre d'hypothèses présentes dans la littérature.
Nous avons hoisi de ommen er l'évaluation des ve teurs au pas 21. En eet,
les arti les de Wang et al. [WYY05b, WYY05 ℄ ont montré qu'il était possible
de trouver des modi ations de messages avan ées permettant de s'assurer du
bon omportement des ollisions lo ales au moins jusqu'à e pas.
De la même façon que dans [DCM07℄, nous avons hoisi d'ignorer les ondi-
tions liées aux retenues pour les pas 79 et 80. En eet pour le premier blo
de la ollision, es onditions peuvent être gérées par la ara téristique non-
linéaire appliquée au se ond blo . De plus notre obje tif onsistant à obtenir
une estimation de l'e a ité d'un ve teur de perturbation donné, il ne nous
a pas semblé omplètement déraisonnable de ne pas prendre en ompte es
onditions.
Nos deux fon tions de oût intègrent aussi les te hniques de ompression de
bits, dé rites dans [WYY05b℄ et [YIN08℄.
L'évaluation des ve teurs de perturbations andidats que nous avons hoisie repose
sur l'appro he probabiliste. La fon tion de oût 1 utilise les probabilités théoriques
de bon omportement des ollisions lo ales que l'on peut retrouver dans l'arti le de
Mendel et al. [MPR06℄. La fon tion de oût 2 utilise les probabilités données par les
tables B.1 et B.2 de l'annexe B de la thèse de Thomas Peyrin [Pey08℄.
Nous rappelons que es fon tions n'ont pas pour but de donner une évaluation
pré ise et dénitive de la omplexité d'une attaque par ollision ontre SHA-1. Leur
obje tif est de permettre de déterminer de façon grossière mais rapide quels sont
parmi tous les ve teurs andidats, les ve teurs sus eptibles d'être les plus perfor-
mants. En outre, nous soulignons le fait que la fon tion de oût ne onstitue qu'un
paramètre de l'algorithme et que elui- i est à même de fon tionner ave n'importe
quelle fon tion de oût.
113
Chapitre 7. Amélioration de la ara téristique linéaire
58 pas 33 35 35
80 pas 69 73 73
80 pas
Codeword1 - 90 90
Codeword2 - 97 97
Codeword3 - 102 102
80 pas
Codeword1 - 70 76
Codeword2 - 65 69
Codeword3 - 71 76
80 pas - 73 73
Tab. 7-5 Comparaison de l'évaluation, relativement aux fon tions de oûts que
nous avons hoisies, de l'e a ité des ve teurs de perturbations publiés. L'évaluation
1 (respe tivement 2) se fonde sur l'arti le de Mendel et al. (respe tivement la thèse
de Peyrin).
façon assez pertinente l'e a ité des ve teurs de perturbations. Nous notons aussi
que le ve teur de perturbations le plus performant, relativement aux fon tions de
oûts que nous avons hoisies, est le ve teur désigné sous le nom de Codeword2
dé rit pour la première fois par Jutla et Patthak dans [JP05℄.
114
7-4. Fon tion d'évaluation
ations de message avan ées e a es. Cependant si l'on a epte l'hypothèse de leur
existen e, le meilleur ve teur de perturbations obtenu ave ette fon tion optimiste
est le ve teur noté II(49, 0). M Donald et al. ont présenté durant la Rump session
d'EUROCRYPT'09 une attaque par ollision fondée sur e ve teur.
115
Chapitre 7. Amélioration de la ara téristique linéaire
116
8
Évaluation Statistique du
omportement des ollisions
lo ales
Sommaire
8-1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . 117
8-2 Pro édure expérimentale . . . . . . . . . . . . . . . . 118
8-3 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8-3.1 Collision lo ale isolée . . . . . . . . . . . . . . . . . . . 119
8-3.2 Collision lo ales adja entes . . . . . . . . . . . . . . . . 121
8-3.3 Collision lo ales onsé utives . . . . . . . . . . . . . . . 121
8-3.4 Collisions lo ales alternées . . . . . . . . . . . . . . . . 122
8-4 Con lusion . . . . . . . . . . . . . . . . . . . . . . . . . 124
117
Chapitre 8. Évaluation Statistique du omportement des ollisions lo ales
Le nombre de test T est xé à 220 , e qui permet d'obtenir une pré ision relative de
0.01 pour le logarithme de la probabilité.
La pro édure basique d'expérimentation onsiste à tirer aléatoirement un état
initial pour les registres et à générer une paire de message aléatoire se onformant au
patron de ollision lo ale. Puis, haque message est utilisé pour al uler parallèlement
les nouveaux états des registres pour le nombre de pas S né essaire. Finalement, les
deux états nals sont omparés an de vérier si on retrouve ee tivement une ol-
lision. Cette expérien e est reproduite le nombre de fois T né essaire pour obtenir la
pré ision désirée. Pour un type de patron donné toutes les positions de bits possibles
sont testées.
118
8-3. Résultats
Cal uler (A′1 , . . . , A′S ) selon la fon tion de mise à jour des
(A1 , . . . , AS ) et
registres ave la fon tion de ronde f
if (AS−4 ⊕ A′S−4 = AS−3 ⊕ A′S−3 = AS−2 ⊕ A′S−2 = AS−1 ⊕ A′S−1 =
AS ⊕ A′S = 0) then
mi ← mi + 1
end if
end for
end for
Pb ← (m1 + m2 + m3 )/(3 × T )
end for
return P0 , . . . , P31
Une fois ette pro édure dénie, nous avons testé le omportement de diérents
patrons de ollisions lo ales présents dans les ve teurs de perturbations de type-I et
de type-II.
8-3 Résultats
8-3.1 Collision lo ale isolée
Le premier patron de ollision lo ale que nous avons onsidéré est le as d'une
ollision lo ale isolée. Les diérentes probabilités de bon omportement que nous
avons mesurées sont listées dans le tableau 8-1. Les valeurs orrespondant aux pro-
babilités théoriques de bon omportement sont représentées entre parenthèses. La
notation [4.85,4.87℄ indique que les probabilités mesurées varient entre les valeurs
2−4.85 et 2−4.87 selon les diérentes positions de bit onsidérées. Ces résultats sont
ompatibles ave l'analyse fondée sur l'impa t des retenues proposée dans [MPR06℄.
Nous signalons ependant une erreur
3 ontenue dans l'arti le on ernant la proba-
bilité de bon omportement initiée à la position de bit 31 dans une ronde de M AJ .
Cette probabilité est égale à 2−4 et non 2−3 .
Nous pouvons observer que les valeurs mesurées sont égales aux probabilités
théoriques pour les positions de bit 1, 26 et 31. Les probabilités obtenues pour les
autres positions sont légèrement meilleures que les probabilité théoriques du fait de
l'eet de propagation des retenues. Cependant, et eet peut être détruit s'il est
amené à dépasser la position de bit 31, ar à ette position la retenue est ignorée
3
Cette erreur a aussi été remarquée par Thomas Peyrin dans sa thèse.
119
Chapitre 8. Évaluation Statistique du omportement des ollisions lo ales
(addition modulo 232 ). Les perturbations initiées sur les positions de bit 1, 26 ou
31 orrespondent, ou impliquent des orre tions relatives à des modi ations sur la
position de bit 31. Ce i est le fait des valeurs des permutations ir ulaires présentes
dans la formule de mise à jour des registres. Les ollisions lo ales initiées sur ses
positions de bit ne peuvent don pas béné ier de l'eet de propagation des retenues
qui améliore les probabilités sur les autres positions de bit. Pour la fon tion XOR la
probabilité de bon omportement en fon tion de la position de bit b, notée p(XOR, b)
est égale à :
2−4 + 2−6 for b=0
2−2 for b=1
p(XOR, b) = P27−b −4k
k=1 2
for b = 2, . . . , 26
2.2−4.(32−b) + P31−b 2−4k
for b = 27, . . . , 31
k=1
Patron -------------------------------o
Position de bit b 0 1 2, . . . , 25 26 27,28,29 30 31
Tab. 8-1 Probabilités de bon omportement mesurées pour une ollision lo ale
isolée se déroulant entièrement au sein d'une même fon tion de ronde. Les valeurs
présentées sont les moyennes observées sur 3 expérien es omprenant 220 tests ha-
une.
Nous avons présenté dans la table 8-1 les probabilités de bon omportement pour
la fon tion de ronde IF . Dans nos expérien es suivantes, nous avons hoisi d'ignorer
ette fon tion ar on attend de la ara téristique non-linéaire de prendre en main le
omportement des ollisions lo ales pour ette ronde.
120
8-3. Résultats
121
Chapitre 8. Évaluation Statistique du omportement des ollisions lo ales
Patron -------------------------------oo
Position de bit b 0 1 2, . . . , 23 24 25 26 27 28 29 30
−+ 3.68 5.91 [3.90, 3.91℄ 3.91 3.91 7.90 3.91 3.91 3.90 3.83
+− 3.68 5.90 [3.90, 3.91℄ 3.91 3.91 7.91 3.90 3.91 3.90 3.83
(4) (6) (4) (4) (4) (8) (4) (4) (4) (4)
−− 8.00 7.90 [6.90, 6.91℄ 6.96 7.99 7.90 6.91 6.91 6.95 8.00
MAJ ++ 8.00 7.91 [6.90, 6.91℄ 6.96 8.00 7.91 6.91 6.91 6.95 8.00
(8) (8) (8) (8) (8) (8) (8) (8) (8) (8)
−+ 3.91 7.91 [3.90, 3.91℄ 3.91 3.91 7.91 3.91 3.91 3.91 3.91
+− 3.91 7.91 [3.90, 3.91℄ 3.91 3.91 7.91 3.91 3.91 3.91 3.91
(4) (8) (4) (4) (4) (8) (4) (4) (4) (4)
Tab. 8-2 Probabilités de bon omportement de deux ollisions lo ales adja entes se
déroulant entièrement au sein d'une même fon tion de ronde. Les valeurs présentées
sont les moyennes observées sur 3 expérien es omprenant 224 tests ha une.
Nos expérien es montrent que même lorsque les signes sont égaux, l'existen e de
hemins diérentiels impossibles ne semble être établie que pour les positions de bit 1,
26 et 31. Pour les autres positions de bit, ertaines paires de message sont parvenues à
former une ollision, ave ependant une probabilité de bon omportement inférieure
(pro he de 2−10 ) à la probabilité théorique de bon omportement ave signes opposés
(2
−8 ). Lorsque les signes des ollisions lo ales sont ee tivement opposés, on peut
observer que les probabilités mesurées sont meilleures que les probabilités théoriques
(autour de 2−6 au lieu de 2−8 ).
Cette amélioration des probabilités théoriques est aussi présente pour la fon tion
de ronde XOR. À l'ex eption de la position de bit 1, et quelle que soit la ombinaison
de signes, les probabilités mesurées sont meilleures que prévues. Cela est parti uliè-
rement intéressant pour la position de bit 31. Pour e type d'en hevêtrement de
ollisions lo ales, on peut remarquer que la position de bit 1 n'est plus ex lusivement
elle qui donne la meilleure probabilité de bon omportement.
122
8-3. Résultats
Patron -------------------------------o
-------------------------------o
Position de bit b 0 1 2, . . . , 24 25 26 27,28,29 30 31
−− 10.01 > 24 [9.88, 9.92℄ 9.99 > 24 [9.91, 9.92℄ 9.99 > 24
MAJ ++ 10.00 > 24 [9.88, 9.92℄ 10.00 > 24 [9.90, 9.91℄ 10.01 > 24
(∞) (∞ ) (∞ ) (∞) (∞) (∞) (∞) (∞)
−+ 5.98 6.00 [5.97, 5.98℄ 5.98 6.00 5.98 5.98 6.00
+− 5.98 6.00 [5.97, 5.98℄ 5.98 6.00 5.98 5.98 6.00
(8) (8) (8) (8) (8) (8) (8) (8)
Tab. 8-3 Probabilités de bon omportement de deux ollisions lo ales onsé utives
(démarrant au pas i et i + 1) se déroulant entièrement au sein d'une même fon tion
de ronde. Les valeurs présentées sont les moyennes observées sur 3 expérien es om-
prenant 224 tests ha une. La notation "> 24" désigne le fait qu'au une ollision n'a
été trouvée lors des trois expérien es, la probabilité de bon omportement orres-
pondante est don stri tement inférieure à 2
−24 . La notation ∞ désigne un hemin
diérentiel théoriquement impossible.
des dire tions opposées, et la position de bit 31 ave une même dire tion, au une
ollision ne s'est jamais produite au ours des 3 expérien es omportant 224 essais
ha une. D'un point de vue statistique, ela peut signier que la probabilité d'ob-
tenir une ollision est inférieure à 2−25 , ou bien que nous sommes onfrontés à des
hemins diérentiels impossibles et don à de nouveaux as pathologiques. Le même
type de omportement peut être observé pour la position de bit 26, et e quelque soit
la onguration des dire tions des ollisions lo ales. Nous en déduisons qu'il s'agit
là d'un réel nouveau as pathologique. L'observation de es omportements n'a, à
notre onnaissan e, jamais fait l'objet d'une publi ation antérieure à notre arti le
[Man10℄.
Nous remarquons de plus, que la probabilité théorique n'est atteinte que dans
seulement 4 ongurations :
123
Chapitre 8. Évaluation Statistique du omportement des ollisions lo ales
Patron -------------------------------o
--------------------------------
-------------------------------o
Position de bit b 0 1 2, . . . , 24 25 26 27,28,29 30 31
−− 11.88 8.00 [11.77, 11.82℄ 11.91 > 24 [11.80, 11.82℄ 11.91 > 24
MAJ ++ 11.91 7.99 [11.79, 11.82℄ 11.90 > 24 [11.81, 11.82℄ 11.91 > 24
+− 11.89 > 24 [11.58, 11.62℄ 11.90 > 24 [11.60, 11.63℄ 11.93 8.00
−+ 11.92 > 24 [11.58, 11.63℄ 11.90 > 24 [11.58, 11.63℄ 11.89 8.00
(8) (8) (8) (8) (8) (8) (8) (8)
124
8-4. Con lusion
125
Chapitre 8. Évaluation Statistique du omportement des ollisions lo ales
126
Troisième partie
127
9
Sommaire
9-1 La fon tion XOR-Hash . . . . . . . . . . . . . . . . . . 129
9-1.1 Travaux onnexes . . . . . . . . . . . . . . . . . . . . . 130
9-1.2 Des ription de XOR-Hash . . . . . . . . . . . . . . . . 132
9-1.3 Analyse de sé urité . . . . . . . . . . . . . . . . . . . . 136
9-1.4 Con lusion . . . . . . . . . . . . . . . . . . . . . . . . . 137
9-2 La fon tion FSB . . . . . . . . . . . . . . . . . . . . . . 138
9-2.1 Des ription . . . . . . . . . . . . . . . . . . . . . . . . . 138
9-2.2 Sé urité . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9-2.3 Con lusion . . . . . . . . . . . . . . . . . . . . . . . . . 139
129
Chapitre 9. Les fon tions XOR-Hash et FSB
Famille de fon tions FSB. En 2005 [AFS05℄, Augot et al. ont présenté une fa-
mille de fon tions de ompression fondées sur la théorie des odes. Ces fon tions
utilisent une fon tion de syndrome régulier, onsistant à xorer un petit nombre t
des olonnes d'une matri e aléatoire donnée omme paramètre. Les résistan es aux
ollisions et au al ul d'anté édent de ette famille de fon tions de ompression se
fondent sur une rédu tion vers des problèmes di iles de théorie des odes. Les au-
teurs ont démontré que le dé odage de syndrome régulier ainsi que le dé odage de
syndrome régulier double sont des problèmes NP- omplets. Ces fon tions de om-
pression sont paramétrables et leurs paramètres sont déterminés respe tivement aux
deux meilleures attaques onnues qui sont l'algorithme du paradoxe des anniversaires
généralisé de Wagner [Wag02℄ et l'algorithme de dé odage par ensemble d'informa-
tion de Canteaut-Chabaud [CC98℄.
La fon tion de ha hage ryptographique FSB repose sur une instan e de ette
famille de fon tions de ompression, nous dé rirons la fon tion FSB dans le hapitre
suivant.
Bellare et al. ont prouvé que pour une famille sûre de fon tions pseudo-aléatoires,
les s hémas XOR-MAC fondés sur ette famille sont sûrs.
130
9-1. La fon tion XOR-Hash
? ? ?
f f ... f
y1 XX y2 yℓ
XXX S
XX
XXXS
XS
z w 9
•
?
Empreinte
L'avantage prin ipal de e type de onstru tion réside dans son ara tère in ré-
mental. Si l'empreinte d'un message x modié en x′ a déjà été al ulée, la nouvelle
empreinte orrespondant au
′
message x peut être obtenue de façon e a e. Plutt
que de re al uler entièrement ette empreinte, on peut mettre à jour l'empreinte
pré édente en un temps proportionnel au montant des modi ations apportées à x
pour obtenir x′ .
Bellare et Mi ian io ont proposé diérentes solutions fondées sur diérents opé-
rateurs de ombinaisons, trois de es solutions possèdent des rédu tions de sé urité.
Par exemple, la résistan e aux ollisions de la fon tion MuHASH, qui utilise une
multipli ation omme opérateur de ombinaison, peut se réduire à la résolution du
problème du logarithme dis ret sous l'hypothèse que la fon tion de randomisation
f est modélisée en tant que fon tion de ha hage idéale. L'opérateur de ombinaison
xor n'a pas été retenu par Bellare et Mi ian io. En eet, la variante XHASH s'est
révélée ne pas être sûre même si la fon tion f est un ora le aléatoire. Il existe une
attaque utilisant l'algèbre linéaire e a e pour des messages très longs.
Cependant, nous soutenons qu'une fon tion de ha hage fondée sur le xor omme
131
Chapitre 9. Les fon tions XOR-Hash et FSB
opérateur de ombinaison peut être sûre, tant que le nombre de ombinaisons est
inférieur ou égal à un paramètre de sé urité. La fon tion XOR-Hash est fondée sur
e paradigme.
Rumba20. En 2007 [Ber07a℄, une nouvelle onstru tion utilisant le prin ipe de [BM97℄
a été proposée. Bernstein a présenté lors du Workshop ECRYPT sur les fon tions
de ha hage ryptographiques la fon tion Rumba20. Cette fon tion de ompression
est fondée sur le paradigme de randomisation puis ombinaison ave un nombre de
ombinaisons xé à 4 xor bit à bit.
La randomisation est faite à l'aide de 4 diérentes instan es f1 , f2 , f3 et f4 du
s héma de hirement à ot Salsa20 [Ber07b℄. Chaque instan e fi est une expan-
sion de 384 bits vers 512 bits, fi : {0, 1}384 → {0, 1}512 . L'entrée de la fon tion de
ompression (la variable de haînage pré édente et le blo de message ourant) est
dé oupée en 4 sous-blo s (x1 , x2 , x3 , x4 ). La sortie de la fon tion de ompression est
égale à f1 (x1 ) ⊕ f2 (x2 ) ⊕ f3 (x3 ) ⊕ f4 (x4 ).
L'algorithme du paradoxe des anniversaires généralisé de Wagner est onsidéré
omme étant l'attaque la plus e a e ontre ette fon tion. Les arguments de sé urité
de Rumba20 reposent sur une estimation détaillée, dé rite dans l'arti le, du oût de
ette attaque.
Constru tion hybride . La onstru tion hybride est une appro he intermédiaire
entre le paradigme de randomisation puis ombinaison et les onstru tions de fon -
tions de ompression lassiques. Le résultat de haque ombinaison est sto ké dans
un a umulateur H, pré-rempli ave la randomisation d'une valeur initiale IV . Le
paramètre de sé urité t onstitue le nombre maximum de valeurs randomisées qui
seront ombinées. L'idée fondamentale de la onstru tion hybride onsiste à nourrir
l'a umulateur H jusqu'à e que le paramètre de sé urité t soit atteint. Lorsque t−1
132
9-1. La fon tion XOR-Hash
ombinaisons ont été faites, la valeur ourante de l'a umulateur H est tronquée et
utilisée omme nouvelle valeur initiale H̃ . Pour des messages de taille multiple de
t − 1, le omportement de la onstru tion hybride est similaire à une onstru tion
itérative de type Merkle-Damgård.
Modèle d'attaques. Pour les fon tions de la famille FSB et la fon tion Rumba20,
on onsidère que la meilleure attaque onnue est l'algorithme du paradoxe des an-
niversaires généralisé de Wagner. Le prin ipe de onstru tion de XOR-Hash est si-
milaire, bien que diérent, à es deux propositions. Il semble don raisonnable de
onsidérer ette attaque omme la plus signi ative lors de l'évaluation de la sé u-
rité de XOR-Hash. Nous dis uterons des impératifs de sé urité relatifs à la fon tion
de randomisation f et à la fon tion de transformation nale g dans la se tion 9-1.3.
1. La première étape onsiste à al uler la valeur initiale devant être sto kée dans
l'a umulateur : H = f (h0i k IV ).
2. Puis deux ompteurs sont initialisés : le ompteur i désigne le numéro du blo
de message ourant et le ompteur j le nombre de valeurs randomisées destinées
à être ombinées.
(a) Si t valeurs ont déjà été ombinées : tronquer les r − ⌈log2 t⌉ bits les plus
à droite de H, les utiliser omme variable de haînage H̃ an de al uler
la nouvelle valeur initiale de l'a umulateur puis re ommen er un y le
de ombinaisons en posant j = 1.
(b) Combiner la valeur randomisée ourante f (hji k mi ) ave la valeur ou-
rante de l'a umulateur, et sto ker le résultat.
133
Chapitre 9. Les fon tions XOR-Hash et FSB
Algorithm 6 XOR-Hash
Require: IV, m1 , . . . , mℓ ∈ {0, 1}r−⌈log2 t⌉
H ← f (h0i k IV )
i ← 1; j ← 1
while i ≤ ℓ do
if j = t then
H̃ ← hopr−⌈log2 t⌉ (H)
H ← f (h0i k H̃)
j←1
end if
H ← H ⊕ f (hji k mi )
i ← i + 1; j ← j + 1
end while
return g(H)
Il est important de noter que nous n'instantions pas les fon tions f et g. Le
prin ipe de notre onstru tion de fon tion de ha hage munie d'une transformation de
sortie onsiste d'une part à proposer une nouvelle fon tion de ompression fondée sur
une fon tion à sens unique, et d'autre part à évaluer la sé urité de notre onstru tion
relativement aux propriétés de ette fon tion de ompression et de la transformation
de sortie. Nous dis uterons dans la se tion 9-1.3 des impératifs de sé urité que nous
avons identié pour es deux fon tions.
134
9-1. La fon tion XOR-Hash
? ? ? ?
f f f ... f
? ? ?
- +m - +m ... - +m
H
?
h0i k H̃ h1i k mt h2i k mt+1 hℓ mod ti k mℓ
? ? ? ?
f f f ... f
? ? ?
- +m - +m ... - +m
H
?
@
@ g
@
?
h(m)
égal à 2. An de simplier la omparaison ave des onstru tions itératives lassiques,
nous hoisissons de dénir le taux de ha hage de notre onstru tion omme pour une
fon tion de ompression ave un nombre xe t de ombinaisons.
Puisque r est de l'ordre de quelques entaines de bits et que t varie de 2 à 8, on
a (r − ⌈log2 t⌉) ≈ r . En onséquen e :
t
Hrf ≈ ,
t−1
e qui onstitue un taux de ha hage e a e.
135
Chapitre 9. Les fon tions XOR-Hash et FSB
hypothèses sur lesquelles réside la sé urité de notre onstru tion prennent en ompte
le prin ipe de la onstru tion hybride.
Fon tion de ha hage sûre et fon tion de ha hage idéale. Une fon tion de
ha hage idéale h produisant des empreintes de taille n bits se doit de vérier les pro-
priétés lassiques exigées des fon tions de ha hage ryptographiques. Les attaques
par re her he d'anté édent et de se ond anté édent doivent né essiter O(2n ) évalua-
tions de ette fon tion, O(2
n/2 ) évaluations pour une attaque par ollision. Nous re-
marquons que dans le livre référen e : Handbook of Applied Cryptography [MOV96℄,
la notion de fon tion de ha hage ryptographique sûre requiert seulement que es
attaques soient hors de portée d'un adversaire (Computationally Infeasible ). Bien
évidemment une fon tion de ha hage idéale onstitue une fon tion de ha hage sûre.
Cependant une fon tion de ha hage qui ne vérie pas de façon idéale les propriétés
de résistan e au al ul d'anté édent et de se ond anté édent, peut tout de même
onstituer une fon tion de ha hage sûre.
Ainsi l'obje tif de sé urité que nous nous xons est de produire une fon tion de
ha hage sûre. Le oût des attaques lassiques doit être au delà de la puissan e de
al ul d'un adversaire.
Problèmes. Dans le but d'estimer la sé urité de notre onstru tion, nous dénis-
sons une liste des problèmes que doit résoudre un attaquant an de mener à bien
une attaque ontre la fon tion XOR-Hash.
136
9-1. La fon tion XOR-Hash
revient à dé oder un syndrome pour une matri e aléatoire de dimensions (r, 2r ). Ces
problèmes ont été traités dans l'arti le de Augot et al. [AFS05℄.
Le Problème 4 pose omme exigen e pour la fon tion g de résister au al ul
d'anté édent.
Les Problèmes 5 et 6 impliquent les deux fon tions f et g. Dans une ertaine
mesure, ils expriment une ertaine forme d'indépendan e entre f et de g :
La résistan e au Problème 5 induit une résistan e aux ollisions pour g re-
lativement à f. Il ne sut pas à un attaquant de pouvoir trouver une olli-
sion aléatoire (indépendamment de f) pour g, pour être apable de asser le
s héma.
La résistan e au Problème 6 induit une résistan e au al ul de se ond anté-
édent pour g relativement à f. Il ne sut pas à un attaquant de pouvoir
trouver un se ond anté édent aléatoire (indépendamment de f ) pour g, pour
être apable de asser le s héma.
1. Nous onje turons que les résistan es aux attaques par ollisions, par al ul
d'anté édent et par al ul de se ond anté édent de notre fon tion de ha hage
se réduisent à l'un des six problèmes énumérés pré édemment.
Sous es hypothèses, notre onstru tion fournit au moins r/(2 + log2 t) bits de
sé urité ontre les attaques par ollision. Nous hoisissons don en onséquen e le
paramètre n (la taille de la sortie de g) égal à 2r/(2+log2 t). Nous présentons table 9-1
quelques hoix de paramètres de sé urité sûrs pour la résistan e aux ollisions.
137
Chapitre 9. Les fon tions XOR-Hash et FSB
2k k × (2 + ℓ) 2ℓ 2k ≈ t/(t − 1)
Tab. 9-1 Paramètres de sé urité résistants aux attaques par ollision pour la fon -
tion XOR-Hash.
La fon tion de ompression prin ipale prend omme argument une haîne de
bits de taille s et produit en sortie une haîne de bits de taille r. Elle utilise des
te hniques de théorie des odes pour al uler le syndrome d'un mot binaire, dérivé
du blo de message et de la variable de haînage en entrée, pour produire la nouvelle
variable de haînage. En pratique, la sortie de ette fon tion est onstituée du XOR
de permutations ir ulaires d'un ensemble de ve teurs prédénis. L'ensemble de tous
les ve teurs possibles onstitue les olonnes d'une matri e H de taille r × n. Le
pro essus interne à ette fon tion onsiste don à générer un mot binaire parti ulier
(appelé mot régulier) de longueur n et de poids de Hamming w puis à le multiplier
par la matri e H . Du point de vue de la théorie des odes, e mot de poids w peut être
interprété omme un motif d'erreur, et la multipli ation par la matri e H omme
le al ul du syndrome de ette erreur. La fon tion de ompression se ondaire est
onstruite à partir de la fon tion Whirlpool [BR00℄. Lors de la dernière itération
de la fon tion de ompression prin ipale, une variable de haînage de taille r bits
est obtenue. Cette variable est alors à son tour ompressée par l'appli ation de la
fon tion de ha hage Whirlpool pour produire un ha hé de taille 512 bits. Ce ha hé
138
9-2. La fon tion FSB
Tab. 9-2 Paramètres pour les 5 versions de la fon tion de ha hage FSB.
est alors tronqué pour produire une empreinte pour le message orrespondant à la
taille désirée.
La fon tion de ha hage ryptographique FSB soumise au NIST se dé line en 5
versions que nous résumons dans le tableau 9-2.
9-2.2 Sé urité
Les meilleures attaques ontre la fon tion de ompression prin ipale sont bien
identiées et il est possible d'évaluer pré isément leur omplexité. Le tableau 9-3
donne les omplexités des diérentes attaques qui ont été prises en ompte lors de la
séle tion des paramètres pour la fon tion de ha hage FSB. Le hoix de l'utilisation de
l'algorithme de Merkle-Damgård en tant qu'extenseur de domaine et de la fon tion
Whirpool en tant que fon tion de ompression nale ont été fait dans le but de
préserver autant que possible la sé urité de la fon tion de ompression prin ipale. Si
nous notons CF ette fon tion de ompression et HF la fon tion de ha hage dans
son ensemble, nous avons :
139
Chapitre 9. Les fon tions XOR-Hash et FSB
Tab. 9-3 Complexité des meilleures attaques onnues ontre la fon tion de om-
pression prin ipale de FSB. La notation GBA indique l'algorithme du paradoxe des
anniversaires généralisé, la notation ISD indique l'algorithme de dé odage par en-
semble d'information.
des ription est de l'ordre de 2Mb, e qui peut onstituer un désavantage pour les
implémentations en hardware. Elle onstitue ependant, la fon tion de ha hage la
plus rapide pour laquelle il existe des rédu tions de sé urité stri tes vers un problème
algorithmique di ile.
140
Quatrième partie
141
10
Con lusions
La majorité des années de ette thèse a été onsa rée à l'étude des fon tions de
ha hage SHA-0 et SHA-1, et plus parti ulièrement aux ryptanalyses de es fon tions.
L'analyse de es ryptanalyses a né essité un fort investissement en terme d'énergie et
de temps ; et investissement à toutefois porté ses fruits. D'un point de vue pratique,
nous avons ave Thomas Peyrin publié en 2008 une attaque ontre la fon tion SHA-
0, qui reste à e jour la meilleure attaque par ollision publiée pour ette fon tion.
Con ernant la fon tion SHA-1, un travail plus théorique, entré sur la ara téristique
linéaire, a aboutit à une lassi ation des ve teurs de perturbations ainsi qu'à la mise
à jour de omportements non répertoriés de ertains en hevêtrements de ollisions
lo ales.
La se onde partie du travail mené l'a été sous la forme de la on eption ave
Ni olas Sendrier de la fon tion XOR-Hash. La fon tion proposée onstitue un modèle
de on eption de type oquille vide (Empty Shell Constru tion ), dont nous avons relié
la sé urité à un ertain nombre de problèmes que nous avons dénis. Nous avons été
de plus invité à ollaborer au pro essus qui à onduit à la proposition de la fon tion
de ha hage FSB en réponse à la ompétition organisée par le NIST.
Durant la dernière année de ette thèse, dans le adre de l'emploi d'un poste
d'ATER, nous avons ave l'équipe IA de l'université Paris 8 produit un arti le relatif
à la olorisation d'images segmentées a epté pour la onféren e SITIS 2010. Cette
in ursion dans le domaine de la synthèse d'image (bien éloigné de elui des fon tions
de ha hage ryptographiques) nous a permit de onstater que les ompéten es de re-
her he a quises durant ette thèse pouvaient être mises au servi e d'autres domaines
de l'informatique.
Perspe tives
Comme nous avons pu le détailler dans ette thèse, une attaque par ollision
ontre la fon tions SHA-1 né essite la mise en oeuvre de modèles, de te hniques et
d'outils variés. Le modèle de ollision lo ale introduit par Chabaud et Joux et la
onstru tion de ve teurs de perturbations onstitue sans doute la meilleure appro he
dont nous disposons. La génération de ara téristiques non-linéaires, bien que repré-
sentant une di ulté ertaine relativement à son implémentation en tant qu'outil
143
Chapitre 10. Con lusions et perspe tives
144
Bibliographie
[ABD09℄ E. Andreeva, C. Bouillaguet, O. Dunkelman, and J. Kelsey, Herding, se ond
preimage and trojan message atta ks beyond merkle-damgard. In M. J. Ja obson
Sele ted Areas in Cryptography - SAC
Jr., V. Rijmen and R. Safavi-Naini editors,
2009, Le ture Notes in Computer S ien e 5867, pages 393-414. Springer Verlag,
2009.
[BR00℄ P. Barreto and V. Rijmen, The Whirlpool Hashing Fun tion. Available
at http ://[Link]. [Link]/informati a/paulobarreto/[Link].
First version in 2000 revised in May 2003.
[BGR95℄ M. Bellare, R. Guerin and P. Rogaway, XOR MACs : New Methods for Mes-
sage Authenti ation Using Finite Pseudorandom Fun tions. In D. Coppersmith
editor,Advan es in Cryptology - CRYPTO 1995, Le ture Notes in Computer
S ien e 963, pages 15-20. Springer Verlag, 1995.
[BM97℄ M. Bellare and D. Mi ian io, A New Paradigm for Collision-free Hashing :
Advan es in Cryptology
In rementality at Redu ed Cost. In W. Fumy editor,
- EUROCRYPT 1997, Le ture Notes in Computer S ien e 963, pages 15-20.
Springer Verlag, 1997.
145
Bibliographie
[BR93℄ M. Bellare and P. Rogaway, Random Ora les are Pra ti al : A paradigm for
Designing E ient Proto ols. ACM Conferen e on Computer and Communi a-
tions Se urity 1993, pages 62-73. ACM, 1993.
[Ber92℄ T. A. Berson, Dierential Cryptanalysis Mod 232 with Appli ations to MD5.
In R. A. Rueppel editor, Advan es in Cryptology - EUROCRYPT 1992, Le ture
Notes in Computer S ien e 658, pages 71-80. Springer Verlag, 1993.
[BDP06℄ G. Bertoni, J. Daemen, M. Peeters and G. Van Ass he, Cryptographi
Sponges. Available at http ://[Link]/. 2006.
[BDP08a℄ G. Bertoni, J. Daemen, M. Peeters and G. Van Ass he, On the Indieren-
tiability of the Sponge Constru tion. In N. P. Smart editor, Advan es in Cryp-
tology - EUROCRYPT 2008, Le ture Notes in Computer S ien e 4965, pages
181-197. Springer Verlag, 2008.
[BDP08b℄ G. Bertoni, J. Daemen, M. Peeters and G. Van Ass he, KECCAK. Avai-
lable at http ://ke [Link]/. 2008.
[BD06℄ E. Biham and O. Dunkelman, A Framework for Iterative Hash Fun tions :
HAIFA. In pro eedings of Se ond NIST Cryptographi Hash Workshop. Available
at http :// sr .[Link]/groups/ST/hash/se ond_workshop.html. 2006.
[BS90℄ E. Biham, A. Shamir, Dierential Cryptanalysis of DES-like Cryptosystems.
In A. Menezes and S. A. Vansto editors, Advan es in Cryptology - CRYPTO
1990, Le ture Notes in Computer S ien e 537, pages 2-21. Springer Verlag, 1991.
[BS91a℄ E. Biham, A. Shamir, Dierential Cryptanalysis of Feal and N-Hash. In D.
W. Davies editor,Advan es in Cryptology - EUROCRYPT 1991, Le ture Notes
in Computer S ien e 547, pages 1-16. Springer Verlag, 1991.
[BS91b℄ E. Biham, A. Shamir, Dierential Cryptanalysis of Snefru, Khafre, REDOC-
II, LOKI and Lu ifer. In J. Feigenbaum editor, Advan es in Cryptology -
CRYPTO 1991, Le ture Notes in Computer S ien e 576, pages 156-171. Sprin-
ger Verlag, 1992.
[BRS02℄ J. Bla k, P. Rogaway and T. Shrimpton, Bla k-Box Analysis of the Blo k-
Cipher-Based Hash Fun tion Constru tions from PGV. In M. Yung editor, Ad-
van es in Cryptology - CRYPTO 2002, Le ture Notes in Computer S ien e 2442,
pages 320-335. Springer Verlag, 2002.
146
[BCC08℄ E. Bresson, A. Canteaut, B. Chevallier-Mames, C. Clavier, T. Fuhr,
A. Gouget, T. I art, J. Misarsky, M. Naya-Plasen ia, P. Paillier, T. Por-
nin, J. Reinhard, C. Thuillet and M. Videau, SHABAL. Available at
http ://[Link]. om/. 2008.
[Dam89℄ I. Damgard, A Design Prin iple for Hash Fun tions. In G. Brassard editor,
Advan es in Cryptology - CRYPTO 1989, Le ture Notes in Computer S ien e
435, pages 416-427. Springer Verlag, 1990.
[Dea99℄ R. D. Dean, Formal Aspe ts of Mobile Code Se urity. PhD thesis, Prin-
eton University. Available at http ://www. [Link] [Link]/sip/pub/ddean-
dissertation.php3. 1999.
[DBB91℄ B. den Boer and A. Bosselaers, An Atta k on the Last Two Rounds of MD4.
In J. Feigenbaum editor, Advan es in Cryptology - CRYPTO 1991, Le ture Notes
in Computer S ien e 765, pages 293-304. Springer Verlag, 1992.
[DBB93℄ B. den Boer and A. Bosselaers, Collisions for the Compression Fun tion
Advan es in Cryptology - EUROCRYPT 1993,
of MD5. In T. Helleseth editor,
Le ture Notes in Computer S ien e 765, pages 293-304. Springer Verlag, 1994.
[DCM07℄ C. De Cannière, F. Mendel and C. Re hberger, Collisions for 70-step SHA-
1 : On the Full Cost of Collision Sear h. In C. Adams, A. Miri and M. J. Wiener
editors,Sele ted Areas in Cryptography - SAC 2007, Le ture Notes in Computer
S ien e 4876, pages 56-73. Springer-Verlag, 2007.
147
Bibliographie
[DCR08℄ C. De Canière and C. Re hberger, Preimages for Redu ed SHA-0 and SHA-
Advan es in Cryptology - CRYPT0 2008, Le ture Notes
1. In D. Wagner editor,
in Computer S ien e 5157, pages 179-202. Springer Verlag, 2008.
[DH76℄ W. Die and M. E. Hellman. New Dire tions in Cryptography. IEEE Tran-
sa tions on Information Theory, IT-22(6), pages 644-654. 1976.
[Dob96a℄ H. Dobbertin, Cryptanalysis of MD4. In D. Gollmann editor, Fast Software
En ryption - FSE 1996, Le ture Notes in Computer S ien e 1039, pages 53-69.
Springer-Verlag, 1996.
[FIPS-DES℄ National Institute of Standards and Te hnology, FIPS 46-3 : Data En-
ryption Standard. Available at http :// sr .[Link]. 1999.
[Jou04℄ A. Joux, Multi- ollisions in Iterated Hash Fun tions. Appli ation to Cas a-
ded Constru tions. In M. Franklin editor, Advan es in Cryptology - CRYPTO
2004, Le ture Notes in Computer S ien e 3152, pages 306-316. Springer-Verlag,
2004.
[JP07℄ A. Joux and T. Peyrin, Hash Fun tions and the (Amplied) Boomerang At-
Advan es in Cryptology - CRYPTO 2007, Le ture
ta k. In A. Menezes editor,
Notes in Computer S ien e 4622, pages 244-263. Springer-Verlag, 2007.
[JP05℄ C.S. Jutla and A. C. Patthak, A Mat hing Lower Bound on the Minimum
Weight of SHA-1 Expansion Code. Cryptology ePrint Ar hive, Report 2005/266.
Available at http ://[Link] [Link]/2005/266. 2005.
148
[KKS00℄ J. Kelsey, T. Khono and B. S hneier, Amplied Boomerang Atta ks Against
Redu ed-Round MARS and Serpent. In B. S hneier editor, Fast Software En-
ryption - FSE 2000, Le ture Notes in Computer S ien e 1978, pages 75-93.
Springer Verlag, 2001.
[KS05℄ J. Kelsey and B. S hneier, Se ond Preimages on n-Bit Hash Fun tions for
2n Work. In R. Cramer editor, Advan es in Cryptology - EURO-
Mu h Less than
CRYPT 2005, Le ture Notes in Computer S ien e 3494, pages 474-490. Springer
Verlag, 2005.
[KK06℄ J. Kelsey and T. Khono, Herding Hash Fun tions and the Nostradamus
Atta k. In S. Vaudenay editor,Advan es in Cryptology - EUROCRYPT 2006,
Le ture Notes in Computer S ien e 4004, pages 183-200. Springer Verlag, 2006.
[KL94℄ L. R. Knudsen and X. Lai, New Atta ks on All Double Blo k Length Hash
Ad-
Fun tions of Hash Rate 1, In luding the Parallel-DM. In A. De Santis editor,
van es in Cryptology - EUROCRYPT 1994, Le ture Notes in Computer S ien e
950, pages 410-418. Springer Verlag, 1994.
[KP96℄ L. R. Knudsen and B. Preneel, Hash Fun tions Based on Blo k Ciphers
and Quaternary Codes. In K. Kim and T. Matsumoto editors, Advan es in
Cryptology - ASIACRYPT 1996, Le ture Notes in Computer S ien e 1163, pages
77-90. Springer Verlag, 1996.
[KP97℄ L. R. Knudsen and B. Preneel, Fast and Se ure Hashing Based on Codes.
Advan es in Cryptology - CRYPTO 1997, Le ture
In B. S. Kalinski Jr. editor,
Notes in Computer S ien e 1294, pages 485-498. Springer Verlag, 1997.
[KP02℄ L. R. Knudsen and B. Preneel, Constru tion of Se ure and Fast Hash Fun -
tions Using Nonbinary Error-Corre ting Codes. IEEE Transa tions on Informa-
tion Theory, 48(9), pages 2524-2539. 2002.
[LM92℄ X. Lai and J. L. Massey, Hash Fun tions Based on Blo k Ciphers. In R. A.
Advan es in Cryptology - EUROCRYPT 1992, Le ture Notes in
Rueppel editor,
Computer S ien e 658, pages 55-70. Springer Verlag, 1992.
[Leo88℄ J.S. Leon, A Probabilisti Algorithm for Computing the Minimum Weight
of Large Error-Corre ting Codes. IEEE Transa tions on Information Theory,
34(5), pages 1354-1359. 1988.
[Lu 05℄ S. Lu ks, A Failure-Friendly Design Prin iple for Hash Fun tions. In B.
K. Roy editor,Advan es in Cryptology - ASIACRYPT 2005, Le ture Notes in
Computer S ien e 3788, pages 474-494. Springer Verlag, 2005.
[Man06℄ S. Manuel, Cryptanalyses diérentielles de SHA-0. Mémoire pour
l'obtention du Mastère Re her he, Mathématiques Appli ations au Co-
dage et à la Cryptologie. Université Paris8. Available at http ://www-
ro [Link]/se ret/[Link]. 2008.
[Man08℄ S. Manuel, Classi ation and Generation of Disturban e Ve tors for Colli-
sion Atta ks against SHA-1. Cryptology ePrint Ar hive, Report 2008/469. Avai-
lable at http ://[Link] [Link]/2008/469. 2008.
[Man09℄ S. Manuel, Classi ation and Generation of Disturban e Ve tors for Colli-
sion Atta ks against SHA-1. In A. Kolosha, E. Rosnes and M. Parker editors,
International Workshop on Coding and Cryptography - WCC 2009, pages 224-
235. 2009.
149
Bibliographie
[Man10℄ S. Manuel, Classi ation and Generation of Disturban e Ve tors for Col-
lision Atta ks against SHA-1. To appear inDesign, Codes and Cryptography -
DCC 2010. 2010.
[MS07℄ S. Manuel and N. Sendrier, XOR-Hash : A Hash Fun tion Based on XOR.
Western European Workshop on Resear h in Cryptology - WEWoRC 2007. 2007.
[MP05℄ K. Matusiewi z and J. Pieprzyk, Finding Good Dierential Patterns for
Atta ks on SHA-1. In O. Ytrehus editor, International Workshop on Coding
and Cryptography - WCC 2005, Le ture Notes in Computer S ien e 3969, pages
164-177. Springer-Verlag, 2005.
[MOV96℄ A. J. Menezes, P. C. Van Oors hot and S.A. Vanstone, Handbook of Ap-
plied Cryptography. CRC Press, 1996.
[Mer79a℄ R. C. Merkle, Se re y, Authenti ation, and Publi Key Systems. PhD the-
sis, Stanford University. 1979.
[Mer79b℄ R.C. Merkle, Method of providing digital signatures. U.S. Patent No.
4,309,569. 1980.
[Mer89℄ R.C. Merkle, One Way Hash Fun tion and DES. In G. Brassard editor,
Advan es in Cryptology - CRYPTO 1989, Le ture Notes in Computer S ien e
435, pages 428-446. Springer Verlag, 1989.
[Mer90℄ R.C. Merkle, A Fast Software One-Way Hash Fun tion. Journal of Crypto-
logy, 3(1), pages 43-58. Springer Verlag, 1990.
[MS88℄ C. H. Meyer and M. S hilling, Se ure program load with manipulation de-
te tion ode. Se uri om 88, pages 111-130. SEDEP, 1988.
[MOI90℄ S. Miyagu hi, K. Ohta, and M. Iwata, 128-bit hash fun tion (N-hash). NTT
Review, 2(6), pages 128-132. Springer Verlag, 1990.
150
Cryptology - CRYPT0 2002, Le ture Notes in Computer S ien e 2442, pages
111-126. Springer-Verlag, 2002.
[PB95℄ B. Preneel and A. Bosselaers, RIPE, Integrity Primitives for Se ure Infor-
Final Report of RACE Integrity Primitives Evaluation (RIPE-
mation Systems.
RACE 1040), Le ture Notes in Computer S ien e 107. Springer Verlag, 1995.
[PGV93℄ B. Preneel, R. Govaerts and J. Vandewalle, Hash Fun tions Based on Blo k
Approa h. In D. R. Stinson editor, Advan es in Crypto-
Ciphers : A Syntheti
logy - CRYPTO 1993, Le ture Notes in Computer S ien e 773, pages 368-378.
Springer Verlag, 1993.
[PVO96℄ B. Preneel and P. C. van Oors hot, On the Se urity of Two MAC Algo-
Advan es in Cryptology - EUROCRYPTO 1996,
rithms. In U. M. Maurer editor,
Le ture Notes in Computer S ien e 1070, pages 19-32. Springer Verlag, 1996.
[Rab78℄ M. O. Rabin, Digitalized signatures. In R. Lipton and R. DeMillo editors,
Foundations of Se ure Computations, pages 155-168. A ademi Press, 1978.
151
Bibliographie
[Rog95℄ P. Rogaway, Bu ket Hashing and its Appli ation to Fast Message Authen-
ti ation. In D. Coppersmith editor,Advan es in Cryptology - CRYPTO 1995,
Le ture Notes in Computer S ien e 963, pages 29-42. Springer Verlag, 1995.
Progress
[Rog06℄ P. Rogaway, Formalizing Human Ignoran e. In P. Q. Nguyen editor,
in Cryptology - VIETCRYPT 06, Le ture Notes in Computer S ien e 4341,
pages 211-228. Springer Verlag, 2006.
[WFL04℄ X. Wang, D. Feng, X. Lai and H. Yu, Collisions for Hash Fun tions MD4,
MD5, HAVA-128 and RIPEMD. Cryptology ePrint Ar hive, Report 2004/199.
Available at http ://[Link] [Link]/2004/[Link]. 2004.
[WLF05℄ X. Wang, X. Lai, D. Feng, H. Chen and X. Yu, Crytanalysis of the Hash
Fun tions MD4 and RIPEMD. In R. Cramer editor,Advan es in Cryptology
- EUROCRYPT 2005, Le ture Notes in Computer S ien e 3494, pages 1-18.
Springer Verlag, 2005.
[WY05℄ X. Wang and H. Yu, How to break MD5 and other hash fun tions. In R.
Cramer editor, Advan es in Cryptology - EUROCRYPT 2005, Le ture Notes in
Computer S ien e 3494, pages 19-35. Springer Verlag, 2005.
[WYY05a℄ X. Wang, A. C. Yao and F. Yao, Cryptanalysis on SHA-1. In pro eedings
of NIST Cryptographi Hash Workshop. Available at http :// sr .[Link]. 2005.
[WYY05b℄ X. Wang, X. L. Yin and H. Yu, Finding Collisions in the Full SHA-1.
Advan es in Cryptology - CRYPTO 2005, Le ture Notes in
In V. Shoup editor,
Computer S ien e 3621, pages 17-36. Springer Verlag, 2005.
[WYY05 ℄ X. Wang, X. L. Yin and H. Yu, New Collision Sear h for SHA-1. In Rump
Session of Advan es in Cryptology - CRYPTO 2005. 2005.
152
[WYY05d℄ X. Wang, H. Yu and X. L. Yin, E ient Collision Sear h Atta ks on
SHA-0. In V. Shoup editor, Advan es in Cryptology - CRYPTO 2005, Le ture
Notes in Computer S ien e 3621, pages 1-16. Springer Verlag, 2005.
[YSN07℄ J. Yajima, Y. Sasaki, Y. Naito, T. Iwasaki, T. Shimoyama, N. Kunihiro,
and K. Ohta, A new strategy for nding a dierential path of sha-1. Information
Se urity and Priva y - ISP 2007, Le ture Notes in Computer S ien e 4586 pages
45-58. Springer Verlag, 2007.
[YIN08℄ J. Yajima and T. Iwasaki and Y. Naito and Y. Sasaki and T. Shimoyama
and N. Kunihiro and K. Ohta, A Stri t Evaluation Method on the Number
of Conditions for the SHA-1 Collision Sear h. In M. Abe and V. Gligor edi-
tors,ACM Symposium on Information, Computer and Communi ation Se urity
- ASIACCS 2008, pages 10-20. ACM, 2008.
[YIN09℄ J. Yajima and T. Iwasaki and Y. Naito and Y. Sasaki and T. Shimoyama
and T. Peyrin and N. Kunihiro and K. Ohta, A Stri t Evaluation Method on
the Number of Conditions for the SHA-1 Collision Sear h. IEICE Trans. Fun-
damentals E92-A(1), pages 87-95. IEICE, 2009.
153
Bibliographie
154
Table des gures
1-2 Cette gure illustre les diérents obje tifs d'un adversaire souhaitant
mettre en défaut les propriétés de résistan e aux ollisions, de ré-
sistan e au al ul d'anté édent et de résistan e au al ul de se ond
anté édent. Les parties grisées orrespondent aux éléments qui sont
imposés et les points d'interrogation gurent les messages que doit
produire l'adversaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2-1 Ha hage itératif. Le message est dé oupé en éléments de taille xe qui
sont traités itérativement. . . . . . . . . . . . . . . . . . . . . . . . . 14
3-1 Fon tion de mise à jour des registres ommune à SHA-0 et SHA-1. . 35
5-1 Notations utilisées dans [DCR06℄ pour représenter les diérents états
possibles pour un ouple de bits x et x′ . . . . . . . . . . . . . . . . . 58
155
Table des gures
5-10 Prin ipe de mise en oeuvre de la te hnique des blo s multiples utilisée
par Biham et al. dans [BCJ05℄. . . . . . . . . . . . . . . . . . . . . . 76
5-14 Attaque boomerang ampliée appliquée aux fon tions SHA-0 et SHA-
1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
156
6-5 Cara téristique asso iée à la diérentielle auxiliaire AP2 positionnée
sur la position de bit j = 1. Cette diérentielle possède une ollision
lo ale non-linéaire de la forme ∆ =< 2j , 2j+5 , 0, 2j+30 , 2j+30 , 2j+30 >
initiée au pas 1, et deux ollisions lo ales non-linéaires de la forme
∆ =< 2j , 2j+5 , 0, 0, 2j+30 , 2j+30 > initiées aux pas 3 et 11. La olonne
de droite représente les diérents états des mots de message expan-
sés. La olonne de gau he représente les diérents états du registre A
et pré ise les ontraintes né essaires pour que la ollision lo ale non-
linéaire soit vériée. Un - indique qu'il n'y a pas de ontrainte, une
lettre indique une valeur binaire et une lettre surlignée son omplé-
ment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
157
Table des gures
158
Liste des tableaux
1-1 Tableau de orrespondan e entre les propriétés des fon tions de ha-
hage ryptographiques et les domaines d'utilisation. Les notations
Col, P re, Sec et P RF désignent respe tivement la résistan e aux
ollisions, au al ul d'anté édent, au al ul de se ond anté édent et
le ara tère pseudo-aléatoire. La présen e d'une roix indique le fait
qu'un adversaire mettant en défaut la propriété orrespondante peut
être dire tement utilisé pour invalider l'utilisation de la fon tion dans
le domaine. Les domaines de l'authenti ation de message et des pro-
to oles d'engagement ne sont pas présent dans e tableau ar les pro-
priétés qui leur orrespondent varient en fon tion des onstru tions
utilisées. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5-1 Conditions sur les bits de l'état interne orrespondant à la ara téris-
tique non-linéaire utilisée dans [WYY05d℄. La notation a (respe tive-
ment ā) indique que la valeur du bit orrespondant est égale (respe -
tivement opposée) à la valeur du même bit du registre immédiatement
pré édent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
159
Liste des tableaux
6-5 Chemin diérentiel omplet pour le se ond blo , pas 1 à 40. . . . . . 100
6-6 Chemin diérentiel omplet pour le se ond blo , pas 41 à 80. . . . . 101
6-7 Exemple d'une paire de messages pour une ollision sur 2 blo s :
H(M1 , M2 ) = H(M1′ , M2′ ) = A2 ||B2 ||C2 ||D2 ||E2 , obtenue onformé-
ment au hemin diérentiel présenté dans les tableaux 6-3, 6-4, 6-5 et
6-6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
160
8-4 Probabilités de bon omportement de deux ollisions lo ales alternées
(démarrant au pas i et i + 2) se déroulant entièrement au sein d'une
même fon tion de ronde. Les valeurs présentées sont les moyennes
observées sur 3 expérien es omprenant 224 tests ha une. La notation
"> 24" désigne le fait qu'au une ollision n'a été trouvée lors des trois
expérien es, la probabilité de bon omportement orrespondante est
don stri tement inférieure à 2
−24 . . . . . . . . . . . . . . . . . . . . 124
161
Liste des tableaux
162
Bibliographie
Arti le de journal
[DCC 2010℄ S. Manuel, Classi ation and Generation of Disturban e Ve tors for Col-
lision Atta ks against SHA-1. Á paraître dans Design, Codes and Cryptography
- DCC 2010. 2010.
[WCC 2009℄ S. Manuel, Classi ation and Generation of Disturban e Ve tors for
Collision Atta ks against SHA-1. Parus dans les a tes de International Workshop
on Coding and Cryptography - WCC 2009. 2009.
[FSE 2008℄ S. Manuel et T. Peyrin, Collisions on SHA-0 in one hour. Éditeur K. Ny-
berg, Fast Software En ryption - FSE 2008, Le ture Notes in Computer S ien e
5086, pages 16-35. Springer-Verlag, 2008.
163
Bibliographie
164
Résumé
Une fon tion de ha hage est une fon tion prenant omme argument un élément de taille
arbitraire nie et renvoyant un élément de longueur xée. Il existe diérents types de fon -
tions de ha hage qui orrespondent à autant de domaines d'utilisation. Parmi es fon tions,
les fon tions de ha hage ryptographiques se distinguent par la variété des missions qui leur
sont onées et par l'exigen e qui leur est faîte de respe ter de nombreux impératifs de sé u-
rité. Les fon tions de ha hage ryptographiques les plus utilisées en pratiques appartiennent
à la famille MD-SHA, dont les membres les plus onnus sont les fon tions MD5 et SHA-1.
Durant es dernières années, de nouvelles te hniques de rytptanalyses ont fait leur appari-
tion. Ces te hniques, bien que très omplexes, se sont montrés si e a es qu'elles ont onduit
à l'abandon de l'utilisation des fon tions MD5 et SHA-1, et à l'ouverture d'une ompétition
internationale pour le développement d'un nouvel algorithme de ha hage ryptographique.
Les travaux de re her he que nous avons menés dans le adre de ette thèse s'ins rivent
à la fois dans une démar he d'analyse et de on eption. Nous étudions les nouvelles avan ées
dans la ryptanalyse des fon tions de ha hage, et plus parti ulièrement leurs mise en oeuvre
dans le adre des fon tions SHA-0 et SHA-1. Nous présentons à e titre la meilleure attaque
pratique onnue à e jour ontre SHA-0 et proposons la première lassi ation des ve teurs de
perturbations utilisés par les attaques par ollision ontre la fon tion SHA-1. Nous abordons
ensuite la on eption de nouvelle fon tions par le biais des fon tion XOR-Hash et FSB.
Mots- lés: ryptographie, fon tions de ha hage, ryptanalyse, SHA, XOR-Hash, FSB
Abstra t
A hash fun tion is a fun tion taking as argument an element of nite arbitrary
length and returning an element of xed length. There are dierent types of hash fun tions
that orrespond to elds of use. Among these fun tions, ryptographi hash fun tions are
distinguished by the variety of missions assigned to them and requiring them to meet many
se urity requirements. Cryptographi hash fun tions ommonly used in pra ti es belong
to the MD-SHA family, whose most-known members are MD5 and SHA-1. In re ent years,
new rytptanalysis te hniques have emerged. These te hniques, although very omplex, have
proved so su essful that it led to the abandonment of the use of MD5 and SHA-1, and to the
openning of an international ompetition to develop a new ryptographi hash algorithm.
The resear h we ondu ted as part of this thesis stand in both pro ess analysis and
design. We study the new advan es in the ryptanalysis of hash fun tions, parti ularly
their implementation within the fun tions SHA-0 and SHA-1. We present as su h the best
pra ti al atta k known against SHA-0 and propose the rst lassi ation of disturban es
ve tors used by ollision atta ks against SHA-1. We then dis uss the design of new fun tions
through XOR-Hash and FSB.
165
166
167