Skip to content

Hash function

해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 알고리즘이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 체크섬 또는 해시 등으로 불린다. 해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다) 해시 함수의 질은 입력 영역에서의 해시 충돌 확률로 결정되는데, 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 된다.

해쉬함수중에는 암호학적 해쉬함수(Cryptographic Hash Function)와 비암호학적 해쉬함수로 구분되곤 한다.

암호학적 해쉬함수의 종류로는 MD5, SHA계열 해쉬함수가 있으며 비암호학적 해쉬함수로는 CRC32등이 있다.

암호학적 해쉬함수는 역상(pre-image), 제2역상(2nd preimage), 충돌쌍(collision)에 대하여 안전성을 가져야 하며 인증에 이용된다 . 암호학적 해쉬함수는 임의의 길이를 입력 받기는 하지만 MD Strength Padding할 때 길이정보가 입력되므로 최대 길이에 대한 제한이 있다. 예를 들어 패딩시 하위 8비트에 길이정보가 입력 되는 경우에는 해쉬가능한 최대 길이는 0xFF가 되어 255바이트가 된다.(실제 길이정보는 패딩방식에 따라 다를 수 있다)

Categories

해쉬 함수란 무엇인가?

해쉬 함수 H는 가변크기의 입력 m을 해쉬값 h 라 불리는 고정된 크기의 스트링으로 변화 시켜주는 것이다. 이런 특징을 가지는 해쉬 함수는 다양한 일반적인 계산에 사용된다. 그러나 암호에서 사용될 때 해쉬 함수는 일반적으로 몇 가지 추가된 특징을 가진다.

암호적 해쉬 함수의 기본 필요조건은 아래와 같다.

  • 입력은 어느 길이라도 될 수 있다.
  • 출력은 고정된 길이를 가진다.
  • H(x)는 주어진 어떠한 x에 대해서도 상대적으로 계산하기 쉽다.
  • H(x)는 일 방향(one-way)이다.
  • H(x)는 충돌(collision)이 없다.

해쉬 함수 H는 만약 이것이 역 변환 하기 힘들 다면 일 방향이라 불린다. 여기서 "역 변환하기 힘들다"라는 의미는 주어진 해쉬값 h가 H(x)=h인 주어진 x를 찾는 것이 계산적으로 불가능하다는 것을 말한다. 만약 주어진 메시지 x가 H(x)=H(y)인 메시지 x, y를 찾는 것이 계산적으로 불가능하다면, H는 약한 충돌 없는 해쉬 함수라 불린다. 강한 충돌 없는 해쉬 함수 H는, H(x)=H(y)인 두 메시지 x와 y를 찾아내는 것이 계산적으로 불가능한 경우이다. 해쉬 값은 긴 메시지나 컴퓨터화된 글을 간결하게 표현한다. 긴 글의 "디지털 지문"과 같이 메시지 요약으로 생각할 수 있다. 잘 알려진 해쉬 함수의 예는 MD2와 MD5 그리고 SHA가 있다. 아마도 암호적 해쉬 함수의 주요 역할은 디지털 서명의 준비에 있다. 해쉬 함수가 일반적으로 디지털 서명 알고리즘보다 빠르기 때문에, 글 자체에 비해 작은, 그 글의 해쉬 값에 대한 서명을 계산 함으로서 몇몇 글에 디지털 서명을 계산 하는 것은 표준이다. 게다가, 요약은 이것의 유래로부터 글의 내용을 알려주지 않고 공공연하게 만들 수 있다. 이것은 디지털 날짜기록에 중요하다. 여기서 해쉬 함수를 사용 함으로서 날짜기록 서비스 내용을 나타내지 않고 날짜에 기록된 글을 얻을 수 있다.

메시지의 압축된 새로운 표현인 메시지 다이제스트(message digest)를 생성하는 알고리즘으로,

  • 암호학적 체크섬 (cryptographic checksum).
  • 암호학적 압축 (cryptographic compression) 알고리즘.
  • 메시지 다이제스트(message digest).

각각은 사용 환경에 따라 약간의 의미적 차이는 있으나 해쉬 함수와 거의 유사하다.

해시 충돌 (Hash collision)

해시 충돌이란 전산학에서 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 모든 해시 함수는 아무리 잘 디자인된 해시 함수라도 잠재적인 충돌 가능성을 안고 있다. 해시 충돌은 비교적 적게 일어나거나 비교적 찾아내기 어려워야 한다. 가능한 입력 값의 개수를 미리 알 수 있고, 그 개수가 적은 특정 애플리케이션에서는 모든 입력값을 서로 충돌하지 않는 출력값으로 매핑하는 완전 해시 함수를 만들어내는 것이 가능하다. 그러나 암호화 해시 함수를 포함한 대부분의 해시 함수는 상당히 긴 입력값으로부터 고정된 범위의 출력값을 생성한다. 따라서 이러한 설계에서는 해시 출력 값의 범위보다 훨씬 더 큰 범위의 입력 값을 받기 때문에 언제나 충돌이 발생한다.

이중 해시 (Double hashing)

이중 해시법는 해시 충돌을 해결하기 위한 방법이다. 서로 다른 두 값들이 같은 해시 키를 갖게 되면 해시 충돌이 일어나게 된다. 충돌이 일어난 항목들을 따로 관리하지 않고 해시 테이블의 다른 주소 공간에 배열한다면 어디에 이것을 배열해야 하는지에 대한 문제가 생긴다. 이중 해시법은 다른 해시 함수로 값을 해시하여 그 값만큼을 현재 주소에 더하여 새 주소를 얻는다. 이렇게 되면 충돌시 건너뛰는 너비가 값에 따라 달라지기 때문에 한 해시 값에 뭉치는 경우가 줄어든다. 그리고 운이 나쁜 경우 계속 충돌이 일어나서 탐색 시간이 매우 오래 걸리게 되는 문제가 해결된다.

See also

Favorite site

Guide

implementation

References

  1. Www.partow.net.zip ↩