Fowler-Noll-Vo 해시 함수

Fowler-Noll-Vo(또는 FNV)는 Glenn Fowler, Landon Curt Noll 및 Kiem-Phong Vo에 의해 작성된 비암호화 해시 함수입니다.

FNV 해시 알고리즘의 기초는 1991년 Glenn Fowler와 Phong Vo가 IEEE POSIX P1003.2 위원회에 검토자 코멘트로 보낸 아이디어에서 따왔다.그 후의 투표 라운드에서, Landon Curt Noll은 알고리즘을 개선했습니다.랜던에게 보낸 이메일 메시지에서 그들은 그것을 Fowler/Noll/Vo 또는 FNV ^[1]해시라고 명명했다.

개요

현재 버전은 FNV-1 및 FNV-1a로, 0이 아닌 FNV 오프셋을 작성하는 수단을 제공합니다.FNV는 현재 32비트, 64비트, 128비트, 256비트, 512비트 및 1024비트 플레이버가 있습니다.순수 FNV 구현의 경우 이는 원하는 비트 길이에 대한 FNV 프라임 가용성에 의해서만 결정됩니다.단, FNV 웹 페이지에서는 위의 버전 중 하나를 ^[2][3]2의 거듭제곱이 될 수도 있고 아닐 수도 있는 더 작은 길이로 조정하는 방법에 대해 설명합니다.

FNV 해시 알고리즘과 참조 FNV 소스^[4][5] 코드가 퍼블릭도메인에 ^[6]공개되어 있습니다.

Python 프로그래밍 언어는 이전에 수정된 버전의 FNV 스킴을 기본값으로 사용했습니다.hash기능.Python 3.4부터는 "해시 플래딩" 서비스 거부 ^[7]공격에 저항하기 위해 FNV가 SipHash로 대체되었습니다.

FNV는 암호화 ^[4]해시가 아닙니다.

해시

FNV의 주요 장점 중 하나는 구현이 매우 간단하다는 것입니다.FNV 오프셋 기준의 초기 해시 값부터 시작합니다.입력의 각 바이트에 대해 해시에 FNV 소수를 곱한 다음 입력의 바이트로 XOR합니다.대체 알고리즘인 FNV-1a는 곱셈 스텝과 XOR 스텝을 반대로 합니다.

FNV-1 해시

FNV-1 해시 알고리즘은 다음과 같습니다.^[8][9]

알고리즘 fnv-1은 해시할 각 바이트_off_data에 대해 해시:= FNV_offset_basis입니다. 해시:= 해시 × FNV_prime hash:= 해시 XOR 바이트_of_data 반환 해시

위의 의사 코드에서는 모든 변수는 부호 없는 정수입니다.byte_of_data를 제외한 모든 변수는 FNV 해시와 동일한 비트 수를 가집니다.변수 byte_of_data는 8비트 부호 없는 정수입니다.

예를 들어 64비트 FNV-1 해시를 생각해 보겠습니다.

• byte_of_data를 제외한 모든 변수는 64비트 부호 없는 정수입니다.
• 변수 byte_of_data는 8비트 부호 없는 정수입니다.
• FNV_offset_basis 는, 64 비트의 FNV 오프셋 베이스치 14695981039346656037(16 진수에서는 0xcbf29ce484222325)입니다.
• FNV_prime는 64비트의 FNV 프라임 값 1099511628211(16진수에서는 0x100000001b3)입니다.
• 곱셈은 제품의 하위 64비트를 반환합니다.
• XOR은 해시 값의 하위8비트만 수정하는8비트 연산입니다
• 반환되는 해시 값은 64비트 부호 없는 정수입니다.

FNV-1a 해시

FNV-1a 해시는 곱셈과 XOR이 ^[8][10]실행되는 순서만으로 FNV-1 해시와 다릅니다.

알고리즘 fnv-1a는 해시할 각 byte_off_data에 대한 hash:= FNV_basis입니다. hash:= hash XOR byte_of_data hash:= hash × FNV_prime return hash:=

상기의 의사 코드에는, FNV-1 의사 코드에 기재된 것과 같은 전제 조건이 있습니다.순서가 바뀌면 눈사태의 ^[8][11]특성이 약간 좋아지게 되는 것입니다.

