Login
Main Menu
Who's Online
1 utilisateur(s) en ligne (dont 1 sur SAPHIR-Downloads)

Membre(s): 0
Invité(s): 1

plus...
WFDownloads is developed by The SmartFactory (http://www.smartfactory.ca), a division of InBox Solutions (http://www.inboxsolutions.net)
SAPHIR-Downloads > Projet RNRT SAPHIR-Livrables > L4.3 Implémentation et optimisation d’attaques sur fonctions de hachage

SAPHIR-Downloads

L4.3 Implémentation et optimisation d’attaques sur fonctions de hachage



Description : 

Depuis quelques années, de nouvelles attaques contre les fonctions de hachage ont été décrites et implémentées. Plus précisément, ces nouvelles attaques dérivent toutes plus ou moins du même principe, illustré en 2004 par la production des premières collisions sur la fonction MD5[10]. Ce sont des attaques différentielles où une différence est introduite dans le bloc d’entrée du message, de telle sorte que la plupart des variations induites par cette différence s’annulent mutuellement avec une probabilité assez élevée. Dans la pratique, l’attaque commence par un chemin différentiel qui exprime cette probabilité, modulo le respect de contraintes élémentaires sur les bits des valeurs d’entrée et des valeurs intermédiaires au cours du calcul. L’implémentation de l’attaque « essaye » des messages qui respectent ces conditions, et recommence jusqu’à avoir des valeurs telles que le chemin différentiel « fonctionne » et produit une collision.
L’expression mathématique de cet algorithme est relativement simple, mais l’évaluation du temps de calcul impliqué est délicate. On souhaite exprimer ce temps en nombre d’évaluations de la fonction de hachage, en considérant des évaluation « élémentaires ». Les fonctions considérées ici traitent les messages d’entrée par blocs (typiquement 512 ou 1024 bits) qui sont plus larges que la sortie de la fonction elle-même ; sous ces conditions, les attaques génériques de recherche de collisions ont un coût qui s’exprime facilement en nombre moyen d’évaluations de la fonction sur un bloc. Une évaluation élémentaire est donc le temps de calcul nécessaire au traitement d’un bloc.
Les implémentations optimisées de fonctions de hachage peuvent donner une estimation relativement précise de ce temps de calcul élémentaire, mais seulement dans les conditions d’application normale de la fonction. En particulier, l’application normale ne vise à obtenir que le résultat de la fonction, sans chercher à garder une trace des valeurs intermédiaires. A contrario, lors d’une attaque par exploration d’un chemin différentiel, certaines valeurs intermédiaires sont conservées afin d’appliquer les conditions booléennes attachées au chemin. Il est généralement supposé qu’on peut estimer le coût de l’attaque en comptant le nombre moyen d’étapes élémentaires dans le parcours du chemin pour chaque « essai » : par exemple, dans l’attaque sur MD5 que nous décrivons plus loin, le cœur de l’attaque consiste en une évaluation d’en moyenne 21 étapes sur les 64 que comporte le traitement d’un bloc de données par MD5 ; on fait donc la supposition que chaque essai a un coût moyen de 21/64 ≈ 0.328 évaluations élémentaires de la fonction.
Le thème du présent rapport est de déterminer à quel point cette supposition est vraie en pratique. Deux attaques ont été implémentées et optimisées, sur les fonctions MD5 et SHA-0, respectivement. Ces deux fonctions ont également été implémentées et optimisées dans le cadre de la bibliothèque sphlib, par le même programmeur et avec des efforts d’optimisation similaires, dans le même langage (langage C). Nous estimons donc que les mesures présentées ici sont représentatives du coût intrinsèque des attaques. Ce faisant, nous décrivons aussi les techniques d’optimisation mises en œuvre pour l’implémentation des attaques.

Proposé par: admin
Editeur: Projet RNRT SAPHIR
Proposé le : Mon, 27-Apr-2009

Version: 1.0
Téléchargé(s) : 1109
Taille du Fichier (en Octets): 358.9 KB

Note :   (0 votes)

Révisions :  (0)

Miroirs disponibles: 0

Temps de téléchargements :
Modem(56k) : 58s
ISDN(64k) : 51s
DSL(768k) : 4s
LAN(10M) : 0.33s
 
Prix: Libre | Plateformes Supportées: None | License: None | Restrictions: None

Projet RNRT SAPHIR Révisions d'utilisateur

Autres fichiers de : admin

L4.3 Implémentation et optimisation d’attaques sur fonctions de hachage © copyright 2017 http://www.crypto-hash.fr

 
Les commentaires appartiennent à leurs auteurs. Nous ne sommes pas responsables de leur contenu.
Search
Fichiers récents