技術部門のBlog

Code & Daily thoughts.

暗号化されたパスワードを含むアカウント情報が漏洩した、らどうすればよいか？

新春に考えたいセキュリティの話です。

去年「暗号化されたパスワードを含むアカウント情報が漏洩した」というニュースを多く聞きました。 このニュースを聞いてどう思うでしょうか？

「漏洩したからといって、暗号化されているのだからまだ安全なはずだ」と考えるのは危険です。 この記事ではGPUを使ったブルートフォース攻撃で、いとも簡単に暗号化されたパスワード（＝パスワードハッシュ）を解読できることをデモを通して示します。

セキュリティの基本的な仕組みと問題、守り方を復習して新年の業務に備えましょう。

パスワードとハッシュ関数

パスワードの仕組みを学ぶと必ず出てくるキーワードが「ハッシュ関数」です。 ハッシュ関数は「出力から入力を推定することができない」という特徴を持った関数です。 数学的に言うと「逆関数を計算することができない」のがハッシュ関数なのですが、できなくするためにどんな天才数学者をもってしても解けないようなとても意地が悪い複雑な形をした式になっています。

digraph tree { rankdir=LR; 入力2 -> 逆関数 [dir=back]; 逆関数 -> ハッシュ値2 [dir=back]; 逆関数 [shape=rect]; 入力2 [label="元の入力"]; ハッシュ値2 [label="ハッシュ値"]; 入力 -> ハッシュ関数 -> ハッシュ値; ハッシュ関数 [shape=rect]; } tree 入力2 元の入力 逆関数 逆関数 入力2->逆関数 ハッシュ値2 ハッシュ値 逆関数->ハッシュ値2 入力 入力 ハッシュ関数 ハッシュ関数 入力->ハッシュ関数 ハッシュ値 ハッシュ値 ハッシュ関数->ハッシュ値

パスワードはハッシュ関数で計算した「ハッシュ値」としてコンピュータ上に保存されています。 通常コンピュータ上にはハッシュ値だけしか保存されていません。 ユーザが入力するのはパスワードですが、以下のようにしてハッシュ値に変換して比較します。

digraph tree { rankdir=LR; パスワード入力 -> ハッシュ関数 -> ハッシュ値; ハッシュ関数 [shape=rect]; 入力2 -> ハッシュ関数2 [style=dashed]; ハッシュ関数2 -> ハッシュ値2 [style=dashed]; ハッシュ関数2 [shape=rect, style=dashed, label="ハッシュ関数"]; 入力2 [style=dashed, label="パスワード設定"]; ハッシュ値2 [label="パスワードハッシュ"]; } tree パスワード入力 パスワード入力 ハッシュ関数 ハッシュ関数 パスワード入力->ハッシュ関数 ハッシュ値 ハッシュ値 ハッシュ関数->ハッシュ値 入力2 パスワード設定 ハッシュ関数2 ハッシュ関数 入力2->ハッシュ関数2 ハッシュ値2 パスワードハッシュ ハッシュ関数2->ハッシュ値2

ハッシュ関数は入力値が違えばハッシュ値も違うように注意深く設計されているため、「ハッシュ値が一致する＝パスワードが一致する」と考えることができます。 （ハッシュ関数を注意深く設計していても、異なる入力に対して同じハッシュ値を出力してしまうケースもあります。 そのようなケースを「ハッシュ値の衝突」と呼び、衝突が起こる頻度はハッシュ関数の性能を測る一つの尺度になります。 MD5というハッシュ関数はすでにそのような衝突をするケースが発見されています。SHA-1はまだそのような衝突が発見されていない、より強いハッシュ関数です。）

コンピュータ上に保存されたハッシュ値から元のパスワードを推定することはできません。 ハッシュ値の形でパスワードを保存しておくことで万一ハッシュ値が漏洩した場合でも、ある程度のセキュリティを確保することができます。 これがコンピュータセキュリティの基本であり「パスワードの暗号化」の正体です。

UNIX系のシステムの場合、管理者しか見ることができない「/etc/shadow」ファイルの中に各ユーザのパスワードハッシュが保存されています。 Windowsの場合は、管理者でも見ることができない特殊なレジストリ値（SAM領域）としてパスワードハッシュが保存されています。 ユーザ認証を行うWebアプリケーションやActive Directoryの場合は、データベースに各ユーザのパスワードハッシュが保存されます。 攻撃者はシステムへの侵入やSQLインジェクション攻撃、認証プロトコルのパケットキャプチャなどによってこれらのハッシュ値を盗もうとします。

