パスワード問合せシステムを作る (clojureのreducers)

現在のパスワードを教えてくれるからといって、「平文で保存してる！くぁwせdrftgyふじこlp‎」と脊髄反射してはいけません。

JALの6桁数字パスワードがどう格納されているか?
古いシステムなのでMD5でハッシュ化していると想定しますが、もちろんsaltは付けているでしょう。

さて、そんなパスワード保管方式で、現在のパスワード問合せに応答するシステムを作ってみます。

パスワードを「567890」、saltを「hoge」として、データベースには"hoge$567890"のMD5値"4b364677946ccf79f841114e73ccaf4f"が格納されているとします。

総当りしてみましょう。

(ns six-length.core
  (:require [clojure.core.reducers :as r])
  (:import [java.security MessageDigest]))

(defn hexdigest [s]
  (let [digester (MessageDigest/getInstance "MD5")]
    (. digester update (.getBytes s))
    (apply str (map #(format "%02x" (bit-and % 0xff)) (. digester digest)))))

(defn find-password [salt pw]
  (->> (range 0 1000000)
       (map #(format "%06d" %))
       (map (fn [_] [_ (hexdigest (str salt "$" _))]))
       (filter #(= pw (second %)))))  

こんな感じで、(range 0 1000000)で生成した6桁数字のパスワードを総当りで計算します。salt付きなので予め辞書を作っておくことはできません。

実行すると、

=> (time (into [] (find-password "hoge" "4b364677946ccf79f841114e73ccaf4f")))
[["567890" "4b364677946ccf79f841114e73ccaf4f"]]
"Elapsed time: 35719.659129 msecs"

… 36秒近くかかってしまいました。ちょっと使えないですね…

ちなみに実行環境は、Corei7-4770 Windows 7 です。

せっかくのマルチコアを活かせてないので、Clojureのreducersを使って、並列化してみます。

(defn find-password [salt pw]
  (->> (vec (range 0 1000000))
       (r/map #(format "%06d" %))
       (r/map (fn [_] [_ (hexdigest (str salt "$" _))]))
       (r/filter #(= pw (second %)))))

先ほどのfind-password関数はこのようになります。
vectorでないと並列実行されないので、(range 0 1000000)をvecで変換しています。(次のバージョンではrangeもreducers対応されるという噂があります…)

あとは元のmapやfilterをreducersに置き換えるだけです。

=> (time (r/fold (fn ([] [])
                  ([x y] (into x y)))
              (find-password "hoge" "4b364677946ccf79f841114e73ccaf4f")))

["567890" "4b364677946ccf79f841114e73ccaf4f"]
"Elapsed time: 11248.795464 msecs"

11秒になりました！ これならSalt付きMD5で一昔前のふつうのパスワードの保存方式で作ってあるシステムでも、現在のパスワードを通知することができそうですね