블록체인의 기본, 해시란 무엇인가?

블록체인이 작동하는 원리를 제대로 이해하기 위해서는 무결성에 대한 이해가 필요하다. 무결성(Data Integrity)은 ‘특정한 데이터를 보호하여 그 데이터를 정상인 상태로 유지하는 성질’을 의미한다. 무결성은 정보보안 영역에서 굉장히 중요한 키워드다. 블록체인은 암호화폐, 투표 시스템 등에 적용이 된다는 점에서 무결성을 보장하지 못하면 사람들이 신뢰하고 사용하지 않을 것이다. 즉 누구도 데이터를 변질시킬 수 없는 특성, 무결성이 있어 암호화폐도 존재하는 것이다. 먼저 정보보안에서 가장 중요시하는 세 가지 요소인 CIA에 대해 알아보자.

[그림 1] 정보보안의 세 가지 요소(CIA)

CIA란 기밀성(Confidentiality), 무결성(Integrity), 가용성(Availability)의 앞 글자를 딴 단어다. 각종 IT 관련 자격증 시험에서도 매 번 나오는 개념이므로 컴퓨터에 관심이 많은 독자라면 이를 기억해두면 좋을 것이다. 정보보안에서는 무결성 뿐만 아니라 기밀성, 가용성이라는 요소를 중요하게 여기고 시스템을 설계할 때 이를 기준으로 삼는다. 기밀성이란 ‘허가된 자만 데이터에 접근할 수 있도록 하는 것’이고, 가용성은 ‘서비스가 원활하게 제공되도록 하는 것’이다.

예를 들면 개발자가 웹 서비스를 개발할 때는 사용자가 회원가입 시에 비밀번호를 설정하도록 한다. 일반적으로 타인의 비밀번호를 모르면 접근할 수 없으므로 기밀성을 보장하는 것이다. 또한 비밀번호를 데이터베이스에 저장할 때 해시(Hash)라는 알고리즘을 적용해 해커가 이를 취득해도 원래의 비밀번호를 알아낼 수 없도록 한다. 이는 데이터가 정상임을 보장해주는 해시의 개념을 적용했다는 점에서 무결성을 지킨 것이다. 마지막으로 DDoS 공격 등으로부터 서버를 보호해 웹 서비스가 항상 동작 가능하도록 한다. 이는 가용성을 지키는 것이라고 할 수 있다.

암호화폐의 블록체인은 기본적으로 동일한 장부 데이터를 전 세계의 많은 컴퓨터들이 공유하고 가지고 있다는 점에서 가용성을 철저하게 보장받을 수 있다. 장부가 한 컴퓨터에만 담겨있지 않다는 점에서 해커들은 DDoS 공격을 수행할 대상이 되는 단일 서버를 설정할 수 없기 때문이다. 또한 각 개인의 지갑은 고유한 개인키를 가지고 있어 자신이 아닌 다른 사람이 나의 암호화폐를 인출할 수 없어 기밀성을 보장한다. 마지막으로 블록체인은 누구도 장부 내용을 변조할 수 없도록 해시(Hash) 알고리즘이 시스템 전반에 적용되어 무결성을 보장한다.

사실 모든 사람이 동일한 장부 데이터를 가진다는 블록체인 아이디어를 생각해보면 기밀성과 가용성이 쉽게 지켜질 것이라는 점은 이해하기 어렵지 않다. 하지만 장부의 내용을 누구도 쉽게 변조할 수 없으며 장부를 변조했다고 하더라도 다른 사람들이 어떻게 그 사실을 바로 알아차릴 수 있는 것인지, 그 무결성 매커니즘은 잘 이해가 가지 않을 것이다. 무결성이 성립 가능한 이유를 이해하기 위해서는 약간의 수학적 사고가 필요하다. 바로 컴퓨터공학부의 전공과목인 자료구조(Data Structure)나 암호학 관련 강의에서 자주 배우게 되는 해시(Hash) 알고리즘이다.

해시(Hash)의 정의

일반적으로 우리가 특정한 정품 소프트웨어를 다운로드 받을 때 그 소프트웨어가 해커로 인해 변질되지 않은 정상적인 소프트웨어인 것을 어떻게 검증할 수 있을까? 우리는 이 때 해시(Hash)라는 것을 이용하여 검증한다. 이전 강좌에서도 간단히 언급을 했는데 해시는 ‘특정한 데이터를 이를 상징하는 더 짧은 길이의 데이터로 변환하는 행위’를 의미한다. 여기에서 상징 데이터는 원래의 데이터가 조금만 달라져도 확연하게 달라지는 특성을 가지고 있어 무결성을 지키는 데에 많은 도움을 준다. 예를 들어 ‘A’라는 문자열의 해시와 ‘B’라는 문자열의 해시는 고작 한 알파벳이 다를 뿐인데 그 결과가 천차만별이라는 것이다. 예를 들어 대표적인 해시 알고리즘인 MD5는 어떠한 입력 값을 넣든 항상 각양각색의 32자리의 16진수 값을 반환한다.

