Home

해쉬함수는 임의의 길이를 갖는 메시지를 입력으로 하여 고정 길이의 해쉬값을 생성하는 함수이다. 웹사이트에서는 패스워드를 해쉬함수에 입력하여 생성한 해쉬값을 데이터베이스에 저장한다. 사용자가 접속 시에 입력한 패스워드에서 생성한 해쉬값과 기존 데이터베이스에 저장되어 있는 해쉬값을 비교하여 같으면 로그인 할 수 있고, 다르면 로그인이 거부되는 방식으로 사용한다. 해쉬함수의 요구사항은 일방향 함수와 강한 충돌회피이다. 컴퓨터의 성능 향상과 더불어 MD5와 SHA-1은 충돌이 발견되어 사용을 권고하지 않는 함수가 되었다.

중국의 Wang 교수와 그 동료들은 MD5의 충돌을 발견하였으며[3], 구글 연구팀은 SHA-1의 충돌을 발견하였다[4]. SHA-1은 1993년 NIST에 의해 안전한 표준 해쉬함수로 지정되어 사용되었으나 컴퓨터 성능의 발전에 따라 더 이상 안전하지 않은 해쉬함수가 되었다. 해쉬함수의 무차별공격은 복호화 하려는 해쉬값을 미리 계산하여 두고, 가능성 있는 메시지들에 대하여 생성된 해쉬값과 복호화하고 싶은 해쉬값이 일치하면 메시지를 찾아내는 것이다. 다른 해쉬함수에 비해 월등히 빠른 계산속도로 인하여 널리 사용되고 있는 MD5의 해쉬값에 대하여, php.net은 무차별 공격으로 쉽게 복호화될 수 있다고 경고하였다[6].

LAUGHFOOL's LAB에서는 MD5 CrackFAST 툴을 이용하여 무차별 공격으로 MD5 복호화 시험을 수행하였다[7]. 패스워드가 알파벳 대문자와 소문자 그리고 숫자의 조합이라 가정하면 n자리 패스워드의 경우에 가능한 패스워드의 수는 62의 n제곱이 된다. 5자리 패스워드의 경우에 가능한 패스워드의 수는 916,132,832(=62⁵) 이다. 가정용 PC(i5 2.67GHz CPU, Thread count 3)를 이용하여 5자리 부터 12자리의 패스워드를 찾는데 걸린 시간을 측정하였다. 5자리 패스워드의 복호화 시간은 6.287초이며, 11자리의 복호화에는 약 360,140일이 소요되었다.

Securityledger사에서는 25개의 virtual AMD GPU 스펙으로 초당 1800억개의 MD5 해쉬값을 생성할 수 있는 패스워드 크래킹 PC를 소개하였다[8]. Securityledger사의 크래킹 PC는 가정용 PC에서 동작하는 MD5 CrackFast 툴에 비하여 약 2400배 빠르게 해쉬값을 생성할 수 있는 성능이다.

그림 1은 Statista에서 조사한 2017년 유출된 전세계 사용자 패스워드의 평균 글자 수를 나타낸다. 자료에 의하면 유출된 약 3억 2천만개의 패스워드 중 가장 많이 사용된 것은 7~8자리 패스워드들 이었다[9]. 10자리 패스워드의 MD5 해쉬값은 Securityledger사의 크래킹 PC에 의해 약 2.5일만에 크래킹되며, 가장 많이 사용되는 8자리의 경우는 1분도 안되어 크래킹 될 수 있다.

Fig. 1. 
Average number of characters in leaked user passwords worldwide in 2017

그러나 11자리의 경우에 150일 이상 소요되어 무차별 공격을 통한 크래킹이 쉽지 않다는 것을 알 수 있다. 길이가 길수록 패스워드가 안전할 수 있지만 편리함 때문에 실제로는 7~10자리의 패스워드를 대부분 사용하고 있다.

