calcul de crc32

Sébastien Monbrun aka TiChou

10/05/2006 à 03:30

Dans le message
<news:,
** tapota sur f.c.o.unix :

Qu'est-ce que tu cherches exactement?

j'ai un CRC32
je sais que ce sont 6 caracteres qui donnent ce CRC

je voudrais connaitre la liste de tous les 6 caracteres
qui me donnent le CRC32

Je me suis intéressé il y a quelques années à coder quelques petits outils
CRC32 en perl dont un « proof of concept » avec « reverse engineering » pour
démontrer que la signature de fichier (checksum) en CRC32 est facilement
falsifiable (je ne suis pas sûr d'être très clair mais je pense que ceux qui
se sont déjà intéressé à la chose me comprendront).

Un premier script dont le calcul est relativement rapide puisque la table
des polynômes servant au calcul CRC32 est déjà pré-calculée :

,----[ crc32.pl ]

#!/usr/bin/perl

@table = (
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d);

$crc = 0xFFFFFFFF;
$len = length($ARGV[0]);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($ARGV[0],$i,1))) & 0xff];
}

printf "crc = %sn 0xU%08xn", $crc, $crc;

$crc32 = $crc ^ 0xFFFFFFFF;

printf "crc32 = %sn 0xU%08xn", $crc32, $crc32;

`----[ crc32.pl ]

La même chose, théoriquement plus lent, car on calcule d'abord la table des
polynômes :

,----[ crcxx.pl ]

#!/usr/bin/perl

$polynome = 0xEDB88320;
for ($i = 0; $i < 256; $i++) {
$crc = $i;
for ($j = 8; $j > 0; $j--) {
if ($crc & 0x01) {
$crc = ($crc >> 1) ^ $polynome;
} else {
$crc = $crc >> 1;
}
}
$table[$i] = $crc;
}

$crc = 0xFFFFFFFF;
$len = length($ARGV[0]);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($ARGV[0],$i,1))) & 0xff];
}

$crc32 = $crc ^ 0xFFFFFFFF;
printf "crc32 = %sn 0xU%08xn", $crc32, $crc32;

`----[ M-ID crcxx.pl ]

et enfin le script perl qui fait du « reverse CRC32 », c'est-à-dire qu'il va
trouver toutes les chaînes de caractères qui ont comme checksum celui donné
en argument au script :

,----[ crc32rev.pl ]

#!/usr/bin/perl

$polynome = 0xEDB88320;
for ($i = 0; $i < 256; $i++) {
$crc = $i;
for ($j = 8; $j > 0; $j--) {
if ($crc & 0x01) {
$crc = ($crc >> 1) ^ $polynome;
} else {
$crc = $crc >> 1;
}
}
$table[$i] = $crc;
$tablepos[$crc >> 24] = $i;
}

sub splitcrc {
$crc = shift;
$l = shift;
${$l.3} = $crc >> 24;
${$l.2} = ($crc >> 16) & 0xff;
${$l.1} = ($crc >> 8) & 0xff;
${$l.0} = $crc & 0xff;
}

@tablo = ("",0..9,a..z,A..Z);
$" = "";
$base = $#tablo+1;
$max = 3;

$ARGV[0] =~ /^(0x)([[:xdigit:]]+)$/ && ($crc32 = hex($2));

printf "crc32t= %snt 0xU%08xn", $crc32, $crc32;

$crc = $crc32 ^ 0xFFFFFFFF;

printf "crct= %snt 0xU%08xn", $crc, $crc;

&splitcrc($crc, f);

$count = 0;
while ($count < ($base ** $max)) {
$pref = "";
$M = $count;
until ($M < $base) {
$S = $M % $base;
$pref .= $tablo[$S];
$M = int $M / $base;
}
$pref .= $tablo[$M];
if($count % $base) {
$crc = 0xFFFFFFFF;
$len = length($pref);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($pref,$i,1))) & 0xff];
}

&splitcrc($crc, a);

$g3 = $tablepos[$f3];
&splitcrc($table[$g3], e);

$g2 = $tablepos[$f2 ^ $e2];
&splitcrc($table[$g2], d);

$g1 = $tablepos[$f1 ^ $e1 ^ $d2];
&splitcrc($table[$g1], c);

$g0 = $tablepos[$f0 ^ $e0 ^ $d1 ^ $c2];
&splitcrc($table[$g0], b);

