cerhu > misc.* > misc.cryptologie

ptilou (15/12/2018, 17h49)
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 ?

J'ai jetter un oeuil à la page Wikipedia et fait une recherche sur hal, et j'ai pas trouvé une preuve scientifique non discutable !
[..]
[..]
[..]

Peut-être j'ai mal cherché ?

merci
ptilou (15/12/2018, 18h35)
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 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 ?
> J'ai jetter un oeuil à la page Wikipedia et fait une recherche sur hal, et j'ai pas trouvé une preuve scientifique non discutable !
> [..]
> [..]
> [..]
> Peut-être j'ai mal cherché ?
> merci
> --
> ptilou


[..]

C'est un petit pavé de 300 pages, si y avait un vulgarisateur de la science, par avance toutes courbettes possibles et imaginable, dit simplementmerci de m'éclairer !
Marc SCHAEFER (15/12/2018, 20h49)
ptilou <ptilou> wrote:
> 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 ?
ptilou (17/12/2018, 11h27)
Slt,

Le samedi 15 décembre 2018 19:49:48 UTC+1, Marc SCHAEFER a écrit :
[..]
> 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 ?


D'après ce que j'ai lu, je ne bombarde pas de liens, la clès de hash seul en effet peut avoir des collisions, mais le couple nom de fichier + cles de hash n'a pas à ce jour de collision connue (en sha 256 et 512) !

Donc le système d'empreinte à ses avantages, inconvénient, on n'est pas à l?abri d'une attaque de l'homme du milieu, avec creation à la volet de cles de hash, ensuite le logiciel qui controle (crée) la cles de hash, on n'est pas sur qu'il ne soit pas "vérolé" !
y a t'il d'autre inconvénient ?
Pascal J. Bourguignon (18/12/2018, 11h37)
ptilou <ptilou> writes:

> 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=16 octets, 8N=128 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 !
> [..]
> [..]
> [..]
> Peut-être j'ai mal cherché ?


Oui, enfin c'est des maths de collège, les bijections?
Discussions similaires
comparaison de fichier par clés de hash ?

cles d'un hash

Initialiser un hash de hash de hash de hash au fur et à mesure

types de données pour les clés des hash


Fuseau horaire GMT +2. Il est actuellement 00h11. | Privacy Policy