Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
125
Help us understand the problem. What is going on with this article?
@kawasima

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

More than 5 years have passed since last update.

JALパスワード運用

現在のパスワードを教えてくれるからといって、「平文で保存してる!くぁ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対応されるという噂があります…)

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

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

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

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

125
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
kawasima
Clojure関連のことをブログがわりに書き綴ります。 ※ここでの発言はシステムエンジニアを代表するものであって、所属する組織は二の次です。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
125
Help us understand the problem. What is going on with this article?