2017년 3월 5일 자 전자신문에는 <오래된 해시 알고리즘 SHA-1 시대는 끝났다>라는 제목의 기사가 눈길을 끌었습니다. 기사의 내용은 암호학자들이 이론적 위험성을 경고한 2004년 이후, 구글이 13년 만에 SHA-1의 보안성을 깨트렸다는 내용이었는데요. 실제로 구글은 네덜란드 암스테르담 국립수학전산학연구소(CWI)와 함께 SHA-1의 결과값이 똑같은 PDF 파일 두 개(충돌쌍)를 만들었다는 연구 결과를 발표했습니다.

이것은 1995년 미국의 표준기술연구소(NIST)가 국가 표준으로 채택한 이후, 22년 만에 ‘SHA-1이 더 이상 안전한 해시 알고리즘으로 역할을 할 수 없다’는 것을 공식화한 것입니다.

해시함수는 우리의 일상 속에서 가장 널리 사용되는 암호 알고리즘입니다. 가장 쉬운 예로 사용자가 시스템에 접속하는 첫 단계인 로그인 시에 아이디와 비밀번호를 확인하는 과정에서 활용되죠.

사용자의 아이디와 비밀번호는 통상적으로 데이터베이스에 보관됩니다. 로그인을 시도하면 시스템이 사용자 아이디를 확인하고, 입력한 비밀번호와 테이블 내에 있는 비밀번호가 일치하는지 비교합니다. 이때 테이블에 비밀번호를 ‘암호화되지 않은, 읽을 수 있는 데이터(평문)’로 저장하지 않고, 해시함수를 이용해서 ‘정보를 되돌리기 어려운 형태(일방향)’로 암호화하여 저장합니다.

그리고 사용자가 입력한 비밀번호를 실시간으로 해시하여 그 결괏값을 테이블 내 저장된 암호화된 비밀번호와 비교하죠. 해시 이전의 비밀번호 원본을 찾기 힘든 해시함수의 암호적 특성을 활용해 사용자의 아이덴티티를 안전하게 확인하는 방식입니다.

이처럼 해시함수는 비밀번호를 암호화해 저장하는 용도 외에도, 다양한 디지털 서비스의 프리미티브로 활용되고 있습니다. 지금부터 해시함수의 다양한 활용 분야를 소개하겠습니다.

해시함수의 활용

디지털 데이터는 위변조가 용이하므로 트랜잭션의 위변조를 방지하고, 무결성을 확인할 수단이 필요합니다. 그렇기 때문에 디지털 데이터를 교환하는 현재 거의 모든 트랜잭션은 해시함수를 가장 기초적인 무결성 보장의 수단으로 사용합니다. 좀 더 구체적으로 살펴보겠습니다.

첫 번째, 메시지와 파일 등의 무결성을 검증하는 데 활용합니다.
트랜잭션의 송신 전후, 메시지 다이제스트(메시지의 해시함수 결괏값)을 비교해 트랜잭션을 통해 메시지나 파일에 대한 변경이 있었는지를 확인할 수 있습니다. 공유하는 파일의 해시 결괏값을 웹사이트나 포럼 등에 공개해 다운로드한 파일의 무결성을 검증할 수 있도록 합니다.

두 번째, 전자서명의 생성과 검증에 활용할 수 있습니다.
거의 모든 전자서명 알고리즘은 메시지에 대한 암호학적 해시함수를 적용하도록 설계하고 있죠. 전자서명을 수행하기 이전에 해시함수를 적용함으로써, 원본 메시지보다 상대적으로 작고, 안전하고, 계산적으로 원하는 크기의 메시지 다이제스트값을 생성하여 서명을 수행하도록 하는데요. 이 과정에서 전자서명 생성과 검증에 드는 계산 시간을 단축할 수 있으며, 전체 트랜잭션의 신뢰성을 확보할 수 있습니다.

세 번째, 패스워드 검증에 활용할 수 있습니다.
서두에 언급한 대로, 이는 해시함수가 가장 보편적으로 활용되는 분야이며, 패스워드의 해시값을 저장함으로써 내부자 유출 시도 또는 해커의 공격 시에도 개인정보 노출의 위험을 감소시킬 수 있습니다.

공개된 표준 해시 암호 알고리즘은 계산적으로 빠른 성능(일반적인 장비에서 약 0.1~0.2초 이내 소요)을 내도록 설계됐습니다. 하지만 역으로 이러한 특성이 빠른 계산에 기반한 패스워드 추측 공격을 시도할 수 있게 하는 취약점이 되기도 합니다.

패스워드 추측 공격을 방어하기 위해, PBKDF2처럼 키 스트레칭을 수행하는 알고리즘을 통해 추측 공격 시도에 훨씬 더 많은 시간이 소요되도록 할 수 있습니다. 사용자가 입력한 패스워드에 해시함수를 한 번이 아니라 여러 번 수행하는 방식인데요. 일반적인 장비로 1초에 50억 개 이상의 해시값을 비교할 수 있지만, 키 스트레칭을 적용하면 동일한 장비에서 1초에 5번 정도만 비교할 수 있게 됩니다.

