이전 게시글 제목의 오타가 url로 고정이 되어 조금 보완하여 새롭게 작성하였습니다.

해시함수란

해시함수는 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수이다.

입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환한다.

동일한 값이 입력되면 언제나 동일한 출력값을 보장한다.

암호화 해시 함수란

암호화 해시 함수 는 이 해시함수의 부분집합으로 역상저항성과 제2역상저항성 그리고 충돌저항성을 가지고 있어 암호화에 활용될 수 있는 경우를 의미한다.

암호화 해시 함수의 특성과 효과들

• 역상저항성은 입력값 A에 의해 B가 출력되었다면, 출력된 B값만 주어졌을 때 입력값인 A값을 찾는 것이 계산적으로 불가능함을 의미한다.
• 제2역상저항성 은 입력값 A와 출력값 B가 모두 주어졌을 때, 똑같은 B를 반환하는 A2 를 찾아내거나 만들어내는 것이 계산적으로 불가능함을 의미한다.
• 단방향 암호화라고도 하는데 양방향 암호화가 A를 B로 암호화하고 다시 B를 A로 복호화하여 원본 내용을 확인할 수 있다면, 단방향 암호화는 A로 만들어진 B를 가지고 다시 A로 역산할 수 없다.
• 충돌저항성은 똑같은 B라는 출력값이 나오는 X가 단일하지 않고 중복이 되는 또 다른 Xn을 발견하는 것이 계산적으로 어려운 성질을 의미한다. 충돌저항성은 제2역상저항성의 외부효과(부수효과, Side effect) 이자 부분집합 이다.
• 압축효과 암호화 해시 함수가 반환하는 일정한 길이의 작은 해시값만으로 크기가 거대한 데이터의 무결성을 보장할 수 있는 외부효과를 의미한다. 예를 들어 SHA-256의 경우 100GB의 파일도 단 256bit의 해시값으로 그 내용의 무결성을 보장할 수 있다.

눈사태 효과

눈사태 효과 란 입력값의 아주 작은 변화로도 결과값이 전혀 다르게 도출되는 효과를 의미한다.
입력값에 점 하나만 추가되어도 전혀 다른 출력값이 출력된다.

또한 변경되는 부분에 있어 어떠한 규칙성도 찾을 수 없다.

예시

아래는 SHA1 함수를 이용해 비슷한 문자열을 암호화한 결과값들이다.

• "주영재" -> DDB0ED48A84B6C328E50B3BFB3D15364C669C3A6
• "주영째" -> 1C2FC56A4172A9B6D5C3C20309A46C01896D3194
• "주형재" -> 1DA926EEF1EF8533F57A45124871F8550A278EA9

용도

• 파일의 Checksum(검사합)을 구한다.
  • SuperVaccine.exe 이라는 가상의 컴퓨터 바이러스 백신 프로그램을 다운로드 받았다고 가정해보자.
  • 만약에 어떤 블랙 해커가 해당 백신 사이트를 해킹해서 설치파일을 비슷한 모양새로 동작하지만 오히려 치명적인 바이러스가 포함된 파일로 변조를 했다면 .. ?
  • 혹은 다운로드 프로그램의 문제나 보관 방식의 문제로 인해 어떤 파일의 내용에 부분적인 결손이 의심된다면 ... ?
    • 우선 전자의 경우 블랙 해커는 제2역상저항성 으로 인해 똑같은 Checksum을 가지는 바이러스 파일을 만들 수 없다.
    • 눈사태효과로 인해 아주 미세한 결손이나 위변조가 발생되어도 Checksum 값이 완전히 달라지게 된다.
  • 이 때 내가 받은 설치파일이 올바른 파일이 맞는지 또 제대로 손실없이 받아진 파일이 맞는지 확인하기 위해 해당 설치파일의 데이터를 입력값으로 하여 생성된 해시값을 공식 홈페이지나 다른 공인된 인터넷 페이지에 공개된 해시값과 비교하여 검증할 수 있다.
  • 이상이 없는 파일이라면 내가 받은 파일을 같은 함수로 검증했을 때, 공개된 해시값과 동일한 해시값이 출력될 것이기 때문이다.
  • 마치 해시값을 어떤 데이터의 지문Fingerprint 처럼 활용하는 경우이다.
