구글과 네덜란드 CWI 연구소에서 SHA-1 해시함수의 충돌쌍을 생성하는 서비스를 공개하였습니다. 원문 글은 Google Security Blog에 2017년 2월 23일에 업데이트되었습니다. 해당 블로그의 글을 한글화하여 포스팅합니다. 개인적으로, 어색하게 직역되어 무슨뜻인지 이해가 불가능한 글을 상당히 싫어합니다. 이 글은 제가 원문의 글을 파악하고 이해한 후에 그 문장을 익숙한 한국어 문장으로 다시 작성하였습니다. 그렇지만 원저자의 의도를 왜곡하지는 않았습니다.


구글 블로그 : https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

서비스 사이트 : https://shattered.io/

Marc Stevens Research : https://marc-stevens.nl/

참고논문 : https://shattered.io/static/shattered.pdf

  • Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. "The first collision for full SHA-1." 2017.
  • Stevens, Marc, Pierre Karpman, and Thomas Peyrin. "Freestart collision for full SHA-1." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2016.

관련기사 : https://phys.org/news/2017-02-cwi-google-collision-industry-standard.html


SHA-1 등의 암호학적 해시함수는 실생활에서 매우 널리 응용되는 유용한 도구입니다. 인터넷 브라우져에서도 그 원리가 적용되어 있고, Git Repository의 버전관리 기능이나, 디스크 내부의 중복 파일을 검출하는 일에도 해쉬함수가 사용되고 있습니다. 해시함수는 기본적으로 방대한 양의 데이터를 압축하여 단일한 길이의 Message Digest를 생성합니다. 단, 이러한 성질에는 특별한 요구사항을 만족시켜야 하는데, ‘동일한 해시값을 같는 서로 다른 두 메시지’를 찾는 것이 계산상 불가능(Computationally infeasible)해야 한다는 성질입니다. 그러나 지난 세월동안, 암호해독자들은 알고리즘의 설계구조상 약점을 수학적으로 철저하게 파헤치고, 발달하는 고성능 컴퓨팅 자원을 도입함으로써 해시함수를 공격하는일에 열중하고 있었습니다.


SHA-1 해시함수가 최초 설계된 이후 20여년이 흘렀습니다. 저희 연구진에서는 SHA-1의 충돌쌍을 찾는 기술을 개발하였으며, (단지 이론적이 아닌) 실무적으로는 처음 선보이는 것입니다. 본 연구는 네덜란드 암스테르담의 CWI 연구소와 Google의 공동 프로젝트로 수행되었으며, 그 2년여간의 연구의 절정에 다다른 소식을 여러분께 간략히 전해드립니다. 본 포스팅에서는 해쉬 충돌쌍을 어떻게 찾았는지에 대해 언급하고, 이에 대한 증명으로 서로 다른 내용을 포함하고 있는 PDF 파일 두 개를 제시하고자 합니다. 여러분이 직접 계산해보셔도 두 PDF는 동일한(identical) SHA-1 해시를 출력한다는 것을 확인하실 수 있습니다.


저희 연구의 목적은 다수의 기업들이 더 이상의 SHA-1 사용을 중단하도록 권고하는 것이며, 구글의 경우 이미 오래전부터 TLS 인증서 등에서 SHA-1을 배제해야한다고 강력히 주장해왔습니다. 2014년 초 구글 크롬 개발진들은 단계적으로 SHA-1 사용을 줄여감으로써 결국 단종시키겠다고 선언하였습니다. 본 연구를 통해 밝혀진 실질적인 공격으로, 이제 더 이상 SHA-1을 사용한 프로토콜은 안전하다고 간주할 수 없다는 것을 강조하고 싶습니다. 때문에 이제는 업계에서 SHA-256 같은 대안으로 전환하는 것이 시급하다는 것을 명심하시길 바라겠습니다.



암호학적 해시함수의 충돌쌍(collision)이란 무엇인가?

위의 그림 왼쪽은 일반적인 경우이고, 오른쪽은 Good doc과 Bad doc이 동일한 해쉬값을 나타내고 있는 Collision
위의 그림 왼쪽은 일반적인 경우이고, 오른쪽은 Good doc과 Bad doc이 동일한 해쉬값을 나타내고 있는 Collision

가령 어떤 두 개의 데이터(문서파일, 바이너리, 웹 인증서 등)가 있다고 칩시다. 그런데 이 두 데이터에 대한 해시를 계산하였더니 같은 결괏값이 도출되었다면, 이를 해시 충돌쌍이라고 합니다. (위의 그림 왼쪽은 일반적인 경우이고, 오른쪽은 Good doc과 Bad doc이 동일한 해시값을 나타내고 있는 Collision) 만약, ‘안전한 해시함수’라면 위와 같은 일은 결코 발생하지 않아야 합니다. 그럼에도 불구하고, 유능한 해커라면 해시 알고리즘 자체의 결함이 있다면 그 부분을 집중적으로 공략하여 충돌쌍을 찾아낼 수 있을 것입니다. SHA-1 역시 이렇게 공략당했습니다. 이 방법을 악용한다면 시스템 내부의 파일을 제멋대로 교체해버리고서는 그것이 마치 기존에 존재하던 파일인 것처럼 둔갑시킬 수 있습니다. 그 시스템이 SHA-1에 의존적인 상태라면 말이죠. 실생활을 예로 들자면, ‘보험 서류’를 감쪽같이 위조하여 계약자 본인도 모르는 사이 지불조건 및 보상내용이 최초 확인한 것과는 달리 완전히 뒤바뀐 상황을 상상해보시면 되겠습니다.



