이해 SHA-1 충돌 약점

Question

, 공격은 SHA-1 충돌을 찾고은 2^52 운영 개선되었습니다

http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/

는 내가 알고 싶은 것은의 의미입니다 공격 받고 있지 않은 시스템에서의 이러한 발견. 무작위 데이터를 해시하는 경우 충돌의 통계적 확률은 무엇입니까? 다른 말로하면, 최근 조사에 따르면 무차별 공격력이있는 원래의 공격이 원래 제안한 충돌을 발견 할 확률이 더 높다는 사실이 드러났습니까?

위와 같은 writeups는 무차별 대입을 통해 SHA-1 충돌을 얻으려면 2^80 작업이 필요하다고 말합니다. 대부분의 소식통은 2^80은 이론적 인 숫자라고 말합니다. 해시 함수가 실제로 다이제스트 공간에서도 완벽하게 분산되지 않았기 때문에 가정합니다.

기본 해시 배포에서 알려진 sha1 충돌 취약점이 있습니까? 또는 유도 된 수학적 공격의 결과 만 충돌 확률이 증가 했습니까?

결국 나는 그것이 확률의 게임이고, 그것들은 당신의 첫 번째와 두 번째 메시지가 충돌을 가져올 수있는 극도로 작은 변화라는 것을 깨닫습니다. 나는 또한 2^52조차도 정말 큰 숫자라는 것을 알았지 만, 여전히 공격 받고 있지 않은 시스템에 대한 함의를 이해하고자한다. 그래서 "그것에 대해 걱정하지 마십시오."라고 대답하지 마십시오.

Answer 1

귀하의 링크에서 발표 된 결과는 공격이며, 임의로 공격하는 것보다 더 큰 확률로 충돌을 생성하는주의 깊고 알고리즘 적으로 선택된 단계의 순서입니다. 해시 함수의 배포에서 약점이 아닙니다. 글쎄, 알았어, 그렇지만 2^52의 순서로 무작위 공격이 성공할 가능성이있는 것은 아니다.

아무도 해시 출력에서 ​​충돌을 생성하려고 시도하지 않으면이 결과는 영향을주지 않습니다.

Answer 2

잘하는 해시 함수는 3 가지 유형의 공격 (기사 상태와 마찬가지로)에 내성이 있습니다.

실용적인면에서 가장 중요한 저항은 두 번째 사전 이미지 저항입니다. 이것은 기본적으로 메시지 M1과 Hash (M1) = H1이 주어지면 Hash (M2) = H1과 같은 M2를 찾기가 어렵다는 것을 의미합니다.

누군가가 효율적으로 그 일을 할 수있는 방법을 찾으면 그럴 것입니다. 또한 메시지 M1이 고정되어 있기 때문에 프리 이미지 공격은 생일 패러독스의 영향을받지 않습니다.

이것은 사전 이미지 또는 두 번째 사전 이미지 공격이 아니며 단순히 충돌 검색 공격입니다. 질문에 대답하려면 무차별 대입 (brute force attack)은 충돌을 발견 할 가능성이 더 높지 않습니다. 이것이 의미하는 것은 연구자 방법과 결합 된 순진한 무차별 방식이 2^52 이후에 충돌을 발견하게된다는 것입니다. 표준 무차별 공격은 여전히 ​​2^80입니다.

Answer 3

중요한 질문은 "공격자가 m1 및 m2 메시지를 모두 수정할 수 있습니까?"입니다. 그렇다면 공격자는 해시 (m1) = 해시 (m2)와 같은 m1, m2를 찾아야합니다. 이것은 생일 공격이며 복잡성은 크게 줄어들고 --- 제곱근이됩니다. 해시 출력이 128 비트 (MD5) 인 경우 복잡성은 2^64이며 현재 컴퓨팅 성능으로는 충분히 도달 할 수 있습니다.

주어진 예는 판매자가 비서에게 "나는 그것을 1000 만 달러에 판매 할 것입니다"라는 메시지를 입력하라고합니다.계획 사무 총장은 "나는 그것을 1 천만 달러에 판매 할 것"이라는 문구와 x가 10보다 훨씬 적은 "백만 달러를 팔아서 판매 할 것"이라는 두 가지 문서를 만들고 공백을 추가하여 두 메시지를 수정하고 자본화 단어 등은 해시 (m1) = 해시 (m2)까지 x를 수정합니다. 이제 비서는 판매자에게 올바른 메시지 m1을 보여주고 자신의 개인 키를 사용하여 해시 h로 서명합니다. 비서는 메시지를 교환하고 (m2, h)를 발송합니다. 판매자 만 자신의 개인 키에 액세스 할 수 있으므로 거부 할 수 없으며 메시지에 서명하지 않았다고 말할 수 없습니다.

160 비트를 출력하는 SHA1의 경우 생일 공격으로 인해 복잡성이 2^80으로 줄어 듭니다. 이것은 30 년 이상 동안 안전해야합니다. 새로운 정부 규정 인 4G 3gpp 사양에 SHA256이 필요합니다.

그러나 유스 케이스에서 두 가지 메시지 (프리 이미지 또는 두 번째 프리 이미지 시나리오)를 수정할 수없는 경우 SHA1의 경우 복잡성은 2^160입니다. 무차별 공격이 발견되지 않는 한 영원히 안전해야합니다.