Hors Sujet: Fonction de hashage cryptographique

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Hors Sujet: Fonction de hashage cryptographique

Ludovic Gélé
Bonjour à tous,

Juste une petite question (sûrement débile, mais bon). On a parlé
beaucoup de collision au sujet de md5, et je me demandais ce qui se
passe si on calcul les signatures de tous les fichiers plus grands que
la taille de la signature elle-même.

Un petit exemple: SHA256 produit des signatures sur 256 octets (si j'ai
bien compris), il y a donc 2^2048 signatures possibles. Admettons que je
calcul les signatures de tous les fichiers de 257 octets, soit les
signatures de 2^2056 fichiers tous de même tailles. Étant donné que j'ai
plus de fichiers possible que de signature, je vais avoir des fichiers
différents avec la même la même signature, non?

Si oui, comment éviter ça? En signant avec deux fonctions différentes?

D'avance merci pour tout éclaircissement, et n'hésitez pas à me répondre
en privé.

PS: Non, je n'ai pas de cluster à la maison ;-)

--
   Cordialement


http://scolyo.blogspot.com


________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Julien Escario
Le 03/11/2010 11:30, Ludovic Gélé a écrit :

> Bonjour à tous,
>
> Juste une petite question (sûrement débile, mais bon). On a parlé beaucoup de
> collision au sujet de md5, et je me demandais ce qui se passe si on calcul les
> signatures de tous les fichiers plus grands que la taille de la signature
> elle-même.
>
> Un petit exemple: SHA256 produit des signatures sur 256 octets (si j'ai bien
> compris), il y a donc 2^2048 signatures possibles. Admettons que je calcul les
> signatures de tous les fichiers de 257 octets, soit les signatures de 2^2056
> fichiers tous de même tailles. Étant donné que j'ai plus de fichiers possible
> que de signature, je vais avoir des fichiers différents avec la même la même
> signature, non?

Oui, forcément, il va y avoir collision à un moment ou un autre.
La sécurité de ce type de hachages se base sur le fait qu'il est impossible à un
instant donné de calculer tous les hachages de 2048 bytes.
Le soucis de cet exercice c'est qu'une signature doit être lisible, or avec
l'augmentation de la taille des hachages (aujourd'hui 2048, bientôt 4096) (qui
va s'amuser à comparer deux signatures de plusieurs milliers de caractères ? Les
gens vont commencer à comparer les premiers et les derniers chiffres (ce que je
fais déjà quand je veux valider le transfert d'un fichier entre deux de mes
machines) et on tuera la sécurité apportée pour ces systèmes.

Verdict : il faut soit démocratiser la vérification par logiciel soit changer le
système.

Certains sites commencent à proposer de retrouver le mot de passe original quand
on leur met le hachage md5. Ils créent tout simplement une base données.

> Si oui, comment éviter ça? En signant avec deux fonctions différentes?

Oui mais la somme de contrôle va commencer à être longuette ... (c'était un peu
le principe de 3DES quand DES a été cassé).

> D'avance merci pour tout éclaircissement, et n'hésitez pas à me répondre en privé.
>
> PS: Non, je n'ai pas de cluster à la maison ;-)

Dommage ... ca peut toujours être utile ;-)

