ようこそ!浜村拓夫の世界へ

    ブログ内検索

    最近の記事

    ブックマーク数の多い記事

    Blog Translation

    Powered By FC2ブログ

    Powered By FC2ブログ
    ブログやるならFC2ブログ


    FC2ブログ LOGIN

    with Ajax Amazon

    衝突しにくいハッシュ値をMySQLの代理キーにする方法

    このエントリーを含むはてなブックマーク はてなブックマーク - 衝突しにくいハッシュ値をMySQLの代理キーにする方法 あとで読む
    MySQLのテーブル設計で、一つ気付いたことがありました。
    主キーに、auto_incrementな連番を用いない方が良い、ということです。


    ●連番の欠点
    連番の欠点は、何かの事情で、連番カラムのデータが失われたら、再び同じ連番を各レコードに割り当てることがで困難であることです。
    物理的なデータ削除等で、連番に欠番が生じていれば、再度連番を割り当てても、ズレが生じます。
    主キーに、このような不安定要素を残しておくことは、堅牢なシステムとは言えません。

    単一の主キー、もしくは、複合主キーを一つにまとめた代理キー(サロゲートキー)は、生成アルゴリズムを決めて、プログラムで割り当てるべきです。

    再現性がない、という点で、乱数も主キーにしない方が良いと思います。

    では、どのようなアルゴリズムで、主キー(代理キー)を生成したら良いでしょうか?

    ●ハッシュ関数の補完
    単純には、ハッシュ関数を使えば良いのですが、ハッシュ関数の欠点は、衝突の可能性があることです。

    ハッシュ関数 - Wikipedia

    ハッシュ関数 (ハッシュかんすう、hash function) あるいは要約関数とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことを要約値やハッシュ値または単にハッシュという。

    ハッシュ関数は主に検索の高速化やデータ比較処理の高速化、さらには改竄の検出に使われる。例えば、データベース内の項目を探したり、大きなファイル内で重複しているレコードや似ているレコードを検出したり、核酸の並びから類似する配列を探したりといった場合に利用できる。



    ハッシュ関数の安全性

    暗号学的ハッシュ関数の安全性を議論する場合、以下の三種類について議論を行う。

    原像計算困難性
    原像計算困難性(Preimage Resistance)とは、与えられたどのハッシュ値に対しても、そのハッシュ値を出力するようなハッシュ関数への入力を求めることが困難であるような性質を言う。ただし、異なる入力から同じハッシュ値が得られるため、そのハッシュ値を得られる入力を一つ求めればよい。

    第2原像計算困難性
    第2原像計算困難性(Second Preimage Resistance)とは、与えられたどの入力値に対しても、その入力値をハッシュ関数へ入力したときのハッシュ値と同じハッシュ値を出力する入力値を求めることが困難であるような性質を言う。

    衝突困難性
    衝突困難性(Collision Resistance)とは、同じハッシュ値を与える二つの入力値を求めることが困難であるような性質を言うのである。

    それぞれの困難性の関係
    原像計算困難性を満たさないハッシュ関数では、任意の入力値からハッシュ値を得られるため、第2原像計算困難性を満たさない。また、第2原像計算困難性を満たさないハッシュ関数では、衝突困難性を満たさない。 すなわち、

     原像計算困難 ⊂ 第2原像計算困難 ⊂ 衝突困難

    である。



    MySQLでTEXT型にUNIQUEなインデックスを張る方法 - 浜村拓夫の世界

    ソルトとは?

    暗号理論におけるソルトとは、ハッシュ処理の際に追加するデータのことです。
    事前に計算済みのハッシュとその元入力の対応表 (レインボーテーブル) で出力を解析される可能性を減らすために利用します。

    端的に言うと、ソルトとはちょっとした追加データです。




    X:ハッシュ値の元になる値
    Y:ハッシュ値
    F:ハッシュ関数
    として、
    Y = F(X)
    で、ハッシュ値が求まります。

    異なるX同士で、同じYが求まる場合が、ハッシュ値の衝突です。

    衝突防止策として、XとYを組み合わせた、Zという値を用意します。

    Z = X + Y = X + F(X)
    というアルゴリズムにすると、異なるX同士で、同じYが求まりハッシュ値が衝突しても、Zは同じになりません。

    (例)
    X1:1111 → Y1 = F(X1) = 4444
    X2:2222 → Y2 = F(X2) = 4444

    X1:1111とX2:2222のハッシュ値が同じ4444となって衝突しても、
    Z1 = X1 + Y1 = 1111 + 4444 = 5555
    Z2 = X2 + Y2 = 2222 + 4444 = 6666
    となるので、Z1とZ2は衝突しません。

    ハッシュ値の衝突を回避する一つの方法として、ハッシュ値の元になっている値を、何らかのアルゴリズムで、ハッシュ値に付け加えれば良いことが分かります。

    今回のハッシュ値は、リレーショナルデータベースのキーに用いることが目的であり、暗号化ではありません。
    従って、衝突困難性が高ければ、暗号強度が低いアルゴリズムでもOKです。

    ハッシュ衝突防止のアルゴリズムについて、Google検索してみましたが、定番の計算方法が分かりませんでした。
    おそらく、数学の整数論とか暗号の理論について調査したら、定番の解法があると思われます。


    ●PHPで実装
    CodeIgniterで、salt+ハッシュの値を生成するヘルパー関数を用意してみました。
    ハッシュ値の文字長は、md5関数にならい、32バイト(32文字)程度になるようにしてみました。

    入力値をUTF16の文字コードで16進数とみなし、各文字の重みを足して、これをsaltとして使います。
    =厳密には、下記の計算では、ハッシュ生成に混ぜてないので、saltじゃないけど。

    <?php  if ( ! defined('BASEPATH')) exit('No direct script access allowed');

    /**
    * Hash 36 - 36進数のハッシュ値を生成する / md5より衝突率が低いはず
    *
    * @access public
    * @param string $str
    * @return string $hash
    */
    if ( ! function_exists('hash36'))
    {
    function hash36($str = '')
    {
    $salt = 0; // 衝突防止用の付加データ
    $arr = preg_split("//u", $str, -1, PREG_SPLIT_NO_EMPTY);
    foreach ($arr as $val) {
    // UTF8 -> UTF16(16進数) -> 10進数 に変換
    // cf. http://blog.sarabande.jp/post/35048351213
    $dec = hexdec( bin2hex( mb_convert_encoding($val, 'UTF-32BE', 'UTF-8') ) );
    $salt += $dec;
    }
    $salt_36 = base_convert($salt, 10, 36);

    $md5 = md5($str);
    $md5_36 = base_convert($md5, 16, 36);

    $hash_36 = $md5_36.'_'.$salt_36;
    $hash = substr($hash_36, 0, 32);
    return $hash;
    }
    }

    /* End of file hash_helper.php */
    /* Location: ./application/heleprs/hash_helper.php */


    上記の処理だと、ハッシュ値は32文字以下になりますが、ピッタリ32文字にしたい場合は、
    $hash_36 = $md5_36.'_'.$salt_36.'========';
    のように、末尾に文字を詰める(padding)しておけば良いと思います。

    ・md5 → 32桁の16進数 → 25桁の36進数
    ・残り7桁を、saltとpaddingで埋めて、先頭から32文字を取り出す

    最初、CRCでいいかな?と思いましたが、PHPのCRCは、計算結果が変わる場合があるそうなので、採用しませんでした。(補正が面倒くさい?)

    PHP: crc32 - Manual

    警告
    PHP の整数型は符号付きで、多くの crc32 チェックサムは 32 ビットシステム上では負の整数になります。 しかし、64 ビット環境では crc32() の結果はすべて正の整数となります。

    つまり、符号なしの crc32() チェックサムの文字列表記を 十進形式で取得するには、 sprintf() もしくは printf() の "%u" フォーマッタを使う必要があります。

    チェックサムの十六進表記を取得するには、 sprintf() あるいは printf() の "%x" フォーマッタを使うか、あるいは変換関数 dechex() を使います。これらはいずれも、 crc32() の結果を符号なし整数に変換することも行います。

    64 ビット環境でも、返り値が大きくなると負の整数を返すことが考えられます。 その場合は十六進変換がうまくいかないので、負の整数については オフセット 0xFFFFFFFF######## を与えます。 十六進表現は最もよく使われる形式なので、この処理が壊れないようにしました。 32 ビット環境から 64 ビット環境に移したときに ほぼ 50% の確率で十進形式での比較が失敗してしまいますが、 それよりも十六進表記のほうを優先したのです。

    今思えば、この関数が整数値を返すようにしたというのがまずい判断でした。 最初から、 md5() のように十六進形式の文字列をを直接返すようにしておけばよかったのでしょう。

    移植性を考慮した選択肢として、より汎用的な hash() を使う方法もあります。 hash("crc32b", $str) は dechex(crc32($str)) と同じ文字列を返します。





    新版暗号技術入門 秘密の国のアリス
    結城 浩
    ソフトバンククリエイティブ
    2008-11-22
    3150円







    関連記事

    コメント

    コメントの投稿


    管理者にだけ表示を許可する

    トラックバック

    トラックバックURL:
    http://hamamuratakuo.blog61.fc2.com/tb.php/971-50550897

    FC2Ad