블록체인 암호학 - 암호학적 해시 함수

해시(Hash)

해시 함수는 입력 데이터를 고정된 길이로 출력하는 함수다. 입력을 받아 출력을 계산하기는 쉬워도, 주어진 출력값에 해당하는 입력값은 찾기 어렵다. 작업 증명, 전자 서명, 멤버쉽 증명 등 다양한 곳에서 사용한다.

 

일반적인 해시 함수를 만드는 방법

 

해시 테이블(Hash table)

연관 구조를 이용하는 자료 구조

 

블룸 필터(Bloom Filter)

원소가 집합에  속하는지 여부를 검사하는데 사용되는 확률적 자료구조

 

 

 

체크섬(Checksum)

입력 데이터가 바뀌었는지 찾아내는 방법. 네트워크에서 오류가 발생했는지 체크하는 데 사용된다.

---

암호학적 해시 함수

 

 

이런 해시 함수를 작업증명이나 체인에 어떻게 적용할 수 있을까? 이런 해시 함수로는 적용할 수 없다. 일반적인 해시 함수와 다른 성질을 요구하는 암호학적 해시 함수가 필요하다.

 

해시 함수는 필연적으로 해시 충돌(Hash collision)이 일어난다. 해시 충돌은 입력 값은 서로 다른데 출력값이 같은 경우다.

 

$x$라는 입력값이 해시 함수 $H$에 들어가 $H(x)$라는 출력값을 가진다. 

$y$라는 입력값이 해시 함수 $H$에 들어가 $H(y)$라는 출력값을 가진다. 

이 떄 $H(x)$ = $H(y)$라면 해시 충돌이 발생한다.

 

암호학적 해시 함수는 이런 해시 충돌을 찾기 매우 어려운 해시 함수를 말한다. '충돌 저항성', '역상 저항성', '제2역상 저항성'이라는 세 가지 특성을 가진다.

 

충돌 저항성(Collision-resistant)

해시 값이 같은 입력 값 두 개를 찾기 매우 어렵다는 특성이다. 

$H(x)=H(y)$인 $x \neq y$를 찾기 어렵다.

 

역상 저항성(Preimage Resistant)

해시 값이 주어졌을 때, 그 해시 값을 생성하는 입력 값을 알아내기 어렵다는 특성이다.

$h$가 주어졌을 때 $h=H(x)$인 입력 값 $x$는 계산하기 어렵다.

 

제2 역상 저항성

어떤 입력 값과 동일한 해시 값을 가지는 다른 입력 값을 찾을 수 없어야 한다는 특성이다.

어떤 입력 값 $x$가 있고, 출력값 $H(x)$가 주어졌을 때 $H(x) = H(y)$인 다른 입력 값 $y$를 찾기 어렵다.

 

---

암호학적 해시 함수의 관계

 

 

충돌 저항 해시 함수면, 제2 역상 저항 해시 함수도 되고, 역상 저항 해시 함수도 된다.

 

1. 우선 $a$를 선택하고 $H(a)$를 계산한다.

2. 역상을 찾을 수 있는 알고리즘을 통해 $H(a)$에 대한 역상 $x$를 계산한다. 높은 확률로 $x$와 $a$는 다른 값이다. 

3. $H(x) = H(a)$인 $x$를 찾는다. 제2역상을 찾았다. 즉, 해시 충돌을 찾았다.

 

따라서 역상을 찾을 수 있으면 충돌을 찾을 수 있다.

여기에 대우를 취하면 충돌을 찾지 못하면 역상도 찾을 수 없다. 그러므로 충돌 저항 해시 함수이면 역상 저항 해시 함수도 된다.

 

---

SHA(Secure hash Algorithm)

서로 관련된 암호학적 해시 함수들의 모음이다. 이들 함수는 미국 국가안보국(NSA)이 1993년에 처음으로 설계했으며 미국 국가 표준으로 지정되었다.

 

• SHA-1: 출력 크기는 160비트이다. 충돌이 발견되어서 안전하지 않다. 현재는 사용되지 않는다.
• SHA-2: 224, 256, 384, 512비트로 된 해시값이 있는 6개의 해시 함수를 구성하고 있다.
• SHA-3: SHA-2를 대체하기 위한 함수다. SHA-2에 비해 2~4배 느리지만 훨씬 안전하다고 여겨진다. 하드웨어로 구현하면 오히려 더 빠른 경우도 있다.

 

현재 기술로 충돌을 찾기는 어려우므로 표준 암호 해시 함수로서 SHA-2 게열, SHA-3 계열을 사용한다. 

국내 표준으로는 HAS-160와 LSH가 있다.

 

출력 길이와 안전성

암호학적 해시 함수는 왜 256비트씩이나 되는 긴 출력값을 사용할까? 이는 생일 문제와 관련 있다. 생일 문제는 임의로 모은 사람들 중 생일이 같은 두 명이 있을 확률을 구하는 것이다.

 

생일 문제를 살펴보기 전에 비둘기집 원리를 살펴보자.

 

비둘기집 원리(Pigeonhole Principle)

$n+1$개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리이다.

 

귀류법으로 증명

$n$개의 비둘기집과 $n+1$마리의 비둘기가 있다고 하자. 만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면 전체 비둘기집에는 많아야 $n$마리의 비둘기가 존재한다. 그런데 비둘기는 모두 $n+1$마리이므로 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.

 

생일 문제(Birthday Paradox)

1년은 365일이므로 생일은 총 365개가 있다. 사람이 366명 이상 모이면 비둘기집 원리에 따라 생일이 같은 두 사람이 반드시 존재해야 한다. 

 

365명 이하의 사람이 있을 경우를 게산해보자. $n$명의 사람이 있을 때 그 중 생일이 같은 사람이 둘 이상 있을 확률을 $p(n)$이라 한다면 반대로 모든 사람의 생일이 다를 확률 $\bar{p}(n)$은 $1-p(n)$이 된다. 먼저 $\bar{p}(n)$을 구해보자. 두 번째 사람의 생일은 첫 번째 사람과 다르고, 세 번째 사람의 생일은 첫 번째 사람과 두 번째 사람 모두와 달라야 하므로 다음 식을 얻을 수 있다. 

따라서 $p(n)$은

이다. 두 사람의 생일이 같을 확률은 $\frac{1}{365}$이니 365명이 모여야 생일이 같은 두 명이 있을 것이라 생각할 수 있지만, 위 식을 계산해보면

$n$	1	5	10	23	30	50	70	366
$p(n)$	0.0%	2.7%	11.7%	50.7%	70.6%	97.0%	99.9%	100%

이다. 

 

23명만 있어도 생일이 같은 사람이 있을 확률이 50%다. 

$n \approx 1.17\sqrt{365}\approx 22.3$

23은 대충 365의 제곱근 정도된다고 볼 수 있다. 

 

출력값이 256비트인 해시 함수가 있다 하자. 이 중 같은 값이 있는 경우, 즉 충돌을 찾으려면 

$2^{n/2}=2^{256/2}=2^{128}$정도 걸린다. $2^{128}$번만 계산해도 충돌을 찾을 수 있기 때문에 출력 비트를 충분히 길게 한다. 

보통 암호학에서는 $2^{80}$ 이상 시간이 걸리면 안전하다고 얘기한다. 따라서 훨씬 안전하게 하기 위해 출력 길이를 256비트 정도로 충분히 길게 사용하고 있다.