지난 콘텐츠에서 해시함수의 다양한 활용 분야를 소개했습니다. 이번 글에서는 해시함수의 안전성을 깨기 위한 도전의 결과인 충돌쌍 발견 사례와 올바른 해시함수 선택과 사용에 관해 알아보겠습니다.

해시함수의 충돌쌍 발견 사례

해시함수의 충돌쌍을 발견했다는 것은 더 이상 해시함수가 안전하지 않다는 것을 의미한다고 봐도 무방합니다. 해시함수 충돌쌍 발견은 생일 역설(birthday paradox)에 기반을 두고 있는데요. 생일 역설이론은 랜덤하게 모인 23명 중에 생일이 같은 사람이 존재할 확률이 50% 이상 된다는 이론으로, 모수가 크지 않더라도 해시함수의 주어진 출력으로부터 입력을 찾아내는 것이 가능함을 뒷받침합니다.

해시함수를 공격하는 방법은 세 가지가 있습니다. 먼저, 주어진 해시 결과값을 가지고 입력값을 찾는 공격법인 ‘역상공격(preimage attack)’이 있습니다. 그리고 어떠한 입력에 대한 해시 결과값을 가지고 같은 해시값을 찾아 그에 해당하는 입력을 구하는 ‘제2역상공격(second preimage attack)’이 있습니다. 마지막으로, 가장 공격하기 쉬우면서 생일 역설을 근거로 앞의 두 가지 공격 방법보다 공격 성공률이 높은 방법이 있는데요. 동일한 해시 결과값을 갖는 충돌쌍(똑같은 해시값을 반환하는 서로 다른 데이터의 쌍)을 찾는 방법이 있습니다. 이를 ‘충돌공격(collision attack)’이라 부릅니다.

2000년대 초반까지 널리 사용되던 MD계열의 해시함수들은 중국의 Wang 교수가 2004년에 공개한 공격법으로 충돌쌍 발견 가능성이 커졌으며, 그중 MD5의 경우는, 이미 충돌쌍이 발견돼 암호학적 목적으로 더 이상 사용이 불가능하게 됐습니다. 또한 2005년에는 SHA-1가 안전하지 않다는 것이 알려졌는데요. 미국 정부는 2008년에 이미 MD5와 SHA-1의 사용을 중지하도록 했고, 이후에는 SHA-2를 사용할 것이라고 발표했습니다.

알려진 MD5의 제2역상 공격이 성공한 사례는 다음과 같습니다. 같은 해시 결과값을 갖는 서로 다른 입력값이 M1, M2와 같이 존재합니다. 두 메시지의 MD5 해시 결과값은 동일한 값 “79054025255fb1a26e4bc422aef54eb4”입니다. (https://www.mscs.dal.ca/~selinger/md5collision/)

앞서 언급한 SHA-1의 경우에도 2017년 충돌쌍의 사례가 발견됐습니다. 구글과 CWI 공동 연구진은 SHA-1의 충돌쌍을 찾는 기술을 2년여간 개발한 끝에, 동일한 SHA-1 해시 결과값은 가진 두 개의 서로 다른 PDF 파일 예시(https://shattered.it/)를 발표했습니다. 이들의 연구 목적은 다음과 같습니다.

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

이들이 충돌쌍을 발견하기 위해 투입한 자원은 전례를 찾아볼 수 없는 규모로, 클라우드 인프라를 활용해 아래와 같은 방대한 계산량을 처리했습니다. 해당 계산작업의 규모가 얼마나 큰 것인지 짐작할 수 있는 수치는 다음과 같습니다.

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

위 표에 의하면, MD시리즈와 SHA시리즈 모두 충돌, 제2역상, 역상에 대한 공격 가능성이 존재함을 확인할 수 있습니다. 위 공격은 아래 [참고] The Merkle–Damgård hash construction 방식을 채택하는 경우이며, 이 경우 대부분의 해시 알고리즘에서 충돌쌍이 발견되었습니다. SHA-2의 경우, Merkle–Damgård 방식이 아닌, 다른 변이로 사용하는 경우, 현재까지 충돌쌍이 발견되지 않았다고 보고됐습니다.

[참고] “Merkle–Damgård hash construction” 방식은 메시지를 고정 크기의 블록으로 나누고 해시함수로 한 번에 하나씩 처리합니다. 매번 입력 블록과 이전 라운드의 출력 블록을 결합합니다. 안전한 구성을 위해 원본 메시지의 길이를 인코딩하는 패딩으로 메시지 패딩하는 방법을 추가하였습니다.

<해시함수의 충돌쌍 발견 사례 요약>

■ 2004년 8월, MD5를 포함한 다양한 해시함수에서 충돌쌍 발견
■ 2004년 8월, SHA-0의 충돌쌍 발견, 복잡도 251, 8만 CPU 시간 소요(256개의 Itanium2 프로세서 장착한 수퍼 컴퓨터를 full-time 사용하여 13시간 연산하는 것과 동일한 시간)
■ 2005년 2월, SHA-1의 충돌쌍 발견(SHA-1 160비트의 경우)
■ 2008년 TLS(Transport Layer Security)에서 사용되는 인증서 내 사용된 MD5 충돌쌍 발견
■ 2017년 2월, CWI+구글 SHA-1의 PDF형식의 충돌쌍 발표

해시함수 올바른 선택과 사용

해시함수는 디지털 트랜잭션의 무결성 보장을 위한 핵심적인 역할을 하는 기반 기술로서, 신중하게 선택하고 사용해야 합니다. 해시함수 활용 시 다음과 같은 점에 주의하기를 권고합니다.

■ 충돌쌍이 발견된 해시함수 선택은 지양해야 합니다. (MD2/MD4/MD5, SHA-0/SHA-1 등)
■ 향후 프로젝트에서는 SHA-256이나 SHA-3와 같은 최신의 해시함수 선택을 권고합니다.
■ 안전성이 취약한 해시함수를 여러 번 수행하여도 안전성이 증가하지 않습니다. 표준에서 안전성이 확인된 해시함수를 채택하여, 반복 적용할 것을 권고합니다.
■ SALT와 키 스트레칭(키에 대한 반복적인 해시함수 적용)을 필수적으로 고려해야 합니다.
■ 해시함수 구현에 자의적인 해석에 기반하여 안전성이 미 확인된 형태로 변형을 가하거나 결과값의 일부만 사용하는 것을 지양해야 합니다.

[참고문헌]

충돌쌍 탐색 공격에 대한 해시함수 안전성 강화에 관한 연구, 정은진, 한정훈, 김승주,원동호
성균관대, 정보보호연구소, 2008
Finding Collisions in the Full SHA-1, Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, Advances in Cryptology – CRYPTO 2005 pp 17-36, 2005
The first collision for full SHA-1, Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov 2017
New collision attacks on SHA-1 based on optimal joint local-collision analysis, Marc Stevens, EUROCRYPT 2013, Lecture Notes in Computer Science, vol. 7881, Springer, 2013, pp. 245-261
블록체인의 암호기술: 해시함수 활용, 김종현, 아주대학교, 2018
MD5 Collision Demo, Peter Selinger, Published Feb 22, 2006. Last updated Oct 11, 2011.

글 ㅣ LG CNS 사이버시큐리티팀 전경화 책임