SipHashは、 2011年後半に発生した一連の「ハッシュフラッディング」サービス拒否攻撃（HashDoS）への対応として、 Jean-Philippe AumassonとDaniel J. Bernsteinによって2012年に作成された、加算、回転、XOR（ARX）ベースの疑似乱数関数ファミリーです。[1] : 165  [2 ]

SipHash は安全な疑似乱数関数として設計されており、安全なメッセージ認証コード(MAC)としても使用できます。ただし、SipHash はセキュア ハッシュ アルゴリズム(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万件のエントリのいずれかにマッピングします。ハッシュ関数を知っている攻撃者は、任意の入力を与えるだけで済みます。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 を他の方法で使用します。

実装

  • C (リファレンス実装)
  • C++ (Wassenberg & Alakuijala 2017、「highwayhash」研究の一部)
  • C#
  • 暗号++
  • 行く
  • ハスケル
  • JavaScript
  • ピコリスプ
  • さび
  • 迅速
  • ベリログ
  • VHDL

参照

参考文献

  1. ^ 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日閲覧。
  2. ^ Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). 「SipHash: 高速なショート入力PRF」. Cryptology ePrint Archive .
  3. ^ Lennon, Mike (2011年12月28日). 「ハッシュテーブルの脆弱性により大規模なDDoS攻撃が可能に」SecurityWeek .
  4. ^ So, Won; Narayanan, Ashok; Oran, David; Stapp, Mark (2013). 「ルータ上の名前付きデータネットワーキング」. ACM SIGCOMM 2013 カンファレンス SIGCOMM の議事録. pp.  495– 496. doi :10.1145/2486001.2491699. ISBN 9781450320566. S2CID  1457918 . 2018年2月28日閲覧.最近提案されたSipHash [1]は衝突耐性と非暗号ハッシュに匹敵する性能を備えており、バランスの取れたハッシュである。
  5. ^ Aumasson, Jean-Philippe; Bernstein, Daniel J .; Boßlet, Martin (2012年11月8日). ハッシュフラッディングDoS攻撃の再発：攻撃と防御(PDF) . Application Security Forum – Western Switzerland 2012. 2013年9月13日時点のオリジナル(PDF)からアーカイブ。
  6. ^ ab "SipHash: a fast short-input PRF". 2016年8月1日. オリジナルから2017年2月2日にアーカイブ。 2017年1月21日閲覧。知的財産：SipHashに関連する特許や特許出願は把握しておらず、今後出願する予定もありません。SipHashのリファレンスコードは、パブリックドメインに類似したライセンスであるCC0ライセンスの下で公開されています。
  7. ^ Crosby, Scott A.; Wallach, Dan S. (2003-08-06). アルゴリズム複雑性攻撃によるサービス拒否攻撃. Usenixセキュリティシンポジウム. ワシントンD.C.
  8. ^ Aumasson, Jean-Philippe (veorq) (2015年11月12日). 「コメント: Siphash をアルゴリズムのより高速な変種 (Siphash13、Highwayhash) のいずれかを使用するように変更 · Issue #29754 · rust-lang/rust」. GitHub . 2024年2月28日閲覧。SipHashの設計者ですが、SipHash-1-3 についての意見は変わりません :-) [...] 4ラウンドには「識別子」があります [...] 。簡単に言えば、4ラウンドシーケンスの入力に特定の差異パターンがある場合に現れる統計的バイアスです。しかし、SipHash-1-3 ではすべての状態を制御できないため、そのパターンを注入することはできません。たとえそのパターンを注入できたとしても、そのバイアスはそもそも悪用できないでしょう。
  9. ^ Aumasson, Jean-Philippe; Bernstein, Daniel J. (2016年8月1日). 「SipHash: 高速なショートインプットPRF、ユーザー向け」。2017年2月2日時点のオリジナルよりアーカイブ。 2017年1月21日閲覧。
  10. ^ Vagg, Rod (2019-02-28). 「build: ハッシュシード作成にv8のSipHashを有効にする」. Node.js . 2021年10月21日閲覧– GitHub経由.
  11. ^ Guo, Yang (2019-01-09). 「整数ハッシュにhalfsiphashをオプションで使用する」V8 . 2021年10月21日閲覧。
  12. ^ 「OCamlライブラリ: Hashtbl」 。 2024年2月17日閲覧。
  13. ^ 「Perl セキュリティ – アルゴリズム複雑性攻撃」Perldoc ブラウザ. 2016年5月16日. 2021年10月21日閲覧。
  14. ^ Heimes, Christian (2013年9月27日). 「PEP 456 – 安全で交換可能なハッシュアルゴリズム」 . 2017年1月21日閲覧。
  15. ^ 「SipHash-1-3への移行 #73596」。GitHub。
  16. ^ McVey, Samantha (2018-07-16). 「SipHashを実装し、64ビットハッシュ値を持つハッシュ関数として使用する」MoarVM . 2018年7月16日閲覧– GitHub経由.
  17. ^ 「機能 #13017: SipHash を SipHash24 から SipHash13 に切り替える - Ruby マスター - Ruby 問題追跡システム」。
  18. ^ McArthur, Sean (2016-06-30). 「std: HashMapにはsiphash-1-3を使用する」Rust . 2017年1月21日閲覧– GitHub経由.
  19. ^ Poettering, Lennart (2013年12月22日). 「shared: ハッシュテーブル実装をSipHashに切り替える」systemd . 2017年1月21日閲覧– freedesktop.orgより。
  20. ^ "SRC/Sys/Crypto/Siphash.h at master · openbsd/SRC". GitHub .
  21. ^ "[base] /Head/Sys/Crypto/Siphash のインデックス".
  22. ^ "ハッシュテーブルにsiphashを使用する · WireGuard/Wg-dynamic@360b9c8". GitHub .
  23. ^ 「コンパクトブロックリレー」GitHub 。 2018年9月27日閲覧。
  24. ^ bslh_siphashalgorithm.h
  25. ^ "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が十分に速くない場合について説明します