Help us understand the problem. What is going on with this article?

hashアルゴリズムとハッシュ値の長さ一覧(+ハッシュ関数の基本と応用)

「ハッシュ値の衝突(コリジョン)」や「データの改ざん防止」など、複数のハッシュ・アルゴリムを組み合わせるためにハッシュ値の「長さ」と「速度の目安」一覧が欲しい

TL; DR(このハッシュ関数は何文字?)

この記事はハッシュ関数の出力結果を桁数ごとに、まとめたものです。

ハッシュ関数の各々の「アルゴリズムが何文字の 16 進数で返してくるか」の事前確認にご利用ください。

また、各アルゴリズムの PHP 7.2.6 での計算速度も記載しています。しかし環境だけでなく PHP のバージョンによってかなり速度が異なります。速度は目安程度にご利用ください。

なお、TS;DR では「ハッシュ関数の基本」や「ハッシュ値の長さの具体的な用途」を記載しています。

🐒  ちなみに「n バイトって HEX 文字列で最大何文字だっけ?」という場合は、単純に n を2倍してください。(1バイト=0xFF、例:4バイト=HEXで8桁=FF FF FF FF


ハッシュ・アルゴリズムとビット長の一覧
(ハッシュ値の長さ一覧)

すべて同じメッセージ(文字列)をハッシュ化したものなのに、ハッシュ値の長さ、つまりビット長が同じでも値がまったく異なることに注目ください。

仕様
  • 検証環境:macOS HighSierra(OSX 10.13.6), PHP 7.2.6(cli), MacBookPro Early 2015, 2.7GHz Corei5, Mem 8GB 1867MHz DDR3
  • ハッシュするメッセージ:「Hello Qiita!」
  • ループ回数:1,000,000 回(100 万回)
  • 速度:上記ループの 10 回ぶんの平均値
  • 並び順:桁数の少ない順 → 速い順
  • メッセージダイジェストは横スクロールをさけるため 8 桁(4バイト)ごとのブロックに分けています
  • 測定のソースコード @ Paiza.IO

8 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
fnv132 4 Byte 0.157887 sec b04649f6
fnv1a32 4 Byte 0.157962 sec 129b42dc
adler32 4 Byte 0.165301 sec 1bf5042e
crc32 4 Byte 0.169681 sec dd54ff69
crc32b 4 Byte 0.172050 sec ad6adc0d
joaat 4 Byte 0.173369 sec 2cbbf315

16 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
fnv164 8 Byte 0.168120 sec 97bfaffd 885daad6
fnv1a64 8 Byte 0.176964 sec 07c72cc2 7b5f8b5c

32 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
md4 16 Byte 0.284748 sec e2500f3f 1eb028a4 563ca3d4 35028996
md5 16 Byte 0.337097 sec 7c414ef7 535afff2 1e05a36b 1cfc9000
tiger128,3 16 Byte 0.341727 sec 60bd4df9 e039716f 07c9ecd4 4c203d34
tiger128,4 16 Byte 0.397596 sec 7c20d9b5 d9e79da7 b5241a08 a353018a
ripemd128 16 Byte 0.553369 sec 0ff7eaf1 38540680 8e92e642 28a79243
haval128,3 16 Byte 0.954699 sec a8fe5c62 4c856077 d07db6bc 9a7f1275
haval128,4 16 Byte 1.027350 sec b5ee64c0 6a003d55 65108356 08c6a34c
haval128,5 16 Byte 1.197690 sec ad189ff3 183c9cfe cf5a39e3 45ba95f8
md2 16 Byte 4.762099 sec 8cd3c9c1 f1079b15 639ddab1 2227d400

40 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha1 20 Byte 0.348829 sec 5d8793ae d96d808a b6af8e47 5ce244e8
a604e478
tiger160,3 20 Byte 0.367638 sec 60bd4df9 e039716f 07c9ecd4 4c203d34
6f07e46a
tiger160,4 20 Byte 0.399170 sec 7c20d9b5 d9e79da7 b5241a08 a353018a
bf178a02
ripemd160 20 Byte 0.694799 sec 99a6c172 52ae4e64 e8d22853 c54ee2ad
44089160
haval160,3 20 Byte 0.900242 sec aba140dc e20ac7a2 615053de 4336e343
37a49b46
haval160,4 20 Byte 1.033398 sec 6bc4fecd c33d5d21 14c695ff f449d333
58f3030d
haval160,5 20 Byte 1.197252 sec d87a41cb 73469426 42faf2ae 7d62e81a
eba5dcc6

48 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
tiger192,3 24 Byte 0.394713 sec 60bd4df9 e039716f 07c9ecd4 4c203d34
6f07e46a 9c308ef7
tiger192,4 24 Byte 0.410200 sec 7c20d9b5 d9e79da7 b5241a08 a353018a
bf178a02 0a74f3fb
haval192,3 24 Byte 0.874294 sec e2b0c018 6b1cc119 0eebe1be 9d61953d
2dd78ba4 8136086c
haval192,4 24 Byte 1.031765 sec 7540fa22 a5714124 cf942e1b 31a890b9
bb59d58c e5a61157
haval192,5 24 Byte 1.211350 sec e4a6b10a d8286eaf 8cb3f225 950c2f93
b6fdab8c 601626c8

56 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha224 28 Byte 0.713225 sec d72d6ef7 0a788b3e 7f720b5d 88f20a13
bf161c31 b260fd34 6573094d
sha3-224 28 Byte 0.817025 sec e833eab3 4fbefbe8 9e44dcf1 d4ea9990
10981761 22f51708 df9cd9d0
sha512/224 28 Byte 0.825188 sec e205b15d 16eda0ce e195d210 73edca14
a69198e9 0070b9b0 09f7cb16
haval224,3 28 Byte 0.842655 sec a69049ca 88565098 a6f5e2bc adb22980
e59da983 9a779b63 c214e019
haval224,4 28 Byte 1.045480 sec 090b25d0 e8a0f5ef ecf6b683 5be72fe5
6913b34e 2d086922 3b1ac5d1
haval224,5 28 Byte 1.209415 sec 5343b4b1 a16119c5 dcd7726e 53128841
fecb7607 88e9008f 6c6f2cb6

64 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
ripemd256 32 Byte 0.574046 sec e0fe9c49 b1a59fae 47096909 83e62829
4887b161 5722a62c 2c4187be 816b058d
sha256 32 Byte 0.668654 sec e863d36c 24ada694 fa77454b 33e8f9b9
545d372a ae251e87 79fc25df 16943fed
sha3-256 32 Byte 0.824698 sec cedaea23 33478d77 bc9ed3e3 3303f455
85af1917 4a451ce9 3029fedc dd4d1ecb
sha512/256 32 Byte 0.833001 sec aaa2e875 112de9b6 1744d4a0 ae757e40
cd12008a 0f3948fb 7c42a8cd 48c361b8
haval256,3 32 Byte 0.845439 sec 5f788c8a 5359387b acf7bf60 ff4dd08d
e7176205 a0aae1ce 4f485b40 126c0d2f
haval256,4 32 Byte 1.048196 sec 4ebb9e6f a6c045b0 cbba419e f06ac973
b2fd4914 f746e142 bb6b840f bd836158
haval256,5 32 Byte 1.218753 sec c99614ae a2985f43 f480d029 bcb7974b
f5aface5 8730c9d6 f3141a67 58270431
gost 32 Byte 1.828385 sec 667f4328 0ff9e0a5 9c15de57 022becf3
cd1a48f8 d37a165c 87576b6f 814fa482
gost-crypto 32 Byte 1.849877 sec 7ebf0f97 0f1246b6 aea110d7 32cbcdfd
b0169cf1 7336bae7 814e99f1 8abfbd21
snefru 32 Byte 2.841073 sec ad081810 0ab15234 b13b8d09 ad0c519a
35469221 adbf8c5f a71594ca f7dfddc2
snefru256 32 Byte 2.850217 sec ad081810 0ab15234 b13b8d09 ad0c519a
35469221 adbf8c5f a71594ca f7dfddc2

80 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
ripemd320 40 Byte 0.725499 sec 6d152e32 fee2b979 024b8cff e416c898
16032680 779f7c3a 93c9aa26 35441245
8d4a9010 ad8fdfa5

96 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha384 48 Byte 0.831855 sec b10497cf 49601678 4d8413a4 662983a8
dc4ac470 039ea755 d5ec985f 1aab04ee
26dc3d67 71bbe404 75ea7d13 5a97ba58
sha3-384 48 Byte 0.835068 sec e83e54ee 323dafb5 ca2d800f d479e1cc
94502362 93d5ad74 36228519 aa657ea3
d1da8bb6 2d07035d ec1ece2f 428ec8dc

128 桁のハッシュ値

アルゴリズム バイト長 速度 ハッシュ値
sha3-512 64 Byte 0.851400 sec 9d1aaed0 79bac194 6a5fbafb 4285ec5b
dcf0053a 9e005590 46884a14 8f28fcb9
02441b49 cb3a8277 5834a244 4dd183ed
a36cee90 0f5662f8 2353fae7 e7111740
sha512 64 Byte 0.860255 sec cac9036c 1dd3652f c550e99a 4ec2b066
d69d6a40 a369bc85 e3078960 e6f26012
4138f5d0 f4e9a6e0 47dfb833 c9dd9b33
76d02d49 be37de26 dd6234d4 e79cc09e
whirlpool 64 Byte 1.041927 sec 488c6cd6 eccb5348 8a7c7617 8c89d514
16b8eb2b 88a30b79 71f1f176 70e27659
fc477cd9 6ade86e4 b6176c5e f2f67068
89606786 4ce15443 eff90733 fd4fcf4c

TS;DR

最速のDBキー検索を求めて with SQLite3

ハッシュ値の衝突は別のアルゴリズムでは衝突しない(限りなく)

衝突のイメージ
// 値が微妙に異なる $a と $b
$a = 'xxxxxxxxx..1..xxxxxxxxx'; // 長ったらしい値 a
$b = 'xxxxxxxxx..0..xxxxxxxxx'; // 長ったらしい値 b

$result_sha1 = (hash('sha1', $a) === hash('sha1', $b));
$result_md5  = (hash('md5',  $a) === hash('md5',  $b));

 // $result_sha1 -> true, 偶然にも衝突が発生!
 // $result_md5  -> false, アルゴリズムが異なると衝突しない(可能性が高い)

古くはダウンロード・ページなどでファイルの改ざんや破損がないかを比べるのに使われていたり、身近なところではアクセス・トークンの作成、いつもお世話になっているパッケージマネージャーのパッケージ管理や、みんな大好き Git のコミットID にも使われている「ハッシュ関数」。

近年話題のブロックチェーンなどではかなめの関数とも言えるなど、今後もさまざまな場面で活躍が期待される関数です。

ハッシュ関数の基本と特徴

ハッシュ関数は、任意のアルゴリズムとデータを渡すと「ハッシュ値」と呼ばれる値が返ってくる関数のことです。ほとんどのプログラム言語でハッシュ関数は実装されていますが、使用できるアルゴリズムは環境によって異なります。

ハッシュ関数には4つの大きな特徴があります。

  1. 同じ結果:アルゴリズムと引数が同じ場合は、同じハッシュ値が返ってくる。
  2. 予測困難:入力の規則性に対して出力に規則性がないため、ハッシュ値から元の値の予測は難しい。※
  3. 逆算不可:ハッシュ値から元の値(引数の値)は計算式による算出ができない。※
  4. 固定長値:ハッシュ値は固定長の数値で返ってくる(一般的に n 桁の HEX 文字列)

総当たり攻撃による算出や辞書攻撃による予測の場合除く。また、後述する暗号学的ハッシュでないアルゴリズムは暗号学的ハッシュと比べ、より予測可能です。

つまり、「結果からオリジナルの予測が難しい」のと「同じ結果が得られる」のが一番の特徴です。

このハッシュ関数の戻り値である「ハッシュ値」を生成するには、本記事の TL;DR で紹介しているように、色々なアルゴリズムがあります。各々異なった思想や目的で設計されていますが、いずれのアルゴリズムでも「引数が同じであれば戻り値も同じ」という特徴は変わりません。

ハッシュ値とは何か

では、ハッシュ関数の戻り値である「ハッシュ値とは何か」の前に、以下の "beef" という文字列をハッシュ値にした例をご覧ください。

bashopenssl コマンドと、PHP の hash() 関数を使ってみました。どちらを使っても、「引数が同じ場合は結果も変わらない」「塩を 1 足すだけで結果が大きく変わる」ことに注目です。

ハッシュ・ド・ビーフの例

引数が同じ(同じ具材)
$ # 粗挽き牛ミンチ
$ echo -n 'beef' | openssl md5
34902903de8d4fee8e6afe868982f0dd

$ # 粗挽き牛ミンチ(言語が違っても同じアルゴリズムと引数なら同じミンチ肉)
$ php -r 'echo hash("md5", "beef"), PHP_EOL;'
34902903de8d4fee8e6afe868982f0dd
具材を変えてみる
$ # ハッシュド・ポテト
$ echo -n 'poteto' | openssl md5
147f31c730caa77f8a3440e549264a2e

$ # トマト・ペースト
$ echo -n 'tomato' | openssl md5
006f87892f47ef9aa60fa5ed01a440fb
引数を少し変化させる(味付けしてみる)
$ # 粗挽き牛ミンチ + 1g の塩入り
$ salt=1; echo -n 'beef'$salt | openssl md5
30017279d6a5bac241e764eeed261dd8

$ # 粗挽き牛ミンチ + 1g の塩入り(コックが違っても同じレシピなら同じ味)
$ php -r '$salt=1; echo hash("md5", "beef" . $salt), PHP_EOL;'
30017279d6a5bac241e764eeed261dd8
より細かいアルゴリズムに変えてみる
$ # 絹ごし牛ミンチ
$ echo -n 'beef' | openssl sha512
8cd8bb0cef938ef9cd054c2c2cb965e83310ab5c197cb5fc8f35892a44c1a028bac9e1bcd6248580fa2739cc96074885ea3ee116ef35c2d8f6124270aeff50b7

$ # 絹ごし牛ミンチ(コマンドの言語が違っても同じアルゴリズムと引数なら同じミンチ肉)
$ php -r 'echo hash("sha512", "beef"), PHP_EOL;'
8cd8bb0cef938ef9cd054c2c2cb965e83310ab5c197cb5fc8f35892a44c1a028bac9e1bcd6248580fa2739cc96074885ea3ee116ef35c2d8f6124270aeff50b7

$ # 絹ごし牛ミンチ+ 1g の塩入り
$ salt=1; echo -n 'beef'$salt | openssl sha512
a528829f370819123ad3fb04d8066b77ec79ce6eddad07e5b2c925bbd9b2e699e73428d23315875c29b45500b8c767262cf5546e33974e4f7a6102abd1bb045e

$ # 絹ごし牛ミンチ+ 1g の塩入り(コックが違っても同じレシピなら同じ味)
$ php -r '$salt=1; echo hash("sha512", "beef" . $salt), PHP_EOL;'
a528829f370819123ad3fb04d8066b77ec79ce6eddad07e5b2c925bbd9b2e699e73428d23315875c29b45500b8c767262cf5546e33974e4f7a6102abd1bb045e

beef の原型はありませんが、元は beef もしくは beef1 であることは確認できそうです。

つまり、「成分表上は同じだが、原型を留めていない状態」を「数値の文字列にした値」がハッシュ値です。プログラミング言語のハッシュ関数のオプションによって、数値の文字列でなくバイナリとして取得できるものもありますが、いずれにしても数値として認識できる値で返ってきます。

ハッシュしたてのビーフはミミズにしか見えませんが、「覆水盆に返らず」でも「水である」ことはわかるようなイメージです。

ハッシュ関数によっては、暗号化にも使われているアルゴリズムを利用しているものがあります。そのためか、ハッシュ関数を暗号の一種のように説明しているブログもありますが、違います

暗号は「可逆」、つまり元に戻せる(復号できる)とわかっているから暗号と呼ばれます。反対にハッシュ関数は「非可逆」、つまり「元には戻せないことが特徴」であるため、ハッシュ化は暗号化ではありません

この違いは意外に重要なのですが、「暗号学的ハッシュ関数」を説明する時に「暗号学的な特性をもたなければいけない」という言葉から、誤解が生まれているようです。

この言葉意味することは、「A → (処理) → B」としたとき「B から A がバレてはいけない」し、「A から B を作成」したときは「同じ結果でなくてはいけない」というだけのことです。

しかし暗号化ではないものの、ハッシュ値は暗号と密に関係しています。ハッシュ値は暗号データの担保情報としても使われるためです。

特に暗号通信においては「切っても切れない関係」にあります公開鍵・秘密鍵暗号では、公開鍵を担保する情報としても使われるからです。

🐒 【余談】「公開鍵・秘密鍵暗号」とは

「公開鍵・秘密鍵暗号」とは、ペアとなる A と B の2つの鍵があり、片方の鍵で暗号化したものは、もう片方の鍵でしか復号できないタイプの暗号です。

つまり A 鍵 で暗号化したものは同じ A 鍵 では復号できません。ペアとなる B 鍵 でしか復号できません。また、その逆もしかり・・・です。

この特徴により、片方の鍵を公開しておき、その公開している鍵で相手に暗号化してもらえれば、もう片方の鍵を持つものでなければ復号できないデータが作れます。鍵を公開してるのに、安全に暗号通信やファイルのやりとりが行える魔法が使えます。鍵を公開してるのに、です。

ちなみに「鍵」とは、いわゆるパスワードと同じ役割をするものです。しかし、ワード(単語)ではなく、覚えられないくらいの長い不規則な文字列、もしくはそれをファイルにしたものを「鍵」と言います。そして一般的なパスワードとの違いは自分で決められるものではないことです。伝わるかわかりませんが、「復活の呪文」をファイルに落としたようなものです。(鍵の例 @ GitHub)

重要なのが A 鍵B 鍵 は「親」と「子」の 1:1 の関係になっていることです。「親の鍵」からは同じ「子の鍵」は何度でも作成できますが、その逆(子から親の鍵)は作成できません。

そのため「親」の鍵で暗号化したデータは同じ「親」の鍵では復号できませんが、復号に必要な「子」は作れてしまうということです。つまり、ユーザーは「親の鍵」さえ大切に保管しておけばよく、必要な時に「子の鍵」を作成し、外部に公開するのが一般的です。

このことから親の鍵を「秘密鍵」、子となる鍵を「公開鍵」と呼びます。秘密鍵は「シークレット・キーSecret Key」もしくは「プライベート・キーPrivate Key」、公開鍵は「パブリック・キーPublic Key」とも呼ばれます。

また、「公開鍵で暗号化」し「秘密鍵で復号する」といった説明の記事が多いのですが、どちらの鍵でも暗号化できますし、反対の鍵で復号できます

この2つの鍵ですが一般的に素数を使って作成されています。例えば、自然数 15 を素因数分解すると 3 と 5 ですが、3 という数からは 15 はわかりません。3 を素数とする自然数は無限にあるからです。また、5 からも 15 はわかりませんが、3 と 5 からは 15 が簡単にわかったり、15 と 3 からは 5 が作成できるような仕組みを使っています。

逆に従来の1つのパスワード(鍵)で暗号化および復号できる暗号方式を「共通鍵暗号」と呼びます。「公開鍵・秘密鍵暗号」と比べ「共通鍵暗号」は処理速度が速い・データサイズが小さいという特徴もあるため、大きなファイルの場合は「共通鍵暗号」で暗号化し、その鍵を「公開鍵・秘密鍵暗号」でやりとりするという手法が多くとられます。

このハッシュ関数の「非可逆」な特徴は、一般的に「パスワードの保存」などに使われます。特に「パスワードはサーバーに保存しておきたくない」が「パスワードが登録したものと同じか確認したい」という、覚えたくないけど答えられるようになりたい、みたいなわがままです。

具体的には「パスワードをハッシュ化して保存する」ことで可能です。パスワードが正しいかの確認はハッシュ値を比較すれば良く、「ハッシュ値が流出したとしても元のパスワードはわからない」だけでなく「管理者すら元のパスワードはわからない」といったメリットがあるからです。パスワード流出事件があると「自分たちでもわからない状態で保存されているから云々うんぬん」という話しがでるのもこのためです。

しかし「引数が同じ場合は戻り値も同じ」という、もう1つの特徴により、流出したデータがハッシュ化されていても意味をなさないことがあるのです。別途、パスワード・リストなどがあった場合です。なぜならパスワード・リストからパスワードをハッシュ化して同じ値を探せばいいからです。つまり「辞書攻撃に使える」ということなのでハッシュ化したからといって安心できません

ハッシュしただけでは味気ない

さて、ハッシュ関数や暗号関数を触っていくと「salt」という言葉が出てきます。

これは、各々のデータに加えるランダムな数値や文字列のことです。先の例で言えば beef に加えた salt=1 です。

料理でいう「塩加減」のように「同じ具材でも塩の加減1つで味が変わるため、毎回調整が必要で加減も秘伝hidden」と言ったイメージが近いのですが、「塩土化」、つまり「戦時中の敵国が占領地の土地に塩を撒いて使えなくする」から来ている説もあるようです。

そして、この「salt」(塩)は基本的に個々のデータに加えるのですが、全体に加える「pepper」(胡椒)と呼ばれる値もあります。

例えば、下記はプレーンな(加工や手を加えていないの状態の)パスワード情報です。偶然にも user1user2 のパスワードが同じです。

ユーザ名 パスワード
user1 passw0rdA
user2 passw0rdA

上記だと流出時にバレバレなので、次のような処理をします。

passwdとsaltとpepperの文字列変数をつなげてMD5でハッシュ化する例
$passwd_hashed = md5($passwd . $salt . $pepper);

スクリーンショット 2019-09-08 22.46.20.png

DB の保存で考えると、定数に pepper='pepperA' と設定しておき、テーブルは以下のようなイメージになります。

ユーザ名 パスワード
user1 7915e17989dcbb1d2132c1d207ef9e1d
user2 5ee508cb664f91000826933e626cd5df
ユーザ名 ソルト
user1 saltA
user2 saltB

DB ファイル自体が流出したらテーブルをわけても同じことであるため、パスワードとソルトを同じテーブルに格納する場合もあります。どこに格納するかは運用の考え方しだいだと思います。

また、実際には以下のように、より複雑にシェイクします。

  1. "saltA" などの単純な文字列でなくランダムな数値や文字列を使う
  2. アルゴリズムを sha256sha512 などのより複雑なアルゴリズムを使う
  3. hash('sha256', hash('sha256', $value))二重・三重にハッシュ化させたりする

複雑さが増すほど処理速度やレスポンスの問題も出てくるため、どの程度 複雑化させるのかも運用の考え方しだいになると思います。いずれにしても、引数に $salt$pepper という絶対公開しない値を引数に加えることで、予測を難しくさせているのです。

もちろん salt 値や pepper 値が流出してしまうと意味がありません。シオシオのパーです。つまり、秘密鍵と同じくらい扱いには気をつけないといけないので、「ハッシュ化しても安心できない」とわかると思います。

ところが、せっかく塩・胡椒をして独自の味付けをしたのに「同じ味や歯ごたえなのに実は合成肉だった」みたいな、なりすましが発生するご時世になってきました。詳しくは後述の「MD5SHA-1 のセキュリティについて」でも説明しますが、塩・胡椒しただけの粗挽き肉ではグルメセキュリティ重視の人を唸らせることは難しくなってきているのです。

ハッシュ関数はセキュリティ用途だけではない

しかし、データのセキュリティ用途ばかりに目を向けるのではなく、「処理」に目を向けると「数値で返ってくる」という特徴を活かすことができます。

ハッシュ値の王道の使い方は「変更の検知」です。1バイトどころか1ビットでも違いがあるとハッシュ値の結果は大きく変化します。この特徴により、大量の文書(データ)であっても1文字の変化を検知できるのです。(変化した場所の特定は別の話し)

この「本編を詳細に見なくてもザッと見るだけで把握できる」的な意味で「ハッシュ値」を「ダイジェスト値」もしくは「メッセージ・ダイジェスト」と呼ぶこともあります。また「ハッシュ関数」は「要約関数」とも呼ばれますが、個人的に「『要するに...』と言われても、まったく意味がわからないのと似た関数」だと思っています。

むしろ、海外ドラマなどの冒頭で流れる「前回までのなんとか」のダイジェストのように「以前が何であったか、わかっている人にしか伝わらない確認をするためのもの」といったイメージです。

🐒 「ハッシュ値」「メッセージ・ダイジェスト」どちらも同じものですが、暗号などの確認に使う場合に「ダイジェスト値」と呼ぶことが多い気がします。この記事では「ハッシュ関数」の値という意味で「ハッシュ値」と統一します。

ZIP や ISO といった巨大なアーカイブ・ファイル(複数ファイルを1つにまとめたファイル)をダウンロードする際に、リンクと一緒にファイルのハッシュ値を添えておけば、ダウンロードしたファイルのハッシュ値と比べて破損もしくは改ざんされていないことが確認できます。ここらへんはみなさんも馴染みがあると思います。

逆に言えば、「ハッシュ値が同じであれば、データに変更はない」という使い方でデータの管理にも利用できます。

みんな大好き git などは、ファイルのハッシュ値を比較して変更があったかを検知していたり、いつもお世話になっているアプリやライブラリなどのパッケージマネージャーも競合や改ざんを防ぎつつ共通の動作をさせるために ライブラリ名<ハッシュ値> のような形式で内部管理していたりします。他にも BitTorrent などは、ファイルのハッシュ値を使うことで、ネットワーク上に同名のファイルがあっても、個別に認識できるようになっています。

このように「ファイル名が異なっていても中身が同じファイルであった場合はハッシュ値は同じ」ということを逆手に利用した、データの管理方法に使えます。

預言者の予言を担保する(当たるとは言ってない)

さて、この「ハッシュ値が同じならデータに変更はない」仕組みをさらに工夫すると、電子証明書が作れます。

どういう事かと言うと、「ハッシュ値」と「公開鍵・秘密鍵暗号」を組み合わせることで電子証明書が作成できるのです。

具体的に言うと、ファイルのハッシュ値を自分の「秘密」鍵で暗号化して公開すれば、それが電子証明書になるのです。

つまり、自分が正しいと認めたファイルのハッシュ値を自分の「秘密鍵」で暗号化し、それを証明書としてファイルと一緒に公開し(相手に渡し)ます。相手は、その公開鍵で証明書を復号して対象のファイルのハッシュ値と比較します。同じであれば、相手は自分が認めたファイルであることが確認できます。

これは秘密鍵の「片方の鍵で暗号化したものは、もう片方の鍵でしか復号できない」という特徴を活かした手法です。

他にも、「対象のファイルと片方の鍵をセットでハッシュ化したもの」を署名(サイン)とし、もう片方の鍵で検証するシュノア署名と呼ばれるシンプル・効率的かつ堅牢な手法もあります。これは Ed25519 と呼ばれる署名方法で、最近では RSA に変わってこれが主流になりつつあるようです。

いずれの方法でも、このような、「暗号鍵のペアの作成」「証明書の作成」「暗号の復号および検証」といった一連の仕組みを総合して「デジタル署名」と呼びます。

デジタル署名の面白い使い方としては「予言の書」などがあります。

事前に予言と予言した日付を書いておき、「秘密」鍵で暗号化したその予言(ファイル)と、その電子証明書を公開します。そして予言後に「公開」鍵を公開するなどです。まぁ予言なので普通に公開しちゃっても良いんですけど。

肥大化しないパターン ID

「引数がどれだけ長くても、ハッシュ値は固定長の数値」であることもメリットです。つまり、データがそれ以上増えないということです。

例えば、Web サイトのページ遷移せんいのパターンを固定長の ID にすることもできます。

ページせん移をID化する
$list_url_visited=[
  'http://hoge.com/p1',
  'http://hoge.com/p6',
  'http://hoge.com/p4',
  ...
];

asort($list_url_visited); //配列をソート
$string     = implode(' ', $list_url_visited); //配列を文字列に結合
$id_visited = hash('md5', $string); //文字列をハッシュ化

この行動パターンに固定長の ID を振れるメリットは機械学習などにも応用できます。もちろんページ遷移だけでなく、5x5 ピクセルや 10,000x10,000 ピクセルといった、どんなサイズのピクセル・データにも固定長の ID を振ることもできます。なぜなら、ハッシュ値は数値なので機械学習における「離散値」の特徴量としても使えるからです。

つまり、ハッシュ関数の特徴をよく理解すれば、アイデア次第でさまざまな活用方法がある関数でもあるのです。


ハッシュ関数とブロック・チェーンの関係

ハッシュ関数とブロック・チェーン

仮想通貨(暗号通貨)で有名なブロック・チェーンですが、その仕組みのベースに使われているのがハッシュ関数です。(ハッシュ関数の特徴に関しては上記「ハッシュ関数の基本と特徴」参照)

ブロック・チェーンでは、以下の3つのハッシュ関数の特徴が活かされています。

  1. 非可逆である(元に戻せない)
  2. 同一性(同じものであること)が確認できる
  3. 衝突を探すのは大変だが、探したものを確認するのは簡単

ここで言う「衝突」とは「異なる値なのにハッシュ値が同じになっちまった」という状態です。業界用語で「コリジョン」(collision)と呼ばれます。

しかし、ブロック・チェーンの何が「すごい」のでしょう。

「中央集権型に依存しなくていい」とか「お金に変わる何とか」とか聞きます。しかし、エンジニアを続けていると peer-to-peer(or 分散型)が必ずしも良いわけではないことを体感していたり、メンコとかトレーディングカードとかと何が違うのか、と。パチンコやスロットの換金コインと何が違うのか、と。「世間との熱量の違い」を感じてしまいます。

恐らく、エンジニア的にブロック・チェーンが面白いのは「ビザンチン将軍問題」もしくは「二人の将軍問題」を解決できることかもしれません。

「ビザンチン将軍問題」「二人の将軍問題」の概要

「ビザンチン将軍問題/二人の将軍問題」は、一言で説明すると「A から B へ情報を伝達するルートが信用できない場合に、正しい情報を伝えることができるか」という問題です。

おおざっぱにサーバーで例えると以下のイメージです。

A 国にサーバー A 、B 国にサーバー B があり、お互いの準備が整うと各々「処理 X」を始めます。しかし、どちらかの準備が整っていないで「処理 X」を始めると、核核然然かくかくじかじかな理由で「両国が崩壊する」と仮定します。

問題は A 国と B 国のネットワークが複数の国を経由しないといけないことです。

その経由先には敵対する C 国があるだけでなく、寝返る「かも」しれない同盟国 D 国と E 国もあります。「寝返る『かも』」と言うのは、D 国も E 国もお賃金が安く、役人でさえ小遣い稼ぎで賄賂をもらうような人が多い国である、という設定です。

「準備ができていない」と伝えたのに「準備できた」と伝わってしまった場合、両国が崩壊します。つまり敵対国は中継経路で改ざんするのが狙い目であるため、同盟国といっても安心できないのです。

この、「準備が整った」と伝達するルートの途中で改ざんされる可能性があるのが最大の問題です。

途中の経路が絶対的に信頼できない状態は、まさにサーバー間通信が持つネットワークの問題と同じだと感じると思います。

この問題に対して現在ネットワークで使われているのが TLS/SSL 通信です。

HTTPS などの TLS/SSL 通信の場合は、秘密鍵・公開鍵暗号を使って「傍受」されたり「改ざん」されることを防いでいます。しかし、残念なことに復号された内容そのものが「正しいか」まではわかりません。(秘密鍵・公開鍵暗号の概要に関しては、本記事上部にある「ハッシュ関数の基本と特徴」を参照ください)

ここで、データのハッシュ値も別ルートで送れば「内容が正しいこと」を検知できそうです。しかし、どの通信ルートも信用できないため、そのハッシュ値すら正しいか確信が持てません。

同じインターネットのルートでなく、電話網、トークンキースニーカーネットワークといった別の媒体のルートを介して確認することを「2『要素』認証」と呼んだりしますが、肝心の電話会社やトークンキー開発会社も運び屋も信用できない状態です。

話した内容がマスメディアを通すと違っていたり、決算報告で大丈夫と思っていた銀行や企業が突然なくなったり、脅されているのか血迷ったのか公文書を改ざんしたりする政治家がいる世の中だと、なおさら確信が持てないかもしれません。

そう考えると、意外にリアルな話だと思います。

共通鍵暗号が全盛だった時代、メールを送ったら届いたか電話で確認するのが流行りました。ちょうどその頃、プライバシーマークを取得するため「添付ファイルはパスワード付き ZIP でメールに添付して送り、パスワードは次のメールで同じアドレスに送る」のが企業で流行りました。今で言う失敗した「2『段階』認証」の走りです。

もちろん、そんなのはダメちんなので、現在は公開鍵暗号による方法が主流になりつつあります。また、公開鍵は公開鍵基盤を通して安全に取得できるようになりました。つまり、認証局から電子証明書(公開鍵のハッシュ値)をもらうことで公開鍵が正しいものであるという確認をしているのです。

ここで、先の「ビザンチン将軍問題/二人の将軍問題」がチラついてきます。

現在の TLS/SSL 通信は、銀行や政府のように、公開鍵を証明する先を「信用するしかない」という状態で動いています。つまり、証明書(公開鍵が正しいものであるかの証明書)を発行する組織や担当者が洗脳されて、敵対国と手を組み、偽の公開鍵を発行する可能性はゼロではないのです。

このように「二人の将軍問題」はネットワークの問題だけでなく、中間に位置するものを信用できない状況で起きる現代の問題でもあるのです。

この「二人の将軍問題」を道徳でなく仕組みで解決できるかもしれないというのが話題のブロック・チェーンです。なんと「賄賂などの小銭で寝返る小悪党を味方にしちゃえばいいんじゃね?」という逆転の発想です。

ブロック・チェーンの概要

ブロック・チェーンの基本構造は割と単純で、「1つのデータが、前のデータのハッシュ値も持つ」というものです。

🐒   実際のデータは高速化なども配慮してもっと複雑ですが、概念は同じです。

ブロック・チェーンではデータのかたまりを「ブロック」と呼ぶのですが、ネットワークの「パケット」と「フレーム」のように、ブロックと呼ばれる区分けがレベル(レイヤー)によって違います。ここでは仕組みがわかりやすいように「登録したい1つのデータ」を「ブロック」と呼びます。参考として、ビットコインなどは「n 分間の取引データ」を1ブロックと時間単位で区切っています(現在は n=10)。そして登録される個々のデータを「トランザクション」と呼んでいます。

データを JSON 形式で簡略表現すると以下のようになります。hash data nonce の1セットを1ブロックとします。

[
    {
        "hash": "<hash1>",
        "data": "<data1>",
        "nonce": "<nonce1>"
    },
    {
        "hash": "<hash2>",
        "data": "<data2>",
        "nonce": "<nonce2>"
    },
    ...
]

hash キーの値は、前のデータの hashdatanonce の値をつなげてハッシュしたものです。(<hash2> = hash('sha256', <hash1> + <data1> + <nonce1>);)

data キーの値は、何かしらのデータで平文でも暗号文でも構いません。

3つめの "nonce"(ナンスもしくはノンス)キーですが、これがブロック・チェーンのキモ・・です。この nonce の値を算出することを「マイニング」と呼んでいます

マイニング(発掘)と呼ぶのは、この nonce の値を最初に見つけ、承認を得られた人は報酬がもらえるからです。ブロック・チェーンがビットコインの場合は、ビットコインがもらえます。

つまり、nonce を見つけることが現金につながるだけでなく、みんなのマイニング作業や承認作業によって「データのハッシュ値が正確であるか」を複数人で確認しあっていることになるため、データが堅牢になって行きます。

🐒   たまにマイニングを仮想通貨(暗号通貨)そのものを発掘するような意味とも思える記述を見かけますが、違います。

「金を発掘したら俺のもの」的な宣伝が多いのでわかりづらいのですが、どちらかと言うと「レアメタルを発掘したら報酬でお金がもらえる」イメージが近いと思います。ビットコインの場合は「nonce 値」がレアメタルで、「ビットコイン」が報酬のお金です。
仮想通貨自体は1コインごとに、コインの秘密鍵とコインの ID となるハッシュ値がセットになったようなデータで、各コインは 0〜1 の float 値を持っており分割可能です。ビットコインの場合は、1.00000000 まで分割可能です。このコインは、一般的に ICO と呼ばれるステップで作成(発行)され、ユーザーは購入もしくはもらいます。
受け取ったコインは、ユーザーごとに作成される秘密鍵とフォルダをセットにした「ウォレット」と呼ばれる先に保存されます。この時、ユーザー間のウォレットでコインが移動したときの取り引き内容が「ノード」と呼ばれる先の DB にブロック・チェーン形式で記録されます。

ノード
「ノード」はコイン取引所やメンテナやマイナー(マイニングをする人)などのうちブロックチェーンの DB の管理をしているサーバーです。各々のノードの DB は同期されており、これがブロック・チェーンを「分散台帳」とも呼ぶゆえん・・・です。「ノード」はネットワークの常時接続やディスク容量が必要といったデメリットもありますが、「ノード」になるメリットはブロックチェーン追加時に報酬のためのコインを作成(発行)することができる点と DB 追加の手数料がもらえる点です。そのため、初期の頃は、ノードとマイナー(マイニング)を兼任するサーバーも多く、これが「マイニング=コインの発掘」というイメージを産んだ理由でもあります。

いずれにしても、ブロック・チェーンは DB の1種であると考えて差し支えないと思います。そのため、ブロック・チェーンの仕組みは仮想通貨/暗号通貨でなくても活用できます。

ブロック・チェーンは "nonce" センスなゲーム

ブロック・チェーンにおける nonce は、一言で言うと「ハッシュ値の衝突を探すゲームで、最初に見つかった値」です。

このゲームとは「現在の datahash に、nonce を加えてハッシュ化すると、最初の n 桁が 0(ゼロ)になる nonce の値を探す」といったものです。

その桁数や 0(ゼロ)の値などはブロックチェーンによってルールは異なりますが、いずれも nonce を加えてハッシュ化した時に出る値に対するルールです。

nonce を探すイメージを Bash で書いてみました。

bashでマイニングする(nonceを探す)例
#!/bin/bash

# RULE
VALUE_HEAD='0000'
LEN_HEAD=${#VALUE_HEAD}

# Function
function dechex() {
    printf '%x' $1
}

function isValidNonce() {
    [ "${1:0:$LEN_HEAD}" = "${VALUE_HEAD}" ]
    return $?
}

function hash() {
    algo=$1
    value=$2
    echo $(echo -n $value | openssl $algo | awk '{print $2}')
}

# Data
data='something'
hash='34902903de8d4fee8e6afe868982f0dd'
nonce=''

# Mining/Search nonce
counter=0
while true
do
    nonce=$(dechex $counter)
    string_to_hash="${data}${hash}${nonce}"
    hash_temp=$(hash 'md5' $string_to_hash)
    isValidNonce $hash_temp && {
        break
    }
    counter=$((counter+1))
done

echo "Nonce found: ${nonce}"

しかし、ブロックチェーンは「一度、生でブロックチェーンを見たら分かる」と言われるくらいなので、全体の流れをプログラムで見た方がピンとくるかもしれません。

PHP で簡単に書いてみました。

既存のブロック・チェーンのデータ
// 2つ前のブロック・データ
$block_chain[] = [
    'data'  => 'sample1',
    'hash'  => 'a4626f9d3e6802aebbff46697248e0b9',
    'nonce' => 'xxxxxx',
];
// 1つ前のブロック・データ(Latest)
$block_chain[] = [
    'data'  => 'sample2',
    'hash'  => '3152851bf5419247cf948e871b0adfe8',
    'nonce' => '32648',
];
Nonceのルール
// 最初の4文字が 0 である
define('VALUE_HEAD', '0000');
define('LEN_HEAD', strlen(VALUE_HEAD));

/* 検証用の関数 */
function isValidNonce(string $nonce): bool
{
    // ルール:$nonce の頭 n 文字が VALUE_HEAD と同じ( n = LEN_HEAD )
    return (substr($nonce, 0, LEN_HEAD) === VALUE_HEAD);
}

function isValidHashInLatestBlock(array $block_chain): bool
{
    // 現在のブロックの長さ
    $len_block_chain = count($block_chain);

    // 2つ前のブロックのデータ取得
    $key_2block_ago = $len_block_chain - 2;

    $data_2block_ago  = $block_chain[$key_2block_ago]['data'];
    $hash_2block_ago  = $block_chain[$key_2block_ago]['hash'];
    $nonce_2block_ago = $block_chain[$key_2block_ago]['nonce'];

    // 期待するハッシュ値の算出
    $hash_previous_expect = hash('md5', $data_2block_ago. $hash_2block_ago . $nonce_2block_ago);

    // 1つ前のブロックのハッシュ値取得
    $key_block_previous   = $len_block_chain - 1;
    $hash_previous_actual = $block_chain[$key_block_previous]['hash'];

    // 1つ目のブロックのハッシュ値の検証
    return ($hash_previous_expect === $hash_previous_actual);
}

function getBlockLatest(array $block_chain):array
{
    $len_block_chain = count($block_chain)-1;
    return $block_chain[$len_block_chain];
}
ブロックチェーンにデータを追加したい人の作業
/* 1つ前のブロックの検証 */
if(! isValidHashInLatestBlock($block_chain)){
    echo 'Error: Not a valid hash value. Block-chain broken.' . PHP_EOL;
    exit(1);
}

/* 新規ブロックのデータ作成 */
// 追加したいデータ
$data_current = 'sample3';
// ブロックのハッシュ値を計算(1つ前のブロックより)
$block_previous = getBlockLatest($block_chain);
$hash_current   = hash('md5', $block_previous['data'] . $block_previous['hash'] . $block_previous['nonce']);
$block_current  = [
    'data' => $data_current,
    'hash' => $hash_current,
];
echo 'Request to add to the block-chain.' . PHP_EOL;
echo '  Data:' . $data_current . PHP_EOL;
echo '  Hash:' . $hash_current . PHP_EOL;
マイナー(マイニングする人)の作業
/* 1つ前のブロックの検証 */
if(! isValidHashInLatestBlock($block_chain)){
    echo 'Error: Not a valid hash value. Block-chain broken.' . PHP_EOL;
    exit(1);
}

$data_current  = $block_current['data'];
$hash_current  = $block_current['hash'];
$nonce_current = '';
// Nonce 探索
$i = 0;
while( true ){
    $nonce_current = dechex($i);
    $hash_temp = hash('md5', $data_current . $hash_current . $nonce_current);
    if(isValidNonce($hash_temp)){
        echo 'Nonce found: ' . $hash_temp . PHP_EOL;
        break;
    }
    $i++;
}

/* マイニングの結果(これを検証依頼する) */
echo 'Block Data to add:' . PHP_EOL;
echo '  Data: ' . $data_current . PHP_EOL;
echo '  Hash: ' . $hash_current . PHP_EOL;
echo '  Nonce: ' . $nonce_current . PHP_EOL;
ブロック・チェーンに追加する人の検証作業
/* 1つ前のブロックの検証 */
if(! isValidHashInLatestBlock($block_chain)){
    echo 'Error: Not a valid hash value. Block-chain broken.' . PHP_EOL;
    exit(1);
}

$hash_verify = hash('md5', $data_current . $hash_current . $nonce_current);

echo 'Hash result: ' . $hash_verify . PHP_EOL;
if(! isValidNonce($hash_verify)){
    echo '  Error: Nonce not valid.' . PHP_EOL;
    exit(1);
};

// ブロック・チェーンに追加
$block_chain[] = [
    'data'  => $data_current,
    'hash'  => $hash_current,
    'nonce' => $nonce_current,
];
echo '  Success: New data added to block-chain.' . PHP_EOL;

// ブロック・チェーンの内容表示
echo 'Current Block-Chain:' . PHP_EOL;
print_r($block_chain);

上記で重要なのが、マイナー(マイニングする人)の処理の while ループの箇所です。

一部のマッチが true になるのか、全文マッチが true になるか以外はマッチ対象が違うだけでハッシュ値の衝突を探す手法そのままです。

実際には文字列の比較でなく、FF000...and 処理(ビットマスク)した方が速いなどありますが概念的に、こういうことです。😳

ここで大事なのが、「nonce を探すのは大変だ(時間がかかる)がハッシュ関数で確認することは一瞬」ということです。

プルーフ・オブ・ワーク(仕事の証明)

ブロック・チェーンの重要な基本ルールに「現在一番長いチェーンを『正』とする」があります。

つまり、せっかく計算しているのに短い方のブロックチェーンを使っていた場合は無効になるということです。自分より早く「nonce を見つけた!」という人がいた場合、計算を続けても電気や時間のリソース(👌)が無駄になってしまいます。noncenone になってしまいますのん。

そこでマイナー(マイニングする人)は、本当に見つけたのかを確認する作業を行い、正しければ早々にブロックチェーンを更新して、次の登録待ちデータのマイニングを始めるのです。

この仕組みにより、ブロック・チェーンの途中にあるデータを改ざんしようとした場合、大変なコストが発生します

改ざんしたブロックより後のブロックのハッシュ値の計算だけでなく nonce の値まですべて再計算してリリースしないといけないからです。それだけでなく、世界中のマシンに散らばったブロック・チェーンのデータにも不正アクセスして書き換える必要もあります。

しかし、改ざんして再計算したり、他のマシンをハッキングしてデータをクラックしている間にも、よほど過疎っているブロックチェーンでない限りデータはどんどん長くなり更新されていきます。改ざんさせる暇を与えづらい状況が作られるのです。

ビットコインの場合は、ウォレット間の移動がある(取引がある)たびに 10 分おきに長くなって行くので、とうてい間に合わないのがわかると思います。2020 年 07 月の現在のビットコインのブロックチェーンの長さは約 270 GB です。

つまり「データを改ざんして小銭を稼ぐよりはマイニングした方が稼げる」ということです。

そして、当然これらの処理は自動で行われます。つまり、スパムメール/フィッシング/詐欺商品/ゴミ記事の広告収入など、単純作業を自動化して「数を打って薄利多売で稼ぐ」という昔ながらの手法を使う人にとっては「楽して稼げる」だけでなく、「他人のマイニング結果の粗探し」が結果としてブロック・チェーンの正当性(データのハッシュ値が同じであること)を保証することになります。

そのため、「ホワイト」しかも「ウィン・ウィン」となるため、中小規模の悪党の犯罪心理学を逆手に応用した、敵を味方に付ける有効な概念なのです。

もちろん、国家レベルの資金がある大規模な悪党が、相手を潰すために鬼のようなマシンを大量に用意できれば、以下の攻撃でブロックチェーンを改ざんデータ入りで更新させることはできます。

  • 改ざん後、残りのすべてを再計算し、現在のブロック・チェーンより少しだけ長いチェーンを作成してリリースする
  • 改ざんデータを、オリジナルのデータと同じハッシュ値になるような値とセットで改ざんデータとして埋め込む

しかし、利用者が多ければ多いほど多彩な人がおり、nonce のマイニングでなく過去のデータの検証だけを行う人も出てきます。また、後述するように前のブロックのデータサイズも含めるようにすれば、より堅牢なブロックチェーンを構築できることになります。

つまり、ブロック・チェーンは「複数人でチェックしあい、チェックしてもらったら早い者勝ちで報酬を与える」「チェーンの長さがセキュリティにつながる」「利用者が多ければ多いほど堅牢になる」という仕組みなのです。

この、データのハッシュ値を確認し nonce の値を探す、それを他者が粗探し(検証)をし、問題なければ各々のチェーンに追加する。これを「プルーフ・オブ・ワーク」(仕事の証明)と呼びます。

ブロックチェーンのセキュリティ

ちなみに、巷で何度か「暗号通貨(仮想通貨)が盗まれた」という事件が発生していますが、これはブロックチェーンの仕組みが崩れたわけではありません。

単純に、パソコンがクラッキングされ、暗号通貨用の秘密鍵が盗まれてしまい、別の口座に移されてしまったという、クレジットカードや銀行口座のそれ・・と同じでセキュリティ管理上の問題による事件です。「ほらな」と言いたいメディアが仕組みを把握せずに印象操作をしているだけです。

51%攻撃(数の暴力)

おそらくブロックチェーンのセキュリティでシステム的に一番有名な攻撃が 51% 攻撃と呼ばれるものです。一言で言うと「多様性に欠けた際の、多数決による意思決定の情報操作」です。

ブロックチェーンは基本的に主となるサーバーが存在しません。そのため、意思決定はノードによる多数決で決めることになります。「ノード」とは、先述したように分散された各々のブロックチェーンの DB サーバーのことです。各ノード(サーバー)には、各々マイナー(マイニングする人)やユーザー(ブロックチェーンにデータを追加したい人、例えば仮想通貨の場合は取引内容を登録したい人)が所属しています。

この時、間違った登録内容であってもノードやマイナーの過半数が「問題ない」と答えると登録されてしまうのです。ここで言う「間違った」と言うのは、ハッシュ値が合わないデータではなく、データそのものを改竄した物を言います。

つまり、現実世界の多数決と同じように、数と資産(処理能力)を持った組織でコントロールすることができてしまうのです。

🐒   資本主義と犯罪学の観点からは、残念なことにブロック・チェーンを仮想通貨(暗号通貨)に使うにも昔からある問題が出てきています。

ビットコインの場合、マイニングにかかる時間(nonce が発見されるまでの時間)が自動的に 10 分前後になるようにルール(ゼロの個数)を調整しています。逆に言えば、マシン・パワーを持つ人が常に優位になるということです。
「今からマイニング事業を始めても儲けが少ない」と言われるのは、初期のころからルールにあわせて設備投資していた人と比べ、必要なマシンスペックの費用対効果が薄いからです。そうなると、すでに資本(マシンパワー)を持っている人にしか稼げない土壌ができつつあります。せっかくの「小悪党を味方に付ける」仕組みが崩壊する可能性もあるのです。また、マイナー(マイニングする人)のバラエティが少ないと、イレギュラー時に全滅する可能性も高くなります。特に上記の 51% 攻撃をさせやすくなってしまいます。
そういった問題に対して、マイニングの処理を分散させて、資本が少ない(マシン・スペックが低い)人でもマイニングに参加できるような仕組みも出てきました。事件にもなった Coinhive などです。この事件は Winny と同じく「犯罪の温床となりうるから」と検挙された事例で、どちらも「賢くない人」が「ズル賢くやろう」と迷惑をかけたことによる弊害で、どちらの技術も分散技術における重要なものではありました。アンチ資本主義(資本を持っている人を脅かす考え方)に対する弾圧とまでは言いませんが、特に Winny の件は日本の分散技術が遅れた理由ではあります。
「賢くない人から賢い人にお金が集まる」ことを資本主義の特徴の1つと仮定すると、犯罪における資本主義は「賢くない人からズル賢い人にお金が流れる仕組み」とも言えます。つまり「賢くない手下にマシンを走らせ、ズル賢い元締めに流れる仕組み」が生まれてきます。犯罪組織の王道の仕組みです。つまり、マイニングから得たクリーンな資金が犯罪組織の資産にもなりうるということです。
しかし、これらはブロック・チェーンに限らず、自動的にお金が発生すると必ず起きる問題です。そのため、ブロック・チェーンの仕組みとは分けて考えるべきです。

さて、DB の改ざんにスポットを当てると、不特定多数で多様性に富んだ組織においては、一見ブロック・チェーンがベストな方法に見えます。しかし、nonce のように「そもそも時間をかけることでセキュリティを高めている」仕組みである以上、ブロック・チェーンは遅いのでケース・バイ・ケース(適材適所)と言えると思います。

また、ブロック・チェーンが「分散台帳」とも呼ばれるように、DB の分散に関しては、ハッシュ関数とは別の話しなので割愛しますが、以上のようにブロック・チェーンにはハッシュ関数の特徴が存分に活かされているのがわかると思います。

いずれにしても、この性善説(相手を信用する)でなく性悪説(悪党は楽をして稼げる方を選ぶ)を逆手に取った社会的な心理も加味したプルーフ・オブ・ワークの仕組みにより「A → B への(遅いけど)正確なデータの伝達が可能になった」のがプログラマとして面白いなー、と思うところです。

暗号通貨使ってないけど。


そんな便利なハッシュ関数ですが、「メッセージダイジェストのコリジョン」(異なる入力値なのにハッシュ値が同じという「衝突」)が悩みのタネです。つまり、「改ざんされているのにハッシュ値が変わらない」状態です。

しかし、上記記事のように特定のアルゴリズムでハッシュ値が衝突してもアルゴリズムを変えると衝突しません

「衝突しない」と言いましたが限りなく本当に近い嘘ですが、本当です。それでは以下の検証をご覧ください。

MD5 の衝突(検証と実証)

MD5 の衝突

検証実証withPHP
<?php
// MD5 で衝突するサンプルデータ
$str1 = '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518'
      . 'afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2';
//              ↑                                      ↑
$str2 = '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518'
      . 'afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2';
//              ↑                                      ↑

// バイナリに変換
$bin1 = hex2bin(trim($str1));
$bin2 = hex2bin(trim($str2));

// 衝突させる
$algo  = 'md5';
$md5_a = hash($algo, $bin1);
$md5_b = hash($algo, $bin2);
echo ( $md5_a === $md5_b ) ? '衝突しました' : '衝突していません', PHP_EOL;

// 別のアルゴリズムで確認
$algo   = 'sha1';
$sha1_a = hash($algo, $bin1);
$sha1_b = hash($algo, $bin2);
echo ( $sha1_a === $sha1_b ) ? '衝突しました' : '衝突していません', PHP_EOL;

/* 出力結果 */
// 衝突しました
// 衝突していません

SHA-1 の衝突(検証と実証)

SHA1 の衝突

SHA1 の衝突はデータサイズが大きすぎるので paiza.IO で動作サンプルを作れませんでした。簡単なスクリプトとローカルで実行してみた結果結果を載せます。

検証スクリプト
<?php

$url_pdf1='https://shattered.io/static/shattered-1.pdf';
$url_pdf2='https://shattered.io/static/shattered-2.pdf';

$algo = 'sha1'; //衝突する
echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;

$algo = 'md5'; //衝突しない
echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
exit
実行結果
$ php -a
Interactive shell

php > $url_pdf1='https://shattered.io/static/shattered-1.pdf';
php > $url_pdf2='https://shattered.io/static/shattered-2.pdf';

php > $algo = 'sha1'; //衝突する
php > echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
38762cf7f55934b34d179ae6a4c80cadccbb7f0a
php > echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
38762cf7f55934b34d179ae6a4c80cadccbb7f0a

php > $algo = 'md5'; //衝突しない
php > echo hash($algo, file_get_contents($url_pdf1)), PHP_EOL;
ee4aa52b139d925f8d8884402b0a750c
php > echo hash($algo, file_get_contents($url_pdf2)), PHP_EOL;
5bd9d8cabc46041579a311230539b8d1
php > exit


md5sha-1 のセキュリテイについて

MD5 と SHA1 のセキュリテイについて

先日(2018 年夏頃)、とある居酒屋の隣の席で「md5 は破られたから安全ではない」という会話を耳にしました。しかし、調べてみたら厳密には破られたわけではないようです。

と言うのも、ハッシュ・アルゴリズムが「破られた」(break)と言われる場合3つの意味があり、業界によって使い方が違うので注意が必要そうです。

  1. ハッシュ前の元の値を計算で出せるようになった
    • インパクト:大。身元がバレる。
  2. ハッシュ値を衝突させる効率的な方法を見つけた
    • インパクト:中。身元はバレないが、なりすましされる。
  3. ハッシュ値が衝突する異なる2つの値を見つけた
    • インパクト:少。単体を狙ったなりすましには有効。

🐒   ちなみに、上記の「身元がバレる」と「なりすましされる」の違いですが、ここでは「(ハッシュ値からの逆算で)パスワードがバレてログインされた」と「(ハッシュ値が衝突する)違うパスワードでログインされた」、みたいな違いを指しています。
例えば、「ハッシュ値が衝突するパスワードを見つけた」としても、それは(少なくとも)1つのサービス内において起きることです。その反面、「ハッシュ値からパスワードが逆算できる」となると、同じパスワードの他のサービス全てにアクセスできることになります。(「衝突」に関しては上記「ハッシュ関数の基本と特徴」を参照してください。)

どうやら「md5 が破られた」というのは2番目の「衝突する値の効率的な探し方」を指しているようです。先の md5sha-1 の衝突の検証実証例も、その手法を使って発見された値です。

現在(2020年4月)でも、やはり md5sha-1 も「ハッシュ値から引数の値は逆算できない」状態ではある(1番目の状態は破られていない)ようです。

増える MD5、SHA-1 脱獄者

しかしながら、時代は「脱 MD5」を経て「脱 SHA-1」に動いています。

例えば、macOS では High Sierra(OSX 10.13)から Apple 社内で OpenSSL を移植・開発した「Apple 版 OpenSSL」を OpenSSL098-76.200.2 で打ちめました。その、主な理由が「SHA-1 をベースにしていたから」です。

同時に、SSL/TLS の暗号通信に使うライブラリ(ハッシュ関数や暗号関数を担うライブラリ)も、ベースを 「Apple 版 OpenSSL」から「LibreSSL」に切り替えました。

For this reason, the programmatic interface to OpenSSL is deprecated in macOS and is not provided in iOS. Use of the Apple-provided OpenSSL libraries by apps is strongly discouraged.

OpenSSL | Transmitting Data Securely @ developer.apple.com より)

ご利用の macOS がどちらのライブラリを使っているかは、ターミナルから $ openssl version コマンドで確認できます。

🐒   「開発を止めた」というだけで、Apple 版 OpenSSL の旧バージョン「OpenSSL098-76.200.2」(2016 年版)は Mojave (OSX 10.14.6) の公開ソースコードには、現在でも存在しています。

また、SSH 接続ツールの OpenSSH も v8.3 から、SHA-1 を使った公開鍵の署名は「将来的に無効になる」旨の表示がデフォルトになりました。

The OpenSSH 8.3 release is out. This primarily a bug-fix release with a handful of minor new features. It does, however, carry a prominent notice that ssh-rsa signature algorithm will be disabled in "a near-future release".

OpenSSH 8.3 released (and ssh-rsa deprecation notice) | LWN.net より)

