Webのアプリケーションでは、ユーザ認証を行うことがよくあります。その際に皆様はどのようにパスワードを保管されているでしょうか。
PGP,DESのような暗号ロジックで符号化している場合もあると思います。
しかし処理に時間がかかることもあり、MD5,SHA1のような非可逆符なハッシュ値を求めて保管することも多いと思います。
このように平文ではなく符号化した値で保管するのは、「パスワードは設定した本人しかわからない」ようにするためでしょう。
MD5であっても16進表記で32文字に変換されますので、人間が符号化された後の値から元の平文を推測することは簡単ではありません。
（パスワードは、ユーザが密かに保管しているべきものですから、非可逆な符号化で問題ありません。）
とは言っても、符号化された後の値から元の平文を推測できないわけではありません。「なりすまし」にあう危険が残っていることになります。
そこで「なりすまされない」ように、できる限り元の平文を推測できないようにすることを検討してみたいと思います。
概要
ハッシュ値から平文は推測できてしまう
問題は、ハッシュ値から平文が推測できてしまうことです。
何か工夫をして元の平文を推測できないようにすることはできないのでしょうか。
よく行われる方法としては、saltと呼ばれる秘密の文字列を元の平文に混ぜて、一緒に符号化することです。
この場合元の平文とsaltの混ざった文字列は推測されてしまいますが、元の平文は特定できていません。
またsaltは秘密にされていますので、元の平文を抽出することは非常に困難になると思います。
繰り返すとより推測が困難になる
しかし、まだ時間をかければ推測できると思われます。
そこで、得られたハッシュ値と新しいsaltを混ぜてハッシュ値を取得するとどうなるでしょうか。
先にも示したようにハッシュ値から平文は推測できてしまいますが、推測された平文はハッシュ値にsaltを混ぜたものです。
ここからハッシュ値を抽出することは可能ですが時間がかかります。
さらに得られたハッシュ値と新しいsaltを混ぜてハッシュ値を取得する操作をn回行うと、元の平文を推測するまでの時間が伸びます。
また繰り返す回数が固定されていなとしたら、元の平文を推測するこためにかかる時間は非常に長くなるのではないでしょうか。
時間がかかることがポイント
「時間がかかっても分かっちゃうんでしょ。」と言われそうですが、現在運用されている暗号技術も時間をかければ解読できるのです。ただ、解読にかかる時間が100年とかかかりますので、解読できたころには利用価値が疑われるために安全であるとされています。
要は元の平文が推測されても、推測できた時には意味のない値になっていればよいのです。
オンラインゲーマーよ！6文字パスワードは17秒で破られるでは、10文字のパスワードを解読するのに8年と紹介しています。
グラボ(GPU)の力でMD5を解読では、1秒間に約20億回の解読を試行できることが報告されています。
（いずれも少し古い記事なので、現在ではもっと高速に処理できるようになっていると思います。）
では、MD5のハッシュ値と1文字のsaltを混ぜた値から処理時間を計算するとどうなるでしょうか。
(16文字種 ^ ( 32文字 ＋ 1文字 )) ÷ 33億処理 ÷ 60秒 ÷ 60分 ÷ 24時間 ÷ 365日 ＝ 5.2316524e+22年と、十分時間がかかっています。
さらに、n回繰り返すので、元の平文を推測することは現実的にできないと言えるでしょう。
仕様
要件
MD5,SHA1のような非可逆なハッシュ値を求めるロジックで対応する。
SQL、PHP、Perl etc. の各言語で実装する。
基本設計
-
パラメータ
- 平文
- salt文字列
-
処理フロー
- 前処理として平文とsalt文字列からそれぞれのハッシュ値を取得する
- 平文のハッシュ値から繰り返し回数を取得する
- (以後、繰り返し)
- 平文のハッシュ値からsalt文字列合成位置を取得する
- 平文のハッシュ値から大小文字化方法を取得する
- 平文のハッシュ値を得られた大小文字化方法で大小文字化する
- salt文字列のハッシュ値からsalt文字列開始オフセットを取得する
- salt文字列のハッシュ値からsalt文字列長を取得する
- salt文字列のハッシュ値から大小文字化方法を取得する
- salt文字列のハッシュ値からsalt文字列を取得する
- salt文字列を得られた大小文字化方法で大小文字化する
- 大小文字化された平文のハッシュ値のsalt文字列合成位置にsalt文字列を挿入する
- 合成された値のハッシュ値を取得する
- (繰り返し回数分処理した場合は得られたハッシュ値をもって処理を終了する)
- 得られたハッシュ値を平文のハッシュ値とする
- salt文字列のハッシュ値を取得して新たなsalt文字列のハッシュ値とする
実装
PHP
まずは手元の開発環境を利用するとソースレベルデバックが可能なPHPを使って、MD5を難読化してみたいと思います。
function smd5($plain = '', $salt = '') {
// Get the hash value
$encoded = md5($plain);
$salt = md5($salt);
// Get the number of repetitions
$repeat_count = hexdec(substr($encoded, 0, 1)) + hexdec(substr($encoded, 1, 1)) + 2;
for ($idx = 0; $repeat_count > $idx; $idx++) {
// Get the insertion position of the salt string
$insert_offset = hexdec(substr($encoded, 2, 1));
// Case of
$encoded = (hexdec(substr($encoded, 3, 1)) % 2 != 0) ? strtoupper($encoded) : strtolower($encoded);
// Get the salt string start offset
$salt_offset = hexdec(substr($salt, 0, 1));
// Get the salt string length
$salt_length = hexdec(substr($salt, 1, 1)) + 1;
// Get the Case method
if (hexdec(substr($salt, 2, 1)) % 2 != 0)
$is_upper_salt = true;
else
$is_upper_salt = false;
// Get the salt string
$salt = substr($salt, $salt_offset, $salt_length);
// Case of
$salt = $is_upper_salt ? strtoupper($salt) : strtolower($salt);
// Insert the salt string to salt string synthetic position
$encoded = ($insert_offset ? substr($encoded, 0, $insert_offset) : '') . $salt . ($insert_offset ? substr($encoded, $insert_offset) : $encoded);
// Get the hash value
$result = md5($encoded);
// Set the new hash value
$encoded = $result;
$salt = md5($salt);
}
return $result;
}
ハッシュ値を取る関数は、md5()を使っています。
PHPのmd5()関数は32文字の16進数文字列が返ってきますので、オフセット値や長さ、回数といった数値は、ハッシュ値の指定された場所から取得しています。具体的には、hexdec(substr(ハッシュ値, オフセット, 1))のようにしています。
MySQL
PHPのソースを参考に、MySQLのストアドファンクションを作成したいと思います。
DELIMITER //
DROP FUNCTION IF EXISTS smd5//
CREATE FUNCTION smd5 (plain TEXT, salt TEXT)
RETURNS TEXT DETERMINISTIC
BEGIN
DECLARE encoded VARCHAR(48);
DECLARE encoded_salt VARCHAR(32);
DECLARE insert_offset INT;
DECLARE is_upper_salt INT;
DECLARE salt_offset INT;
DECLARE salt_length INT;
DECLARE repeat_count INT;
DECLARE result VARCHAR(32);
DECLARE idx INT;
-- 平文のハッシュを取得
IF plain IS NULL THEN
SET plain = '';
END IF;
SET encoded = MD5(plain);
IF salt IS NULL THEN
SET salt = '';
END IF;
SET encoded_salt = MD5(salt);
-- 各変換設定値を取得する
SET repeat_count = CONV(SUBSTRING(encoded, 1, 1), 16, 10) + CONV(SUBSTRING(encoded, 2, 1), 16, 10) + 2;
SET idx = 0;
WHILE repeat_count > idx DO
-- salt文字列挿入位置を取得する
SET insert_offset = CONV(SUBSTRING(encoded, 3, 1), 16, 10);
-- 大小文字化
IF CONV(SUBSTRING(encoded, 4, 1), 16, 10) % 2 != 0 THEN
SET encoded = UPPER(encoded);
ELSE
SET encoded = LOWER(encoded);
END IF;
-- salt文字列抽出条件を取得する
SET salt_offset = CONV(SUBSTRING(encoded_salt, 1, 1), 16, 10) + 1;
SET salt_length = CONV(SUBSTRING(encoded_salt, 2, 1), 16, 10) + 1;
-- salt文字列の大小文字化方法を取得する
IF CONV(SUBSTRING(encoded_salt, 3, 1), 16, 10) % 2 != 0 THEN
SET is_upper_salt = 1;
ELSE
SET is_upper_salt = 0;
END IF;
-- salt文字列を抽出する
SET encoded_salt = SUBSTRING(encoded_salt, salt_offset, salt_length);
-- 大小文字化
IF is_upper_salt = 0 THEN
SET encoded_salt = LOWER(encoded_salt);
ELSE
SET encoded_salt = UPPER(encoded_salt);
END IF;
-- salt文字列を挿入する
IF insert_offset = 0 THEN
SET encoded = CONCAT(encoded_salt, encoded);
ELSE
SET encoded = CONCAT(SUBSTRING(encoded, 1, insert_offset), encoded_salt, SUBSTRING(encoded, insert_offset + 1));
END IF;
-- ハッシュを取得する
SET result = MD5(encoded);
-- ハッシュ値をセットする
SET encoded = result;
SET encoded_salt = MD5(encoded_salt);
-- カウンタをインクリメント
SET idx = idx + 1;
END WHILE;
RETURN result;
END//
DELIMITER ;
このような関数をクラスにまとめていきます。
これらのソースはGPLライセンスでGitHubにアップロードしております。よろしければご覧ください。