パスワード・セキュリティ:或る対策の歴史に学ぶ

Takayuki Kawamoto

1st appeared: 2016-03-14 11:08:37.

パスワードを使った認証方式の歴史は、もちろんパスワードのライフサイクルに関するルールつまりはポリシーの歴史でもあります。ここ数年来、国内でもパスワードのポリシーや、認証方式としてのパスワードに代わると宣伝されている生体認証など、パスワードに関する話題は尽きませんが、その殆どは体系立った観点なり基礎的な知識を無視した素人談義の域を出ていないと言えます。そこで、当サイトでは情報セキュリティ・マネジメントやプライバシーに関する古典的な業績を紹介しつつ、別のページで公開する予定の体系立った論説に寄与する材料とします。特に、公的な記録や学術雑誌に掲載される論説は簡単にリソースとして失われたりはしませんが、オンラインで公開されるブログ記事やウェブページの論説は、ありていに言えば当人の気分次第でどうにでもなる刹那的なリソースなので、単にリンクするだけでは後から読む人がアクセスできなくなる恐れがあります。このため、当サイトのページは元の論説の著作権を侵害しない範囲で積極的に重要と思われる箇所を翻訳し、ハイパーリンク(この言い方も今となっては古めかしい響きがありますが)先のリソースが消失しても大意は当サイトのページだけで理解していただける資料集として制作するつもりです。(なお、この一節はサイトの運営方針にも関わるため、別途「当サイトの運営方針及び想定問答」でも同様の趣旨を述べます。)

ここで取り上げるのは、ロバート・モリス(Robert Morris)とケン・トンプソン(Ken Thompson)が Communications of the ACM, Vol.22, No.11 (November 1979), pp.594-597 に発表した、“Password Security: A Case History” という論説です。1979年に書かれた論説ですが、いまだに 1979 年のレベルのパスワード・セキュリティにすら達していない実装が多くのウェブアプリケーションには蔓延っているため、まだ意義を失っているとは言えません。なお、先にも述べましたが、当サイトでは他の方による論説やレクチャーをご紹介していきますが、著作権法で許される範囲で引用したり、私が読んで理解した限りでの要約を述べて、私なりの論評を加えることが趣旨なので、私の要約が正しい理解にもとづいているかどうかは、ご自身で元の文章を参照して検証してください。

序論

まず、或る一台のコンピュータへ複数のユーザがリモートでログインし、コンピュータのリソースである処理時間を共有する(time-sharing)というシステムを想定します。これは現在でも Windows Storage Server のファイルサーバや Linux のウェブサーバなど、非常に多くの「サーバ」と呼ばれるホストコンピュータで利用されているリソース管理方式です。或るウェブサーバにおいて、サーバのシステム管理者(root ユーザ、あるいはスーパーユーザ)が利用者 A のアカウントを設定すると、スーパーユーザがログインした状態で利用者 A が自分のパソコンからファイルをウェブサーバへ FTP でアップロードしているとき、両者は同じサーバの処理時間をそれぞれ必要に応じて割り振られて使っていることになります。このとき、「スーパーユーザ」というのは、そのアカウントを使っている人物である必要はなく、root の権限で cron から自動的に動作している何らかのプログラムであっても構いません。このようなシステムを安全にするため、我々はシステムを攻撃する新しい手法を考え出したり、そういう攻撃に対抗する新しい手法を考え出すという競争を繰り返していく必要があります。これはちょうど、頑強な装甲を作る製造業者と、頑強な装甲を打ち抜く弾丸を作る製造業者の競争みたいなものです。このようなわけで、セキュリティ対策の設計を理解するには、そこで想定されている攻撃が何であるかを理解することが求められます。

パスワード・セキュリティには、利便性を損なわずに、許可された者のアクセスを認めつつ、許可されていない者のアクセスを拒否することが求められます。この論説では、その次に、パスワード・システムはひとたびログインしたユーザが許可されていないことをコンピュータ内でできないように制御しなくてはならないと書いています。これは、現在では「認可(authorization)」と呼ばれるポリシーを実装して制御する仕組みの話であり、正当性を保証されたアカウントの利用者であるという identity を「認証(authentication)」する仕組みの話とは区別されています。したがって、ひとまず以降の紹介や批評では、モリスとトンプソンが認可(あるいはその実装である「アクセス制御(access control)」)の実行フェイズについて言及しているところは除外します。コンピュータ・システムにおいてユーザが何かを実行する権限の認可を定義している設定内容や、それによってログインしたユーザのリソースへのアクセスを制御する機能は、パスワードを使う認証のシステムによって保護するものではなく、それらは分離して実装した方が安全であるというのが現代の考え方だからです。