🐒   元記事が素人向けにわかりやすく書いていないこともありますが、いくつかの記事で SSH で RSA 公開鍵が使えなくなるなるような記載がありますが、違います。
ssh-rsa というのは、SSH 通信において SHA-1 を使って作成された RSA 公開鍵の署名ファイルのことで、SSH でログインすると接続先サーバーに保管される署名ファイルのことです。RSA 暗号自体のことを指すわけではありません。

なぜ、みんな「脱 MD5」「脱 SHA-1」を目指しているのかと言うと、とある・・・論文のせいです。

先の sha-1 の衝突実証ですが、そのデータは Google が見つけたものです。その手法は、発見から 10 年以上前に発表されたとある・・・論文をベースに世界の暗号学者や Google が改良を重ねたもので、Google のクラウドりょくを利用すれば 13 万米ドル(約 1,400 万円)程度で衝突を発見できることを証明したのです。

たかが 1つの衝突に 1,000 万円以上かかるというのは、個人としては大きな金額かもしれません。しかし、大企業が広告費を億単位でかけるのはザラであることを考えると、決して大きい金額というわけでもないことがわかります。

逆に言えば、とあるサーバーの、とあるユーザーの SSH 接続をターゲットにした場合、10 数万ドルもあればハッキングできてしまう可能性があるということです。そして、それだけのコストをかける価値のある情報を持った企業や行政機関は狙われる可能性がある、ということでもあります。

