Complément : Fonctions de hachage

Summary

Cette vidéo explique les fonctions de hachage, surtout les fonctions cryptographiques, qui sont essentielles en sécurité informatique. Les fonctions de hachage prennent une entrée binaire de n'importe quelle taille et produisent un hachage de taille fixe, souvent exprimé en hexadécimal. Elles sont unidirectionnelles et résistentes aux collisions. Le script explore également des algorithmes tels que MD5, SHA-1, SHA-2, et SHA-3, et les constructions de fonctions de hachage comme Merkle-Damgård et le mécanisme de l'éponge. Enfin, il discute de l'importance de la longueur du hachage pour la sécurité et des attaques potentielles telles que la recherche de pré-images et de collisions.

Takeaways

• 🔑 Les fonctions de hachage cryptographiques sont essentielles en sécurité informatique et dans les systèmes distribués.
• ⚙️ Une fonction de hachage prend une chaîne binaire en entrée et génère une chaîne binaire de taille fixe, souvent 256 bits.
• 🔒 Une fonction de hachage n'a pas de réciproque, il est donc impossible de revenir à la chaîne originale à partir de l'empreinte.
• ❌ Les bonnes fonctions de hachage résistent aux collisions, c'est-à-dire qu'il est très difficile de trouver deux entrées différentes donnant la même empreinte.
• 📜 MD5 est une fonction de hachage obsolète car elle ne garantit pas la résistance aux collisions.
• 🔄 SHA-1 et SHA-2 sont des améliorations de MD5, produisant des empreintes de 160 à 512 bits.
• 💡 SHA-3 utilise un mécanisme différent des fonctions précédentes, appelé mécanisme de Keccak.
• 📊 Les attaques sur les fonctions de hachage incluent la recherche d'une pré-image (retrouver la chaîne d'origine) et la recherche de collisions.
• 🤔 Le paradoxe des anniversaires illustre la difficulté à trouver des collisions, même avec un petit nombre de tentatives.
• 🔢 Pour une sécurité optimale contre les collisions, les fonctions de hachage doivent avoir des empreintes de longueur suffisante, comme 256 bits.

Q & A

Qu'est-ce qu'une fonction de hachage?

Une fonction de hachage est une fonction qui prend n'importe quelle chaîne binaire en entrée et produit une chaîne binaire de taille fixe en sortie, appelée empreinte ou hachage.

Quels sont les types de fonctions de hachage abordés dans cette vidéo?

Dans cette vidéo, on parle des fonctions de hachage cryptographiques, qui sont les plus utilisées et souvent simplement appelées 'fonctions de hachage'.

Quelles sont les propriétés importantes d'une fonction de hachage?

Les propriétés importantes incluent la capacité à prendre n'importe quelle entrée et à produire une sortie de taille fixe, l'impossibilité de trouver une entrée à partir de l'empreinte (pas de réciproque), et la résistance aux collisions.

Pourquoi la fonction de hachage doit-elle être résistante aux collisions?

Une fonction de hachage doit être résistante aux collisions pour qu'il soit très difficile de trouver deux entrées différentes qui produisent la même empreinte.

Quel est le rôle des fonctions de hachage en informatique?

Les fonctions de hachage jouent un rôle crucial en sécurité informatique et dans les systèmes distribués, notamment pour l'authentification, le stockage sécurisé des mots de passe et la détection des modifications de données.

Quels sont les exemples de fonctions de hachage mentionnés dans la vidéo?

La vidéo mentionne MD5, SHA-1, SHA-2 et SHA-3 comme exemples de fonctions de hachage.

Pourquoi MD5 n'est-il pas recommandé d'utiliser en sécurité?

MD5 n'est pas recommandé car il ne fournit pas les propriétés de sécurité nécessaires, comme la résistance aux collisions et la pré-image resistance.

Quelle est la différence entre la construction de Merkle-Damgård et le mécanisme de Keccak?