パスワード・セキュリティに対する攻撃はどんどん洗練されていますし、とりわけリモート・アクセスという手法には特有の脆弱性があります。それに対抗して、パスワードを暗号化する手法も数学的に高度なものとなってきています。しかし、理論的な可能性は幾らでも追及できますが、良いセキュリティ対策というものは、意図的な攻撃だけではなく、何かの事故でアクセス情報が公開されてしまっているとか、退職した人のアクセス情報が残ったままになっているといった理由で、安易にシステムへアクセスできてしまうような、現実に起き得るリスクを考慮していなければなりません。

冒頭に戻る

プロローグ

初期の UNIX システムでは、一個のパスワードファイルが全てのユーザの生のパスワード文字列を格納していたため、それの読み書きには厳重な制約がありました。しかし、厳重に保護されていても、そうした手法には幾つかの理由で問題があります。

パスワードファイルを一時的にでも編集できるなら、ファイルを編集しているそのときに、ファイルは保護されていない状態となります。そして、そのファイルを正当なユーザがコピーできてしまうといった脆弱性があります。また、モリスが遭遇した事例では、システム管理者がログインして全てのユーザに通知するようなメッセージを入力していた時に、別のシステム管理者がパスワードファイルを編集していたら、ソフトウェアの設計ミスによって、両者の扱っていたデータが置き換えられてしまい、全てのユーザに対してパスワードファイルの中身が通知されてしまったと言います。更に、仮にそれらの脆弱性に対処したとしても、システム全体を磁気テープにバックアップしている場合、その中にはパスワードファイルも含まれているため、システムにアクセスできなくても磁気テープを扱える人ならパスワードファイルのデータを取り出せてしまうという問題も考えられます。それから、アクセス可能なユーザを頻繁に追加したり削除しているようなプログラムには、パスワードファイルへのアクセスに特別な権限が必要とされておらず、プログラムごとに生成している数多くのファイルにパスワードファイルの内容(パスワードはユーザ情報の一つです)が個々に転記されたり、あるいはパスワードファイルの内容がごっそり移されてしまったりしていたそうです。

冒頭に戻る

第一のスキーム

まず、明らかに対策となりうるのは、パスワードを暗号化することです。そして、現在でもウェブアプリケーションの開発で導入されているように、ユーザが入力した文字列を暗号化して、既に暗号化されている文字列と比較すればいいわけです。このような処置は 1968 年には既に発表されていたものです。このようなシステムを開発すれば、パスワードを暗号化してあるパスワードファイルや、入力された文字列を使ってパスワードを検証するプログラムですら、誰にアクセスされても問題なくなります(もちろん、プログラムが改竄されたら話は別なので、モリスらの論評は単純すぎると思いますが)。すると次に考えるべきことは、どのように暗号化すればパスワードが解読されにくくなるかということになります。当時の標準的な暗号化アルゴリズムの多くは、解読がたやすいものでした。当時の暗号化アルゴリズムは、第二次世界大戦においてアメリカ軍が採用していた M-209 という暗号機(M-209 はスウェーデンのハーゲリン社がアメリカ軍向けに製造したため、“Hagelin M-209” とも呼ばれました。なお、“M-209” は陸軍での呼称らしく、アメリカ海軍では “CSP-1500” と呼んだようです)をシミュレートしたものでしたが、これは鍵があるとメッセージを簡単に復号できてしまうのでした。しかし、メッセージと暗号化された文字列だけでは鍵を解読するのが難しかったため、当時はパスワードは暗号化されずに一つの文字列が鍵として暗号化され、その結果がパスワードファイルに書き込まれていました。

冒頭に戻る

第一のスキームに対する攻撃

ここで、攻撃者がパスワードを暗号化するプログラムとパスワードファイルを持っているとしましょう。それから相当な解析能力の手段も使えるとします。現在では、AWS などのクラウド・コンピューティング・サービスを使っていると仮定してもよいですね。このパスワード・システムを攻撃する方法として誰でも考え付くのは、パスワードファイルを復号するアルゴリズムを発見しようとすることでしょう。しかし、仮にそういうアルゴリズムを見つけられたとしても、それを使った解析そのものには多くの時間がかかるでしょう。次に、一つのパスワードを総当たり攻撃(全数探索、あるいはブルートフォースとも言います)するとしましょう。多くの人は、人である限りは短くて単純な覚えやすいパスワードを選びがちなところがあるので、もしそのようなパスワードを使われていると、解析は非常に簡単になります。総当たり攻撃の要点は、選んだパスワードを暗号化してみて、パスワードファイルの内容と比べるのに一定の時間がかかるということです。彼らが論文を書いた当時、PDP-11/70 という DEC 社が製造していたコンピュータ(メモリは 4MB「も」あった)の想定では、一回の攻撃を試すのにかかる時間は 1.25 ミリ秒とされています。もしパスワードが長さ n の英小文字だけで作られていると仮定すれば、パスワードの組み合わせの数は 26n です。これが印刷可能な文字にまで拡張されると、最大で 95n にまで増えるでしょう。こうした想定から、全ての文字の組み合わせを試してみる総当たり攻撃の所要時間が割り出せます。(なお、[...] で括ってある所要時間は、2012 年に DIT 社が公表した ZIP のパスワードを解析する所要時間です。暗号化の処理が違うので単純に比較はできませんが、参考として出しておきます。)