とある女性暗号学者の衝撃論文

md5 は以前よりオワコンと言われていたのですが、ダメチンと言われる大きなキッカケとなったのが、王 小雲(Wang Xiaoyun)さんという中国の山東大学の女性暗号研究者が 2004 年の上旬に発表した論文下旬に発表した論文です。

CRYPTO と呼ばれる世界的な暗号学会があるのですが、その 2004年の学会で発表され、話題をさらいました。

しかし、2004 年の CRYPTO 登壇者一覧を見ても、王(ワン)さんの名前の登壇記録がありません

どうやら運営側から「んなこたーない」と論文を却下されたため登壇できなかったそうです。

「それならば」と急遽きゅうきょ生徒を連れてアメリカまで飛んで行き、学会の発表後に行われるランプセッション(持ち時間 15 分程度の発表、学会版 LT)で、目の前でハッシュ値の衝突を見せたところ驚かれ、話題となったそうです。特に MD4 に関しては、コンピューターなしでも衝突を見つけることができたからです。

しかし、彼女の英語がわかりづらいのと論文の内容が難しく、周りも「なんかすごいことが起きてるっぽい」という状態だったそうです。ところが、同年末から翌年頭(2004 - 2005 年)にかけてさらなる衝撃的な論文を発表します。

SHA-1 の衝突を見つけるアルゴリズムの論文です。

