깨진 해시가 아직 코드에 남아 있는 이유

MD5를 쓰지 말라는 말은 오래됐습니다. 그런데 도구 목록에는 MD2·MD4·MD5·SHA-1이 다 있습니다. 각각 무엇이 깨졌고 왜 아직 필요한지 봅니다.

충돌이 실제로 어떤 모습인가

2009년에 공개된 MD5 충돌 쌍을 돌려 봤습니다. 서로 다른 64바이트 두 개입니다.

A 와 B 가 같은 바이트인가 : false
다른 바이트 수            : 2 개
MD5(A) = 008ee33a9d58b51cfeb425b0959121c9
MD5(B) = 008ee33a9d58b51cfeb425b0959121c9
같은가 : true

64바이트 중 2바이트만 다른데 MD5가 같습니다. 같은 입력에 SHA-256을 걸면 갈립니다.

SHA-256(A) = 54bcb9a4fda31e4f254303e3959acd5e …
SHA-256(B) = 90774a6455a2bdb7d106e533923ecbef …

충돌은 뒤로 전파된다

여기서 중요한 성질이 하나 있습니다.

MD5(A + 꼬리) = 9e8689418e1f43fe25d24467d3382b14
MD5(B + 꼬리) = 9e8689418e1f43fe25d24467d3382b14

충돌하는 두 블록 뒤에 같은 내용을 붙이면 충돌이 그대로 유지됩니다. 머클-담고르 구조에서 두 입력이 같은 내부 상태에 도달했기 때문에, 그 이후는 완전히 같은 계산입니다.

그래서 실제 공격은 이렇게 만들어집니다. 파일 앞부분에 충돌 블록 두 벌을 심어 두고, 뒤에 보여 주고 싶은 내용을 붙입니다. 계약서 두 벌이나 실행 파일 두 개가 같은 MD5를 갖게 됩니다. "해시가 같으니 같은 파일"이라는 검사가 여기서 무너집니다.

무엇이 아직 안 깨졌나

충돌 저항성이 깨진 것과 원상 복원이 되는 것은 다릅니다.

성질	뜻	MD5
원상 저항성	해시로부터 원문을 찾기	아직 깨지지 않음
제2 원상 저항성	주어진 파일과 같은 해시의 다른 파일 찾기	아직 깨지지 않음
충돌 저항성	같은 해시를 갖는 두 파일을 내가 만들기	깨짐

깨진 것은 세 번째입니다. 공격자가 두 파일을 모두 만들 수 있을 때 위험합니다. 이미 존재하는 남의 파일에 맞춰 다른 파일을 만드는 것은 아직 안 됩니다.

그래서 다운로드 무결성 검사 같은 용도는 "당장 뚫린다"가 아닙니다 — 다만 배포자가 악의적일 수 있는 모델에서는 무너지고, 새로 만들 이유는 없습니다.

SHA-1은 값이 매겨졌다

2017년 구글과 CWI가 같은 SHA-1을 내는 서로 다른 PDF 두 개를 공개했습니다(SHAttered). 계산량은 SHA-1 연산 2^63.1회로, 무차별 대입 2^80보다 10만 배 적습니다.

2020년에는 선택 접두사 충돌이 나왔습니다 — 앞부분을 원하는 대로 정해 놓고 충돌을 만드는 것이고, 클라우드 비용으로 약 4만 5천 달러였습니다. 지금은 더 쌉니다.

Git이 아직 SHA-1을 쓰는 것은 그대로 쓰기 때문이 아닙니다. 2017년부터 SHA-1DC라는 충돌 탐지판을 씁니다 — 충돌 생성에 쓰이는 블록 패턴이 보이면 해시를 거부합니다. SHAttered PDF 두 개를 넣으면 오류가 납니다. SHA-256 저장소 형식도 있지만 전환은 진행 중입니다.

MD4는 OpenSSL이 막았다

이 환경에서 각 해시를 만들어 봤습니다.

md4        거부됨 — ERR_OSSL_EVP_UNSUPPORTED
md5        사용 가능
sha1       사용 가능
sha256     사용 가능

MD4는 OpenSSL 3이 legacy 프로바이더로 밀어내서, 기본 설정에서는 코드가 실행조차 되지 않습니다.

그런데도 MD4가 필요한 자리가 있습니다. 윈도의 NTLM 해시가 MD4(UTF-16LE(비밀번호))입니다. 계정 해시를 읽거나 대조하는 도구는 지금도 MD4를 계산해야 합니다. rsync의 옛 프로토콜도 MD4를 씁니다.

MD2는 더 오래됐습니다. MD4보다 앞서고 이후의 모든 것보다 느리며, 아주 오래된 X.509 인증서에서만 마주칩니다.

속도는 이유가 되지 못한다

md5       91ms    706 MB/s
sha1      25ms   2523 MB/s
sha256    25ms   2568 MB/s
sha512    43ms   1495 MB/s

64MB를 한 번씩 돌린 결과입니다. MD5가 SHA-256보다 느립니다.

이 기계의 CPU에 SHA 확장 명령이 있어서 SHA-1과 SHA-256이 전용 하드웨어로 계산되기 때문입니다. SHA-1이 SHA-256을 못 이기는 것이 그 신호입니다. 확장 명령이 없는 환경에서는 MD5가 더 빠르지만, 요즘 서버 CPU에는 대체로 있습니다.

"빠르니까 MD5"라는 근거가 성립하지 않는 하드웨어가 늘고 있습니다.

비트코인이 SHA-256을 두 번 돌리는 이유

SHA-256       = 44def25e0467af2f48ec188407deceb195ced02c …
SHA-256 두 번 = 9e50f00b9ccbe85eaf9d00cadf1dcbad56879112 …

머클-담고르 해시는 출력이 곧 내부 상태입니다. 그래서 원문을 몰라도 뒤에 데이터를 이어 붙인 메시지의 해시를 계산할 수 있습니다(길이 확장). 두 번째 해시의 입력은 32바이트 다이제스트뿐이라 그 통로가 막힙니다. 비트코인이 블록 헤더와 트랜잭션 id에 쓰는 구조입니다.

확인 순서

MD5·SHA-1이 서명이나 무결성 검증에 쓰이면 바꿉니다. 파일 식별용 캐시 키라면 급하지 않습니다
공격자가 두 입력을 모두 만들 수 있는 자리인지 봅니다. 그렇다면 충돌 저항성이 필요합니다
속도를 이유로 MD5를 고르고 있다면 배포 하드웨어에서 재 봅니다. 순서가 뒤집혀 있을 수 있습니다
MD4가 필요하다면 NTLM이나 rsync 호환 때문인지 확인하고, 그 경로만 격리합니다
hash(비밀키 + 데이터) 형태가 있으면 HMAC으로 바꿉니다. 길이 확장이 열려 있습니다

tools.onuel.dev에 계열이 다 있습니다. MD5와 SHA-1에 같은 입력을 넣어 SHA-256과 대조할 수 있고, MD4는 NTLM 해시를 확인할 때, MD2는 옛 인증서를 읽을 때 씁니다. 길이 확장을 막는 구조는 Double SHA-256에서 볼 수 있습니다.