Basic 認証は本当に遅いのか?

Posted by
ぴろり
Posted at
2012/03/10 22:24
Trackbacks
関連記事 (0)
Post Comment
コメントできます
Category
開発メモ カテゴリ
カバーイメージ

 HTTP(S) 通信で簡易にパスワード セキュリティを実現できる Basic 認証。ちょろっと検索したところでは、セキュリティの問題に加えてパフォーマンスについても問題があるように書かれています。

 .htpasswd ファイルのような、テキストファイルによるユーザー管理は最も手軽ですが、パスワードファイルを上から下へと線形で読むために、実際のところ効率はよくありません。ユーザ数が数 100 単位に増えてきた時に、サーバのパフォーマンスは低下します。

ユーザー認証のパフォーマンス問題 - ミケネコの htaccess リファレンス

 正確に言えば、テキスト ファイルでパスワードを管理する Basic 認証は本当に遅いのか?ということになります。数百ユーザのアカウントを、テキスト ファイル ベースで管理するのもアレだと思いますが、んじゃ、実際のところどれくらいパフォーマンスに影響するのよ? ってところを調べてみました。

この記事を Delicious に追加する   このエントリーをはてなブックマークに追加  

実験方法

  • Web サーバには MacBook の Web 共有(Apache 2)を使用
    • MacBook のスペック → Intel Core 2 Duo@2.26GHz, DDR3-1066 2GB
  • 実験用ディレクトリに .htaccess を設置して Basic 認証を設定する
  • アカウントは htpasswd コマンドで生成できるテキスト ファイルに保存する
  • 同一の MacBook のターミナルから ab コマンドを使用してリクエストを投げる
    • ab コマンドには -A オプションを指定して Basic 認証を行わせる
    • リクエスト数は適当に 100 回くらい
    • 並列度は 1
  • Basic 認証で使用するパスワード ファイルに登録されているアカウント数を変化させる
    • 1 行目に目的のユーザ アカウントが登録されており、残りの (n-1) 行にはダミーのアカウントが登録されている場合
    • (n-1) 行までダミーのアカウントが登録されており、最終行に目的のユーザ アカウントが登録されている場合
    • n は、1 〜 1,000,000 とする
  • Basic 認証で使用するパスワードのハッシュ方式を変化させる
    • crypt ハッシュ方式
    • MD5 ハッシュ方式

 面倒だったのでサーバもクライアントも同じマシンでサクサクッと済ませていますが、もっと正確なデータが欲しいんじゃーという方は自分でなんとかしてくださいませ。

