[Cryptography] stage5_Hash

해시 함수는 임의 크기의 데이터를 입력받아 고정된 크기의 데이터를 반환하는 함수이다. 해시 함수의 반환값을 해시 값이라고 하며, 암호학적 해시 함수(Cryptographic Hash Function)는 해시 함수 중 특정 성질을 만족하는 함수를 뜻한다.

 

 

위 그림을 보면 입력값의 크기에 상관없이 해시 함수를 거친 출력값의 크기가 동일하다.

 

 

 

*암호학적 해시 함수(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`를 찾는 것이 어렵다. 

 

위 세 가지 성질을 만족하는 해시 함수를 암호학적 해시 함수라고 한다. 그리고 현대에는 추가적으로 눈사태 효과(Avalanche Effect)를 이상적인 해시 함수의 조건 중 하나로 보기도 한다. (대칭키 암호의 확산과 비슷한 개념이다.)

 

 

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

f(x) = x mod 1000

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

π(x) 는 π의 소수점 아래 (402*x + 621)번째 자릿수를 말한다.

 

여기서 f와 g는 정수를 입력받아 0에서 999사이의 값을 반환하는 해시 함수이다. 그런데 함수 f의 경우 f(x)값에 대한 x값을 쉽게 알 수 있지만 함수 g의 경우 값 g(x)에 대해 x값을 찾는 것이 힘들다. π가 무리수이므로 소수점 아래 자릿수에 대한 규칙성을 찾을 수 없기 때문이다.

 

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

 

 

생일 역설(Birthday Paradox): 

한 반에 30명의 학생이 있다. 이 중 생일이 같은 학생이 있을 확률은 얼마일까? -> 이 확률을 생각해보는 것은 쉽다. 모두 같은 년도에 태어났고, 해당 년도가 윤년이 아니라는 가정 하에 확률은 다음과 같다. 1 -  (1 * (364/365) * (363/365) * ... * (336/365)) -> 이 확률은 약 70.6%이다. 

 

이 문제의 의의는 학생이 30명 밖에 없으니 생일이 같은 학생이 존재할 확률은 꽤 낮을 것 같지만, 예상과 달리 해당 확률은 약 70%나 된다는 것에 있다. (그래서 생일 역설인가보다.)

 

위 문제를 재해석해보면, 공역의 크기가 365인 해시 함수 H에 대해 무작위로 30개의 해시값을 생성하면 충돌이 발생할 가능성이 70%이상이라는 뜻이다.

 

여기서 좀 더 일반화를 가하면, 공역의 크기가 A인 해시 함수 H에 대해 무작위로 A^(1/2)개의 해시 값을 생성하면 그 안에 충돌이 발생할 확률이 유의미하게 높다.(고 알려져 있다.)

 

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

 

따라서 암호학적 해시 함수를 만들 땐 공역의 크기를 크게 만들어야 한다. 어떤 해시 함수 입력이 256비트의 출력에 대응할 때, 이 함수 공역의 크기는 2^256이며, 따라서 개략적으로 보아 2^128 (≃ 10^36) 이상의 연산을 해야 충돌 쌍을 찾을 수 있다는 의미이다. -> 요구되는 연산 횟수가 매우 큼 -> 충돌 저항성 만족

 

 

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

암호학적 해시 함수는 어떤 통신의 무결성을 보이기 위해 사용될 수 있다. 암호학적 해시 함수는 충돌 저항성을 만족하므로, 임의 데이터의 해시 값은 고유하다고 볼 수 있다. 따라서 송신자가 데이터와 함께 데이터의 해시 값을 보내면 수신자는 받은 데이터로부터 해시값을 생성한 뒤 이를 송신자가 보낸 해시값과 비교해 무결성을 검사할 수 있다.

 

또한 민감한 데이터 보관에 사용할 수도 있는데, 웹 서버의 데이터베이스에서 사용자의 비밀번호를 해시 값으로 저장한다면, 암호학적 해시 함수는 일방향 함수이므로 데이터베이스 유출 시에도 평문 비밀번호가 알려질 가능성이 매우 낮다. (사용자 인증 시에는 사용자가 입력한 비밀번호의 해시 값을 저장된 해시 값과 비교한다.)

 

 

 

*해시 함수의 종류

 

MD5: 임의 입력으로부터 128비트값을 생성하는 함수이다. 임의 길이의 입력을 512비트 단위로 쪼갠 뒤 연산을 거쳐 값을 생성한다. 

 

 python에서 hashlib를 import하면 MD5를 포함한 다양한 해쉬 함수들을 사용할 수 있다. ↓

 

import hashlib

print(hashlib.md5(b'dreamhack').hexdigest()) # str, 298d75fe864c08e3a68dd1da1483654d
print(hashlib.md5(b'dreamhacc').hexdigest()) # str, 02ac31c7f653161b28554a383ba36bae

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

 

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

 

 

 

SHA256: 256비트 값을 생성하는 함수이다. MD5에 비해 길이가 2배로 길어 충돌 저항성이 크게 증가했다. 

 

NIST에서 만들었으며, 현재까지 취약점이 발견되지 않아 해시가 필요한 곳에서 대부분 이용되고 있다. (이전 SHA0과 SHA1의 경우 모두 취약점이 발견되었다.)

 

 

 

*MAC

Message Authentication Code(메세지 인증 코드)의 약자이다. Diffie-Hellman 키 교환 방법에 대해 설명했을 때, 해당 키 교환 방식에 대해 중간자 공격이 가능하며, 이 때문에 무결성 검사가 추가적으로 요구된다고 했었다. ↓

 

https://orcinus-orca.tistory.com/102

[Cryptography] stage4_키 교환: Diffie-Hellman 알고리즘

 

MAC은 데이터와 함께 보내는 추가 정보인데, 이를 통해 데이터이 무결성 보장과 동시에 상대가 위장한 공격자가 아니라는 사실까지 알 수 있다.

 

MAC생성을 위해서는 메시지 + 키가 필요하다. (키는 송수신자 사이 사전 공유가 필요하다.)

 

송신자는 수신자에 데이터를 전송할 때 해당 메시지와 키로 계산된 MAC값을 같이 보낸다. 수신자는 받은 메시지를 기반으로 MAC을 계산하고 해당 값이 수신한 MAC값과 일치하는지 검사한다. 

 

공격자는 키를 모르므로 올바른 MAC값을 알아낼 수 없다.

 

 

HMAC: 

MAC을 만드는 방법은 크게 다음과 같은 두 가지 방법이 있다. 암호학적 해시 함수 이용/블록 암호 이용 

HMAC의 경우 해시 함수를 기반으로 하는 MAC이다. 

 

표준으로 정의된 HMAC은 키의 길이와 블록의 길이를 인자로 하는 복잡한 함수이지만, 간단하게 다음과 같은 HMAC함수가 있다고 가정하자. 

 

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

 

위 함수는 키와 메시지를 이어붙인 것의 해시 값으로 HMAC을 생성한다. (||는 비트 배열 연결 연산자) 

 

HMAC을 이용하면 역상 저항성으로 인해 메시지가 유출되어도 HMAC에 사용된 키를 알 수 없으며, 메시지를 위조할 경우 올바를 HMAC을 생성할 수 없다.

 

이것도 python에서 import해서 쓸 수 있다.