← 블로그

자신의 MD5 해시를 보여 주는 PNG: The Arma Of Efe hashquine

미리 만든 템플릿 없이 자신의 MD5 해시를 픽셀에 적은 PNG를 어떻게 만들었는지, MD5 충돌 열쇠, PNG 레이어, RTX 5070으로 efe23…23efe를 찾은 과정을 인터랙티브 설명으로 정리했습니다.

위 이미지는 평범한 로고가 아닙니다. 오른쪽 곡선 위에 위에서 아래로 efe235ae1b88c53e73d1c11515623efe라고 적혀 있는데, 이것은 파일 자신의 MD5 해시예요. 이미지를 내려받아 md5sum을 실행하면 같은 32자리를 볼 수 있어요.

이런 파일을 hashquine이라고 불러요. 인터넷에 떠도는 유명한 예시는 retr0id의 드래건 PNG인데, 대부분은 그 완성된 템플릿을 그대로 씁니다. 저희는 어떤 템플릿도 쓰지 않고, 직접 만든 로고(The Arma Of Efe)와 직접 만든 블로그 링크, 그리고 efe로 시작해서 efe로 끝나는 특별한 해시를 가지고 처음부터 만들었어요. 아래에서 단계별로, 시행착오를 거친 과정을 설명해 드릴게요.

자기 자신의 MD5를 보여 주는 Retr0id의 용 그림 PNG hashquine

David “Retr0id” Buchanan의 PNG hashquine, MD5 1337e2ef42b9bee8de06a4d223a51337. 이미지: Retr0id, corkami/collisions 제공.

해시란 무엇이고 왜 글자마다 바뀔까?

해시(hash)는 파일 내용에서 나오는 고정 길이의 지문입니다. MD5는 Ronald Rivest가 1991년에 설계한 해시 함수예요. 입력이 1바이트이든 50GB이든 출력은 언제나 128비트, 즉 0-9와 a-f 문자로 이루어진 32자리가 됩니다.

해시 함수의 기본 성질은 눈사태 효과입니다. 입력의 아주 작은 변화도 출력을 처음부터 끝까지 바꿔 놓아요. 아래에 무엇이든 입력해 보세요:

닭과 달걀의 문제

눈사태 효과 때문에, 자기 MD5를 자기 위에 얹은 그림은 언뜻 불가능해 보입니다:

  1. 그림을 그리고 MD5를 구합니다. 예를 들어 4a8c91e0….
  2. 이 코드를 그림 위에 적고 저장합니다.
  3. 픽셀이 바뀌었으므로 파일의 MD5는 이제 다른 값이 됩니다. 예를 들어 9f02d71a….
  4. 새 코드를 적으면 해시가 다시 바뀝니다.

이 순환을 끊으려면 MD5 내부를 들여다봐야 해요.

순환을 끊는 아이디어: MD5를 바꾸지 않는 열쇠

MD5는 파일을 한 번에 처리하지 않아요. 파일을 64바이트 블록으로 나눠 순서대로 처리하죠. 시작 상태(IV)가 첫 블록과 섞여 중간 상태(IHV)를 만들고, 이 중간 상태는 다음 블록과 섞이며 파일이 끝날 때까지 이어집니다. 마지막 중간 상태가 바로 32자리 MD5예요.

핵심은 이것입니다. 64바이트 경계에 맞춘 128바이트짜리 서로 다른 두 데이터 조각(A와 B)이 존재할 수 있고, 둘 다 같은 중간 상태로 귀결됩니다. 이를 같은 접두부 충돌이라고 하며, FastColl 같은 도구로 짧은 시간에 만들 수 있어요. 이 조각 뒤의 모든 블록은 같은 중간 상태를 보게 되므로:

  • A 조각을 넣으면 화면에 선 하나가 보이고, B를 넣으면 보이지 않아요.
  • 그러나 파일 끝의 MD5는 전혀 바뀌지 않습니다.

따라서 각 충돌 쌍은 MD5를 깨뜨리지 않고 열고 닫을 수 있는 열쇠입니다. 먼저 파일의 MD5를 계산하고, 그 해시를 정확히 그려 낼 수 있도록 열쇠를 맞춥니다. 해시는 변하지 않으므로 순환이 끊어져요.

곡선의 글자를 하나씩 그린 방법