かねてより SHA-1 の脆弱性を指摘していた暗号・情報セキュリティの巨匠で「シュナイアーの法則」でも知られるブルース・シュナイアー氏が 2005 年 2 月に、この論文を認めたことで、一気に注目のまと・・になります。総当たりで最低でも 2^80 回の処理が必要だったものが、理論上 2^69 回で衝突を発見できるからです。

そして、今度は CRYPTO 学会の方から彼女を招待し、2005 年の CRYPTO に登壇依頼します。ところが、またもや登壇できないということがわかりました。VISA の発行手続きが遅れたからです。

このことは、この論文の解析が難しく検証も遅れていたため、彼女の登壇を心待ちにしていた暗号学者だけでなく、シュナイアー氏も憤慨ふんがいしている記事を書いたくらいの話題性がありました。

その後、時間はかかったものの各種論文も認められ、暗号学会において王(ワン)さんは無事、認知されたそうです。当時の暗号学者たちは、この彼女の論文をパズルを解くようでワクワクしたそうです。

ブルートフォースおまえもか

さて、閑話休題。

つまり、「効率的に衝突する方法は見つかった」ものの、md5sha-1 でハッシュ化されたパスワードが流出しても「オリジナルのパスワードが計算で出せるわけではない」ということです。

ところがブロックチェーンの台頭により、やはり md5sha-1 は危険とは言えるようです。