実験結果

 ab コマンドを使用して得られた秒間あたりのリクエスト数(#/sec)は以下の通りとなりました。

Basic 認証は本当に遅いのか?

 ただ、このままでは数値の範囲が大きすぎるので、アカウント数(User#)と秒間リクエスト数(#/sec)について常用対数をとり、グラフ化したものが次になります(Fig.1 )。常用対数なので、数値が 1 異なると、実際の数値は 10 倍変化します。


Fig.1 graph アカウント数(User#)に対する秒間リクエスト数(#/sec)の変化

 グラフを見ると、パフォーマンスの変化パターンが二通りあることが判ります。まず、パスワードのハッシュ方式に関わらず、パスワード ファイルの 1 行目に目的のアカウントがある場合(青:MD5, First と 黄:crypt, First)には、パスワード ファイルに登録されているアカウント数に関わらず、動作パフォーマンスは変化しないということです。おそらく、パスワード ファイルの先頭から一行ずつ走査して、目的のアカウントが見つかった時点で残りの行を無視していると予想できます。アカウント数が多くなると、パスワード ファイルのサイズがそれに伴って大きくなるので*1、パスワード ファイルを読み込むための時間がより長くなりますが、しかし、多くの OS ではディスク キャッシュが機能するため、パスワード ファイルへのアクセスは実質メモリ上での操作となり、それほど大きな問題にはならないと思われます。

 次に、パスワード ファイルの末尾に目的のアカウントがある場合(赤:MD5, Last と 緑:crypt, Last)には、アカウント数の増加に対してパフォーマンスが比例的*2に悪化することがわかります。ただし、アカウント数が 1,000 (= 103) 程度までの変化は穏やかで、劇的に重くなる、というほどではありません。しかし、10,000 (= 104) あたりから、アカウント数の増加に伴ってパフォーマンスがほぼ直線的に低下することが見てとれます。しかも、アカウント数が 10 倍になると、パフォーマンスもきっちり 10 倍に悪化しています。
 アカウント数の増加と、パフォーマンスの悪化が全領域で比例しない理由として、アカウント数が少ない領域では、パスワード ファイルを走査する以外のアカウント数の多少に影響されないサーバ処理——例えば、ネットワーク コネクションの確立やHTTP プロトコルの解析、コンテンツの読み込みなど——が占める割合が「相対的に」高いために表面化しにくいためと推測されます。反対に、アカウント数が増えてくると、先のサーバ処理に掛かる時間は同じでも、各アカウント毎に認証の正否をチェックするため、アカウント数の増加によるパフォーマンス低下が支配的になってくるわけです。

 パスワードのハッシュ方式について、パスワード ファイル中のアカウントの記述された順番や、ユーザ数の増加に関わらず、一定して crypt ハッシュ方式の方が、MD5 ハッシュ方式よりも良いパフォーマンスを出しています。Apache の Basic 認証に用いられる MD5 ハッシュは、計算の過程で本来の MD5 ハッシュ計算を用いていますが、確かその計算+α を 100 回だか何だかループさせて最終的なハッシュ値を得る変な方法(失念)を用いています。ですので、単純な crypt よりも要求される CPU リソースが多く、それがパフォーマンスの差に出ているように思えます。
 しかし、crypt ハッシュ方式の方が良いパフォーマンスを出せると言っても、アカウント数の増加に対しては、どちらも確実にパフォーマンスが低下することには変わりありません。

 10,000 (= 104) ユーザを、パスワード ファイルで認証を行った場合のパフォーマンス低下はほぼ 10 倍にもなりますので、このあたりがテキスト ファイルで認証できる限界でしょうか。しかし、1,000 (= 103) アカウント程度であれば、ちょっと遅いかな? 程度で済みそうな気もします。
 このことを前向きに考えると、もし、アカウント認証システムが必要になった時、想定されるユーザ数が 1,000 人以下の規模であれば、テキスト ファイルでパスワードを管理する Basic 認証において、パフォーマンス低下を考える必要はあまりない、と言えるでしょう。
 これは小規模なコマース サイトでも言えると思います。高いコストを払って、アカウント認証システムを導入する替わりに、テキスト ファイル ベースの Basic 認証でも十分使えますよ、と。ただ、その場合には、パフォーマンス低下の問題以上に、セキュリティやアカウント認証ダイアログの見た目などの別の問題の方が大きくて、やっぱり Basic 認証は採用されないんですけどね。

まとめ?

 テキスト ファイルでパスワードを管理をする Basic 認証は;

  • アカウント数が、数百程度ならパフォーマンス低下を気にしなくてもよい
  • アカウント数が、1,000 を超えたあたりからパフォーマンス低下が見え始める
  • アカウント数が、10,000 を超えるとかなりキツい、というか無理
  • 将来的にマシン パワーがガンガン上昇すれば、その限界も上昇するかもしれない
  • MD5 ハッシュ方式よりも、crypt ハッシュ方式の方がちょっと軽い
この記事を Delicious に追加する   このエントリーをはてなブックマークに追加  

  1. *1 MD5 ハッシュ方式では 1,000,000 ユーザで 40MB 程度、crypt ハッシュ方式では 20MB 程度
  2. *2 グラフは両軸とも対数目盛りなので、指数関数的ではなくて比例的になる


関連記事/トラックバック

関連記事/トラックバックはまだありません

この記事にトラックバックを送るには?

コメントを投稿する

 
 (必須, 匿名可, 公開, トリップが使えます)
 (必須, 匿名可, 非公開, Gravatar に対応しています)
 (必須)
スパム コメント防止のため「投稿確認」欄に ランダムな数字 CAPTCHAについて を入力してから送信してください。お手数ですがご協力のほど宜しくお願いいたします。