Julien

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Nicolas Bernard-2
In reply to this post by Ludovic Gélé
Ludovic Gélé([hidden email])@2010.11.03 11:30:25 +0100 wrote:
> Bonjour à tous,
>
> Juste une petite question (sûrement débile, mais bon). On a parlé
> beaucoup de collision au sujet de md5, et je me demandais ce qui se
> passe si on calcul les signatures de tous les fichiers plus grands
> que la taille de la signature elle-même.
>
> Un petit exemple: SHA256 produit des signatures sur 256 octets (si

256 bits (et SHA produit des empreintes, pas des signatures).

> j'ai bien compris), il y a donc 2^2048 signatures possibles.

Non, seulement 2^256.

> Admettons que je calcul les signatures de tous les fichiers de 257
> octets, soit les signatures de 2^2056 fichiers tous de même tailles.
> Étant donné que j'ai plus de fichiers possible que de signature, je
> vais avoir des fichiers différents avec la même la même signature,
> non?

aux corrections bits/octets près, oui.

> Si oui, comment éviter ça? En signant avec deux fonctions différentes?

Pas réellement, dans ce cas tu arrives au mieux à 2^(taille fct1 +
taille fct2). Mais calcule donc la place qu'il faut pour stocker tous
ces fichiers et surtout le temps qu'il faudrait pour calculer
l'empreinte de chacun, tu va voir... ;-)

N.

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Julien Cabillot-2
In reply to this post by Ludovic Gélé
Le 03/11/2010 11:30, Ludovic Gélé a écrit :

> Bonjour à tous,
>
> Juste une petite question (sûrement débile, mais bon). On a parlé
> beaucoup de collision au sujet de md5, et je me demandais ce qui se
> passe si on calcul les signatures de tous les fichiers plus grands que
> la taille de la signature elle-même.
>
> Un petit exemple: SHA256 produit des signatures sur 256 octets (si j'ai
> bien compris), il y a donc 2^2048 signatures possibles. Admettons que je
> calcul les signatures de tous les fichiers de 257 octets, soit les
> signatures de 2^2056 fichiers tous de même tailles. Étant donné que j'ai
> plus de fichiers possible que de signature, je vais avoir des fichiers
> différents avec la même la même signature, non?
>
> Si oui, comment éviter ça? En signant avec deux fonctions différentes?
>
> D'avance merci pour tout éclaircissement, et n'hésitez pas à me répondre
> en privé.
>
> PS: Non, je n'ai pas de cluster à la maison ;-)
>

Forcément, tu as un nombre fini de md5/sha256 et tu vas te retrouver
avec des collisions.
Le problème de sécurité c'est de se retrouver avec un binaire usurpé à
la place de ton binaire avec le même sha256. Mais c'est extrêmement
compliqué d'avoir un fichier avec le même hash, tout en restant
exécutable (ou par exemple pour un pdf, de rester lisible par un reader
pdf).

Tu veux moins de collisions ? sha512 :)

Julien

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Jean-Francois Simon
In reply to this post by Ludovic Gélé
Le Wednesday 03 November 2010 11:30:25, Ludovic Gélé a écrit :

> Bonjour à tous,
>
> Juste une petite question (sûrement débile, mais bon). On a parlé
> beaucoup de collision au sujet de md5, et je me demandais ce qui se
> passe si on calcul les signatures de tous les fichiers plus grands que
> la taille de la signature elle-même.
>
> Un petit exemple: SHA256 produit des signatures sur 256 octets (si j'ai
> bien compris), il y a donc 2^2048 signatures possibles. Admettons que je
> calcul les signatures de tous les fichiers de 257 octets, soit les
> signatures de 2^2056 fichiers tous de même tailles. Étant donné que j'ai
> plus de fichiers possible que de signature, je vais avoir des fichiers
> différents avec la même la même signature, non?
>
> Si oui, comment éviter ça? En signant avec deux fonctions différentes?
>
> D'avance merci pour tout éclaircissement, et n'hésitez pas à me répondre
> en privé.
>
> PS: Non, je n'ai pas de cluster à la maison ;-)

On peut estimer le nombre de fichier en puissance de 10.
2^256 ~ 10^80.

Est-ce que je fais erreur ? En tout cas un nombre de fichier suffisant dans la
plupart des cas. On dépasse probablement la capacité physique ou de certains
systèmes de fichiers en tout cas.

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Ludovic Gélé
In reply to this post by Julien Escario
Le 03/11/2010 11:35, Julien Escario a écrit :

