Loading article…
SipHashは、 2011年後半に発生した一連の「ハッシュフラッディング」サービス拒否攻撃（HashDoS）への対応として、 Jean-Philippe AumassonとDaniel J. Bernsteinによって2012年に作成された、加算、回転、排他的論理和（ARX）ベースの疑似乱数関数ファミリーです。 [1] : 165 [2 ]
SipHash は、非暗号ハッシュ関数として設計されています。セキュリティを確保するために使用できますが、SipHash は、メッセージ認証コード、つまりキー付きハッシュ関数のようなハッシュメッセージ認証コード ( HMAC )としてのみ適しているという点で、セキュアハッシュアルゴリズム(SHA)などの暗号ハッシュ関数とは根本的に異なります。つまり、SHA は、誰でも SHA(X) を計算できたとしても、攻撃者が SHA(X) = SHA(Y) となる 2 つのメッセージ X と Y を見つけることが困難になるように設計されています。代わりに、 SipHash は、X iと SipHash( X i、k ) を見た後、キーk を知らない攻撃者が、以前に見たことのないメッセージY ∉ { X i } のkまたは SipHash( Y、k ) (に関する情報) を見つけることができないようにします。
概要
SipHash は、可変長メッセージと 128 ビットの秘密鍵から64 ビットの メッセージ認証コードを計算します。これは、短い入力でも効率的に動作するように設計されており、 CityHashなどの非暗号ハッシュ関数に匹敵するパフォーマンスを備えています。[4] : 496 [2]これは、ハッシュ テーブル に対するサービス拒否攻撃(「ハッシュ フラッディング」) を防ぐため、[5]またはネットワーク パケットを認証するために使用できます。後に、128 ビットの結果を生成するバリアントが追加されました。[6]
SHA などのキーなしハッシュ関数は、出力全体が使用される場合にのみ衝突耐性があります。実用的なサイズのハッシュ テーブルへのインデックスなどの小さな出力を生成するために使用される場合、衝突を防ぐことができるアルゴリズムはありません。攻撃者は、可能な出力の数だけ試行するだけで済みます。
たとえば、ネットワーク サーバーが一度に 100 万件までのリクエストを処理できるように設計されているとします。このサーバーは、200 万件のエントリを持つハッシュ テーブルで受信リクエストを追跡し、ハッシュ関数を使用して各リクエストの識別情報を 200 万件のテーブル エントリの 1 つにマッピングします。ハッシュ関数を知っている攻撃者は、任意の入力を与えるだけで済みます。200 万件のうち 1 件が特定のハッシュ値を持ちます。攻撃者が、すべて同じハッシュ値を持つように選択された数百件のリクエストをサーバーに送信すると、多数のハッシュ衝突が発生し、数百万件のリクエストのパケット フラッドと同様の影響でサーバーが遅くなり (場合によっては停止し) ます。[7]
SipHash のようなキー付きハッシュ関数は、攻撃者に知られていないキーを使用することで、この種の攻撃を防ぎます。キーなしハッシュ関数にキーを追加することは可能ですが ( HMACは一般的な手法です)、SipHash の方がはるかに効率的です。
SipHashファミリーの関数はSipHash- c - dと指定されます。ここで、cはメッセージブロックあたりのラウンド数、dはファイナライズラウンド数です。推奨パラメータは、最高のパフォーマンスを得るにはSipHash-2-4、保守的なセキュリティにはSipHash-4-8です。いくつかの言語では、未知のDoS攻撃のリスクを負ってパフォーマンスを上げるためにSiphash-1-3を使用しています。[8]
リファレンス実装はCC0の下でパブリックドメインソフトウェアとしてリリースされました。[6]
使用法
SipHashは様々なソフトウェアのハッシュテーブル実装に使用されている: [9]
次のプログラムは SipHash を他の方法で使用します。
- 短縮トランザクションID用のビットコイン[23]
- C++ オブジェクトハッシュとしての Bloomberg BDE [24]
- インタープラネタリーファイルシステム（IPFS）の7つのブルームフィルターハッシュ[25]
実装
- C (パブリック ドメイン リファレンス実装)
- C++ (Wassenberg & Alakuijala 2017、「highwayhash」研究の一部)
- C#
- 暗号++
- 行く
- ハスケル
- JavaScript
- ピコリスプ
- さび
- 迅速
- ベリログ
- VHDL
参照
- ブルームフィルタ（高速ハッシュのアプリケーション）
- 暗号ハッシュ関数
- ハッシュ関数
- メッセージ認証コード
- ハッシュ関数のリスト
参考文献
- ^ Dobraunig, Christoph; Mendel, Florian; Schläffer, Martin (2014 年 11 月 29 日)。「SipHash の差分暗号解析」。暗号化の分野選択 -- SAC 2014。コンピュータ サイエンスの講義ノート。第 8781 巻。pp. 165–182。doi : 10.1007 /978-3-319-13051-4_10。ISBN 978-3-319-13050-7. 2018年2月28日閲覧。
- ^ ab Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). 「SipHash: 高速なショート入力 PRF」. Cryptology ePrint Archive。
- ^ Lennon, Mike (2011-12-28). 「ハッシュ テーブルの脆弱性により、大規模な DDoS 攻撃が可能に」SecurityWeek。
- ^ So, Won; Narayanan, Ashok; Oran, David; Stapp, Mark ( 2013)。「ルーター上の名前付きデータ ネットワーキング」。SIGCOMM に関する ACM SIGCOMM 2013 カンファレンスの議事録。pp. 495–496。doi :10.1145/ 2486001.2491699。ISBN 9781450320566. S2CID 1457918 . 2018年2月28日閲覧.
最近提案されたSipHash [1]は衝突耐性と非暗号ハッシュに匹敵する性能を提供するため、バランスが取れている。
- ^ Aumasson, Jean-Philippe; Bernstein, Daniel J .; Boßlet, Martin (2012-11-08). ハッシュフラッディング DoS の再来: 攻撃と防御(PDF)。アプリケーション セキュリティ フォーラム – 西スイス 2012。2013-09-13 のオリジナル(PDF)からアーカイブ。
- ^ ab "SipHash: 高速なショート入力 PRF". 2016-08-01. 2017-02-02 にオリジナルからアーカイブ。2017-01-21に取得。
知的財産: SipHash に関連する特許や特許申請は認識しておらず、申請する予定もありません。 SipHash のリファレンス コードは、パブリック ドメインのようなライセンスである CC0 ライセンスの下でリリースされています。
- ^ Crosby, Scott A.; Wallach, Dan S. (2003-08-06). アルゴリズム複雑性攻撃によるサービス拒否。Usenix セキュリティシンポジウム。ワシントン DC
- ^ Aumasson, Jean-Philippe (veorq) (2015 年 11 月 12 日). 「コメント: Siphash を変更して、アルゴリズムのより高速なバリアントの 1 つを使用するようにする (Siphash13、Highwayhash) · Issue #29754 · rust-lang/rust」。GitHub。2024年2 月 28 日取得。SipHashの
設計者ですが、SipHash-1-3 についての意見は変わりません :-) [...] 4 ラウンドには「識別子」があります [...]、つまり、最も簡単に言えば、4 ラウンドのシーケンスの入力に特定の差異パターンがある場合に表示される統計的バイアスです。ただし、すべての状態を制御していないため、SipHash-1-3 にそのパターンを挿入することはできません。また、そのパターンを挿入できたとしても、そのバイアスはいずれにしても悪用できません。
- ^ Aumasson, Jean-Philippe; Bernstein, Daniel J. (2016-08-01). 「SipHash: 高速ショート入力 PRF、ユーザー」。2017-02-02 にオリジナルからアーカイブ。2017-01-21に取得。
- ^ Vagg, Rod (2019-02-28). 「build: ハッシュシード作成のために v8 の SipHash を有効にする」. Node.js . 2021-10-21取得– GitHub経由。
- ^ Guo, Yang (2019-01-09). 「整数ハッシュにオプションで halfsiphash を使用する」V8 . 2021-10-21閲覧。
- ^ 「OCaml ライブラリ: Hashtbl」 。2024年 2 月 17 日閲覧。
- ^ 「Perl セキュリティ – アルゴリズム複雑性攻撃」。Perldocブラウザ。2016 年 5 月 16 日。2021 年 10 月 21 日閲覧。
- ^ Heimes, Christian (2013-09-27). 「PEP 456 – 安全で交換可能なハッシュアルゴリズム」。2017-01-21閲覧。
- ^ 「SipHash-1-3 への移行 #73596」。GitHub。
- ^ McVey, Samantha (2018-07-16). 「SipHash を実装し、64 ビットのハッシュ値を持つハッシュ関数として使用します」。MoarVM。2018年7 月 16 日に取得– GitHub経由。
- ^ 「機能 #13017: SipHash を SipHash24 から SipHash13 に切り替える - Ruby マスター - Ruby 問題追跡システム」。
- ^ McArthur, Sean (2016-06-30). 「std: HashMap には siphash-1-3 を使用する」。Rust 。2017-01-21取得– GitHub経由。
- ^ Poettering, Lennart (2013-12-22). 「shared: ハッシュ テーブルの実装を SipHash に切り替える」systemd . 2017-01-21に取得– freedesktop.org経由。
- ^ 「SRC/Sys/Crypto/Siphash.h at master · openbsd/SRC」。GitHub。
- ^ "[base] /Head/Sys/Crypto/Siphash のインデックス".
- ^ 「ハッシュテーブルに siphash を使用する · WireGuard/Wg-dynamic@360b9c8」。GitHub。
- ^ 「Compact Block Relay」。GitHub 。 2018年9月27日閲覧。
- ^ bslh_siphashalgorithm.h より
- ^ 「Bbloom/SipHash.go at 73e3f896a4f8bbed8589df6ff5c28ebfbd728e31 · ipfs/Bbloom」。GitHub。
外部リンク
- Jean-Philippe Aumasson、Daniel J. Bernstein (2016-08-01)。「SipHash: 高速なショート入力 PRF – プロジェクト ページ」。GitHub。
- Jean-Philippe Aumasson、Daniel J. Bernstein (2012-09-18)。「SipHash: 高速なショート入力 PRF」(PDF)。
- Jean-Philippe Aumasson、Daniel J. Bernstein (2012-08-15)。「SipHash: 高速なショート入力 PRF – プレゼンテーション スライド」(PDF)。
- Jean-Philippe Aumasson、Daniel J. Bernstein、Martin Boßlet (2012-12-29)。「ハッシュフラッディング DoS の再来: 攻撃と防御」。
- 「ハッシュ」。Rustパフォーマンス ブック。– SipHashが十分に速くない場合について説明します