と言うのも、ブロックチェーンのプルーフ・オブ・ワーク、俗に言うマイニングと呼ばれる作業が、まさにハッシュ値の衝突を探す作業だからです。(ブロックチェーンの概要は前項の「ハッシュ関数とブロック・チェーン」参照)

マイニングは、基本的に総当たり攻撃の手法を使うわけですが、先の論文を応用すれば他より早くマイニングができることになります。中国のマイナー(マイニングする人)が多いのも、おそらく論文が中国語で読めたからなのかもしれません。

同じハッシュ値の改ざん作業でも、ブロックチェーンを崩すよりはマイニングした方が直接的にお金(暗号通貨)を得られるし、そのぶんブロックも堅牢になっていくという良いところ取りなのが、仮想通貨(特にビットコイン)が広まった理由とも言われます。

逆に言うと「その衝突させるノウハウやインフラは悪意を持って改ざんするのにも使える」ということでもあります。そういう意味でも、やはりクリティカルな情報は計算コストが高いとはいえ sha-256sha-512 を使った方が安全であるとは言えそうです。

それでも md5 は使いやすく軽量であるため、頻繁に使い捨てされるようなものには依然有用です。やはり、結局のところ機能や特徴をきちんと理解した上で、コストと相談した運用の方針によると思います。

