sha-1 충돌 약점 이해

Question

다양한 소스에 따르면 sha-1 충돌을 찾는 공격은 2^52 작업으로 개선되었습니다.

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

제가 알고 싶은 것은 이러한 발견이 공격을 받지 않는 시스템에 미치는 영향입니다.즉, 무작위 데이터를 해시하면 충돌의 통계적 확률은 얼마나 됩니까?다르게 말하면, 최근 연구에서는 무차별 생일 공격이 원래 제안했던 충돌을 발견할 가능성이 더 높다는 것을 나타냅니까?

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

그렇다면 기본 해시 분포에 있어 발표된 sha1 충돌 약점이 있습니까?아니면 증가된 충돌 확률은 유도된 수학적 공격의 결과일 뿐입니까?

나는 그것이 결국 확률 게임일 뿐이라는 것과 첫 번째 메시지와 두 번째 메시지가 충돌을 초래한다는 것은 극히 작은 변화라는 것을 깨달았습니다.또한 2^52라는 숫자도 정말 큰 숫자라는 것을 알고 있지만 여전히 공격을 받지 않는 시스템에 대한 의미를 이해하고 싶습니다.그러니 "걱정하지 마세요"라고 대답하지 마세요.

Answer 1

귀하의 링크에 발표된 결과는 공격, 무작위 공격보다 더 큰 확률로 충돌을 생성하는 신중하고 알고리즘적으로 선택된 일련의 단계입니다.해시 함수 분포의 약점은 아닙니다.글쎄요, 그렇습니다. 하지만 2^52 정도의 무작위 공격이 성공할 가능성이 있는 종류는 아닙니다.

해시 출력에서 ​​충돌을 생성하려는 사람이 없다면 이 결과는 영향을 미치지 않습니다.

Answer 2

좋은 해시 함수는 3가지 다른 유형의 공격에 저항합니다(기사에 나와 있듯이).

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

누군가가 그것을 효율적으로 수행하는 방법을 찾았다면 그것은 나쁠 것입니다.게다가 메시지 M1이 우리에게 고정되어 있기 때문에 사전 이미지 공격은 생일 역설에 취약하지 않습니다.

이는 사전 이미지 또는 두 번째 사전 이미지 공격이 아니며 단지 충돌 탐지 공격입니다.귀하의 질문에 대답하자면, 아니요, 무차별 대입 공격은 충돌을 발견할 가능성이 더 높지 않습니다.이것이 의미하는 바는 연구원의 방법과 결합된 순진한 무차별 대입 방법이 2^52 이후에 충돌을 발견한다는 것입니다.표준 무차별 공격에는 여전히 2^80이 소요됩니다.

Answer 3

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

일반적인 예는 판매자가 비서에게 "나는 그것을 천만 달러에 팔겠습니다"라는 메시지를 입력하도록 요청하는 것입니다.교활한 비서는 "1천만 달러에 팔겠습니다"라는 문서와 "x백만 달러에 팔겠습니다"라는 문서 2개를 생성합니다. 여기서 x는 10보다 훨씬 작으며 공백을 추가하고 대문자로 두 메시지를 모두 수정합니다. 단어 등은 해시(m1) = 해시(m2)가 될 때까지 x를 수정합니다.이제 비서는 판매자에게 올바른 메시지 m1을 보여주고 판매자는 자신의 개인 키를 사용하여 서명하여 해시 h를 얻습니다.비서는 메시지를 전환하여 (m2, h)를 보냅니다.판매자만이 자신의 개인 키에 접근할 수 있으므로 판매자는 자신이 메시지에 서명하지 않았다고 부인하거나 말할 수 없습니다.

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

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