Fichier contenant sa propre somme de contrôle

Question

Est-il possible de créer un fichier qui contiendra sa propre somme de contrôle (MD5, SHA1, etc.) ? Et pour contrarier les plaisantins, je parle de checksum en clair, pas de la fonction qui le calcule.

Answer 1

J'ai créé une table précalculée de 96 Mo pour crc32, puis j'ai exécuté bruteforce pendant moins de 2 minutes et j'ai obtenu cette merveille :

The CRC32 of this string is 4A1C449B

Notez qu'il ne doit y avoir aucun caractère (fin de ligne, etc.) après la phrase.

Vous pouvez le consulter ici : http://www.crc-online.com.ar/index.php?d=The+CRC32+de+cette+chaîne+est+4A1C449B&en=Calcular+CRC32

Celui-ci est également amusant :

I killed 56e9dee4 cows and all I got was...

Answer 2

Oui, c'est possible, et c'est courant avec les sommes de contrôle simples. Obtenir qu'un fichier inclue son propre md5sum serait assez difficile.

Dans le cas le plus simple, créez une valeur de somme de contrôle qui fera en sorte que le module additionné soit égal à zéro. La fonction de somme de contrôle devient alors quelque chose comme

(n1 + n2 ... + CRC) % 256 == 0

Si la somme de contrôle devient alors une partie du fichier, et est vérifiée elle-même. Un exemple très courant de ceci est le Algorithme de Luhn utilisé dans les numéros de cartes de crédit. Le dernier chiffre est un chiffre de contrôle, et fait lui-même partie du numéro à 16 chiffres.

Answer 3

"Je souhaite que mon crc32 soit 802892ef..."

J'ai pensé que c'était intéressant, alors aujourd'hui j'ai codé un petit programme java pour trouver les collisions. J'ai pensé le laisser ici au cas où quelqu'un le trouverait utile :

import java.util.zip.CRC32;

public class Crc32_recurse2 {

    public static void main(String[] args) throws InterruptedException {

        long endval = Long.parseLong("ffffffff", 16);

        long startval = 0L;
//      startval = Long.parseLong("802892ef",16); //uncomment to save yourself some time

        float percent = 0;
        long time = System.currentTimeMillis();
        long updates = 10000000L; // how often to print some status info

        for (long i=startval;i<endval;i++) {

            String testval = Long.toHexString(i);

            String cmpval = getCRC("I wish my crc32 was " + testval + "...");
            if (testval.equals(cmpval)) {
                System.out.println("Match found!!! Message is:");
                System.out.println("I wish my crc32 was " + testval + "...");
                System.out.println("crc32 of message is " + testval);
                System.exit(0);
            }

            if (i%updates==0) {
                if (i==0) {
                    continue; // kludge to avoid divide by zero at the start
                }
                long timetaken = System.currentTimeMillis() - time;
                long speed = updates/timetaken*1000;
                percent =  (i*100.0f)/endval;
                long timeleft = (endval-i)/speed; // in seconds
                System.out.println(percent+"% through - "+ "done "+i/1000000+"M so far"
                        + " - " + speed+" tested per second - "+timeleft+
                        "s till the last value.");
                time = System.currentTimeMillis();
            }       
        }       
    }

    public static String getCRC(String input) {
        CRC32 crc = new CRC32();
        crc.update(input.getBytes());
        return Long.toHexString(crc.getValue());
    }

}

Le résultat :

49.825756% through - done 2140M so far - 1731000 tested per second - 1244s till the last value.
50.05859% through - done 2150M so far - 1770000 tested per second - 1211s till the last value.
Match found!!! Message is:
I wish my crc32 was 802892ef...
crc32 of message is 802892ef

Notez que les points à la fin du message font en fait partie du message.

Sur mon i5-2500, il fallait environ 40 minutes pour rechercher tout l'espace crc32 de 00000000 à ffffffff, en effectuant environ 1,8 million de tests par seconde. Un seul cœur était utilisé au maximum.

Je suis assez novice en Java, donc tout commentaire constructif sur mon code serait apprécié.

"Mon crc32 était c8cb204, et tout ce que j'ai eu, c'est ce minable T-shirt !"

Answer 4

C'est certainement possible. Mais l'une des utilisations des sommes de contrôle est de détecter la falsification d'un fichier - comment savoir si un fichier a été modifié, si le modificateur peut également remplacer la somme de contrôle ?

Answer 5

Bien sûr, vous pourriez concaténer le condensé du fichier lui-même à la fin du fichier. Pour le vérifier, il faudrait calculer le condensé de toutes les parties sauf la dernière, puis le comparer à la valeur de la dernière partie. Bien sûr, sans une certaine forme de cryptage, n'importe qui peut recalculer le condensé et le remplacer.

modifier

Je dois ajouter que ce n'est pas si inhabituel. Une technique consiste à concaténer un CRC-32 de sorte que le CRC-32 de l'ensemble du fichier (y compris ce condensé) soit égal à zéro. Mais cela ne fonctionne pas avec les condensés basés sur des hachages cryptographiques.