La construction de Merkle-Damgård est un processus où la chaîne d'entrée est coupée en blocs et traitée par une fonction de compression, tandis que le mécanisme de Keccak, également appelé 'l'éponge', fonctionne en deux phases: absorption de l'information et extraction du hachage.

Quelle est la complexité d'une attaque par recherche de pré-images?

La complexité d'une attaque par recherche de pré-images est élevée, nécessitant en moyenne 2^n essais pour trouver une pré-image, où n est la taille de l'empreinte en bits.

Comment fonctionne le paradoxe des anniversaires et qu'est-ce qu'il a à voir avec les collisions de hachage?

Le paradoxe des anniversaires illustre comment il est plus probable de trouver une collision avec un nombre relativement petit d'essais, comparé à l'intuition qui suggère qu'il faudrait beaucoup plus d'essais. Cela s'applique aux collisions de hachage, où il est nécessaire de tester en moyenne √2^n valeurs pour trouver une collision, où n est le nombre d'empreintes possibles.

Outlines

00:00

🔐 Introduction aux fonctions de hachage

Cette vidéo aborde le sujet des fonctions de hachage, en particulier les fonctions de hachage cryptographiques, qui sont essentielles en matière de sécurité informatique et de systèmes distribués. Le hachage est une fonction sans réciproque qui prend une entrée binaire de n'importe quelle taille et produit une sortie binaire de taille fixe, souvent représentée sous forme hexadécimale. Les fonctions de hachage doivent être résistantes aux collisions, c'est-à-dire qu'il doit être difficile de trouver deux entrées différentes qui produisent la même sortie. La vidéo mentionne également divers types de fonctions de hachage, tels que MD5, SHA-1 et SHA-2, ainsi que la récente invention de SHA-3. Les mécanismes de construction de ces fonctions de hachage sont brièvement expliqués, notamment la construction de Merkle-Damgård et le mécanisme de l'éponge (sponge construction).

05:01

🔎 Attaques sur les fonctions de hachage

Le deuxième paragraphe se concentre sur les attaques possibles contre les fonctions de hachage, notamment l'attaque par recherche d'images antérieures et l'attaque par recherche de collisions. L'attaque par recherche d'images antérieures consiste à trouver une entrée qui produit un hachage donné, ce qui est en général difficile à cause du grand nombre potentiel d'images possibles. L'attaque par recherche de collisions consiste à trouver deux entrées différentes qui produisent le même hachage. Le paradoxe des anniversaires est utilisé pour expliquer la probabilité de trouver une collision et montre que même avec un nombre relativement faible d'essais, il est possible de trouver des collisions. La vidéo conclut en soulignant l'importance de la longueur des hachages pour assurer la sécurité contre ces attaques.

Keywords

💡fonction de hachage

Une fonction de hachage est une transformation mathématique qui prend une entrée arbitraire de taille et produit une sortie de taille fixe, souvent appelée empreinte ou hachage. Dans le contexte de la vidéo, les fonctions de hachage sont utilisées pour la sécurité informatique, comme dans le cas de la protection des mots de passe. L'exemple donné est de hacher un mot de passe ou une vidéo, produisant toujours une chaîne binaire de taille fixe de 256 bits.

💡réciproque

La notion de réciproque fait référence à l'impossibilité de retrouver l'entrée originale à partir du hachage. C'est une propriété souhaitable des fonctions de hachage pour assurer la sécurité, comme expliqué dans la vidéo où il est dit qu'il est très difficile de trouver l'entrée à partir du hachage.

💡résistance aux collisions

La résistance aux collisions est une propriété où il est très difficile de trouver deux entrées différentes qui produisent le même hachage. C'est essentiel pour la sécurité, car cela protège contre certaines formes d'attaques. La vidéo mentionne que les fonctions de hachage doivent être résistantes aux collisions.

💡MD5

MD5 est un algorithme de hachage qui produit un hachage de 128 bits. Il est décrit dans la vidéo comme étant dépassé et non recommandé pour les utilisations sécurisées en raison de sa vulnérabilité aux attaques. Cependant, il est encore utilisé par certaines personnes.

💡SHA

