セキュリティ

暗号化のパスワードの妥当な長さはいくらか?

More than 1 year has passed since last update.


はじめに

:bangbang: この記事の内容に従って問題が発生した場合でも責任は負いかねますので自己責任でお使いください :bangbang:

この記事では暗号化ハッシュを用いて保存されているパスワードを総当たり攻撃から守るために必要なパスワードの長さを検討します。すなわち、暗号化されたファイルや暗号化されたパスワードリスト(/etc/shadowとか)が流出したような場合にどの程度データが守れるのかを検討します。前提をよくお読みの上自己責任でお使いください。


前提


  • ある暗号化ハッシュを総当たり攻撃から守ることを考える


    • すなわち暗号化ハッシュに対して総当たり攻撃以外の攻撃が有効になった時には短時間で破られうる

    • すなわちパスワードがよくあるもの(passwordとかadminとか)であれば、辞書攻撃で短時間で破られうる



  • 暗号化ハッシュは手元にあることを想定する


    • よって、並列化などにより短期間に大量の試行ができる場合を想定している

    • オンラインサービスで一秒間のアクセス数が制限されていたり、異常なふるまいを検知して遮断できる場合には当てはまらない



  • 総当たり攻撃には Aamazon Web Service / Tesla K80 / hashcat を用いる


    • ハードウエアには Amazon Web Service の p2.xlarge インスタンスを用いている


      • Tesla K80を搭載している

      • すなわち FPGA を使ったり、より強力なハードウエアが登場した時にはより短時間で破られうる



    • ソフトウエアは hashcat を用いている


      • すなわち、より効率的なソフトウエアがあれば、より短時間で破られうる





  • 妥当であるの定義は Tesla K80 を1つ用い、100万年かけて総当たり攻撃によって解析できる確率が$10^{-20}$以下であること


    • 100万年と長いのは最近のスパコンが1万台近くのGPUを積んでいるので、並列計算されることを前提に安全係数をかけているため

    • AWSのスポットインスタンスまかなった場合 p2.xlarge の時間当たりの価格が \$0.2 程度であったので、 $0.2 \times 10^6 \times 356 \times 24 = \$1752000000$で約2000億円程度



  • ある一つのパスワードを破ることを想定している


    • すなわち、暗号化ハッシュ化されたパスワードリストが大量に手に入り、どれか一つだけでも破れればいい場合にはより短時間で破られうる



  • そもそも暗号化したファイルといえど流出することは問題であること


    • 一度流出してしまえばパスワードの変更はできない




計算方法

$L$: 解析にかかる時間(秒)

$R$: 1秒間に計算できるハッシュ値の数

$A$: 文字種の数

$M$: パスワードの長さ

$P$: パスワードが破られる確率

の時、以下の数式で表される。文字と数式は「DEPARTMENT OF DEFENSE PASSWORD MANAGEMENT GUIDELINE」に合わせた。

P=\frac{L\times R}{A^M}

A^M=\frac{L\times R}{P}

M=\frac{\log \frac{L\times R}{P}}{\log A}

また、前提より$P=10^{-20}$、$L=10^6\times 365 \times 24 \times 60 \times 60 < 6.4 \times 10^{12}$とおける。あとは1秒間に計算できるハッシュの数と文字種の情報があれば計算可能。


文字種の数

文字種の数は以下の通りである。ただし、この数字を数式に当てはめて計算してよいのは、パスワードが以下の種類の中からランダムに選ばれている場合のみで、数字が少ないとか記号が一文字しかないとかの場合にはパスワード空間が狭まってしまい適用できない。よくありがちな数字や記号の使用を必須とする制限を加えても、多くの人は末尾に1や!を追加するだけらしいので、あまり意味がないことに注意。

種類

数字のみ
10

アルファベット小文字のみ
26

アルファベット小文字+数字
36

アルファベット小文字大文字+数字
62

アルファベット小文字大文字+数字+記号
94


1秒間に計算できるハッシュの数

AWSのp2.xlargeインスタンスを利用して計測した主な結果は以下の通り。CSVでほしい方はGistからどうぞ。N=1なので、ばらつきがどの程度になるかの評価はしていない。

種類
試行回数 (H/s)

MD5
4626000000

SHA1
2005600000

SHA512
200500000

WPA/WPA2
93936

NTLM
8269700000

sha512crypt, SHA512(Unix)
34367

OSX v10.8+
2626

7-Zip
2398

WinZip
250000

MS Office <= 2003 SHA1 + RC4, collision-mode #1
58633100

Office 2007
32016

PDF 1.7 Level 3 (Acrobat 9)
831400000


前提を満たすパスワード長

以上の条件を満たすときにパスワード長はどの程度になるかを計算した結果が以下の通り。

Hash
数字のみ
アルファベット小文字のみ
アルファベット小文字+数字
アルファベット小文字+大文字+数字
+記号

MD5
42.5
30.0
27.3
23.7
21.5

SHA1
42.1
29.8
27.1
23.5
21.3

SHA512
41.1
29.1
26.4
22.9
20.8

WPA/WPA2
37.8
26.7
24.3
21.1
19.1

NTLM
42.7
30.2
27.5
23.8
21.7

sha512crypt, SHA512(Unix)
37.3
26.4
24.0
20.8
18.9

OSX v10.8+
36.2
25.6
23.3
20.2
18.4

7-Zip
36.2
25.6
23.3
20.2
18.3

WinZip
38.2
27.0
24.5
21.3
19.4

MS Office <= 2003 SHA1 + RC4, collision-mode #1
40.6
28.7
26.1
22.6
20.6

Office 2007
37.3
26.4
24.0
20.8
18.9

PDF 1.7 Level 3 (Acrobat 9)
41.7
29.5
26.8
23.3
21.1

こうしてみると、 $P=10^{-20}$と$L=10^{12}$が大きな影響を与えていて$R$による差はあまりなかった。


短いパスワードはどの程度危険か?

8文字などの短いパスワードを設定した場合、解析にどの程度の時間がかかるかを計算してみた。ここでは現実的なパスワードとして数字とアルファベット小文字のみで計算した。計算式は以下の通りで、平均的にかかる時間を計算するために$P=0.5$とした。

L=\frac{A^M\times P}{R}

Hash
所要時間(日)

MD5
0.0

SHA1
0.0

SHA512
0.1

WPA/WPA2
173.8

NTLM
0.0

sha512crypt, SHA512(Unix)
475.0

OSX v10.8+
6217.0

7-Zip
6808.1

WinZip
65.3

MS Office <= 2003 SHA1 + RC4, collision-mode #1
0.3

Office 2007
509.9

PDF 1.7 Level 3 (Acrobat 9)
0.0

0.0となっているのは1.2時間以内に解析可能で切り捨てられてしまっていたため。この数字が十分に大きいように見えても並列化すれば解析速度を10倍100倍には簡単にできることに注意すること。


まとめ

パスワードで暗号化ファイルを守るためには30文字近いランダムな文字列を使用する必要がある。そして、人間が簡単に覚えられるパスワードは英単語など一定の規則があることを考えると、そもそも暗号化に人間が設定するパスワードを使うことは不適切かもしれない。