해시 함수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 특징
3. 해시 함수의 종류
- 3.1. 암호학적 해시 함수
- 3.2. 비암호학적 해시 함수
4. 해시 함수의 응용
5. 한계 및 주의사항
6. 한국 정보보호 관련 법규 및 정책
참조

1. 개요

해시 함수는 임의의 길이의 데이터를 고정된 길이의 값으로 변환하는 함수로, 데이터의 무결성 검증, 비밀번호 보안, 캐싱, 블룸 필터 등 다양한 분야에 활용된다. 해시 함수는 균일성, 계산 효율성, 결정성, 고정 출력 크기 등의 특징을 가지며, 암호학적 해시 함수와 비암호학적 해시 함수로 분류된다. 해시 함수는 해시 테이블과 함께 사용되어 데이터 저장 및 검색에 사용되며, 파일 무결성 검사, 키 파생, 메시지 인증 코드 생성, 비밀번호 저장, 디지털 서명 등에도 활용된다. 그러나 해시 함수는 충돌 발생 가능성, DoS 공격 취약성 등의 한계를 가지며, 안전한 사용을 위해 주의가 필요하다.

더 읽어볼만한 페이지

오류 검출 정정 - 부호 이론
부호 이론은 정보를 효율적으로 표현하고 오류를 감지 및 수정하는 기술을 연구하며, 소스 부호화, 채널 부호화, 암호 부호화 등으로 발전하여 CD, 모뎀, 휴대폰 등 다양한 분야에 응용된다.
오류 검출 정정 - 비터비 알고리즘
비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다.
검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.

해시 함수
개요
유형	알고리즘
분야	컴퓨터 과학
목적	임의 크기의 데이터를 고정 크기 값으로 매핑
상세 정보
속성	결정론적 효율적
이상적인 속성	균일성 충돌 저항성 역상 저항성 제2 역상 저항성
응용 분야	데이터 구조 암호학 데이터 무결성 검사
주요 내용
해시 테이블	데이터 검색 속도 향상 평균 시간복잡도 O(1)
암호학적 해시 함수	암호학에서 데이터 보안 및 무결성 검증 예시: SHA-2, SHA-3, Blake
충돌	해시 함수가 서로 다른 입력값에 대해 동일한 해시값을 생성하는 현상
충돌 해결	분리 연결법 개방 주소법
예시
간단한 해시 함수	입력 값을 테이블 크기로 나눈 나머지
암호학적 해시 함수	SHA-256 MD5
해시 함수 설계 고려 사항
균일성	모든 입력 값이 해시 테이블 전체에 균등하게 분포되도록 설계
효율성	계산 속도가 빠르고 시스템 자원 소모가 적도록 설계
충돌 저항성	서로 다른 입력 값에 대해 동일한 해시 값을 생성할 확률을 최소화
역사
기원	데이터 검색 및 정렬 알고리즘에서 유래
발전	암호학 및 데이터 무결성 검증 분야로 확장

2. 특징

해시 함수는 같은 종류의 자료를 묶어서 파악할 수 있게 해주며, 다음과 같은 주요 특징을 가진다.