솔트는 그림 2와 같이 패스워드의 앞이나 뒤에 추가되어 패스워드 해쉬값을 생성하는데 사용된다[10].솔트를 사용하면 해쉬함수의 입력 메시지가 길어져 더 많은 크래킹 시간이 요구되므로 패스워드를 보다 안전하게 보호할 수 있는 방법이다. Pritesh[5]는 솔트를 사용한 패스워드는 사전공격을 줄일 수 있고, 크래킹이 어려울 뿐 아니라 SQL Injection 공격까지 막을 수 있음을 보이고 있다. 그러나 Pritesh에서 제시한 솔트는 데이터베이스의 회원테이블에 하나의 컬럼으로 저장된다.

Fig. 2. 
Generation of password hash value using Salt

사용자가 접속 시에 입력한 패스워드에 솔트 컬럼의 값을 추가하고 해쉬함수에 입력하여 생성한 해쉬값과 데이터베이스에 저장되어 있던 패스워드 해쉬값과의 일치여부로 로그인 성공과 실패를 판정한다. 솔트는 사용자마다 랜덤하게 생성되더라도, 생성된 후에는 특정 값으로 고정되어 데이터베이스의 솔트 컬럼에 저장된다. 따라서 데이터베이스가 해킹되는 경우에 공격자는 각 사용자 별로 부여된 솔트를 쉽게 파악하여 패스워드 크래킹에 이용하게 된다. 솔트는 대부분 패스워드의 앞이나 뒤에 붙여 사용되므로, 공격자 입장에서는 솔트를 단순히 패스워드 앞 또는 뒤에 붙이는 경우에 비하여 무차별 공격 회수가 2배 정도 늘어나는 것에 불과하다.

삼성전자의 특허에서 제시한 솔트는 입력된 패스워드에 솔트를 부가하여 조합 패스워드를 생성하고 인증정보를 생성한다. 또한 난수발생기로부터 생성된 솔트를 데이터베이스에 저장하고 인증 시 입력된 패스워드와 함께 조합하여 인증한다[11]. 삼성전자의 특허로 제시된 방법도 솔트가 고정값으로 저장되므로, 솔트가 노출되면 크래킹에 취약한 문제점이 있다.

데이터베이스에 저장된 해쉬값의 변화를 일으키기 위하여 국내·외 개인정보보호 정책은 정기적으로 사용자에게 패스워드 변경을 요구하고 있다[13]. 하지만 2016년과 2017년 영국 NCSC와 미국 NIST 에 따르면 정기적인 변경요구가 외우기 쉬운 단순한 패스워드를 사용하게 만들어 오히려 해킹에 취약하다는 결론을 내렸다[14][5]. 이에 NIST는 새로 공표한 2019년의 패스워드 가이드라인에서 정기적인 패스워드 변경 요구항목을 삭제하였다[16]. KISA또한 2019년 개정된 패스워드 선택 및 이용 안내서에 해당 내용을 제외시켰다[17].

국내·외 개인정보보호 정책에 따라 웹사이트의 개인정보 처리자는 방문자의 접속기록 (IP 주소, 접속날짜, 브라우저, OS 종류 등)을 반드시 데이터베이스에 저장하여야 한다[1][18]. 로그인 시에 변경되는 접속 기록들을 솔트로 사용하면 개인정보보호 정책도 따르면서, One-Time Pad[12]의 완벽한 랜덤까지는 아니더라도 패스워드 해쉬값을 자주 바꿀 수 있게 된다. 즉, 접속로그 기반의 솔트(Access log-based Salt)는 로그인할 때마다 패스워드 해쉬값이 변경되므로 데이터베이스 관리자나 공격자 입장에서는 사용자가 패스워드를 자주 변경하는 것과 동일한 효과를 보이게 된다.

이처럼 접속기록 기반의 솔트를 사용하게 되면 데이터베이스가 유출되더라도 Salt라는 컬럼이 별도로 존재하지 않으므로 공격자에게 솔트의 존재 및 사용여부를 감출 수 있게 된다. 또한, 공격자가 패스워드 크래킹 중에 사용자가 로그인을 하면 패스워드 해쉬값이 바뀌게 되어 크래킹을 새로 시도해야하므로, 패스워드의 보안 레벨이 매우 높게 안정적으로 유지될 수 있게 된다.

