Combien de temps puis-je trouver la collision 6-bytes sha-1 en utilisant ce code?

Question

J'ai besoin de trouver la collision des "derniers 6 octets du condensé SHA-1". Voici mon code Python (ont supprimé une partie non apparentée):

import hashlib 
import os 
import binascii 

start_string = os.urandom(20) 
x0 = binascii.hexlify(start_string) 

hash_value = hashlib.sha1(x0) 
x1 = hash_value.hexdigest() 

while x0[28:]!=x1[28:]: 
    x0 = x1 
    x1_hash = hashlib.sha1(x0) 
    x1 = x1_hash.hexdigest() 
else: 
    print x0 
    print x1 

J'utilise un ordinateur portable Thinkpad T400 (Intel Core 2 Duo cadencé à 2,8 GHz, 6 Mo de cache L2, 800 MHz). Combien de temps peut-il trouver la collision? De toute façon pour améliorer le code pour le rendre plus rapide? (ce Python)

Answer 1

6 octets de données est 2 (281474976710656) possibilités. Vous vous attendriez à trouver une collision dans environ la moitié de ces contrôles en moyenne, soit environ 140 milliards de dollars. Je reçois environ 200 000 opérations SHA1/hexdigest par seconde sur ma machine (en utilisant Python), donc je m'attends à environ 22 années d'exécution. Si vous ne demandez pas spécifiquement que la collision se produise entre deux condensés successifs que vous générez, vous pouvez accélérer considérablement le processus en vérifiant par tous les condensés des digests précédemment générés (conservez-les dans un set ou dict). (Recherchez le "paradoxe d'anniversaire" pour plus de détails sur combien cela peut vous aider.) Cette mémoire manquerait de mémoire assez rapidement, mais à moins que votre ordinateur portable ne dispose d'un minimum de RAM, il est probable que vous rencontriez une collision . Je viens avec une estimation d'une minute ou deux d'exécution, en supposant 1-2 Go de RAM disponible.