• 암호를 저장한다
  • 회원가입 기능을 제공하는 인터넷 서비스를 만든다 가정했을 때 가입된 회원들의 암호를 날 것 그대로 저장하면 안된다.
  • 사용자 암호의 원문이 아닌 해시 암호화한 값을 DB에 저장해놓고, 이후 회원이 로그인을 시도할 때 입력한 암호를 동일한 해시함수로 암호화하여 DB의 해시값과 비교한다. 이 경우 원본 암호를 서버에 기록하지 않고도 유저들은 불편함 없이 평소에 사용하던 암호를 로그인에 활용할 수 있게 된다.
  • 또한, 우리의 가상 서비스가 해킹이 되어 회원들의 DB가 유출이 되더라도 해커는 역상저항성으로 인해 회원들의 진짜 암호를 알아낼 수 없다.
• 해시테이블에서의 활용.
  • 어떤 데이터의 목록에서 특정 데이터를 조회한다고 생각해보자.
  • 일반적인 방법으로는 데이터를 첫번째 순서부터 하나하나 대조해보거나 특정한 규칙에 따라 순차적으로 각 요소들을 대조하여 특정한 값을 찾아내는 방법이 있다.
  • 해시함수의 충돌저항성을 활용해 데이터를 저장할 때 해당 데이터의 해시값을 별도로 원하는 데이터를 찾아낼 수 있는 '키값' 으로 활용한다면?
  • 각 데이터의 전체값을 비교하지 않고도 일정 길이의 해시값을 이용해 원하는 데이터를 찾아낼 수 있다.
  • 별도의 탐색절차 없이 그 즉시 원하는 데이터를 추출할 수 있으므로 궁극의 탐색 알고리즘이다.

블록체인에서 해시함수의 쓰임새

아래의 내용은 필자가 관련 분야의 전문가가 아님을 감안하고 읽어주면 감사하겠다.

블록체인을 아주 높은 수준에서 추상화해서 다음 블록이 그 이전 블록에 체인을 걸고 또 다음 블록이 그 이전 블록으로 체인을 걸고.. 이런 식으로 기차들 처럼 모든 블록들이 선형으로 줄줄이 이어져 있는 모양새라고 생각해보자.

앞선 블록들은 어떤 목적을 위해 포함하고 있는 내용들이 절대 변경되서는 안된다라고 규칙을 정했을 때..
(코인의 과거 거래 이력은 상식적으로 당연히 변동이 있어서는 안된다)

이를 실현하기 위해 각 블록들은 자기 자신의 '내용'을 해싱해서 해시값을 갖고(블록헤더라고 칭해보자), 자기자신의 해시값을 갖고 있음은 물론 그 이전 블록의 해시값을 참조하게 된다.
(이전 블록의 해시값을 다음 블록이 참조한다라는 것을 앞서 이야기한 체인을 거는 비유의 구체적인 실체이다)

혹시라도 어떤 나쁜 사람이 자신의 이익을 위해 가거 블록의 내용을 변경하게 된다면 그 블록의 해시값이 변경되고(눈사태효과, 쇄도효과에 의해)..
그 이후 블록은 이전 블록을 해시값으로 참조하고 있기 때문에 연결이 단선되고, 만약에 그 나쁜 사람이 변경된 내용을 거래에 참여하는 모든 사람들에게 인정받고자 한다면 그 이후 모든 블록들의 해시값을 전부 다시 만들어 내야 될 것이다.

위 설명에서 블록체인에서 해시함수는 각 블록을 연결시키는 체인의 용도로써, 또 과거 이력의 변경을 감지하는 역할로써 사용한다라고 정리해볼 수 있을 것이다.

블록체인에서 해시함수의 또 다른 용도에 대해 설명해보겠다.

