はじめに
この記事の内容に従って問題が発生した場合でも責任は負いかねますので自己責任でお使いください
この記事では暗号化ハッシュを用いて保存されているパスワードを総当たり攻撃から守るために必要なパスワードの長さを検討します。すなわち、暗号化されたファイルや暗号化されたパスワードリスト（/etc/shadowとか）が流出したような場合にどの程度データが守れるのかを検討します。前提をよくお読みの上自己責任でお使いください。
前提
- ある暗号化ハッシュを総当たり攻撃から守ることを考える
- すなわち暗号化ハッシュに対して総当たり攻撃以外の攻撃が有効になった時には短時間で破られうる
- すなわちパスワードがよくあるもの（passwordとかadminとか）であれば、辞書攻撃で短時間で破られうる
- 暗号化ハッシュは手元にあることを想定する
- よって、並列化などにより短期間に大量の試行ができる場合を想定している
- オンラインサービスで一秒間のアクセス数が制限されていたり、異常なふるまいを検知して遮断できる場合には当てはまらない
- 総当たり攻撃には Aamazon Web Service / Tesla K80 / hashcat を用いる
- ハードウエアには Amazon Web Service の p2.xlarge インスタンスを用いている
- Tesla K80を搭載している
- すなわち FPGA を使ったり、より強力なハードウエアが登場した時にはより短時間で破られうる
- ソフトウエアは hashcat を用いている
- すなわち、より効率的なソフトウエアがあれば、より短時間で破られうる
- ハードウエアには Amazon Web Service の p2.xlarge インスタンスを用いている
- 妥当であるの定義は 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秒間に計算できるハッシュの数と文字種の情報があれば計算可能。
文字種の数
文字種の数は以下の通りである。ただし、この数字を数式に当てはめて計算してよいのは、パスワードが以下の種類の中からランダムに選ばれている場合のみで、数字が少ないとか記号が一文字しかないとかの場合にはパスワード空間が狭まってしまい適用できない。よくありがちな数字や記号の使用を必須とする制限を加えても、多くの人は末尾に１や！を追加するだけらしいので、あまり意味がないことに注意。
| 種類 | 数 |
|---|---|
| 数字のみ | 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文字近いランダムな文字列を使用する必要がある。そして、人間が簡単に覚えられるパスワードは英単語など一定の規則があることを考えると、そもそも暗号化に人間が設定するパスワードを使うことは不適切かもしれない。