[그림 2] 대표적인 해시 알고리즘인 MD5의 연산 결과

16진수는 ‘1부터 9까지의 숫자와 A부터 F까지의 알파벳으로 수를 표현하는 방식’이다. 실제로 ‘A’라는 문자열의 MD5 해시 결과 값은 ‘7FC56270E7A70FA81A5935B72EACBE29’이라는 16진수 문자열을 가진다. 반면에 알파벳 하나만 다른 ‘B’라는 문자열의 MD5 해시 결과 값은 완전히 다른 문자열인 ‘9D5ED678FE57BCCA610140957AFAB571’다. 해시는 그 결과 값을 완전히 바꾸어준다는 점에서 강력한 도구다. 이렇게 ‘암호화된 정보가 큰 폭으로 변화하는 효과’를 눈사태 효과(Avalanche Effect)라고 하는데 좋은 암호 알고리즘들은 모두 눈사태 효과를 그 특성으로 가진다. 흔히 소프트웨어 판매 업체에서는 판매하는 소프트웨어 설치 프로그램의 바이너리 코드에 해시 알고리즘을 적용한 결과 값을 웹 사이트에 함께 게시한다. 고객들은 자신이 어디선가 받은 소프트웨어가 정품인지 확신이 안 설 때 자신이 가지고 있는 소프트웨어의 해시 값이 사이트에 출력된 해시 값과 일치하는 지 확인하여 검증할 수 있다.

