이 코드를 사용하여 6 바이트 sha-1 충돌을 얼마나 오래 찾을 수 있습니까?

Question

"SHA-1 다이제스트의 마지막 6 바이트"의 충돌을 찾아야합니다.

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 

나는 씽크 패드 T400 노트북 (인텔 코어 2 듀오 2.8GHz의, 6메가바이트 L2 캐시, 800 MHz의)를 사용하고 있습니다 : 여기에 (관련이없는 부분을 삭제 한) 내 파이썬 코드입니다. 얼마나 오랫동안 충돌을 찾을 수 있습니까? 어쨌든 코드를 개선하여 더 빨리 만들 수 있습니까? (이 파이썬)

Answer 1

데이터의 6 바이트는 2 (281474976710656) 가능성입니다. 평균적으로 수표의 반 정도가 충돌 할 것으로 예상되므로 약 140 조원입니다. 내 컴퓨터에서 (Python을 사용하여) 초당 약 200000 건의 SHA1/hexdigest 연산을 얻었으므로 22 년 정도의 런타임을 기대합니다. 특별히 당신이 생성하는 두 개의 연속 다이제스트 사이에 충돌이 필요하지 않은 경우

, 당신은 크게 이전에 생성 된 다이제스트 (세트 또는 딕셔너리에 보관의 모든에 대해 확인하여 처리 속도를 높일 수 있습니다). 이것이 얼마나 도움이되는지에 대한 자세한 내용은 "생일 패러독스"를 참조하십시오.) 메모리가 상당히 빨리 소모되지만 랩톱에 절대 최소 RAM이 설치되어 있지 않으면 충돌이 발생할 가능성이 높습니다. . 1 ~ 2GB의 사용 가능한 RAM을 가정 할 때 런타임의 1 ~ 2 분이 소요될 것으로 예상됩니다.