翻訳: unordered_mapのハッシュ衝突攻撃とその対策 (neal: Blowing up unordered_map, and how to stop getting hacked on it)


This article is a translation of the following, 
neal's blog: [Blowing up unordered_map, and how to stop getting hacked on it](https://codeforces.com/blog/entry/62393)
Neal, thank you for a very interesting article.

この記事はnealの記事の翻訳です。また、DeepLを多分に活用しています。ありがとうございます。

# はじめに
初期のC++バージョンから`std::set` と `std::map`を使うことができます。これらは便利ではありますが、ツリー型のデータ構造体で管理されているため、各操作(挿入、消去、アクセスなど)に時間がかかります。ついにC++11では、ツリーではなくハッシュで管理する`std::unordered_set`と `std::unordered_map`が使えるようになりました。これらは通常、高速なアクセスを提供しますが、Codeforcesではこれらを使ったsubmitがハッキングされたり、システムテストでTLEする例を見ます。この記事では、これらがどのように攻撃され、逆に、ハッキングされることを気にせずに使うためにはどのように対策ができるのかを説明します。

まず、どのようにして攻撃されるのでしょう？私たちは、ハッシュの操作の計算量は$O(1)$であると仮定しています。これは、入力がランダムであり、ハッシュの衝突がランダムに発生すると仮定できる場合は妥当な仮定です。しかし、ハッキングフェイズなどの敵意を持つ相手が入力を設計している場合はどうでしょうか？我々のハッシュ関数の仕組みを相手が熟知している場合、意図的なハッシュを衝突させるような入力を生成して最悪$O(n^2)$の計算量となることがあるのです。