SHA (Secure Hash Algorithm) est une famille d'algorithmes de hachage sécurisés. La vidéo mentionne SHA-1 qui produit des hachages de 160 bits et SHA-2 qui peut produire des hachages entre 256 et 512 bits. Ces algorithmes sont plus sécurisés que MD5 et sont couramment utilisés.

💡construction de Merkle-Damgård

La construction de Merkle-Damgård est un mécanisme utilisé dans la conception de nombreux algorithmes de hachage, y compris MD5 et SHA-1. La vidéo explique que cette construction divise l'entrée en blocs et utilise une fonction de compression pour hacher chaque bloc, en utilisant le résultat pour chiffrer le bloc suivant.

💡mécanisme de Keccak

Le mécanisme de Keccak, également appelé le mécanisme de l'éponge, est une approche différente de la construction de hachage qui fonctionne en deux phases : absorption et extraction. Cette méthode est utilisée dans SHA-3 et est expliquée dans la vidéo comme une alternative à la construction de Merkle-Damgård.

💡attaque de l'après-image

L'attaque de l'après-image consiste à trouver une entrée qui correspond à un hachage donné. La vidéo explique que, sans informations supplémentaires sur l'entrée, l'attaque par force brute est la seule méthode possible, essayant toutes les valeurs possibles jusqu'à ce qu'une correspondance soit trouvée.

💡collision

Une collision est une situation où deux entrées différentes produisent le même hachage. La vidéo aborde la complexité de trouver une collision et mentionne le paradoxe des anniversaires comme une analogie pour expliquer la probabilité de trouver une collision.

💡paradoxe des anniversaires

Le paradoxe des anniversaires illustre comment il est plus probable qu'il semble de trouver une collision (deux personnes ayant le même anniversaire) avec moins d'éléments que l'on pourrait s'y attendre. La vidéo utilise ce paradoxe pour expliquer la probabilité de trouver une collision dans une fonction de hachage.

Highlights

La vidéo parle des fonctions de hachage cryptographique et leur importance en sécurité informatique.

Les fonctions de hachage sont des fonctions sans réciproque qui transforment des données en une chaîne binaire de taille fixe.

Les fonctions de hachage peuvent prendre n'importe quelle chaîne binaire en entrée et produire un hash de taille fixe.

Les hachages sont souvent représentés en hexadécimal pour faciliter leur écriture et leur lecture.

Les fonctions de hachage doivent être résistantes aux collisions, c'est-à-dire qu'il doit être difficile de trouver deux entrées différentes qui produisent le même hash.

Historiquement, des fonctions de hachage telles que MD5, SHA-1 et SHA-2 ont été créées, mais certaines ne sont plus considérées comme sécurisées.

SHA-3, créée en 2015, est basée sur un mécanisme différent appelé le mécanisme de sponge.

La construction de Merkle-Damgård est utilisée par de nombreuses fonctions de hachage pour produire un hash de 256 bits.

Le mécanisme de sponge fonctionne en deux phases : absorption de l'information et extraction du hash final.

La fonction de compression est utilisée dans la construction de Merkle-Damgård et peut être basée sur des algorithmes de chiffrement de bloc.

Le mécanisme de sponge mélange les bits à l'aide d'une fonction de permutation pseudo-aléatoire.

Il est important de comprendre la complexité des attaques contre les fonctions de hachage, comme l'attaque de l'après-image et l'attaque de collision.

L'attaque de l'après-image consiste à trouver une entrée qui produit un hash donné, ce qui peut être difficile si l'entrée est arbitraire.

L'attaque de collision consiste à trouver deux entrées différentes qui produisent le même hash.

Le paradoxe des anniversaires montre que peu d'essais sont nécessaires pour trouver une collision, contrairement à l'intuition.

La longueur des hachages est importante pour résister aux attaques de collision, et plus elle est longue, plus la sécurité est élevée.

La vidéo explique également comment calculer la probabilité de trouver une collision en fonction du nombre de valeurs de hachages possibles.

