• パスワードクラック概論(1) (2004/7/11 12:41) （>>この記事のみを表示）
• パスワードクラック概論(2) (2004/7/11 14:33) （>>この記事のみを表示）
• パスワードクラック概論(3) (2004/7/11 14:39) （>>この記事のみを表示）
• パスワードクラック概論(4) (2004/7/11 14:46) （>>この記事のみを表示）
• パスワードクラック概論(5) (2004/7/11 14:51) （>>この記事のみを表示）

<<トップカテゴリー「NetChildren」に戻る

「ターゲットのIDと適当なパスワードでログインを試みる」という「パスワードクラック」なら結構多くの人が一度は試したことがあるでしょう。「*****というツールを使えば毎秒数百万回の試行が可能」といった文章を読んだことがある人もいるでしょう。「パスワードクラック」という世界の概要について。

□1

例えばある「会員制サイト」にアクセスする。ログイン用formが表示される。ターゲットのIDを入力し、適当なパスワードを打ち込んで「ログイン」を押す。偶然パスワードが当たっていれば、「パスワードクラック」が成功したことになる。「ログイン」を押してから「ログイン成功」「失敗」が表示されるまでの時間を1秒としよう。

□2

例えばFFFTPを使ってターゲットが使用しているホスティングサーバーにアクセスする。ターゲットのアカウントと適当なパスワードを打ち込みログインを試みる。偶然パスワードが当たっていれば、「パスワードクラック」が成功したことになる。一度失敗してから再びパスワード入力を求められるまでの時間を0.5秒としよう。

---

さて、通常パスワードとは「半角英数字8文字」です。パスワードに使用できる文字は英小文字26+英大文字26+数字10で62個。最初の一文字は英字だけなので52個。故に8文字のパスワードは52*62^7通り(a^bはaのb乗)。
上記のような方法で「クラック」できるパスワードはJOE(パスワード=ID)や誕生日やエトセトラだけです。よく「辞書に出てくるような英単語をパスワードに使うのは危険」とか言いますけど、全ての「クラッカー」が上記の方法を用いているならばアレはオーバーですよね。だって例えば「addicted」をパスワードにしている人がいたとしても、「addicted」と同じくらいの知名度な英単語なんて数万はありますし。逆に言えば「addicted」程度の簡単なパスワードですら、上記の方法で破ることは困難でしょう。

---

ここで我々は「パスワード認証とはどのようなシステムなのか」という話に目を向けなくてはいけなくなる。例えば「ID制サイトにおけるパスワードログイン」「FTPサーバーに対するパスワードログイン」というモノを「IDとパスワードを打って結果を待つ」ではなく「その時サーバー内部で何が行われているのか考える」コトによって破らなくてはいけない、と。

単純に考えてみましょう。原始的な「パスワード認証」とは以下です。

1. IDとパスワードを入力させる
2. 入力されたID・パスワードをサーバー内部のデータファイルと照合する
3. 一致ならば「ログイン成功」・不一致ならば「ログイン失敗」

なるほど。つまり「パスワードクラック」のためには「サーバー内部にあるデータファイル」が必要になる。「サーバー内部にあるデータファイル」ってのは例えば以下のようなモノなのでしょうね。
もし「サーバー内部のデータファイル」を何らかの方法で抜くことができたなら、全てのパスワードを・・・「ランダムな英数字」だろうと「誕生日」だろうと同じように・・・クラックすることが可能になる。サーバーサイドから見れば「サーバー内部のデータファイルを抜かれる」は「全てのアカウントを破られる」と同値。
抜くことが出来ないならば「パスワード=誕生日」をクラックするには最高366回の試行が必要になるし「パスワード=英単語」をクラックするには数千数万回の試行が必要になる。「パスワード=誕生日」ですら決して「簡単に破れるパスワード」ではないし「パスワード=英単語」を破ることなんて現実的に不可能だ。

---

これが、原始的な「パスワード認証」「パスワードクラック」の世界です。サーバー内の何処かに「正しいパスワード」があり、認証とは「『打ち込まれたパスワード』が『正しいパスワード』と一致するか否か」である、と。

前回書いたように、「サーバー内のパスワードデータファイル」を抜かずに「パスワードクラック」を行うことは(JOE等一部の例外を除いて)現実的に不可能です。「パスワードクラッカー」が最初にすべきことは「サーバー内の『パスワードデータファイル』を抜く」です。これは前提としておきましょう。
では、パスワードクラック概論(1)で書いたような「パスワード認証」の問題点(脆弱性)は何か。「正しいパスワード」を平文で(=暗号化せずに)サーバー内に保存しているコトです。だから「パスワードデータファイルを抜かれる」が即「全てのアカウントを破られる」に繋がる。
ならば。「正しいパスワード」を暗号化して保存しておけば良い。

