Cles de hash , et collision ?

Le
ptilou
Slt,

Je discute avec un prof d'informatique qui me dit que une clès de hash=
étant donnée sa taille de 16 octes ? Il n'est pas possible si le=
s fichier qui font plusieur Megaoctets, il n'y ai pas de collision, je dis =
NON, on me pilorise comme d'hab !

Quelqu'un pour m'aider à démontrer que j'ai raison ?

J'ai jetter un oeuil à la page Wikipedia et fait une recherche sur hal=
, et j'ai pas trouvé une preuve scientifique non discutable !
https://fr.wikipedia.org/wiki/Keyed-hash_message_authentication_code
https://tools.ietf.org/html/rfc3566
https://hal.archives-ouvertes.fr/search/index/?q=hash+&submit=&docType_=
s=ART+OR+COMM+OR+OUV+OR+COUV+OR+DOUV+OR+REPORT+OR+OTHER+OR+THESE+OR+HDR+O=
R+LECTURE+OR+UNDEFINED&submitType_s=file

Peut-être j'ai mal cherché ?

merci

--
ptilou
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
ptilou
Le #26501598
Le samedi 15 décembre 2018 16:49:07 UTC+1, ptilou a écrit :
Slt,
Je discute avec un prof d'informatique qui me dit que une clès de ha sh étant donnée sa taille de 16 octes ? Il n'est pas possible si les fichier qui font plusieur Megaoctets, il n'y ai pas de collision, je di s NON, on me pilorise comme d'hab !
Quelqu'un pour m'aider à démontrer que j'ai raison ?
J'ai jetter un oeuil à la page Wikipedia et fait une recherche sur h al, et j'ai pas trouvé une preuve scientifique non discutable !
https://fr.wikipedia.org/wiki/Keyed-hash_message_authentication_code
https://tools.ietf.org/html/rfc3566
https://hal.archives-ouvertes.fr/search/index/?q=hash+&submit=&docTyp e_s=ART+OR+COMM+OR+OUV+OR+COUV+OR+DOUV+OR+REPORT+OR+OTHER+OR+THESE+OR+HDR +OR+LECTURE+OR+UNDEFINED&submitType_s=file
Peut-être j'ai mal cherché ?
merci
--
ptilou

https://pastel.archives-ouvertes.fr/tel-01495634/document
C'est un petit pavé de 300 pages, si y avait un vulgarisateur de la sc ience, par avance toutes courbettes possibles et imaginable, dit simplement merci de m'éclairer !
Marc SCHAEFER
Le #26501613
ptilou
Je discute avec un prof d'informatique qui me dit que une clès de hash étant donnée sa taille de 16 octes ? Il n'est pas possible si les fichier qui font plusieur Megaoctets, il n'y ai pas de collision, je dis NON, on me pilorise comme d'hab !

Le principe même d'un hachage est effectivement une projection.
Si le fichier original est plus grand que 16 octets, il y a donc forcément
perte d'information. Donc plusieurs fichiers différents vont donner le même
hash.
Toute la beauté de la chose est de rendre très, très difficile à partir d'un
hash connu de trouver une collision, d'autant plus avec une partie de son
contenu fixé. Ou de trouver deux modifications d'un même fichier avec le même
hash résultant.
Les algorithmes de hachage pour lesquels il est facile de trouver ce genre de
collisions ne sont pas adaptés aux applications cryptographiques.
Une façon de se prémunir contre ce genre de problème est, avant de signer un
message, de toujours modifier un peu le message. On se protégera alors contre
un éventuel calcul à l'avance de collisions, préparées depuis longtemps par
l'attaquant.
A ma connaissance, md5 qui n'est plus recommandé aujourd'hui, serait
toutefois sûr avec l'idée de modification ci-dessus, est-ce vrai ?
Pascal J. Bourguignon
Le #26501901
ptilou
Slt,
Je discute avec un prof d'informatique qui me dit que une clès de hash
étant donnée sa taille de 16 octes ? Il n'est pas possible si les
fichier qui font plusieur Megaoctets, il n'y ai pas de collision, je
dis NON, on me pilorise comme d'hab !
Quelqu'un pour m'aider à démontrer que j'ai raison ?

C'est facile. Si tu as un hash qui fait N octet, c'est à dire 8N bits,
tu peux avoir au total 2^8N hash differents.
Donc il suffit de créer 2^8N+1 fichiers différents (on peut y mettre en
binaire les nombres de 0 à 2^8N+1, chaque fichier faisant alors 8N+1
bit, arrondit à N+1 octets…)
Il y aura donc forcément deux fichiers avec le même hash.
MAIS
en pratique, avec N octets, 8N8 bits et 2^8N 340282366920938463463374607431768211456 fichiers.
À raison de 17 octets par fichier, même bien tassés, ça fait
5784800237655953878877368326340059594752 octets.
un 1To c'est: 1099511627776 octets
le temps restant à cet univers est 200 milliard d'années à tout
casser. Ça fait environ 6.3e18 secondes.
Il faut donc traiter
340282366920938463463374607431768211456 / 6307200000000000000
= 53951415354030070944 fichiers par seconde.
Avec un processeur 4GHz, il faudrait traiter 13487853838 fichiers par
cycle de processeur. Alors, si on avait 13 billions ou 1300 billions de
GPU, ce serait peut être envisageable de calculer tout ces hash avant la
fin de l'univers.
En pratique, non. Alors à moins d'un défaut dans l'algorithme de
hashage permettant par un raccourci de modifier un fichier pour obtenir
un hash donné rapidement, en pratique, on n'a pas le temps et on n'a pas
la puissance de calcul pour le faire.
Ton prof d'informatique, c'est un gars pratique. On ne peut lui opposer
que les maths, mais les maths (et tous les O(...) en algorithmique) ne
servent à rien, quand on n'a que 1e80 particules dans un univers qui n'a
que 6.3e18 secondes à vivre (et en plus, on ne peut accéder qu'à une
toute petite partie de cet univers dans notre cône de lumière).
J'ai jeté un oeuil à la page Wikipedia et fait une recherche sur
hal, et j'ai pas trouvé une preuve scientifique non discutable !
https://fr.wikipedia.org/wiki/Keyed-hash_message_authentication_code
https://tools.ietf.org/html/rfc3566
https://hal.archives-ouvertes.fr/search/index/?q=hash+&submit=&docType_s=ART+OR+COMM+OR+OUV+OR+COUV+OR+DOUV+OR+REPORT+OR+OTHER+OR+THESE+OR+HDR+OR+LECTURE+OR+UNDEFINED&submitType_s=file
Peut-être j'ai mal cherché ?

Oui, enfin c'est des maths de collège, les bijections…
--
__Pascal Bourguignon__
Publicité
Poster une réponse
Anonyme