SHA-1의 충돌쌍을 찾기위한 여정

2013년, Marc Stevenes 는 SHA-1의 충돌쌍을 찾는 이론적인(theoretical) 접근을 시도하여 이를 논문으로 발표하였습니다. 이에 착안하여, 먼저 특별히 설계된 PDF 헤더(prefix)를 제작하였습니다. 이 헤더를 통해 두 파일의 내용이 확연히 구분될 수 있도록 한 것입니다. 그러나 두 헤더의 SHA-1 해시값은 일치하여야 한다는 조건이었습니다. 이러한 이론적인 전제를 기반으로 이를 실제적으로 구현하는 것은 상당히 극복하기 쉽지않은 도전과제였습니다. 저희는 Google의 기술지원과 막강한 클라우드 인프라를 활용하여 지금까지 도무지 전례를 찾아볼 수 없는 어마어마한 계산량을 처리하였습니다.


아래의 숫자를 보시면 해당 계산작업의 규모가 얼마나 큰 것인지 체감하실 수 있을 것입니다.

  • SHA-1 계산 총량 : 9 quintillion(10^18), 한국 단위로 900경(京) (9,223,372,036,854,775,808)
  • 이를 CPU 계산속도 기준으로 치면 6,500년 소요
  • GPU로 치면 110년 소요 ( *110개의 GPU를 병렬처리하면 1년)

위의 숫자는 여전히 매우 크지만, 저희의 기법(SHA-1 shattered attack)을 사용하면 단순 Brute Force 같은 비현실적인 방식에 비해 10만배 이상 빠릅니다.



SHA-1 충돌쌍 공격에 대한 대비책

때문에 보안업계 종사자들은 향후 프로젝트에서 SHA-256이나 SHA-3와 같은 더욱 진보된 암호학적 해쉬함수 체제로 전환하는 것이 상당히 시급하게 권고됩니다. 구글의 취약점 공개 정책에 따라, 저희의 소스코드를 90일 후에 공개할 예정입니다. 해당 코드를 사용하면 누구나 SHA-1 충돌을 일으키는 PDF 파일쌍을 생성하실 수 있습니다. 그 파일들은 사전조건을 충족시키도록 설계된 두 개의 서로 다른 이미지를 내포하고 있습니다.


혹시나 저희의 연구를 악용한 공격이 발생할수도 있습니다. 이를 보호하기 위해서 저희는 자사의 서비스인 Gmail이나 GSuite에 적절한 보안조치를 취하였습니다. 또한, 이를 탐지할 수 있는 시스템을 무료로 제공합니다.


SHA-1 공격에 관한 본 연구에 대해 기술적인 세부사항은 아래의 링크에서 확인하실 수 있습니다.



연구진에 관하여

본 연구는 CWI 연구소와 Google의 보안팀(security, privacy and anti-abuse Group)의 장기간에 걸친 협력의 산물입니다. Marc Stevens(CWI 책임자)의 SHA-1 공격에 관한 이론 논문이 발표된 이후, Google의 Elie Bursztein이 협력하여 구글의 컴퓨팅 자원을 통해 실제적인 적용을 이루어냈습니다. Ange Albertini 는 PDF 파일 생성 부분을 담당하였고, Pierre Karpman은 GPU 프로세싱과 암호해독을 맡았으며, Yarik Markov는 GPU 계산 코드를 구현하였습니다. 마지막으로 Alex Petit Bianco는 Google 사용자를 보호하기 위한 Collision 감지 기능을 개발하였고, Clement Baisse는 전체적인 신뢰성을 검증하였습니다.



번역자 첨언

저의 지난번 포스팅 "디지털증거의 무결성 입증시 MD5 해시함수 사용에 관한 재고찰"에서 Marc Stevens의 업적을 언급한 바 있습니다. 그는 CRYPTO 2009에서 발표한 논문에서("Short chosen-prefix collisions for MD5 and the creation of a rogue CA Certificate") MD5의 충돌쌍을 이용한 인터넷 브라우저의 인증서를 위조하는 기법으로 SSL 통신에서 중간자 공격이 가능함을 보임으로써 MD5에 대한 사망선고를 내렸습니다. 이후 그는 더이상 MD5에 대한 연구에 실효성이 없다고 판단하고 SHA-1 해시함수에 대한 공격쪽으로 연구분야를 변경한 것으로 보입니다. 


모질라, 마이크로소프트 및 구글은 자사의 브라우저에 대한 SHA-1 지원 종료예고를 발표하였습니다. 2017년 1월에 발표된 파이어폭스 5,1, 크롬 56 및 2017년 2월 14일 발표된 마이크로소프트 에지 및 인터넷 익스플로러 11은 더이상 SHA-1을 지원하지 않습니다. SHA-1 해시 알고리즘의 취약점 역시 10년이상 되었습니다.(참고 : Microsoft plans St Valentine's Day massacre for SHA‑1


이번에 Stevens와 Google 의 연구성과를 통해 해쉬함수에 대한 전환이 조금 더 빠르게 이루어지기를 기대해보며, 더불어 디지털포렌식계에서 여전히 널리 사용되고 있는 MD5와 SHA-1에 대한 고찰도 필요하다고 지적하는 바 입니다.

CPUU님의 창작활동을 응원하고 싶으세요?