CRC32 Collision

Je suis en train d'essayer de trouver une collision entre deux messages qui vont conduire à la même CRC de hachage.
Étant donné que je suis en utilisant CRC32, est il possible que je peux raccourcir la liste des messages que j'ai essayer de faire une attaque par force brute?

Tous les liens vers des sites web avec des conseils sur ce qui vous seront utiles. J'ai déjà un algorithme brute force qui va le faire mais il suffit d'incrémenter entiers et voit si elle correspond à d'autres tables de hachage.

source d'informationauteur

  1. 19

    Il dépend entièrement de ce que vous entendez par "message". Si vous pouvez ajouter les quatre octets de charabia de l'un des messages. (I. E. quatre octets qui n'ont aucun sens dans le contexte du message.) Puis il devient trivial dans le vrai sens du mot.

    Penser en termes de bits se déplaçant à travers le CRC32 de l'état de la machine.

    CRC32 est basé sur une galois feedback shift register, chaque bit dans son état sera remplacé par l'induction de 32 bits à partir de données de la charge utile. Lors de l'induction de chaque bit, les positions indiquées par le polynôme sera exclusif par un ou binaire avec la séquence observée à partir de la fin du registre à Décalage. Cette séquence n'est pas influencée par les données d'entrée jusqu'à ce que le registre à décalage a été rempli.

    Comme un exemple, imaginons que nous ayons un registre à décalage rempli avec l'état initial 10101110, polynôme 10000011, et de remplir avec de l'inconnu bits, X.

    Polynomial *     **  |feedback (End of SR.)
State      10101110     0
State      X1010111     1
State      XX101000     0
State      XXX10100     0
State      XXXX1010     0
State      XXXXX101     1
State      XXXXXX01     1
State      XXXXXXX1     1
State      XXXXXXXX     0

    La rétroaction n'est pas en termes de X jusqu'à ce que le SR a été rempli!
    Ainsi, afin de générer un message avec une certaine somme de contrôle, vous prenez votre nouveau message, générer de la CDE et de travail, c'est à côté de 32 bits de rétroaction. Ce que vous pouvez faire en 32 étapes de la CRC de la fonction. Vous devez ensuite calculer l'effet de la rétroaction sur le contenu du registre à décalage.

    Un raccourci pour ce faire est de remplir votre message avec quatre zéro octets et puis regardez à la somme de contrôle. (Somme de contrôle est l'état de la SR à la fin, qui, si rembourré avec quatre zéro octets est l'influence de la rétroaction et le vide octets.)

    Exclusif OU qui influencent la valeur de la somme que vous voulez, remplacer les quatre octets de la remorque avec que le calcul de la valeur et de régénérer la somme de contrôle. Vous pouvez le faire avec n'importe quel programme qui génère CRC32, un éditeur hexadécimal, et un calculateur qui permet de gérer hex.

    Si vous voulez générer des deux messages à la fois le sens complet et ne contiennent pas de fuite d'ordures, les choses deviennent un peu plus difficiles. Identifier un certain nombre des articles que vous pouvez écrire alternative plausible, avec exactement la même longueur.

    À l'aide de la prose anglaise comme un exemple.
    "Je pense que cela peut fonctionner"
    et
    "Je crois que dans cette approche"
    Ont dans l'ensemble des significations semblables, et exactement de la même longueur.

    Identifier suffisamment d'exemples dans votre message est le problème (Sauf si vous voulez tricher avec les espaces!) CRC 32 est linéaire, à condition que les données sont correctes décalage dans le message. Donc CRC([messagea][rembourrage])^CRC([rembourrage][messageb])=CRC([messagea][messageb])
    Il ya quelques mises en garde avec word alignement, que vous aurez besoin pour faire face à, comme une astuce générale, vous souhaitez étendre les passages dans le "fixe" les parties du message. En règle générale, vous souhaitez avoir des solutions de rechange pour n*1.5 passages, où n est la taille de la CRC.

    Vous pouvez maintenant calculer le CRC que le squelette message a l'impression que chaque alternative passage aurait sur elle, et puis dresser un tableau comparant l'influence que chaque solution de rechange pour chaque passage aurait. Vous devez ensuite sélectionner les solutions de rechange susceptibles de modifier le squelette de la CRC pour correspondre à la CRC vous le souhaitez. Ce problème est en fait assez amusant à résoudre, d'Abord de trouver des solutions de rechange qui permet de modifier un peu, si ça doit changer pour votre CRC, sélectionnez la variante et le plier de l'influence dans la CRC, puis aller de nouveau. Cela devrait permettre de réduire l'espace des solutions que vous devez rechercher.

    C'est tout à fait une chose difficile à code, mais il serait de générer votre collisions dans un très court laps de temps.

  2. 14

    Court d'une faille avec mon calcul, la probabilité de pas avoir trouvé un choc après N essais est approchée dans le tableau suivant:

     N Probabilité 