La vidéo conclut en soulignant l'importance de la compréhension des fonctions de hachage pour la sécurité informatique.

Transcripts

salut à tous dans cette vidéo on va

parler de fonction de hachage fait cette

vidéo en complément de celle sur le

craquage du mot de passe donc si ce

n'est pas déjà fait commencer par

regarder cette vidéo on ira un peu plus

dans les détails et serra et je pars du

principe que vous avez certaines

connaissances de base en mathématiques

mais si c'est pas le cas vous en faites

pas si vous savez simplement qu'une

fonction de la chasse est une fonction

qui n'a pas de réciproque c'est tout à

fait suffisant pour la suite

[Musique]

alors il existe beaucoup de types de

fonctions de hachage dans cette vidéo je

vais parler des fonctions de hachage

cryptographique c'est celle qui sont le

plus souvent utilisés

c'est pour ça que communément on les

appelle juste fonction de hachage ses

fonctions le son très important pour

beaucoup de domaines en sécurité

informatique et en systèmes distribués

donc c'est pour ça que je sais vidéo

complément parce qu'il sera utile pour

d'autres vidéos que je ferais sur

d'autres sujets alors une fonction de

hachage noté h à plusieurs propriétés

déjà elle peut prendre n'importe quelle

chaîne binaire en entrée et comme on

peut encoder pratiquement toutes

informations en binaire une fonction de

la charge peut prendre un entrer du

texte des images des vidéos des fichiers

etc

la fonction produits en sortit une

chaîne binaire de taille fixe par

exemple 256 bits qu'on appelle le ch ou

empruntent donc c'est à dire que la

fonction on peut prendre d'entrée du

texte un simple mot ou une vidéo et dans

les deux cas elle va produire une chaîne

binaire de taille fixe de 256 bits comme

ça peut être long d'écrire un has been r

souvent on les note en hexadécimal c'est

à dire en bas 16 avec des symboles qui

vont de zéro à m l'une des propriétés

les plus importants des fonctions

d'achat ce qu'elles n'ont pas de

réciproque c'est à dire qu'on peut

calculer facilement le h de n'importe

quelle chaîne binaire mais ensuite à

partir du h

on ne peut pas revenir en arrière pour

retrouver la chaîne binaire original et

finalement une fonction de la charge

doit être résistantes aux collisions

c'est à dire qu'il est très difficile de

trouver deux valeurs d'entrée

différentes telles que si on applique la

fonction en obtiennent deux fois le même

match depuis la fin du xxème siècle

plusieurs fonctions de hachage ont été

inventés emmener son enfant on invente

md5 y produit des âges de 128 bits et

plus personnes devraient utiliser parce

qu'en fait ne fournit pas les propriétés

qu'on a évoqué tout à l'heure

malheureusement beaucoup de gens

continuent encore à l'utiliser plus tard

c'est ch a un qui a été inventée qui

produit des empreintes de 160 buts et

encore plus tard chats 2 qui peut

fournir des empreintes entre 256 et 512

bits

toutes ces fonctions de hachage sont

basés sur le même mécanisme qu'on

appelle la construction de merkel ii en

garde mais en 2015 les chercheurs belges

l'ont inventé chat 3 qui peut produire

dh entre 256 et 512 b et qui est basée

sur un mécanisme complètement différent

qu'on appelle le mécanisme de kate

chaque on va maintenant voir ces deux

constructions de manière assez

superficiel juste pour donner un peu une

idée de comment les fonctions de hachage

sont construites on commence par voir la

construction de

arcade en garde admettons que la

fonction produisez h de 256 bits

on coupe la chaîne binaire fourni en

entrée en bloc de longues heures fixes

par exemple 512 bits et on décide une

valeur initiale qui sera une clé de

chiffrement symétrique de la même taille

que le h on veut produire dans notre cas

256 bits

on utilise cette valeur pour chiffrer le

premier bloc avec une fonction de

compression c'est qui peut être

construite à partir de chiffrement par

blog par exemple d es ou aes

le résultat de la fonction c est aussi