$h0 = $g0 ^ $a0;
$h1 = $g1 ^ $b0 ^ $a1;
$h2 = $g2 ^ $c0 ^ $b1 ^ $a2;
$h3 = $g3 ^ $d0 ^ $c1 ^ $b2 ^ $a3;

$" = "";
if (($sub = chr($h0).chr($h1).chr($h2).chr($h3)) =~ /^[@tablo]{4}$/s) {
print "$pref$subn";
}
}
$count++;
}

`----[ crc32rev.pl ]

Les résultats sont obtenus à vitesse grand V comparés à un algo qui ferait
du brute force (c'est-à-dire calculer tous les checksums de toutes les
combinaisons de chaînes de caractères possibles et ne retenir que les
chaînes ayant le checksum voulu).

Sinon, on remarquera qu'à l'époque je débutais sous perl. J'avoue, j'ai
honte de mon code. :-P

ex: 123456 me donne: B8B072C2

Hmmm. Et comment avez-vous obtenu ce CRC32 ?

$ ./crc32.pl "123456"
crc = 4136447134
0xF68D2C9E
crc32 = 158520161
0x0972D361

Donc le même résultat que celui donné par Stéphane Chazelas.

y a t'il d'autres chaines de 6 caracteres qui me donnent ce resultat?

$ ./crc32rev.pl 0x0972D361
crc32 = 158520161
0x0972D361
crc = 4136447134
0xF68D2C9E
r1Oyht
123456 <- ;-)
5gLTXI
hgUwMF
Gg8OQT
fhJGqH
HhfNvC
eHA42X
xJq9PI
POTcgd
YYLmqA

Je pensais qu'il existatit un utilitaire en ligne de commande comme
md5sum qui me calculait les crc32, mais je n'ai pas trouve.

j'aurais fait tourner le programme avec l'ensemble des chaines de
6 caracteres et verifie avec mon resultat.

Ouch ! :-) Que de ressources il vous faudra alors. ;-)

--
Sébastien Monbrun aka TiChou

Dans le message
<news:1147186415.743608.238790@i39g2000cwa.googlegroups.com>,
*octane@alinto.com* tapota sur f.c.o.unix :

Qu'est-ce que tu cherches exactement?

j'ai un CRC32
je sais que ce sont 6 caracteres qui donnent ce CRC

je voudrais connaitre la liste de tous les 6 caracteres
qui me donnent le CRC32

Je me suis intéressé il y a quelques années à coder quelques petits outils
CRC32 en perl dont un « proof of concept » avec « reverse engineering » pour
démontrer que la signature de fichier (checksum) en CRC32 est facilement
falsifiable (je ne suis pas sûr d'être très clair mais je pense que ceux qui
se sont déjà intéressé à la chose me comprendront).

Un premier script dont le calcul est relativement rapide puisque la table
des polynômes servant au calcul CRC32 est déjà pré-calculée :

,----[ crc32.pl ]

#!/usr/bin/perl

@table = (
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d);

$crc = 0xFFFFFFFF;
$len = length($ARGV[0]);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($ARGV[0],$i,1))) & 0xff];
}

printf "crc = %sn 0xU%08xn", $crc, $crc;

$crc32 = $crc ^ 0xFFFFFFFF;

printf "crc32 = %sn 0xU%08xn", $crc32, $crc32;

`----[ crc32.pl ]

La même chose, théoriquement plus lent, car on calcule d'abord la table des
polynômes :

,----[ crcxx.pl ]

#!/usr/bin/perl

$polynome = 0xEDB88320;
for ($i = 0; $i < 256; $i++) {
$crc = $i;
for ($j = 8; $j > 0; $j--) {
if ($crc & 0x01) {
$crc = ($crc >> 1) ^ $polynome;
} else {
$crc = $crc >> 1;
}
}
$table[$i] = $crc;
}

$crc = 0xFFFFFFFF;
$len = length($ARGV[0]);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($ARGV[0],$i,1))) & 0xff];
}

$crc32 = $crc ^ 0xFFFFFFFF;
printf "crc32 = %sn 0xU%08xn", $crc32, $crc32;

