지난 23일, 구글은 블로그를 통해 SHA-1 충돌을 현실화 시켰다고 발표하며, 이에 대한 코드를 90일 뒤 공개하기로 했습니다.
도입된 지 20년이 넘은 SHA-1 해시 알고리즘은 수많은 곳에서 사용되어 왔습니다. 2005년에 이론적인 공격 방법이 알려졌으며 2011년에 미국국립표준기술원(NIST)에 의해 공식적으로 폐기되었습니다. 개발 당시보다 비약적으로 컴퓨팅 성능이 발달한 오늘날에는 더욱 안전한 SHA-256이나 SHA-3으로 많이 전환되었으나, 아직까지도 SHA-1 알고리즘이 쓰이고 있는 경우를 많이 볼 수 있습니다.
그렇다면 구글에서 발표한 SHA-1 충돌은 무엇이며 어떤 의미를 갖는 걸까요.
◆ 해시충돌이란
해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 ‘해시충돌’이라고 합니다. 해시는 무한한 가짓수의 입력값을 받아 유한한 가짓수(해시의 비트수에 따름)의 출력값을 내므로 절대로 충돌을 피할 수 없습니다(비둘기집 원리).
암호화 해시 함수의 중요한 요소 중 하나는 계산을 통해 임의의 충돌을 찾아내는 것이 불가능해야 한다는 것입니다. 이러한 전제 하에서는 어떠한 파일의 위변조 여부를 가리기 위한 수단으로 해시 함수의 출력값을 이용할 수 있습니다. 여기서 ‘불가능’은 해시 함수의 출력 값 범위 내에서 어떤 알고리즘을 사용하더라도 해시 충돌을 일으키는 값을 다항시간 내에 찾아낼 수 없다는 것을 의미하며, ‘가능’은 생일 공격(Birthday attack)의 알고리즘 보다 훨씬 빠르게 충돌을 찾아낸다는 것입니다.
생일 공격의 논리적 기반이 되는 생일역설(birthday paradox)은 단순히 눈에 보이는 숫자보다 훨씬 적은 노력으로 해시충돌을 이룰 수 있음을 보여줍니다.
생일 역설 : 어떠한 그룹에 생일이 같은 사람이 있을 확률
n명의 그룹에서 생일이 전부 다를 확률
따라서, n명의 그룹에서 생일이 같은 사람이 있을 확률 p(n)은
이를 계산하면, 23명이 있는 그룹에서 생일이 같은 사람이 있을 확률은 50%를 넘어가며 40명이 넘는 경우 약 89.1%, 60명이 넘는 그룹에서는 확률이 99%를 넘어갑니다.
위의 경우를 날짜 -> 해쉬 출력값, n명의 사람 수 -> 해쉬 입력값 으로 치환해서 생각하면, 해시 함수의 입력값을 다양하게 할 수록 해시 값이 같은 두 입력값을 발견할 확률은 빠르게 증가함을 알 수 있으며, 따라서 모든 값을 대입하지 않고도 해시 충돌을 찾아낼 확률을 충분히 크게 만들 수 있습니다.
이러한 이론적 기반을 통해 충돌을 찾아내기 위한 계산의 양을 획기적으로 줄일 수 있었음에도 불구하고, 여전히 실제 충돌을 구현하기 위해서는 GPU로 1200만년동안 계산해야 할 분량이었으며 이는 비현실적이었습니다.
◆ SHAttered attack
구글과 네덜란드국립연구소의 합동연구팀은 이러한 이론적 가능성을 현실에 재현했습니다. 이를 위해서 새로운 방식을 사용한 것으로 보입니다.
네덜란드 국립 연구기관의 Mark Stevens가 발표한 이론적 접근을 기초로, 구글과 네덜란드연구기관의 합동연구팀은 전혀 다른 두 PDF 문서의 프리픽스를 생성하는 방법부터 연구하기 시작했고, 이후 구글의 기술자들과 클라우드인프라의 거대한 컴퓨팅 자원을 사용해 이론을 현실화할 수 있었습니다.
구글에 따르면, SHAttered attack으로 이름붙여진 이 방식은 생일역설(Birthday paradox) 에 기반한 브루트포스 공격보다 약 10만 배 빠릅니다. 이 공격 방식을 위해서는 약 922경 회(9,223,372,036,854,775,808)의 SHA-1 계산을 필요하며 이는 싱글CPU에서 6500년, 싱글GPU에서는 110년 걸려 계산할 분량입니다. 여전히 천문학적인 컴퓨팅 자원을 필요로 하나, 이론적으로만 가능성이 제시되었던 단계에서 크게 한 발 나아간 것이며 앞으로 하드웨어 성능이 향상되어감에 따라 이러한 장벽은 점점 낮아질 것입니다.
자세한 방식은 코드가 공개되어야 알 수 있으나 이는 SHA-1에 기반한 많은 리소스들에 큰 위협이 될 수 있습니다. 구글이 코드 공개까지 90일 딜레이를 둔 것은 이에 대응할 시간을 마련해주기 위함으로 보입니다.
◆ SHA-1의 취약점에 영향받는 사례
예를 들면, 공격자가 SHA-1의 충돌을 이용하면 원본 계약서를 위조 계약서로 바꿔치기 하는 등의 행위가 가능합니다. 그 외에 잠재적으로 SHA-1 취약점에 노출되어있는 사례는 다음과 같습니다.
신용카드거래
전자문서
오픈소스 저장소
소프트웨어 업데이트
디지털인증서
이메일 PGP/GPG 서명
소프트웨어 벤더 서명
소프트웨어 업데이트
ISO 체크섬
백업시스템
복제 시스템
Git
SVN
◆ 대응
현재 사용하고 있는 SHA-1 알고리즘을 안전한 SHA-3나 SHA-256으로 변경해야 합니다. Hardened SHA-1는 이번 SHAttered attack으로부터 안전합니다.
크롬과 파이어폭스 등의 브라우저에서는 이미 SHA-1을 이용한 TLS/SSL 인증서를 위험한 것으로 표시하고 있습니다.
이번 취약점을 테스트 할 수 있도록 준비된 테스트코드가 깃허브에 올라가 있습니다. (https://github.com/cr-marcstevens/sha1collisiondetection)
구글은 이번 발표를 통해 SHA-256이나 SHA-3 와 같은 안전한 알고리즘으로의 이행을 촉구할 수 있는 계기가 될 수 있다고 강조했습니다. 아직 이러한 변화를 미뤄두신 분들이 계시다면 이번 기회를 통해 점검해보시는게 어떨까요.
References:
(1) Google Security Blog. Announcing the first SHA1 collision. https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html (Accessed 2017-02-28).
(2) ITmedia. SHA-1衝突攻撃がついに現実に、Google発表 90日後にコード公開. http://www.itmedia.co.jp/enterprise/articles/1702/24/news067.html (Accessed 2017-02-28).
(3) SHAttered. https://shattered.it/ (Accessed 2017-02-28).
(4) Github. sha1collisiondetection. https://github.com/cr-marcstevens/sha1collisiondetection (Accessed 2017-02-28).
(5) Marc-stevens. https://marc-stevens.nl/research/ (Accessed 2017-02-28).
(6) Wikipedia. Birthday problem. https://en.wikipedia.org/wiki/Birthday_problem (Accessed 2017-02-28).
(7) Wikipedia. SHA-1. https://en.wikipedia.org/wiki/SHA-1 (Accessed 2017-02-28).
(6) Wikipedia. Collision (computer science). https://en.wikipedia.org/wiki/Collision_(computer_science) (Accessed 2017-02-28).
(6) Wikipedia. Pigeonhole principle. https://en.wikipedia.org/wiki/Pigeonhole_principle (Accessed 2017-02-28).
