블록체인과 해시함수

카테고리 없음

by caution.dev 2018. 12. 14. 17:06

해시 함수란 무엇인가?

해시 함수는 임이의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수이다. 암호 알고리즘에는 키가 사용되지만, 해시 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 된다. 이러한 해시함수를 사용하는 목적은 메시지의 오류나 변조를 탐지할 수 있는 무결성을 제공하기 위해 사용된다.

특징

1. 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다.

2. 눈사태 효과 : 입력값의 일부분만 변경되어도 전혀 다른 결과값을 출력한다.

3. 출력된 결과값을 토대로 입력값을 유추할 수 없다.

Block Header

블록의 헤더는 다음 6가지 정보로 구성된다.

1. version: 소프트웨어 / 프로토콜 버전

2. Previousblockhash: 이 블록체인의 바로 앞에 위치하는 블록의 block hash 값

3. Merkle Root: 개별 거래 정보의 거래 해쉬를 2진 트리 형태로 구성할 때, 트리의 루트에 위치하는 해쉬값

4. Time: 블록이 생성된 시간

5. Bits: 난이도 조절용 수치

6. Nonce: 임의로 대입하여 조건을 만족하는 해쉬값이 나타났을 때, (블록이 생성되었을 때) 임의의 값

Block Hash는 블록의 식별자 역할을 하며, 블록 헤더 정보를 입력값으로 하여 SHA256 Hash funtion을 적용하여 계산된다. 항상 32바이트의 숫자값이다.

SHA 256

SHA(Secure Hash Algorithm) 알고리즘은 미국 표준 기술 연구소(NIST)에 의해 공표된 표준 해시 알고리즘으로 소프트웨어 시장 전반에서 전세계적으로 가장 많이 사용되고 있다. 구글 보안 연구팀이 발표한 SHA-1의 해시 충돌 공격 사례에 대한 구체적인 내용은 SHAttered 서비스의 URL(https://shattered.io/)에서 확인할 수 있다. 이러한 연구를 통해 SHA-1을 대상으로 하는 공격이 가능하다는 것이 실무적으로 증명되어 최근 보안 전문가들은 각종 소프트웨어를 개발할 때는 반드시 SHA-256 이상의 해시 알고리즘을 사용하기를 권고하고 있다. SHA-2는 2001년 개발되었으며 2002년에 표준으로 지정되었다. SHA-2가 생성하는 결과의 출력 길이는 256, 384, 512 bit로 다양하다.

SHA 알고리즘은 크게 SHA-1과 SHA-2로 나눌 수 있으며 종류에 따른 성능은 다음과 같다.

SHA-512 진행과정

Padding : 입력된 문자열을 1024bit 문자열로 변환할 때, 입력된 값을 제외하고 남은 블록의 크기만큼 0 으로 메우는 작업

위의 그림은 “abc” 라는 문자열을 입력했을 때 패딩작업의 결과를 보여준다.

입력받은 문자열을 먼저 넣어주고, 문자열의 끝을 의미하는 1을 넣어준 다음 나머지는 0으로 패딩하되, 끝에서 128bit는 입력받은 문자열의 크기를 적어준다.

Parsing : N개의 1024bit 문자열들을 64bit로 쪼갠다.
초기 해시값을 지정한다. 설계 당시의 값으로 고정되어 있다,

비둘기집 원리

블록체인에 사용되는 SHA-256 함수는 약 256비트의 결과값을 가진다. 그렇다면 이 결과는 이론적으로 몇 개의 경우의 수를 가질 수 있을까? 한 비트의 단위는 0 혹은 1이라는 두 가지 경우의 수를 가진다는 점에서 256비트는 2의 256 제곱의 경우의 수를 가진다.

115792089237316195423570985008687907853269984665640564039457584007913129639936

하지만 아무리 큰 숫자라 해도 무한이 아니라는 점에서 특정 두 입력값의 결과 해시 값이 동일한 문제가 발생할 수 있다. 앞서 말했던 2의 256제곱의 수는 매우 큰 수임에 분명하나, 입력값이 이 수보다 많이 발생할 경우 최소한 한 쌍의 입력 값은 그 결과 값이 동일할 것이다. 이처럼 n + 1 개의 물건을 n 개의 상자에 넣을 때 최소한 하나의 상자에는 두 개 이상의 물건이 들어 있는 원리를 비둘기집 원리라고 한다.

이러한 충돌이 적게 발생할 수록 좋은 해시 알고리즘이 되며 만일 이러한 충돌이 많이 일어나거나 무차별 대입이 아닌 특정 연산으로 원하는 문자열의 해시 결과 값을 만들어낼 수 있다면 그 해시 알고리즘은 무결성을 보장할 수 없다는 점에서 더 이상 사용되지 않게 될 것이다.

레인보우 테이블 공격

앞서 해시는 복호화가 불가능하다는 특징이 있다고 했는데 데이터의 유형에 따라서 사실상 복호화가 가능할 수 있다. 예를 들어 특정한 사용자의 비밀번호가 ‘123456’이고 특정한 시스템에서 이 비밀번호를 해시하여 데이터베이스에 저장했다고 가정해보자. 이 때 해커는 비밀번호 ‘000000’부터 ‘999999’까지를 반복적으로 해시를 적용하여 일종의 해시 사전(Hash Dictionary)을 구성할 수 있다. 이후에 특정한 해시 값을 이 사전에 대입하여 원래의 비밀번호를 찾아내는 프로그램을 작성하게 되면 사용자의 비밀번호인 ‘123456’이 해커에게 드러나게 되는 것이다. 이렇게 ‘특정한 해시 알고리즘을 적용해 만들어낼 수 있는 데이터를 모두 저장하여 만든 해시 사전’을 레인보우 테이블(Rainbow Table)이라고 부른다. 특정 서비스에 회원가입을 할 때 어려운 비밀번호를 설정해야 하는 이유는 바로 레인보우 테이블 공격 때문이다.

왜 SHA-256을 사용하는가?

https://security.stackexchange.com/questions/165559/why-would-i-choose-sha-256-over-sha-512-for-a-ssl-tls-certificate