Xorshift を用いた Zobrist hashing を衝突させる方法

概要

Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに $0$ になる。

Xorshift

説明は Wikipedia に丸投げする。本記事では簡略化のため、実装例の一番上にある周期 $2 ^ {32} - 1$ の実装について議論する。

Zobrist hashing

$N$ 個の要素があるとして、要素 $i$ に乱数 $r _ i \in \mathbb{Z} _ {\geq 0}$ を割り当てる。このとき、集合 $S$ の hash $h(S)$ を $\displaystyle \bigoplus _ {i \in S} r _ i$ で定める。ただし $\oplus$ は bitwise xor とする。この hashing の方法を Zobrist hashing と呼ぶ。

hash の衝突

異なる集合 $T _ 1, T _ 2$ について $h(T _ 1) = h(T _ 2)$ となることを衝突と呼ぶ。 Zobrist hashing の場合 $h(T _ 1) = h(T _ 2) \Leftrightarrow h(T _ 1 \mathbin{\triangle} T _ 2) = 0$ であるから、 $S \neq \emptyset$ かつ $h(S) = 0$ となるような $S$ が分かれば衝突を引き起こすことができる。

結論から言うと、 $r _ i$ を Xorshift が $i$ 番目に出力した値として設定した場合、seed に依存せず $h(S) = 0$ となるような $S \subseteq \lbrace 0, 1, \dots, 32 \rbrace$ が存在する。 Xorshift の乱数列は途中から切り出しても何らかの seed を与えた Xorshift の乱数列であるから、 $r _ i$ の設定が行われるまでに何度か乱数生成されていても衝突することになる。思いつく回避方法を挙げる

$r _ i$ の設定を行う際に ~~1 つ飛ばしや逆順にするなどの~~ *1 変化を加える。ソースコードを読まれた場合対応される可能性がある。
Xorshift における shift の幅などを変える。ソースコードを読まれると対応される上、パラメータを間違えると乱数の質が落ちる。
Xorshift 以外の乱数生成アルゴリズムを用いる。

$S$ の存在の証明、及び構成方法

32 bit 整数をベクトル空間 $V := \mathbb{F} _ 2 ^ {32}$ の元として解釈する。整数の xor が $V$ における $+$ に対応することに注意せよ。このとき、Xorshift における演算は全て $V$ 上の線形変換となっている。従って、線形写像 $A: V \to V$ によって Xorshift は以下のように表現できる (酷く厳密性に欠ける表現ではあるが)。

V Xorshift() {
    static V y = seed;
    y = A(y);
    return y;
}

つまり、Xorshift の乱数列は初項を $t$ として $t, A(t), A ^ 2(t), \dots$ と表現される。 $A$ の最小多項式を $p(X) \in \mathbb{F} _ 2 \lbrack X \rbrack$ とすると、定義より $p(A)(t) = 0$ である。 $S := \lbrace i \mid \lbrack X ^ i \rbrack p(X) = 1 \rbrace$ とすると、 $S$ は求める集合になっている。

Cayley-Hamilton の定理より、 $p$ として最小多項式ではなく固有多項式を用いても良い。周期 $2 ^ {128} - 1$ の実装例を用いた場合でも、全く同様の議論で衝突を起こすことができる。

Wikipedia の 32 bit の実装を衝突させる例

固有多項式を用いて、 $S = \lbrace 0, 6, 9, 14, 15, 17, 18, 19, 20, 21, 32 \rbrace$ を得た。 seed を自由に変えて実行してみると、毎回 hash が衝突していることが分かる。

[C++] gcc 11.1.0 - Wandbox

追記

$\mathbb{F} _ 2 \lbrack X \rbrack$ における $2$ 乗は $X$ の指数を $2$ 倍したものに等しいため、Xorshift を $1$ つ飛ばしにしてもそのまま衝突する。また、 $\mathrm{rev}(p) p$ は reverse について不変なので、Xorshift を逆から読んでも衝突する。