블록체인 - 2. 해시 함수 (Hash Function), SHA256

 이 글은 블록체인에서의 해시 함수/해시 값의 역할에 대해 기술한 글이기에, 해시에 대한 모든 내용에 대해 설명하지 않고 필요한 내용만 추려 작성하였다.

---

해시 함수

< 그림 1 - 해시 함수의 동작을 나타낸 간단한 그림 >

 

 해시 함수(Hash Function)는 어떤 데이터가 입력으로 주어지면 이를 고정된 길이의 데이터로 변환(매핑) 시켜주는 함수다. 가령 위의 그림 1에서는 입력 값의 길이와 무관하게, 항상 일정한 길이(16진수 7자리)의 출력으로 바꾸어 출력하고 있다. 이렇게 해시 함수를 적용하는 과정을 해싱(Hashing)이라 하고, 해싱 후에 나온 출력값 해시 값, 해시 코드, 해시 체크섬, 그냥 해시 등으로 부른다.

 

 블록체인에서 해시 값은 블록의 지문과도 같은 역할을 한다. 데이터에 아주 작은 변화라도 생길 경우 해시값은 급격히 달라지며, 해당 블록 뒤에 있는 다른 블록들의 해시값도 모두 달라져버리기 때문에 데이터 조작 여부를 알 수 있게 된다(이는 바로 다음 절에서 설명할 쇄도 효과 때문에 발생한다).

---

암호화 해시 함수의 요구사항

 블록 체인에서는 해시 함수의 일종인 암호화 해시 함수/알고리즘을 이용한다. 암호화 해시 함수에는 여러 종류가 존재하나 비트코인에서는 SHA256 함수를 이용하고 있다(MD5, SHA-1등은 설계 결함이 발견되었음). 이러한 암호화 해시 함수(Cryptographic Hash Function)에는 3가지 요구 사항이 존재한다. 이는 역상 저항성, 제 2 역상 저항성, 충돌 저항성이다. 이 세 가지 요구 사항과 함께, 해시 함수에 요구되는 요구 사항도 함께 확인할 것이다.

 

 

1. 역상 저항성 (Preimage Resistance) / 단방향성 (One-Way)

< 그림 2 - One-way의 예시 >

 

 출력에서 입력을 찾아내는것이 계산상 어려운 성질을 역상 저항성이라 한다. 단방향성이란 거의 유사한 의미인데, 데이터에서 해시값을 만드는 건 가능해도 해시값에서 데이터를 만드는 건 몹시 어려워야 한다는 성질이다. 위 그림 2에서와 같이 '오장원에 지는 별'이라는 문구에서 해시값을 만드는 건 가능해도, 원문을 모르는 사람이 해시 값만을 가지고 '오장원에 지는 별'이라는 입력이 주어졌음은 추측할 수 없어야 한다.

 

 해시 값을 알고 있을 때 그 해시 값을 만들어내는 입력값을 찾는 공격을, 제 1 역상 공격(First Preimage Attack)이라 한다.

 

 

2. 제 2 역상 저항성 (Second Preimage Resistance) / 쇄도 효과 (Avalanche Effect)

< 그림 3 - Avalanche Effect의 예시 >

 

 쇄도 효과는 해시 함수에 요구되는 가장 중요한 특성이다. 이는 데이터가 1비트만 달라지더라도 해시값은 완전히 달라져야 함을 의미한다. 만약 이러한 성질이 없다면 해시 값의 규칙성을 찾아낼 수 있을 것이고, 같은 해시 값을 가지게 되는 서로 다른 입력 값을 찾을 수 있을 것이다. 이것을 막기 위해 암호화 해시 함수는 어떤 입력값의 해시 값을 바꾸지 않는 다른 입력 값을 찾기 어려워야 하는데, 이를 제 2 역상 저항성이라 한다.

 

 제 2 역상 저항성에 대해, 좀 더 자세히 설명하자면 '어떤 메시지가 주어지고', '그 메시지에 대한 해시 값도 주어졌을 때', 그 해시 값과 같은 출력을 내는 다른 메시지를 찾아내는 것이 계산상 불가능함을 말한다.

 

 입력값이 정해져 있을 때, 그 입력값과 같은 해시 값을 출력하는 다른 입력값을 찾는 공격을 제 2 역상 공격(Second Preimage Attack)이라 한다. 특정한 해시 값이 아닌, 모든 해시 값에 대해서, 같은 해시 값을 가지는 두 메시지를 찾는 공격은 바로 뒤에서 설명할 충돌 공격으로, 제 2 역상 공격과는 다르다.

 

 

