Hash란?
Hash가 영어니깐 먼저 단어 뜻을 먼저 알아봐야 겠지? Hash란 “저미다, 다지다, 잘게 썰다(chop up)”라는 뜻을 가지고 있는데.. 요리 중에서 Hash Brown 이란 요리는, 잘게 다져진 감자를 주재료로 해서 만드는 간단한 음식이랍니다.
Hash Function이란?
우리가 알고 있듯이 함수(F)는 입력값(X)와 출력값(Y) 사이의 관계를 표현하는 식 또는 시스템이다. X값과 Y값을 주고 함수F를 찾는다 던가, X값 또는 Y값을 주면 출력값 또는 입력값을 계산해 낼 수 있지만, 해시함수는 좀 특이하다.
해시함수는 출력값이 주어졌을 때, 이에 해당하는 본래의 입력값을 찾는 것이 (일정 시간 내에는)불가능하다. 마치 Hash Brown을 보고서 감자의 모습을 유추할 수 없 듯이 말이다. 수퍼컴퓨터로도 계산했을 때 100년이상이 걸린다면 일단은 불가능에 가까운 것이다. 이를 해시함수의 단방향성이라고 한다. 이외에도 아래와 같은 특징이 있다.
-압축 : 출력값의 길이는 입력값의 길이보다 작아야한다.
-충돌방지 : 서로 다른 입력값은 서로 출력값을 가져야한다.
-눈사태효과 : 입력값이 단 1비트라도 차이날 때 출력값은 반이상 다른 값이 나와야한다.
-효율성 : 어떤 입력값이라도 출력값은 쉽게 계산되어야 한다.
해시함수의 압축특징은 충돌의 가능성을 가지고 있다. 왜냐하면 왼쪽의 input영역이 오른쪽의 output 영역(8자리의 16진수)보다 항상 크기 때문이다. 이와 관련하여 생일문제가 이해에 도움을 준다.
생일문제
생일 문제란 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 고2 정도의 수학 수준으로 그렇게 많이 어렵지는 않으므로 미리 겁먹지는 마시길^^ 생일의 가능한 가짓수는 365개(2월29일을 고려할 경우 366개)이므로 366명 이상의 사람이 모인다면 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2을 넘는다.
얼핏 직관적으로 생각 하기에는 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 확률이 99%가 넘어서 “항상 있다” 라고 이야기해도 크게 거짓말 하는 사람이 아니다.^^
이제 수식으로 한번 풀어 보자. n명의 사람이 있을 때 그 중 생일이 같은 사람이 둘 이상 있을 확률을 p(n)이라고 하자. 그럼 모든 사람의 생일이 다를 확률 [p(n)] 은 1-p(n)이 된다. 먼저 [p(n)]을 구해보면, 두 번째 사람의 생일은 첫번째 사람과 다르고, 세번째 사람의 생일은 첫 번째와 두 번째와 모두 달라야 하므로 아래와 같은 식을 얻을 수 있다. [p(n)]이 아래이다.. 수식지원이 안됨--;;
가 되고, 최종적으로 구하고자 하는 생일이 같은 사람이 둘 이상 있을 확률 p(n)은
가 된다. 여기서, n≤365인 자연수 이다. 이 p(n)값을 특정 n값에 대하여 계산하면 아래와 같다.
즉, 50명만 모이면 그 가운데 2명 이상의 생일이 같을 확률이 97%이고, 100명이 모이면 거의 1에 가까워진다는 것을 알 수 있다. 생일이 같은 두 사람을 찾는 것과 비슷하게, 암호학적 해시 결과가 같은, 즉 해시충돌이 발생하는 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 생일 공격(birthday attack)이라고 부른다.
정보보호의 기본 원칙
정보의 수집, 가공, 저장, 검색, 송수신 중에 정보의 훼손, 변조, 유출 등을 방지하기 위한 관리적, 기술적 수단을 강구하는 것으로 아래와 같은 특징을 가진다.(CIA/ANA: 중요한 내용이므로 미중앙정보국 “CIA아나?"로 숙지^^)
-기밀성(Confidential) : A가 B에게 정보전달 시 제 3자가 알아차릴 수 없도록 변환시키는 기술
-무결성(Integrity) : A가 B에게 정보전달 시 내용이 중간에 변경되지 않도록 하는 기술
-인증(Authentication) : 정보를 받는 사람이 누구 인지 확인하는 기술
-접근제어(Access Control) : 허가 받은 사람만이 데이터에 접근할 수 있도록 하는 기술
-부인방지(Non-repudiation) : 정보를 송수신 한 후에 그에 대한 사실의 부인을 방지하는 기술
-감사추적(Audit) : 시스템에서 처리 이력을 기록하여 향후 문제발생시 근원지를 확인하는 기술
해시함수의 종류
이렇게 해서 만들어진 현재의 해시함수의 종류는 MD(Message Digest) 계열과 SHA(Secure Hash Algorithm) 계열 등이 있으며, 이 외에도 여러 종류의 해시함수들이 개발되고 있다. MD5는 이미 해시충돌이 발견되었고, SHA-1의 경우도 구글이 클라우드에 있는 컴퓨터를 동원해 922경 3372조 368억 5475만번 이상 연산을 수행해 충돌을 규명했다. 주로 사용되는 것이 SHA-256이며, 비트코인의 블록체인상에서 사용된 해시함수가 SHA-256이다.
해시함수의 사용 예
가장 간단한 예로 시스템로그인 패스워드의 암호화이다. 암호화 되지않은 Plaintext형태로 패스워드를 저장하면 당연히 CIA/ANA의 원칙중에서 기밀성을 위반하는 것이다. 사용자가 설정한 패스워드를 해시함수로 함호화해서 해시값을 저장하고, 이후에 사용자가 로그인시 입력한 패스워드의 해시함수 값이 저장된 해시함수 값과 같으면, 입력값이 같다고 보고 시스템 접근을 허용한다.
H(x)=H(y) 이면 x=y <=> x≠y 이면 H(x) ≠H(y)
해시 함수는 전자 서명과 함께 사용되어 효율적인 서명 생성을 가능하게 한다. 긴 메시지에 대해 서명을 하는 경우, 전체 메시지에 대해 직접 서명을 하는 것이 아니고 짧은 해쉬값을 계산해 이것에 대해 서명을 하게 된다. 공개키 연산은 많은 계산량을 필요로 하기 때문에 전체 메시지를 공개키 길이의 블록 단위로 나누어 모든 블록에 대해 서명을 하는 것은 매우 비효율적이다. 그러므로 먼저 메시지를 입력 받아 짧은 해쉬값을 계산하고, 이것에 대해 한 번의 서명 연산을 하는 것이다. 이 계산값은 원래의 메시지에 대한 서명으로 인정된다.
이러한 로그인 인증 및 전자서명 외에도 메시지 지문, 데이터 훼손 발견 및 바이러스 탐지 등 에도 사용된다.
암호학과 해시함수
암호학과 별관련이 없는 듯 하지만 암호학을 배우다 보면 해시함수는 필수라는 것을 알게된다. 암호라는게 복호가 되었을 때만 의미가 있는 것처럼 보인다. 해쉬함수는 어떠한 메세지를 특정 길이의 메세지로 바꾸어서 해당 메세지가 전달과정에 손상 되지 않았는지 무결성을 확인하는 용도로 사용된다. 예를 들면 10MB 짜리 데이터에 대한 내용을 SHA-256 이면 256비트짜리 메세지로 해시값을 구한 후10MB 짜리 데이터와 같이 해시값을 전달하면, 받은 사람이 10MB 짜리 데이터를 다시 SHA-256 으로 해시값을 구해서 전달받은 해시값과 비교해 같으면 데이터가 손상되지 않았다는 것을 확인한다.
암호화/복호화 방식
ECB(Electronic Codebook) 모드 : 가장 기본적인 암호화 방식으로 메시지블록이 서로 섞이지 않았기 때문에 정확히 어떤 내용인지는 모르지만, 어렴풋하게 틀은 짐작할 수 있다.
-ECB Encryption(암호화) : Plaintext -> Input block(Encrypt)Output block -> Ciphertext
-ECB Decryption(복호화) : Ciphertext -> Input block(Decrypt)Output block -> Plaintext
메시지가 들어오면 일정 단위로 끈어서 암호화 복호화 시킨다. ECB 모드의 가장 큰 문제점은 공격자가 중간의 한블록을 없애더라도 수신자는 변조(순서변화, 삭제 등)를 알 수 없다.
CBC(Cipher Block Chain) 모드 : 메시지가 들어 오면 일정 단위로 끊는다. 첫번째 블록을 암호화 한다. M1 -> C1 두번째 블록은 첫번째 블록의 암호문과 결합된 후 암호문 블록을 만든다. M2*C1 -> C2 이후 동일한 과정을 거치며, 복호화는 이의 역순이다. 메시지의 패턴조차 짐작하기 힘들다. 따라서 해쉬함수로 사용하여 전자서명 등의 응용분야에 사용할 수 있다.
특징은 암호화 혹은 복호화의 과정에서 첫번째 블록 혹은 두번째 블록에서 에러가 발생하면 그 이후의 블록들에서 연달아 에러가 발생한다. CBC 모드에서는 블록과 블록이 서로 연결되어 있기 때문에 한 블록을 없애거나 순서를 바꾸면 암호화 혹은 복호화가 제대로 되지 않는다.
해시함수와 암호화폐
사토시의 논문에 전자화폐를 디지털서명의 체인으로 정의를 하고 있다.(We define an electronic coin as a chain of digital signature). 이 전자화폐가 제대로 기능을 하기위해서는 이중지불(double spending)문제를 해결해야 하는데, 이를 위해서 어느 것이 진짜 인지를 결정하는 과정이 필요하며, 이때에 해시함수의 암호화가 원리가 적용된다. 그래서 암호화폐(Cryptocurrency)라고도 부른다.
블록은 거래 기록의 집합이고 블록체인은 그 블록들이 연결되어 있는 것이다. 블록을 "체인닝"하기 위해 해시 암호화 알고리즘을 이용한다. 블록은 각기 주소를 갖고 있다. 이 주소가 바로 ‘현재 해시’이다. 그리고 블록은 서로 연결되어 있으므로, 이전 블록의 주소도 갖고 있어야 한다. 이전 블록의 주소가 바로 ‘이전 해쉬’이다. 그리고 이 해시값들은 반드시 ‘0000’으로 시작되어야 한다. 여기서 현재해시는 "Nonce, 거래내역, 이전해시" 의 함수로 구성되어 있다.
현재해시 = f(Nonce, 거래내역, 이전해시)
자, 이제 10번째 블록을 생성하는 과정을 보자. 먼저, 지난 10분간의 ‘거래내역’을 블록에 담는다. 그리고, ‘이전해시’ 값을 가져 온다. 이제 거래내역과 이전해시 값은 이미 정해졌다. 여기서 10번째 블록을 생성하는 과정이란, ‘현재해시’ 값을 ‘0000’으로 시작되게 하는 Nonce값을 찾는 과정이다.
즉, 위의 f(Nonce, 거래내역, 이전해시 ) 식에 Nonce 값을 넣어 본다. 예를들어 1을 넣어 본다. 이 때 구해지는 현재 해시값이 ‘0000’으로 시작되면 성공이다. 만약, 아니라면 실패다. 실패한다면, 이제 2를 넣어 본다. 만약 실패 한다면, 이번에는 3을 넣어 본다. 정답을 찾을 때까지 이 과정은 반복된다. 그러다가, 특정한 Nonce 값을 넣었을 때, 현재 해시값이 ‘0000’으로 시작되면, 비로소 성공이다. 이 때, 이 블록은 9번째 블록과 연결된다. 10번째 블록이 생성되는 순간이다.
새로운 블록을 기존의 블록체인에 연결하는 과정은, 이처럼 현재해시 값이 ‘0000’으로 시작되는 Nonce값을 찾는 과정이다. Nonce는 다른 블록의 내용과 함께 해쉬 함수로 들어가 해쉬 함수의 결과를 특정한 목표값 이하로 만들게 하는 숫자이다. Nonce 값을 찾는데 성공하면 그 보상으로 가상화폐가 주어진다.
Nonce값을 찾는데 기준시간 보다 짧았다면, 0의 개수를 증가시켜서 난이도를 높인다. 비트코인, 이더리움 등 에서는 이것을 채굴(Mining)이라고 한다. 통상 GPU방식의 채굴기 보다 ASIC방식의 채굴기가 더 성능이 뛰어나다. 현재 비트코인은 ASIC방식을, 비트코인골드는 ASIC방식은 불가하게 끔 해시함수를 변경하여 GPU방식이고, 이더리움도 GPU방식을 사용한다.
이러한 Nonce를 찾기 위해서 1초에 몇 번을 계산할 수 있는지를 나타내는 지표가 Hashing Power이고, 이는 채굴기의 성능지표이다. (1MH/S = 1,000,000 Hashes Per Second, 1초에 백만번 연산 수행)
마치며
해시함수란 DES(Data Encryption Standard)와 블록 알고리즘으로 만들어진 일종의 단방향 암호화 기술이다. 아무리 큰 메시지라도 그것의 무결성 문제는 상대적으로 매우 작은 크기의 해시값의 무결성 문제로 축소될 수 있다. 해시함수 자체는 무결성(Integrity) 검증을 위해 사용한다고 보면 되고, 다른 기법과 조합하여 인증(Authentication) 기능까지 수행한다.
IT보안전문가나 프로그래머의 영역이었던, 해쉬암호학이 이제는 암호화폐라는 이름의 “돈”으로 일반 대중에 다가서고 있다. 누구나 가지고 있는 돈과 IT가 결합되었기 때문에.. 더 이상 문송(문과라서 죄송)하지 않도록.. IT를 쉽고 재미있게 하나씩 알아 보도록하자. IT는 이제 그 무엇과도 결합될 테니까..