무르 해쉬

MurmurHash

Murmur Hash는 일반적인 해시 기반 [1][2][3]검색에 적합한 비암호화 해시 함수입니다.2008년[4] 오스틴 애플비에 의해 만들어졌으며 현재 'SMHasher'라는 이름의 테스트 스위트와 함께 GitHub에서 호스팅되고 있다.또한 여러 가지 [5]변형으로 존재하며, 이 모든 변형은 퍼블릭 도메인으로 출시되었습니다.이름은 내부 루프에서 사용되는 곱셈(MU)과 회전(R)의 두 가지 기본 연산에서 유래합니다.

암호화 해시 함수와 달리, 상대방이 되돌리기 어렵도록 특별히 설계되지 않았기 때문에 암호화 목적에 적합하지 않습니다.

변종

무르 해쉬 3

현재 버전은 32비트 또는 128비트 해시 값을 생성하는 Murmur Hash3입니다.[6][7]128비트를 사용하는 경우 알고리즘이 각각의 플랫폼에 최적화되어 있기 때문에 x86 및 x64 버전은 동일한 값을 생성하지 않습니다.Murmur Hash3는 SMHasher와 함께 출시되었습니다.SMHasher는 해시함수 테스트 스위트입니다.

무르 해쉬2

MurmurHash2는[8] 32비트 또는 64비트 값을 생성합니다.증분 해시를 허용하고 정렬된 버전 또는 중립 버전을 포함하여 여러 변형으로 제공되었습니다.

  • MurmurHash2(32비트, x86) - 원래 버전. 경우에 [9]따라 충돌을 약화시키는 결함이 있습니다.
  • Murmur Hash2A(32비트, x86) - Merkle-Damgörd 구조를 사용한 고정식 변형.조금 느리다.
  • CMurmurHash2A(32비트, x86) - MurmurHash2A이지만 증분 동작합니다.
  • Murmur Hash Neutral 2(32비트, x86) - 느리지만 엔디언 및 얼라인먼트 뉴트럴
  • Murmur Hash Aligned 2(32비트, x86) - 속도는 느리지만 정렬된 판독이 이루어집니다(일부 플랫폼에서는 더 안전합니다).
  • Murmur Hash64A(64비트, x64): 원래 64비트 버전.64비트 계산에 최적화되어 있습니다.
  • Murmur Hash64B(64비트, x86) - 32비트 플랫폼에 최적화된64비트 버전스트라이프의 [10]혼재가 불충분하기 때문에 진정한 64비트 해시가 아닙니다.

MurmurHash2의 결함을[clarification needed] 발견한 사람은 MurmurHash2_160이라는 비공식 버전의 MurmurHash2를 만들었습니다.[11]

무르 해쉬 1

원래 Murmur Hash는 [12]Lookup3보다 빠른 기능을 만들기 위해 만들어졌습니다.성공적이긴 했지만, Lookup3에서처럼 철저한 테스트를 거치지 않았고 64비트 해시를 제공할 수 없었습니다.이것은 곱셈 해시(Fowler-Noll-Vo 해시 함수와 유사함수)와 Xorsshift를 조합하여 나중에 MurmurHash2에서 구축될 다소 우아한 디자인을 가지고 있다.

실장

정규 구현 C++에 살고 있지만, 유명한 언어 중 다양한 효율적인 항만, Python,[13]C,[14]Go,[15]C#,[7][16]D,[17]을 통해 Lua, Perl,[18]Ruby,[19]Rust,[20]PHP,[21][22]공통 Lisp,[23]Haskell,[24]Elm,[25]Clojure,[26]Scala,[27]Java,[28][29]Erlang,[30]Swift,[31일]ObjectPascal,[32]Kotlin,[33]과 JavaSc 등이 들어 있다.ript.[34]

(얼음 1.0.1)[35]Rubinius,[36]libmemcached 그것은 오픈 소스 프로젝트를 많이, 특히libstdc++(얼음 4.6), nginx에 입양된 적이 없다는(Memcached의 C운전자)[37]npm(nodejs 패키지 매니저)[38]maatkit,[39]Hadoop,[1]교토 Cabinet,[40]Cassandra,[41][42]Solr,[43]vowpal wabbit,[44]Elasticsearch,[45]Guava,[46]Kafka[47]과 RedH.가상 데이터 최적기(VDO)에서.[48]

취약성

