2017년 2월 23일, 구글과 CWI 암스테르담의 연구자들이 두 개의 PDF 파일을 웹사이트에 올렸다. 두 파일은 눈에 띄게 달랐고 — 나란히 열어보면 내용이 다른 게 보였다 — SHA-1 해시가 같았다. shattered.io에서 두 파일을 직접 내려받아 sha1sum을 돌려볼 수 있었다. 똑같은 40자리 16진수. 서로 다른 두 문서.
칠판 위의 증명에 머물던 해시 충돌이 손에 쥘 수 있는 파일이 되면 이런 모습이다. 그리고 곱씹어볼 대목은 이게 마침내 일어났다는 사실이 아니다. 보안 업계 전체가 2005년부터 이게 온다는 얘기를 들었고, 추정 비용이 해마다 떨어지는 걸 지켜봤으면서도, 2017년 2월 23일을 소식이 도착한 날처럼 취급했다는 것이다.
충돌이 실제로 무엇을 깨뜨리는가
암호학적 해시가 여기서 중요한 약속은 하나다. 같은 출력을 내는 두 입력을 아무도 찾을 수 없다. “찾기 어렵다”가 아니라 아무도 못 찾는다. 해시를 보안에 쓰는 모든 용도가 여기에 기댄다 — 전자서명은 문서가 아니라 문서의 해시에 서명하므로, 내가 해시가 같은 두 번째 문서를 만들 수 있다면 첫 문서에 대한 당신의 서명은 내 문서에 대한 유효한 서명이 된다. 인증기관(CA)은 인증서의 해시에 서명한다. Git은 모든 커밋을 그 내용의 해시로 이름 붙인다. “같은 출력을 내는 두 입력을 못 찾는다”가 깨지면, 이 모든 게 그 균열을 물려받는다.
SHA-1은 160비트를 출력한다. 무차별 대입 — 생일 공격 — 으로 아무 충돌이나 찾으려면 약 2⁸⁰번의 연산이 필요한데, SHA-1이 나온 1995년엔 넉넉히 손이 닿지 않는 수였다. 문제는 SHA-1의 내부 구조에 약점이 있어서 무차별 대입보다 훨씬 싸게 갈 수 있다는 점이고, 2005년 왕샤오윈(Xiaoyun Wang)과 동료들이 그 비용을 대략 2⁶⁹까지 낮추는 공격을 발표했다. 무차별 대입보다 약 2,000배 싸다. 아무도 실제로 돌리진 않았다 — 여전히 어마어마했으니까 — 하지만 그 숫자가 발표됐고, 그 순간부터 SHA-1은 알려진 균열과 떨어지는 가격표를 단 해시였다. 유능한 사람은 다 알았다. 충돌은 예산과 시간의 문제일 뿐이었다.
12년의 기다림
여기가 마음에 걸려야 하는 대목이다. NIST는 2011년에 SHA-1을 공식 폐기 대상으로 지정했고 2013년엔 전자서명 용도를 금지했다. CA/브라우저 포럼은 인증기관이 2016년 1월 1일 이후로 SHA-1 인증서 발급을 중단하고 브라우저는 1년 뒤부터 신뢰하지 않기로 못박았다. 이 모든 게 실제 충돌이 시연되기 전에 벌어졌다 — 데드라인은 이론만 보고 정해졌고, 원래 그래야 맞다. 그런데도 인터넷의 상당 부분은 데드라인에 코가 닿을 때까지 질질 끌었다. “이론상 깨졌다”는 게 고통스러운 마이그레이션을 할 이유처럼 느껴지지 않았기 때문이다. 누군가 파일을 올리기 전까진 학술적 각주처럼 느껴진다.
누군가 파일을 올렸다. SHAttered에는 약 92해(9.2 × 10¹⁸, quintillion) 번의 SHA-1 연산이 들었다 — 1단계에 약 6,500 CPU-년, 2단계에 110 GPU-년, 구글의 서버 팜에서 병렬로 돌려 실제 소요 시간은 수백 년이 아니라 수개월이었다. 무차별 대입보다 약 10만 배 싸다. 그게 핵심이다. SHA-1을 안전해 보이게 만들던 “2⁸⁰”은 애초에 진짜 숫자가 아니었다. 진짜 숫자는 10년간 논문 속에서 줄어들고 있었고, 2017년은 그저 그 숫자가 “대기업이 시연용으로 감당 가능한” 선 아래로 떨어진 해였을 뿐이다.
정말 위험했던 충돌은 나중에 왔다
명성은 SHAttered가 가져갔지만, 그건 제한된 무기였다. 그건 identical-prefix(동일 접두) 충돌이었다. 두 파일은 같은 앞부분을 공유해야 했고, 연구자들이 양쪽 파일 가운데의 충돌 블록을 통제했다. 다르게 렌더링되는 두 PDF를 만드는 데는 충분하고 분명한 균열이지만, 실제 표적에 무기화하기는 껄끄럽다. 공격자가 충돌의 양쪽 절반을 다 만들어야 하기 때문이다.
걱정해야 할 쪽은 2020년 1월에 왔다. 게탕 뢰랑(Gaëtan Leurent)과 토마 페이랭(Thomas Peyrin)이 “SHA-1 is a Shambles”를 발표하며 최초의 실용적 chosen-prefix(선택 접두) 충돌을 내놨다. 선택 접두란 공격자가 서로 다른 임의의 두 시작 — 이를테면 서로 다른 두 신원 — 을 고르면, 수학이 각각에 덧붙일 충돌 블록을 찾아준다는 뜻이다. 이게 실제 물건을 위조하는 공격의 형태다. 그들은 PGP 신뢰의 웹(web of trust)에서 피해자를 사칭하며 이를 시연했다. 한 사람의 키에 대한 서명이 다른 사람의 키에 대한 유효한 서명이 되어버린다. 비용은 대여한 GPU 시간으로 약 4만 5천 달러, “학술 연구자의 예산 범위 안”이었고, 누구나 빌릴 수 있는 하드웨어였다. SHAttered 3년 뒤, 위험한 버전의 공격은 중고차 한 대 값도 안 됐다.
그러니 2015년엔 그토록 공격적으로 느껴지던 마이그레이션 데드라인이, 지나고 보니 정확히 맞았다 — 그리고 질질 끈 쪽은 암호학자들이 말하던 그대로 무모했다.
Git은 왜 무너지지 않았나
뻔한 반박이 있다. Git은 모든 걸 SHA-1로 이름 붙이는데, Git은 2017년에 무너지지 않았다. 왜?
Git은 SHA-1을 적대적 입력에 대한 서명으로 쓴 게 아니라, 대체로 커밋을 건네는 상대를 이미 신뢰하는 시스템 안에서 콘텐츠 주소로 썼기 때문이다. 충돌은 공격자가 축복받은 객체를 악성 쌍둥이로 바꿔치기할 수 있을 때 문제가 된다. Git의 노출은 실재하지만 CA보다 좁고, 프로젝트는 두 가지 방법으로 시간을 벌었다. 첫째, SHAttered 저자 중 한 명인 마르크 스테번스(Marc Stevens)가 충돌 탐지기를 만들어뒀다. 평소처럼 해시하되 알려진 공격 기법 특유의 내부 상태를 알아채고 그 입력을 거부하는 함수다. Git과 GitHub은 이 하드닝된 SHA-1(SHA-1DC)을 배포해, SHAttered가 만들어낸 바로 그 부류의 충돌 블록을 즉시 걷어낸다. 둘째, Git은 SHA-256으로 가는 길을 천천히 닦아왔다. 탐지기는 가라앉는 배에 댄 반창고다. 시간을 벌 뿐 해결책은 아니다. 다만 이건 “SHA-1이 깨졌다”가 하나의 사실이 아니라는 걸 잘 보여준다 — 그건 전적으로 당신의 위협 모델에 입력을 고를 수 있는 공격자가 포함되느냐에 달렸다.
진짜 교훈은 SHA-1 이야기가 아니다
폐기되는 모든 기본 요소가 이 곡선을 그린다. 학술 문헌이 그 균열을 예측 가능하게 만드는 순간이 있고, 훨씬 뒤에 누군가 내려받을 수 있는 개념 증명(PoC)을 공개하는 순간이 있다. 실제 위험은 전부 그 둘 사이의 틈에 산다 — 그 창(窓)이 바로, 원리상 악용 가능하고, 예산 있는 자는 다 알고 있으며, 대부분의 운영자는 마이그레이션에 한 스프린트를 쓰기 전에 여전히 PoC를 기다리고 있는 구간이기 때문이다. SHA-1 이야기 전체를 그렇게 굴렸고, 우리는 지금 양자 컴퓨터가 깨뜨릴 것으로 예상되는 기본 요소들을 두고 똑같은 각본을 돌리고 있다. 이론은 나왔고, 데드라인은 정해졌으며, 인터넷의 대부분은 움직이기 전에 그 파일을 보기를 기다리고 있다.
SHAttered가 증명한 불편한 사실은 SHA-1이 약했다는 게 아니다. SHA-1이 약하다는 건 다들 알았다. 증명한 건, “다들 약한 줄 안다”와 “다들 약한 것처럼 행동한다” 사이가 몇 년으로 벌어져 있고, 그 사이를 가르는 건 시연 — 발견이 아니라 시연 — 이라는 점이다. 암호학자들은 2005년에 옳았다. 업계는 2017년에 그들을 믿었다. 설득당하기를 기다리며 악용 가능한 채로 보낸 12년은 긴 시간이다.