해시
분류
- 비암호학적 해시함수: 암호학적으로 사용하기에 안전하지 않은 해시함수들
데이터 저장 및 찾기, 저장/ 전송 중에 생긴 데이터 오류 탐지, 고유한 ID 생성 등
모든 데이터에 대해 최고의 결과를 보장하는 해시함수는 존재하지 않는다.
입력값에 따라 다른 해시함수를 사용하는 확률적 알고리즘은 존재(Universal hashing)
용도에 맞는 해시 함수를 사용하는게 중요
- 암호학적 해시함수
응용
- 체크섬(checksum)
- CRC(순환 중복 검사, cyclic redundancy check)
속성
- 효율성(efficiency)
공간을 더 쓰더라도 보통 빠른 해시함수를 선호
충돌이 나더라도 더 빠른 함수를 선호
하지만 하드웨어 가속이 어려운 해시를 선호하기도 함(소프트웨어 적으로는 빠름) - 암호학적 해시
- 균일성(uniformity)
해시함수의 출력값이 고르게 분포될 수록 균일성이 높다.
출력 범위 안의 모든 값들이 동일한 확률로 나오는 것이 좋다(균등분포).
균일성이 높아야 해시충돌이 적어진다.
균일성의 측정
카이제곱(chi-squared test)를 사용
n : 키의 수
m : 버킷 수
bj : 버킷에 들어있는 아이템 수
결과가 0.95~1.05 사이면 균일한 분포를 가진 해시함수
1. 해시값이 덜 중복되게 버킷 수를 정한다
2. 눈사태 효과(Avalanche Effect) : 입력값이 약간만 바뀌어도 출력값이 굉장히 많이 바뀌는 것
- 규칙을 예측하기 어렵게 되서 암호학적 알고리즘이 선호하는 효과
엄격한 눈사태 기준(Strict Avalanche Criterion, SAC)
입력값에서 1비트를 뒤집으면 출력값의 각 비트가 뒤집힐 확률이 50%
이 기준을 충족하는 해시함수는 분포가 균일할 가능성이 높음
지역 민감 해시( locality-sensitive hashing)
해시충돌의 최소화 대신 최대화를 목표로 하는 알고리즘
비슷한 내용을 가진 데이터끼리 충돌해야함
- 엄청나게 많은 데이터에서 비슷한 것들을 찾는 용도
스팸메일 찾기, 비슷한 문서 추천하기, 음원, 사진 등의 저작권 침해 검사 등
암호학적 해시 알고리즘의 속성
- 역상 저항성(pre-image resistance)
- 제 2 역상 저항성(second pre-image resistance)
- 충돌 저항성(collision resistance)