> Le 03/11/2010 11:30, Ludovic Gélé a écrit :
>> Bonjour à tous,
>>
>> Juste une petite question (sûrement débile, mais bon). On a parlé
>> beaucoup de
>> collision au sujet de md5, et je me demandais ce qui se passe si on
>> calcul les
>> signatures de tous les fichiers plus grands que la taille de la
>> signature
>> elle-même.
>>
>> Un petit exemple: SHA256 produit des signatures sur 256 octets (si
>> j'ai bien
>> compris), il y a donc 2^2048 signatures possibles. Admettons que je
>> calcul les
>> signatures de tous les fichiers de 257 octets, soit les signatures de
>> 2^2056
>> fichiers tous de même tailles. Étant donné que j'ai plus de fichiers
>> possible
>> que de signature, je vais avoir des fichiers différents avec la même
>> la même
>> signature, non?
>
> Oui, forcément, il va y avoir collision à un moment ou un autre.
> La sécurité de ce type de hachages se base sur le fait qu'il est
> impossible à un instant donné de calculer tous les hachages de 2048
> bytes.
> Le soucis de cet exercice c'est qu'une signature doit être lisible, or
> avec l'augmentation de la taille des hachages (aujourd'hui 2048,
> bientôt 4096) (qui va s'amuser à comparer deux signatures de plusieurs
> milliers de caractères ? Les gens vont commencer à comparer les
> premiers et les derniers chiffres (ce que je fais déjà quand je veux
> valider le transfert d'un fichier entre deux de mes machines) et on
> tuera la sécurité apportée pour ces systèmes.
>
> Verdict : il faut soit démocratiser la vérification par logiciel soit
> changer le système.
>
> Certains sites commencent à proposer de retrouver le mot de passe
> original quand on leur met le hachage md5. Ils créent tout simplement
> une base données.
>
>> Si oui, comment éviter ça? En signant avec deux fonctions différentes?
>
> Oui mais la somme de contrôle va commencer à être longuette ...
> (c'était un peu le principe de 3DES quand DES a été cassé).
>
>> D'avance merci pour tout éclaircissement, et n'hésitez pas à me
>> répondre en privé.
>>
>> PS: Non, je n'ai pas de cluster à la maison ;-)
>
> Dommage ... ca peut toujours être utile ;-)

C'est sur, mais bon, c'est Madame qui ne serait pas contente.

Encore merci :D

--
   Cordialement


http://scolyo.blogspot.com


________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Ludovic Gélé
In reply to this post by Nicolas Bernard-2
Le 03/11/2010 11:36, Nicolas Bernard a écrit :

> Ludovic Gélé([hidden email])@2010.11.03 11:30:25 +0100 wrote:
>    
>> Bonjour à tous,
>>
>> Juste une petite question (sûrement débile, mais bon). On a parlé
>> beaucoup de collision au sujet de md5, et je me demandais ce qui se
>> passe si on calcul les signatures de tous les fichiers plus grands
>> que la taille de la signature elle-même.
>>
>> Un petit exemple: SHA256 produit des signatures sur 256 octets (si
>>      
> 256 bits (et SHA produit des empreintes, pas des signatures).
>    

ah pardon, désolé pour la méprise, je croyais que c'était des octets

>> j'ai bien compris), il y a donc 2^2048 signatures possibles.
>>      
> Non, seulement 2^256.
>    

>> Admettons que je calcul les signatures de tous les fichiers de 257
>> octets, soit les signatures de 2^2056 fichiers tous de même tailles.
>> Étant donné que j'ai plus de fichiers possible que de signature, je
>> vais avoir des fichiers différents avec la même la même signature,
>> non?
>>      
> aux corrections bits/octets près, oui.
>
>    
>> Si oui, comment éviter ça? En signant avec deux fonctions différentes?
>>      
> Pas réellement, dans ce cas tu arrives au mieux à 2^(taille fct1 +
> taille fct2). Mais calcule donc la place qu'il faut pour stocker tous
> ces fichiers et surtout le temps qu'il faudrait pour calculer
> l'empreinte de chacun, tu va voir... ;-)
>    

Étant donné ma tendance à confondre octets et bits (faut pas le dire à
me prof), je ferais ça une autre fois ;-)

Merci

--
   Cordialement


http://scolyo.blogspot.com


________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Ludovic Gélé
In reply to this post by Julien Cabillot-2
Le 03/11/2010 11:37, Cabillot Julien a écrit :

> Le 03/11/2010 11:30, Ludovic Gélé a écrit :
>> Bonjour à tous,
>>
>> Juste une petite question (sûrement débile, mais bon). On a parlé
>> beaucoup de collision au sujet de md5, et je me demandais ce qui se
>> passe si on calcul les signatures de tous les fichiers plus grands que
>> la taille de la signature elle-même.
>>
>> Un petit exemple: SHA256 produit des signatures sur 256 octets (si j'ai
>> bien compris), il y a donc 2^2048 signatures possibles. Admettons que je
>> calcul les signatures de tous les fichiers de 257 octets, soit les
>> signatures de 2^2056 fichiers tous de même tailles. Étant donné que j'ai
>> plus de fichiers possible que de signature, je vais avoir des fichiers
>> différents avec la même la même signature, non?
>>
>> Si oui, comment éviter ça? En signant avec deux fonctions différentes?
>>
>> D'avance merci pour tout éclaircissement, et n'hésitez pas à me répondre
>> en privé.
>>
>> PS: Non, je n'ai pas de cluster à la maison ;-)
>>
>
> Forcément, tu as un nombre fini de md5/sha256 et tu vas te retrouver
> avec des collisions.
> Le problème de sécurité c'est de se retrouver avec un binaire usurpé à
> la place de ton binaire avec le même sha256. Mais c'est extrêmement
> compliqué d'avoir un fichier avec le même hash, tout en restant
> exécutable (ou par exemple pour un pdf, de rester lisible par un
> reader pdf).
>
> Tu veux moins de collisions ? sha512 :)

Justement, c'est le problème que je risque de rencontrer. Je voudrais
dédupliquer des données, et signer les blocs. Si deux blocs différents
on la même signature, (n'est-ce pas Murphy), je dois contourner ça. Je
pensais donc signer deux fois, un coup en sha256 et un coup en md5. La
probabilité pour qu'un autre bloc ait le même couple de signature me
semble acceptable.

Merci encore

--
   Cordialement


http://scolyo.blogspot.com


________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

jc1-2
In reply to this post by Jean-Francois Simon
Le 03/11/2010 12:50, Jean-Francois a écrit :

> Le Wednesday 03 November 2010 11:30:25, Ludovic Gélé a écrit :
>> Bonjour à tous,
>>
>> Juste une petite question (sûrement débile, mais bon). On a parlé
>> beaucoup de collision au sujet de md5, et je me demandais ce qui se
>> passe si on calcul les signatures de tous les fichiers plus grands que
>> la taille de la signature elle-même.
>>
>> Un petit exemple: SHA256 produit des signatures sur 256 octets (si j'ai
>> bien compris), il y a donc 2^2048 signatures possibles. Admettons que je
>> calcul les signatures de tous les fichiers de 257 octets, soit les
>> signatures de 2^2056 fichiers tous de même tailles. Étant donné que j'ai
>> plus de fichiers possible que de signature, je vais avoir des fichiers
>> différents avec la même la même signature, non?
>>
>> Si oui, comment éviter ça? En signant avec deux fonctions différentes?
>>
>> D'avance merci pour tout éclaircissement, et n'hésitez pas à me répondre
>> en privé.
>>
>> PS: Non, je n'ai pas de cluster à la maison ;-)
>
> On peut estimer le nombre de fichier en puissance de 10.
> 2^256 ~ 10^80.
>
> Est-ce que je fais erreur ? En tout cas un nombre de fichier suffisant dans la
> plupart des cas. On dépasse probablement la capacité physique ou de certains
> systèmes de fichiers en tout cas.

2^256 pour chipoter 1,16 ^ 77 fichiers de 256 octets.

Cela fait en tera octets (1,16 ^ 77 * 256) / 1^ 12 = 2,96 ^67 Tio
A 70 Euro le disque d'un 1 Tio (environ), 2 ^ 69 Euros (je ne sais même
pas combien cela fait, enfin ridicule par rapport à ma paye horaire ;)).

