개요
해시 함수(Hash Funtion)란 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환시켜주는 함수이다.
해시 함수의 3가지 조건
-
역상 저항성(Pre-image Resistance)
해시 값을 생성하는 입력값을 찾는 것이 계산상 어려워야한다.
암호화에서 출력문(암호문)을 가지고 원본 메시지를 찾는 것이 어려운 것과 동일한 의미이다.
h(x)=y 일때, y 가지고 x를 유추할 수 없어야한다. -
제2 역상저항성(Second Pre-image Resistance)
입력값이 주어져 있을 때, 이 입력값이 출력하는 해시 값과 같은 해시 값을 출력하는 다른 입력값을 찾는 것이 어려워야한다.
h(x)=y 일때, x와 y를 알고 있는 경우, h(x')=y인 x'를 찾는 것이 어려워야한다. -
충돌 저항성(Collision Resistance)
같은 해시 값을 생성하는 2개의 입력값을 찾기가 어려워야한다.
h(x)=h(x')인 x, x'을 찾는 것이 어려워야한다.
해시 함수의 특징
위의 사진은 안녕하세요, 안녕하세여라는 두 문장을 해시 함수를 거쳤을 때 어떻게 되는지 임의로 보여주는 그림이다. 그림에서 맨 뒤에 한 글자만 바뀌었는데도 해시 함수 출력 값이 완전히 바뀌어 버린다. 즉, 해시 함수는 조금이라도 입력값이 달라지면 해시 함수로 매칭되는 출력 값은 바뀌기 전 값을 유추할 수 없게 된다.
해시 함수의 종류
1. MD4
Rivest가 1990년에 만든 일방향 해시 함수로 128비트의 해시 값을 갖는다.
해시 값의 충돌을 발견하는 방법이 고안되어 현재는 안전하다고 할 수 없다.
2. MD5
MD4의 해시 함수에서 입력을 512bit 블록으로 처리한다.
몇 년전까지만 해도 가장 널리 사용되던 안전한 해시 함수였으나 2005년 이후로 깨지게 되었다.
3. SHA-0(SHA)
1993년에 미국 국가 안보국(NSA)이 설계한 해시 함수이다. 미국 국가 표준으로 지정되었으며 SHA 함수군에 속하는 최초의 함수는 공식적으로 SHA이지만 SHA-0이라고도 불린다. 암호학적으로 보안을 감소시키는 문제점을 고쳐 1995년에 SHA-1로 발전시켰다.
4. SHA-1
SHA-0의 압축 함수에 비트 회전 연산을 추가하였다.
SHA-1 알고리즘은 SHA 함수군 중에서 가장 많이 사용되고 보편화되어있다.
하지만, 2008년에 해시 충돌이 발생했고 점차적으로 지원을 중단하고 있다.
SHA-0와 SHA-1은 최대 2⁶⁴비트의 메시지로부터 160비티의 해시값을 만들어낸다.
5. SHA-2
SHA-1의 4종류의 변형인, SHA-224, SHA-256, SHA-384, SHA-512가 더 발표되었다. 이들을 통칭해서 SHA-2라고 하기도 한다.
2002년에 SHA-1과 함께 정식 표준으로 지정되었다.
SHA-2부터 뒤에 비트 수가 붙는데, 주로 이렇게 다양한 비트들은 암호 연산의 키 길이와 비례한다.
6. SHA-3
SHA-2를 대체하기 위해 2015년 8월에 발표한 암호화 해시 함수이다.
공개적인 방식을 통해 후보를 모집한 다음 함수 안전성을 분석하여 몇 차례에 걸쳐 후보를 걸러내는 방식으로 선정하였다.
SHA-3의 단점
SHA-1과 SHA-2에는 동일한 수학적 결함이 있고 SHA-3에는 그 결함이 없다는 것을 알면서도 SHA-3이 아닌 SHA-2가 보편화되어 있다.그 이유는 SHA-3을 사용하면 암호 알고리즘이 복잡하기에 속도 문제가 가장 크다.
소프트웨어에서 SHA-3는 SHA-1에 비해 3배 느리며 SHA-512는 2배 느리다.이로 인해 SHA-2에서 SHA-3로 전환하는 소프트웨어, 하드웨어가 사실상 전무하다.
다만, 이를 극복해 몇 년 내에 SHA-3 전환을 실시하게 될 것임은 확실하다.
대표 공격 방법
1. 생일 역설 공격(Birthday Attack)
생일 역설이란?
사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 경우의 수는 366개 이므로 367명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존대하며 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 50%을 넘는다.
즉, 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%을 넘고, 57명이 모이면 99%을 넘어간다.
반대로 생각하면, 이 문제는 무작위로 만난 367명의 생일이 서로 겹치지 않고 고르게 분포할 확률이 매우 극히 낮다는 점을 나타낸다.
생일 역설 공격
생일 역설을 통해 모수가 크지 않더라도 해시 함수의 주어진 출력으로부터 입력을 찾아내는 것이 가능함을 알 수 있다.
해시 함수의 충돌쌍 발견 사례
- 2004년 8월 : MD5를 포함한 다양한 해시 함수에서 충돌쌍 발견
- 2004년 8월 : SHA-0의 충돌쌍 발견
- 2005년 2월 : SHA-1의 충돌쌍 발견
- 2008년 : TLS(Transport Layer Security)에서 사용되는 인증서 내 사용된 MD5 충돌쌍 발견
- 2017년 2월 : CWI+구글 SHA-1의 PDF형식의 충돌쌍 발표
충돌쌍이 발견된 해시 함수(MD5, SHA-0, SHA-1 등) 선택을 피하고 SHA-256이나 SHA-3와 같은 최신 해시 함수의 선택을 하여 안전하게 데이터를 보호할 수 있다.
2. 중간자 공격
두 사람이 서로 통신을 주고 받는데, 중간에 제3의 인물이 끼어서 데이터를 중계한다면, 이 제3자는 그 내용을 모두 알 수 있고, 데이터를 위/변조할 경우 두 사람에게 서로 잘몬된 정보를 전달하게 만들 수도 있다.
- 지나가는 패킹을 모두 감청하여 ID/패스워드/공인인증서 등 중요 개인 정보를 훔쳐볼 수 있다.
- DNS 정보 등을 위조하여 피싱 사이트로 연결되도록 속일 수 있다.
- 암호 키 교환에 개입하여 암호화에 사용되는 키를 뺴낼 수 있다.
중간자 공격은 해시 함수 자체의 취약점이라기보다 안전하지 않은 전송 과정을 악용한다.
데이터를 암호화하지 않거나 전송 과정에서 보안 채널을 사용하지 않을 경우 해시 값이 변조될 수 있다.
대응 방법
데이터 전송 시 HTTPS와 같은 보안 채널 사용
메시지 인증 코드(MAC)와 같은 해시 기반 인증 기법 추가
비대칭 암호화를 통해 디지털 서명 보완중간자 동격은 보안 채널을 확보하고 해시 값만으로 검증하지 않도록 추가 인증 절차를 도입해야 방어할 수 있다.
공격 사례
1. Flame 악성코드
2012년 Flame 악성코드가 MD5의 충돌 취약점을 악용하여 마이크로소프트의 디지털 서명을 위조했다.
공격자들은 MD5 해시를 사용한 인증서에 충돌을 생성해 악성 코드가 신뢰할 수 있는 소프트웨어로 인식되도록 만들었다.
2. SHA-1 충돌 공격
2017년 구글과 CWI 암스테르담 연구소가 평소 이론적으로만 인지해온 충돌 가능성을 기반으로 실제 충돌을 생성해냈다.
연구에서는 두 개의 다른 PDF 문서가 동일한 SHA-1 해시 값을 가지도록 설계하였다. 이로 인해 동일한 해시를 가진 위조 문서가 원본 문서처럼 보이도록 위장할 수 있었다.
3. Superfish 사건(중간자 공격)
2015년 레노버가 배포한 일부 노트북에 Superfish라는 광고 소프트웨어가 중간자 공격을 시도하였다.
Superfish는 자체 인증서를 사용해 TLS 연경을 가로채고, 클라이언트와 서버 간 데이터 전송을 변경하거나 감시할 수 있었다.
공격자가 Superfish를 이용하면 TLS 통신 중 해시 값 검증 과정에 개입하여 데이터를 위조하거나 사용자 세션을 탈취할 수 있었다.
