같은 SHA-1 값을 낸 두 PDF: 해시 함수가 깨진다는 것
SHA-1 은 1995년에 표준이 된 해시 함수입니다 [S8]. 2005년에 이론으로, 2017년에 실제로 «깨졌다» 는 말을 듣습니다. 무엇을, 몇 번 만에 해냈길래 그럴까요?
같은 SHA-1 값을 낸 두 파일
2017년 2월 23일, 연구진이 서로 다른 PDF 두 개를 내놓았습니다. 두 파일의 SHA-1 해시 값은 같았습니다 [S1] [S2]. 서로 다른 입력이 같은 해시 값을 내는 충돌을 만든 것입니다.
해시 값은 블록을 차례로 압축 함수에 넣어 만든다
SHA-1·SHA-256 같은 해시 함수는 글을 64바이트씩 블록으로 자르고, 표준이 정해 둔 «처음 값» 에서 시작해 블록을 하나씩 섞어 넣습니다. 섞는 일을 맡은 부분이 압축 함수입니다. 블록 하나를 넣을 때마다 압축 함수가 내놓는 값이 중간 해시 값입니다. 중간 해시 값은 지금까지 넣은 블록을 모두 섞은 결과이고, 다음 블록은 이 중간 해시 값하고만 섞입니다. 마지막 블록까지 섞은 마지막 중간 해시 값이 해시 값입니다.
그래서 두 글이 어느 블록에서 같은 중간 해시 값에 이르면, 그 뒤로 같은 블록을 넣는 한 끝까지 같은 중간 해시 값이 되고 해시 값도 같아집니다. 이렇게 블록을 차례로 압축 함수에 넣어 이어 가는 방식을 머클-담고르 구조라고 합니다.
출처: NIST FIPS 180-4 Secure Hash Standard (§5·§6 — H(0)·H(i)·H(N), 512비트 블록) · Handbook of Applied Cryptography 9장 Algorithm 9.25 (Merkle-Damgård construction)
2017년의 두 파일이 바로 이 성질을 썼습니다. 두 파일의 앞부분을 직접 넣어 보세요 [S3].
앞 320바이트 가운데 62바이트가 달라도 SHA-1 값은 같고, SHA-256 값은 다릅니다. 아래 사슬을 보면 두 파일은 넷째 블록에서 중간 해시 값이 갈렸다가, 다섯째 블록에서 다시 같아집니다. 그 뒤에 무엇을 붙여도 SHA-1 값이 같은 까닭입니다.
그럼 SHA-256 은 왜 다를까요? 압축 함수는 안에서 작은 단계를 되풀이합니다. SHA-1 은 80단계, SHA-256 은 64단계이고, 단계마다 블록에서 늘린 단어를 하나씩 넣습니다 [S7]. 그림 1 은 넷째 블록을 넣는 단계마다 두 파일의 차이를 잰 것입니다.
SHA-256 은 몇 단계 만에 차이가 절반으로 퍼져 끝까지 갑니다. 넣는 단어의 차이도 커집니다.
SHA-1 은 처음에 차이가 생겼다가 금세 줄고, 끝날 때까지 몇 비트에 머뭅니다. 넷째 블록은 중간 해시 값에 14비트 차이만 남기고, 다섯째 블록이 그 차이를 지웁니다 [S1].
아무 두 파일이나 이렇지는 않습니다. 같은 31바이트 자리를 무작위로 바꾼 블록 쌍 1,000개를 넣어 보면, 차이는 SHA-256 처럼 절반으로 퍼집니다. 차이가 머무는 쌍은 연구진이 계산을 2⁶³ 번 남짓 들여 찾아낸 드문 쌍입니다. 찾는 방법은 이 글에서 다루지 않습니다.
«깨졌다» 의 뿌리는 이것입니다. SHA-1 에서는 차이가 퍼지지 않는 쌍을 실제로 찾을 수 있었습니다.
| SHA-1 | SHA-256 | |
|---|---|---|
| 블록을 차례로 넣는 구조 | 같음 (머클-담고르) | 같음 |
| 블록 크기 | 64바이트 | 64바이트 |
| 중간 해시 값 · 해시 값 크기 | 160비트 | 256비트 |
| 압축 함수의 단계 | 80번 | 64번 (규칙이 다름) |
| 충돌의 기준선 (생일 문제, 2장) | 2⁸⁰ | 2¹²⁸ [S6] |
몇 번이면 «깨졌다» 고 할까
2017년의 충돌에는 SHA-1 압축 계산이 2⁶³ 번 남짓 들었습니다. 빠른지 견줄 기준은 «아무 꾀 없이 글을 하나씩 만들어 해시 값을 견주기만 해도 충돌이 나오는 횟수» 입니다. 이보다 적게 들면 해시 함수가 깨졌다고 합니다 [S9].
이 기준은 생각보다 작습니다. 생일로 보면, «내 생일과 같은 사람 찾기» 와 «아무 둘이나 생일이 같기» 는 전혀 다른 일입니다.
아무 둘이나 생일이 같을 확률 (견줄 짝 쌍)
나와 생일이 같은 사람이 있을 확률
내 생일과 같은 사람이 있을 확률이 절반을 넘으려면 253명이 필요하지만(이 글의 계산), 아무 둘이나 같을 확률은 23명이면 절반을 넘습니다 [S4]. 23명이 만드는 짝이 253쌍이라, 겹칠 기회가 사람 수보다 훨씬 많기 때문입니다.
해시 값도 같습니다. 주어진 해시 값과 같은 글을 찾는 일(원래 글 찾기)이 «내 생일» 이고, 해시 값이 같은 아무 두 글을 찾는 일(충돌)이 «아무 둘» 입니다. 해시 값의 앞 몇 자리로 직접 해 보세요.
«찾기» 를 누르면 번호를 바꿔 가며 SHA-1 값을 만들고, 앞 자리가 겹치는 두 글이 나올 때까지 견줍니다.
자리가 하나 늘 때 원래 글 찾기는 16배, 충돌은 4배쯤씩만 어려워집니다. 16진수 한 자리는 16가지라, 자리가 하나 늘면 짝 하나가 겹칠 확률이 16분의 1로 줄어 짝이 16배 필요합니다. 글이 두 배면 짝은 네 배가 되니, 글은 4배면 됩니다. 한 자리는 4비트, 두 배는 1비트이니 4비트를 더 맞추는 데 2비트(4배)만 더 드는 셈입니다. 그래서 n비트 해시 값의 충돌은 2ⁿ 번이 아니라 약 2^(n/2) 번이면 나옵니다 [S5]. 160비트 SHA-1 이면 2⁸⁰ 번, 이것이 기준선입니다 [S6].
2⁸⁰ 보다 빨리
2005년에 2⁶⁹ 번보다 적은 계산으로 충돌을 찾는 방법이 나와, 이론으로 깨졌습니다 [S9].
2017년에는 SHA-1 압축 계산 약 2⁶³·¹ 번(2⁶³ 보다 조금 많음)으로 충돌을 실제로 만들었습니다 [S1]. 2⁸⁰ 과 견주면 두 배를 17번 덜 한 셈, 약 12만 배 빠릅니다. 그래도 CPU 6,500년에 GPU 100여 년을 더한 계산이었습니다 [S1] [S2].
그래서 무엇이 위험한가
디지털 서명은 파일 대신 파일의 해시 값에 합니다 [S14]. 따라서 해시 값이 같은 두 파일은 서명 하나를 나눠 쓸 수 있습니다.
두 방식 모두 공격자가 두 파일을 함께 만들어, 남이 이미 서명한 파일은 못 건드립니다. 다만 2017년 방식은 앞부분이 같아야 했고, 2020년의 선택 접두사 충돌은 앞부분을 각자 고를 수 있어 더 위험합니다. 연구진은 이것으로 남의 PGP 키를 사칭하는 예를 보였고, 계산에 7만 5천 달러 남짓을 썼습니다 [S10].
| 무엇 | 근거 | |
|---|---|---|
| 해낸 것 | 같은 해시 값의 다른 두 파일 만들기 (2017), 앞부분을 각자 고른 두 파일 겹치기 (2020) — 서명을 나눠 쓸 위험 | [S1] [S10] |
| 아직 못 한 것 | 원래 글 찾기(원상 공격: 주어진 해시 값과 같은 값을 내는 글 찾기) — 2017·2020 충돌 공격이 해낸 일이 아니다. n비트 해시 값이면 기대치는 약 2ⁿ 번 | [S1] [S10] [S5] |
| 대신 쓰는 것 | SHA-256 · SHA-3 — NIST 는 서명 생성에 SHA-1 을 쓰지 말라고 하고(NIST 가 정한 일부 프로토콜 제외), 2030년 말까지 자기 표준과 연방 조달에서 뺀다. Git 은 2018년 SHA-256 을 다음 해시로 골랐지만, 새 저장소의 기본값은 아직 충돌 공격을 막도록 고친 SHA-1 이다 | [S11] [S12] [S13] [S15] |
처음 시뮬레이터에서 해시 함수를 SHA-256 으로 바꾸면 같은 두 파일의 해시 값이 곧바로 갈립니다.
이 글의 계산과 확인
«약 12만 배» 는 2⁸⁰ ÷ 2⁶³·¹ = 2¹⁶·⁹ 에서 나온 값입니다. «253쌍» 은 23 × 22 ÷ 2, 확률은 1 − (1 − 1/365)(1 − 2/365)…(1 − 22/365) ≈ 0.507 입니다 [S4]. «253명» 은 1 − (364/365)ᵏ 이 처음 절반을 넘는 k 입니다.
시뮬레이터의 SHA-1·SHA-256 은 표준 [S7] 을 옮겨 이 글을 위해 직접 짠 교육용 코드입니다. 실제 보안에 쓰지 마세요. 두 PDF 의 앞 320바이트는 원본에서 그대로 옮겼고, OpenSSL 로도 SHA-1 은 같고(f92d74e3…) SHA-256 은 다름을 확인했습니다.
2017년 계산의 GPU 시간은 논문이 «100년», 발표가 «110년» 이라 «100여 년» 으로 적었습니다. 2020년 비용은 논문의 추정 최저치가 4만 5천 달러, 실제로 쓴 돈이 7만 5천 6백 달러입니다 [S10].
출처
- [S1] Stevens 외, The first collision for full SHA-1 (CRYPTO 2017)
- [S2] Google Security Blog — Announcing the first SHA1 collision (2017)
- [S3] shattered-1.pdf · shattered-2.pdf (앞 320바이트)
- [S4] Menezes 외, Handbook of Applied Cryptography 2장 (Fact 2.27)
- [S5] 같은 책 9장 (Algorithm 9.25, Fact 9.33)
- [S6] NIST SP 800-107 Rev. 1 (2012) §4.1
- [S7] NIST FIPS 180-4, Secure Hash Standard (2015)
- [S8] NIST FIPS 180-1 (1995)
- [S9] Wang · Yin · Yu, Finding Collisions in the Full SHA-1 (CRYPTO 2005)
- [S10] Leurent · Peyrin, SHA-1 is a Shambles (USENIX Security 2020)
- [S11] NIST SP 800-131A Rev. 2 (2019)
- [S12] NIST Retires SHA-1 (2022)
- [S13] Git — hash-function-transition
- [S14] NIST FIPS 186-5, Digital Signature Standard (2023)
- [S15] Git — git-init (--object-format «sha1 is the default») · hash-function-transition (v2.13.0 부터 «hardened SHA-1»)