FNV-0 해시(사용되지 않음)

FNV-0 해시는 해시 ^[8][12]변수의 초기화 값만으로 FNV-1 해시와 다릅니다.

알고리즘 fnv-0은 해시할 각 byte_of_data에 대해 hash := 0입니다. hash := hash × FNV _ prime hash := hash XOR byte_of_data return hash := hash XOR byte_of_data

상기의 의사 코드에는, FNV-1 의사 코드에 기재된 것과 같은 전제 조건이 있습니다.

해시를 0으로 초기화하면 빈 메시지와 바이트0만으로 구성된 모든 메시지가 길이에 관계없이0 ^[12]으로 해시됩니다.

FNV-0 해시의 사용은 FNV-1 ^[8][12]및 FNV-1a 해시 파라미터로서 사용하는 FNV 오프셋 베이스의 연산 이외에는 권장되지 않는다.

FNV 오프셋 기준

다양한 비트 길이에 대해 몇 가지 다른 FNV 오프셋 기준이 있습니다.이러한 FNV 오프셋 베이스는, ASC 로 표현되는 다음의 32 옥텟으로부터 FNV-0 을 계산하는 것으로 계산됩니다.II:

chongo <랜든 Curt Noll> /\../\

랜든 커트 놀의 대표 대사 중 하나죠이것은 현재 사용되지 않는 FNV-0에 ^[8][12]대한 유일한 실제 용도입니다.

FNV 소수

FNV 소수는 소수이며 다음과 ^[4][13]같이 결정됩니다.

$특정{\displaystyle }$ s$\displaystyle$ s$:$

• ${\displaystyle s{\mathbb{}}^{}}$ Z ${\displaystyle \{\backslash {}^{}}$ \ $displaystyle$s \ $in$\ $mathbb${ $Z }^$ { * } ~ （$$ s 는 정수)
• ${\displaystyle 4\s\11}$

$여기$서 n$\displaystyle$n은 다음과$$ 같습니다.

• ${\displaystyle n=2^{s}}$

$\displaystyle$t는 다음과$$ 같습니다.

• $\displaystyle t=\left\lfloor\frac {5+n}{12}\right\loor}$

메모:${\displaystyle }$($)$ ({$displaystyle\lfloor$ x$\rfloor})$는 플로어 기능입니다.

n비트 FNV 소수는 다음과 같은 형식의 최소 $소수{\displaystyle }$ p$\displaystyle$p입니다$$.

${\displaystyle 256^{t}+2^{8}+\mathrm {b},}$

다음과 같이 합니다.

• ${\displaystyle 0<b<2^{8}}$
• b$(\displaystyle$ b$)$의 이진수 표현에 포함되는1비트 수는 4비트 또는 5비트입니다
• ${\displaystyle p\mod (2^{40}-2^{24}-1)> (2^{24}+2^{8}+2^{7})}$

실험적으로 상기 제약조건과 일치하는 FNV 프라임은 더 나은 분산 특성을 갖는 경향이 있다.FNV 프라임이 중간 해시 값을 곱할 때 다항식 피드백 특성을 개선합니다.따라서 생성된 해시 값은 n비트 해시 ^[4][13]공간 전체에 더 분산됩니다.

FNV 해시 파라미터

위의 FNV 프라이머리 제약조건과 FNV 오프셋베이스의 정의에 의해 다음 FNV 해시 파라미터의 표가 생성됩니다.

FNV 파라미터

크기(비트) ${\displaystyle n=2^{s}}$	표현	FNV 소수	FNV 오프셋 기준
32	표현	224 + 28 + 0x93
	십진수	16777619	2166136261
	16진수	0x01000193	0x811c9dc5
64	표현	240 + 28 + 0xb3
	십진수	1099511628211	14695981039346656037
	16진수	0x00000100000001B3	0xcbf29ce484222325
128	표현	288 + 28 + 0x3b
	십진수	309485009821345068724781371	144066263297769815596495629667062367629
	16진수	0x0000000001000000000000000000013B	0x6c62272e07bb014262b821756295c58d