MD5 해시 알고리즘의 경우 온라인 MD5 해시 생성기 웹 사이트에 접속하여 실습해볼 수 있다. 해당 URL(http://www.convertstring.com/ko/Hash/MD5)로 접속해 몇 가지 입력 데이터를 넣어 MD5 해시를 거친 결과 데이터가 나오는 것을 확인해보자.

비둘기집의 원리

대부분의 해시 알고리즘들은 항상 고정된 길이의 결과 문자열을 반환한다는 특징을 가지고 있다. 앞서 언급한 MD5 해시 알고리즘은 128 비트로 구성된 결과, 즉 32자리의 16진수 값을 반환한다. 이 문자열의 길이는 변함이 없다. 그렇다면 128 비트라는 결과는 이론적으로 최대 몇 개의 경우의 수를 가질 수 있을까? 한 비트(Bit) 단위는 0 혹은 1이라는 두 가지 경우의 수를 가진다는 점에서 128bit는 총 2의 128 제곱만큼의 경우의 수를 표현할 수 있다. 이는 약 340 간(澗)에 해당하는 매우 큰 숫자이다. 단순히 무차별 대입(Brute-Forcing)으로 해시 결과가 동일한 두 입력 값을 찾기 위해서는 개인용 컴퓨터로는 억겁의 시간이 소요될 것이다.

[그림 3] 128비트로 표현할 수 있는 경우의 수 근사치

하지만 아무리 큰 숫자라고 하더라도 무한(Infinite)은 아니라는 점에서 특정한 두 입력 값의 결과 해시 값이 동일한 경우가 발생할 수 있다. 예를 들어 입력 값의 개수가 2의 128 제곱을 넘어가게 되면 최소한 한 쌍의 입력 값은 그 결과 값이 동일할 것이다. 더 간단한 예로 설명을 하자면 비둘기가 5마리일 때 상자가 4개밖에 존재하지 않는다면 아무리 비둘기를 균등하게 분배해도 최소한 한 상자에는 2마리의 비둘기가 들어가게 된다. 지난 시간에도 언급했지만 이처럼 ‘n + 1개의 물건을 n개의 상자에 넣을 때 최소한 하나의 상자에는 두 개 이상의 물건이 들어 있는 원리’를 비둘기집 원리라고 말한다. 당연히 해시는 수학적 공리인 비둘기집 원리를 따른다.

[그림 4] 비둘기집 원리 예시

비둘기집 원리에 따라 해시에서는 이처럼 ‘서로 다른 입력 값의 해시 결과 값이 동일한 문제’, 즉 한 상자에 두 개의 물건이 들어가는 현상인 충돌(Collision)이 발생할 여지가 있다. 당연히 충돌이 적게 발생할수록 좋은 해시 알고리즘이다. 또한 만약 특정한 해시 알고리즘에 대하여 무차별 대입이 아닌 수학적인 연산 과정으로 원하는 문자열의 해시 결과 값을 만들어낼 수 있다면 그 해시 알고리즘은 무결성을 보장할 수 없다는 점에서 더 이상 사용되지 않게 될 것이다.

더불어 해시는 기본적으로 복호화가 불가능하다는 특징이 있다. 이는 당연히 입력 데이터 집합이 출력 데이터 집합을 포함하고 있으므로 특정한 출력 데이터를 토대로 입력 데이터를 찾을 수 없기 때문이다. 즉 동일한 출력 값을 만들어낼 수 있는 입력 값의 가짓수는 수학적으로 무한(Infinite)개라고 볼 수 있다. 만약에 해시 결과 값에 대해서 복호화를 수행할 수 있다면 이는 압축률이 무한인 압축 알고리즘과도 같다. 해시는 애초에 복호화를 수행할 수 없도록 설계 되었으며, 실제로도 해커가 쉽게 복호화를 할 수 없다는 점에서 매력적인 알고리즘인 것이다.

MD5와 SHA-1

이제 과거에 많이 사용되었던 대표적인 해시 알고리즘인 MD5와 SHA1에 대해서 자세히 알아보도록 하자. MD5(Message-Digest Algorithm 5)는 ‘128비트 고정 길이의 결과를 가지는 암호화 해시 함수’다. 대표적인 인터넷 표준안인 RFC 1321로 지정되어 있고, 10년이 넘는 시간동안 컴퓨터 시스템에 사용되어 해시 알고리즘의 아버지와도 같다. MD5는 최근 개인용 PC 한 대로 수 초 내로 해시 충돌을 찾을 수 있을 정도의 효율적인 공격 알고리즘이 발표되어 무결성을 보장하기 어렵다는 점에서 현재는 사용되지 않고 있다.

MD5의 핵심 알고리즘은 32비트 워드 네 개로 이루어진 128 비트 스테이트(Bit State)를 이용하여 연산하는 것이다. 처음에 각 워드는 A, B, C, D라는 변수명으로 상수 값을 가진다. 이후에 입력 문자열이 블록 단위로 들어오게 되면 각 워드를 이용해 연산 과정을 거치고, 그 결과로 128 비트 스테이트의 값을 새롭게 갱신한다. 입력 문자열 블록을 처리하는 과정은 총 4 라운드(Round)로 구성되는데 이산수학에서 사용되는 기초 연산을 이용하므로 관련 문서를 찾아보면서 구현하면 고급 프로그래머가 아니더라도 프로그래밍 언어로 쉽게 구현할 수 있다는 장점이 있다.

이러한 MD5는 현재 무결성을 효과적으로 보안하지 못한다는 점에서 이보다 더 나은 해시 알고리즘인 SHA-1 혹은 나아가 SHA-256을 사용하도록 권장되고 있다. SHA-1(Secure Hash Algorithm 1)은 ‘미국 국가안보국(NSA)에서 처음으로 개발한 해시 암호화 모델로 MD5를 대신하여 많이 사용되고 있는 해시 알고리즘’이다. 기본적으로 알고리즘은 MD5 해시 함수에서 사용되었던 것과 같이 다양한 기초 수학적 연산 과정을 포함한다. 이러한 SHA-1 알고리즘도 MD5 알고리즘만큼 치명적인 보안 결함이 발견된 것은 아니지만 충돌이 발견된 적이 있다는 점에서 보다 보안이 중요한 시스템에서는 이후에 다루게 될 SHA-256을 사용하도록 권장되고 있다.

기본적으로 충돌(Collision)은 해시 알고리즘의 이용 과정에서 충분히 발생할 수 있다. 단순히 수학적으로 계산해도 컴퓨터가 확률적으로 언젠가는 충돌을 찾아낼 수 있기 때문이다. 하지만 무차별적으로 데이터를 대입하는 방식인 무차별 대입(Brute-Forcing)이 아니라 충돌을 연산 수식을 통해 ‘의도적으로’ 발생시킬 수 있다면 보다 큰 문제가 될 수 있다. 앞서 다루었던 MD5 알고리즘은 이미 다양한 프로그램을 이용해 손쉽게 의도적으로 해시 충돌을 만들어낼 수 있다는 점에서 심각한 보안 결함을 가지고 있다. 이러한 측면에서 저자 또한 실제로 웹 서비스 등의 프로그램을 개발할 때 고객의 비밀번호를 반드시 SHA-256 이상의 해시를 적용해 저장한다.

레인보우 테이블 공격

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

물론 레인보우 테이블을 막기 위한 다양한 방어 기법도 연구되었다. 그 대표적인 것은 바로 소금(Salt) 값을 넣는 방법이다. 개발자가 사전에 미리 정해 놓은 문자열을 입력 데이터에 추가하여 해시 결과를 저장하는 방식이다. 이처럼 ‘원본 데이터를 찾아내기 어렵도록 하기 위해 추가하는 문자열’을 소금이라고 한다. 예를 들어 소금 값이 ‘Teddy Bear’라고 가정했을 때 MD5에 문자열 ‘A’, ‘B’, ‘C’를 넣었을 때의 결과는 다음과 같다. 이와 같이 소금 값을 적절하게 대입하는 경우 악의적인 공격자는 해시 결과 값을 얻었다고 하더라도 원래 문자열이 ‘A’, ‘B’, ‘C’와 같은 형태였다는 것을 파악하기가 기하급수적으로 어려워진다. 따라서 실제 서버 운영 시에 개발자들은 레인보우 테이블을 막기 위해 소금 값을 반드시 적용한다.

[그림 5] 소금 값을 적용한 MD5 이용 사례 예시

하지만 실제로 해커에게 서버가 해킹을 당하는 경우에는 솔트 값을 적용하는 소스코드 또한 해커의 손에 넘어가는 경우가 많으므로 궁극적으로 가장 중요한 것은 사용자 본인이 암호를 얼마나 어렵게 설정했느냐다. 기본적으로 비밀번호에 특수문자, 알파벳, 숫자가 포함될 수 있도록 설계하면 하나의 문자 당 약 80개의 경우의 수를 가지게 된다. 이 때 사용자의 비밀번호가 12자리라면 80의 12제곱인 68,719,476,736,000,000,000,000 개의 경우의 수를 가지게 되므로 사실상 해커가 하나의 비밀번호 해시 데이터를 탈취하고, 소금 값까지 가지고 있다고 하더라도 원래의 비밀번호를 알아내기는 쉽지 않다. 하지만 특정한 사용자가 이용하는 모든 웹 사이트의 비밀번호가 동일하다면 해커는 그 비밀번호 하나만 복호화에 성공하면 모든 서비스를 해당 사용자의 권한으로 이용할 수 있을 것이다. 따라서 암호를 복잡하게 설정하는 것은 매우 중요하다.

MD5 복호화 실습하기

이제 한 번 MD5 복호화를 실습해보도록 하자. 먼저 저자는 독자들에게 하나의 암호문을 제시할 것이다. 앞서 저자는 레인보우 테이블(Rainbow Table)이라는 개념을 설명하여 독자들에게 힌트를 주었다. 정보보안에 재능이 있는 독자라면 저자가 제시하는 암호문이 의미하는 원래 문장을 찾아내는 방법을 금방 생각해낼 수 있을 것이다.

[그림 6] 특정한 의미를 가지고 있는 MD5 암호문 예제

위와 같은 암호화 문장을 해커의 입장에서 발견했다고 가정해보자. 이 때 이를 어떻게 복호화 할 수 있을까? 해시 암호문을 복호화하는 가장 대표적인 두 가지 방법은 ① 자신이 직접 자신의 컴퓨터에 사전 데이터베이스(Dictionary Database)를 생성한 뒤에, 이를 레인보우 테이블로 삼아 프로그램으로 많은 입력 값을 넣어 해시 결과 값 데이터베이스를 구축하는 방법, 그리고 ② 레인보우 테이블을 제공해주는 무료 사이트를 이용하는 것이다. 두 번째 방법이 자신의 컴퓨터 용량을 소비하지 않아도 된다는 점에서 보다 효율적이다. MD5 복호화를 위한 레인보우 테이블을 무료로 제공해주는 사이트의 URL(http://md5decryption.com/)로 들어가 보자.

위 사이트에서 저자가 제시한 암호문 ‘0CFDE61FEF91A54F5289BE8106FDB85D’을 넣고 실행해보면 결과 값인 ‘나동빈’이 나오는 것을 알 수 있다. 하지만 여기에서 의문점이 들 수 있다. 아무리 이 외국 웹 서비스가 방대한 양의 레인보우 테이블을 가지고 있을 지라도 어떻게 ‘나동빈’이라는 저자의 한국 이름을 가지고 있는 것일까 하는 의문점 말이다. 사실 이는 이 웹 서비스가 현재 방대한 양의 레인보우 테이블을 가지게 된 이유를 고려해보면 이해하기 쉽다. 해당 웹 서비스는 MD5 복호화 기능 말고도 암호화 서비스를 제공하고 있다. 이 때 사용자가 암호화를 위해 입력한 문장을 레인보우 테이블에 새롭게 삽입하는 것이다. 즉 저자는 ‘나동빈’이라는 문장을 먼저 해당 사이트에서 암호화를 시켜놓았기 때문에 이 사이트에서 복호화가 가능한 것이다.

MD5 해킹 실습하기

해시의 개요 챕터의 마지막으로 다룰 내용은 바로 MD5 해킹 실습이다. 구체적으로 ‘서로 다른 역할을 수행하는 두 파일의 MD5 해시 값이 같도록, 즉 충돌이 발생한 것처럼 타인을 속이는 실습’을 해보자. 이를 위해 특정한 파일의 바이너리 코드를 MD5 해시 결과로 바꾸어주는 프로그램을 이용하면 된다. 국내 개발자가 개발한 파일 해시 계산기(File Hash Calculator)를 공식 URL(http://www.owlnetworks.pe.kr/software/calcfilehash)에서 다운로드 받아 실행해보자.

[그림 7] 파일 해시 계산기 실행 결과

이제 ‘찾아보기’ 버튼을 눌러서 아무 파일이나 파일 해시 계산기에 넣은 뒤에 해시를 계산해보자. 저자는 한 번 현재 작성하고 있는 원고 파일(HWP)을 넣어보았다. 그 결과 MD5 해시 값으로 ‘79D4BE7B9C390E30ECC7B5BA8ACEB337’가 출력되었다. 현재 작성하고 있는 원고는 이러한 해시 결과 값으로 상징된다는 것이다. 아마 독자가 특정한 파일을 넣을 때마다 MD5 해시 결과 값은 항상 다를 것이다. 만약에 넣은 두 개의 파일의 해시 결과 값이 우연히 동일하게 나온 독자가 있다면 바로 로또를 구매하라고 추천하고 싶다. 단순히 계산했을 때 확률적으로 로또 1등에 760,620,663,133,661,799,251,010,032 번 당첨된 셈이니까.

[그림 8] 파일 해시 계산기 실습 결과

이제 한 번 완전히 다른 역할을 수행하는 두 개의 파일의 MD5 해시 값이 동일하도록 만들어 보자. 사실 지금 소개할 방법은 MD5 뿐만 아니라 어떠한 해시 알고리즘에 적용하더라도 동일하게 작동하는 방법이다. 일단 저자는 다음과 같이 두 개의 파일을 준비해보았다.

[그림 9] 해시 충돌 눈속임 준비물

이후에 명령 프롬프트(CMD)를 실행해서 두 파일이 위치한 폴더로 이동한다. 이 때 폴더 이동명령어(Change Directory, CD)를 이용한다. 그리고 이어서 copy /b 명령어를 이용해 두 개의 파일을 합친 파일을 만들어보자. 저자는 차례대로 result.jpg와 result.zip이라는 이름으로 결과 파일을 생성해주었다.

[그림 10] 서로 다른 두 파일을 명령 프롬프트를 이용해 합치는 방법

이제 두 결과 파일은 다음과 같다. 둘 다 파일의 용량이 늘어난 것을 제외하고는 기존의 image.jpg 파일과 hided.zip 파일과 동일하게 작동한다. 하지만 실제로 바이너리 코드의 관점에서는 두 파일은 완전히 동일한 파일이라고 할 수 있다.

[그림 11] 해시 충돌 눈속임 결과 파일

한 번 파일 해시 계산기를 이용해 두 결과 파일의 해시 값을 확인해보자. 저자의 경우 생성한 두 파일의 MD5 해시 값이 모두 ‘D7BF42DD206E03A72526F5609E1CBB4C’라는 값을 가지고 있는 것을 확인할 수 있었다. 이와 같이 간단하게 서로 다른 역할을 수행하는 파일이 완전히 동일한 바이너리 코드를 가지게 할 수 있는 것이다.

[그림 12] 해시 충돌 눈속임 결과 파일의 해시 결과 값

이처럼 해시는 무결성이라는 정보보안 요소의 핵심 알고리즘이며 다양한 편법과 기술이 존재한다는 점에서 알고 있으면 도움이 되는 개념이다.

http://www.bitweb.co.kr/news/view.php?idx=360