`----[ M-ID crcxx.pl ]

et enfin le script perl qui fait du « reverse CRC32 », c'est-à-dire qu'il va
trouver toutes les chaînes de caractères qui ont comme checksum celui donné
en argument au script :

,----[ crc32rev.pl ]

#!/usr/bin/perl

$polynome = 0xEDB88320;
for ($i = 0; $i < 256; $i++) {
$crc = $i;
for ($j = 8; $j > 0; $j--) {
if ($crc & 0x01) {
$crc = ($crc >> 1) ^ $polynome;
} else {
$crc = $crc >> 1;
}
}
$table[$i] = $crc;
$tablepos[$crc >> 24] = $i;
}

sub splitcrc {
$crc = shift;
$l = shift;
${$l.3} = $crc >> 24;
${$l.2} = ($crc >> 16) & 0xff;
${$l.1} = ($crc >> 8) & 0xff;
${$l.0} = $crc & 0xff;
}

@tablo = ("",0..9,a..z,A..Z);
$" = "";
$base = $#tablo+1;
$max = 3;

$ARGV[0] =~ /^(0x)([[:xdigit:]]+)$/ && ($crc32 = hex($2));

printf "crc32t= %snt 0xU%08xn", $crc32, $crc32;

$crc = $crc32 ^ 0xFFFFFFFF;

printf "crct= %snt 0xU%08xn", $crc, $crc;

&splitcrc($crc, f);

$count = 0;
while ($count < ($base ** $max)) {
$pref = "";
$M = $count;
until ($M < $base) {
$S = $M % $base;
$pref .= $tablo[$S];
$M = int $M / $base;
}
$pref .= $tablo[$M];
if($count % $base) {
$crc = 0xFFFFFFFF;
$len = length($pref);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($pref,$i,1))) & 0xff];
}

&splitcrc($crc, a);

$g3 = $tablepos[$f3];
&splitcrc($table[$g3], e);

$g2 = $tablepos[$f2 ^ $e2];
&splitcrc($table[$g2], d);

$g1 = $tablepos[$f1 ^ $e1 ^ $d2];
&splitcrc($table[$g1], c);

$g0 = $tablepos[$f0 ^ $e0 ^ $d1 ^ $c2];
&splitcrc($table[$g0], b);

$h0 = $g0 ^ $a0;
$h1 = $g1 ^ $b0 ^ $a1;
$h2 = $g2 ^ $c0 ^ $b1 ^ $a2;
$h3 = $g3 ^ $d0 ^ $c1 ^ $b2 ^ $a3;

$" = "";
if (($sub = chr($h0).chr($h1).chr($h2).chr($h3)) =~ /^[@tablo]{4}$/s) {
print "$pref$subn";
}
}
$count++;
}

`----[ crc32rev.pl ]

Les résultats sont obtenus à vitesse grand V comparés à un algo qui ferait
du brute force (c'est-à-dire calculer tous les checksums de toutes les
combinaisons de chaînes de caractères possibles et ne retenir que les
chaînes ayant le checksum voulu).

Sinon, on remarquera qu'à l'époque je débutais sous perl. J'avoue, j'ai
honte de mon code. :-P

ex: 123456 me donne: B8B072C2

Hmmm. Et comment avez-vous obtenu ce CRC32 ?

$ ./crc32.pl "123456"
crc = 4136447134
0xF68D2C9E
crc32 = 158520161
0x0972D361

Donc le même résultat que celui donné par Stéphane Chazelas.

y a t'il d'autres chaines de 6 caracteres qui me donnent ce resultat?

$ ./crc32rev.pl 0x0972D361
crc32 = 158520161
0x0972D361
crc = 4136447134
0xF68D2C9E
r1Oyht
123456 <- ;-)
5gLTXI
hgUwMF
Gg8OQT
fhJGqH
HhfNvC
eHA42X
xJq9PI
POTcgd
YYLmqA

Je pensais qu'il existatit un utilitaire en ligne de commande comme
md5sum qui me calculait les crc32, mais je n'ai pas trouve.

j'aurais fait tourner le programme avec l'ensemble des chaines de
6 caracteres et verifie avec mon resultat.

Ouch ! :-) Que de ressources il vous faudra alors. ;-)

--
Sébastien Monbrun aka TiChou

Vous avez filtré cet utilisateur ! Consultez son message

Dans le message
<news:,
** tapota sur f.c.o.unix :

Qu'est-ce que tu cherches exactement?

j'ai un CRC32
je sais que ce sont 6 caracteres qui donnent ce CRC

je voudrais connaitre la liste de tous les 6 caracteres
qui me donnent le CRC32

Je me suis intéressé il y a quelques années à coder quelques petits outils
CRC32 en perl dont un « proof of concept » avec « reverse engineering » pour
démontrer que la signature de fichier (checksum) en CRC32 est facilement
falsifiable (je ne suis pas sûr d'être très clair mais je pense que ceux qui
se sont déjà intéressé à la chose me comprendront).