3. 충돌 저항성 (Must withstand collisions)

 

< 그림 4 - 출력 값의 범위가 최대 2 bit일때, 발생하는 해시 충돌의 예시 >

 

 고정된 길이의 출력을 내보내는 해시 함수의 특성상, 서로 다른 입력에 대해서 같은 출력 값을 가지는 경우는 필연적으로 발생한다. 위 그림 4와 같이 입력값의 길이에는 제한이 없으나 출력 값이 2 bit로 제한되어 있는 어떤 함수가 존재한다면, 입력값이 완전히 다름에도 같은 출력 값을 가지게 된다. 이를 해시 충돌이라 한다. 이와 같은 성질을 비둘기 집의 원리라고도 부른다.

 

< 그림 5 - 비둘기 집의 원리를 나타낸 그림 >

 

 비둘기 집의 원리는 앞의 그림 4의 설명과 유사하다. 비둘기 집의 수보다 비둘기의 수가 더 많다면, 반드시 어떤 집에는 비둘기가 두 마리 이상 들어가게 된다는 이야기다.

 

 암호화 해시 알고리즘은 인위적으로 해시 충돌을 일으키는 서로 다른 입력값을 찾아내는 것이 계산상 어려워야 한다. 이것을 충돌 저항성이라 한다. 반대로, 인위적으로 해시 충돌이 일어나는 두 입력값을 찾는 공격을 충돌 공격(Collision Attack)이라 한다. 이는, 출력 값이 고정되어 있는 역상 공격에 비해 좀 더 쉬운 것으로 알려져 있다.

 

 

4. 결정적 (Deterministic)

< 그림 6 - Deterministic의 예시 >

 

 동일한 입력에 대해서는 항상 동일한 해시 값이 나와야 한다는 성질이다.

 

 

5. 빠른 연산 (Fast Computation)

< 그림 7 - 시간 복잡도가 O(n), O(n^2)인 두 그래프의 입력길이(x)에 대한 연산 시간(y)을 나타낸 그래프 >

 

 빠른 연산은 메시지에서 해시 값을 찾아내는 속도가 빨라야 함을 말한다. 입력값이 늘어남에 따라 연산 시간이 기하급수적으로 늘어나는 함수는 암호화 해시 함수로 적합하지 않다. 암호화 해시 함수는 최소한 입력 길이와 연산 시간 사이에 선형적인 관계가 나타나는 것을 요구한다.

---

SHA256

 SHA256은 비트코인에서 작업증명(PoW, 이는 다른 글에서 자세히 설명한다)에 이용하는 암호 해시 함수이다. 이름인 SHA는 Secured Hash Algorithm의 약자이다. SHA 함수군은 미국 국가안보국(NSA)에서 1993년 개발하였으며, NSA의 많은 논란과는 별개로 현재까지도 굉장히 잘 동작하고 안전하며, 많은 어플리케이션의 비밀번호 저장, 디지털 문서 검사, 블록체인등에 이용되고 있다.

 

 SHA256의 알고리즘은 공개되어 있고(이곳에서 확인 가능), 누구나 배우고 활용할 수 있으며, 영상/텍스트/오디오/실행파일/운영체제 등 모든 디지털 문서에 대해 적용할 수 있다. 256비트로 구성되어 있으며, 이는 곧 64글자짜리 문자열로 이루어져 있다.

 

< 그림 2 - SHA256 함수에 직접 입력값을 넣고, 출력을 확인해보는 과정 >

 

 이곳에서 SHA256을 간편하게 경험해 볼 수 있다.