corkami/collisions해시 충돌 및 악용
Ange Albertini와 Marc Stevens 작성.
Q: MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 중 임의의 해시를 갖도록 파일을 만들거나 다른 파일과 동일한 해시를 갖도록 만드는 것이 가능한가요?
A: 아니요.
Q: 동일한 해시를 가진 서로 다른 2개의 파일을 만들 수 있나요?
A: MD5는 일반 컴퓨터에서 몇 초면 됩니다. SHA1은 가능하지만 일반 사용자에게는 실용적이지 않습니다 (복잡도: 2^61.2, 비용: $11k).
Q: 데이터를 추가하여 서로 다른 2개의 파일이 동일한 해시를 갖도록 만들 수 있나요?
A: MD5는 일반 컴퓨터에서 몇 시간이면 됩니다. SHA1은 가능하지만 일반 사용자에게는 실용적이지 않습니다 (복잡도: 2^63.4, 비용: $45K)
Q: 두 파일은 여전히 유효한가요?
A: 일반적으로 그렇습니다. 대부분의 파일 형식은 추가된 데이터를 허용하기 때문입니다. 반면 파일 서명은 손상될 가능성이 높습니다.
Q: 임의의 내용을 가진 서로 다른 2개의 파일이 동일한 해시를 갖도록 만들 수 있나요?
A: 예, 특수한 파일 구조를 활용하면 즉시 가능합니다:
Q: 어떤 형식에 대해 즉시 MD5 충돌 파일 쌍을 얻을 수 있나요?
A: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. 해당 스크립트를 실행하기만 하면 됩니다.
Q: SHA1은 어떤가요?
A: SHA1의 경우 PDF 안의 JPG에 대한 충돌이 계산되어 구현되어 있습니다.
Q: MD5에서는 지원되는 형식(JPG, PNG 등)을 SHA1로도 할 수 있나요?
A: SHA1에서도 지원될 가능성이 높지만, 해당 충돌은 아직 계산되지 않았습니다.
Q: 유사하지만(다른) 내용에 대해서는 계산이 더 빠른가요?
A: 아니요. 아주 작은 차이라도 전체 계산이 필요합니다.
Q: 어떤 형식에는 그러한 지름길이 없나요?
A: ELF, Mach-O, Java Class, TAR, ZIP (그 외 다수...)
Q: 이러한 형식에서도 (몇 시간이 걸리는) 고전적인 충돌이 여전히 가능한가요?
A: 예, 추가된 데이터가 어느 정도 허용되는 한 가능합니다 (즉, ZIP이나 Class는 아마 안 됩니다).
Q: 충돌 예제를 제공하나요?
A: 예.
목표는 기존 공격들을 광범위하게 탐구하고, 그 과정에서 MD5가 얼마나 취약한지 보여주는 것입니다 (모든 JPG, PNG, PDF, MP4, PE...의 즉시 충돌) - 또한 일반적인 파일 형식을 자세히 살펴보아 현재 또는 미래의 공격으로 어떻게 악용될 수 있는지 결정하는 것입니다.
실제로 동일한 파일 형식 트릭은 여러 해시에 사용될 수 있습니다 (동일한 JPG 트릭은 MD5, 악성 SHA-1 및 SHA1에도 사용되었습니다), 충돌이 동일한 바이트 패턴을 따르는 한 말이죠.
이 문서는 새로운 공격에 관한 것이 아니라 (가장 최근의 공격은 2012년에 문서화되었습니다), 기존 공격의 새로운 악용 형태에 관한 것입니다.
알려진 공격들의 현재 상태:
파일이 다른 파일의 해시나 주어진 해시를 갖도록 만들기: 불가능
동일한 MD5를 가진 서로 다른 두 파일 만들기: 즉시
임의의 두 파일이 동일한 MD5를 갖도록 만들기: 몇 시간 (72시간.core)
특정 파일 형식(PNG, JPG, PE...)의 임의의 두 파일이 동일한 MD5를 갖도록 만들기: 즉시
동일한 SHA1을 가진 서로 다른 두 파일 만들기: 6500년.core
import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'
# 공격
MD5와 SHA1은 64바이트 블록으로 작동합니다.
두 콘텐츠 A와 B가 동일한 해시를 가지면, 둘 다에 동일한 콘텐츠 C를 추가해도 동일한 해시가 유지됩니다.``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)
충돌은 파일에서 앞부분에 무엇이 있었는지에 따라 블록 경계에 계산된 충돌 블록 여러 개를 삽입하여 작동합니다. 이 충돌 블록들은 각 공격에 대해 특정 패턴을 따르는 약간의 차이를 제외하고는 매우 무작위적으로 보이며, 이 블록들 이후에는 해시가 동일한 값이 되면서도 블록들 사이에 미세한 차이를 만들어 냅니다.
이러한 차이점들은 특정 속성을 가진 유효한 파일을 제작하는 데 악용됩니다.
파일 형식도 위에서 아래로(top-down) 작동하며, 대부분 바이트 단위 청크로 구성됩니다.
일부 '주석(comment)' 청크는 파일 청크를 블록 경계에 정렬하거나, 충돌 블록의 차이점에 특정 구조를 정렬하거나, 파일 파서로부터 나머지 충돌 블록의 무작위성을 숨기거나, 파서가 다른 내용을 보도록 유효한 콘텐츠를 숨기는 데 삽입될 수 있습니다.
이러한 '주석' 청크는 공식적인 실제 주석이 아닌 경우가 많습니다. 파서가 무시하는 데이터 컨테이너로 사용될 뿐입니다 (예: 소문자로 시작하는 ID를 가진 PNG 청크는 필수(critical)가 아닌 보조(ancillary) 청크입니다).
대부분의 경우, 충돌 블록의 차이는 주석 청크의 길이를 수정하는 데 사용되며,
이 길이는 일반적으로 이 청크의 데이터 바로 앞에 선언됩니다.
이 청크의 더 짧은 버전과 더 긴 버전 사이의 간격에는
파일 콘텐츠 A를 건너뛰기 위한 또 다른 주석 청크가 선언됩니다.
이 파일 콘텐츠 A 다음에 파일 콘텐츠 B를 추가로 붙이기만 하면 됩니다.
파일 형식은 일반적으로 파서가 그 뒤에서 멈추게 만드는 종결자(terminator)를 정의하므로,
A는 파싱을 종료하고, 추가된 콘텐츠 B는 무시됩니다.
따라서 일반적으로 최소 두 개의 주석이 필요하며, 종종 세 개가 필요합니다:
이러한 파일 형식의 공통 속성 덕분에 이러한 기법이 가능합니다. 이들은 일반적으로 취약점으로 간주되지 않지만, 탐지하거나 정규화하여 제거할 수 있습니다: