« Tiger (fonction de hachage) » : différence entre les versions
m Corrections Typos using AWB |
-wikif titre de sous-paragraphe (voir Aide:Syntaxe#Syntaxe de base) |
||
(26 versions intermédiaires par 19 utilisateurs non affichées) | |||
Ligne 1 : | Ligne 1 : | ||
{{homon|Tiger}} |
|||
⚫ | '''Tiger''' est une [[fonction de hash|fonction de hachage]] [[cryptographie|cryptographique]] conçue par |
||
{{à sourcer|date=novembre 2016}} |
|||
⚫ | La cryptographie '''Tiger''' est une [[fonction de hash|fonction de hachage]] [[cryptographie|cryptographique]] conçue par {{lien|lang=en|trad=Ross_J._Anderson|Ross Anderson}} et [[Eli Biham]] {{refnec|en [[1996]]}}. 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. |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | 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ération|itérations]]). A chaque passage, il effectue 8 tours ; chaque tour consistant à lire plusieurs tables appelées [[S-Box|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 [[processeur]]s. 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 faut compléter le message de telle sorte qu’il soit un multiple de 512. |
||
Ligne 9 : | Ligne 12 : | ||
On utilise des tampons (VI : valeur initiale) avec 3 registres de 64 bits pour l’empreinte (3*64=192) |
On utilise des tampons (VI : valeur initiale) avec 3 registres de 64 bits pour l’empreinte (3*64=192) |
||
⚫ | |||
⚫ | |||
# sauvegarder ABC (porter les valeurs) |
# sauvegarder ABC (porter les valeurs) |
||
# Passage 1 ( |
# Passage 1 (tours 1 à 8) |
||
# Programme principal 1 |
# Programme principal 1 |
||
# Passage 2 ( |
# Passage 2 (tours 9 à 16) |
||
# Programme principal 2 |
# Programme principal 2 |
||
# Passage 3 ( |
# Passage 3 (tours 17 à 24) |
||
# Alimenter Vers l'avant (calcul |
# Alimenter Vers l'avant (calcul) |
||
Tiger effectue 3 |
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 rounds correspondent aux 8 mots du block de 512. |
|||
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) |
(X8, . . ., X15) := Key Schedule(X0, . . ., X7) |
||
(X16, . . ., X23)):= Key Schedule(X8, . . ., X15) |
|||
Le Key Schedule permet de faire la redistribution |
Le Key Schedule permet de faire la redistribution des bits |
||
Les constantes sont Const1 = A5A5A5A5A5A5A5A5A5 et Const2 = 0123456789ABCDEF. |
|||
Les constants sont ; |
|||
Const1 = A5A5A5A5A5A5A5A5A5 |
|||
Const2=0123456789ABCDEF |
|||
Si |
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’ |
A’’=A A’ |
||
B’’=B-B’ |
B’’=B-B’ |
||
C’’=C+C’ |
C’’=C+C’ |
||
=== Fonctionnement d’un tour === |
|||
Tiger utilise des opérations arithmétiques (addition, soustraction, multiplication) |
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 |
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 |
C=:C ^ X |
||
Puis A et B sont modifiés |
Puis A et B sont modifiés |
||
Ligne 47 : | Ligne 45 : | ||
B: = B * (const.) |
B: = B * (const.) |
||
En suite on fait un décalage circulaire de A, B, C |
En suite on fait un décalage circulaire de A, B, C |
||
La fonction constante const. {5,7,9} |
La [[fonction constante]] const. {5,7,9} |
||
les fonctions even et odd calculées comme suit: |
les fonctions even et odd calculées comme suit: |
||
even(C) := T1(C[0]) ^ T2(C[2]) ^ T3(C[4])^ T4(C[6]) |
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]). |
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 |
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 |
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 === |
|||
La force et la faiblesse pour les fonctions de hachage se calcule grâce aux théorèmes de paradoxes des anniversaires |
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 |
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. |
||
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== |
== Tiger 2 == |
||
'''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. |
|||
Une nouvelle version de Tiger devrait prochainement apparaître. Les premières informations indiquent que les modifications apportées ne seront que minimes, comme c'est souvent le cas en cryptographie, et concernent plus particulièrement le remplissage (padding). |
|||
== Notes et références == |
|||
==À voir== |
|||
{{Références}} |
|||
===Liens internes=== |
|||
== Annexes == |
|||
=== Articles connexes === |
|||
*[[MD5]] |
*[[MD5]] |
||
*[[SHA-1]] |
*[[SHA-1]] |
||
*[[Whirlpool (algorithme)|Whirlpool]] |
*[[Whirlpool (algorithme)|Whirlpool]] |
||
*[[Cryptanalyse différentielle]] |
*[[Cryptanalyse différentielle]] |
||
*[[Serpent (cryptographie)|Serpent]] |
|||
===Liens externes=== |
=== Liens externes === |
||
* {{en}} [http://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger/tiger.html Page de Eli Biham sur Tiger] |
* {{en}} [http://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger/tiger.html Page de Eli Biham sur Tiger] |
||
{{Fonctions de hachage cryptographiques}} |
{{Palette|Fonctions de hachage cryptographiques}} |
||
{{Portail |
{{Portail|Cryptologie}} |
||
[[Catégorie:Algorithme de hachage]] |
[[Catégorie:Algorithme de hachage]] |
||
[[cs:Tiger (hash)]] |
|||
[[de:Tiger (Hashfunktion)]] |
|||
[[en:Tiger (cryptography)]] |
|||
[[es:Tiger]] |
Dernière version du 8 décembre 2023 à 10:35
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 :
- sauvegarder ABC (porter les valeurs)
- Passage 1 (tours 1 à 8)
- Programme principal 1
- Passage 2 (tours 9 à 16)
- Programme principal 2
- Passage 3 (tours 17 à 24)
- 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[modifier | modifier le code]
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.