SipHashとそのRust標準ライブラリでの実装
この記事はRust Advent Calendar 2023の14日目の記事です。
はじめに
SipHashはRustの標準ライブラリのstd::collections::HashMapなどでデフォルトで使われるハッシュアルゴリズムです。
HashDos攻撃に対する耐性がありデフォルトのアルゴリズムとして相応しいですが、個人的にHashMapの速度を上げたいときに適当に(耐性のない)他のアルゴリズムに変えてしまいがちなので今回ちゃんと調べてみました。
SipHashとは
Overview
SipHashはPRFの一種で
128bitの秘密鍵と任意の長さの入力から64bitのハッシュ値を生成します。
秘密鍵の内容がバレていない限り、入力がどのようなハッシュ値になるかは予測できないのでHashDos攻撃に対して耐性があるというわけです。
Rustでの秘密鍵の生成
Rustの標準ライブラリでは秘密鍵の生成に、最初だけちゃんとOSから乱数を取得してそれ以降はその値をthread_localに保持して一ずつインクリメントしていくという方法を取っています。
毎回OSから乱数を取得すると遅かったということがコメントに書いてあります。
アルゴリズム
SipHashのアルゴリズムをRustの標準ライブラリの実装とともに見ていきます。
- k0, k1のu64を2つ、合計128bitの秘密鍵と固定値で内部状態を初期化する
XORしてる固定値はb'somepseudorandomgeneratedbytes'のASCIIコードから来ています
とにかくv0-3の各状態が別の値になればいいっぽいです。
# python
>>> ''.join(['%x' % c for c in b'somepseudorandomgeneratedbytes'])
'736f6d6570736575646f72616e646f6d67656e6572617465646279746573'
- (入力の残りが8バイト未満になるまで)8バイトずつ入力を読み込んで内部状態を更新する
miには入力が64bit区切りで入ってきます。
やっていることはc_roundsを呼ぶ前後に内部状態に入力をXORしているだけです。
肝心のc_roundsはRustの標準ライブラリではSipHashの中でもSipHash-1-3という種類が使われているので、compress!を一回だけ呼び出しています。
SipHash-1-3の1の部分が入力の8バイトチャンクに対して一回だけcompress!を呼び出すということを示しています。
compress!はマクロで定義されています(コンパイラの最適化が信用できなかったのかな？)
とにかく、wrapping_add(Add), rotate_left, XORの3つの演算を繰り返して内部状態を更新しています。
上記の三種類の演算のみを用いているこのような関数を頭文字を取ってARXと呼ぶそうです。
特別な命令(AES命令とか)を必要としないのでローエンドなCPUでも高速に動作するという利点があるそうです。
SipHash: a fast short-input PRF Jean-Philippe Aumasson and Daniel J. Bernsteinから引用した画像
各回転の数は機械的に試して決めたそうです。
- 最終出力
入力の残りが8バイト未満になったら、入力の長さ%255を入れて内部状態を更新して、その後に0xffをv2にXORしてd_roundsを呼び出して内部状態を更新して、最後にv0-3をXORして出力します。
SipHash1-3なのでd_roundsは3回compress!を呼び出します。
SipHashの種類
SipHash-c-dという表記でSipHashのラウンド数を表します。各８バイトのチャンクに対してc回compress!を呼び出し、最後にd回compress!を呼び出します。
論文にはSipHash-2-4がおすすめされていますが、Rustの標準ライブラリではSipHash-1-3が使われています。
SipHashのデザイナーのJean-Philippe Aumasson[1]氏的にもSipHash-1-3で十分なようです(https://github.com/rust-lang/rust/issues/29754)。
他のアルゴリズムとの比較
SipHashはその当時の自明な対抗馬であるHMAC-SHA1よりも高速で、特に短い入力に対して最適化されているのでHashMapのようなデータ構造に使うのに適しています。
HMAC-SHA1は安全ですがどうせ秘密鍵を使うのでSHA1より計算量を少なくしても安全性を保てる(超意訳)ということのようです。
歴史
- 2015-05 Rust 1.0.0リリース。このときはSipHash2-4が使われていた https://github.com/rust-lang/rust/blob/1.0.0/src/libcore/hash/sip.rs
- 2015-11 SipHash1-3でも十分だということでSipHash2-4からSipHash1-3に変更
- https://github.com/rust-lang/rust/issues/29754
- RubyでもSipHash2-4からSipHash1-3に変更された https://bugs.ruby-lang.org/issues/13017
- 2016-08 SipHashの実装をアセンブリとかで高速化する案がでたがあんまり変わらなかったのでやめる
-
Serious Cryptographyの著者でもあります ↩︎
Discussion