임의의 크기를 가진 값을 고정 크기의 값에 대응시키는 함수
입력값이 같으면 언제나 출력값도 같아야 한다(결정론적 작동)
사용
해시 테이블에서 데이터를 저장할 위치를 찾기 위해
길이가 긴 데이터 둘을 빨리 비교하기 위해
패스워드 같은 누출되면 곤란한 데이터의 원본을 저장하지 않기 위해
용도에 따라 해시 알고리듬의 요구사항이 조금씩 달라질 수 있음
속성
균일성(uniformity)
해시 함수의 출력값이 고르게 분포될수록 균일성이 높음
훌륭한 해시 함수는 균일성이 높다(해시 충돌이 적음을 의미, 균등 분포)
완벽한 해시 함수로 해시 충돌이 전혀 없는 함수(입력값이 매우 제한적인 경우에 해당)
균일성을 높이기 위한 방법
해시값이 덜 중복되게 버킷 수를 정할 것(소수 사용)
눈사태가 나도록 해시 함수 설계
눈사태 효과
입력값이 약간만 바뀌어도 출력값이 굉장히 많이 바뀌는 것
암호학적 알고리듬이 선호, 알고리듬의 규칙을 쉽게 유추하기 어려움
엄격한 눈사태 기준
입력값에서 1비트를 뒤집으면 출력값의 각 비트가 뒤집힐 확률 50%
균일성이 높다고 무조건 좋지는 않다
지역 민감 해시(locality-sensitive-hashing)
해시 충돌의 최소화 대신 최대화를 목표로 하는 알고리듬
비슷한 내용을 가진 데이터 끼리 충돌이 필요한 경우
빅데이터에서 비슷한 것들을 찾는 용도
스팸 메일, 웹 문서 추천, 저작권 침해 등
효율성(efficiency)
보통 빠른 해시 함수 선호
공간을 더 낭비해도 빠른 접근 속도 선호(저장된 데이터를 빨리 찾는 해시 함수)
충돌이 좀 더 나더라도 빠른 함수 선호(해시 충돌은 드물고 몇 번의 충돌로 속도 저하가 심하지 않음)
암호학적 해시 함수에서 하드웨어 가속이 어려운 해시를 선호하기도 함(비밀번호 깨기 막는 용도)
분류
비암호학적 해시 함수
안전하지 않은 해시 함수
보안적으로 문제없는 용도에 주로 사용(데이터 저장 및 찾기, 데이터 오류 탐지, 고유 ID 생성)
최고의 결과를 보장하는 해시 함수는 존재하지 않으며 필요에 따른 해시 함수를 찾아 사용
입력값에 따라 다른 해시 함수를 사용하는 확률적 알고리즘은 존재(유니버셜 해싱)
체크섬(checksum)
여러 데이터로 도출한 작은 크기의 데이터 하나
해시 함수와 비슷한 개념, 출력 값 크기가 고정 = 해시 함수
저장 전송 중 발생한 오류를 찾음
체크섬 플로우
1.처음 데이터 저장시 체크섬 계산하여 저장
2.데이터를 읽는 곳에서 위 계산방법과 동일하게 체크섬 계산하여 비교
3.체크섬 값 비교하여 다르면 오류
CRC
체크섬 알고리듬 중 하나
다항식의 나머지 연산을 이용하여 검사값을 만듦
다항식의 최고차항에 따라 CRC 에 사용하는 비트 수가 달라짐
각 항의 계수는 1 or 0, 최고차항의 계수는 언제나 1
흔히 사용하는 CRC 알고리즘으로 CRC-8,16,32,64
암호학적 해시 함수
해시값에서 원본 값을 찾는게 사실상 불가능한 알고리듬
원본 값을 찾으려면 모든 조합을 시도(무차별 대입 공격)
보안 분야에서 다양한 용도로 사용
디지털 서명 생성 및 검증, 비밀번호 검증, 일반 해시 알고리듬 대신 사용 가능(느림), 등...
추가 속성
역상 저항성 : 해시값으로 원본 데이터를 찾기 어려워야 함
제2 역상 저항성 : 똑같은 해시값이 나오는 다른 입력값을 찾기 어려워야 함
충돌 저항 : 해시값이 똑같은 두 입력값을 찾기가 어려워야 함