해시 함수는 사용자가 의도적으로 해시 충돌을 일으키도록 입력 데이터를 선택할 수 있는 충돌 공격에 취약할 수 있습니다.Jean-Philippe Aumasson과 Daniel J. Bernstein은 무작위 시드를 사용하는 MurmurHash의 구현조차도 소위 HashDoS [49]공격에 취약하다는 것을 보여줄 수 있었습니다.차분 암호 분석을 사용하여 해시 충돌을 일으킬 수 있는 입력을 생성할 수 있었습니다.공격 작성자는 대신 자체 SipHash를 사용할 것을 권장합니다.

알고리즘.

알고리즘 Murmur3_32는 // 주의:이 버전에서, 모든 연산 부호 없는 32비트 정수 쌍을. 플로의 경우 끓여, 그 결과 과학자나 감소는 232번이에요. 입력:,에 살고 있는데, 씨앗 c1 0xcc9e2d51 c2 ← 0x1b873593 r1 ← ← 키 수행한다 15r2 ← 13m← 5n← 0xe6546b64 해시 ← 씨앗을 위해 각 fourByteChunk의 주요니 k ←fourByteChunk k←. k× c1 k ← k ROL r1 k ← k × c2 hash ← hash XOR k hash ← hash ROL r2 hash ← (hash × m) + n (남은 바이트 포함)InKey 나머지 바이트 실행 ← SwapToLittleEndian(남은 바이트)InKey) // 주의: 엔디안 스왑은 빅 엔디안 머신에서만 필요합니다.// 목적은 의미 있는 숫자를 값의 하한에 배치하는 것입니다. // 이러한 숫자가 후속 곱셈에서 낮은 범위 숫자 //에 가장 큰 영향을 미칠 수 있도록 합니다.  의미 있는 숫자 //를 하이 레인지로 지정하면 // 곱셈의 하이 디짓에 더 큰 효과가 발생하며, 특히 이러한 하이 디짓은 오버플로 아래의 모듈로 산술에 의해 // 폐기될 가능성이 높습니다.← remainingBytes remainingBytes×c1 remainingBytes ← remainingBytes 롤런드 r1 remainingBytes← remainingBytes ×c2 해시 ← 해시 XORremainingBytes 해시하는← 해시 XOR에 살고 있는데 hash← 해시 XOR(해시 시퀀스를<>16)hash← 해시 × 0x85ebca6b 해시 ← 해시 XOR(해시 시퀀스를<>13)hash← 해시×우리는. 그걸 원하지 않아.0xc2b2ae35hash ← 해시 XOR (hash >> 16)

다음으로 (리틀 엔디안 CPU의 경우) 구현 예를 나타냅니다.

