7주차 암호학 정리

해시 함수

: 임의 크기의 데이터를 입력받아 고정 크기의 데이터를 반환하는 함수

반환값 = 해시 값

암호학적 해시 함수 = 해시 함수 중에서 특정 성질을 만족하는 함수

 

 

 

1. 암호학적 해시 함수

 

1-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'을 찾는 것이 어렵다" - 제2역상저항성과 유사함. x가 기존에 주어지지 않아도 조건을 만족하는 x, x' 쌍을 찾는 것 자체가 어려움
4. + 눈사태 효과(Avalanche Effect) : 입력의 작은 변화가 해시값의 큰 변화로 이어지는 성질(대칭키 시스템의 확산과 유사)

 

1-2. 일방향함수(One-way Function)

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

 

1-3. 생일 역설(Birthday Paradox)

: " 한 반에 30명의 학생이 있다. 이들 중에서 생일이 같은 학생이 있을 확률은 얼마일까? 

A. 2.7% B. 11.7% C. 24.6% D. 40.6% E. 70.6% "

• 생일의 경우의 수는 365, 학생은 30. 낮은 확률로 예상하기 쉽지만 정답은 E(70.6%).
• 일반적인 직관과 다르게 공역이 크고 생성되는 해시값의 수가 적어도 그 안에서 충돌이 발생할 확률이 높게 존재하는 현상
• = 정교한 해시 함수를 만들더라도 공역의 크기가 작으면 해시 함수는 충돌 저항성을 만족하기 어렵다
• 이를 고려해 공역의 크기를 충분히 크게 만들 필요가 있음.

 

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

: 어떤 통신의 무결성을 보이기 위해 암호학적 해시 함수가 사용될 수 있음.

• 무결성 = 수신한 데이터가 원본과 같게(무결하게) 송수신되는 성질
• 암호학적 해시 함수는 충돌저항성을 만족하므로, 임의 데이터의 해시값은 그 데이터의 고윳값이라고 볼 수 있음
• -> 송신자가 데이터와 함께 데이터의 해시 값을 보내면
• 수신자는 데이터로부터 해시값을 생성하고,
• 이를 송신된 해시값과 비교하여 데이터의 변조 여부를 확인 가능

: 민감한 데이터를 보관하는 데도 암호학적 해시 함수가 사용될 수 있음

• 웹서버의 DB에서 사용자 데이터를 평문으로 저장하면 관리자에 의한 유출이나 해킹 사고로 인한 도난 위험이 존재함
• 암호학적 해시 함수는 일방향함수이므로 비밀번호를 해시값으로 저장하면 DB가 유출되어도 원본이 알려질 가능성이 희박
• 사용자를 인증할 때는 사용자가 입력한 비번의 해시값을 저장된 해시값과 비교하는 형식으로 사용

 

 

---

2. 해시 함수의 종류

 

2-1. MD5

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

임의 길이 입력을 블록 암호와 유사하게 512비트 단위로 쪼갠 뒤 연산을 거쳐 값을 생성함

현대에는 다양한 취약점이 발견되어 안전하게 여겨지지 않으나, 몇몇 구형 시스템에는 잔존함

 

2-2. SHA256

: 임의 입력으로부터 256비트(=32바이트)의 출력을 내는 함수

MD5 대비 길이가 2배 증가 -> 충돌저항성 크게 증가 (현재까지 충돌 사례 없음)

현재까지 취약점 발견 x. 대부분의 곳에서 사용

 

 

 

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

: Diffie-Hellman 키 교환의 약점인 중간자 공격에 대비해 데이터의 무결성과 통신 상대의 안전성을 보장하는 방법

메시지와 (사전에 공유된) 키 필요

송신자는 송신 시 메시지 + 키를 이용해 계산된 MAC 값을 같이 송신

수신자는 키를 이용해 수신한 메시지의 MAC을 계산하여 전송받은 MAC과 일치하는지 비교

공격자는 위조를 위해서 올바른 MAC값을 알아야 할 필요가 있으나, 키를 모르면 MAC을 계산할 수 없음.

 

3-1. HMAC

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

키의 길이, 블록의 길이를 인자로 삼는 복잡한 함수. 인자들을 비트 배열 연결한 것의 해시값으로 HMAC 생성

메시지를 도청당해도 역상저항성으로 인해 공격자가 키를 알아낼 수 없음

메시지를 위조하면 위조한 메시지에 대한 올바른 HMAC을 생성할 수 없음