어떻게 sha 알고리즘은 데이터를 모두 다르게 - eotteohge sha algolijeum-eun deiteoleul modu daleuge

해시함수란

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

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

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

암호화 해시 함수란

암호화 해시 함수 는 이 해시함수의 부분집합으로 역상저항성과 제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가 유출이 되더라도 해커는 역상저항성으로 인해 회원들의 진짜 암호를 알아낼 수 없다.
• 해시테이블에서의 활용.
  • 어떤 데이터의 목록에서 특정 데이터를 조회한다고 생각해보자.
  • 일반적인 방법으로는 데이터를 첫번째 순서부터 하나하나 대조해보거나 특정한 규칙에 따라 순차적으로 각 요소들을 대조하여 특정한 값을 찾아내는 방법이 있다.
  • 해시함수의 충돌저항성을 활용해 데이터를 저장할 때 해당 데이터의 해시값을 별도로 원하는 데이터를 찾아낼 수 있는 '키값' 으로 활용한다면?
  • 각 데이터의 전체값을 비교하지 않고도 일정 길이의 해시값을 이용해 원하는 데이터를 찾아낼 수 있다.
  • 별도의 탐색절차 없이 그 즉시 원하는 데이터를 추출할 수 있으므로 궁극의 탐색 알고리즘이다.
• 블록체인에서 체인의 역할을 함
  • 블록체인의 각 블록은 현재 자신의 해시값과 이전 블록의 해시값을 가지고 있다.
  • Z 블록이 Y 블록의 해시값을 참조하고 Y 블록이 X 블록의 해시값을 참조하여 마치 하나의 사슬처럼 연결이 되는 것이다.
  • 블록 내 데이터(거래이력)가 약간이라도 변조되면 H가 み가 되버리는 눈사태 효과가 나타나게 된다.
    • 실제로 내부 동작구조를 알아보면 어떤 특정 거래의 데이터를 위변조 한다고 가정했을 때, 정말 눈사태처럼 해당 거래건부터 단계별로 타고타고 올라가 최종적으로 블록 해시의 입력값이 완전히 다른 값으로 변화되는 과정을 알아볼 수 있다.
  • 또한, 공격자는 제2역상저항성으로 인해 원하는 의도의 데이터 변조가 불가능하다.
  • 일정 길이의 해시값 만으로 이전 블록의 모든 데이터의 무결성을 보장할 수 있다. (압축효과)
  • 암호화 해시는 이 블록체인의 핵심적인 기술요소로써 역할을 맡고 있다.

취약한 부분과 충돌쌍

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

심지어 SHA1의 경우에도 충돌쌍(똑같은 해시값을 반환하는 서로 다른 데이터의 쌍) 이 아래와 같이 발견된 예시가 있다.
해당 페이지에서는 동일한 SHA1 체크섬을 가진 두 개의 다른 PDF를 예시로 들고 있다.

SHA1 충돌쌍 예시

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

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

생일 역설 Birthday Paradox

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

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

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

아래의 질문에서 출발한다.

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

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

그런데 366명을 하나하나 생일을 물어보고 기록지에 적고 비교하는게 너무 힘든데, 보다 적은 수의 사람을 모아서 비슷한 결과(한 확률적으로 97% 정도)를 낼 수는 없을까?

그럼 대체 임의로 모인 사람들 중에서 생일이 중복되는 사람이 한 쌍 이상 나올 확률이 97%가 되려면 최소 몇 명의 사람이 모여야 되는 것일까?

정답은 놀랍게도 50명 뿐이 필요하지 않다는 것이다.

100%가 되려면 366명이 필요하던 것이 불과 3% 의 확률적 손실밖에 없음에도 그 대상의 수는 50명으로 줄었다.

그럼 이번엔 확률의 목표값을 설정하는데 있어서 97%도 지나치게 높으니까 그냥 두 번 조사했을 때 한 번만 나와도 되게끔 50% 정도로만 목표를 낮춰보겠다고 하자.

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

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

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

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

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

그럼에도 불구하고

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

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

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

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

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

SHA1의 경우 160bit의 출력값을 가지는데, 앞서 링크된 충돌쌍을 찾아내는데 있어서 약 9경번의 연산이 필요했으며, 수억원의 가치에 상응하는 컴퓨팅 비용이 필요했다고 한다. (가성비가 0에 수렴한다는 이야기다)

고로, 일상적인 경우에서 이용하는데 있어서는 크게 무리가 없다는 이야기 정도로 결론 지으면 될 것 같다.

종류와 선택

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

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

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

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

완벽에 가까운 역상저항성과 충돌저항성이 필요하지 않으며 단순 파일 체크섬 생성 등의 용도로만 필요한 경우 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을 사용한다.

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

비트코인에서 작업증명(채굴에 성공해서 비트코인을 버는 것) 하는게 해시값에서 원본을 정확히 찾아내는 것보다 훨씬 더 쉽다.

결론은 그냥 특별할거 없으면 SHA2 를 쓰자.

LSH 국산 해시 암호화 함수

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

LSH(Lightweight Secure Hash)

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

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