정적인 인라인 uint32_t 소곤소곤_32_displays(중얼중얼)(uint32_t k) {     k *= 0xcc9e2d51;     k = (k << > 15)   (k >> 17);     k *= 0x1b873593;     돌아가다 k; } uint32_t 잡음 3_32(컨스턴트 uint8_t* 열쇠, size_t 렌, uint32_t 씨를 뿌리다) {  uint32_t h = 씨를 뿌리다;     uint32_t k;     /* 4인 1조로 읽습니다.*/     위해서 (size_t i = 렌 >> 2; i; i--) {         // 다음은 엔디안니스에 따라 다른 결과의 소스입니다.         // 여기서의 스왑은 해시 속성에 영향을 주지 않습니다.         메모리(&k, 열쇠, 크기(uint32_t));         열쇠 += 크기(uint32_t);         h ^= 소곤소곤_32_displays(중얼중얼)(k);         h = (h << > 13)   (h >> 19);         h = h * 5 + 0xe6546b64;     }     /* 나머지를 읽어 주세요.*/     k = 0;     위해서 (size_t i = 렌 & 3; i; i--) {         k <<=> 8;         k = 열쇠[i - 1];     }     // 이전 루프가 이미 있기 때문에 *스왑은 필요 없습니다*     // 엔디안성에 따라 낮은 바이트를 낮은 위치에 배치합니다.     // 사용.스왑은 메모리가 청크로 복사된 경우에만 적용됩니다.     h ^= 소곤소곤_32_displays(중얼중얼)(k);     /* 완료.*/  h ^= 렌;  h ^= h >> 16;  h *= 0x85ebca6b;  h ^= h >> 13;  h *= 0xc2b2ae35;  h ^= h >> 16;  돌아가다 h; }

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b "Hadoop in Java". Hbase.apache.org. 24 July 2011. Archived from the original on 12 January 2012. Retrieved 13 January 2012.
  2. ^ 추자 등
  3. ^ "Couceiro et al" (PDF) (in Portuguese). p. 14. Retrieved 13 January 2012.
  4. ^ Tanjent (tanjent) wrote,3 March 2008 13:31:00. "MurmurHash first announcement". Tanjent.livejournal.com. Retrieved 13 January 2012.
  5. ^ "MurmurHash2-160". Simonhf.wordpress.com. 25 September 2010. Retrieved 13 January 2012.
  6. ^ "MurmurHash3 on Github".
  7. ^ a b Horvath, Adam (10 August 2012). "MurMurHash3, an ultra fast hash algorithm for C# / .NET".
  8. ^ "MurmurHash2 on Github".
  9. ^ "MurmurHash2Flaw". Retrieved 15 January 2019.
  10. ^ "MurmurHash3 (see note on MurmurHash2_x86_64)". Retrieved 15 January 2019.
  11. ^ "MurmurHash2_160". Retrieved 12 January 2019.
  12. ^ "MurmurHash1". Retrieved 12 January 2019.
  13. ^ "pyfasthash in Python". Retrieved 13 January 2012.
  14. ^ "C implementation in qLibc by Seungyoung Kim".
  15. ^ "murmur3 in Go".
  16. ^ Landman, Davy. "Davy Landman in C#". Landman-code.blogspot.com. Retrieved 13 January 2012.
  17. ^ "std.digest.murmurhash - D Programming Language". dlang.org. Retrieved 5 November 2016.
  18. ^ "Toru Maesaka in Perl". metacpan.org. Retrieved 13 January 2012.
  19. ^ Yuki Kurihara (16 October 2014). "Digest::MurmurHash". GitHub.com. Retrieved 18 March 2015.
  20. ^ "stusmall/murmur3". GitHub. Retrieved 29 November 2015.
  21. ^ "PHP userland implementation of MurmurHash3". github.com. Retrieved 18 December 2017.
  22. ^ "PHP 8.1 with MurmurHash3 support".
  23. ^ "tarballs_are_good / murmurhash3". Retrieved 7 February 2015.
  24. ^ "Haskell". Hackage.haskell.org. Retrieved 13 January 2012.
  25. ^ "Elm". package.elm-lang.org. Retrieved 12 June 2019.
  26. ^ "Murmur3.java in Clojure source code on Github". clojure.org. Retrieved 11 March 2014.
  27. ^ "Scala standard library implementation". 26 September 2014.
  28. ^ 무르무르3, 구아바의 일부
  29. ^ "Murmur3A and Murmur3F Java classes on Github". greenrobot. Retrieved 5 November 2014.
  30. ^ "bipthelin/murmerl3". GitHub. Retrieved 21 October 2015.
  31. ^ Daisuke T (7 February 2019). "MurmurHash-Swift". GitHub.com. Retrieved 10 February 2019.
  32. ^ GitHub - Xor-el/HashLib4Pascal:현대 객체 파스칼을 위한 해싱
  33. ^ "goncalossilva/kotlinx-murmurhash". GitHub.com. 10 December 2021. Retrieved 14 December 2021.
  34. ^ raycmorgan (owner). "Javascript implementation by Ray Morgan". Gist.github.com. Retrieved 13 January 2012.
  35. ^ "nginx". Retrieved 13 January 2012.
  36. ^ "Rubinius". Retrieved 29 February 2012.
  37. ^ "libMemcached". libmemcached.org. Retrieved 21 October 2015.
  38. ^ "switch from MD5 to murmur".
  39. ^ "maatkit". 24 March 2009. Retrieved 13 January 2012.
  40. ^ "Kyoto Cabinet specification". Fallabs.com. 4 March 2011. Retrieved 13 January 2012.
  41. ^ "Partitioners". apache.org. 15 November 2013. Retrieved 19 December 2013.
  42. ^ "Introduction to Apache Cassandra™ + What's New in 4.0 by Patrick McFadin. DataStax Presents". YouTube. 10 April 2019.
  43. ^ "Solr MurmurHash2 Javadoc".
  44. ^ "hash.cc in vowpalwabbit source code".
  45. ^ "Elasticsearch 2.0 - CRUD and routing changes".
  46. ^ "Guava Hashing.java".
  47. ^ "Kafka DefaultPartitioner.java".
  48. ^ Virtual Data Optimizer 소스 코드
  49. ^ "Breaking Murmur: Hash-flooding DoS Reloaded".

외부 링크