암호학 7주차 - 해시

0. 서론

해시 함수(Hash Function)는 임의 크기의 데이터를 입력으로 받아서 고정된 크기의 데이터를 반환하는 함수

해시 값(Hash Value) 는 해시 함수의 반환값

암호학적 해시 함수(Cryptographic Hash Function)는 해시 함수 중에서 특정 성질을 만족하는 함수

---

1. 암호학적 해시 함수

• 암호학적 해시 함수의 성질

1. 제 1 역상 저항성(Preimage Resistance)

: 암호학적 해시 함수 H에 대해 y가 주어졌을 때 H(x)=y 를 만족하는 x를 찾는 것이 어렵다.

함수가 일방향 함수여야 한다는 것을 의미한다.

​

2. 제 2 역상 저항성 (Second Preimage Resistance)

: 암호학적 해시 함수 H에 대해 x가 주어졌을 때 x와 x'이 같지 않으며 H(x)와 H(x')을 만족하는

x'를 찾는 것이 어렵다.

 

3. 충돌 저항성 (Collision Resistance)

: 암호학적 해시 함수 H에 대해 x와 x'이 같지 않고 H(x)와 H(x')을 만족하는 x와 x'을 찾는 것이 어렵다.

​

+ 눈사태 효과 (Avalanche Effect) 를 이상적인 해시 함수 조건 중 하나로 보기도 한다.

대칭키 암호 시스템의 확산처럼 입력에 작은 변화가 발생하면 해시값에도 큰 변화가 발생한다.

​

​

• 일방향 함수 (One-way Function)

: 임의의 인자에 대한 함수 값은 쉽게 계산할 수 있지만 함수 값으로부터 함수 인자를 알아내기 어려운 함수

f(x) = x mod 1000

g(x) = ((x^1721 mod 754352) x π(x))mod 1000

π(x) = π의 소숫점 아래 (402x + 621)번째 자릿 수

​

함수 f, g는 정수를 입력받아 0-999 사이의 값을 반환하는 해시 함수이다.

f에서는 x를 쉽게 알 수 있지만 g(x)=17을 만족하는 x를 알아내는 것이 어렵다.

​

​

​

​

• 생일 역설 (Birthday Paradox) - 충돌 저항성 관련 이론

생일 역설 문제

한 반에 30명의 학생이 있다. 이들 중에서 생일이 같은 학생이 있을 확률은 얼마일까? A. 2.7% B. 11.7% C. 24.6% D. 40.6% E. 70.6%

정답은 E. 70.6%이다.

: 일반적인 직관과 다르게 전체 인원이 적어도 그 안에 생일이 같은 학생이 높은 확률로 존재하는 현상

​

--> 공역의 크기가 365인 해시 함수 H가 있을 때 H에 대해 무작위로 30개의 해시값을 생성하면 충돌이 발생할

확률이 70% 이상이다.

 

--> 공역의 크기가 A인 해시 함수 H가 있을 때 H에 대해 무작위로 A^(1/2)개의 해시값만 생성하면 그 안에

충돌이 발생할 확률이 높다.

​

--> 아무리 정교한 해시 함수를 만들더라도 공역의 크기가 작으면 해시 함수는 충돌 저항성을 만족하기 어렵다.

따라서 공역의 크기를 크게 만들어야 한다.

 

예시) 해시 함수의 입력이 256비트의 출력에 대응될 때 함수의 공역의 크기는 2^256으로

충돌쌍을 찾기 힘들기 때문에 충돌 저항성을 만족한다.

​

​

• 암호학적 해시 함수의 사용

- 통신의 무결성 (Integrity)을 보이기 위해 사용

- 무결성: 데이터가 무결(수신한 데이터가 원본과 같을 때) 하게 송수신되는 성질

- 암호학적 해시 함수는 충돌 저항성을 만족하므로 임의 데이터의 해시 값은 그 데이터의 고윳값

- 송신자가 데이터와 함께 데이터의 해시 값을 보내면 수신자는 받은 데이터로부터 해시 값을 생성하고

이를 송신자가 보낸 해시값과 비교하여 받은 데이터가 변조되지 않았는지 확인할 수 있다.

​

- 민감한 데이터를 보관할 때 사용

- 웹 서버의 데이터베이스에서 사용자의 비밀번호를 평문으로 저장하면 계정정보 도난 등의

사고 발생 위험 존재

- 암호학적 해시 함수는 일방향 함수이므로 비밀번호를 해시 값으로 저장하면 데이터베이스가 유출돼도

비밀번호 원본이 알려질 가능성이 거의 없다.

- 사용자 인증 시 사용자가 입력한 비밀번호의 해시 값을 저장된 해시 값과 비교한다.

​

---

2. 해시 함수의 종류

• MD5

: Ronald Lorin Rivest가 1991년에 만들어낸 해시 함수

임의 입력으로부터 128비트(16바이트)의 값을 생성하는 함수

임의 길이의 블록 암호를 비슷하게 512 비트 단위로 쪼갠 후 연산을 거쳐 값을 생성한다.

현재는 다양한 취약점이 발견되어 안전한 해시 함수로 여겨지지 않는다.

​

​

​

• SHA256

: 미국 표준 기술 연구소에서 만들어낸 해시 함수로 현재 취약점이 발견되지 않아 사용하고 있다.

256비트 (32 바이트) 의 출력을 내는 함수이다.

MD5에 비해 길이가 2배로 늘어나 충돌 저항성이 크게 증가했다.

지금까지 충돌 발생 사례는 알려지지 않고 있다.

SHA256 이전에 SHA0, SHA 1이 있었지만 취약점이 발견되어 사용하지 않는 것을 권장한다.

​

​

---

3. MAC (Message Authentication Code, 메세지 인증 코드)

:데이터와 함께 보내는 추가적인 정보

MAC을 통해 데이터의 무결성을 보장할 수 있고 현재 통신 중인 상대방이 위장한 공격자가 아니라는 사실도

알아낼 수 있다.

​

• MAC 만드는 방법

- 암호학적 해시 함수를 이용하는 방법​

- 블록암호를 이용하는 방법

​

​

메시지와 키가 필요하다. 키는 송신자와 수신자 사이에 사전에 공유되어있어야 한다.

1. 송신자는 수신자에게 메시지를 보낼 때 메시지와 키를 이용해 계산된 MAC 값을 같이 보낸다.

2. 수신자는 기존에 알고 있던 키를 이용해 수신한 메시지의 MAC을 계산하고 전송받은 MAC과 일치하는지

비교한다.

​

공격자가 메시지를 위조하고 싶은 경우 위조된 메시지에 대한 올바른 MAC 값을 알아야 하는데 키를 모른다면 MAC을 계산할 수 없다.

 

​

​

• HMAC

: 해시 함수를 기반으로 하는 MAC

실제 표준으로 정의된 HMAC는 키의 길이, 블록의 길이를 인자로 하는 복잡한 함수.

 

예시) HMAC(K, M) = H( K || M )

||는 비트 배열을 연결하는 연산자 - ex. 01||110 =01110

-> 키와 메시지를 붙인 것의 해시 값으로 HMAC을 생성한다.

​

• HMAC 사용의 장점

1. 메세지를 도청당해도 역상 저항성으로 인해 공격자가 HMAC에 사용된 키를 알아낼 수 없다.

2. 메세지를 위조하면 위조한 메세지에 대해 올바른 HMAC을 생성할 수 없다.