비트코인과 관련하여 '채굴'이라는 용어를 많이 들어봤을 것인데, '채굴'을 조금 더 전문적인 용어로 작업증명(Proof of work)이라고 하고, 그 진짜 의미는 '해시함수를 활용한 어떤 퍼즐을 풀어내는 일'이다.

해시함수를 이용해 의도적으로 계산적 소모량을 유발하는 퍼즐을 만들어 이 퍼즐을 풀어냈을 때 작업증명을 해냈다 혹은 채굴에 성공했다라고 한다.

그 과정을 대략적으로 설명하자면,
우선 해당 블록의 거래내역을 참조한 해시값(정확한 용어로 Merkle root 해시값), 이전 블록의 블록해시, 블록 생성시각 등등 고정된 데이터들의 집합이 재료로 주어지고,

이 변경될 수 없는 데이터에 nonce 라는 이름의 Salt(해시값을 바꾸기 위해 첨가하는 임의의 숫자) 를 계속 바꿔 더해가며 특정한 조건의 SHA256 해시값을 찾는 과정이라고 보면된다.

이 조건이라는 것은 nonce를 계속 증가시켜가며 만들어낸 해시값이 00000000A84B6C328E50B3BFB3D15364C669C3A6 와 같이 앞에 0이 몇 개 이상 있어야 된다 같은 것이다.

확률적으로 (1/16)^n 이 될텐데,
암호화 해시함수를 통해 특정 해시값을 만들어내기 위해선 어떠한 지적 추론도 불가능하고 오로지 컴퓨팅 파워를 이용한 수많은 시행착오를 반복할 수 밖에 없다는 특징을 응용한 것이다.

앞서 체인을 만드는 용도로써 해시함수를 설명할 때, 과거 내용을 변조하려는 공격자의 예를 들었는데..

이 공격자가 왜 공격을 실패할 수 밖에 없는지..
해시퍼즐을 통해 유발되는 계산적 소모량이 그 정답이 된다.
변조하려는 블록부터 시작하여 이후 모든 블록의 해시값을 계산해야되고 그 이후 새롭게 생성되는 블록들의 해시값도 전부 다 다시 계산해야 한다면..
어떤 누가 쉽게 공격을 하려는 의지를 갖을 것이며, 그 공격이 성공할 수 있을까?

취약한 부분과 충돌쌍

y = 2x 라는 함수를 가정했을 때 y가 A인 x를 찾아내는 과정을 역산이라고 한다.

y가 12라면,

1. 12 = 2x
2. 12 / 2 = x
3. 6 = x

해시함수는 그 구현내용이 공개되어 있음에도 이러한 과정으로 원본값을 알아내는 역산이 계산상 불가능하다.

하지만 역산 외의 방법으로도 B를 반환하는 An에 대해 탐색할 수 있는 다양한 방법들이 존재하는데

예를 들자면, 해당 해시함수에 의해 도출될 수 있는 방대한 경우의 수를 기록해 사전과 같은 형태로 만들어둔 후 해당 사전에서 A값을 찾아내어 대조해보는 방식(Rainbow attack) 이나,

반환값 B가 나오는 A 혹은 A2를 찾기 위해 임의의 경우의 수를 f(x)의 x에 무차별적으로 대입하여 찾아내는 방법(무차별 대입법, Brute-force attack)이 있을 수 있다.

단순 무식한 방법처럼 보일 수 있으나 컴퓨터는 이러한 단순 작업을 불평없이 수억번 수백억번 반복 수행하는데 특화된 기계이다.

또한, 컴퓨팅 파워가 나날이 발전하고 해시함수 연산을 위한 주문형 반도체가 등장하면서 현재의 암호화 해시 함수는 미래에 보안상 완결성을 상실할 가능성을 충분하게 가지고 있다.

일례로 1977년에 개발된 어떤 암호화 함수(RSA-129)의 개발자(Ronald Rivest)는 자신의 함수로 암호화된 메시지가 해독되는데 4경년이 걸릴 것으로 자신있게 예상했으나, 불과 17년 만인 1994년에 해독이 되어버린 사례가 있다.

