배우면서 쓰는 암호학
- Hash -
먼저, hash 함수는 암호학에 관심이 없는 사람이라도 들어봤을 만큼 여러 분야에서 쓰이는 용어이다. 암호 화폐나 자료 구조에서도 hash 함수가 등장하게 된다.
암호학 내부에서 사용하는 hash 는 이를 구분하기 위해
암호학적 해시 함수 라는 말을 사용한다. 그렇다면 hash 함수는 도대체 무엇일까??
- hash 함수는 임의의 크기의 데이터를 입력받아 고정된 크기의 데이터로 변환해주는 함수를 말한다.
이해를 돕기 위해 사진을 첨부했다.
사진에서 볼 수 있듯이, 다양한 크기의 Input 이 들어가도, 크기와는 관계없이 항상 일정한 크기의 Output 이 나오게 된다.
- Cryptographic Hash Function -
그렇다면, 암호학적 해시 함수는 기존의 해시 함수와 비교되는 부분이 무엇일까?? 암호학적 해시 함수는 마치 암호화 체계와 매우 유사하다.
다음 사진과 같이, 암호화 ( hash ) 과정이 이루어진다.
이런 암호학적 해시 함수는 다음 3가지 조건을 만족해야 한다.
- 제 1 역상 저항성
- 제 2 역상 저항성
- 충돌 저항성
그럼, 각각의 성질에 대해서 알아보도록 하자.
제 1 역상 저항성
-
암호학적 해시 함수 H 에 대해서, H(x) = y 라고 할 때, 주어진 y 값에 대하여 x 값을 알아내는 것은 어렵다.
-
일방향 함수임을 의미한다.
제 2 역상 저항성
- 암호학적 해시 함수 H 에 대해서, 어떤 x 가 주어졌을 때, x와 다른 H(x) = H(x') 을 만족하는 x' 을 알아내는 것은 어렵다.
충돌 저항성
- 암호학적 해시 함수 H 에 대해서, x 와 다른 x' 에 대해서 H(x) = H(x') 인 x, x' 을 알아내는 것은 어렵다.
현대에는 새로운 특징이 추가되었는데, 바로 눈사태 효과 ( Avalanche Effect ) 이다.
Avalanche Effect
- 현대 암호의 '확산' 성질과 동일.
- 기존의 평문에서 하나의 값만 조작되어도 암호문의 값은 크게 바뀐다.
- Birthday Paradox -
Q . 한 반에 30명의 학생이 있다. 이들 중에서 생일이 같은 학생이 있을 확률은 얼마일까?
A. 2.7% B. 11.7% C. 24.6% D. 40.6% E. 70.6%
한번 계산을 하지 말고 직관적으로 답을 구해보자.
정답은????
.
.
.
.
.
E 이다!!
보통 사람들은 365일 중에서 생일이 겹칠 확률은 매우 낮을 것이라고 생각하기 마련이다. 필자도 이 역설을 처음 접했을 때, C 보기가 정답이라고 생각했다.
하지만, 직접 계산해보면 정답은 E 임을 실감할 수 있었다.
이 문제를 hash function 에 빗대어 생각해보면, 공역이 365 인 hash 함수에서 임의로 30 개의 hash 값을 생성했을 때, 겹칠 확률이 70% 라고 생각할 수 있을 것이다.
조금 더 일반화해서 계산해본 결과, 공역의 개수가 n 개인 hash 함수에서 임의로 √n 개의 hash값을 생성하면 겹칠 확률이 늘어남을 알 수 있다.
따라서, 결국 n ( hash 함수의 공역 ) 의 크기가 매우 크지 않다면 해시 함수의 충돌 저항성을 만족하지 않음을 얻어낼 수 있겠다.
- used -
data 송신, 수신
암호학적 해시 함수는 송수신에 많이 사용된다.
해시 함수는 일방향 함수임과 더불어 충돌 저항성을 지니고 있다. 이 성질을 이용해서 송 수신에 hash 함수를 사용하곤 한다.
우리가 데이터를 송신, 수신할 때, 보통 무결성 ( Integrity ) 검사를 한다. 이는 송신, 수신 시에 데이터의 누락 가능성이 있어 이를 보완해주기 위한 과정이다.
이렇게, 데이터와 해시 값을 이용해서 비교함으로써 무결성을 확인한다.
송, 수신 과정에서의 hash 는 위의 사진과는 살짝 다르지만 근본을 같다.
- 데이터를 송신할 때 데이터와 데이터를 hash 함수를 이용해서 변조한 hash 값을 동시에 보낸다.
- 수신자는 데이터와 그 데이터의 hash 값을 동시에 받는다.
- 직접 그 data 를 이용해서 hash 함수로 hash 값을 생성한다.
- 기존의 hash 값과 직접 만든 hash 값이 일치하는지 확인한다.
이는 hash function 의 눈사태 효과 를 이용한 것이다.
기밀정보 저장
또, hash 함수는 기밀정보를 저장할 때 사용되기도 한다. 일상생활에서 hash 함수가 가장 많이 쓰이는 예시는 바로 아이디와 비밀번호이다. 보통 아이디와 비밀번호를 이용해서 로그인 할 때, 각 아이디에 대응되는 비밀번호가 일치하는지 확인을 통해서 로그인이 된다.
하지만, 만약 database 에 있는 비밀번호의 정보가 누출된다면, 해킹을 통해 비밀번호로 로그인이 가능할 것이다.
이를 위해 다음과 같은 방식을 사용한다
이 방식을 사용하면, database 에 있는 정보를 누출시켜도, 이 정보는 hash 값의 형태로 저장이 되어있기에 일방향 함수의 특징을 이용해 원래의 password 을 알아낼 수가 없게 된다.
우리가 비밀번호를 잊어버렸을 때, 비밀번호의 값을 알려주지 않고 비밀번호를 변경시키도록 하는 이유도 이러한 hash 의 특성 때문이다.
wow!
- Hash funtion : MAC -
MAC 는 메세지 인증 코드(Message Authentication Code, MAC) 을 뜻한다. 쉽게 말해서 우리가 평소에 메세지를 보낼 때, 무결성 검사의 과정이라고 생각하면 되겠다.
이전의 포스트에서 Diffie-Hellman 키 교환 알고리즘에 대해서 설명했었다. 이 키 교환 알고리즘은 중간자 공격에 취약한데, 이 MAC 를 활용한다면 이 단점을 보완해줄 수 있다.
MAC 는 다음 사진을 보면 알다시피 새로운 데이터의 종류이다.
메세지를 보낼 때 무결성 검사를 위한 또 다른 하나의 데이터라고 볼 수 있다.
MAC 을 만들어내기 위해서는 Key 가 필요하다. 이는 사전에 송신자와 수신자가 서로 합의되어 있어야 한다.
위 그림과 같이, 메세지를 키를 이용해서 해시 함수 내부의 값을 정하고, 최종적으로 hash 함수를 사용해 MAC 값을 생성한다. 따라서, Diffie-Hellman 키 교환 과정의 중간에서 중간자 공격을 한다고 해도, key 를 알아낼 수 없기 때문에 무결성에 걸리게 된다.
그렇다면 이 MAC 은 어떻게 생성될까??
MAC 은 암호학적 해시 함수를 사용하는 방식과 블록 암호 방식을 사용하는 것으로 나눌 수 있다.
이중에서 hash function 을 사용하는 HMAC 에 대해서 알아보자.
- HMAC(K,M)=H(K ∣∣ M)
다음과 같은 방식이다. HMAC 의 값은 K || M 을 해시 함수에 집어넣어서 만들게 된다. 그 후에 해시 함수로 만들어진 값이 MAC 의 값이 되겠다.
번외
※ 여기서 HMAC(K,M)=H(K) ∣∣ H(M) 로 MAC 의 값을 정하게 되면, Key의 값을 몰라도 H(K) 를 알기에 공격자가 마음대로 MAC 의 값을 변조할 수도 있다. 따라서 이런 방법은 위험하다.
