【暗号コラム】第7回パスワード解析：辞書攻撃＆類推攻撃篇

パスワードは"password"です。

前回はZipアーカイブファイルにかけられたパスワードを破る方法の1つとして総当り攻撃を紹介しました。総当り攻撃は確実な方法であるものの、攻撃に非現実な時間がかかり実用的ではない、という話でした。

非現実な時間がかかる原因として可能な組み合わせをすべて試すからなのですが、実際にそのパスワードを使うものなのでしょうか？例えば、いくら安全だからといって「Kd6Qw9tFB7nJtbUf」というパスワードを利用するでしょうか？情報はそれを守ることだけでなく利用することにも価値があります。覚えられない、覚えにくいパスワードでは情報の利用価値が減ります。

覚えやすいパスワードは便利ですが、場合によっては攻撃者に付け込むスキを与えることになります。今回は、もう1つのパスワード解析手段「辞書攻撃」「類推攻撃」を題材に「覚えやすい、かつ安全なパスワード」を模索します。

辞書攻撃と類推攻撃

辞書攻撃とは、パスワードに使われそうな文字列が大量に登録された辞書（テキストファイル）を使って順次試す方法です。例えば、英語辞典に載っている単語(dog, cat, birdなど)やコンピュータでよく使われる単語(tmp, admin, hogeなど)が該当します。例えば、「qwerty」という単語はご存知でしょうか？これはよく使われるキーボード配列の一部で左上にある「q」から右へ読んだものです。パスワードが覚えられないからキーボードの文字列にしちゃおう、と「aqwsxz」とようにすると辞書攻撃の餌食となります。

類推攻撃とは、サービスの利用者の情報からパスワードを推測する方法です。例えば、誕生日や特定の日付（ファイルの送信日）、担当者の名前からパスワードを推定します。担当者が鈴木だから「ikuzus」にしようとか、今日は2016年4月11日だから「20160411」にしようとすると見事に類推攻撃にしてやられます。

ここで、SplashData社が公開した「2015年に最も使われたパスワード」のランキングを紹介します。 https://www.teamsid.com/worst-passwords-2015/ 1位から5位まで引用してみます。

1. 123456
2. password
3. 12345678
4. qwerty
5. 12345

このように、よく使われるパスワードは単純な数列やキーボードの文字列となっています。よく使われる、ということは辞書攻撃の餌食になりやすい、ということを意味しています。

総当り攻撃 VS 辞書攻撃

まず総当り攻撃と辞書攻撃を比較します。パスワードは「fire」であるとします。

総当り攻撃はパスワードが半角英字6文字でと仮定して総当りで調べます。
辞書攻撃は有名なパスワードクラッカーであるJohn the Ripperの開発元にある辞書を利用して攻撃します。

総当りの場合を実行するプログラムは次のようになります。

%%timeit
import itertools
import os
import string
import zipfile
def extract_zip(zipfile_path, passward_str):
with zipfile.ZipFile(zipfile_path, 'r') as zf:
zf.extractall(os.path.splitext(zipfile_path)[0], pwd=passward_str.encode())
target_iter = itertools.chain([""], itertools.product(string.ascii_lowercase, repeat=4))
for challenge in target_iter:
try:
password = "".join(challenge)
extract_zip("fire.zip", password)
print('PASS:', password)
break
except KeyboardInterrupt:
print("KeyboardInterrupt")
break
except RuntimeError:
pass
except Exception:
pass

Jupyter Notebook上で実行すると、約1分もかかりました。次に、辞書を使って解析します。

%%timeit
import itertools
import os
import zipfile
def extract_zip(zipfile_path, passward_str):
with zipfile.ZipFile(zipfile_path, 'r') as zf:
zf.extractall(os.path.splitext(zipfile_path)[0], pwd=passward_str.encode())
with open("password.txt") as f:
for password in f:
try:
extract_zip("fire.zip", password.rstrip("\n"))
print('PASS:', password.rstrip("\n"))
break
except KeyboardInterrupt:
print("KeyboardInterrupt")
break
except RuntimeError:
pass
except Exception:
pass

Jupyter Notebook上で実行するとわずか2秒！4文字でもここまで差が付くのでより長いパスワードだとさらに差が付きます。長くすれば安全と思って辞書にある長い単語「Supercalifragilisticexpialidocious」を採用するとあっさり魔法のように破られます。

総当り攻撃 VS 類推攻撃

次に総当り攻撃と類推攻撃を比較します。パスワードが日付を基にした「20160412」であるとします。

総当り攻撃の場合は数値のみと仮定して1桁から順に試します。
類推攻撃は「yyyymmddという形式になっているだろう」と推測して順に試します。

総当りの場合を実行するプログラムは次のようになります。簡略化のため、20100101（2010年1月1日）から探索を開始します。

%%timeit
import itertools
import os
import zipfile
def extract_zip(zipfile_path, passward_str):
with zipfile.ZipFile(zipfile_path, 'r') as zf:
zf.extractall(os.path.splitext(zipfile_path)[0], pwd=passward_str.encode())
for challenge in itertools.count(20100101):
try:
password = str(challenge)
extract_zip("cutecat.zip", password)
print('PASS:', password)
break
except KeyboardInterrupt:
print("KeyboardInterrupt")
break
except RuntimeError:
pass
except Exception:
pass

Jupyter Notebook上で実行すると約30秒かかりました。次に、「パスワードは日付である」と推測して解析します。こちらも簡略化のために2010年1月1日から始めます。

%%timeit
import datetime
import itertools
import os
import zipfile
START_DATE = 733773 # 2010年1月1日
def extract_zip(zipfile_path, passward_str):
with zipfile.ZipFile(zipfile_path, 'r') as zf:
zf.extractall(os.path.splitext(zipfile_path)[0], pwd=passward_str.encode())
for ordinal in itertools.count(START_DATE):
d = datetime.date.fromordinal(ordinal)
try:
password = "{y:0>4}{m:0>2}{d:0>2}".format(y=d.year, m=d.month, d=d.day) 
extract_zip("cutecat.zip", password)
print('PASS:', password)
break
except KeyboardInterrupt:
print("KeyboardInterrupt")
break
except RuntimeError:
pass
except Exception:
pass

Jupyter Notebook上で実行するとわずか2秒弱でパスワードが解析できました。総当り攻撃、類推攻撃いずれも2010年1月1日（を意味する整数）から始めましたが、「日付」という推測だけでここまで結果が変わります。「日付」という推測が間違っていたとしても攻撃にかかる時間が短く済むのですぐに別の推測を行うこともできます。このように「送信日」や「誕生日」、「記念日」というのは簡単に破られてしまうのです。