ここで「暗号」というモノについて軽く触れておきます。
小学生くらいの頃に親しんだ「暗号」ってのは以下のようなモノですよね。
PCの世界において、「暗号」とは「関数」と同じです。上記や「タヌキで『た』抜き」みたいな「暗号」観から抜け出しましょう。

---

BASICとかでもいいのですが、何らかのプログラム言語を使ったことがある人ならば次のような話に頭を悩ませたことが一度あると思います。
つまり、「10」「5」を数字と見れば10+5は「15」で、文字と見れば10+5は「105」。なるほど。では「to+kix」は？「tokix」？それは「to」「kix」を文字として見た場合ですね。「to」「kix」を数字と見たら？

---

そう、PCにとって文字とはn進数の数字にすぎない。パスワードの場合だったら

パスワードに使用できる文字は英小文字26+英大文字26+数字10で62個

なので62進数(という説明はかなり乱暴ですが今回はそういうことで)。
(我々10進数に慣れた人間には「文字列」としか思えない)パスワードを「数字」として見ることができれば、あらゆる計算・・・例えば足し算なりかけ算なり・・・が可能になる。そうして行うことができる「関数への代入」が「暗号化」であり、「解読」とは「逆関数への代入」です。

※参考: コミレク内「関数」
・・・いや、別に読まなくても次を読めば多分意味分かると思いますけど一応。

「正しいパスワード」を暗号化してサーバー内に保存しておけば、「『パスワードデータファイルを抜かれる』が即『全てのアカウントを破られる』に繋がる」ことはなくなる。

1. IDとパスワードを入力させる
2. サーバー内部のデータファイルを参照し「暗号化された正しいパスワード」を解読し「正しいパスワード」を得る
3. 「入力されたパスワード」と「(2で解読した)正しいパスワード」が一致ならば「ログイン成功」・不一致ならば「ログイン失敗」

---

しかしそれでも、「パスワードデータファイル」を手に入れたクラッカーには希望がある。「関数」の正体が分かれば「逆関数」を求めることができ、パスワードデータファイル内の「暗号化された正しいパスワード」から元の「正しいパスワード」を知ることができる、という希望。「暗号化された正しいパスワードデータ」を手に入れた上で、その希望を「パスワードクラック」に結びつけるための方法は大まかに二種類。

□1: 関数なり逆関数なりのルーチンを手に入れる

「パスワード設定プログラム」には「関数」が、「パスワード認証プログラム」には「逆関数」が記述されているはずです。サーバー内部で動作しているプログラムのソースを入手することができれば「パスワードクラック」が可能になる。

□2: 「入力」「出力」から関数を推測する

このように、様々な「パスワード」を設定して「暗号化されたパスワードデータファイル」を抜けば良い。そうすれば「暗号(=関数)」の正体を推測することができ、「ターゲットyamadaのパスワードをある関数に代入した結果」である「JUhbgfd4E」の「解読(=逆関数への代入)」を行うことができるかもしれない。f(1)=8でf(2)=11でf(3)=14ならば「f(x)=3x+5」でありf(a)=35の時a=10ではないか？ということです。

---

「パスワードデータの暗号化」の問題点(=脆弱性)とは、「全てのアカウントに関するパスワードが同じ関数に代入されている」ということです。だから上記test1・test2・・・の「パスワード」と「暗号化されたパスワード」を解析されることで「関数」の正体を推測されてしまう。

• 関数への入力: 自分が設定したパスワード
• 関数からの出力: パスワードデータファイル内の文字列

「入力」「出力」が手に入れば「関数」の推測が可能になる、と。

---

まずもって「パスワードデータファイル」を抜かれなければ「パスワードクラック」に脅える必要はあまりない(JOEとかは例外ですけど)。仮に抜かれたとしても、その「データ」が「生のパスワード」ではなく「暗号化されたパスワード」であれば一応安全である。が、関数(逆関数)を求められたら全てのアカウントを破られる。
これが、「暗号化」という世界です。

「平文で正しいパスワードを保存すると『パスワードデータファイルを抜かれる』が即『全てのアカウントを破られる』に繋がってしまう、そこで正しいパスワードを暗号化した上で保存しておく」。自然な発想ですね。今回から少しずつ話が不自然になっていきます(例えばコンテンツ中の「暗号」という言葉が、日常生活で用いる「暗号」という言葉から離れていきます)。

---

さて、何故パスワードに対する暗号化処理を行っているにも関わらず「パスワードクラック」の可能性を完全に塞ぐことができないのか。その主な原因は
ということです。
「全てのアカウントに関するパスワードが同じ関数に代入されている」からこそ、(パスワードデータファイルを抜く方法を発見した)クラッカーには様々な「入力(自分が設定したパスワード)」と「それに対する出力(パスワードデータファイル内の文字列)」から「関数」の実体を推測することが可能になる。
仮に、それぞれのアカウントに関するパスワードが全て別の関数に代入されていたら。「パスワードデータファイル」を抜かれたとしてもどうってことはありません。