접속로그 기반의 솔트는 소스코드가 공격자에 노출되는 경우에 솔트로 사용하는 접속기록도 노출된다. 이 경우에 공격자는 솔트로 사용된 접속기록을 이용하여 패스워드 해쉬값을 크래킹하게 된다. 데이터베이스와 소스코드가 노출되더라도 사용된 솔트들이 무엇인지 파악하기 어렵게 만들어 패스워드 해쉬값을 더 안전하게 보호할 수 있는 방안이 요구된다. 패스워드 별 동적솔트(Dynamic Salt according to password)는 사용자가 입력한 패스워드를 숫자화하여 N개의 접속기록들 중에서 r개를 솔트로 선택하여 패스워드 해쉬값을 생성하는 방식이다. 이러한 패스워드 별 동적솔트는 데이터베이스와 소스코드가 노출되더라도 사용자마다 서로 다른 r개의 솔트를 사용하므로 패스워드 해쉬값을 보다 안전하게 보호할 수 있다.

그림 3은 접속기록 N개를 전부 솔트로 사용하는 경우에 패스워드와 접속기록의 전체 조합을 나타낸다. 패스워드를 포함하여 N개의 접속기록을 모두 사용하는 경우에 가능한 조합의 수는 (N+1)의 계승 개수가 된다. 그림에서 각 조합의 왼쪽에 있는 x는 패스워드를 숫자화 하여 (N+1)!로 모듈러 연산을 수행한 결과이다.

Fig. 3. 
Combination of password and N Salts

그림 4는 N개의 접속기록을 모두 솔트로 사용하는 경우에 대한 패스워드 별 동적솔트 방식의 로그인 인증절차를 나타낸다. 웹사이트와 같은 서버는 사용자로부터 수신한 패스워드를 숫자화한 후, (N+1)!로 모듈러 연산을 수행한다. 연산의 결과로 x번째 솔트조합을 선택하여 패스워드 해쉬값을 생성하며, 이 해쉬값을 DB에 저장되어 있는 인증용 패스워드 해쉬값과 비교한다. 두 해쉬값이 일치하면 x번째 조합의 새로운 접속로그 기록으로 다음 로그인 인증에 사용할 패스워드 해쉬값을 생성하여 데이터베이스에 저장하며, 로그인 성공을 반환한다.

Fig. 4. 
Login authentication procedure of dynamic Salt by password

패스워드 별 동적솔트 방식에서 공격자가 솔트조합을 얻기 위해서는 사용자가 입력한 패스워드를 숫자화한 후 모듈러 연산을 수행하여야 한다. 접속로그 기반 솔트와 다르게 패스워드 별 동적솔트 방식에서는 소스코드가 노출되더라도 공격자는 사용자의 패스워드를 알 수 없으므로 어떤 솔트조합을 사용하여 패스워드 해쉬값을 생성하였는지 쉽게 알 수 없다. 해쉬값이 바뀌지 않더라도 공격자는 소스코드에 나타나는 모든 경우의 솔트조합을 이용하여 패스워드 해쉬값을 크래킹하여야 한다. N개의 접속기록을 모두 솔트로 사용하는 경우라면 패스워드와 솔트를 포함한 전체 경우의 조합 수는 (N+1)! 이므로 평균 (N+1)! /2번의 크래킹이 요구된다.

접속기록 뿐만 아니라 사용자의 아이디, 이메일주소, 생일과 같은 고정값을 솔트로 같이 사용하면 조합의 수가 증가하고 해쉬함수의 입력도 길어져 보안이 더욱 강화된 패스워드 해쉬값을 생성할 수 있다. 고정값들이 솔트조합에 포함되더라도 접속기록과 같이 로그인할 때마다 변하는 가변값들이 솔트조합에 섞여 있으므로 동적솔트의 장점은 유지하면서 패스워드 해쉬값의 보안 레벨을 매우 높게 그리고 안정적으로 유지할 수 있게 된다.