de 256 bits et on applique un qui sort

entre le résultat est la clé ce qui sort

est donné comme clé à la prochaine

application de la fonction c'est qui

prend d'entrée le bloc suivant de 512

bits

le processus continue ainsi jusqu'à ce

qu'on ait fait tous les blocs pour

finalement produire le h de 256 bits

on passe maintenant aux mécanismes de

kate chaque qui est aussi appelé le

mécanisme de l'épongé parce qu'il

fonctionne en deux phases d'abord on

absorbe l'information puis on les sort

pour extraire le hpv obtenir on définit

deux nombre de bits est un essai on

commence par des coupes et l'entrée

enveloppe de redites et on choisit un

vecteur initiale de longueur est

repoussé on fait un qui sort entre le

premier bloc et les arbitres initiaux et

le résultat est donné en entrée à une

fonction f

j'entre pas dans les détails complexes

de cette fonction f mais en gros c'est

une fonction de permutations pseudo

aléatoires

c'est à dire que les beats fourni en

entrées sont mélangées entre eux la

fonction prend aussi en entrée les ses

beats de l'état initial et produit deux

sorties l'une deux arbitres et une de

ces dites on fait un sort entre les

arbitres résultant est le deuxième bloc

de l'entrée le résultat duc soirée

donnée en entrée de nouveau à la

fonction f

on continue ce processus jusqu'à voir

traiter tous les blocs de l'entrée

ensuite on passe à la deuxième phase on

applique de nouveau la fonction f mais

cette fois le résultat de rbi tête a

ajouté une chaîne binaire qui sera le

résultat final

à chaque itération de f on ajoutera rbi

tôt h finale et on s'arrête quand le h a

au moins la taille désirée par exemple

256 bits

maintenant qu'on a une petite idée de

comment ces fonctions de hachage sont

construites on va voir la complexité de

plusieurs attaques qu'on peut faire sur

ses fonctions de hachage on verra dans

d'autres vidéos des applications de ces

attaques

ici on se concentre sur l'aspect

théorique la première de ces attaques

c'est ce qu'on appelle la tacc de

l'après images c'est à dire que si

j'ai l'image résultant de la fonction de

hachage comment retrouver la chaîne

binaire original qu'on appelle aussi

l'après images qu'on a vu un cas

particulier de cette attaque le craquage

de mots de passe et on a vu qu'il y

avait des attaques bien meilleure que la

force brute mais c'est parce qu'on sait

que l'entrée x est un mot de passe et

que les mots de passe ont certaines

propriétés

si on généralise dans le cas où on dit

que l'entrée x est une chaîne binaire

complètement arbitraire il est difficile

de faire mieux que la force brute

on essaye donc toutes les valeurs

possibles pour x et à chaque fois on

calcule h2x et on regarde si le résultat

est égal à y

alors combien de x faudra-t-il essayé

pour cela il faut se poser la question

de combien d' image différente il existe

on a dit que le fonction de hachage

produisent dh de taille fixe

si la fonction produits dh de longueur

elle il y à n égale deux puissances

pelle différents âges possible donc à

chaque fois que je calcule le hdx la

probabilité paix que le h résultant soit

y est de 1 sur rennes et la probité que

ce soit pas le cas ce qu'on cherche et

de 1 - p donc le nom des scènes avant de

trouver le hb peut être calculée avec

l'explication peu de haine c'est la

somme de ifois un mois paie à l'appui

106 - 1 x p et ça c'est un résultat

mathématique standard je pas le démontre

ici ça fait 1 / p donc en moyenne il

faudra essayer un surper différents âges

possible c'est-à-dire deux puissances

elle donc vous voyez pourquoi la

longueur du hasch produit est importante

plus les âges sont longs et plus les

difficile de trouver une pré images on

passe maintenant à la deuxième attaque

trouver une collision

formellement il s'agit de trouver deux

valeurs x1 et x2 tels que h2x 1 est égal

à h 2 x 2 pour ce faire on va procéder

de la manière suivante on teste toutes

les valeurs possibles