파일의 32자는 로고의 호를 따라 위에서 아래로 놓여 있습니다. 각 글자는 일곱 세그먼트 숫자이고, 세그먼트마다 별도의 열쇠가 하나씩 글자를 그립니다. 열쇠는 모두 224개예요. 슬라이더로 해시가 곡선에 어떻게 놓이는지 따라가 볼 수 있어요:

미리 만든 템플릿을 쓰지 않았기 때문에 PNG의 네 가지 검증 계층을 동시에 통과해야 했어요:

  1. 64바이트 정렬: 각 열쇠는 파일 안에서 정확히 ofset % 64 == 0 경계에 놓여야 합니다. DEFLATE 압축 스트림에 길이가 0인 빈 블록을 넣어, 각 열쇠를 이 경계에 맞췄어요.
  2. PNG Sub와 Up 필터: 팔레트의 0..254 인덱스는 검은색, 255 인덱스만 흰색으로 지정했어요. 충돌 쌍의 두 조각은 몇 바이트의 최상위 비트에서 갈라집니다. Sub 필터가 적용된 줄에서는 이 차이가 뒤따르는 픽셀을 128만큼 밀어 가로선이 되고, Up 필터가 적용된 줄은 그 선을 아래로 옮겨요. 열쇠 뒤의 바이트들은 한 상태에서 선이 정확히 255(흰색), 다른 상태에서는 검은색이 되도록 골랐습니다.
  3. Zlib Adler-32 보정: 압축된 데이터는 풀릴 때 Adler-32 체크섬을 통과해야 합니다. 각 열쇠는 이 합을 수백 단위로 흔들어 놓기 때문에, 검은 줄에 160개의 보정 열쇠를 넣었어요. 합을 정확히 되돌리는 부분집합은 동적 계획법과 중간에서 만나기(meet-in-the-middle) 탐색으로 골랐습니다.
  4. IDAT CRC-32 검증: 모든 IDAT 청크의 끝에는 32비트 CRC-32가 있습니다. 압축 스트림 바로 뒤에 추가 블록 40개를 넣고, GF(2) 위의 선형 방정식 시스템을 가우스 소거법으로 풀어 CRC-32 값을 0x1807EFE0으로 고정했어요.

특수 해시: 글자마다 작업량이 16배가 됩니다

파일이 자기 MD5를 보여 주는 것만으로는 부족했어요. 해시가 efe로 시작해서 efe로 끝나기를 원했습니다. 이를 위해 파일 끝의 64바이트 nonce 블록을 바꿔 가며 수십억 개의 해시를 시도했어요.

각 자리는 16가지 값을 가질 수 있으므로, 고정하는 자리가 하나 늘어날 때마다 평균 시도 횟수는 16배가 됩니다. N개 자리를 고정하면 평균적으로 16^N번 시도가 필요해요. 24코어 CPU에서 단순한 C 루프는 초당 1억 7,700만 번의 MD5를 시도합니다. 같은 작업을 RTX 5070 노트북 그래픽카드에서 OpenCL로 돌리면 초당 35억 4천만 번으로, 약 20배 빨라집니다. efe23…23efe는 평균 1조 1,000억 번의 시도가 필요합니다. 우리 해시는 900억 번째 시도에서, 약 25초 만에 나왔어요.

슬라이더로 고정하는 자리 수를 바꿔 보세요. 실제로 찾아낸 결과는 표시된 점에 나타나 있습니다:

직접 확인해 보세요

이미지를 내려받아 터미널에서 실행해 보세요. Windows에서는 certutil -hashfile dosya.png MD5, macOS에서는 md5 dosya.png 명령을 쓸 수 있어요:

$ md5sum the-arma-of-efe-23-hashquine.png the-arma-of-efe-hashquine.png
efe235ae1b88c53e73d1c11515623efe  the-arma-of-efe-23-hashquine.png
efe8d2bee9dc7b5815f72581e5c17efe  the-arma-of-efe-hashquine.png

출력된 32자리는 곡선 위에서 위에서 아래로 적힌 코드와 정확히 같습니다.

이미지를 만드는 코드 전체는 GitHub에 있습니다: the-arma-of-owl/the-arma-of-efe-hashquine. 충돌 골격도 저장소에 들어 있으니, 직접 nonce 값을 바꿔 새로운 hashquine을 만들어 볼 수 있어요.

참고 자료: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