두 메시지가 동일한 MD5 다이제스트와 동일한 SHA1 다이제스트를 가질 가능성은 무엇입니까?

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

문제

두 가지 다른 메시지가 주어지면 A와 B (아마도 20-80 문자의 텍스트, 크기가 중요한 경우) A의 MD5 다이제스트가 B의 MD5 다이제스트와 동일 할 확률은 얼마입니까? 그리고 A의 SHA1 다이제스트는 B의 SHA1 다이제스트와 동일합니까? 그건:

(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))

악의적 인 의도는 없다고 가정합니다. 즉, 메시지가 충돌을 찾기위한 목표로 선택되지 않았다고 가정합니다. 나는 단지 자연스럽게 일어나는 확률을 알고 싶습니다.

나는 기회가 "천문학적으로 낮다"고 생각하지만, 이것을 어떻게 확인하는지 잘 모르겠습니다.

자세한 정보 : 가능한 메시지 풀의 크기는 제한되지만 크다 (수억). 생일 역설 상황은 내가 걱정하는 것입니다.

도움이 되었습니까?

해결책

임의의 문자열에 대한 MD5 및 SHA-1 해시의 범위에 균일 한 스프레드를 가정하고, 우리가 두 줄에 대해서만 이야기하고 줄에 대해 이야기하지 않는다고 가정합니다 (따라서 생일-파라 독을 피합니다. -유형 복잡성) :

MD5 해시는 폭이 128 비트이고 SHA-1은 160입니다. 위의 가정에서는 두 개의 문자열 A와 B가 두 해시가 충돌하면 충돌 가능성이 있습니다. 그래서 

P(both collide) = P(MD5 collides) * P(SHA-1 collides)

그리고 

P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)

그래서

P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87

다시 말하지만, 끈 풀이 있고 수영장과의 충돌 확률을 결정하려고한다면, 당신은 생일 역설 그리고 여기에서 계산 한이 확률은 적용되지 않습니다. 그것과 해시는 그들만큼 균일하지 않습니다. 실제로는 충돌 속도가 훨씬 높지만 여전히 작을 것입니다.

편집하다

생일 역설 상황을 다루고 있기 때문에 생일 역설에 대한 해결책과 동일한 논리를 적용하십시오. 하나의 해시 기능의 관점에서 볼 때 다음을 살펴 보겠습니다.

N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)

2^29 (약 5 억 5 천만)와 같은 수많은 해시가 있다고 가정 해 봅시다.

P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)

요컨대, 나는이 숫자를 계산하는 것에 대해 생각하고 싶지도 않습니다. 나는 당신이 그것을 어떻게 추정 할 수 있는지 잘 모르겠습니다. 최소한 죽지 않고 거대한 계승을 처리 할 수있는 임의의 차가 계산기가 필요합니다.

확률은 거의 0에서 시작하는 곡선을 따릅니다. N = 1 or 2, 그리고 그것은 언제 1에 도달 할 것입니다 N >= 2^288, 생일 역설에 대한 위키 백과 페이지의 것과 비슷합니다.

생일 역설이 도달합니다 P = .5 언제 N = 23. 다시 말해, 충돌 확률은 S의 6% 일 때 충돌 확률이 50%입니다. 그 규모가 확신하지 못하는 경우 (그렇지 않은지 확실하지 않음). 2^288 해시의 6%. 2^288의 6%는 약 2^284입니다. N (수억)의 가치는 그 근처에 없습니다. 그것은 당신의 S에 비해 실제로 무의미합니다. 그래서 나는 당신이 걱정할 것이 없다고 생각합니다. 충돌은 그리 가능성이 없습니다.

다른 팁

Welbog의 게시물에 대한 부록 :

대형 팩토리 노트의 비율은 스털링의 근사:

N! ≈ sqrt (2πn) * (N/E)N

그래서 (s!)/(s^n * (s -n)!) ≈ sqrt (2πs)/sqrt (2π (sn)) * (s/e)에스/(SN)/e)Sn/에스N

= sqrt (s/(sn)) * (s/(sn))Sn * e-N

= SQRT (1 + α) * (1 + α)Sn * e-N 여기서 α = n/(sn)는 작습니다.

근사치 (1+a/n)NX ≈ e도끼 n → ∞로 보유합니다 (또는 적어도 매우 커집니다)

