젠킨스 해시 함수

Jenkins hash function

Jenkins 해시 함수는 Bob Jenkins가 설계한 멀티바이트 키에 대한 (비암호화) 해시 함수의 집합입니다.첫 번째 책은 1997년에 정식으로 출판되었다.

해시함수

한 번에 한 개

Jenkins의 one_at_a_time 해시는 [1]밥 젠킨스의 WWW 페이지에서 개작되었으며, 이것은 그의 [2]Dobb 박사의 기사를 확장한 것이다.원래는 암호화 기술자인 콜린 플럼이 설명한 특정 요건을 충족하기 위해 만들어졌지만 결국 [1]사용되지 않았습니다. 

uint32_t jenkins_one_at_a_time_time_disples(컨스턴트 uint8_t* 열쇠, size_t 길이) {   size_t i = 0;   uint32_t 해시 = 0;   하는 동안에 (i != 길이) {     해시 += 열쇠[i++];     해시 += 해시 << > 10;     해시 ^= 해시 >> 6;   }   해시 += 해시 << > 3;   해시 ^= 해시 >> 11;   해시 += 해시 << > 15;   돌아가다 해시; }

one_at_a_time 해시 함수의 해시 값 샘플. 

한 번에 한 개("a", 1) 0xca2e9442 한 번에 한 개("빠른 갈색 여우는 게으른 개를 뛰어넘는다", 43) 0x519e91f5
3바이트 키에 대한 Jenkins One Atrail 해시의 눈사태 동작

이 해시의 눈사태 동작은 오른쪽에 나와 있습니다.

24개의 각 행은 3바이트 입력 키의 단일 비트에 대응하고, 32개의 각 열은 출력 해시의 비트에 대응합니다.색상은 입력 키비트가 특정 출력 해시 비트에 얼마나 잘 영향을 미치는지에 따라 선택됩니다.녹색 사각형은 양호한 혼합 동작을 나타내고 노란색 사각형은 약한 혼합 동작을 나타냅니다.빨간색은 혼합을 나타내지 않습니다.입력 키의 마지막 바이트에 있는 일부 비트만이 출력 해시 내의 소수의 비트와 약하게 혼합됩니다.

버전 5.28 이전의 Perl 프로그래밍 언어의 표준 구현에는 Jenkins의 1회성 해시 또는 [3][4]디폴트로 사용된 그것의 강화된 변형이 포함되어 있습니다.

검색 2

lookup2 함수는 한 번에1개씩의 중간 후계 함수입니다.1997년 닥터 돕스 저널 기사에서 "My Hash"라고 언급되었지만 젠킨스가 발표한 후속 기능으로 인해 폐지되었습니다.이 해시 함수의 응용 프로그램은 다음 위치에 있습니다.

  • 확률적 오류 검출을 위한 SPIN 모델 검사기.이 프로그램에 관한 논문에서 Dillinger와 Manolios 연구원은 lookup2가 "해시 테이블과 Bloom 필터의 구현자들 사이에서 인기 있는 선택"이라고 지적했습니다.이들은 lookup2와 32비트 해시 [5]값이 아닌 96비트 해시 값을 생성하는 lookup2의 단순 확장을 연구합니다.
  • 충돌에 너무 민감한 이전 해시 함수를 대체한 [6]Linux의 Netfilter 방화벽 구성 요소입니다.단, Jenkins 해시가 비밀키를 [7]사용하여 랜덤화된 경우에도 결과 시스템은 해시 플래딩 공격에 여전히 민감한 것으로 나타났습니다.
  • kalah 게임을 해결한 프로그램은 이러한 유형의 문제에 더 일반적으로 사용되는 Zobrist 해싱 기법 대신 Jenkins 해시 함수를 사용했습니다; 이 선택의 이유는 kalah 보드의 작은 표현에서 Jenkins의 함수의 속도, 그리고 kalah의 기본 규칙이 근본적으로 판을 바꿀 수 있다는 사실이었습니다.해시 [8]함수에 대한 Zobrist의 증분 계산의 이점을 부정합니다.

검색 3

lookup3 함수는 12바이트(96비트) [9]청크의 입력을 소비합니다.단순함보다 속도가 더 중요한 경우에는 적절할 수 있습니다.단, 이 해시를 사용한 속도 향상은 큰 키에만 도움이 될 수 있으며, 복잡성이 증가하면 최적화 컴파일러가 해시 함수를 삽입할 수 없게 되는 등의 속도에도 영향을 미칠 수 있습니다.

스푸키 해시

2011년 Jenkins는 SpokeyHash라는 새로운 128비트 해시 [10]함수를 출시했습니다.SpokyHash는 lookup3보다 훨씬 빠릅니다.

V2(리틀 엔디언 x64)의 예:

192바이트(43바이트) 미만의 짧은 메서드: 

Hash128("빠른 갈색 여우가 게으른 개를 뛰어넘는다") 2b12e846aa0693c71d367e742407341b

191바이트(219바이트)를 넘는 표준 방식: 

Hash128 ("빠른 갈색 여우는 게으른 개를 뛰어넘는다.빠른 갈색 여우는 게으른 개를 뛰어넘는다.빠른 갈색 여우는 게으른 개를 뛰어넘는다.빠른 갈색 여우는 게으른 개를 뛰어넘는다.") f1b71c6ac5af39e7b69363a60d29c49

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Jenkins, Bob (November 3, 2013). "A hash function for hash Table lookup". Retrieved February 9, 2018.
  2. ^ Jenkins, Bob (September 1997). "Hash functions". Dr. Dobb's Journal.
  3. ^ "RFC: perlfeaturedelta": "한 번에 하나의 해시 알고리즘...[버전 추가] 5.8.0"
  4. ^ "hv_func.h"
  5. ^ Dillinger, Peter C.; Manolios, Panagiotis (2004). Fast and accurate bitstate verification for SPIN. Proc. 11th International SPIN Workshop. pp. 57–75. CiteSeerX 10.1.1.4.6765.
  6. ^ Neira Ayuso, Pablo (2006). "Netfilter's connection tracking system" (PDF). ;login:. 31 (3).
  7. ^ Bar-Yosef, Noa; Wool, Avishai (2007). Remote algorithmic complexity attacks against randomized hash tables Proc. International Conference on Security and Cryptography (SECRYPT) (PDF). pp. 117–124.
  8. ^ Irving, Geoffrey; Donkers, Jeroen; Uiterwijk, Jos. "Solving kalah" (PDF). ICGA Journal.
  9. ^ Jenkins, Bob. "lookup3.c source code". Retrieved April 16, 2009.
  10. ^ Jenkins, Bob. "SpookyHash: a 128-bit noncryptographic hash". Retrieved Jan 29, 2012.