패스워드 추측공격을 막을 수 있는 다른 방법으로, ‘SALT’라 불리는 크고 랜덤한 숫자를 입력값으로 사용하는 방법이 있습니다. 동일한 패스워드 입력값이 주어지더라도, SALT에 의해 결괏값이 랜덤하게 달라지도록 하는데요. 이를 통해 해커가 사전에 계산한 방대한 해시값 테이블을 준비해 패스워드 추측 공격을 불가능하게 할 수 있습니다.

결국, 패스워드 해시함수로 가장 많이 사용되고 권장되는 것은 PBKDF2(Password-Based Key Derivation Function)입니다. 해시함수의 컨테이너인 PBKDF2는 SALT를 적용한 후 해시함수의 반복 횟수를 임의로 선택할 수 있습니다. 아래는 PBKDF2 함수이며, 키 스트레칭과 SALT가 포함된 입력값을 알 수 있습니다.

DIGEST = PBKDF2(PRF, Password, Salt, c, DLen)

■ PRF: 난수(예: HMAC), Password: 패스워드 원본 값, Salt: 암호학 솔트
■ c: 원하는 iteration 반복 수(해시함수 적용 회수), DLen: 원하는 다이제스트 길이

네 번째, 파일이나 데이터의 식별자(identifier)로 사용할 수 있습니다.
해시함수는 Git과 같은 소스 코드 관리시스템이 파일을 안전하게 관리하고 식별할 목적으로 사용할 수 있습니다. 파일 콘텐츠나 디렉터리 트리 구조, 생성 계보 정보 등을 기반으로 해시값을 생성해 파일 식별 기능을 제공합니다.

요약하면, 해시함수는 무결성 검증, 전자서명의 생성과 검증, 패스워드 암호화 및 검증과 파일의 식별자 등 4가지 분야에서 활용 가능합니다. 블록체인에서도 이들 해시함수의 기능을 활용해 블록체인 지갑주소, 체인 무결성 검증, 채굴 합의 알고리즘 등에 사용하고 있습니다. 좀더 자세히 살펴보면 다음과 같습니다.

첫째, 공개키의 해시값을 지갑 주소로 활용해 익명화된 거래를 수행하도록 합니다. 즉, 가상화폐의 전자지갑 주소는 공개키 기반 암호화 알고리즘에서 생성된 공개키의 해시 결괏값을 사용합니다. 송신자의 개인정보인 계좌정보를 공개하지 않고, 익명화된 거래를 통해 송금자의 신원을 감추고, 송금할 수 있도록 기능을 제공하고 있습니다.

둘째, 해시함수를 사용해 블록체인 무결성 검증을 수행합니다. 머클루트는 블록이 보유하고 있는 거래 내역의 해시값을 가장 가까운 거래내역끼리 쌍을 이뤄 해시화하고, 더는 쌍을 이룰 수 없을 때까지 이 과정을 반복했을 때 마지막에 얻게 되는 값입니다. 머클루트는 각 거래 정보(TXID)가 변경됐는지에 대한 유효성을 검사하는 임무를 수행하는데요. 머클루트의 결괏값을 통해 블록 해시의 정보가 구성됨으로 그 블록의 유효성 또한 함께 검사할 수 있습니다.

[머클루트 생성과정]
■ 최초 데이터를 SHA256 형태의 해시값으로 변환한다.
■ 가장 가까운 노드 두 개를 한 쌍으로 묶어 합친 후 해시값으로 변환한다.
■ 계속해서 해시값으로 변환해 마지막 하나가 남을 때까지 이 과정을 반복한다.

셋째, 합의 알고리즘으로 PoW(Proof of Work) 방식을 사용할 경우, 해시값을 계산하는 채굴에 활용합니다. 이것은 새로운 화폐가 생성되는 과정에서 채굴자에게 ‘일을 했다는 것을 증명(proof of work)’하도록 해 화폐의 가치와 보안성을 확보하는 방식입니다. 분산 네트워크에서는 채굴과정에서 누가 얼마의 새 화폐를 받을지를 결정할 중앙 권력이 없기 때문에 모든 참여자가 자동으로 동의할 방법이 필요했는데요. 이때 일방향함수인 해시 함수가 계산하기는 쉽지만, 역을 구하는 것(채굴)은 어렵다는 것에 착안해, 모든 참여자 중 가장 먼저 채굴한 사람이 새 화폐를 받아 가게 하는 방식을 채택했습니다.

이처럼 다양한 분야에서 디지털 트랜잭션의 검증 수단으로 활용되는 해시함수는 완벽할까요? 오랫동안 이 분야에서 전문가들은 ‘완벽한’이라는 단어 대신 ‘계산적으로 충분히 안전한’이라는 표현을 사용해 왔습니다. 다시 말해서, 당대의 컴퓨팅 자원을 총동원해 계산적으로 깨질 수 없는 정도를 안전하다고 간주해 온 거죠.

2편에서는 해시함수의 안전성을 깨기 위한 도전의 결과인 충돌쌍 발견 사례와 올바른 해시함수 선택과 사용에 관해서 말씀드리겠습니다.

[참고문헌]

충돌쌍 탐색 공격에 대한 해시함수 안전성 강화에 관한 연구, 정은진, 한정훈, 김승주,원동호
성균관대, 정보보호연구소, 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 사이버시큐리티팀 전경화 책임