x à chaque fois on calcule le h et on

regarde dans une table si on a déjà

calculé ce h la cie oui on a trouvé une

collision

sinon on stocke la valeur et le h dans

la table et on continue ainsi jusqu'à ce

qu'on trouve une collision

la question maintenant de savoir combien

en moyenne il faudra 2 x à considérer

pour pouvoir trouver une collision en

sachant qu'on a n h différents possibles

ce problème en priorité les connu sous

le nom de paradoxe des anniversaires

c'est pas du tout un paradoxe en fait

c'est juste que la réponse est contre

intuitive

si j'ai une classe d'élèves combien

d'élèves faudra-t-il pour qu'on ait une

probabilité de 50% que deux

élèves et le même anniversaire et

combien d'élèves faudra-t-il pour que

cette probabilité soit deux au moins 99

% on part du principe qu'une année a

toujours 365 jours et que tous les

anniversaires son équipe probable on

peut voir ce problème comme une analogie

pour notre attaque de collision le

nombre de jours dans l'année représente

le nom de hache possible le nombre

d'élèves dans la classe représente le

nombre d'essais pour trouver une

collision clairement lorsqu'on a au

moins 366 élèves dans la classe on aura

de toute façon au moins deux élèves qui

ont le même anniversaire puisque il ya

que 365 anniversaire possible

est ce qu'on appelle le pin junk rôle

principal donc on va s'intéresser

uniquement à la probabilité paix lorsque

le nombre d'élèves est plus petit que

366 on note l le nombre d'élèves et p2 n

la probabilité qu'au moins deux élèves

aient le même anniversaire

on a donc un mois p de haine qui est la

probabilité que tous les élèves est un

anniversaire différents notons la non p2

elles n'ont pas de haine et facilement

calculable le premier élève peut avoir

n'importe lequel des 365 anniversaire il

ne peut pas y avoir collision

donc la probabilité d'avoir des

anniversaires différents et de 1,365 sur

365

le deuxième élève doit avoir un des 364

anniversaire restants ne peut pas avoir

le même anniversaire que le premier

élève donc la probité et de 364 sur 365

de la même manière le troisième élève

peut avoir un des trois cent soixante

trois anniversaires restant etc

jusqu'aux énième élèves qui peut avoir

un adversaire parmi les 365 - n + 1

restants on peut ensuite mettre ensemble

toutes ces fractions et utiliser les

factorielle pour avoir une

représentation plus compact on peut donc

calculer paix de haine pour n'importe

quelle haine je vous mets ici certaines

valeurs de haine et de paix de haine

ce qui est surprenant c'est qu'avec

seulement 23 élèves on a déjà 50% de

chances de deux anniversaires identique

et avec seulement 60 élèves

on a déjà 99,4 % de chance d'avoir deux

élèves avec le même anniversaire

à partir de cette formule on peut faire

différentes approximations mathématiques

dont je vous passe les détails et dans

notre cas des fonctions de hachage on

trouve que si on na n différents âges

possible il faut aussi en moyenne racine

carrée de pi sur deux fois n différentes

valeurs de x pour trouver une collision

comme n est égale à deux puissances

elles le nombre d'essais de racine

carrée de pi sur deux fois depuis sans

selle sur deux

ça veut dire que si on oublie le facteur

constant si on a des âges de 256 bits il

faut en moyenne de puissance 128 essais

pour trouver une collision

donc c'est important à savoir que si on

veut une sécurité quand tu es collision

de deux puissances

elle essaie en moyenne il faut avoir des

âges deux longueurs de l et non pas de

longueur elle

voilà c'est la fin de cette vidéo

j'espère que ça vous a plu et que vous

avez maintenant une meilleure

compréhension des fonctions de hachage

n'hésitez pas à dire dans les

commentaires ci avait des choses pas

claires j'ai passé un peu vite sur les

notions mathématiques

n'hésitez pas aussi à vous abonner si

vous voulez voir d'autres vidéos on

verra en pratique des cas qui utilise

ses fonctions de hachage à bientôt