더 가까운 과거의 사례로는 MD5 라는 암호화 해시 함수의 예를 들 수 있는데,

현재 MD5 해시값을 복호화하는 인터넷 사이트를 구글링만으로 쉽게 찾아볼 수 있는가 하면,

MD5 Decryption - (MD5에 대한 Rainbow attack 의 예시)

심지어 서로 다른 문자열을 출력하는 두 개의 프로그램이 각각 똑같은 MD5 해시값을 갖는 경우도 발견되어 있다.

MD5 Collision Demo

2011년까지 미국 표준으로 자리 잡았던 SHA1의 경우에도 충돌쌍(똑같은 해시값을 반환하는 서로 다른 데이터의 쌍) 이 아래와 같이 발견된 예시가 있다.
해당 페이지에서는 동일한 SHA1 체크섬을 가진 두 개의 다른 PDF를 예시로 들고 있다.

SHA1 충돌쌍 예시

생각해보면 입력값의 길이가 출력값의 길이보다 길어질 수 있다면 출력값의 충돌은 필연적으로 발생할 수 밖에 없기도 하다.

즉, 충돌쌍을 발견함에 있어서 충돌되는(중복되는) 경우가 확률적으로 아주 희소할지 몰라도, 무조건 하나 이상은 100%의 확률로 존재할 수 있다. (비둘기집 원리)

생일 역설 Birthday Paradox

역설이란 보통 일반적인 생각에 반대되는 이론이나 말을 뜻한다.

일반적인 상식으로 당연히 A 가 맞다고 생각해왔는데 과학적으로 검증해보니 사실은 전혀 엉뚱한 B 가 진실인 경우들이 있다.

이 생일 역설 역시 그런한 경우인데,

이 역설은 처음 아래의 질문에서 출발한다.

"n명의 사람이 임의로 모였을 때 우연히 생일이 중복되는 사람이 두 명 이상 있을 확률은 얼마나 될까?"

일단 1년은 365일 이므로 366명이 모이면 비둘기집 원리에 따라 100% 최소 한 쌍은 생일이 중복될 것이 분명하다.

이렇게 생각해보자

당신은 방송국 PD이다.
세간에 유명한 "생일이 같은 사람은 비슷한 성격을 갖는다" 라는 속설에 대한 실험카메라 프로그램을 만들고자 한다.

그래서 생일이 같은 사람을 찾아야 하는데,
문득 그런 사람들을 찾자고 (비둘기집 원리에 따라)366명이나 인터뷰를 해야되나라는 생각이 드니 눈 앞이 아득해지기 시작한다.

파일럿 프로그램이라 주어진 시간적, 경제적 자원이 많지 않기 때문이다.

그렇다고 좋은 기획을 날리기는 싫어서 울며 겨자먹기식으로 밖으로 나가 사람들을 인터뷰하는데 겨우 51명째에 벌써 생일이 같은 두 사람을 찾아내 버렸다.

당신은 속으로 생각한다.

"이거 정말 운이 좋구만! 우리 프로그램이 잘 되려는 징조인가보다!"

과연 그럴까

과연 당신은 정말 기가 막히게 운이 좋았던 것일까?

사실은 아니다.

왜냐하면 사실 임의로 모인 50명의 사람들 중에서 생일이 중복되는 사람을 한 쌍 이상 찾아낼 확률이 무려 97% 이상 되었기 때문이다.

이번엔 100% 가까운 확률까지는 필요 없으니 그냥 두 번 조사했을 때 한 번만 나와도 되게끔 50% 정도로만 목표를 낮춰보겠다고 하자.

이 때 필요한 인원수를 계산하면 놀랍게도 그 수는 23명으로 파격적으로 줄어들게 된다.

이렇듯 확률의 목표값을 활용 가능한 범위내로 아주 약간 낮춤으로써 중복된 값을 찾아내는 비용을 파격적으로 낮출 수 있다는 점이 이 생일 역설의 골자가 되는 내용이다.

