7주차 정리

해시 (Hash)

---

1. 들어가며

해시(Hash)는 자료 구조, CTF, 암호 화폐 등  컴퓨터 과학의 여러 분야에서 사용된다.

해시 함수(Hash Function)는 임의 크기의 데이터를 입력으로 받아서, 고정된 크기의 데이터를 반환하는 함수이며, 해시 함수의 반환값은 해시 값(Hash Value)이라고 부른다. 암호학적 해시 함수(Cryptographic Hash Function)는 해시 함수 중에서 특정 성질을 만족하는 함수를 의미합니다.

---

2. 암호학적 해시 함수

1. 암호학적 해시 함수의 성질 

• 현대에는 눈사태 효과(Avalanche Effect)를 이상적인 해시 함수의 조건 중 하나로 보기도 한다. 이 성질은 대칭키 암호 시스템의 확산과 비슷하게 입력에 조그만 변화가 발생하면, 해시값에도 큰 변화가 발생한다.

• 암호학적 해시 함수(Cryptographic Hash Function)는 다음 성질을 만족하는 해시 함수이다.

제 1 역상 저항성(Preimage Resistance) : 암호학적 해시 함수 H에 대해 y가 주어졌을 때 H(x) = y를 만족하는 x를 찾는 것이 어렵다. 이는 함수가 일방향 함수여야 함을 의미한다.
제 2 역상 저항성(Second Preimage Resistance) : 암호학적 해시 함수 H에 대해 x가 주어졌을 때 x ≠ x', H(x) = H(x')을 만족하는 x'을 찾는 것이 어렵다.
충돌 저항성(Collision Resistance) : 암호학적 해시 함수 H에 대해  x ≠ x', H(x) = H(x')을 만족하는 x, x'을 찾는 것이 어렵다.

 

2. 일방향 함수

임의의 인자에 대한 함수 값은 쉽게 계산할 수 있지만, 함수 값으로 부터 함수의 인자를 알아내기 어려운 함수를 일방향함수(One-way Function)라고 부른다.

 

3. 생일 역설

• 생일 역설(Birthday Paradox)은 암호학적 해시 함수의 충돌 저항성과 관련된 이론이다.
• 생일 역설 문제를 보면, 일반적인 직관과 다르게 전체 인원이 적어도, 그 안에 생일이 같은 학생이 높은 확률로 존재하는 현상을 생일 역설이라고 한다.
• 아무리 정교한 해시 함수를 만들더라도, 공역의 크기가 작으면 해시 함수는 충돌 저항성을 만족하기 어렵다. 암호학적 해시 함수를 만들 땐 이를 고려하여 공역의 크기를 크게 만들어야 한다. 

4. 암호학적 해시 함수의 사용

• 암호학적 해시 함수는 어떤 통신의 무결성을 보이기 위해 사용될 수 있다.
• 수신한 데이터가 원본과 같을 때, 이 데이터는 무결하다고 하며, 데이터가 무결하게 송수신되는 성질을 통신의 무결성(Integrity)이라고 한다.
• 암호학적 해시 함수는 충돌 저항성을 만족하므로, 임의 데이터의 해시 값은 그 데이터의 고윳값이라고 볼 수 있다. 따라서 송신자가 데이터와 함께 데이터의 해시 값을 보내면, 수신자는 받은 데이터로부터 해시값을 생성하고, 이를 송신자가 보낸 해시값과 비교하여 받은 데이터가 변조되지 않았는지 확인할 수 있다.
• 암호학적 해시 함수는 민감한 데이터를 보관할 때 사용될 수 있다. 웹 서버의 데이터베이스에서 사용자의 비밀번호를 평문으로 저장하면 관리자가 비밀번호를 유출하거나, 해킹 사고로 사용자의 계정 정보를 모두 도난당할 위험이 있다. 그러나 암호학적 해시 함수는 일방향 함수이므로 비밀번호를 해시 값으로 저장하면 데이터베이스가 유출돼도 비밀번호의 원본이 알려질 가능성이 거의 없다. 

---

3. 해시 함수의 종류

1. MD5

• MD5는 Ronald Lorin Rivest가 1991년에 만들어낸 해시 함수이다.
• MD5 해시 함수는 임의 입력으로부터 128비트(=16바이트)의 값을 생성하는 함수이다.

2. SHA256

• SHA256은 미국 표준 기술 연구소(NIST)에서 만들어낸 해시 함수이다. 현재까지 취약점이 발견되지 않아 해시가 필요한 대부분의 곳에서 사용되고 있다.
• SHA256은 256비트(=32바이트)의 출력을 내는 함수이다. MD5에 비해 길이가 2배로 늘어나 충돌 저항성이 크게 증가했다.

---

4. MAC

1. MAC이란?

• MAC은 데이터와 함께 보내는 추가적인 정보로, MAC을 통해 데이터의 무결성을 보장할 수 있고 또 현재 통신 중인 상대방이 위장한 공격자가 아니라는 사실 또한 알아낼 수 있다.

• MAC을 만들어내기 위해서는 메시지와 키가 필요하다. 이때 키는 송신자와 수신자 사이에서 사전에 공유되어있어야 한다.
• 송신자는 수신자에게 메시지를 보낼 때, 메시지와 키를 이용해 계산된 MAC 값을 같이 보낸다. 수신자는 기존에 알고 있던 키를 이용해 수신한 메세지의 MAC을 계산하고, 이를 전송받은 MAC과 일치하는지 비교한다.
• 공격자가 메시지를 위조하고 싶으면 위조된 메시지에 대한 올바른 MAC값을 알아야 하는데 키를 모르는 공격자로서는 MAC을 계산할 수 없다.

2.HMAC

• MAC을 만드는 방법은 크게 암호학적 해시 함수를 이용하는 방법과 블록 암호를 이용하는 방법으로 나눌 수 있다. 그중에서 HMAC은 해시 함수를 기반으로 하는 MAC이다.
• HMAC은 키의 길이, 블록의 길이를 인자로 하는 복잡한 함수이다.
• HMAC을 사용하면, 메세지를 도청당해도 역상 저항성으로 인해 공격자가 HMAC에 사용된 키를 알아낼 수 없으며, 메세지를 위조하면 위조한 메세지에 대한 올바른 HMAC을 생성할 수 없다.

---

5. 마치며

해시 함수는 웹, 네트워크, 블록체인 등 컴퓨터와 연관된 여러 분야에서 무결성을 입증하는 수단으로 사용되고 있다.

-퀴즈

Q1. A

Q2. A