가변 길이 입력을 고정 길이 값으로 변환: 해시 함수는 다양한 길이의 입력을 받아 머신 워드 길이 이하의 고정된 길이의 값으로 변환한다. 이 과정에서 패리티 함수와 같은 연산자를 사용하여 키의 비트를 섞어 결과 값이 키 공간 전체에 균일하게 분산되도록 한다.^[4]
빠른 계산 속도: 좋은 해시 함수는 계산 속도가 매우 빨라야 하며, 출력 값의 중복 (해시 충돌)을 최소화해야 한다.^[4]
균등한 분포: 좋은 해시 함수는 예상되는 입력을 출력 범위에 가능한 한 균등하게 매핑해야 한다. 즉, 출력 범위의 모든 해시 값은 대략 동일한 확률로 생성되어야 한다.^[4]
최소 충돌: 해싱 기반 방법의 비용은 동일한 해시 값에 매핑되는 입력 쌍인 ''충돌''의 수가 증가함에 따라 급격히 증가하므로, 충돌을 최소화하는 것이 중요하다.
결정성: 해시 함수는 결정적이어야 한다. 즉, 주어진 입력 값에 대해 항상 동일한 해시 값을 생성해야 한다. 이는 수학적 의미에서 해싱될 데이터의 함수여야 함을 의미한다.^[10]
고정 길이 출력 (선택 사항): 많은 응용 분야에서 해시 값의 출력 크기를 고정하는 것이 바람직하다. 예를 들어, 출력을 32비트 정수 값으로 제한하면 해시 값을 배열의 인덱스로 사용할 수 있다. 이러한 해싱은 데이터 검색 속도를 높이는 데 일반적으로 사용된다.^[11]
동적 해시 테이블 지원: 해시 함수가 프로그램 실행을 넘어서는 해시 테이블에 값을 저장하는 데 사용되고, 해시 테이블을 확장하거나 축소해야 할 때 해당 해시 테이블을 동적 해시 테이블이라고 한다. 테이블 크기를 조정할 때 최소한의 레코드를 재배치하는 해시 함수가 바람직하다.

3. 해시 함수의 종류

해시 함수는 사용 목적에 따라 다양한 알고리즘이 존재한다. 좋은 해시 함수는 계산 속도가 매우 빨라야 하고, 출력 값의 중복 (해시 충돌)을 최소화해야 한다. 또한, 효과적인 기능을 위해 유리한 확률 분포를 생성하여 거의 상수 시간에 접근할 수 있도록 한다.^[4]

해시 함수는 해시 테이블과 함께 데이터 항목 또는 데이터 레코드를 저장하고 검색하는 데 사용된다. 각 데이터 또는 레코드와 관련된 키를 해시 코드로 변환하며, 이 해시 코드는 해시 테이블을 인덱싱하는 데 사용된다.^[6]

특수한 경우, 키를 미리 알고 있고 키 집합이 정적인 경우, 절대적(또는 무충돌) 균등성을 달성하는 해시 함수를 찾을 수 있다. 이러한 해시 함수를 ''완전''하다고 하며, 유니버설 해시 함수도 참고할 수 있다.

자료 저장 및 검색 애플리케이션에서 해시 함수를 사용하는 것은 검색 시간과 데이터 저장 공간 사이의 절충이다. 대부분의 경우 해시 함수는 최소한의 대기 시간으로 계산되어야 하며, 그 다음으로 최소한의 명령 수로 계산되어야 한다. 충돌은 드물게 발생하고 부가적인 지연을 발생시키지만, 해가 없기 때문에, 계산이 더 복잡하고 충돌을 약간 줄이는 해시 함수보다 더 빠른 해시 함수를 선택하는 것이 보통 더 좋다.

키를 반복적으로 해싱하고 해시 함수가 비용이 많이 드는 경우, 해시 코드를 미리 계산하여 키와 함께 저장하여 계산 시간을 절약할 수 있다. 해시 코드가 일치한다는 것은 거의 확실하게 키가 동일하다는 의미이다.

3. 1. 암호학적 해시 함수

암호학적 해시 함수는 데이터의 무결성과 보안을 위해 사용되는 해시 함수이다. 주어진 출력에 대해 해당 출력으로 사상되는 입력을 찾는 것이 계산적으로 불가능하고, 주어진 입력에 대해 같은 출력으로 사상되는 다른 입력을 찾는 것이 계산적으로 불가능하다는 성질을 만족한다. 임의의 비트열을 고정된 길이의 비트열로 변환하며, 제3자는 짧은 길이의 데이터로부터 원래 데이터를 복구할 수 없고, 동일한 출력을 갖는 서로 다른 데이터를 찾을 수 없어야 한다.^[9]

암호학적 해시 함수는 다음과 같은 다양한 분야에 응용된다.^[9]