------- ----------- 
De 50 000 à 74,7% 
De 77 000 50.1% 
Plus de 78 000 à 49,2% 
De 102 000 à 29,8% 
De 110 000 24.5% 
De 128 000 à 14,8% 
De 150 000 7.3% 
De 200 000 0.95%

    En d'autres termes, la probabilité d'avoir à calculer plus de 200 000 valeurs CRC32 avant trouver un duplicata est inférieure à 1%, ou, la probabilité de trouver un double avant de 102 000 tentatives est de 70,2%

    BTW, ce qui est remarquable, parce que la probabilité de trouver une collision sur, disons, la très de 200 000 ème tentative est toujours de l'ordre de 1/1000e de 1% ((4M - 200,0000) /4M), mais le doute d'avoir trouvé une collision avant les 200 000 ème tentative est une quasi certitude (enfin, au-dessus de 99% de toute façon). Cela montre l'intérêt de maintenir une base de données de Crc calculé jusqu'à présent.

    On peut certainement passer un peu de temps à l'étude de l'algorithme CRC32 et ses mathématiques sous-jacentes, dans une tentative de trouver messages plus susceptible de produire une CRC32 collisionsmais le nombre relativement faible de vraiment aléatoire tentatives nécessaires pour trouver au moins une collision avec quasi certitude, rend ce type de cryptanalyse approche à peine en vaut la chandelle. Par exemple, en supposant que l'on pourrait découvrir un moyen de sélectionner les messages qui sont 10 fois plus susceptibles d'entrer en collision les uns avec les autres, nous serions encore essayer dans l'ordre de 63 000 fois avant d'atteindre les 99% de chances d'avoir au moins une collision (mieux que 200 000 mais, il reste à peu près le même type d'application.)

    La seule chose que l'on peut envisager, dans ce domaine, est à éviter les messages en moins de 4 octets de longueur (j'ai lu quelque part que CRC32 est bijective dans ce message de l'espace), et à éviter les messages qui sont trop similaires (c'est à dire uniquement diffèrent par un ou deux caractères), puisque, après CRC32 but initial est de détecter (et éventuellement de s'auto-corriger) ces petites différences dans les messages.

    Par conséquent, il apparaît que la difficulté de la tâche n'est pas tellement de trouver des moyens de calcul CRC32s au grésillement de la vitesse (bien que nous ne devrions pas être trop lent avec ce soit), mais plutôt pour gérer rapidement interrogeable et articulée de la base de données de plus de 200.000 Messages (ou le message "la clé", plus ci-dessous) et de leurs associés CRC32 de valeur.

    Quelques idées à mettre en œuvre tout ce

    • Besoin que d'une simple bibliothèque ISAM, ou mieux un officiel interface SGBD comme MySql ou même SqlLite.
    • À l'aide d'un pseudo-générateur de nombres aléatoires (PRNG), afin de produire des messages, nous pouvons enregistrer le message clés (c'est à dire ce à quoi nous nourrir le PRNG à la production d'un message), plutôt que de stocker l'ensemble de message. Ce serait la base de données des inserts et des recherches plus efficaces, au risque de tort de la cueillette de l'PRNG, (ou plutôt le message générateur basé sur pm nombres aléatoires), c'est à dire celle qui permettrait de produire (au premier abord) les messages qui sont en quelque sorte moins susceptibles de CRC32-collision...
    • Il est probablement préférable de travailler en lots, à savoir la production de dire de 1 000 nouveaux Cdc et puis de vérifier, pour les collisions, et de les stocker, au lieu de faire toutes ces choses pour un CRC à la fois. Cela est particulièrement vrai si nous utilisons off-the-shelf SGBD
  3. 0

    Je suppose que tu veux dire "message" au lieu de "clé".

    Si vous êtes autorisé à choisir à la fois des "clés", puis par la force brute serait assez rapide tout de même, car le paradoxe d'anniversaire. De sélection aléatoire des messages, de calculer, de leur CRC, n'oubliez pas tous d'entre eux et de la CRC, et chaque nouvelle a de plus en plus de chances d'entrer en collision avec un existant comme ils s'accumulent. Franchement, je m'attends à cette approche pour être plus rapide sur un ordinateur moderne que de rechercher des approches connues pour faire CRC32 entrent en collision.

  4. 0

    Je crois que les CRC sont linéaires, donc si vous modifier (sur place, sans modification de la longueur) deux différentes parties de votre fichier, les différences dans le CRC devrait être xor ed ensemble.

    -- correction: il ne semble pas être tout à fait aussi simple que cela. Cependant, c'est encore le genre de tack je prendrais en essayant de construire une collision-vous besoin de suivre les mathématiques dans plus de détails que je suis enclin à faire ce soir...

  5. 0

    Juste hier il y avait cette question ici DONCun couple de pointeurs mentionné, il peut vous aider.

  6. 0

    Force Brute dont vous avez besoin sur sqrt(6N) longueur aléatoire des messages pour une table de hachage de taille N pour obtenir une probabilité de 95% pour la collision. E. g. CRC32 , N = 2^32 , vous avez besoin d'environ 160 000 messages

  7. 0

    usurper est exactement ce que fait. Il ne nécessite pas de force brute.