Et le temps de calcul, 1 seconde pour 1000 fichiers (pourquoi 1000,
pourquoi pas!!! je n'ai pas d'idée sur ce temps, donc ...), 1,16 ^74
seconde.
L'univers à 14^9 ans => 4,4^17 secondes

Je n'aimerai pas payer la note d'électricité du truc qui serait capable
de faire cela ;)

PS : est-ce que le "2^256 solutions possibles" est bon ?

PS1 : "2^2048 signatures possibles" => niak, niak, niak ...

PS2 : cela sent la phosphoration d'un chercheur cette question ;)
--

Cordialement,

Jean-Claude aka jc1

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Philippe Schwarz
Le 03/11/2010 15:41, jc1 a écrit :
> Le 03/11/2010 12:50, Jean-Francois a écrit :
>> Le Wednesday 03 November 2010 11:30:25, Ludovic Gélé a écrit :
.

> Justement, c'est le problème que je risque de rencontrer. Je voudrais
> dédupliquer des données, et signer les blocs. Si deux blocs différents

.
> PS2 : cela sent la phosphoration d'un chercheur cette question ;)
Ou de celui qui veut bien réfléchir à son usage de ZFS ?

Si c'est le cas, et qu'on tient à ses données, pas certain que l'usage
de dedup soit une bonne idée..mais je m'égare!

A+

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

js-35
In reply to this post by jc1-2
Moi, je dirais mieux. Mais bon ....

PS2 : cela sent la phosphoration d'un chercheur cette question ;)
--

Cordialement,

Jean-Claude aka jc1

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php




Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

Ludovic Gélé
In reply to this post by jc1-2
Le 03/11/2010 15:41, jc1 a écrit :

