암호학 - 해시

해시 함수(Hash Function) 

임의 크기의 데이터를 입력으로 받아서, 고정된 크기의 데이터를 반환하는 함수.

반환값 = 해시 값(Hash Value)

 

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

다음 성질을 만족한다.

 

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

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

이는 함수가 일방향이어야 함을 의미한다.

 

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

암호학적 해시 함수 H에 대해 x가 주어졌을 때 

이를 만족하는 x'을 찾는 것이 어렵다

 

3. 충돌 저항성 (Collision Resistance)

암호학적 해시 함수 H에 대해 

을 만족하는 x, x'을 찾는 것이 어렵다.

눈사태 효과

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

대칭키 암호 시스템의 확산과 비슷하게 입력에 조그만 변화가 발생하면, 해시값에도 큰 변화가 발생하는 성질이다.

 

 

일방향 함수(One-way Function)

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

함수 f는 f(x) = 17을 만족하는 x가 17, 1017, 2017 임을 쉽게 알 수 있는 반면, 

g는 x를 알아내는 것이 어렵다. 

파이가 무리수이므로 x를 0부터 차레로 대입하면서 g(x)의 값을 17로 비교하는 것이 최선이다. 

 

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

 

생일 역설(Birthday Paradox)

 

생일 역설 문제

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

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

 

가능한 생일 수 365개의 비해 학생 수는 적으니 확률이 낮을거라고 생각하지만 답은 제일 높은 E이다.

이처럼 일반적인 직관과 다르게 전체 인원이 적어도, 그 안에 생일이 같은 학생이 높은 확률로 존재하는 현상을 생일역설이라고 한다.

 

재해석 : 공역의 크기가 365인 해시 함수 H가 있을 때, H에 대해 무작위로 30개의 해시값을 생성하면 충돌이 발생할 확률이 70%이상이다.

 

공역의 크기가 A인 해시 함수 H가 있을 때, H에 대해 무작위로 √A개의 해시 값만 생성하면 그 안에 충돌이 발생할 확률이 유의미하게 높다고 알려져있다.

 

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

-> 공역의 크기를 크게 만들어야한다.

 

256비트 출력 - 공역 크기는 2의 256승

 

 

암호학적 해시 함수의 사용

 

1. 어떤 통신의 무결성을 보이기 위해 사용.

수신한 데이터가 원본과 같으면 무결하다. 

 

통신의 무결성(Integrity) : 데이터가 무결하게 송수신되는 성질

 

데이터와 함께 해시 값을 보내면, 수신자는 받은 데이터로부터 해시값을 생성하고, 받은 값과 비교해서 변조 여부를 확인할 수 있다. 

 

2. 민감한 데이터 보관시에도 사용 가능

 

비밀번호를 해시 값으로 저장하면 DB가 유출돼도 비밀번호의 원본이 알려질 가능성이 거의 없다. 

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

 

MD5 

1991년 Ronald Lorin Rivest가 만든 해시 함수.

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

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

import hashlib
print(hashlib.md5(b'dreamhack').hexdigest())
print(hashlib.md5(b'dreamhacc').hexdigest())

with open('/path/to/file', 'rb') as f:
	print(hashlib.md5(f.read()).hexdigest())

SHA256

 

NIST에서 만들어낸 해시 함수.

아직 취약점이 발견되지 않아 해시가 필요한 대부분의 곳에서 사용되고 있다. 

 

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

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

실제로 충돌 사례가 없다.

import hashlib
print(hashlib.sha256(b'theori').hexdigest()) # str, 95610a88dd5e9cd53a1ba879608d8cbd938f8dea4ea800dcc7c4d925a4466e47
print(hashlib.sha256(b'theorr').hexdigest()) # str, acd88112d4c87351e193cfd425cf7f01925ea15b9c03b7be03ad1343c8f13f70
# SHA256 hash of file 
with open('/path/to/file', 'rb') as f:
    print(hashlib.sha256(f.read()).hexdigest())

 

메시지 인증 코드 (Message Authentication Code, MAC) 

Diffie-Hellman 키 교환은 중간자 공격으로부터 안전하지 않으며, 무결성을 입증할 방법이 필요하다.

MAC은 데이터와 함께 보내는 추가 정보.

- 데이터의 무결성 보장

- 현재 통신 중이 상대방이 위장한 공격자가 아니라는 걸 알아냄.

MAC을 만드려면 키와 메시지가 필요하고, 키는 송수신자 사이에 사전 공유돼있어야한다.

메시지를 보낼 때, 메시지와 키를 이용해 계산된 MAC값을 같이 보낸다. 

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

 

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

 

 

MAC을 만드는 방법

1. 암호학적 해시 함수 이용

2. 블록 암호 이용

 

HMAC 

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

 

HMAC(K,M)=H(K ∣∣ M)

 

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

이 함수는 키와 메시지를 붙인 것의 해시 값으로 HMAC을 생성한다.

 

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

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

 

취약성

HMAC(K,M)을 알 때, 공격자가 K를 알 수 있다. 

-> K를 몰라도 HMAC값으로부터 H(K) 값을 알아내어 공격자가 임의 데이터에 대한 올바른 HMAC을 구할 수 있다.

import hashlib, hmac
# key : b'secret', msg : b'hello world'
h = hmac.new(b'secret', b'hello world', hashlib.sha256).hexdigest() 
print(h) # 734cc62f32841568f45715aeb9f4d7891324e6d948e4c6c60c0621cdac48623a