해시 충돌 확률을 어떻게 평가합니까?

StackOverflow https://stackoverflow.com/questions/862346

문제

검색 시스템을위한 백엔드 응용 프로그램을 개발하고 있습니다. 검색 시스템은 파일을 임시 디렉토리로 복사하고 임의 이름을 제공합니다. 그런 다음 임시 파일의 이름을 내 응용 프로그램에 전달합니다. 내 응용 프로그램은 제한된 기간 내에 각 파일을 처리해야합니다. 그렇지 않으면 차단됩니다. 이는 워치 독과 유사한 보안 조치입니다. 파일 처리는 오래 걸릴 수 있으므로이 시나리오를 처리 할 수있는 응용 프로그램을 설계해야합니다. 다음 번에 내 응용 프로그램이 종료되면 검색 시스템이 동일한 파일을 색인화하려는 경우 다른 임시 이름을 줄 수 있습니다.

명백한 솔루션은 검색 시스템과 백엔드 사이에 중간 계층을 제공하는 것입니다. 백엔드에 대한 요청을 대기하고 결과가 도착하기를 기다립니다. 중간 계층의 요청 시간이 문제가되지 않으면 백엔드가 계속 작동하고 중간 계층 만 다시 시작되며 검색 시스템에 의해 요청을 반복 할 때 백엔드에서 결과를 검색 할 수 있습니다.

문제는 파일을 식별하는 방법입니다. 그들의 이름은 무작위로 변합니다. 파일 내용을 해시하기 위해 MD5와 같은 해시 함수를 사용하려고합니다. 나는 잘 알고 있습니다 생일 역설 링크 된 기사의 추정을 사용하여 확률을 계산했습니다. 파일이 100,000 명 이하라고 가정하면 동일한 MD5 (128 비트)를 갖는 두 파일의 확률은 약 1,47x10입니다.-29.

그러한 충돌 확률을 관리해야합니까? 아니면 동일한 해시 값이 동일한 파일 내용을 의미한다고 가정해야합니까?

도움이 되었습니까?

해결책

동일한 해시는 누군가가 파일을 엉망으로 만들고 충돌을 주입하지 않는 한 동일한 파일을 의미합니다. (인터넷에서 물건을 다운로드하는 경우에 해당 될 수 있습니다)이 경우 SHA2 기반 기능에 사용됩니다.

우발적 인 MD5 충돌, 1,47x10은 없습니다-29 정말 정말 작은 숫자입니다.

큰 파일을 다시 해치는 문제를 극복하기 위해 3 단계의 신원 체계가있을 것입니다.

  1. 파일 크기 만
  2. 파일의 다른 위치에서 파일 크기 + 64k * 4 해시
  3. 완전한 해시

따라서 새로운 크기의 파일이 표시되면 분명히 중복이 없을 것입니다. 등등.

다른 팁

확률이 1/x이기 때문에 X 레코드가있을 때까지 발생하지 않는다는 의미는 아닙니다. 복권과 같아서 이길 가능성이 없지만 어떤 사람 저 밖에 ~ 할 것이다 이기다.

요즘 컴퓨터의 속도와 용량 (보안에 대해서는 이야기하지 않고 신뢰성)을 사용하면 MD5보다 더 크고 더 나은 해시 기능을 사용하지 않을 이유가 없습니다. SHA-1로 올라가면 밤에 더 잘자는 데 도움이 될 수 있지만, 조심하고 싶다면 SHA-265로 가서 다시는 생각하지 마십시오.

성능이 실제로 문제 인 경우 실제로 MD5보다 빠른 Blake2를 사용하지만 256 개 이상의 비트를 지원하여 성능이 동일하거나 더 나은 성능을 유지하면서 충돌 가능성을 줄입니다. 그러나 Blake2는 잘 결합되었지만 프로젝트에 새로운 종속성을 추가해야 할 것입니다.

나는 당신이해서는 안된다고 생각합니다.

그러나 두 개의 동일한 파일이 다르다 (MD5 기반이 아닌 실제 이름)에 대한 개념이 있다면해야합니다. 마찬가지로, 검색 시스템에서 두 문서는 정확히 동일한 내용을 가질 수 있지만 다른 장소에 있기 때문에 뚜렷합니다.

나는 충돌없이 직렬화 해야하는 분산 시스템에 UUID를 사용하면서 안전하게 잠을 잘 수 있도록 Monte Carlo 접근 방식을 생각해 냈습니다.

from random import randint
from math import log
from collections import Counter

def colltest(exp):
    uniques = []
    while True:
        r = randint(0,2**exp)
        if r in uniques:
            return log(len(uniques) + 1, 2)
        uniques.append(r)

for k,v in Counter([colltest(20) for i in xrange(1000)]):
    print k, "hash orders of magnitude events before collission:",v

다음과 같은 것을 인쇄 할 것입니다.

5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1

전에 공식을 들었습니다. 로그 (x/2) 키를 저장 해야하는 경우 키스 공간 e ** (x) 이상의 해싱 기능을 사용하십시오.

반복 실험에 따르면 1000 개의 로그 -20 공간 인구의 경우 때로는 로그 (x/4)까지 조기에 충돌이 발생합니다.

122 비트 인 UUID4의 경우, 여러 컴퓨터가 약 2 ** 31 항목을 가질 때까지 임의의 UUID를 선택하는 동안 안전하게 잠을 자고 있음을 의미합니다. 내가 생각하는 시스템의 최고 트랜잭션은 초당 약 10-20 개의 이벤트입니다. 평균 7이라고 가정합니다. 이는 극심한 편집증을 감안할 때 약 10 년의 작동 창을 제공합니다.

다음은 해시 크기 및 객체 수에 대한 충돌 확률을 추정 할 수있는 대화식 계산기입니다. http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top