Loading article…
ジェンキンスハッシュ関数は、ボブ ジェンキンスによって設計された、マルチバイトキー用の非暗号化ハッシュ関数のファミリです。最初のものは 1997 年に正式に公開されました。
ハッシュ関数
一度に一つずつ
Jenkins のone_at_a_timeハッシュは、Bob Jenkins の WWW ページ[1]から引用したものです。このページは、 Dr. Dobb の記事[2]の拡張版です。このハッシュは、もともと暗号学者の Colin Plumb が記述した特定の要件を満たすために作成されましたが、最終的には使用されませんでした。[1]
uint32_t jenkins_one_at_a_time_hash ( const uint8_t * key , size_t length ) { size_t i = 0 ; uint32_t hash = 0 ; while ( i != length ) { hash += key [ i ++ ]; hash += hash << 10 ; hash ^= hash >> 6 ; } hash += hash << 3 ; hash ^= hash >> 11 ; hash += hash << 15 ;ハッシュを返す; }
one_at_a_timeハッシュ関数のサンプル ハッシュ値。
one_at_a_time ( "a" , 1 ) 0xca2e9442 one_at_a_time ( "素早い茶色のキツネが怠け者の犬を飛び越える" , 43 ) 0x519e91f5
このハッシュの雪崩動作は右側に示されています。
24 行のそれぞれは 3 バイトの入力キーの 1 ビットに対応し、32 列のそれぞれは出力ハッシュの 1 ビットに対応します。色は、入力キー ビットが特定の出力ハッシュ ビットにどの程度影響するかによって選択されます。緑の四角は良好な混合動作を示し、黄色の四角は弱い混合動作を示し、赤は混合がないことを示します。入力キーの最後のバイトのいくつかのビットのみが、出力ハッシュの少数のビットと弱く混合されます。
Perlプログラミング言語バージョン5.28より前の標準実装には、Jenkinsのone-at-a-timeハッシュまたはその強化版が含まれており、デフォルトで使用されていました。[3] [4]
ルックアップ2
lookup2関数は、 one-at-a-time の暫定的な後継関数です。これは、1997 年の Dr. Dobbs ジャーナル記事で「My Hash」と呼ばれている関数ですが、Jenkins がリリースした後続の関数によって廃止されました。このハッシュ関数のアプリケーションは次の場所にあります。
- 確率的エラー検出のためのSPINモデルチェッカー。このプログラムに関する論文で、研究者のディリンジャーとマノリオスは、lookup2は「ハッシュテーブルとブルームフィルタの実装者の間で人気のある選択肢」であると述べています。彼らはlookup2と、32ビットではなく96ビットのハッシュ値を生成するその単純な拡張を研究しています。[5]
- LinuxのファイアウォールコンポーネントであるNetfilter [ 6]は、衝突に対して敏感すぎる以前のハッシュ関数を置き換えました。しかし、結果として得られたシステムは、秘密鍵を使用してJenkinsハッシュをランダム化した場合でも、ハッシュフラッディング攻撃に対して依然として敏感であることが示されました。 [7]
- カラのゲームを解いたプログラムは、この種の問題でより一般的に使用されるゾブリストのハッシュ技術ではなく、ジェンキンスのハッシュ関数を使用しました。この選択の理由は、カラのボードの小さな表現に対するジェンキンスの関数の速度と、カラの基本ルールがボードを根本的に変える可能性があり、ゾブリストのハッシュ関数の増分計算の利点を打ち消すという事実でした。[8]
ルックアップ3
lookup3関数は、入力を12バイト（96ビット）のチャンクで消費します。[9]速度がシンプルさよりも重要な場合に適しています。ただし、このハッシュの使用による速度の向上は、大きなキーに対してのみ有効である可能性があり、複雑さが増すと、最適化コンパイラがハッシュ関数をインライン化できなくなるなど、速度に影響する可能性があることに注意してください。
lookup3関数は、CRC32やFletcher32と比較した相対的な強度と速度に基づいて、内部データ構造のチェックサムとして階層データフォーマット5に組み込まれました。 [10]
スプーキーハッシュ
2011年にJenkinsはSpookyHashと呼ばれる新しい128ビットハッシュ関数をリリースしました。[11] SpookyHashはlookup3よりも大幅に高速です。
V2 (リトルエンディアン x64) の例:
192 バイト (43 バイト) 未満の短縮方法:
Hash128("素早い茶色のキツネが怠け者の犬を飛び越える")
2b12e846aa0693c71d367e742407341b
191バイト（219バイト）を超える場合の標準的な方法：
Hash128("素早い茶色のキツネが怠け者の犬を飛び越える。素早い茶色のキツネが怠け者の犬を飛び越える。素早い茶色のキツネが怠け者の犬を飛び越える。素早い茶色のキツネが怠け者の犬を飛び越える。素早い茶色のキツネが怠け者の犬を飛び越える。素早い茶色のキツネが怠け者の犬を飛び越える。")
f1b71c6ac5af39e7b69363a60dd29c49
参照
参考文献
- ^ ab Jenkins, Bob (2013年11月3日). 「ハッシュテーブル検索用のハッシュ関数」. 2018年2月9日閲覧。
- ^ ボブ、ジェンキンス (1997 年 9 月)。 「ハッシュ関数」。ドブ博士の日記。
- ^ 「RFC: perlfeaturedelta」: 「one-at-a-time ハッシュ アルゴリズム ... [バージョン 5.8.0 で追加されました]」
- ^ "perl: hv_func.h"
- ^ Dillinger, Peter C.; Manolios, Panagiotis (2004). SPIN の高速かつ正確なビット状態検証。Proc . 11th International SPIN Workshop。pp. 57–75。CiteSeerX 10.1.1.4.6765。
- ^ Neira Ayuso、Pablo ( 2006)。「Netfilter の接続追跡システム」(PDF)。;ログイン:。31 (3)。
- ^ Bar-Yosef, Noa; Wool, Avishai (2007). ランダム化ハッシュテーブルに対するリモートアルゴリズム複雑性攻撃 Proc. International Conference on Security and Cryptography (SECRYPT) (PDF) . pp. 117–124.
- ^ ジェフリー・アーヴィング;ドンカーズ、ジェローン。 Uiterwijk、Jos. 「カラハの解決」(PDF)。ICGAジャーナル。
- ^ Jenkins, Bob. 「lookup3.c ソースコード」 。2009年4 月 16 日閲覧。
- ^ Koziol, Quincey. "[svn-r12661] 説明: · HDFGroup/hdf5@d3a12e1" . 2023年7月18日閲覧。
- ^ Jenkins, Bob. 「SpookyHash: 128 ビットの非暗号化ハッシュ」 。2012年1 月 29 日閲覧。