256	표현	2168 + 28 + 0x63
	십진수	374144419156711147060143317 175368453031918731002211	100029257958052580907070968620625704837 092796014241193945225284501741471925557
	16진수	0x00000000000000000000010000000000 00000000000000000000000000000163	0xdd268dbcaac550362d98c384c4e576ccc8b153 6847b6bbb2323b4caee0535
512	표현	2344 + 28 + 0x57
	십진수	358359158748448673689190764 890951084499463279557543925 583998256154206699388825751 26094039892345713852759	965930312949666949800943540071631046609 041874567263789610837432943446265799458 293219771643844981305189220653980578449 5328239340083876191928701583869517785
	16진수	0x0000000000000000000000000000000000 0000000001000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000157	0xb86db0b1171f4416 dca1e50f309990ac ac87d059c900000000000000000d21 e948f68a34c192f6 2ea79bc942dbe7ce 182036415f56e34b ac982aac4afe9×9
1024	표현	2680 + 28 + 0x8d
	십진수	501645651011311865543459881103 527895503076534540479074430301 752383111205510814745150915769 222029538271616265187852689524 938529229181652437508374669137 180409427187316048473796672026 0389217684476157468082573	14197795064947621068722070641403218320 88062279544193396087847491461758272325 22967323037177221508640965212023555493 65628174669108571814760471015076148029 75596980407732015769245856300321530495 71501574036444603635505054127112859663 61610267868082893823963790439336411086 884584107735010676915
	16진수	0x0000000000000000000000000000000000 0000000000000000 0000000000000000 0000000000000000 0000010000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 00000000000000000000000018D	0x0000000000000000000000005f7a76758µ4d 32e56d5a591028b7 4b29fc4223 ada1 ada 1 6c3bf34eda3674da 9a21d90000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 00000000000000000000000004c6d7 eb6e73802734510a 555f256cc005ae55 6bde8cc9c6a93b21 aff4b16c71ee90b3

비암호화 해시

FNV 해시는 암호화가 아닌 고속 해시 테이블 및 체크섬 사용을 위해 설계되었습니다.작성자들은 알고리즘이 암호화 해시 ^[15]함수로 적합하지 않은 다음 속성을 식별했습니다.

• 계산 속도 – 주로 해시 테이블 및 체크섬 사용을 위해 설계된 해쉬로서 FNV-1 및 FNV-1a는 계산 속도가 빠를 수 있도록 설계되었습니다.그러나 이와 같은 속도로 인해 브루트 포스로 특정 해시 값(충돌)을 더 빨리 찾을 수 있습니다.
• 스틱 상태– 주로 곱셈과 XOR에 기반한 반복 해시이므로 알고리즘은 숫자0에 민감합니다.구체적으로 계산 중에 해시 값이 0이 되고 다음 바이트 해시도 모두 0이 되면 해시는 변경되지 않습니다.이로 인해 계산 중 어느 시점에서 해시 값이 0이 되는 메시지가 지정되면 메시지 충돌은 쉽게 생성됩니다.각 단계에서 제3의 상수 소수를 추가하는 것과 같은 추가 연산은 이를 완화할 수 있지만 눈사태 효과 또는 해시 값의 랜덤 분포에 해로운 영향을 미칠 수 있습니다.
• 확산 – 이상적인 보안 해시 함수는 입력의 각 바이트가 해시의 모든 비트에 동일하게 복잡한 영향을 미치는 함수입니다.FNV 해시에서는 1 자리(맨 오른쪽 비트)는 항상 모든 입력 바이트의 맨 오른쪽 비트의 XOR입니다.이것은 XOR 폴딩(해시를 원하는 길이의 2배로 계산한 후 "상반"의 비트와 "하반"^[4]의 비트를 XOR)으로 완화시킬 수 있습니다.

「 」를 참조해 주세요.

• Bloom 필터(고속 해시용)
• 비암호화 해시 함수

레퍼런스

외부 링크

• FNV에 관한 Landon Curt Noll의 웹 페이지 (기본 파라미터 및 주요 파라미터 표 포함)
• Fowler, Noll, Vo 및 Eastlake에 의한 인터넷 드래프트(IETF Informational Internet Draft)