【PHP】前方一致である程度検索可能なハッシュ値の作り方

　稀にハッシュ化済みの値をハッシュ化前の値で検索しなければいけない時があります。その様な際に全件についていちいち一致するか否かをチェックする様なつくりでは実行時間が非常に長くなり問題となってしまいます。これの対策としてある程度一致するか否か確かめる対象を絞り込み、高速化を狙える様にしたくなります。この要望を叶える方法の一つは前方一致である程度検索可能かつハッシュ化した値を保存する方法です。より具体的には「元の値の先頭N文字」+「元の値のハッシュ値」を組み合わせた値を保存します。これにより前方一致検索を行いつつ、ハッシュ値による一致するか否かの検証もできます。

　実装例は次です。

<?php


class SearchableHash
{
    protected array $conf = [
        'prefix_length' => 5,
    ];

    /** 前方一致検索可能なハッシュ化 */
    function toHash($input): string
    {
        // 元の値の先頭N文字を取得
        $prefix = substr($input, 0, $this->conf['prefix_length']);

        // 元の値のハッシュ値を取得。
        // ハッシュ化アルゴリズムは目的に応じて要変更。セキュアにすべきか否かとか速度とかが目安
        $hash = hash('sha256', $input);

        // 元の値の先頭N文字とハッシュ値を組み合わせて返す
        return $prefix . $hash;
    }

    /** 前方一致検索例。Laravelのクエリビルダを使用 */
    function search(string $input, callable $searchQuery): array
    {
        // 検索したい文字列の先頭N文字を取得
        $searchPrefix = substr($input, 0, $this->conf['prefix_length']);

        // データベースから検索したい文字列の先頭N文字に一致するレコードを取得
        $results = $searchQuery($searchPrefix);
        /*
            $searchQuery は例えば次の様なクロージャ。どこに保存するかをこのクラスの外に任せているため、どこから読むかも外に任せている
            $searchQuery = function(string $searchPrefix) {
                return DB::table('searchable_hashes')
                    // like で前方一致検索
                    ->where('searchable_hash', 'like', $searchPrefix . '%')
                    ->get();
            };
        */
        // 完全一致するレコードだけを保持するための配列を用意
        $matchedResults = [];

        // 結果の中から、元の入力値と完全一致するハッシュ値を持つものだけを取得
        foreach($results as $result) {
            // 元の入力値とハッシュ値の完全一致確認
            if(hash('sha256', $input) === substr($result->searchable_hash, $this->conf['prefix_length'] - 1)) {
                $matchedResults[] = $result;
            }
        }

        // 完全一致した結果を返す。該当するものがなければ空配列を返す
        return $matchedResults;
    }
}

// 使用例
$hasher = new SearchableHash(); // ハッシュ化クラスのインスタンスを生成
// ハッシュ化して保存
$hashed = $hasher->toHash('hoge');
var_dump($hashed);
DB::table('searchable_hashes')->insert([
    'searchable_hash' => $hashed,
]);
// ハッシュを検索
$matched = $hasher->search('hoge', function(string $searchPrefix) {
    return DB::table('searchable_hashes')
        // like で前方一致検索
        ->where('searchable_hash', 'like', $searchPrefix . '%')
        ->get();
});
var_dump($matched);

　おおまかには元の入力値を一部平文で残しておき後からそれを使って検索できるようにする、という流れです。こうするとそれなりの速度でハッシュ化済みの値を平文で検索できます。この手法には注意点が一つ、難点が一つあります。注意点は入力値の長さを長くとる必要があることです。理由はどうあれハッシュ化済みの値のみ残すようなシステムで平文で入力値全体が残っているのはよろしくないです。難点の一つはセキュリティ的に思いっきりタイミング攻撃の餌食ということです。文字列の比較をタイミング攻撃に安全な hash_equals などにしても検索する内容やヒットした件数やループの長さなどで何がハッシュ化されているか予測されやすいです。このためセキュアな性能が要求する場面に用いるにはいささか不完全です。