각각 1MB의 10 억 개의 고유 이미지가 있다고 가정 해 봅시다. 각 파일의 내용에 대한 SHA-256 해시를 계산합니다. 충돌 가능성은 다음에 따라 다릅니다.
- 파일 수
단일 파일의 크기
이 가능성이 0이라고 가정 할 때이 가능성을 무시하고 얼마나 멀리 갈 수 있습니까?
답변
일반적인 대답은 다음과 같습니다. 다음 초 내에 도적 소행성이 지구에서 충돌하여 문명을 아는 문명을 없애고 수십억 명의 사람들을 죽일 확률은 얼마입니까? 그보다 낮은 확률을 가진 불행한 사건은 실제로별로 중요하지 않다고 주장 할 수 있습니다.
출력 크기가 n 인 “완벽한”해시 함수가 있고 해시 할 p 메시지가있는 경우 (개별 메시지 길이는 중요하지 않음) 충돌 확률은 약 p 2 / 2 n + 1입니다 (이는 근사치입니다). “작은” p , 즉 2 n / 2 보다 실질적으로 작은 유효 . 예를 들어 SHA-256 ( n = 256 ) 및 10 억 개의 메시지 ( p = 10 9 )를 사용할 경우 확률은 약 4.3 * 10 -60 입니다.
대량 살인자 우주 암석은 평균적으로 약 3 천만 년마다 한 번씩 발생합니다. 약 다음 제에서 발생하는 이러한 이벤트의 확률이 리드 (10) -15 . 그건 45 개 SHA-256 충돌보다 더 가능성이 크기 순서. 간단히 말해 SHA-256 충돌이 무섭다면 우선 순위가 잘못되었습니다.
공격자가 해시 될 메시지를 선택하는 보안 설정에서 공격자는 10 억 개가 넘는 메시지를 사용할 수 있습니다. 그러나 공격자의 성공 확률은 여전히 거의 사라질 것입니다. 256 비트 출력으로 해시 함수를 사용하는 것이 요점입니다. 따라서 충돌 위험을 무시할 수 있습니다.
물론, 위의 모든 내용은 SHA-256이 “완벽한”해시 함수라고 가정하며, 이는 입증되지 않았습니다. 여전히 SHA-256은 상당히 강력 해 보입니다.
답변
충돌 가능성은 파일 크기에만 의존하지 않으며 파일 수에만 의존합니다.
이것은 생일 역설 의 예입니다 . Wikipedia 페이지는 충돌 가능성을 추정합니다. 숫자를 실행하면 지구상에서 생성 된 모든 하드 디스크가 SHA-256에 대해 0.01 %의 충돌 가능성을 얻기에 충분한 1MB 파일을 보유 할 수 없다는 것을 알 수 있습니다.
기본적으로 가능성을 무시할 수 있습니다.
답변
우선, 그것은 0이 아니라 0에 매우 가깝습니다 .
중요한 질문은 실제로 충돌이 발생하면 어떻게됩니까 ? 답이 “원자력 발전소가 폭발 할 것”이라면 충돌 가능성을 무시해서는 안됩니다. 대부분의 경우 결과는 그다지 심각하지 않으므로 충돌 가능성을 무시할 수 있습니다.
또한 소프트웨어 (또는 소프트웨어의 일부)가 여러 대의 컴퓨터 (현재는 거의 모든 곳에 포함 된 일부 소형 임베디드 마이크로 컴퓨터)에 배포되어 동시에 사용될 수 있다는 것을 잊지 마십시오. 이 경우 추정값에 가능한 최대 사본 수를 곱해야합니다.