---

勿論そんなことは現実的に不可能です(アカウントが数個なら可能かもしれませんが)。しかしそれを簡易的に実現する方法はある。「関数」に対する入力を複数にすれば良い。
このように、ある文字列(この場合はパスワード)に対する暗号化を行うために用いられるそれ以外の文字列(例1では「アカウント」で例2では「ユーザーが決めた秘密の数字」)を「鍵」と言います。

例えばある関数があったとします。
この式を「x=〜」の形に直すことを「関数を解く」と呼んでいましたよね。
さて、単純な1次関数ならば解くことは可能ですし簡単です。コレが2次関数になってくると・・・例の「解の公式」という・・・ややこしい計算が必要になってくる。3次関数・4次関数になっても(高校数学では扱われませんが3次関数・4次関数にも「解の公式」は存在します、異常にややこしいですけど)一応解くことは可能です。しかし、この世には「解けない関数」も存在する。「計算がややこしい」とか「解くのが困難」ではなく「解けない」関数。
そう、関数を与えられた我々は必ず「関数への代入」を行うことができる。しかし「関数を解く」ことは「必ずできる」訳ではない。こういう性質を持った関数は「一方向関数」と呼ばれます。y=f(x)だったとして、「xからyを求めることもyからxを求めること(=逆関数を求めること)もできる」というのが「双方向」、「xからyを求めることはできてもyからxを求めることはできない」というのが「一方向」。

---

パスワードクラック概論(2)やパスワードクラック概論(3)の「パスワード認証」の脆弱性とは

y=3x+a

---

y:パスワードデータファイルに保存する文字列
x:(生の)パスワード
a:アカウント

---

勿論、「鍵(=暗号化関数に対するパスワード以外の入力)がアカウントである」というコトがバレてしまえばパスワードクラック概論(2)と同じ方法で「yamadaの正しいパスワード」の解読を試みられるでしょう。

---

x=(y-a)/3 ←上記□例1の関数を「y=〜」の形に直した式

---

関数の実体さえ分かれば逆関数を求めることは可能ですからね。

「暗号化」の関数を「解く」ことが可能だ、というコトです。だからこそ「パスワードデータファイルを入手」し「関数の実体を推測」したクラッカーは「ターゲットのパスワードを当該関数に代入した結果」から「ターゲットのパスワード」を推測する。
パスワードデータファイルの中身が「正しいパスワードを一方向関数に代入した結果」だったら？たとえ「パスワードデータファイルを入手」し「関数の実体を推測」したとしても「ターゲットのパスワードを当該関数に代入した結果」から「ターゲットのパスワード」を解くことはできない。

---

さて、ここである疑問を持つかもしれません。「それではどのように認証を行えば良いのか？」と。

---

前回までで扱ったような「双方向関数による暗号化」を使ったパスワード認証システムは以下でしたね。

1. IDとパスワードを入力させる
2. サーバー内部のデータファイルを参照し「暗号化された正しいパスワード」を解読し「正しいパスワード」を得る
3. 「入力されたパスワード」と「(2で解読した)正しいパスワード」が一致ならば「ログイン成功」・不一致ならば「ログイン失敗」

同じことを「一方向関数」を使ったパスワード認証システムで行うのは不可能です。

サーバー内部のデータファイルを参照し「暗号化された正しいパスワード」を解読し「正しいパスワード」を得る

「一方向」ってことは「解読不可能」ってことですから。よって「一方向関数を使ったパスワード認証」とは以下。

1. IDとパスワードを入力させる
2. サーバー内データファイルから「正しいパスワードを一方向関数に代入した結果」を参照し、また、入力されたパスワードを同じ一方向関数に代入する
3. 「(データファイルから参照した)正しいパスワードを一方向関数に代入した結果」と「(2で計算した)入力されたパスワードを同じ一方向関数に代入した結果」が一致ならば「ログイン成功」・不一致ならば「ログイン失敗」

「関数を解く」ことは不可能でも「関数に代入を行う」「代入結果を比較する」ことは可能ですからね。
では、こうしたパスワード認証を破るにはどうすれば良いのか。「パスワードデータファイルを入手」し「関数の実体を推測」した上で何ができるのか。そう、「パスワード総当たり試行」しかない。

yamada,JUhbgfd4 ←ターゲットyamadaのパスワードをある一方向関数に代入した結果

1. 「takoyaki」を同じ一方向関数に代入したら「Dr5Bhgwx」だった。「JUhbgfd4」ではない。よってyamadaのパスワードは「takoyaki」ではない。
2. 「tabetaii」を同じ一方向関数に代入したら「kP6Nbw8V」だった。「JUhbgfd4」ではない。よってyamadaのパスワードは「tabetaii」ではない。
3. (以下略)