🐒   SHA-1 の後続である SHA-2 は、SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256 などの総称です。


以上のことから、「セキュリティの強度」や「同一性の確実度」を高めるには、以下の3点を同時に提供するのが効果的とわかりました。

  1. 複雑な計算が必要な、長いハッシュ値を提供する(SHA256 など)
  2. 異なるアルゴリズムのハッシュ値も一緒に提供する(SHA512MD5 など)
  3. データの長さ(ファイル・サイズ)を提供する

OS のイメージ・ダウンロードで SHA-1MD5 などの複数ハッシュ値を提供しているのは「SHA-1 ハッシュが使えない人のため」なのかと思っていましたが、どうやらそれだけではないようです。というのも、SHA-1MD5 の両方といった複数のアルゴリズムのハッシュ結果を「単一の改ざん」で衝突させるのは難しいからです。

また、3番目のデータ・サイズですが、ウィルス本体 + 衝突用ハッシュ値 もしくは 改ざんデータ + 衝突用ハッシュ値 のデータが埋め込まれた場合の対策です。と言うのも、オリジナルのデータと同じハッシュ値にさせつつ悪意あるデータを埋め込んで、かつ同じサイズにするには、とても大変な労力を必要とするからです。

いまや CSV のように小馬鹿にされる MD5 ですが、SHA-1, SHA-256 などのメジャーどころ以外に、どんなアルゴリズムがあるのか気になりました。PHP の hash_algos() 関数 でサポートしているハッシュ・アルゴリズム一覧を出したところ「こんなにハッシュ関数(のアルゴリズム)ってあるの?!」とビックリ。各々のアルゴリズムの仕組みを把握する気力さえ失せる勢い。(失せた)