'''무결성 검사''': 서로 다른 파일에 대해 동일한 해시 값은 동일성을 의미하며, 파일 수정 사항을 감지하는 신뢰할 수 있는 수단을 제공한다.
'''키 파생''': 작은 입력 변경은 임의적으로 보이는 출력 변경을 초래하며, 이는 확산 속성으로 알려져 있다. 따라서 해시 함수는 키 파생 함수에 유용하다.
'''메시지 인증 코드(MAC)''': 기밀 키를 입력 데이터와 통합하여 해시 함수는 HMAC와 같이 데이터의 진위 여부를 보장하는 MAC을 생성할 수 있다.
'''비밀번호 저장''': 비밀번호의 해시 값은 어떠한 비밀번호 세부 정보도 노출하지 않으므로 서버에 해시된 비밀번호를 안전하게 저장하는 것이 중요하다.
'''서명''': 전체 메시지가 아닌 메시지 해시가 서명된다.

SHA와 같은 암호화 해시 함수는 체크섬이나 핑거프린트보다 강력한 균일성을 보장하므로, 범용 해시 함수로도 최적이다. 그러나 암호화 등의 용도 외에는 계산 비용이 높기 때문에 이점이 상쇄된다^[30]。 하지만 악의적인 사용자가 키를 선택하더라도 해시값이 균일하게 분포한다는 특성이 있다. 이 때문에 DoS 공격으로부터 서비스를 보호하는 데 도움이 되기도 한다.

3. 2. 비암호학적 해시 함수

비암호학적 해시 함수는 데이터 검색 속도 향상, 중복 데이터 검출 등 보안보다는 효율성을 중시하는 용도로 사용된다. 이러한 해시 함수는 다음과 같은 특징을 갖는다.

속도: 계산 속도가 매우 빨라야 한다.
충돌 최소화: 출력 값의 중복(해시 충돌)을 최소화해야 하지만, 암호학적 해시 함수만큼 엄격하지는 않다.
균등 분포: 예상되는 입력을 출력 범위에 가능한 한 균등하게 매핑해야 한다. 즉, 출력 범위의 모든 해시 값은 대략 동일한 확률로 생성되어야 한다.

해시 함수는 해시 테이블과 함께 데이터 항목 또는 데이터 레코드를 저장하고 검색하는 데 사용된다.^[6] 해시 함수는 각 데이터 또는 레코드와 관련된 키를 해시 코드로 변환하며, 이 해시 코드는 해시 테이블을 인덱싱하는 데 사용된다.

특수한 경우, 키를 미리 알고 있고 키 집합이 정적인 경우, 절대적(또는 무충돌) 균등성을 달성하는 해시 함수를 찾을 수 있다. 이러한 해시 함수를 ''완전''하다고 한다. 유니버설 해시 함수도 참조.

자료 저장 및 검색 애플리케이션에서 해시 함수를 사용하는 것은 검색 시간과 데이터 저장 공간 사이의 절충이다. 대부분의 애플리케이션에서 해시 함수는 최소한의 대기 시간으로 계산되어야 하며, 그 다음으로 최소한의 명령 수로 계산되어야 한다.

충돌은 드물게 발생하고 부가적인 지연을 발생시키지만, 해가 되지는 않으므로, 계산이 더 복잡하고 충돌을 약간 줄이는 해시 함수보다 더 빠른 해시 함수를 선택하는 것이 보통 더 좋다.

키를 반복적으로 해싱하고 해시 함수가 비용이 많이 드는 경우, 해시 코드를 미리 계산하여 키와 함께 저장하여 계산 시간을 절약할 수 있다. 해시 코드가 일치한다는 것은 거의 확실하게 키가 동일하다는 의미이다.
주요 비암호학적 해시 함수 종류

제곱 중간 방법: 입력을 제곱하고 적절한 수의 중간 숫자 또는 비트를 추출한다.
나눗셈 방법: 키에 모듈로 함수를 사용하는 것으로, 테이블 크기에 가까운 소수인 제수를 선택한다.
곱셈 해싱: 공식을 사용하며, 값은 와 상호 소수 관계를 가지도록 적절하게 선택된 값이다. 피보나치 해싱은 곱셈 해싱의 한 형태이다.
표 계산 해싱 (조브리스트 해싱): 표 조회와 XOR 연산을 결합하여 보편적인 해시 함수 패밀리를 구성하는 방법이다.
PJW 해시: 문자열의 모든 문자의 정수 값을 더하거나, XOR 연산을 하는 방식이다.
유니버설 해싱: 해시 함수를 그러한 함수들의 집합 중에서 선택하는 랜덤 알고리즘으로, 두 개의 서로 다른 키의 충돌 확률이 이 되도록 한다.
퍼지 해싱: 유사성을 기반으로 데이터를 비교하는 해싱 방법이다. 지각 해싱도 퍼지 해싱의 일종이다.
기하학적 해싱: 모든 입력 집합은 일종의 거리 공간이며, 해싱 함수는 해당 공간을 '셀' 격자로 분할하는 것으로 해석할 수 있다.

