「数字6桁パスワードのMD5ハッシュ値の総当たり」Pythonでやってみた

  • 16
    Like
  • 0
    Comment
More than 1 year has passed since last update.

面白そうなので、参加してみた

これは、パスワード問合せシステムを作る (clojureのreducers)に端を発する企画(?)でJALのパスワードの管理システムを現実的な範囲で達成可能な方法を妄想するものです。

今更とか時代遅れとか言わないでください。

過去の業績(順不同)

一覧に漏れがあった場合はお知らせください。追加させていただきます。

ここに、全く輝かない記録が付け加わります。

Pythonによる「数字6桁パスワードのMD5ハッシュ値の総当たり」

実行環境

os:windows7 Home Premium sp1
cpu:i7-4770T @2.50GHz
Python:3.4.1(Anaconda 2.0.1 (64-bit))

ソースコード

Python3なので、文字列をbyte列に変換する作業が入っています。
cpuは8コアですが、並列数は4にしてあります。
使ったコードはここに置いてあります。

シングルスレッド版

hash_single.py
import time
import hashlib
import sys

def main():
    argv = sys.argv[1:]
    if len(argv) != 2:
        sys.exit(0)

    salt = argv[0]
    hash = argv[1]

    start = time.time()
    for i in range(1000000):
        pw = "{0}${1:06d}".format(salt, i).encode("utf-8")
        tmp = hashlib.md5(pw).hexdigest()
        if hash == tmp:
            print("match[{0:06d}]".format(i))
    end = time.time()
    print("elapsed time:{0}s".format(end - start))

if __name__ == "__main__":
    main()

マルチスレッド版

hash_parallel.py
import time
import hashlib
import sys
from multiprocessing import Pool
from itertools import repeat

def calc_hash(arg):
    hash, salt, i = arg
    tmp = hashlib.md5("{0}${1:06d}".format(salt, i).encode("utf-8")).hexdigest()
    return hash == tmp

def main():
    argv = sys.argv[1:]
    if len(argv) != 2:
        sys.exit(0)

    salt = argv[0]
    hash = argv[1]

    start = time.time()

    pool = Pool(4)
    result = pool.map(calc_hash, zip(repeat(hash), repeat(salt), range(1000000)))
    index = result.index(True)
    print("match[{0:06d}]".format(index))

    end = time.time()
    print("elapsed time:{0}s".format(end - start))

if __name__ == "__main__":
    main()

実行方法

それぞれを5回ずつ繰り返して時間を計ります。

python hash_single.py hoge 4b364677946ccf79f841114e73ccaf4f
python hash_parallel.py hoge 4b364677946ccf79f841114e73ccaf4f

計測結果

1回目 2回目 3回目 4回目 5回目 平均 標準偏差
シングル版 1.724097967 1.736099005 1.729099035 1.733099937 1.739099026 1.732298994 0.005891065
マルチ版 1.086061954 1.098062992 1.080061913 1.113064051 1.085062027 1.092462587 0.013278723

単位は秒

並列時の実行時間は非並列の63%
※参考
「数字6桁パスワードのMD5ハッシュ値の総当たり」OpenMPを使うと0.70秒までキタを元に少し変更したものの実行結果(並列数4)は0.912sでした。(ソースコード)

まとめ

並列化で実行時間が63%程度にしかなっていないので、並列化という点では全然ですが、cの場合と16%程度の差まで追いつけたので、Pythonは頑張った方だと思います。
cが駄目なだけとも言えなくもないですが。

追記(2014/09/23)

bytearrayなるものの存在を知りました。
pythonの文字列、byte列は変更不可ですが、bytearrayは変更可能です。
これを利用してシングルスレッド版で毎回byte列全体を作り直さずに数字6桁の部分だけを作り直せば速くなるかと思いましたが、0.1秒ほどしか早くならず、期待したほどではありませんでした。

何をしたのかわかる程度に、変更部分を載せておきます。

from itertools import product
pw = bytearray("{0}${1:06d}".format(salt, 0).encode("utf-8"))  # bytearrayを用意
for i, value in enumerate(product(b'0123456789', repeat=6)):
    pw[-6:] = value  # 数字の部分のみ変更

やっぱり、速さを突き詰めるならC/C++かな。