un CRC32 se calcule a partir d'un tableau et d'un nombre?
function crc(bit array bitString[1..len], int polynomial)
admettons que j'ai le array, le int polynomial, le nombre de caracteres
en entree et le resultat, puis-je remonter a la valeur des caracteres
en entree?
en gros, j'ai:
crc32(xxxxxx)=986A48BE
le polynomial = 0x00FFFFFF
est il possible de retrouver les 6 'x' ?
Il y a une methode intelligente ou le bruteforce est la solution?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Christophe HENRY
un CRC32 se calcule a partir d'un tableau et d'un nombre? function crc(bit array bitString[1..len], int polynomial)
admettons que j'ai le array, le int polynomial, le nombre de caractères en entrée et le résultat, puis-je remonter a la valeur des caractères en entrée?
Aucune possibilité de retrouver de façon certaine la donnée d'origine. Tout au plus tu peux retrouver des collisions : des données en entrée résultant en le même CRC.
D'une façon générale, le calcul du CRC est à ranger dans les fonctions de hachage à sens unique. A l'instar de MD5 ou de SHA, la somme de contrôle est obtenue par des calculs qu'on ne peut inverser pour retrouver la donnée originale. Le CRC a une taille unique en sortie, pourtant on peut le calculer sur des données de taille variable. S'il était possible de faire le calcul à l'envers, cela voudrait dire qu'il y a une correspondance exacte (une bijection) entre une donnée et sa somme. Impossible à obtenir avec des données de tailles différente.
Voici un exemple simple mettant en évidence l'impossibilité concrète de remonter en arrière :
En guise de somme de contrôle on compte le nombre de bit d'un octet, d'un mot, d'un Ko. Si le nombre est pair, le résultat est 0, sinon 1. Cette fonction renvoie donc un bit. On se rapproche - de loin et par temps de brouillard - du principe du CRC. Il est évident qu'un bit ne contient pas la même quantité d'information que la donnée d'origine ; par là, il n'est pas possible de retrouver la donnée ayant une somme de contrôle à 0 ou 1. Le problème est plus compliqué mais identique sur ce point avec le CRC.
-- Christophe HENRY (sans lkm) GnuPG : 3922239E60036EC86BF7268A877C52AC 4883C02A
un CRC32 se calcule a partir d'un tableau et d'un nombre? function crc(bit
array bitString[1..len], int polynomial)
admettons que j'ai le array, le int polynomial, le nombre de caractères
en entrée et le résultat, puis-je remonter a la valeur des caractères
en entrée?
Aucune possibilité de retrouver de façon certaine la donnée d'origine.
Tout au plus tu peux retrouver des collisions : des données en entrée
résultant en le même CRC.
D'une façon générale, le calcul du CRC est à ranger dans les fonctions
de hachage à sens unique. A l'instar de MD5 ou de SHA, la somme de
contrôle est obtenue par des calculs qu'on ne peut inverser pour
retrouver la donnée originale. Le CRC a une taille unique en sortie,
pourtant on peut le calculer sur des données de taille variable. S'il
était possible de faire le calcul à l'envers, cela voudrait dire qu'il y
a une correspondance exacte (une bijection) entre une donnée et sa somme.
Impossible à obtenir avec des données de tailles différente.
Voici un exemple simple mettant en évidence l'impossibilité concrète de
remonter en arrière :
En guise de somme de contrôle on compte le nombre de bit d'un octet, d'un
mot, d'un Ko. Si le nombre est pair, le résultat est 0, sinon 1. Cette
fonction renvoie donc un bit.
On se rapproche - de loin et par temps de brouillard - du principe du CRC.
Il est évident qu'un bit ne contient pas la même quantité d'information
que la donnée d'origine ; par là, il n'est pas possible de retrouver la
donnée ayant une somme de contrôle à 0 ou 1.
Le problème est plus compliqué mais identique sur ce point avec le CRC.
--
Christophe HENRY
forumslkm.sbgodin@nerim.net (sans lkm)
GnuPG : 3922239E60036EC86BF7268A877C52AC 4883C02A
un CRC32 se calcule a partir d'un tableau et d'un nombre? function crc(bit array bitString[1..len], int polynomial)
admettons que j'ai le array, le int polynomial, le nombre de caractères en entrée et le résultat, puis-je remonter a la valeur des caractères en entrée?
Aucune possibilité de retrouver de façon certaine la donnée d'origine. Tout au plus tu peux retrouver des collisions : des données en entrée résultant en le même CRC.
D'une façon générale, le calcul du CRC est à ranger dans les fonctions de hachage à sens unique. A l'instar de MD5 ou de SHA, la somme de contrôle est obtenue par des calculs qu'on ne peut inverser pour retrouver la donnée originale. Le CRC a une taille unique en sortie, pourtant on peut le calculer sur des données de taille variable. S'il était possible de faire le calcul à l'envers, cela voudrait dire qu'il y a une correspondance exacte (une bijection) entre une donnée et sa somme. Impossible à obtenir avec des données de tailles différente.
Voici un exemple simple mettant en évidence l'impossibilité concrète de remonter en arrière :
En guise de somme de contrôle on compte le nombre de bit d'un octet, d'un mot, d'un Ko. Si le nombre est pair, le résultat est 0, sinon 1. Cette fonction renvoie donc un bit. On se rapproche - de loin et par temps de brouillard - du principe du CRC. Il est évident qu'un bit ne contient pas la même quantité d'information que la donnée d'origine ; par là, il n'est pas possible de retrouver la donnée ayant une somme de contrôle à 0 ou 1. Le problème est plus compliqué mais identique sur ce point avec le CRC.
-- Christophe HENRY (sans lkm) GnuPG : 3922239E60036EC86BF7268A877C52AC 4883C02A
johann.d
"Christophe HENRY" a écrit dans le message de news:
Aucune possibilité de retrouver de façon certaine la donnée d'origine. Tout au plus tu peux retrouver des collisions : des données en entrée résultant en le même CRC.
Si je ne m'abuse l'OP cherchait un antécédent sur 3 octets (6 'x' dans son vocabulaire). Si c'est bien cela le sujet avait déjà été abordé ici : http://groups.google.fr/group/fr.misc.cryptologie/browse_thread/thread/fc9b6356f97dc629/329846f0da774799
-- Johann
"Christophe HENRY" <forumslkm.sbgodin@nerim.net.sans_lkm> a écrit dans le
message de news:uf87j3-7h5.ln1@serveur.sbgodin.net...
Aucune possibilité de retrouver de façon certaine la donnée d'origine.
Tout au plus tu peux retrouver des collisions : des données en entrée
résultant en le même CRC.
Si je ne m'abuse l'OP cherchait un antécédent sur 3 octets (6 'x' dans son
vocabulaire). Si c'est bien cela le sujet avait déjà été abordé ici :
http://groups.google.fr/group/fr.misc.cryptologie/browse_thread/thread/fc9b6356f97dc629/329846f0da774799
"Christophe HENRY" a écrit dans le message de news:
Aucune possibilité de retrouver de façon certaine la donnée d'origine. Tout au plus tu peux retrouver des collisions : des données en entrée résultant en le même CRC.
Si je ne m'abuse l'OP cherchait un antécédent sur 3 octets (6 'x' dans son vocabulaire). Si c'est bien cela le sujet avait déjà été abordé ici : http://groups.google.fr/group/fr.misc.cryptologie/browse_thread/thread/fc9b6356f97dc629/329846f0da774799
-- Johann
Sylvain
johann.d wrote on 09/05/2006 23:05:
"Christophe HENRY" a écrit dans le message de news:
Aucune possibilité de retrouver de façon certaine la donnée d'origine. Tout au plus tu peux retrouver des collisions : des données en entrée résultant en le même CRC.
Si je ne m'abuse l'OP cherchait un antécédent sur 3 octets (6 'x' dans son vocabulaire). Si c'est bien cela le sujet avait déjà été abordé ici : http://groups.google.fr/group/fr.misc.cryptologie/browse_thread/thread/fc9b6356f97dc629/329846f0da774799
en fait sur 6 octets dans [0-9]u[A-Z]u[a-z] - tel qu'il a exprimé sur fr.comp.os.unix
la cardinalité des entrées est (en gros) 13 fois celle des CRC possibles, donc il y aura des collisions et corollairement il ne peut déterminer de manière unique et certaine le message d'origine.
reste que le post de Thomas Pornin dans le thread cité nous rappellais bien la linéarité des algos CRC et donc les "inversabilité" ... pour donner ici plusieurs solutions.
Sylvain.
johann.d wrote on 09/05/2006 23:05:
"Christophe HENRY" <forumslkm.sbgodin@nerim.net.sans_lkm> a écrit dans le
message de news:uf87j3-7h5.ln1@serveur.sbgodin.net...
Aucune possibilité de retrouver de façon certaine la donnée d'origine.
Tout au plus tu peux retrouver des collisions : des données en entrée
résultant en le même CRC.
Si je ne m'abuse l'OP cherchait un antécédent sur 3 octets (6 'x' dans son
vocabulaire). Si c'est bien cela le sujet avait déjà été abordé ici :
http://groups.google.fr/group/fr.misc.cryptologie/browse_thread/thread/fc9b6356f97dc629/329846f0da774799
en fait sur 6 octets dans [0-9]u[A-Z]u[a-z] - tel qu'il a exprimé sur
fr.comp.os.unix
la cardinalité des entrées est (en gros) 13 fois celle des CRC
possibles, donc il y aura des collisions et corollairement il ne peut
déterminer de manière unique et certaine le message d'origine.
reste que le post de Thomas Pornin dans le thread cité nous rappellais
bien la linéarité des algos CRC et donc les "inversabilité" ... pour
donner ici plusieurs solutions.
"Christophe HENRY" a écrit dans le message de news:
Aucune possibilité de retrouver de façon certaine la donnée d'origine. Tout au plus tu peux retrouver des collisions : des données en entrée résultant en le même CRC.
Si je ne m'abuse l'OP cherchait un antécédent sur 3 octets (6 'x' dans son vocabulaire). Si c'est bien cela le sujet avait déjà été abordé ici : http://groups.google.fr/group/fr.misc.cryptologie/browse_thread/thread/fc9b6356f97dc629/329846f0da774799
en fait sur 6 octets dans [0-9]u[A-Z]u[a-z] - tel qu'il a exprimé sur fr.comp.os.unix
la cardinalité des entrées est (en gros) 13 fois celle des CRC possibles, donc il y aura des collisions et corollairement il ne peut déterminer de manière unique et certaine le message d'origine.
reste que le post de Thomas Pornin dans le thread cité nous rappellais bien la linéarité des algos CRC et donc les "inversabilité" ... pour donner ici plusieurs solutions.