이 외에도 다양한 비암호학적 해시 함수들이 존재하며, 응용 분야와 데이터 특성에 따라 적절한 해시 함수를 선택하는 것이 중요하다.

4. 해시 함수의 응용

해시 함수는 다양한 분야에서 활용되며, 특히 암호학에서 중요한 역할을 한다. 주요 응용 분야는 다음과 같다.^[9]

무결성 검사: 서로 다른 파일이 동일한 해시 값을 가지면 두 파일이 동일하다는 것을 의미한다. 따라서 해시 값을 비교하여 파일의 수정 여부를 확인할 수 있다.
메시지 인증 코드 (MAC): 기밀 키를 입력 데이터와 함께 해시 함수에 넣어 HMAC와 같은 MAC을 생성하여 데이터의 진위 여부를 확인할 수 있다.
비밀번호 저장: 비밀번호를 그대로 저장하는 대신 해시 값을 저장하여 보안을 강화한다. 해시 함수는 비가역적 변환이므로 해시 값으로부터 원래 비밀번호를 알아내기 어렵다.
서명: 전체 메시지 대신 메시지의 해시 값에 서명하여 효율성을 높인다.

해시 함수는 데이터 무결성 검증에도 사용된다. 파일의 해시 값을 계산하여 원래의 해시 값과 비교하면 데이터 변경 여부를 알 수 있다.^[9] 단순한 해시 함수는 쉽게 같은 해시 값을 만들 수 있으므로, 안전한 해시 함수를 사용해야 데이터 위조 및 변조를 막을 수 있다.

이 외에도 해시 함수는 중복 레코드 검출, 유사 레코드 검색 등 다양한 분야에서 활용된다.

중복 레코드 검출: 큰 파일에서 중복 레코드를 찾을 때, 해시 함수를 사용하여 각 레코드의 해시 값을 계산하고 비교하여 중복 여부를 빠르게 판별할 수 있다.^[26]
유사 레코드 검색: 음성 파일, 문서, 유전자 데이터베이스 등에서 유사한 항목을 찾을 때, 유사한 키에 대해 비슷한 해시 값을 생성하는 해시 함수를 사용하여 검색 속도를 높일 수 있다.^[26]

4. 1. 해시 테이블

해시 테이블에서 해시 함수는 데이터나 레코드를 식별하는 키를 입력받아 데이터 저장 및 검색에 사용한다. 키는 고정 길이(정수 등) 또는 가변 길이(이름 등)일 수 있으며, 때로는 키 자체가 데이터이기도 하다. 출력은 해시 테이블을 인덱싱하는 데 사용되는 해시 코드이다.

해시 함수는 다음과 같은 세 가지 기능을 수행한다.

가변 길이 키를 고정 길이 값으로 변환한다. (예: 머신 워드 길이 이하)
키의 비트를 섞어 결과 값이 키 공간 전체에 균일하게 분산되도록 한다.
키 값을 테이블 크기보다 작거나 같게 매핑한다.

좋은 해시 함수는 계산 속도가 빠르고, 출력 값의 중복(해시 충돌)을 최소화해야 한다. 좋은 확률 분포를 생성하여 거의 상수 시간에 접근할 수 있도록 한다. 하지만 높은 테이블 로딩 팩터, 병리적 키 집합, 잘못 설계된 해시 함수는 접근 시간을 선형에 가깝게 만들 수 있다. 해시 함수는 최악의 경우에도 좋은 성능을 제공하고, 높은 테이블 로딩 팩터에서도 잘 작동하며, 특수한 경우에는 키를 해시 코드로 완벽하게 매핑할 수 있도록 설계할 수 있다. 구현은 패리티 보존 비트 연산(XOR 및 ADD), 곱셈 또는 나눗셈을 기반으로 한다. 충돌 해결을 위해 연결 리스트와 같은 보조 데이터 구조를 사용하거나 빈 슬롯을 찾기 위해 테이블을 체계적으로 조사하는 방법이 사용된다.