생일은 불과 365가지의 경우의 수를 가진다.
하지만 해시 함수의 영역에서는 2^126 같은 엄청난 크기의 경우의 수를 갖게 되는데,
이 안에서 n개의 임의의 서로 다른 데이터를 모아 중복되는 경우를 찾는 일은 실로 엄청난 컴퓨팅 비용이 필요하게 될 것이고 이는 경제적인 비용 문제로 이어질 것이다.
(충돌쌍을 찾는다고 한다, 위에서 언급한 생일찾기와 닮아있다)

하지만 이 생일역설이 해시함수의 충돌쌍을 찾는 일에도 적용된다면 생각보다 적은 비용을 가지고도 충돌쌍을 찾는 일을 할 수 있을 것이다.

실제로 충돌쌍을 찾는 확률을 50%로 맞추면 2^(n/2) 의 표본만 있으면 된다고 한다.

출력값의 길이가 2^10(1024) 라는 암호화 해시함수가 있다고 가정했을 때, 2^5(32)회의 무차별 대입을 통해 무려 50%의 확률로 충돌쌍을 찾아낼 수 있게되는 것이다.

경제성이 없어 포기할 수도 있었던 일을 생일 역설을 통해 다시 경제성이 있는 일로 판단할 수 있게 된 것이다.

그럼에도 불구하고

확률적으로 n 비트의 출력값을 가지는 해시함수의 경우 2^(n/2) 가지의 입력값을 조사할 경우 충돌쌍을 발견할 확률이 50% 정도가 된다고 했다. (엄밀히 말하면 이보다 조금 더 많은 가짓수가 필요)

128bit의 출력값을 가지는 MD5의 경우 약 2^64 의 서로 다른 데이터를 만들어 무차별 대입하는 공격을 시도하면 50%의 확률로 1개 이상의 충돌쌍을 발견할 수 있다는 이야기이다.

2^64 가 얼마나 많은 경우의 수인지 짐작 어려울 것 같아 이를 10진수로 표현하면 아래와 같음을 참고하기 바란다.

18,446,744,073,709,551,617 개의 경우의 수를 가진다.

차수가 1씩 늘어날 때 위 숫자에 곱하기 2씩 해야되는 것이다. 당연하게도 출력값의 길이가 길어질 수록 경우의 수는 무차별적으로 증가한다.

필자가 위 생일 역설을 참고해 n개의 데이터가 m종류의 해시값에 대해 하나 이상의 중복값을 가질 확률을 계산해 보았더니, 128bit의 출력값을 가지는 해시함수의 경우 백억번이라는 어마무시한 분량의 무차별 대입 공격법을 시도해도 그 확률은 0에 수렴했다.

(파이썬으로 구현해 pypy3로 돌렸다. 구현내용은 너무 단순무식 + 허접하여 차마 공개하지 못 하겠다 ㅠㅠ)

64bit의 출력값을 가지는 해시함수의 경우에도 일억번의 무차별 대입을 가정했을 때, 그 확률은 약 0.00027101407375584863 로 계산되었다.

앞서서 구글에서 SHA1 의 충돌쌍을 발견한 경우를 간단히 링크로 소개했는데, 그 결과를 도출해내는데 있어 약 9경번의 연산이 필요했으며, 수억원의 가치에 상응하는 경제적 비용이 필요했다고 한다. (SHA1은 160bit의 결과값을 가진다. 가성비가 0에 수렴한다는 이야기)

이러한 이유로 전문가들이 충돌쌍이 하나가 발견되었던 어쨌던 실제 응용 환경에 적용할만한 공격은 발견되지 않았다..라고 하는 것 같다.

고로, 일상적인 경우.. 그러니까 뭐 인덱스로 사용한다거나 체크섬 생성 용도로 이용하는데 있어서는 대충 SHA1 이상 아무 해시함수나 사용해도 전혀 무리가 없다는 이야기 정도로 결론 지으면 될 것 같다.

종류와 선택

우선 보안성을 고려한 선택을 할 수 있다.