> Le 03/11/2010 12:50, Jean-Francois a écrit :
>> Le Wednesday 03 November 2010 11:30:25, Ludovic Gélé a écrit :
>>> Bonjour à tous,
>>>
>>> Juste une petite question (sûrement débile, mais bon). On a parlé
>>> beaucoup de collision au sujet de md5, et je me demandais ce qui se
>>> passe si on calcul les signatures de tous les fichiers plus grands que
>>> la taille de la signature elle-même.
>>>
>>> Un petit exemple: SHA256 produit des signatures sur 256 octets (si j'ai
>>> bien compris), il y a donc 2^2048 signatures possibles. Admettons
>>> que je
>>> calcul les signatures de tous les fichiers de 257 octets, soit les
>>> signatures de 2^2056 fichiers tous de même tailles. Étant donné que
>>> j'ai
>>> plus de fichiers possible que de signature, je vais avoir des fichiers
>>> différents avec la même la même signature, non?
>>>
>>> Si oui, comment éviter ça? En signant avec deux fonctions différentes?
>>>
>>> D'avance merci pour tout éclaircissement, et n'hésitez pas à me
>>> répondre
>>> en privé.
>>>
>>> PS: Non, je n'ai pas de cluster à la maison ;-)
>>
>> On peut estimer le nombre de fichier en puissance de 10.
>> 2^256 ~ 10^80.
>>
>> Est-ce que je fais erreur ? En tout cas un nombre de fichier
>> suffisant dans la
>> plupart des cas. On dépasse probablement la capacité physique ou de
>> certains
>> systèmes de fichiers en tout cas.
>
> 2^256 pour chipoter 1,16 ^ 77 fichiers de 256 octets.
>
> Cela fait en tera octets (1,16 ^ 77 * 256) / 1^ 12 = 2,96 ^67 Tio
> A 70 Euro le disque d'un 1 Tio (environ), 2 ^ 69 Euros (je ne sais
> même pas combien cela fait, enfin ridicule par rapport à ma paye
> horaire ;)).
>
> Et le temps de calcul, 1 seconde pour 1000 fichiers (pourquoi 1000,
> pourquoi pas!!! je n'ai pas d'idée sur ce temps, donc ...), 1,16 ^74
> seconde.
> L'univers à 14^9 ans => 4,4^17 secondes
>
> Je n'aimerai pas payer la note d'électricité du truc qui serait
> capable de faire cela ;)
>
> PS : est-ce que le "2^256 solutions possibles" est bon ?
>
> PS1 : "2^2048 signatures possibles" => niak, niak, niak ...

rooo, ça va, j'ai mal lu ;-)
J'ai une excuse, je suis papa pour la deuxième fois depuis trois
semaines, les nuits sont courtes :D

> PS2 : cela sent la phosphoration d'un chercheur cette question ;)

Je n'ai pas phosphoré aussi loin que toi ;-)
Je me suis juste dis que je pourrais ne pas avoir de bol et tomber sur
deux bloc de données différents pour une même empreinte.
Peu probable, je m'en doutais, mais je ne savais pas si c'était possible
ou pas.

--
   Cordialement


http://scolyo.blogspot.com


________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php

Reply | Threaded
Open this post in threaded view
|

Re: Hors Sujet: Fonction de hashage cryptographique

jc1-2
Le 03/11/2010 16:03, Ludovic Gélé a écrit :
>>
>> PS1 : "2^2048 signatures possibles" => niak, niak, niak ...
>
> rooo, ça va, j'ai mal lu ;-)

mon "niak, niak niak", voulait dire seulement, vous avez vu ce que cela
donne avec 256, alors avec 2048, !!!

> J'ai une excuse, je suis papa pour la deuxième fois depuis trois
> semaines, les nuits sont courtes :D

Je comprend (je compatis) et je te félicite.


>> PS2 : cela sent la phosphoration d'un chercheur cette question ;)
>
> Je n'ai pas phosphoré aussi loin que toi ;-)

J'aime les chiffres :D
J'ai voulu avoir une idée de ce que cela donnait.
Je ne rendais pas compte du résultat (cf plus bas), là ..


> Je me suis juste dis que je pourrais ne pas avoir de bol et tomber sur
> deux bloc de données différents pour une même empreinte.
> Peu probable, je m'en doutais, mais je ne savais pas si c'était possible
> ou pas.

Hum, là ta vraiment pas de bol ;)
Au loto tu as 1 chance sur 13 ^ 9 ;)

C'est suite à la réponse de xxx (désolé, je ne retrouve plus, doublement
mille excuses), disant que le FS ne pourrait pas supporter le nb de
fichiers.
Je me suis dit, "pouf, même pas vrai !! Et si je faisais les calculs
pour lui démonter qu'il a tord !!!"
Et en faisant les calculs, "non, whaou !!! il a raison, tout faux le jc !!!"

Très intéressante et amusante question :)

--

Cordialement,

Jean-Claude aka jc1

________________________________
French OpenBSD mailing list
[hidden email]
http://www.openbsd-france.org/communaute.php