ブルートフォース攻撃によるパスワードの解読

新しいハッシュ関数が考案されると、衝突可能性が検査されると同時に、本当に出力から入力を推定することができないかどうか多方面からの検討が行われます。

逆関数が計算できないにしろ、もしかしたらハッシュ値から入力を推定する部分的な手掛かりがあるかもしれません。 そのような甘い部分がないかどうかを検証するために、セキュリティの専門家達は考案されたハッシュ関数を徹底的に攻撃します。 現行利用されているハッシュ関数はそのような攻撃に耐えたものであるため（今後、新たな攻撃手法が発明されない限りは）安全に利用することができると考えられています。

ただ、逆の推定ができないハッシュ値ですがそこからパスワードを解読する方法もあります。 それがこれから紹介する「ブルートフォース（brute force）攻撃」です。

bruteは「野蛮」という意味です。 ブルートフォース攻撃は直訳すると「野蛮な力（チカラワザ）」を使った攻撃なのですが、具体的には以下のようにしてパスワードを解読しようとします。

digraph tree { rankdir=LR; 適当に生成した大量のパスワード -> ハッシュ関数 -> ハッシュ値; ハッシュ関数 [shape=rect]; 適当に生成した大量のパスワード [label="適当に生成した\n大量のパスワード"]; 入力2 -> ハッシュ関数2 [style=dashed]; ハッシュ関数2 -> ハッシュ値2 [style=dashed]; ハッシュ関数2 [shape=rect, style=dashed, label="ハッシュ関数"]; 入力2 [style=dashed, label="パスワード設定"]; ハッシュ値2 [label="パスワードハッシュ"]; } tree 適当に生成した大量のパスワード 適当に生成した 大量のパスワード ハッシュ関数 ハッシュ関数 適当に生成した大量のパスワード->ハッシュ関数 ハッシュ値 ハッシュ値 ハッシュ関数->ハッシュ値 入力2 パスワード設定 ハッシュ関数2 ハッシュ関数 入力2->ハッシュ関数2 ハッシュ値2 パスワードハッシュ ハッシュ関数2->ハッシュ値2

ハッシュ関数は逆の推定ができませんが、順方向の計算はできます。 ありとあらゆる文字列のパターンに対して順方向の計算を行いハッシュ値との比較を行うことで、いつか一致する文字列が見つかるだろう、というまさにチカラワザを使うわけです。

hashcatによるパスワード解読のデモ

原理的には確かにパスワード解読ができるブルートフォース攻撃ですが、特にパスワードが長い場合には天文学的な計算量が必要になり、実用的ではないと考えられていました。 しかし、近年だいぶ事情が変わりつつあります。

近年注目されているコンピュータ技術にGPUがあります。 GPUは元は3次元グラフィックを扱うための専用プロセッサだったのですが、計算を並列化して大量に処理できることから、人工知能分野で利用され様々な成果をあげています。 この特徴はパスワード解読でも非常に強力な武器になります。

これから紹介する「hashcat」はGPUを使ったブルートフォース攻撃を行うためのソフトウェアです。

hashcatを利用するにはOpenCLライブラリが必要です。 UbuntuとNvidia GPUの組み合わせを使っている場合、以下のコマンドを入力すると最新のOpenCLをインストールできます。

$ sudo add-apt-repository ppa:graphics-drivers/ppa
$ sudo apt-get update
$ sudo apt-get install nvidia-375 nvidia-opencl-dev

次にhashcatをダウンロードしてコンパイルします。

$ git clone https://github.com/hashcat/hashcat.git
$ cd hashcat/
$ make

無事にコンパイルができてOpenCLが認識されると、以下のコマンドに対して以下のように出力されるはずです。

$ ./hashcat -I
hashcat (v3.20-88-gd36cc4c) starting...

OpenCL Info:

Platform ID #1
  Vendor  : NVIDIA Corporation
  Name    : NVIDIA CUDA
  Version : OpenCL 1.2 CUDA 8.0.0

  Device ID #1
    Type           : GPU
    Vendor ID      : 32
    Vendor         : NVIDIA Corporation
    Name           : GeForce GTX 750 Ti
    Version        : OpenCL 1.2 CUDA
    Processor(s)   : 5
    Clock          : 1084
    Memory         : 499/1998 MB allocatable
    OpenCL Version : OpenCL C 1.2 
    Driver Version : 375.26