나와 사용자의 암호를 암호화하는데 사용할 해시함수는 앞으로도 우리의 소중한 암호들을 오랜 기간 지켜줄 수 있는 녀석으로 고르는 것이 현명할 것이기 때문이다.

앞서 설명한 MD5 함수는 매우 취약한 함수로 분류되어 해시테이블의 인덱스로 사용하거나 파일의 Checksum 생성 등의 한정된 용도를 제외한 사용자 암호 보존 용도의 사용을 권하지 않고 있다.

(물론 비밀번호 생성이나 변경시 임의의 난수값을 붙여서 함께 해싱하는 방법으로 Rainbow attack 등 공격을 예방할 수 있기도 하다.
입력값 A에 별도의 의미없는 난수값 @ 를 붙여서 해싱을 하면 A일 때와는 전혀 다른 결과값이 나온다. 이를 소금치기(Adding Salt) 라고 하고 위 경우에서 @를 소금(Salt) 이라고 한다.
이 때 이 난수값은 해싱된 비밀번호와 마찬가지로 별도 보관된다.)

또한, 해시함수는 그 용도와 사용방법에 따라서도 서로 다른 것을 선택할 수 있다.

완벽에 가까운 역상저항성과 충돌저항성이 필요하지 않으며 단순 파일 체크섬 생성 등의 용도로만 필요한 경우 MD5나 SHA-1같은 것을 선택할 수도 있고,

무차별 대입공격 등을 예방하기 위해 한 번의 연산에 다소간의 시간이 소요되는 함수를 일부러 선택할 수도 있으며,
(0.2초의 시간이 걸린다고 했을 때 사람 입장에서는 찰나의 순간일지 몰라도 수많은 경우의 수를 반복해서 대입해야 하는 공격 프로그램 입장에서는 엄청난 시간적 자원의 소모를 불러 일으킨다.)

한번에 많은 양의 해시값을 만들어야 내는 경우 혹은 하나의 입력값에 일부러 여러번의 재귀 연산을 해야되는 경우에는 속도가 빠른 함수를 골라야될 필요가 있다.

세상에는 다양한 종류의 암호화 해시 함수가 존재한다.

그중에서도 가장 대표적인 것은 단연 SHA(Secure Hash Algorithm) 함수군이며,
SHA 함수군은 NSA(미국 국가 안보국)에서 SHA-0이 1993년에 처음 개발되었다.

SHA함수군은 다시 또 세대별로 SHA-0, SHA-1, SHA-2, SHA-3 으로 나뉘고,
SHA-2 함수군은 다시 다이제스트의 길이에 따라 SHA-256, SHA-512 등으로 나뉜다.

SHA-256은 256bit의 다이제스트 길이를, SHA-512는 512bit의 다이제스트 길이를 갖는 함수로써 보통 다이제스트 길이가 길수록(출력값의 경우의 수가 많을수록) 암호화 함수로써 안정성이 높다고 본다.

잡설이 길었지만.. 결론은 용두사미..

SHA2 함수군은 2002년에 개발되었으며 그냥 일반적으로 널리 사용된다.

SHA-256 부터는 우리가 사용하는 입력값의 가짓수를 수억개 단위로 놓고 보아도, 충돌값이 나올 확률은 그냥 지구 대멸종을 야기할 소행성의 충돌 확률 보다도 더 낮다고 생각하면 되겠다.

결론적으로 일반적인 용도로는 그냥 SHA2 함수군을 사용하고, 보안에 정말 장기적인 관점에서 각별히 신경을 써야 하는 주체라면 SHA3 혹은 잘 설계된 자체 함수를 사용하면 된다.

LSH 국산 해시 암호화 함수

여담이지만, 국내에도 NSR이라는 기관에서 개발된 토종 국산~신토불이~ 암호화 해시 함수가 있다.

LSH(Lightweight Secure Hash)

자세한 구현 방법과 C, Java, Python 으로 작성된 소스코드도 제공하니 관심있으신 분들은 살펴보시면 좋을 것 같다.

향후 대한민국의 표준화된 해시 함수로써 자리매김할 가능성이 농후하다.