n 26(英小文字) 36(英小文字+数字) 62(英数文字全体) 95(印刷可能文字) 128(ASCII文字全体)
1 30ミリ秒 40ミリ秒 80ミリ秒 120ミリ秒 160ミリ秒
2 800ミリ秒 2秒 5秒 11秒 20秒
3 22秒 58秒 5分 17分 44分
4 10分 35分 5時間 28時間 93時間
5 4時間 21時間 318時間 112日 500日
6 107時間
[1秒以下]
760時間 2.2年
[13秒]
29年
[2分24秒,93文字]
174年

これを見ると、PDP-11 を利用できる人であれば、英小文字だけでパスワードを作っているユーザについては、何週間か週末にアクセスして全てのパターンを試してみるだけで、6 桁のパスワードを設定していても相当な数の解析が成功するでしょう。

他には、あらかじめ単語や名前のリストを用意しておいて、それを試してみるという手法が考えられます。発売されている大型辞書には、250,000 くらいの単語が収録されています。もしパスワードが辞書に載っているような単語で登録されていれば、この辞書を使って総当たり攻撃すると約 5 分でパスワードが割り出せます。パスワードファイル全体について同じことを試せば、かなりの数のパスワードが短時間で割り出せるはずです。また、こうした攻撃では単語に次のような変形を加えて辞書を拡張している場合もあります。

試しに彼らが何の制約もかけないで好きなパスワードを選んでもらったところ、その結果は攻撃者の望むとおり散々なものだったようです。彼らが集めた 3,289 のパスワードの統計は、以下のような結果でした。

冒頭に戻る

第一のスキームを改善する

1. 暗号化の速度を落とす

先のスキームで使っていた暗号化のアルゴリズムは、あまりにも速過ぎるのです。DES 暗号化のアルゴリズム(1977 年に規格化されたアメリカの古い暗号規格。現在は AES という規格で置き換えられています)を使うと、暗号化の処理が非常に遅くなります。DES では、ユーザのパスワード文字列から作った固定長の入力を使って暗号化の処理を一定の所要時間に揃え、それに加えて 64 ビット長の鍵も使います(実際には 8 ビット分をパリティチェックに使うため、実際の長さは 56 ビット長)。なお、モリスとトンプソンの論文では反復繰り返し(iteration)を 25 回としていますが、DES の規格である FIPS Publication 46-3 (1999-10-25, PDF file) では 16 回の「ラウンド(round)」として定義しています。

2. 推測困難なパスワード

次の対策は、ユーザに推測困難なパスワードを設定するよう強制することです。もしユーザが 6 文字以内で、英小文字だけとか、英大文字だけのパスワード(“pass” とか “PASS”)を設定したり、あるいはもっと多くの文字種を許容する場合でも 5 文字以下でパスワードを設定しようとすると、もっと長いパスワードを設定するように求めるプログラムを使うわけです。これによって、総当たり攻撃のリスクは低減できるでしょう。しかし、これだけでは、例えばユーザが伴侶の名前をパスワードに設定することまでは止めさせられません。

3. ソルトの利用

以上の対策だけだと、巨大なリストを予め持っている攻撃者は、僅か乍ら幾つかのパスワードを上手く解析できてしまいます。そこで、パスワードの設定内容が入力されたら、パスワードを扱うプログラムは入力された時刻から求めた 12 ビットのランダムな数字(ソルト(“salt”)と言います)をユーザが設定したパスワード文字列に繋げて、パスワード文字列+12 ビットの数字という合成された文字列の全体を暗号化して(モリスとトンプソンは “encrypted” と書いていますが、現代ではハッシュ化することが多いので奇妙に感じる方がおられるかもしれません。彼らの論文では DES で処理する想定なので、ここでは暗号化のままとしておきます)、ソルトと、暗号化処理を経た文字列だけをパスワードファイルへ記録します。

