Wie lange kann ich 6-Byte sha-1 Kollision mit diesem Code finden?

Question

Ich muss die Kollision von "letzten 6-Bytes von SHA-1 Digest" finden. Hier ist mein Python-Code (haben unabhängigen Teil gelöscht):

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 

Ich bin mit einem Thinkpad T400 Laptop (Intel Core 2 Duo Prozessor mit 2,8 GHz, 6 MB L2-Cache, 800 MHz). Wie lange kann es die Kollision finden? Wie auch immer, um den Code zu verbessern, um es schneller zu machen? (dieses Python)

Answer 1

6 Bytes Daten sind 2 (281474976710656) Möglichkeiten. Sie würden erwarten, eine Kollision in etwa der Hälfte dieser Schecks im Durchschnitt zu finden, also etwa 140 Billionen. Ich erhalte ca. 200000 SHA1/Hexdigest-Operationen pro Sekunde auf meinem Rechner (mit Python), so dass ich ungefähr 22 Jahre Laufzeit erwarten würde.

Wenn Sie nicht speziell die Kollision benötigen zwischen zwei aufeinanderfolgenden verdaut sein, dass Sie generieren, können Sie den Prozess stark beschleunigen, indem die Überprüfung gegen alle der zuvor erzeugten Digests (halten sie in einem Satz oder dict). (Schaut euch das "Geburtstagsparadoxon" an, um zu erfahren, wie sehr das hilft.) Das würde ziemlich schnell zu viel Speicher haben, aber wenn dein Laptop nicht das Minimum an RAM installiert hat, wirst du vermutlich eine Kollision finden . Ich rechne mit einer Schätzung von ein oder zwei Minuten Laufzeit, wobei ich von 1-2 GB verfügbarem RAM ausginge.