コレを繰り返していけばいつか「同じ一方向関数に代入すると『JUhbgfd4』になる文字列」が見つかるかもしれない。その「同じ一方向関数に代入すると『JUhbgfd4E』になる文字列」が「正しいパスワード」です。

前回までで、どのような「関数」がパスワード認証に向いているのか書いてきました。

• 同じ「入力」に対しても「鍵」によって「出力」を変えられる関数
• 「出力」から「入力」を求めることが不可能な一方向関数

---

実は、パスワード認証で使用されている「関数」はほぼ二種類しかありません。両方とも上記二条件を満たす関数です。

□1：DES

二文字の鍵を「XX」とすると出力は「XXYYYYYYY」となる。「Y」が「入力」「鍵」によって変わる。

□2：MD5

八文字(以内)の鍵を「XXXXXXXX」とすると出力は「$1$XXXXXXXX$YYYYYYYY$」となる。「Y」が「入力」「鍵」によって変わる。

---

特にMD5は「出力」が特徴的であるため、「パスワードデータファイル」を抜いたクラッカーは「そのサイト(なりサーバーなり)で使用されている関数」を推測することができます(逆の言い方をすると、関数の実体を推測されても使うだけのメリット・・・つまり「パスワード認証に使う関数」としての有用性・・・が上記二関数にはある、ということです)。

MD5ハッシュで暗号化されたパスワードは、DES ハッシュで暗号化されたパスワードよりも長いですし、その上$1$という文字で始まるという特徴も持っています
DESのパスワードはこれといって識別可能な特徴は持っていませんが、MD5のパスワードよりは短く、そして$という文字を含まない64文字のアルファベットを使って表現されているので、比較的短い文字列でドル記号で始まっていないものはおそらくDESのパスワードでしょう
「FreeBSDハンドブック」内「DES,MD5,とCrypt」より

DES,MD5ともに「出力」を見れば「鍵」は分かる(が「入力」は分からない)という関数であるため、パスワードデータファイルを抜いたクラッカーのすべきことは

1. そのパスワード認証で使用されている関数がDESなのかMD5なのか(もしくはその他の関数なのか)を判断する
2. (DESかMD5だったならば出力から)「鍵」を読みとる
3. 当該「関数」「鍵」に対して何を「入力」とすればパスワードデータファイル内の文字列が「出力」となるのか総当たり試行で探す

ということです。そして3の作業を自動化するのが「パスワードクラックツール」というヤツです。そうしたツールは凄まじい速度で様々な入力を当該関数に代入し代入結果を比較する。

一部のパスワードクラッキングソフトは、最新のPentium 4搭載マシンで毎秒800万件近くの文字の組み合わせを試すことが可能
「ZDNet」内「史上最悪のセキュリティホールは、ユーザーのパスワード」より

---

「毎秒800万件」という数字は二つの意味を持っています。

□1： 辞書に載っているような英単語なら一瞬で「クラック」することができる

例えば僕の手元にある(いわゆる学生向けの)英和辞書は「収録語約6万」ということです。一般的にクラッカーは辞書ファイル(よく使われる文字列が羅列されたファイル)を読み込ませて「パスワードクラックツール」を使用するため、多少数字を組み合わせたところで数時間粘ることすら困難でしょう。

□2：ランダムなパスワードを破ることは現実的に不可能である

印刷可能な95種類のASCII文字を使った8文字のパスワードの組み合わせは6600兆以上。一部のパスワードクラッキングソフトは、最新のPentium 4搭載マシンで毎秒800万件近くの文字の組み合わせを試すことが可能だが、それでも8文字のパスワードを破るには平均で13年以上かかる。
「ZDNet」内「史上最悪のセキュリティホールは、ユーザーのパスワード」より

ここまで来てようやく「辞書に出てくるような英単語をパスワードに使うのは危険」というよくある台詞の意味が分かったと思います。「危険」というのは何も「ログインformの『パスワード』に偶然その文字列を打ち込むクラッカーがいるかもしれないから」ではない。「パスワードクラックツールに辞書を読み込ませて総当たり試行させれば一瞬で破られるから」なのです。

---

「パスワードデータファイル」内の文字列は「正しいパスワードを一方向関数に代入した結果」であるため、理論上「パスワード認証」を破ることは(サーバー内部のパスワードデータファイルを抜いたとしても)不可能です。しかし多くの初心者ユーザーは「辞書に載っているような文字列」をパスワードにしている。ならば、「パスワードデータファイル内の文字列」を逆関数に代入することができなくても(英単語等の「関数」への代入による)総当たり試行によって破ることが可能である。
これが、今日の「パスワード認証」「パスワードクラック」の世界の概要です。