# ハッシュ攻撃の実際
実際に`unordered_map`でどのように意図的な衝突を引き起こせるか調べてみましょう。まず、私たちは実装を知る必要があります。[GitHub上でgccの実装](https://github.com/gcc-mirror/gcc)で見ていきます。

まず、`unordered_map.h`[(Githubリンク)](https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/include/bits/unordered_map.h)を見ると`__detail::_Mod_range_hashing`と`__detail::_Prime_rehash_policy`を利用しているとわかります。つまり、`unordered_map`は入力値のハッシュを素数でmodし、その値をハッシュテーブルのインデックスとしてに使っているようです。

`_Prime_rehash_policy` を追いかけると `hashtable_c++0x.cc`[(Githubリンク)](https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/src/c%2B%2B11/hashtable_c%2B%2B0x.cc)にたどり着きます。ハッシュテーブルはそのサイズが大きくなると、別の場所で定義されている`__prime_list`配列を参照して次のサイズを決定し変更することがわかります。このリストは`hashtable-aux.cc`[(githubリンク)](https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/src/shared/hashtable-aux.cc)にあります。

さて、`unordered_map`で使うハッシュ関数を理解しなければなりません。`std::hash`を使用しています。このハッシュ関数を理解すれば`n^2`の衝突を起こすために、リストのような値を挿入すればよいかわかります。先ほど、予め定義されている`__prime_list`を見ましたが、ある値が使われるにはmapがこれらの値を使うようにリサイズされなければなりません。用いられる値はコンパイラのバージョンに依存します。gcc 6 以前のバージョンでは`126271`、gcc 7 以降では `107897` で動作します。以下のコードをCodeforcesの[Custom Invocation](https://codeforces.com/contest/1033/customtest)で実行して、どのような出力が得られるか見てみましょう。

(訳注: このテストは手元で実行してももちろんかまいません。ただし、Codeforcesの環境で攻撃を行うならば、Codeforcesの環境を知らなければなりません)

```C++
#include <ctime>
#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 2e5;

void insert_numbers(long long x) {
    clock_t begin = clock();
    unordered_map<long long, int> numbers;

    for (int i = 1; i <= N; i++)
        numbers[i * x] = i;

    long long sum = 0;

    for (auto &entry : numbers)
        sum += (entry.first / x) * entry.second;

    printf("x = %lld: %.3lf seconds, sum = %lld\n", x, (double) (clock() - begin) / CLOCKS_PER_SEC, sum);
}

int main() {
    insert_numbers(85229ul); // AtCoder C++20, C++23 gcc12.2, MojaCoder killer
    insert_numbers(107897);//  CodeForces C++11, C++14 killer
    insert_numbers(126271);//  CodeForces C++17 killer
}
```

```
訳注: 参考
C++11
x = 107897: 0.043 seconds, sum = 2666686666700000
x = 126271: 3.004 seconds, sum = 2666686666700000
C++14
x = 107897: 0.042 seconds, sum = 2666686666700000
x = 126271: 2.923 seconds, sum = 2666686666700000
C++17
x = 107897: 3.257 seconds, sum = 2666686666700000
x = 126271: 0.016 seconds, sum = 2666686666700000
MSC++17 (いずれの素数とも違うテーブルのようで両方高速に動作します)
x = 107897: 0.040 seconds, sum = 2666686666700000
x = 126271: 0.040 seconds, sum = 2666686666700000
```

これらの2つの数値のうちの1つは他のものよりも明らかに長い時間がかかるはずです。他にも(訳注:要素の数に応じて)いくつかの値が使えます。

`cc_hash_table`や`gp_hash_table`のような他のハッシュテーブル([Chilliの投稿](https://codeforces.com/blog/entry/60737)参照)は、衝突を発生させるのがより簡単です。これらのハッシュテーブルは計算に累乗のmodを使っているので、衝突の発生に`mod 2^16`の数をたくさん挿入するだけで良いです。

## ハッシュ衝突攻撃のハッキングから身を守る方法

それではどのようにすればハッシュを攻撃から守れるのでしょうか？`unordered_map`(だけでなく`gp_hash_table`なども)には自作のハッシュ関数に渡すことができます。ここで与える関数は以下のように定義します。

```C++
struct custom_hash {
    size_t operator()(uint64_t x) const {
        return x;
    }
};
```

さて、計算が確定しており処理が予測可能なハッシュ関数は、リバースエンジニアリングして衝突を引き起こすことが容易です。これを防ぐために最初に思い浮かぶアイデアは、高精度クロックの値を利用して(訳注: 時間を利用して)非決定な処理にすることです。

```C++
struct custom_hash {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return x + FIXED_RANDOM;
    }
};
```

しかし、これは十分ではありません。私(neal)の記事[my post on making randomized solutions unhackable](https://codeforces.com/blog/entry/61675)を見てください。上のコードは、全てに全く同じを関数に加えています。これでは、ある2つの数aとbが$a = b (mod m)$を満たすとき、$a + x = b + x (mod　m)$となります。これだけではなく、似たような問題が単純なハッシュ関数では発生します。例えば、適当な奇数するハッシュ計算は乗算すると($2^64$のオーバーフローを発生させる)、$mod　p$を満たす可能性がありますが、 `gp_hash_table`では2の累乗を用いているため問題となります。

では、以下のようなハッシュ関数はどうでしょうか？

```C++
struct custom_hash {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};
```

例えば`gp_hash_table` を使用している場合、この関数はハッキングを受けます。`(1 << 16) + 1, (2 << 16) + 2, (3 << 16) + 3, ...`をこのハッシュテーブルに挿入すると、すべてのハッシュの出力は$mod 2^{16}$となります。(なぜかわかりますか？)

理想的なハッシュ関数は、入力ビットを変更すると出力ビットを変更する確率が半々になることです。先ほどの `x + FIXED_RANDOM` は、この要件を全く満していません。入力の値のある上位ビットを変更したとしても、出力でそれより下位のビットが変更する確率は0です。

私は、非常に高速で高品質な`splitmix64`[(splitmix64.cへのリンク)](http://xoshiro.di.unimi.it/splitmix64.c)を使うのが好きです。これを用いると、安全なカスタムハッシュ関数ができあがります。

```C++
#include <chrono>
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
```

これで、次のように `unordered_map`や `gp_hash_table` を定義することができるようになりました。

```C++
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;
```

上記のプログラムでこれらを使用すると、非常に速く実行されます。

```
x = 107897: 0.035sec、sum = 2666686666700000
x = 126271: 0.031sec、sum = 2666686666700000
```

(again): This article is a translation of the following, 
neal's blog: [Blowing up unordered_map, and how to stop getting hacked on it](https://codeforces.com/blog/entry/62393)