アルゴリズム一覧を見て、「ってか MD2 なんてあったんだ!」と知ったと同時に「MD2 って MD5 と同じ 16 バイト長(128bit= 32 桁の HEX 文字列)なんだ!」と気づきました。

そこで、各々のアルゴリズムはどれくらいの長さの値を返すのか調べ、一覧にしてみました。(ついでに速度も)

長さを知ったところで何?

ですよねー。実は、私は SQLite31INTEGER PRIMARY KEY フェチなのです。

さら・・で SQL 文も書けないくせに、「SQLite3」と聞かれれば「主キー♥️」と答えるくらいです。

これは、SQLite3 の場合は DB をキー検索する際に「DB の PRIMARY キー(主キー)を INTEGER 型にすると最もパフォーマンスが良い」というのを盲信しとるのです。

元々 SQLite3 では rowid で検索するのが一番速いとされます。rowid とは、SQLite では行番号のことです。DB に行(レコード)が作成されると 64 bit/8 byte(HEX 値で max 16桁)の行 ID が自動で割り振られます。

Searching for a record with a specific rowid, or for all records with rowids within a specified range is around twice as fast as a similar search made by specifying any other PRIMARY KEY or indexed value.
ROWIDs and the INTEGER PRIMARY KEY | SQL As Understood By SQLite @ SQLite.org より)

特定の rawid でのレコード検索、もしくは rawid で指定した範囲内のすべてのレコードを検索をする場合、PRIMARY KEY やインデックスを使った場合に比べて2倍近い速さの速度が得られます。(筆者訳)

この時、テーブルの主キーが rowid と同じであれば、主キーでも同じ速度が得られるのです。

厳密には、テーブル作成時に主キーの列を INTEGER PRIMARY KEY で定義し、テーブルが1次元(1主キー1行構成の DB)だった場合に各行の主キーが rowid のエイリアスとなる仕様を使います。(この時 INTEGER PRIMARY KEY でなく INT PRIMARY KEYINT で宣言するとダメなので注意)

If a table has the primary key that consists of one column, and that column defined as INTEGER, exactly INTEGER in any cases, such as, INTEGER, integer, etc., then this primary key column becomes an alias for the rowid column.

表(テーブル)の主キーが1つの列で構成され、かつその主キーが大文字・小文字関係なく INTEGERINTEGER, integer, INTteger, etc.)と定義されていた場合、この主キーは rowid 列のエイリアスになります。(筆者訳)

主キーが rowid のエイリアスになるサンプル

実際に INT で宣言したテーブルと INTEGER で宣言したテーブルの SQLite3 内のデータ構造の違いを確認してみたいと思います。SQLite3 自身の挙動であるため、プログラム言語に依存しない証拠に bash で書いてみたいと思います。sh zsh どのシェルでも大丈夫だと思います。

テーブル作成の SQL 文の説明

テーブル作成の SQL 文は CREATE TABLE [テーブル名]([テーブル構成]) です。SQL のコマンドは、大文字・小文字は関係ありません。(CREATEcreate も同じ)

まず、主キー名は「myID」、主キーの宣言には PRIMARY KEY を指定します。

そして、主キーの型を INT で宣言したテーブル名を talbe1INTEGER で宣言したテーブルを table2 とします。table1 が従来のテーブル、table2 が倍速のテーブルです。

また、オプションの NOT NULL で「空の値は許さない」ことにし、挿入するデータは同じものとしてみたいと思います。

挿入順を見るために myID をわざと降順にしていることに注意してください。(SQLite3 v3.22.0)

#!/bin/bash

name_db='sample.db'

# Create table 1 and 2 and insert same data
sqlite3 $name_db <<'HEREDOC'
  create table table1(myID INT not null primary key, myName Varchar);
  insert into  table1 values(100, "First  value with ID 100");
  insert into  table1 values(10,  "Second value with ID 10 ");
  insert into  table1 values(1,   "Third  value with ID 1  ");

  create table table2(myID INTEGER not null primary key, myName Varchar);
  insert into  table2 values(100, "First  value with ID 100");
  insert into  table2 values(10,  "Second value with ID 10 ");
  insert into  table2 values(1,   "Third  value with ID 1  ");
HEREDOC
echo '- DB created with sample.'

次に、DB の中身を確認してみます。SQL 文 select rowid, * [テーブル名]rowid の表示および全てのデータを選択しています。

まずは、主キーが rowid のエイリアスではない table1 です。

table1の中身確認
# .header on と .mode column は見栄えを整える SQLite3 コマンドです
echo '- Table1'
sqlite3 $name_db <<'HEREDOC'
.header on
.mode column
  select rowid, * from table1;
HEREDOC
出力結果(1列目がrowid)
- Table1
rowid       myID        myName                  
----------  ----------  ------------------------
1           100         First  value with ID 100
2           10          Second value with ID 10 
3           1           Third  value with ID 1  

rowid 順に並んでおり、rowidmyID の値が同じでないことを確認してください。

このテーブル構成の場合、myIDmyName を検索すると、まずは myIDrowid を紐づけるために自動作成されるハッシュテーブルを検索して該当する rowid を見つけます。次に見つけた rowid に該当する myName を返します。つまり myIDrowidmyName とワンクッション入ることになります。(これ自体は RDB として正しい動きです)

次に、rowid が主キーのエイリアスになっている table2 です。

table2の中身確認
echo '- Table2'
sqlite3 $name_db <<'HEREDOC'
.header on
.mode column
  select rowid, * from table2;
HEREDOC
出力結果(1列目がmyID)
- Table2
myID        myID        myName                  
----------  ----------  ------------------------
1           1           Third  value with ID 1  
10          10          Second value with ID 10 
100         100         First  value with ID 100

SQL 文で select rowid, * としているのに rowidmyID と同じ(エイリアス)であること、そして1列目の myID 順に並んでいることを確認してください。(DB の登録順は 100→10→1)

このテーブル構成の場合、myIDmyName を検索すると、直接 rowid(のエイリアスの myID)の myName を返します。


この仕様により「主キー名」から「rowid」への変換ステップが省略され、テーブルの主キーが rowid と同じ扱いになるので速い、という塩梅です。元々はバグだったそうなのですが下位互換のため残され、仕様となったそうです。

そして、主キー(PRIMARY KEY)が rowid と同じということは、任意の rowid を振れるということでもあります。

となると、SQLite3 で扱えるキー(rawid)の最大長である 8 バイトの数値(64 ビット。文字でいうと 16 文字の HEX 文字列)をいかに作るかが問題になります。

Except for WITHOUT ROWID tables, all rows within SQLite tables have a 64-bit signed integer key that uniquely identifies the row within its table. This integer is usually called the "rowid".

ROWIDs and the INTEGER PRIMARY KEY | CREATE TABLE @ SQLite.org より)

やはり、王道の自動連番が一番楽で、キーの衝突もなく効率的です。基本設計がしっかりしていれば、これが一番だと思います。

しかし、(私の)ユーザにとっては変なバイアスがかかる忖度が発生することがわかりました。

というのも、歴史的事情でデータの ID を DB の主キーと同じにしているというダメちん仕様のため、当然の結果として「情報の ID 番号が時系列に並ぶ」、つまり登録順に並ぶのです。すると(私の)ユーザは無意識に内容の優劣を決めてしまうのです。

