Aller au contenu

Tiger (fonction de hachage)

Un article de Wikipédia, l'encyclopédie libre.

La cryptographie Tiger est une fonction de hachage cryptographique conçue par Ross Anderson (en) et Eli Biham en 1996[réf. nécessaire]. Tiger fournit une empreinte sur 192 bits mais des versions sur 128 et 160 bits existent aussi. Ces versions raccourcies prennent simplement les premiers bits de la signature de 192 bits.

Fonctionnement

[modifier | modifier le code]

La cryptographie moderne est fortement basée sur la théorie mathématique et la pratique de l'informatique; Les algorithmes cryptographiques sont conçus autour d' hypothèses de dureté de calcul. Tiger effectue trois passages (ou itérations). A chaque passage, il effectue 8 tours ; chaque tour consistant à lire plusieurs tables appelées S-Boxes. Des opérations supplémentaires sont effectuées sur les registres de 64 bits de manière à casser la linéarité de la structure. Tiger a été conçu et optimisé pour les systèmes 64 bits, il est surtout 3 fois plus rapide que le SHA-1 sur de tels processeurs. De plus, il est plus rapide que ses concurrents sur les machines 16 ou 32 bits. Cette fonction de hachage a été articulée autour d'un effet avalanche rapide, c’est-à-dire qu'une modification mineure dans un registre va produire de grands changements dans les registres lors des itérations suivantes. Cet effet chaotique repousse les attaques basées sur des techniques habituelles en cryptanalyse qui ont fait leur preuve avec d'autres fonctions comme le MD4.

Il faut compléter le message de telle sorte qu’il soit un multiple de 512. Il est ensuite divisé en blocs de 512 bits. Chaque bloc de 512 est divisé en 8 mots de 64 bits On utilise des tampons (VI : valeur initiale) avec 3 registres de 64 bits pour l’empreinte (3*64=192)

L’algorithme emploie les étapes suivantes :

  1. sauvegarder ABC (porter les valeurs)
  2. Passage 1 (tours 1 à 8)
  3. Programme principal 1
  4. Passage 2 (tours 9 à 16)
  5. Programme principal 2
  6. Passage 3 (tours 17 à 24)
  7. Alimenter Vers l'avant (calcul)

Tiger effectue 3 passages pour un total de 24 tours et à chaque passage, lit à 8 reprises plusieurs tables S-Boxes. A chaque tour, il utilise un mot du message Xi.

   Les clés  des 8 premiers tours correspondent aux 8 mots du block de 512.
   Les clés des 16 autres tours sont générées en appliquant la fonction Key Schedule(programme principal).
   (X8, . . ., X15) := Key Schedule(X0, . . ., X7)
   (X16, . . ., X23)):= Key Schedule(X8, . . ., X15)

Le Key Schedule permet de faire la redistribution des bits

Les constantes sont Const1 = A5A5A5A5A5A5A5A5A5 et Const2 = 0123456789ABCDEF.

Si A, B et C désignent les trois registres (VI), les 8 mots du bloc X1,…,X7 sont introduits dans la fonction Tiger et A’, B’, C’ l’empreinte générée après trois tours alors la nouvelle valeur d’initialisation désignée par A’’, B’’, C’’ pour le prochain parcours (feedforward) est calculée de la manière suivante A’’=A A’ B’’=B-B’ C’’=C+C’

Fonctionnement d’un tour

[modifier | modifier le code]

Tiger utilise des opérations arithmétiques (addition, soustraction, multiplication) L’empreinte est découpé en trois registres A, B, C de 64 bits et dans chaque message le mot X est appliqué avec l’opération XOR avec C

                  C=:C ^ X
      Puis A et B sont modifiés
                             A: = A − even(C)
              B: = B + odd(C)
               B: = B * (const.)

En suite on fait un décalage circulaire de A, B, C La fonction constante const. {5,7,9}

les fonctions even et odd calculées comme suit: even(C) := T1(C[0]) ^ T2(C[2]) ^ T3(C[4])^ T4(C[6]) odd(C) := T1(C[7]) ^ T2(C[5]) ^ T3(C[3]) ^ T4(C[1]). Avec C[0], C[1], …….C[7] les 8 octets de C et T1,…, T4 :{0.1}^8_____________________>{0,1}^64 qui fait la correspondance de 8 bit en 64 bits even et odd désignent respectivement les 4 octets pairs et les 4 octets impairs du registre C

Force et faiblesse de résistance aux attaques

[modifier | modifier le code]

La force et la faiblesse pour les fonctions de hachage se calcule grâce aux théorèmes de paradoxes des anniversaires. Pour une empreinte égale à n, il faut 2^n/2 essais pour trouver une collision .au hasard Puisque Tiger utilise une signature de 192, sa complexité est de 2^96 Mais si on réduit les tours à 16 (Tiger-16) on obtient une collision avec une complexité égale à 2^44 des collisions proches sur Tiger-20 avec 2^48 invocations d’après les attaques faites par Kelsey et Lucks en 2006. D’autres attaques faites par Mendel etal dans cette même année ont montré des collisions sur Tiger-19 avec 2^62 invocations et des collisions proches sur Tiger-22 avec 2^44 invocations.

Tiger 2 est une variante où le message, comme dans le cas de Tiger, est rempli en ajoutant d'abord un octet comme dans MD4 , MD5 et SHA. Les deux variantes sont par ailleurs identiques.

Notes et références

[modifier | modifier le code]

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]