🔬

カード番号をSalt無しのSHA256でトークン化するのがどのくらい危険か試してみた

2021/04/22に公開

はじめに

後輩から実データからトークンキーを生成するの「SHA256とかでハッシュ化でも良いですか？」と聞かれたので「少なくともSaltは必須だね」的な話をしたところ「Saltは（短い可能性があるから）パスワードとかには使うイメージだったけど元データがそれなりに長ければ要らないと思ってました」的な話題になりました。

十分な時間を掛ければ解けるのでもちろんダメなのですが、そういえば十分な時間ってどのくらいだろうと思いちょっと試してみました。

そこそこ長くて識別子に使われる可能性がある番号だとクレジットカード番号が16桁で良い感じなので試してみました。

クレジットカード番号は何通り？

16桁で0-9の値ですが数字なので先頭に0はおけませんから以下のような式になります。

10^15×9
=> 9,000,000,000,000,000

その数なんと9000兆通り！ 果たしてこれは計算しきれるのでしょうか？
ちなみに実際にはクレジットカード番号には下記のように取りうる範囲が決まってるので、このあたりの業務知識を使えばもっとパターンは圧縮できるかもしれないですね。

サンプルコード

とりあえずJavaでびっくりするくらいナイーブな実装で書いて見ました。並列化もしてないシングルスレッドだしString.formatとかすごく重そう。まあ、実際悪い事しようと思ったら大規模分散環境やビットコインのような専用チップを使うだろうから、最低値を知る感じで。

var digest = MessageDigest.getInstance("SHA-256");

var max = ((long) Math.pow(10, 15)) * 9;
var start = System.currentTimeMillis();
for (long i = 0; i < max; i++) {
    var origin = String.format("%016d", i);
    byte[] encodedhash = digest.digest(origin.getBytes(StandardCharsets.UTF_8));
    if (i % 100_000_000 == 0) {
        var end = System.currentTimeMillis();
        var duration = (end - start) / 1000 / 60;
        System.out.println(String.format("%016d, %3d min", i, duration) + ": " + Base64.getEncoder().encodeToString(encodedhash));
    }
}

実行結果

実行してみました。CPUはAMD Ryzen5 3600 3.5GHzです。さすがに相応に時間が掛かるので1時間でどのくらい生成できたか見てみます。

0000000000000000,   0 min: /NtLQj9OUoOvoknXYu9q7xUOkfzNgQ1D5ecZ0UUS3sc=
0000000100000000,   1 min: I1lt2923PiGMgUueQF3/ve6rib1Bs6gfD73N+3yZ3cw=
0000000200000000,   2 min: wLPVuBN7D+GGfSvvleZeXNbNomPHCdum22IPYKcc02o=
...
0000004300000000,  57 min: a4MlKwfk0636KgNMQI0tScCknkihB3uDjiCWWF9MJDw=
0000004400000000,  58 min: XOqWHXg/vfZDZV1O04GaPbs7KXKS6xZLwn1QUVtTeU0=
0000004500000000,  59 min: lZIncJWW0Ss9SUKmh9BoSz7D+Y0A3Yr03Ei4PXpfJ/Y=
0000004600000000,  61 min: qiF6nBqg3Sp/OXpd+4zxfjxX8usuc8H7hk9bOMq8VlU=

時折多少の揺らぎはあるのですがおおむね1分で１億件が生成できました。意外に作れますね。しかしながら相手は9000兆通りあります。終わるまでどのくらいかかるか計算してみましょう。

9000000000000000 / 60 / 24 / 365 / 100000000
=> 171

なんと171年！これは中々の時間ですね。不可能ではないですが私は死んでるし良いのでは？ と思いますがもちろん気のせいです。

100年ではダメなのか？

100年ではダメなのかは議論の余地があるかもしれません。ただ、大前提として100年かかりません。
今回はマルチスレッドもなんもしてない超シンプルなコードですが、このロジックは原理的にコア数分スケールします。私のこのCPUですら6コア付いてるので30年たらずで終わります。
そもそもGCPで80コアのマシンを1台借りれば2年で終わるのでわずか600万円でクレジットカード番号の全ハッシュテーブルは計算できてしまいます。

また、見るからに雑な私のコードはチューニングの余地はいくらでもあるでしょうし、Hadoopで大規模分散もできます。あるいは専用のチップを使えば計算ははるかに高速に終わります。つまり、すでに誰かが解いたものがこの世に辞書として存在しています。そのため実際の判定は一瞬ですむのでクレジットカードなどの良く知られた組み合わせの少ない値をソルト無しで使うのはセキュリティとして成り立ってないと言えるでしょう。

まとめ

まあ、なんのためにトークン化が必要なのかで変わりますし、そもそも元データがセンシティブなものでなければ全く気にする必要はないのですが、どの程度危ないかは感じれたと思います。

今回雑に調べた限りではGoogleなんかでは流石に見当たりませんでしたが、この程度の時間で計算できるものなら確実に辞書が存在していると思います。ハッシュ関数をトークンとして使うときにはソルトが大事とはパスワードを中心に知られている話ですが実際に計算してみて危なさがより身近になった感じがしました。

ソルトを付けたりあるいHMACを使ったり何らかの秘密情報と組み合わせるのが重要ですね。それら秘密情報の管理がもちろん必要ですけど。

それではHappy Hacking!