「ID が小さい → 古参の情報」「ID が大きい → 新参の情報」といった具合です。そのため、(私のようなオッチャン層は特に) ID が小さい方が質が良い・有益であると思い込んでしまうのです。観測すると、実は打ちやすい・覚えやすいだけで、番号に質は無関係だったのですが。

かといって、対オッチャン対策のためにランダムな ID の対応表を別途作るのも面倒なのです。また、すでに現行データの ID は周知されているので入れ替えは容易ではありません。

そこで、近々起こりうるであろうデータの棚卸しに備えてハッシュ関数を使って ID を固定長にできないかと模索をはじめました。

Hash now, don't you cry

ここからは、SQLite3 の主キーが rawid と同等の場合に、主キーの最大長である 8 バイトの数値をハッシュ関数でいかに作成したかの具体的な内容になります。

PHP の場合、fnv1 系(fnv164 もしくは fnv1a64)のアルゴリズム一発で 8 バイト(64 bit, 16 桁の HEX 文字列)のハッシュが作れます。

そのため、古いキーを単純にハッシュ化して再登録すれば楽に移行できます。しかも、速い。

$key_prime_new = hash('fnv164', $key_prime_old);

ところが、いくつか問題があるのです。

現在この記事で話題にしている DB が扱っているデータは登録後の変更はありません。いや、むしろ変更してはいけないものなのです。

ところが自由度の高い設計であるためか、自分の独断と都合により何故か勝手に値を変えちゃう一部の層(上流やオッチャン層)がありました。その層に弱い上司からコッソリと指示を受けるたび、バックアップから元に戻す作業のイタチごっこが定期的に発生していました。

これではいつかは盛大なポカをやりかねません。仕組みとしてのポカよけが必要と感じ、もう少し工夫をしたいなと思いました。

昨今の行政の改ざん問題でも提案されている文書のハッシュ化を ID として取り入れたいと考えたのです。

つまり、イメージではこういうことです。

// 旧IDでデータ取得
$value = fetchValueFromDB($key_prime_old);
// データ → ハッシュ化(16進)→ 10進 → 整数
$key_prime_new = (integer) hexdec(hash('fnv164', $value));

先の「要オッチャン対策 DB」は「ユーザが測定したデータの値と同じ値のものを DB から探し、関連情報(ヒットした行のデータ)を返す」用途に使われています。ピピピッピッと打つか、ピッとバーコードを読み込むと、ポッとデータが表示されるシンプルなものです。

つまり、ユーザ側(クライアント側)で測定したデータをハッシュ化して渡し、 DB(サーバー側)は受け取ったキーを検索すれば速度改善・改ざん防止・オッチャン対策の良いとこ取りになります。DB もシンプルに実装・構成できます。

ここで、もし1つ前の登録データのキーもハッシュ化してフィールドに内包(列を追加)すれば、ブロックチェーンに近い考え方になりますよね。そもそも SQLite なので、同期されたデータは各クライアント(ユーザ)のローカルにありますし。

さて、この方法でテストしたところ、今のところ1億件ちょっとの既存データで衝突もなく問題なさそうなのですが、1つのアルゴリズムに依存したくないという気持ちもありました。そう、ハッシュ値の衝突が怖いのです。

そもそも、この程度(10 年で 1〜2 億件程度)のデータ量であれば、SQLite3 の 1844京6744兆737億件以上も使える 8 バイト(64ビット)のキーをそのまま使うのはもったいないのです。大は小を兼ねるとは言え、貸し倉庫クラスなのにデズニーランド・クラスのスペースを使うようなものです。

十分な年数に耐えつつ、衝突に関しては鳩の巣原理(鳩の数より巣箱の数が少ないと、1つ以上の巣箱で衝突が起きる原理)は少なくとも網羅できるバイトの長さを検討した結果、最長 4 バイト長(= 42.9 億個)のキーとしました。

そして、先の「衝突しても別のアルゴリズムだと衝突しない(可能性が高い)」屁理屈を取り入れて、「4 バイトの A 型ハッシュ値 + 4 バイトの B 型ハッシュ値 = 8 バイトのキー」を作ってみたいと思いました。

具体的には 4 バイト長のハッシュ・アルゴリズムである crc32fnv132 の2つをあわせて以下のような Primeキーの算出を考えました。

$key_prime_hex = hash('fnv132', $value) . hash('crc32', $value);

厳密に言うと CRC-32 はハッシュではなくチェックサムなのですが、計算コストをケチってしまいました。これが後に懸念を産むことになります。

  • crc32 @ Wikipedia(日本語)
  • fnv-1 32 @ Wikipedia(英語)

先の fnv-1 64(8 バイト長のアルゴリズム)単体と比べて2倍くらい速くなるのですが、移行のための一括登録のデータ量が 500 万件を越えたあたりから、むしろ遅くなりました。アルゴリズムの組み合わせにもよると思いますが、アルゴリズムによっては初期化に原因がありそうです。

しかし、本番データは一括 INSERT させる予定です。つまり、一旦 DB をダンプ出力して主キーを整形しておき、データを新規 DB に一括で INSERT させる感じです。

また、実際の用途では新規登録時の速度はさほど必要とされておらず、登録頻度も高くありません。むしろ登録より日々の引き出し時の速度が速くなったことのほうが改善感があって良いと思います。

手元の2億件弱のサンプル・データで、このアルゴリズムの組み合わせで衝突は発生しませんでした。しかし、アルゴリズムの仕様を調べていくうちに確信が持てなくなりました。

非暗号学的ハッシュに悩む

CRC はチェックサムなのでデータが連番の場合に弱いのと、fnv-1 系(Fowler–Noll–Vo)のアルゴリズムは非暗号化型ハッシュ、つまり暗号学的ハッシュ関数ではないため、スティッキーステートと呼ばれる問題を孕んでいます。(暗号学的ハッシュについては上部「ハッシュ関数の基本と特徴」参照)

Sticky State – Being an iterative hash based primarily on multiplication and XOR, the algorithm is sensitive to the number zero. Specifically, if the hash value were to become zero at any point during calculation, and the next byte hashed were also all zeroes, the hash would not change. This makes colliding messages trivial to create given a message that results in a hash value of zero at some point in its calculation. Additional operations, such as the addition of a third constant prime on each step, can mitigate this but may have detrimental effects on avalanche effect or random distribution of hash values.
Non-cryptographic hash | Fowler–Noll–Vo hash function @ Wikipedia より)

【筆者訳】
スティッキーステートFowler–Noll–Vo 関数は、主に乗算と XOR に基づく反復ハッシュであるため、このアルゴリズムは数値ゼロに敏感です。具体的には、ハッシュ値が計算中のいずれかの時点でゼロになり、続くバイトのハッシュがすべてゼロであった場合、ハッシュは変化しません。これにより、計算のある時点でハッシュ値がゼロになるメッセージが与えられた場合、衝突するメッセージを簡単に作成できます。各ステップで第3の素数を定数として追加するなどの操作で、これを軽減できますが、アバランシェ効果またはハッシュ値のランダム分布に有害な影響を与える可能性があります。

筆者も良く理解出来ていないのですが、fnv-1 は主にハッシュテーブルやチェックサムで使用するために速度を優先して設計されたハッシュ関数として開発されたため、暗号学的ハッシュ関数と比較してランダム性に欠けるということのようです。つまり fnv-1 も CRC と 似た連番に弱い問題を持っていたのです。

この DB の仕組みも、ある種のハッシュテーブルと似てはいるものの、この CRC と fnv-1 の組み合わせではコンテンツの高速な確認には使えても ID としては厳しい予感がします。なんたるジレンマ。

となると、より分散性の高いアルゴリズムである SHA などの暗号学的ハッシュの一部を使った方が良いことがわかりました。

問題はコスト(速度)です。

しかし、記事上部の各アルゴリズムの測定速度を見てもわかるように PHP7 の場合 100 万回ぶん回して 0.n 秒の差です。PHP8 だとさらに数倍速くなるので、微々たる差だと思います。

そのため、CRC-32 や fnv-1 を使うよりは Git のコミット ID のように SHA-256 や SHA-512 などのハッシュ値の頭 4 バイトを使うのがよろしいかと思われます。

🐒 私はそうすることにしました。この仕組みが認められるころには PHP8 もリリースされると思うし。いつか Wikipedia のデータをぶっ込んで検証してみたいと思います。どうも、変更できない仕組みが一部で都合が悪いらしく採用されなさげ、ってかその仕事も辞めちゃったので実装することもなさげです。たくさんの「いいね」をいただけたので模索してよかったと思います。

イメージとしてはこんな感じ
$len   = 8; //4バイトのHEX文字列長
$value = fetchValueFromDB($key_prime_old);
$hash1 = substr(hash('sha256', $value), 0, $len);
$hash2 = substr(hash('sha512', $value), 0, $len);

// 8バイトの主キー
$key_prine_new = (integer) hexdec($hash1 . $hash2);

(え? 「もう、KVS でいいじゃん」って?ま、まぁ…ねぇ、、、枯れた技術を好むのも歳なんですかねぇ)


  1. SQLite3とは、著作権の発生しないオープンソースのデータベース管理システムです。名前からわかるように SQL の構文でデータにアクセスでき、リレーショナル・データベース(RDBMS)の1つです。
     特徴としては「本体も動作も軽量である」ことと「サーバーを立てずに使えること」があります。サーバー型でないため、複数ユーザーや複数アプリからの同時利用には向かないのですが、アプリごとにデータを保存する場合に威力を発揮するタイプです。
     モバイル・アプリやゲームなどのダウンロードやキャッシュ・データであったり、macOS の場合は標準でインストールされており、Spotlight などの検索用の DB としても使われています。(sqlite3 -help で確認可能)
     リアルタイムに激しく変動するデータでない場合、アプリ起動時に本艦となるサーバーからデータ・ベースをダウンロードしてローカルに保存することで、ネットワークのトラフィックを減らしたり、オフラインで利用させたり、レスポンスの向上に使われたりする便利なプログラムです。
    関連リンク:SQLite @ Wikipedia 日本語 

KEINOS
A Japanese made in Mexico with Mexican quality ;-) Who monkey around the jungle of codes. 記事の日本語がおかしかったら遠慮なく編集リクください。また、記事に「LGTM」が付くたび、なるべく何かしら加筆・修正してブラッシュアップしています。基本的に変更通知はお送りしません。
https://blog.keinos.com/
qiitadon
Qiitadon(β)から生まれた Qiita ユーザー・コミュニティです。
https://qiitadon.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away