HASH(해시) 함수
원래 고기, 감자, 야채 등을 잘게 다져서 볶아낸 음식을 해시(Hash)라고 한다.
그중에 감자를 잘게 다져 일정한 사각모양으로 튀겨 먹는 해시브라운(Hash brown)을 떠올려 보자.
해시(Hash) 함수도 이와 유사하다.
해시 함수는 임의의 값(감자)을 넣으면 일정한 크기(사각모양)의 결과 값(해시브라운)이 나온다.
해시 함수에는 MD5, SHA-256, SHA-512 등 종류가 다양하지만, 그중 MD5는 어떠한 입력 값을 넣더라도 MD5 해시 알고리즘을 통해 128비트의 결과 값을 출력한다.
예시 1
input : higgsMD5 ↓
output : 3FD838397804752452BAC4F637BBE6D8
예시 2
input : 동해물과백두산이마르고닳도록하느님이보우하사우리나라만세무궁화삼천리화려강산대한사람대한으로길이보전하세남산위에저소나무철갑을두른듯바람서리불변함은우리기상일세무궁화삼천리화려강산대한사람대한으로길이보전하세MD5 ↓
output : A98DF759C9243759B126FF035BDF4D75
위의 예시를 보면 다른 길이의 입력 값이 들어갔지만 동일한 128비트의 결과 값이 나왔다.
그런데 예시 1은 그렇다고 쳐도, 예시 2는 결과 값은 고작 128비트(=16바이트)인데 100바이트는 족히 넘어 보이는 입력 값으로 나중에 다시 복호화가 가능할까?
당연히 불가능하다.
앞서 말한 해시브라운 얘기를 떠올려보자.
감자를 잘게 쪼개 일정한 사각 틀로 찍어 내면 해시브라운이 나온다. 그렇다고 만들어진 해시브라운으로는 원래의 감자로 되돌릴 순 없다.
해시 함수도 유사하다.
해시 알고리즘의 각 연산들을 통해 입력 값의 데이터는 의미를 잃어가기 시작하고, 결과 값에서는 기존의 입력 값을 찾을 수 없게 된다.
그렇다면 예시 1과 같은 작은 입력 값일 경우는 복호화가 되지 않을까?
이 또한 불가능하다.
하나의 해시브라운을 만들 수도 없는 작은 감자일 경우, 다른 감자를 더해서라도 만들어야 한다.
MD5인 경우 한 블럭이 512비트로 구성되는데, 만약 이보다 작은 입력 값이 들어오게 된다면 첫 비트는 1, 나머지 비트는 0으로 패딩하게 된다. 이를 통해 MD5의 결과 값(128비트)보다 작은 입력 값이라도 해시 알고리즘 연산에 들어갈 블럭 사이즈 512비트가 되었다.
그 이후에 기존과 같이 해시 알고리즘의 각 연산들을 통해 입력 값의 데이터에 의미는 사라지며, 기존의 입력 값을 찾을 수 없는 결과 값이 나온다.
사실 DES, AES, RSA와 같이 양방향 암호방식과 달리 해시 함수는 단방향 암호화 알고리즘이기 때문에 암호화 KEY도 존재하지 않을뿐더러, 일반적으로 해시 함수에 대해서는 복호화 개념이 존재하지 않는다.
과연 복호화가 되지 않는 해시 함수가 과연 어떤 용도로 쓰일까?
알고 보면 패스워드 관리, DB의 해시(Hash) 파티션, 파일의 무결성 체크 등 많은 곳에 사용되고 있다.
대표로 계정의 패스워드 관리에 어떻게 사용되나 알아보자.
계정 생성 시 입력된 패스워드는 해시 함수를 통해 암호화된 값을 서버에 저장하고, 추후 계정 접속 시 입력한 패스워드 또한 해시 함수를 통해 암호화된 값을 서버에 저장된 값과 비교해 일치하면 접속되게 사용한다.
이를 통해, 서버에 저장된 패스워드가 악의적인 공격을 통해 유출이 되더라도 실제 접속하는 패스워드는 알지 못하게 되는 것이다. 서버 관리자도 해시된 패스워드만 가지고 있을 뿐 원래 패스워드는 계정 소유자만 알고 있게 된다.
2000년도 초반의 웹 사이트를 떠올려 보자.
몇몇 사이트에서는 패스워드를 까먹었을 때 비밀번호 찾기를 누르고 아이디, 주민등록번호 등 몇 가지 개인정보만 입력하면 패스워드가 1q2**e4*! 와 같이 출력되었다. 이런 사이트들은 비밀번호를 평문으로 저장하거나, 양방향 암호방식으로 사용하여 원래의 패스워드를 찾을 수 있었다.
하지만 현재는 개인정보관리에 대한 관심과 인식이 높아졌고, 대부분의 웹 사이트에서는 패스워드 관리에 대해 복호화가 되지 않는 해시 함수를 사용한다. 이로 인해 까먹은 패스워드는 본인도 찾을 순 없지만, 그만큼 패스워드 유출에 대한 걱정을 한시름 놓을 수 있게 되었다.
최근에 패스워드를 까먹었을 때를 기억해보자.
이제는 해시 함수 사용으로 인해 원래의 패스워드를 찾을 수 없다. 그래서 버튼이 비밀번호 변경으로 바뀌었거나, 기존 그대로 비밀번호 찾기로 되어있더라도 실제로는 본인인증을 통해 새로운 패스워드를 입력하여 사용해야 한다.
RAINBOW TABLE(레인보우 테이블)
예시 1
input : higgsMD5 ↓
output : 3FD838397804752452BAC4F637BBE6D8
위에 예제를 다시 보자. 일반적인 해시 함수는 암·복호화 KEY가 존재하지 않는다. 그래서 예제와 같이 MD5를 통해 'higgs' 문자의 대해 해시 값은 항상 '3FD838397804752452BAC4F637BBE6D8'로 동일하다.
거꾸로 생각해보면 해시 값이 '3FD838397804752452BAC4F637BBE6D8'이면 원래 입력 값은 'higgs'이지 않을까라는 생각을 할 수 있다. 이를 바탕으로 만들어진 것이 바로 레인보우 테이블(Rainbow Table)이다.
레인보우 테이블은 정해진 범위에서 모든 경우의 해시 값을 한 곳에 저장을 한다.
그리고 만들어진 레인보우 테이블을 가지고, 원래의 값을 구하려는 해시 값과 매핑을 하여 원래의 입력 값을 유추해 낼 수 있다. 이 방법으로 입력 값을 유추하는 것을 복호화라기보다는, 크랙에 가까운 개념이라 볼 수 있다.
하지만 이러한 레인보우 테이블에는 하나의 큰 문제가 존재한다. 그것은 바로 테이블의 크기이다. 모든 경우에 대한 해시 값을 한곳에 넣기에 테이블의 크기가 어마 무시하게 클 수밖에 없다.
단순히 8글자 짜리 소문자+숫자 조합으로 만든 레인보우 테이블의 크기는 328GB. 여기다 아스키코드(대문자+소문자+숫자+특수문자)로 8글자 짜리의 레인보우 테이블은 47,225,249,742TB나 된다. (참조 https://namu.wiki/w/레인보우%20테이블)
요즘 웹 사이트 패스워드 설정이나 보안 취약점 조치 가이드에 보면 패스워드가 대·소문자, 숫자, 특수문자를 포함한 8자리 이상으로 설정하는 게 물론 무작위 대입 공격(Brute Force)을 무력화하지만, 레인보우 테이블도 막기 위함일 것이다.
SALT(솔트)
피치 못할 사정으로 암호 대상(은행 ATM 비밀번호 등)의 길이가 짧고 간단하다면 레인보우 테이블에 취약하다. 또한 대·소문자, 숫자, 특수문자를 포함하여 8자리 이상인 패스워드라 하더라도 같은 패스워드를 사용하는 계정들은 해시 값은 동일할 것이다.
예를 들어, 어느 사이트의 기본 패스워드가 'Guest1234!@'설정되어있다고 가정하자. 패스워드의 규칙은 레인보우 테이블에 취약하지는 않지만, 위에 그림을 딱 봐도 기본 패스워드를 사용하는 계정이 누군지 판별이 가능하다.
이런 것들의 대응방안 중 솔트(Salt)라는 기법이 있다. 말 그대로 해시 대상 문자에 소금을 쳐 해시 대상 값에 대해 복잡도를 높이거나, 같은 입력 값에 대해 다른 해시 값을 주기 위해 사용한다.
이번에는 id의 앞에 2글자, 뒤에 2글자를 솔트로 사용하여 패스워드 앞·뒤에 붙여서 해시를 하였다. 해시 대상 값의 복잡도도 올라갔고, 같은 패스워드임에도 불구하고 해시 값이 각기 다른 것을 볼 수 있다.
실제 사용하는 솔트 방법은 서로 상이하겠지만, 사용 방식과 이유에 대해서는 알아두면 좋을 것이다.