暗号化パスワード? ハッシュ化パスワード?

TL;DR

• 長いから大抵省略するけど、単なる「ハッシュ」と「暗号学的ハッシュ」の違いは意識しようぜ!
  • 単なる「ハッシュ」は、データの効率的なインデクス化が由来
  • 「暗号学的ハッシュ」は、元の値が推測困難な一方向性を持った変換を行うもの
  • どちらも「小さな一定の範囲の値に変換する」という意味では共通
• まあ今は大抵「ハッシュ」なんだけど「暗号化パスワード」って目くじら立てるほどじゃね?
  • 「暗号学的ハッシュ」が確立される前にできて定着した言葉だから仕方ないね
  • 単なるハッシュ化とも違うので、どういう違いがあるか知っておいた方がいいかな
• 昔のパスワードの風習が残ってたりするから気をつけろ!!
  • 記号を入れろとか、大文字小文字に数字を混ぜろとか今時古いよ!!
  • むしろ単語を並べていいからひたすら長くしろ!!

背景

まあなんか最近、「暗号化してないパスワードが流出」みたいな話があったせいか、色々言われてるけど、歴史的な話も含めて整理したほうがいいかなと。

ハッシュってなに?

イメージ

このtweet ( https://twitter.com/neer_chan/status/1090391993191034880 ) のイメージが秀逸。

何が秀逸って、ハッシュドポテトの「ハッシュ」と、今回話題にしてる「ハッシュ」は同じ言葉であること。
つまり元の素材を切り刻んでまぜこぜして小さくまとめてるもの。

ただ「非可逆」ってのはちょっと待って欲しい。確かにハッシュはある意味で非可逆なんだけど、注意しないと意味を取り違えてしまう。
何より、単なるハッシュと暗号学的ハッシュってのがあって違う特性を持つからだ。

もともとのハッシュ

このtweetで教えて頂いたけど、ハッシュのアイデアは1953年に誕生したようだ。

上のリンク先の記事は英語なのであんまり読み込めていないんだけど、鍵は効率的なインデクス化。

つまり、サイズもまちまちなデータを切り刻んで小さく一定の範囲にまとめたら ( 例えば1～10000という数値に置き換えるとかできたら )、それをインデクスとして、データの保存・検索が効率的に行えるよね、ということ。

早い話がハッシュテーブルのアイデアだ。今でもフツーに使われていて、プログラミング言語PerlやRubyで連想配列のことをハッシュと言うのはコレが背景にあるから。

ただし、データを小さな範囲に押し込める以上、必ず(ハッシュの)計算結果が同じになるデータの組み合わせが現れる。これを衝突と言う。絶対に避けられない。
※衝突はあまり歓迎できないので、計算結果がばらけるようにしたり、値の範囲を十分に広く確保したりといった対策で、起こりにくいようにはするけどね。

そういう意味で「非可逆」なんだけど、これは「元のデータの候補が複数あるから絞り切れない」という意味であって、元のデータが推測できないかどうかまでは言ってないことに注意。
※ハッシュドポテトだって、「元のポテトの食感が活きてるね!」ってのもありうるよね?

暗号学的ハッシュ

一方で、暗号学的ハッシュは比較的まだ新しい。多分皆大好き公開鍵暗号より後の話だと思う。
1976年に公開鍵暗号のアイデアと、その1つ「鍵交換」としてのDH法、1977年にRSA暗号/RSA署名が発表されてるけど、この時点で暗号学的ハッシュは形になっていない。

ただ、署名のアイデアが色々出てくるなかで、「元のデータを推測できない一方向変換を使うのどうよ?」というアイデアがでてきた。
※RSA署名は(今では珍しいけど)鍵があれば逆変換できる方式なのに注意

これは、1979年のLamport、"Constructing Digital Signatures from a One Way Function"で、"One Way Function"と言ってるのがそう。
で、もし変換した結果できる値の候補の方が少なければ One Way Hashing だと言ってる。つまり、一方向性の方が先にあって、それに「小さい範囲にまとめる」という性質を追加した感じ。これがアイデア的には「暗号学的ハッシュ」の元祖になるんではないかと思う。
※「元のデータを推測できない」以外にも「衝突を起こす元データのペアを作るのが困難」という特性もあるんだけど、ここでは割愛。

その後、主に共通鍵暗号であるDESを活用した様々な方式が考え出されたようだけど、おそらく世の中にちゃんと出て使われ出したのは1989年のMD2 ( RSA-MD2署名 )。そういう意味で、かなり後発の技術。
それ以降、MD5, SHA-1, SHA-2(SHA256等), … と変遷してきているのはまあ説明しなくても良いと思う。

ということで、方やインデクス化、方や一方向性とその元の考えと誕生時期は大分違うということだ。

一旦ハッシュのまとめ

• 「ハッシュ」は元の素材を切り刻んでまぜこぜして小さく一定の範囲にまとめるところから来ている
• 元の目的は、データを小さい範囲にまとめることによる効率的なインデクス化
• それはそれとして「一方向性」(元の値が推測できない)というところから暗号学的ハッシュが発展した
• 単なるハッシュと暗号学的ハッシュは、「小さくまとめる」という点は共通点だけど、その由来は大分違う

暗号化パスワードってなに?

由来

かつて、さるマルチユーザOSにログインするためのログインパスワードは、パスワードそのものが文字列としてファイルに保存されていたらしい。
※もちろん管理者にしかそのファイルを見ることはできなかっただろうけど。

もちろん、開発者だってそれが良いと思っていたわけではないだろうし、実際、パスワードに変換をかけて難読化するような工夫を考えていた。
おそらくUNIX系システムでの元祖は、1973年のUNIX 3rd Editionに搭載されたAPI、cryptだ。実はこのAPI名は、今でもLinux含めUNIX系のシステムに引き継がれている。

あ、そこで「いやLinux/UNIXのパスワード事情なんて知らないよ」とか言わない。Webアプリが発展した土壌だって多くはLinux/UNIXだよ? 2000年以前にCGI用にブレイクしたPerl、2000年あたりから人気の出てきたPHP、これらWebアプリでパスワードを保存するときに使うAPIの名前だってこのcryptだったんだから。

閑話休題。そして1979年のUNIX 7th Editionには、共通鍵暗号の元祖であるDES(1977年)の処理を取り入れた形に進化した。
それは、パスワードをキーとして固定データにDES暗号化を施すことで、元のパスワードを推測することが困難なデータを作り出す、というものだ。
※ちなみに、このDESの制約から、パスワード長は最大8文字、56bit分の選択肢しかない。

ちなみに、単純に暗号化するだけでなく、12bitのソルトというデータでDESのS-BOX(データ変換テーブル)を攪乱し、その上でDESの処理を25回かける(今で言うストレッチングに相当する)ことで、解析に要する手間をかさ増ししている。

このDESによる方式は、ほぼ標準として以降長い間使われ、その間に「暗号化パスワード」という用語が定着したと思われる。
※というより、今でもUNIX系のシステムのマニュアルには「暗号化パスワード」という用語が使われている。例えばshadow(5)に"encrypted password"とあったり。

ハッシュ化じゃないの?

「元のデータが推測困難なように変換する、それって(暗号学的)ハッシュ化じゃないの??」と思われるかも知れない。

いや、確かに暗号化しても復号するわけじゃないし実際問題として暗号学的ハッシュの特性そのものなんだけど、当時まだ暗号学的ハッシュなんてなかったということに注意して欲しい。DES版のcryptが1979年なのに対し、上で挙げたMD2ですら1989年なのだ。

近年では、処理の実態は暗号学的ハッシュを利用したものに移行しているけれども、その最初と思われるのですら1994年のFreeBSD2.0に実装されたmd5版cryptだ。( MD5自体は1992年 )
※当時のRelease NotesにMD5のことが記されている

それでも名前や用語はそのままになっている。まあ、もう、定着しちゃってたんだという他はないと思う。
実際に暗号化はしてたんだし、元のパスワードを隠す意味もあるし、めちゃくちゃ変って訳でもないかなというのが個人的な感触。
少なくとも、全然暗号化じゃないのに署名のことを「秘密鍵で暗号化」とか言っちゃうよりは100倍はマシかな。
※参考: 「電子署名=『秘密鍵で暗号化』」という良くある誤解の話

単純なハッシュ化との違い

さて、今ではパスワードの保存は「ハッシュ化」というのが常識(だよね?)となっているけど、これも単純にハッシュ処理を行っているわけではない。

DES版のcryptの話の時に出た、ソルトとストレッチングだ。

• ソルト
  計算結果を攪乱するための付加データ
• ストレッチング
  内部的に変換を多重化(例えばmd5版cryptだと1000回)することで処理時間をかさ増しすること

なんでこんなことするの? と言うと、それは偏にパスワード自体にハッシュ方式に見合った情報量がないからだ。
例えば、(今では強度不十分として使われなくなった)暗号化ハッシュMD5ですら128bitのハッシュ値を生成するけれど、これはパスワードで言うと、ランダムに作るとしても20文字程度の情報量に相当する。辞書にあるような単語を使うなら、もっと文字数を多く見たものだろう。…一部の人を除いて、そこまでのパスワードを設定なんてしない。
場合によっては、同じパスワードが使われることもあるかもしれない。ソルトによる攪乱がなければ、それだけで同じパスワードだとバレてしまう。

そのため、総当たりや計算済みのハッシュ値の蓄積(レインボーテーブル)で簡単に解析できないよう、これらの処理を行ってるわけだ。

こういった処理の実装は、それ相応のライブラリに任せる話だと思うけど、一応そういう違いがあることは知っておいた方がいいと思う。

おまけ: 今なお残るパスワードの風習

さて、昔のcryptの特徴として、

※ちなみに、このDESの制約から、パスワード長は最大8文字、56bit分の選択肢しかない。

ということにちょろっと触れた。
もちろん、今はDES版のcryptよりももっと適切な手段があるわけだから、この制約にしばられることはない「はず」なんだけど…。でも、今でもこの時代遅れな制約に縛られてると思える風習が残っているので挙げてみたい。

• 適切なパスワード長は?
  上で「ソルト」や「ストレッチング」の説明をしたときに、これらを採用する理由として「パスワード自体にハッシュ方式に見合った情報量がない」ことを説明した。ということは、パスワードは長ければ長いほど破られにくくて良いわけだ。
  なのに…。周りをよく見渡してみよう。だいたいパスワードって最低8文字ってなってないだろうか?? 最低限の妥協という意識はあるかもしれないけどまあ8文字なら許容範囲やろという気分がないか?? 完全ランダムならまだマシかもしれないけど、普通に8文字ってもう今時弱いぞ?? DES版cryptの時の8文字に引きずられてないか? と疑ってみてほしい。
• 英数混合で記号を混ぜて!…??
  さてそうは言っても、無条件に長いパスワードを設定するのは心理的な抵抗がある場合もある。なぜなら、パスワード管理ツールに一任するなら十分長いランダムパスワードでも良いが自分で覚えて手動で入力するケースもあるからだ。そういう意味で8文字というのは心情的にピッタリくるのかもしれない。
  すると、短くても強度を保ちたいという動機からか、英字(大小)・数字に記号を混ぜてパスワードを作ろうというアドバイスが至るところから飛んでくる。
  しかし、だ。それは8文字しか使えないという状況でやむなく編み出した先人の知恵に過ぎない。変に記号を入れても覚えにくくなるだけで、それほどパスワード強度には寄与しない。だったら辞書に載っている単語でいいからたくさんつなげた方がマシだ、ということに気づいてほしい。
  ※参考: https://www.bizcompass.jp/original/re-management-129-2.html

終わりに

今の技術体系からすると用語が妙に感じることがあるかも知れないけど、一応それなりの歴史があったりするから注意したいかな。いや自分が生まれる前の話もあって、調べるのは大変なんだけど。