今回使うのはNvidia GTX 750Tiという、今では1万円程度で買える非常に安価なGPUです。

動作が確認できたら、どの程度の性能が出るかベンチマークを走らせてみます。

$ sudo ./hashcat -b                                                                                                                               
hashcat (v3.20-88-gd36cc4c) starting in benchmark mode...

OpenCL Platform #1: NVIDIA Corporation
======================================
* Device #1: GeForce GTX 750 Ti, 499/1998 MB allocatable, 5MCU

Hashtype: MD4

Speed.Dev.#1.....:  6968.2 MH/s (48.10ms)

Hashtype: MD5

Speed.Dev.#1.....:  3782.7 MH/s (88.68ms)

Hashtype: Half MD5

Speed.Dev.#1.....:  2337.8 MH/s (71.73ms)

Hashtype: SHA1

Speed.Dev.#1.....:  1287.2 MH/s (65.14ms)

Hashtype: SHA256

Speed.Dev.#1.....:   457.3 MH/s (91.33ms)

（省略）

単位が「MH/s」になっていますが、これは「Mega Hash per second」の意味で、例えばMD5ハッシュの場合、このGPUは毎秒3,782,700,000回のハッシュ計算ができるということです。 この数が大きければ大きいほど秒間にできるブルートフォース攻撃の試行回数を増やせるため、より高速にパスワードが解読できることになります。

毎秒3,782,700,000回もハッシュ計算ができると、案外、簡単にパスワードが解読できてしまいます。試しにパスワードを解読してみましょう。

以下のようにして、ある文字列からMD5ハッシュを計算します。

$ echo -n "hoge" | md5sum
ea703e7aa1efda0064eaa507d9e8ab7e  -

「ea703e7aa1efda0064eaa507d9e8ab7e」の部分がハッシュ値です。

hashcatを使ってブルートフォース攻撃によりハッシュ値を解読するために以下のコマンドを入力します。

  • 「-m 0」はMD5ハッシュを使うオプションです（hashcatはMD5以外にも様々なハッシュ関数に対応しています）
  • 「-a 3」はブルートフォース攻撃を行うためのオプションです（この記事では触れませんが辞書攻撃も可能です）
  • 試行する文字列は長さ1から一つずつ伸ばしていきます（「–increment –increment-min=1」オプション）
  • 文字種は小文字英字、大文字英字、数字の組み合わせで最大8文字まで伸ばします（「-1 ?l?u?d ?1?1?1?1?1?1?1?1」オプション）
$ ./hashcat -m 0 -a 3 --increment --increment-min=1 ea703e7aa1efda0064eaa507d9e8ab7e -1 ?l?u?d ?1?1?1?1?1?1?1?1
hashcat (v3.20-88-gd36cc4c) starting...

OpenCL Platform #1: NVIDIA Corporation
======================================
* Device #1: GeForce GTX 750 Ti, 499/1998 MB allocatable, 5MCU

（中略）

ea703e7aa1efda0064eaa507d9e8ab7e:hoge                     

Session..........: hashcat
Status...........: Cracked
Hash.Type........: MD5
Hash.Target......: ea703e7aa1efda0064eaa507d9e8ab7e
Time.Started.....: Mon Jan  2 15:31:58 2017 (0 secs)
Time.Estimated...: Mon Jan  2 15:31:58 2017 (0 secs)
Input.Mask.......: ?1?1?1?1 [4]
Input.Charset....: -1 ?l?u?d, -2 Undefined, -3 Undefined, -4 Undefined 
Input.Queue......: 4/8 (50.00%)
Speed.Dev.#1.....: 43831.8 kH/s (2.07ms)
Recovered........: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.........: 7388168/14776336 (50.00%)
Rejected.........: 0/7388168 (0.00%)
Restore.Point....: 0/238328 (0.00%)
Candidates.#1....: sari -> oXvZ
HWMon.Dev.#1.....: Temp: 45c Fan: 41% Util: 71% Core:1163Mhz Mem:2700Mhz Lanes:16

Started: Mon Jan  2 15:31:56 2017
Stopped: Mon Jan  2 15:31:58 2017

「Started」「Stopped」の時刻からわかるように、2秒で元の文字列「hoge」が解読できてしまいました。