해시 함수는 해시 테이블과 함께 데이터 항목 또는 레코드를 저장하고 검색하는 데 사용된다. 해시 함수는 키를 해시 코드로 변환하고, 이 해시 코드는 해시 테이블을 인덱싱하는 데 사용된다. 항목을 테이블에 추가할 때 해시 코드가 빈 슬롯을 인덱싱하면 해당 항목이 추가된다. 꽉 찬 슬롯을 인덱싱하면 충돌 해결이 필요하다. 새 항목을 생략하거나, 이전 항목을 대체하거나, 다른 위치에 추가할 수 있다.

해시 테이블의 충돌 해결 방법은 다음과 같다.

체인 해싱: 각 슬롯은 연결된 목록의 헤드이며, 충돌하는 항목은 체인에 추가된다. 체인은 임의의 순서로 유지되거나, 선형적으로 검색되거나, 자체 정렬 목록으로 유지될 수 있다.
개방 주소 해싱: 테이블은 지정된 방식으로 점유된 슬롯에서 시작하여 열린 슬롯이 발견되거나 전체 테이블이 탐사될 때까지 조사된다. (일반적으로 선형 탐사, 2차 탐사, 이중 해싱)

해시 함수는 느린 매체에 저장된 대규모 데이터 집합에 대한 캐시를 구축하는 데에도 사용된다. 또한 블룸 필터의 필수 요소이며, 확률적인 자료 구조로, 요소가 집합의 구성원인지 테스트하는 데 사용된다.

해싱의 특수한 경우는 기하학적 해싱("격자 방법")이다. 입력 집합이 거리 공간이고, 해싱 함수는 해당 공간을 '셀' 격자로 분할하는 것으로 해석할 수 있다. 테이블은 둘 이상의 인덱스를 가진 배열(그리드 파일, 그리드 인덱스, 버킷 그리드 등)이며, 해시 함수는 인덱스 튜플을 반환한다. 이 원리는 컴퓨터 그래픽스, 계산 기하학 등에서 근접성 문제를 해결하는 데 사용된다. (예: 최근접 쌍 찾기, 유사한 모양 찾기, 이미지 데이터베이스에서 유사한 이미지 찾기)

해시 테이블은 연관 배열과 동적 집합을 구현하는 데에도 사용된다.^[6] 자료 저장 및 검색 애플리케이션에서 해시 함수를 사용하는 것은 검색 시간과 데이터 저장 공간 사이의 절충이다. 해시 함수는 잠재적으로 큰 키 공간을 유한한 시간 내에 계산 가능한 저장 공간으로 매핑하여 제한된 시간 내에 검색할 수 있게 한다.

계산 복잡성은 필요한 명령 수와 개별 명령의 대기 시간에 따라 달라진다. 비트 단위 방법(접기)이 가장 간단하고, 곱셈 방법이 그 다음이며, 나눗셈 기반 방법이 가장 복잡하다. 충돌이 드물기 때문에, 계산이 더 빠른 해시 함수를 선택하는 것이 좋다.

나눗셈 기반 구현은 상수의 워드 크기 곱셈 역수로 곱셈으로 변환될 수 있다. 보다 훨씬 작을 때, 구간 에서 균일한 해시 함수는 이다. (는 구간 에서 균일한 의사 난수 생성기 함수)

해시 함수는 해시 테이블에서 주어진 검색 키로부터 빠르게 데이터 레코드를 찾는 데 사용된다. 해시 함수는 검색 키를 해시에 매핑하고, 해시는 레코드 저장 위치의 인덱스로 사용된다. 해시 테이블은 연관 배열이나 동적 집합 구현에도 사용된다.