ユーザがログインするときは、パスワードファイルからユーザに対応するソルトを取り出して、入力されたパスワードと繋げて再び同じ方法で暗号化します。このやり方だと、攻撃者が予め巨大なリストを持っていても、追加される 12 ビットのソルトの分、つまり 4,096 (212) 倍だけ解析に時間を要することとなるため、攻撃は更に難しくなります。なお、この仕組みを導入する結果、仮に同じパスワードが設定されてもソルトを追加した結果のハッシュ値は異なるため、或るハッシュ値だけでは、元のパスワードが同じなのかどうか分からなくなります。

4. DES チップの脅威

DES のチップが発売されており、これを使うと DES の処理は非常に高速になるため、パスワードを解析する場合でも格段に所要時間が短くなります。そのため、DES 暗号化で使う内部テーブル(原文では「E-テーブル」と呼ばれていますが、現在では「Sボックス」と言われます)を用意して、12 ビットのランダムな数字によってテーブルを切り替えれば、攻撃者が商用 DES チップを使っていても解析のコストは非常に高くなります。

5. 些細な点

UNIX システムへログインするには(いまやダイヤルインの話は多くの方には不要だと思うので割愛します)、正当なユーザ名と正しいパスワードを入力しなくてはなりません。このとき、侵入者が不正なユーザ名を入力したときに不正な入力であることを教えるのは、ログイン処理のデザインとしてまずいやり方です。ユーザ名の入力には、それが正当であろうとなかろうと、同じレスポンスを返すべきです。

意図的に遅い暗号化処理が初めて実装された当時は、ユーザ名が正当な場合に限って処理が実行され、それ以外の場合は保存されているパスワードと比較する必要がないので、処理は実行されませんでした。すると、ユーザ名が正当な場合にだけ処理全体は時間がかかり、攻撃者は入力したユーザ名が正当であるかどうかを処理時間の差によって推測できてしまいます。したがって、ユーザ名が正当であってもなくても同じ時間で処理できるように改変されました。(入力値の正否を処理時間から推定する方法は、現在ではサイドチャネル攻撃の一種である「タイミング攻撃」と言われている手法です。)

冒頭に戻る

結論

モリスとトンプソンが原文を書いた当時の UNIX では、そもそもシステムへログインする前の「ダイヤルイン」の時点で、セキュリティコードを入力できるようになっていました。そして、これを定期的に(“periodically”)変更すれば、古いパスワードを使って誰かが不正にシステムへアクセスすることを防げるとされています。

また、セキュリティ対策は不正なアクセスを妨いだらいいというだけのものではなく、成功したアクセスや失敗したアクセスの記録も取らなくてはなりません。例えば、コンピュータ処理施設へやってきていた人が退出した後も数時間にわたって利用した記録があるなら、アクセスの正否を記録して、不正なアクセスが外部からないかどうかを確認して不正なアクセスを遮断するのが良い対策となります。

攻撃者の目的は、特定のシステムの管理者パスワードを盗むことから、あらゆるシステムのパスワードを軒並み奪うことまで色々あります。ここで述べている対策の多くは、特に後者の目的をもつ攻撃者に解析の負荷をかけるものです。しかしモリスとトンプソンの経験では、これらの対策を採ると、前者のタイプの攻撃者についても成功の見込みは低くなると言います。

冒頭に戻る

コメント

モリスとトンプソンの論説は、パスワード文字列を平文のまま保存しないとか、ソルトや特別な暗号化処理を使って脆弱なパスワードやタイミング攻撃に対抗するとか、あるいは UI デザインとしてもエラー表示を工夫するとか、現代でも参考にできる点があります。逆に言うと、この論文から 40 年近くが経過した現代においても、この論文に書かれていて、今では当然の対策として実行されている筈のことができていない自称ものづくり開発者や素人プログラマが、オンラインに膨大なゴミを善意の名のもとに「ウェブアプリケーション」と称して公開しています。無知は、情報や素養の学習機会を提供する意思表示によって対策できますが、それに従わない人たちには情け容赦なく断罪するのが大人やプロの責任でもあります。自らの失敗や他人の指摘から学ぶ意志がない者に、善意だけで他人へ何かを提供する資格などあるわけがありません。したがって、プログラマや IT 技術者を志す人たちには、たとえ 40 年近くも前の論説であっても、一度は目を通すくらいの余裕が求められるはずです。(当サイトの記事を読めと言いたいわけではありません。)

冒頭に戻る


※ 以下の SNS 共有ボタンは JavaScript を使っておらず、ボタンを押すまでは SNS サイトと全く通信しません。

Google+ Twitter Facebook