「hoge」はさすがに簡単過ぎだろうということで、今度は複数の文字種が混じった標準的な長さ（8文字）のパスワードで試してみます。

$ echo -n "31EhJTkV" | md5sum
0de24d0f652a4818f5ca124fa00a0d37  -

解読してみましょう。

$ ./hashcat -m 0 -a 3 --increment --increment-min=1 0de24d0f652a4818f5ca124fa00a0d37 -1 ?l?u?d ?1?1?1?1?1?1?1?1
hashcat (v3.20-88-gd36cc4c) starting...

OpenCL Platform #1: NVIDIA Corporation
======================================
* Device #1: GeForce GTX 750 Ti, 499/1998 MB allocatable, 5MCU

（中略）

0de24d0f652a4818f5ca124fa00a0d37:31EhJTkV                 

Session..........: hashcat
Status...........: Cracked
Hash.Type........: MD5
Hash.Target......: 0de24d0f652a4818f5ca124fa00a0d37
Time.Started.....: Mon Jan  2 15:52:21 2017 (16 hours, 11 mins)
Time.Estimated...: Tue Jan  3 08:03:23 2017 (0 secs)
Input.Mask.......: ?1?1?1?1?1?1?1?1 [8]
Input.Charset....: -1 ?l?u?d, -2 Undefined, -3 Undefined, -4 Undefined 
Input.Queue......: 8/8 (100.00%)
Speed.Dev.#1.....:  3625.6 MH/s (11.15ms)
Recovered........: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.........: 210995172147200/218340105584896 (96.64%)
Rejected.........: 0/210995172147200 (0.00%)
Restore.Point....: 885145600/916132832 (96.62%)
Candidates.#1....: saZJlXnZ -> flFouHfQ
HWMon.Dev.#1.....: Temp: 80c Fan: 54% Util: 97% Core:1163Mhz Mem:2700Mhz Lanes:16

Started: Mon Jan  2 15:35:49 2017
Stopped: Tue Jan  3 08:03:24 2017

と、16時間30分ほどの時間がかかりましたが無事に元の文字列「31EhJTkV」が解読できました。

8文字パスワードの解読に16時間30分、という結果を長いと考えるか短いと考えるかですが、長そうに見えて実は一日以下しかかかっていません。 また、今回使ったのは1万円程度で買える非常に安価なGPUである、ということもあわせて考えてみてください（攻撃側が使うGPUの性能については次で紹介します）。

暗号化されたパスワードを含むアカウント情報が漏洩したらどうすればよいか？

デモからわかったように「暗号化されたパスワードを含むアカウント情報が漏洩した」ら、例え複雑なパスワードを設定していたとしても「まもなくパスワードは解読される」と考えるべきです。

元のパスワードが解読されるのは時間の問題で、その時間はあまりかからなくなっています。

今回は安価なGPUを1個だけ搭載したコンピュータを使いましたが、GPUの性能は日進月歩で上がっており、またコンピュータに複数搭載することもできます。 Google画像検索で「gpu bruteforce」で検索すると、GPUブルートフォースを行うために8つのスロットすべてにGPUを搭載したコンピュータの写真が大量に出てきます。

https://www.google.co.jp/search?q=gpu+bruteforce&tbm=isch

以下のURLにNvidia GTX 1080を8枚搭載したコンピュータのベンチマークが公開されています。

https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40

MD5ハッシュの項目を比較すると、

Hashtype: MD5

Speed.Dev.#1.: 24943.1 MH/s (97.53ms)
Speed.Dev.#2.: 24788.6 MH/s (96.69ms)
Speed.Dev.#3.: 25022.2 MH/s (97.76ms)
Speed.Dev.#4.: 25106.6 MH/s (97.42ms)
Speed.Dev.#5.: 25114.1 MH/s (97.42ms)
Speed.Dev.#6.: 24924.1 MH/s (97.30ms)
Speed.Dev.#7.: 25197.9 MH/s (97.30ms)
Speed.Dev.#8.: 25246.4 MH/s (97.00ms)
Speed.Dev.#*.:   200.3 GH/s

GPU 8個の合計で「200.3 GH/s」という結果が出ており、今回デモで使ったコンピュータの約50倍の性能です。 ブルートフォース攻撃にかかる時間は単位時間にできる試行回数に比例しますから、今回の8文字パスワードの場合は約20分で解けることになります。