** 이것은 (1+ (n/(sn))을 의미합니다.Sn ≈ eN Sn >> N.

그래서 나는 그것을 기대할 것입니다

(s!)/(s^n * (s -n)!) ≈ sqrt (1 + n/(sn)) * eN * e-N = sqrt (1 + n/(sn)) sn >> n ....

이것을 제외하고는 1보다 큽니다 ... 근사치 중 하나는 충분하지 않습니다. :피

(** 경고 : N/S는 작아야합니다 : N = 22, S = 365이기는 경우 2 인 숫자 2)

메시지 크기가 제한되지 않은 경우, 가능성은 무한한 수의 가능한 메시지와 유한 한 수의 해시가 있으므로 100% 비대칭 적으로 접근합니다.

(참고 : 질문을 편집하면 지금이 문제가 덜 관련이 있습니다)

일반적으로 N 요소를 무작위로 선택하면 충돌 확률보다 예상 충돌 수를 계산하는 것이 더 쉽습니다. 예상 충돌 횟수는 충돌 확률보다 작을 수 없기 때문에 적절한 상한으로 자주 사용할 수 있습니다.

그것을 가정합니다 피 무작위로 선택된 두 개의 요소가 충돌 할 확률입니다. 무작위 요소를 선택하면 N*(N-1)/2 쌍의 요소가 있으므로 예상 충돌 횟수는 다음과 같습니다.

P * N * (N-1)/2.

예를 들어, MD5와 SHA1의 충돌 가능성이 p = 2라고 가정하면-288 그런 다음 무작위로 선택 한 후에도 2100 우리는 여전히 약 2 만 기대합니다-89 충돌.

또 다른 예 : 우리가 2를 선택하면30 임의의 요소 및 MD5 만 계산합니다. 두 MD5 해시 사이의 충돌이 p = 2라고 가정합니다.-128 이것은 예상 수의 2를 제공합니다-59 충돌 횟수. 따라서 MD5 해시가 두 개의 입력에 대해 충돌 할 확률조차도 이미 매우 작습니다.

선택한 답변은 잘못된 확률을 사용하기 때문에 올바르지 않습니다. 나는 오늘 이것을 조사하는 데 많은 부분을 보냈다 (당신은 그 답에 대한 의견에서 내 생각 과정을 볼 수있다), 실제 답변은 다음 (당신이 말하는 메시지보다 약간 더 큰 메시지의 생일 공격에 대한)라고 믿는다. :

2^-61 * 2^-18 = 2^79에서 한 번의 충돌.

그리고 그것은 이러한 확률을 곱해도 괜찮다는 것입니다 (나는 그것을 확신하지 못합니다).

이것은 오늘날 슈퍼 컴퓨터에 의해 가능하다 (2 개월 미만이며 매년 삭제).

이것은 충분히 큰 메시지 풀을 기반으로합니다 (생일 역설을 의미있게 만들기 위해). 이것은 또한 당신이 걱정했다고 말한 시나리오이기도합니다.

이제 다른 상황은 한 쌍의 해시 (SHA1 및 MD5)에 대한 충돌을 찾는 것입니다. 특정한 메시지. 이것은 당신을 Bday 역설 영토에서 벗어나게하고 더 어려운 순서입니다. 그것이 2^(-61*2)*2^(-18*2)인지 확실하지 않습니다. 누구든지 그것이 무엇인지 알고 있다면,이 답변에 의견을 게시하십시오 (매우 감사 할 것입니다!).

이제 당신은 묻습니다.

두 가지 다른 메시지가 주어지면 A와 B (크기가 중요한 경우 20-80 문자의 문자)

예, 크기는 중요합니다. 2^-18 그림에 대한 링크를 클릭하면 값이 두 개의 입력 블록에 대한 것임을 알 수 있습니다. MD5에서 입력 블록은 512 바이트입니다. 20-80 문자의 문자는 너무 작고 단일 블록 값은 2^41입니다.

따라서 해당 양의 데이터에 대해 2^-61 (생각합니다) * 2^-41 = 2^-102를 얻습니다.

그래서 그 크기에 대해 안전 해 보인다 (링크에는 SHA256 : 46626.93 Th/sec의 두 번의 현재 비트 코인 해시 레이트의 그림이 포함되어 있습니다).

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