Un premier script dont le calcul est relativement rapide puisque la table
des polynômes servant au calcul CRC32 est déjà pré-calculée :

,----[ crc32.pl ]

#!/usr/bin/perl

@table = (
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d);

$crc = 0xFFFFFFFF;
$len = length($ARGV[0]);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($ARGV[0],$i,1))) & 0xff];
}

printf "crc = %sn 0xU%08xn", $crc, $crc;

$crc32 = $crc ^ 0xFFFFFFFF;

printf "crc32 = %sn 0xU%08xn", $crc32, $crc32;

`----[ crc32.pl ]

La même chose, théoriquement plus lent, car on calcule d'abord la table des
polynômes :

,----[ crcxx.pl ]

#!/usr/bin/perl

$polynome = 0xEDB88320;
for ($i = 0; $i < 256; $i++) {
$crc = $i;
for ($j = 8; $j > 0; $j--) {
if ($crc & 0x01) {
$crc = ($crc >> 1) ^ $polynome;
} else {
$crc = $crc >> 1;
}
}
$table[$i] = $crc;
}

$crc = 0xFFFFFFFF;
$len = length($ARGV[0]);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($ARGV[0],$i,1))) & 0xff];
}

$crc32 = $crc ^ 0xFFFFFFFF;
printf "crc32 = %sn 0xU%08xn", $crc32, $crc32;

`----[ M-ID crcxx.pl ]

et enfin le script perl qui fait du « reverse CRC32 », c'est-à-dire qu'il va
trouver toutes les chaînes de caractères qui ont comme checksum celui donné
en argument au script :

,----[ crc32rev.pl ]

#!/usr/bin/perl

$polynome = 0xEDB88320;
for ($i = 0; $i < 256; $i++) {
$crc = $i;
for ($j = 8; $j > 0; $j--) {
if ($crc & 0x01) {
$crc = ($crc >> 1) ^ $polynome;
} else {
$crc = $crc >> 1;
}
}
$table[$i] = $crc;
$tablepos[$crc >> 24] = $i;
}

sub splitcrc {
$crc = shift;
$l = shift;
${$l.3} = $crc >> 24;
${$l.2} = ($crc >> 16) & 0xff;
${$l.1} = ($crc >> 8) & 0xff;
${$l.0} = $crc & 0xff;
}

@tablo = ("",0..9,a..z,A..Z);
$" = "";
$base = $#tablo+1;
$max = 3;

$ARGV[0] =~ /^(0x)([[:xdigit:]]+)$/ && ($crc32 = hex($2));

printf "crc32t= %snt 0xU%08xn", $crc32, $crc32;

$crc = $crc32 ^ 0xFFFFFFFF;

printf "crct= %snt 0xU%08xn", $crc, $crc;

&splitcrc($crc, f);

$count = 0;
while ($count < ($base ** $max)) {
$pref = "";
$M = $count;
until ($M < $base) {
$S = $M % $base;
$pref .= $tablo[$S];
$M = int $M / $base;
}
$pref .= $tablo[$M];
if($count % $base) {
$crc = 0xFFFFFFFF;
$len = length($pref);
for ($i = 0; $i < $len; $i++) {
$crc = ($crc >> 8) ^ $table[($crc ^ ord(substr($pref,$i,1))) & 0xff];
}

&splitcrc($crc, a);

$g3 = $tablepos[$f3];
&splitcrc($table[$g3], e);

$g2 = $tablepos[$f2 ^ $e2];
&splitcrc($table[$g2], d);

$g1 = $tablepos[$f1 ^ $e1 ^ $d2];
&splitcrc($table[$g1], c);

$g0 = $tablepos[$f0 ^ $e0 ^ $d1 ^ $c2];
&splitcrc($table[$g0], b);

$h0 = $g0 ^ $a0;
$h1 = $g1 ^ $b0 ^ $a1;
$h2 = $g2 ^ $c0 ^ $b1 ^ $a2;
$h3 = $g3 ^ $d0 ^ $c1 ^ $b2 ^ $a3;

$" = "";
if (($sub = chr($h0).chr($h1).chr($h2).chr($h3)) =~ /^[@tablo]{4}$/s) {
print "$pref$subn";
}
}
$count++;
}