일반적으로 여러 키가 동일한 인덱스에 매핑될 수 있다. 따라서 해시 테이블의 각 슬롯은 단일 레코드가 아니라 레코드 집합에 해당한다. 각 슬롯을 "버킷", 해시 값을 "버킷 인덱스"라고도 한다. 해시 함수는 레코드 위치에 대한 힌트일 뿐이며, 시작점을 알려준다. 좋은 해시 함수를 사용하면 검색 대상을 한두 개 항목으로 줄일 수 있다.

4. 2. 데이터 무결성 검증

해시 함수는 데이터의 무결성을 검증하는 데 사용된다. 파일이나 데이터의 해시 값을 계산하고, 이를 원래의 해시 값과 비교하여 데이터가 변경되었는지 여부를 확인할 수 있다. 서로 다른 파일에 대해 동일한 해시 값은 동일성을 의미하며, 파일 수정 사항을 감지하는 신뢰할 수 있는 수단을 제공한다.^[9] 예를 들어, 어떤 문서가 정확한지 검증하고 싶지만, 해당 문서 자체를 기록·비교하고 싶지 않은 경우, 문서를 대표하는 수치(문서의 요약)를 수학적으로 만들어 이 요약만 기록하고 비교하면 된다. 이러한 요약을 만드는 조작이 해시화이다.

하지만, 단순한 해시 함수 알고리즘을 사용하면 쉽게 같은 해시값을 구할 수 있으므로, 데이터 위조 및 변조(개찬) 검출을 위해서는 안전하게 설계된 해시 함수를 사용해야 한다.

4. 3. 비밀번호 보안

인증 서버는 비밀번호를 해시화하여 저장하는 것이 권장된다. 비밀번호의 해시 값은 비밀번호 세부 정보를 노출하지 않으므로 서버에 해시된 비밀번호를 안전하게 저장하는 것이 중요하다.^[9] 해시 함수는 비가역 변환이기 때문에 해시 값에서 원래 값을 쉽게 복원할 수 없다. 따라서 서버 내의 인증 정보를 탈취당하더라도 키가 노출될 위험을 줄일 수 있다.

4. 4. 캐시 (Cache)

해시 함수는 느린 매체에 저장된 대규모 데이터 집합에 대한 캐시를 구축하는 데에도 사용된다. 캐시는 해시된 검색 테이블보다 일반적으로 간단하다. 두 개의 충돌하는 항목 중 오래된 항목을 버리거나 다시 쓰면 모든 충돌을 해결할 수 있기 때문이다.^[5]

4. 5. 블룸 필터 (Bloom Filter)

블룸 필터는 확률적인 자료 구조로, 요소가 집합의 구성원인지 테스트하는 데 사용되며, 해시 함수는 블룸 필터의 필수 요소이다.^[5]

4. 6. 기타 응용

해시 함수는 중복 레코드 검출, 유사 레코드 검색, 기하학적 해싱 등 다양한 분야에서 활용된다.

중복 레코드 검출: 정렬되지 않은 큰 파일에서 중복 레코드를 찾을 때, 해시 함수를 이용해 각 레코드의 해시 값을 구한다. 같은 해시 값을 가진 레코드들을 같은 버킷에 모아 비교하여 중복 여부를 빠르게 판별한다. 이 방식은 파일을 정렬 후 인접 레코드를 비교하는 것보다 효율적이다.^[26]

유사 레코드 검색: 키가 비슷하지만 완전히 같지 않은 레코드를 찾을 때도 해시 함수가 유용하다. 유사한 키에 대해 비슷한 해시 값을 만드는 해시 함수를 쓰면, 유사한 레코드들이 같은 버킷이나 근처 버킷에 저장되어 검색이 빨라진다. 이 기술은 음성 파일에서 유사 항목을 찾거나, 문서 저장소, 유전자 데이터베이스 등에서 동일하거나 유사한 부분을 찾는 데 쓰인다.^[26]

기하학적 해싱: 입력 집합을 거리 공간으로 보고, 해시 함수로 공간을 격자 형태로 나누는 방법이다. 컴퓨터 그래픽스, 계산 기하학 등에서 근접성 문제를 해결하는 데 사용된다. 예를 들어 평면이나 3차원 공간에서 점들 중 가장 가까운 쌍을 찾거나, 도형 목록에서 비슷한 도형을 찾거나, 이미지 데이터베이스에서 유사한 이미지를 찾는 데 활용된다.^[26]

