-
네트워크 보안 - 5 | 해시 함수컴퓨터 공학/보안 2022. 10. 10. 22:17
해시함수
해시함수 또는 해시 알고리즘이라고 불리는 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 변환해 주는 함수이다. 보통 자료구조에서 해시 테이블이라는 용도로 사용되며, 이를 이용해 빠른 데이터 검색을 구현할 수 있다.
이러한 해시함수를 암호로도 사용할 수 있는데, 암호로 사용할 수 있는 해시함수를 암호학적 해시 함수라고 한다. 이때 암호학적 해시함수는 특정 조건을 만족해야 하는데, 이 조건은 다음과 같다.
- 압축: 입력의 크기와 상관없이 출력의 길이는 항상 작아야 한다. 이때 출력의 크기는 고정되어 있다.
- 효율성: 입력에 상관없이 해시 함수를 계산하기 쉬워야 한다. 입력의 크기가 커질수록 계산 시간이 증가하는 것은 당연하지만, 너무 빨리 증가해서는 안된다.
- 단방향: 이미 계산된 해시 값을 가지고, 어떤 입력을 이용해 해당 출력을 만들었는지 계산하기 어려워야 한다.
- 약한충돌방지: 임의의 입력과 이에 해당하는 출력이 있을 때, 이와 같은 출력을 만들어내는 다른 입력값을 찾기 어려워야 한다.
- 강한충돌방지: 같은 출력을 만들어내는 임의의 두 입력값을 찾기 어려워야 한다.
※ 강한충돌방지의 경우 공격자가 두 가지 입력값을, 약한충돌방지의 경우 공격자가 한 가지 입력값을 마음대로 제어하여 성질을 깨뜨리려는 공격에 대한 저항성이다. 이때 강한충돌방지가 깨질 가능성이 더 높고, 따라서 강한 충돌 저항성이 큰 해시 함수일수록 보안적으로 더 안전하다고 할 수 있다.
이를 간단하게 설명하자면 다음과 같다.
해시함수는 입력값의 크기에 상관없이 동일한 크기의 출력을 만들어내는데, 이때 입력과 출력에는 아무런 연관성이 없어야 한다. 입력에 아주 사소한 변화가 생기더라도 출력 값은 절반 이상이 완전히 변하기 때문에, 공격자는 이 둘의 연관성을 추측하여 출력 값으로부터 입력값을 알아낼 수 없어야 한다. 동시에 암호학적 해시 함수는 어떠한 데이터를 특정할 수 있는 역할을 해야 하기 때문에 다른 입력값으로 같은 출력을 만들어내는 상황이 거의 없어야 한다.
물론 입력 공간이 출력 공간보다 훨씬 크기 때문에 충돌은 불가피하다. 하지만 그럼에도 충돌 방지를 최대한 만족할 수 있는 해시함수는 존재할 수 있고, 이를 사용하여 보안적인 기능을 구현할 수 있다.
그렇다면 이러한 특성들을 만족하는 해시 함수를 사용하는 이유는 뭘까?
지금까지 대칭키 암호체계와 공개키 암호체계를 공부하면서, 특정 데이터를 암호화하거나 서명하는 등의 대부분의 기능은 모두 이 두 암호체계로 구현이 가능했다. 하지만 그럼에도 해시함수라는 방식을 사용하는 이유는 바로 효율성 때문이다.
해시함수의 효율성
암호학적 해시함수로 사용되기 위한 조건에는 효율성이 있다. 해시함수는 기본적으로 계산의 속도가 매우 빠른 것이 특징이다. 따라서 기존의 암호체계로도 충분히 구현이 가능한 부분들도 해시를 이용하게 되면 그 효율이 매우 좋아질 수 있다. 예를 들어 공개키 암호체계를 이용해서 전자서명을 한다고 하자.
기존의 서명의 경우 메시지 M을 개인키로 서명한다. 이를 S=[M]라고 표현하자. (개인키 연산; 복호화)
그리고 이 서명은 공개키로 확인할 수 있다. 이를 M={S}라고 표현하자. (공개키 연산; 암호화)
이때 M이 클수록 [M]을 계산하는데 시간이 오래 걸린다. 따라서 M을 서명하는 것이 아니라, M을 해시함수에 넣어 나온 결과값인 h(M)을 서명한다. 그리고 서명을 확인할 사람에게는 M과 S=[h(M)]을 함께 전송하는 것이다.
이후 이를 확인한 사람은 {S}=h(M)인지를 확인하여, 해당 서명이 유효한지를 확인할 것이다.
이러한 방식을 사용하는 이유는 M의 크기가 어떻든 간에 해시된 값인 h(M)은 고정된 크기를 가지고 있기 때문이다. 따라서 전체 파일 M대신 작은 크기의 h(M)에 개인키 연산을 적용하는 것이 더 유리하기 때문이다. 이런 효율성은 M의 크기가 커지면 커질수록 더욱 증가한다.
해시 충돌 계산
해시 함수는 큰 입력값을 고정된 작은 출력 값으로 변환하기 때문에 충돌이 필연적으로 생길 수밖에 없다. 이때 충돌이 일어날 가능성을 수학적으로 어떻게 계산할 수 있을까?
이는 생일 문제라 불리는 간단한 문제를 이용해 알아볼 수 있다.
앨리스가 방안에 N명의 사람과 함께 있다고 가정하자. 이때 앨리스와 생일이 같은 사람이 있을 확률이 50% 이상이려면, N은 얼마나 커야 할까?
모든 생일이 확률이 같다고 가정하면, 임의로 선정된 사람이 앨리스와 생일이 같지 않을 확률은 $364 \over 365$이다. 그러면 N명의 사람이 앨리스와 생일이 같이 않을 확률은 $\left( 364 \over 365 \right)^{N}$이다. 따라서 적어도 한 사람 이상이 앨리스와 생일이 같을 확률은 $1 - \left( 364 \over 365 \right)^{N}$이다. 이 값이 0.5 이상이 되려면 N은 253의 값을 가지게 된다.
그렇다면 같은 조건에서 방안의 사람들 중 두 사람 이상의 생일이 같을 확률이 50% 이상이려면, N은 얼마나 커야 할까? 이번에는 앨리스라는 특정 인물의 생일과 같을 필요가 없다.
먼저 생일이 같지 않을 확률을 계산해 보면 다음과 같다.
만약 N이 2라면, ${{365} \over {365}} \times {{364} \over {365}} = 99.72\%$
만약 N이 3이라면, ${365 \over 365} \times {364 \over 365} \times {363 \over 365} = 99.17\%$
이러한 방법으로 식을 세우면, ${365\over365}\times{364\over365}\times...\times{(365-N+1)\over365}$이다.
따라서 생일이 서로 같을 확률은 $1-{365\over365}\times{364\over365}\times...\times{(365-N+1)\over365}$이다.
그리고 이 확률이 50% 이상이 되기 위해서는 N이 23이면 된다.
여기서 해시함수의 입력값을 사람이라 생각하고, 이로 인한 출력을 생일이라 생각한다면, 서로 다른 사람끼리 생일이 겹치는 것을 충돌이라 볼 수 있을 것이다.
이때 앨리스와 생일이 같을 확률을 구하는 것이 약한충돌방지에 대한 내용이고, 서로 다른 두 사람의 생일이 같을 확률을 구하는 것이 강한충돌방지에 대한 내용이다.
따라서 공격자가 하나의 출력 값과 같은 출력을 내는 입력값을 찾기 위해서는 N이 253이었던 것처럼 큰 노력이 필요하다. 하지만 같은 출력을 내는 서로 다른 두 개의 입력값을 찾기 위해서는 N이 23이었던 것처럼 훨씬 적은 노력이 필요하다.
이때 해시함수가 N비트 길이의 출력을 생성한다고 가정한다면, 이 해시를 해독하기 위해서는 거의 $2^{0.5N}$의 노력이 필요하다. 키의 길이가 N인 대칭키 암호의 경우 해독을 위해 $2^{N-1}$의 노력이 필요한 것을 보았을 때, 해시함수가 대칭키 암호와 같은 수준의 보안성을 유지하기 위해서는 거의 두 배의 비트가 필요하다는 것을 알 수 있다.
HMAC
이전에 블록 암호 방식에 대해 알아보면서, 블록 암호의 모드 중 하나인 CBC모드를 사용하면 메시지 인증 코드인 MAC을 사용할 수 있다고 하였다. 이 MAC을 이용하면 중간에 메시지가 변조되더라도 변조된 사실을 알아챌 수 있게 해 주므로, 무결성을 보장해 주는 장치라 할 수 있다.
이러한 MAC을 이번에 알아본 해시 함수를 이용해 구현하는 방식이 바로 HMAC이다. 해시 함수에 들어간 원본 메시지가 조금이라도 변하면 그 결과 해시값은 완전히 다르게 변해버리기 때문에 메시지의 변조 여부를 확인할 수 있는 방식이다.
중요한 것은 메시지 M의 무결성을 위해 해시한 값인 h(M)을 함께 보낸다고 가정하자. 이러한 경우 공격자가 M은 M'로 바꾸고, h(M)은 h(M')로 바꿔버릴 수 있다. 즉, 해시가 무결성을 전혀 보장해주지 못한다.
따라서 이러한 문제를 방지하기 위해 대칭키를 사용해 해시가 이 대칭키에 종속되도록 한다. 메시지를 주고받을 양쪽이 서로 대칭키 K를 공유하고, 해시를 할 때 항상 이 대칭키 K를 함께 이용하여 h(M, K)와 같은 식으로 함께 해시하는 것이다. 그렇다면 중간에 공격자가 원본 메시지를 변경하더라도, 해시값을 그에 맞게 올바르게 변경하지는 못한다. 대칭키 K를 모르기 때문이다.
이를 간단한 예를 통해 알아보면 다음과 같다. 앨리스와 밥이 서로 메시지 M을 주고받으려 한다. 이때 메시지의 비밀성은 고려하지 않지만, 무결성은 보장받고자 하는 상황이라고 가정하자.
- 앨리스와 밥이 대칭키 K를 서로 공유한다. (디피-헬먼 키교환 알고리즘, RSA 등을 사용)
- 앨리스가 메시지 M과 h(M, K)를 함께 밥에게 전송한다.
- 밥은 받은 메시지 M을 자신이 가지고 있던 대칭키와 함께 해시하여 h(M, K)를 만들고, 이를 함께 온 h(M, K)와 비교한다.
- 만약 비교한 값이 동일하다면, 원본 메시지가 변조되지 않았음을 신뢰할 수 있다.
실제 HMAC
위의 예시는 HMAC의 기본적인 개념에 대해 알아보기 위해 간단히 설명한 것이고, 실제 사용하는 HMAC은 훨씬 더 복잡하다고 한다.
다음은 실제 HMAC의 구현을 명세하고 있는 RFC 2104의 내용이다.
RFC 2104: HMAC: Keyed-Hashing for Message Authentication
www.rfc-editor.org
해당 내용을 정말 간단하게 식으로 나타내면 다음과 같다.
$$ HMAC(M,K) = H(K \oplus opad, H(K \oplus ipad, M)) $$
여기서 ipad와 opad는 각각 0x36(0011 0110)과 0x5C(0101 1100)가 해시의 바이트 단위 블록 길이만큼 반복하는 형태이다. 무슨 이유로 대칭키 K를 ipad와 opad와 XOR연산하면서, 두 번씩이나 해시를 하는지는 모르겠지만, 아마 그게 더 보안에 도움이 되어서 그렇지 않을까 싶다.
해시함수의 용도
해시함수는 전자서명의 효율성, HMAC을 이용한 메시지 무결성 확인, 데이터 변형 탐지 등에 사용될 수 있다. 이외에도 보안적인 문제를 해결하기 위해 해시함수를 사용하는 경우가 많다. 다음은 보안적으로 사용할 수 있는 해시함수의 간단한 예시 세 가지를 알아보도록 하겠다.
비밀번호 저장
우리가 어떤 사용자 계정을 만들고 이를 개인적으로 사용하기 위해 비밀번호를 설정하는 경우, 해당 시스템에서는 다음에 사용자가 비밀번호를 입력했을 때, 그 비밀번호가 올바른 것인지 확인하기 위해 원본 비밀번호를 반드시 기억하고 있어야 한다. 즉, 해당 시스템이 관리하고 있는 파일 어딘가에는 사용자의 비밀번호가 그대로 노출되어 있다는 뜻이다.
따라서 반드시 사용자의 비밀번호를 암호화해서 저장할 필요가 있다. 그리고 이때 해시함수를 사용할 수 있다.
해시함수로 비밀번호를 한번 해시해 버리면 다시는 원본 비밀번호를 알아낼 수가 없는데, 그럼 어떻게 사용자 인증을 하냐고 물을 수도 있다. 하지만 사용자가 입력한 비밀번호를 다시 해시해서 저장된 해시값과 비교하는 방식으로 인증을 하면 아무런 문제가 없다. 서로 완전히 같은 값을 해시하는 경우에는 동일한 해시 값이 결과로 나오기 때문이다.
실제로 웹사이트들 대부분에서 비밀번호를 잊은 경우, 본인 인증을 통해 원래 비밀번호를 알려주는 방식이 아닌, 새로운 비밀번호로 변경하게끔 한다. 이는 그 웹서버의 데이터베이스에 실제 비밀번호가 저장되어 있지 않기 때문에, 원래 비밀번호를 애초에 알려줄 수 없는 경우일 가능성이 크다.
온라인 입찰
해시함수는 온라인 경매에서도 사용할 수 있다. 이 경매가 서로의 입찰 가격을 비밀로 하는 방식으로 이루어진다고 했을 때, 온라인 입찰에 참여하는 사람들은 자신이 제출한 입찰 가격을 상대가 알지 못한다는 것을 믿어야만 한다. 만약 다른 상대가 자신의 입찰 가격을 안다면, 해당 가격에서 아주 살짝만 올린 가격으로 물건을 살 수도 있기 때문이다.
따라서 온라인 경매를 주관하는 경매 사이트에서는 입찰 금액을 해시한 값을 먼저 받는 방식을 사용하기로 한다. 해시된 값은 실제 금액과는 아무런 연관이 없기 때문에 이를 가지고는 누군가가 장난을 치기 힘들다. 그리고 이후 모든 입찰 금액이 제출된 다음에, 참가자들은 실제 자신이 제출한 가격을 모두에게 공개한다.
이후 가장 높은 가격을 제시한 사람이 입찰을 받는다. 만약 해당 경매에 참여한 누군가가 이 사람이 중간에 가격을 바꾼 것을 의심한다고 해도, 미리 제출한 해시값과 나중에 보여준 금액을 해시한 값을 비교한다면 이러한 의심에서 벗어날 수 있을 것이다.
스팸 줄이기
인터넷이 발전하고 전자우편 서비스가 대중화되면서 스팸이라고 불리는 원하지 않은 대량의 전자 우편물이 널리 퍼지게 되었다. 이때 이러한 스팸을 줄이기 위한 방법으로도 해시함수가 사용될 수 있다.
전자우편에서 스팸이 많이 발생하는 이유는, 실제 전자우편을 보내는 데에 드는 비용이 아주 적기 때문이다. 사실상 컴퓨터와 전기만 있으면 무한으로 가능한 작업이다. 따라서 스팸을 줄이기 위해서는 우편을 보낼 때 약간의 비용을 부과하면 된다.
이때 여기서 말하는 비용이란 실제 돈이라기보다는 컴퓨터 자원을 의미한다. 일반적으로 전자우편을 송수신하는 데에는 크게 복잡한 계산이 필요한 이유가 없다. 하지만 굳이 복잡한 계산을 추가하는 것이다.
일반적인 사용자의 경우 전자우편을 하나씩 보내는 편이기 때문에 큰 문제가 되지 않는다. 하지만 프로그램을 이용해 계속해서 스팸을 발송하는 사용자의 입장에서는 이러한 계산에 들어가는 시간이 점점 쌓여 큰 부담이 될 것이다.
그렇다면 어떻게 해시함수를 이용해 컴퓨터가 계산을 하는 시간을 들이게끔 할 수 있을까?
전자우편 메시지를 M이라 하고, T를 현재 시간이라 하자. 이때 메시지 M의 송신자는 다음의 R을 구해야 한다.
$$ h(M,R,T)=(0 \times N, X) $$
즉, 메시지 M과 현재 시간 T와 미지수 R을 함께 해시했을 때 나오는 값의 처음이, 0이 N번 반복되는 모양이어야 한다는 것이다.
예를 들어 N을 10으로 설정한다면, 000000000099871613.... 와 같은 값이 나오게 하는 R을 찾아야 한다는 것이다.
이전에도 설명했지만 해시함수의 특성상 어떠한 결과를 가지고 역으로 어떤 값을 해시하였는지 찾는 것은 매우 어려운 일이다. 따라서 N의 크기가 커져 0으로 시작하는 길이가 길어질수록 R값을 찾기가 어려워질 것이다.
이러한 방식으로 적절한 N을 선택한다면, 일반적인 이용자에게는 잠시 참을 수 있는 시간이지만, 스팸 발송자에게는 이 시간이 모이고 모여서 스팸을 보내는 것이 오히려 불리하게 작용하게끔 만들 수 있다.