`----[ crc32rev.pl ]

Les résultats sont obtenus à vitesse grand V comparés à un algo qui ferait
du brute force (c'est-à-dire calculer tous les checksums de toutes les
combinaisons de chaînes de caractères possibles et ne retenir que les
chaînes ayant le checksum voulu).

Sinon, on remarquera qu'à l'époque je débutais sous perl. J'avoue, j'ai
honte de mon code. :-P

ex: 123456 me donne: B8B072C2

Hmmm. Et comment avez-vous obtenu ce CRC32 ?

$ ./crc32.pl "123456"
crc = 4136447134
0xF68D2C9E
crc32 = 158520161
0x0972D361

Donc le même résultat que celui donné par Stéphane Chazelas.

y a t'il d'autres chaines de 6 caracteres qui me donnent ce resultat?

$ ./crc32rev.pl 0x0972D361
crc32 = 158520161
0x0972D361
crc = 4136447134
0xF68D2C9E
r1Oyht
123456 <- ;-)
5gLTXI
hgUwMF
Gg8OQT
fhJGqH
HhfNvC
eHA42X
xJq9PI
POTcgd
YYLmqA

Je pensais qu'il existatit un utilitaire en ligne de commande comme
md5sum qui me calculait les crc32, mais je n'ai pas trouve.

j'aurais fait tourner le programme avec l'ensemble des chaines de
6 caracteres et verifie avec mon resultat.

Ouch ! :-) Que de ressources il vous faudra alors. ;-)

--
Sébastien Monbrun aka TiChou

Nicolas George

10/05/2006 à 13:24

Sébastien Monbrun aka TiChou wrote in message
:

$ ./crc32rev.pl 0x0972D361
crc32 = 158520161
0x0972D361
crc = 4136447134
0xF68D2C9E
r1Oyht
123456 <- ;-)
5gLTXI
hgUwMF
Gg8OQT
fhJGqH
HhfNvC
eHA42X
xJq9PI
POTcgd
YYLmqA

Il en manque, et même beaucoup. Tu as bien arrêté avant la fin ?

Sylvain

10/05/2006 à 18:00

Nicolas George wrote on 10/05/2006 13:24:

Sébastien Monbrun aka TiChou wrote in message
:
$ ./crc32rev.pl 0x0972D361
crc32 = 158520161
0x0972D361
crc = 4136447134
0xF68D2C9E
r1Oyht
123456 <- ;-)
5gLTXI
hgUwMF
Gg8OQT
fhJGqH
HhfNvC
eHA42X
xJq9PI
POTcgd
YYLmqA

Il en manque, et même beaucoup.

dans ([0-9][A-Z][a-z])^6 ?

Tu as bien arrêté avant la fin ?

son code n'a pas de critère d'arrêt sur le nb de solutions ...

Sylvain.

Nicolas George

10/05/2006 à 20:02

Sylvain , dans le message <44620e1b$0$21284$, a
écrit :

Il en manque, et même beaucoup.
dans ([0-9][A-Z][a-z])^6 ?

Je n'avais pas vu de tel grep dans son code. Avec ces conditions, l'ordre de
grandeur est bon, effectivement.

son code n'a pas de critère d'arrêt sur le nb de solutions ...

Mais un Ctrl-C ou un copier-coller partiel peuvent faire la différence.

Sébastien Monbrun aka TiChou

10/05/2006 à 20:21

Dans le message <news:e3sihd$2d6a$,
*Nicolas George* tapota sur f.c.o.unix :

$ ./crc32rev.pl 0x0972D361
[...]

YYLmqA

Il en manque, et même beaucoup. Tu as bien arrêté avant la fin ?

Le script ne matche que les chaînes de caractères [a-zA-Z0-9] (variable
@tablo = ("",0..9,a..z,A..Z); dans le code du script).
De plus, je n'ai laissé que ce qui intéressé l'OP, à savoir les chaînes de 6
caractères uniquement.
Mais sinon, pour répondre à ta question, oui, il en manque beaucoup et j'ai
bien arrêté avant la fin. :-)

--
Sébastien Monbrun aka TiChou

John Deuf

10/05/2006 à 22:02

:

L'algorithme pour l'implementer en C

function crc(bit array bitString[1..len], int polynomial)

ca, oui, je serais preneur. A priori je connais mon array et mon
polynomial.
mais c'est peut etre vers un groupe C qu'il faut que j'aille alors?

http://www.boost.org/libs/crc/crc.html

Ce n'est pas du C, c'est du C++.
Cela dis, cette bibliotheque est livree avec la plupart des distributions
linux.

--
John Deuf

calcul de crc32

6 réponses

Veuillez sélectionner un problème