기타 응용:
블룸 필터의 핵심 요소로, 어떤 요소가 집합에 속하는지 검사하는 확률적 자료 구조이다.
연관 배열, 동적 집합 구현에도 사용된다.^[6]
라빈-카프 문자열 검색 알고리즘은 문자열 비교에 해시 함수를 써서 평균 O(n) 시간에 작동하는 빠른 문자열 검색 알고리즘이다.
벡터 양자화에 사용되어 다차원 신호를 부호화하고 압축한다.

5. 한계 및 주의사항

해시 함수는 임의의 비트열을 고정된 길이의 비트열로 변환하는 함수이다. 이때, 주어진 출력값으로 사상되는 입력값을 찾는 것이 계산적으로 불가능해야하고, 주어진 입력값에 대해 동일한 출력값으로 사상되는 다른 입력값을 찾는 것도 계산적으로 불가능해야 한다. 해시 함수 알고리즘은 긴 데이터를 짧은 데이터로 변환하므로, 제3자는 이 짧은 데이터로부터 원래의 데이터를 복구할 수 없어야 하며, 동일한 출력을 갖는 서로 다른 데이터를 찾을 수 없어야 한다.

하지만 해시 함수에는 한계와 주의사항이 존재한다. 서로 다른 두 입력값이 동일한 해시값을 가지는 경우를 충돌이라고 하는데, 이는 해시 함수의 성능 저하 및 보안 취약점을 야기할 수 있다. 또한, 의도적인 충돌을 통해 (DoS) 공격에 취약할 수 있다.

5. 1. 충돌 (Collision)

해시 함수의 입력값을 "키(key)"라고 부른다. 둘 이상의 키가 동일한 해시값을 가질 수 있는데, 이를 충돌이라고 한다. 대부분의 경우 충돌 발생을 최소한으로 억제하는 것이 바람직하다. 따라서 해시값의 출현 빈도는 균일하게 설계해야 한다.^[4]

서로 다른 두 키의 해시값이 같은 경우를 충돌이라고 하며, 충돌은 해시 함수의 성능 저하를 유발한다. 또한 동일한 해시값을 가지는 데이터를 찾을 수 없어야 한다는 점에서 보안 취약점을 야기할 수 있다.

5. 2. 해시 함수의 안전성

암호학적 해시 함수의 안전성은 다음 세 가지 주요 성질로 평가된다.

원상 계산 저항성 (Preimage Resistance): 주어진 해시 값에 대해, 그 값을 생성하는 원래 입력을 찾는 것이 계산적으로 어려워야 한다. 즉, 해시 함수는 일방향 함수여야 한다.
제2 원상 계산 저항성 (Second Preimage Resistance): 주어진 입력 값에 대해, 동일한 해시 값을 생성하는 다른 입력 값을 찾는 것이 계산적으로 어려워야 한다.
충돌 저항성 (Collision Resistance): 동일한 해시 값을 생성하는 서로 다른 두 입력 값을 찾는 것이 계산적으로 어려워야 한다.

이 세 가지 성질 사이에는 포함 관계가 성립한다.

: 원상 계산 어려움 ⊃ 제2 원상 계산 어려움 ⊃ 충돌 어려움

즉, 원상 계산 저항성이 가장 강력한 조건이며, 충돌 저항성이 가장 약한 조건이다. 해시 함수에 충돌이 많으면 원상 계산이 어려워도 해시값을 통해 임의의 입력을 얻을 수 있으므로 제2 원상 계산이 어렵지 않다. 또한 제2 원상 계산이 어렵지 않으면 충돌 저항성을 만족시키지 못한다.^[9]

5. 3. DoS 공격 취약성

해시 함수는 의도적인 충돌을 통해 서비스 거부 공격(DoS)에 취약할 수 있다. 해시 테이블의 특성상 동일한 해시 값을 갖는 데이터가 많아질수록, 즉 충돌이 증가할수록 검색 효율이 급격히 떨어진다. 공격자는 이 점을 악용하여 의도적으로 충돌을 많이 발생시키는 데이터를 입력하여 서버의 성능을 저하시키거나 마비시킬 수 있다.^[30]