攻撃側はこのような強力な計算機を24時間体制で、場合によっては複数台稼働させて元のパスワードを解読しようとします。 また今回は一つのハッシュだけを解読しましたが、実際は漏洩した大量のハッシュを一度に解析できるのですから、ハッシュはそれこそ面白いように次々と解けていくはずです。

では、暗号化されたパスワードを含むアカウント情報が漏洩したらどうすればよいのでしょうか？ 以下の各対応が有効です。

パスワードをすぐに変更しよう

アカウント情報漏洩のニュースを聞いたらパスワードをすぐに変更しましょう。 解読される前にパスワードを変えてしまえば被害を受けることはありません。

ただし、アカウント情報漏洩の発見自体が遅れたケース（近年このケースが増えています）ではこの対応をしてもアカウントはハッキングされてしまいます。 後述する「多要素（2要素）認証」の方が有効な対策です。

パスワードの使いまわしはやめよう

攻撃者はパスワードが解読できると、そのパスワードを使って漏出元のサイトだけでなく他のサイトへのログインも試行します。 なぜなら、多くのユーザが複数のサイトで同じパスワードを使いまわしていることを知っているからです。

パスワードは各サイトで別のものを設定しましょう。

複数のパスワードを覚えるのが難しい場合はlastpassなどのパスワードマネージャを使いましょう。 パスワードマネージャを使うことにはセキュリティ上のリスクもありますが、覚えられなくて同じパスワードを設定するよりも大分マシです。 覚えられるパスワードの長さは8文字あたりからつらくなってくると思いますが、パスワードマネージャを使えばそれよりも長いパスワードを設定して、漏洩が起こった際の解読までの時間稼ぎをすることもできます。

多要素（2要素）認証を有効化しよう

「多要素（2要素）認証」はパスワード認証を行ったあとにSMSや専用アプリでワンタイムパスワードを発行し、通常のパスワードに加えてそのパスワードを入力しないとログインできなくする認証方式です。 複数の要素（パスワードに加えてSMSなど）を使うことから多要素認証と呼ばれています。

GPUブルートフォースの登場でパスワードの信頼性が崩壊しかけている昨今ですが、多要素認証に対する強力な攻撃手法はまだ見つかっていないことからセキュリティを高く確保することができます。

各サービスに対する多要素認証の設定方法は以下の各URLを参照してください。

Google Accountの多要素認証の設定方法 https://www.google.com/landing/2step/

Facebookの多要素認証の設定方法（英語） https://www.facebook.com/notes/facebook-engineering/introducing-login-approvals/10150172618258920/

Dropboxの多要素認証の設定方法 https://www.dropbox.com/ja/help/363

Evernoteの多要素認証の設定方法 https://evernote.com/intl/jp/contact/support/info/2fa/

マイクロソフトアカウント（Onedrive）の多要素認証の設定方法 https://support.microsoft.com/ja-jp/help/12408/microsoft-account-about-two-step-verification

最近ニュースになったアカウント情報漏洩

過去の大規模なアカウント漏洩事件を受けて多くの組織はパスワードの保存にbcrypt暗号を使うようになっています。 bcryptはハッシュ関数というよりは暗号化アルゴリズムの軽量版というべきもので、MD5などのハッシュ関数に比べて計算（解読）に多くの時間がかかる、という特徴があります。 また、処理が複雑なのでGPUがうまく使えずCPUで処理せざるを得ないため、単体のコンピュータでの計算の並列性は低くなります。

ただし、攻撃側はクラスタマシンを使ってCPUを並列化して解読しようとしますので、時間稼ぎにはなるものの解かれなくなるわけではない、という点に注意しましょう。

yahoo.comのアカウント情報漏洩（5億件, bcrypt暗号） http://www.businesswire.com/news/home/20160922006198/en/

dropboxのアカウント情報漏洩（6800万件, saltつきbcrypt暗号） http://www.itmedia.co.jp/enterprise/articles/1609/01/news073.html

ebayのアカウント情報漏洩（1.6億件, saltつきハッシュ） http://info.rippleshot.com/blog/ebay

adobeのアカウント情報漏洩（3800万件, ハッシュ方式未公開、パスワードヒントを含む） https://nakedsecurity.sophos.com/2013/11/04/anatomy-of-a-password-disaster-adobes-giant-sized-cryptographic-blunder/

Comments