이러한 DoS 공격을 방지하기 위해서는 충돌 발생 확률이 낮은, 즉 균일성이 더 강력하게 보장되는 해시 함수를 사용해야 한다. SHA와 같은 암호화 해시 함수는 일반적인 해시 함수보다 계산 비용이 높지만, 악의적인 사용자가 충돌을 유발하기 어렵도록 설계되어 DoS 공격 방지에 효과적이다.^[30]

6. 한국 정보보호 관련 법규 및 정책

주어진 원본 소스에는 "한국 정보보호 관련 법규 및 정책"에 대한 내용이 없으므로, 이전 답변과 동일하게 해당 섹션은 작성할 수 없습니다.

참조

_[1] conference Hash_RC6 — Variable length Hash algorithm using RC6 https://ieeexplore.i[...] 2023-01-24
_[2] 웹사이트 NIST Glossary — hash digest https://csrc.nist.go[...] 2024-01-01
_[3] 서적 The Art of Computer Programming, Vol. 3, Sorting and Searching Addison-Wesley 1973
_[4] 문서 This is useful in cases where keys are devised by a malicious agent, for example in pursuit of a DOS attack.
_[5] 웹사이트 Understanding CPU caching and performance https://arstechnica.[...] 2022-02-06
_[6] 서적 Handbook of Applied Cryptography https://archive.org/[...] CRC Press
_[7] journal The strict avalanche criterion randomness test Elsevier 2005-02-03
_[8] 웹사이트 Fibonacci Hashing: The Optimization that the World Forgot https://probablydanc[...] 2018-06-16
_[9] Citation Hash Functions Springer Nature Switzerland 2023
_[10] 웹사이트 3. Data model — Python 3.6.1 documentation https://docs.python.[...] 2017-03-24
_[11] 서적 Algorithms in Java Addison Wesley
_[12] 문서 Plain ASCII is a 7-bit character encoding, although it is often stored in 8-bit bytes with the highest-order bit always clear (zero). Therefore, for plain ASCII, the bytes have only 2⁷ = 128 valid values, and the character translation table has only this many entries.
_[13] 문서 For example, for n=15, k=4, t=6, $S=\{1,2,3,4,5,6,8,10,12,9\}$ [Knuth]
_[14] 문서 Knuth conveniently leaves the proof of this to the reader.
_[15] journal Unique permutation hashing
_[16] 웹사이트 CS 3110 Lecture 21: Hash functions http://www.cs.cornel[...]
_[17] 문서 Unisys large systems.
_[18] tech report A New Hashing Method with Application for Game Playing https://www.cs.wisc.[...] Computer Sciences Department, University of Wisconsin 1970-04
_[19] 서적 Compilers: Principles, Techniques and Tools Addison-Wesley 1986
_[20] conference Performance in Practice of String Hashing Functions https://citeseer.ist[...] 2021-12-06
_[21] 서적 A Handbook of Algorithms https://books.google[...] N.B. Singh
_[22] 서적 The Art of Computer Programming, Vol. 3, Sorting and Searching Addison-Wesley 1975
_[23] tech report Expected Length of the Longest Probe Sequence in Hash Code Searching University of Waterloo 1978
_[24] 서적 The Art of Computer Programming, Vol. 3, Sorting and Searching Addison-Wesley 2000
_[25] 웹사이트 https://kotobank.jp/[...]
_[26] 웹사이트 Robust Audio Hashing for Content Identification http://citeseerx.ist[...]
_[27] 웹사이트 Hash Functions http://bretm.home.co[...] 2009-04-11
_[28] 문서 Some applications of Rabin's fingerprinting method Springer-Verlag
_[29] 웹사이트 Evaluation of CRC32 for Hash Tables http://home.comcast.[...] 2009-04-10
_[30] 웹사이트 Evaluation of SHA-1 for Hash Tables http://home.comcast.[...] 2009-04-10
_[31] 서적 The Art of Computer Programming, volume 3, Sorting and Searching

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com