パスワードクラック概論(4)
例えばある関数があったとします。
パスワードクラック概論(2)やパスワードクラック概論(3)の「パスワード認証」の脆弱性とは
パスワードデータファイルの中身が「正しいパスワードを一方向関数に代入した結果」だったら？たとえ「パスワードデータファイルを入手」し「関数の実体を推測」したとしても「ターゲットのパスワードを当該関数に代入した結果」から「ターゲットのパスワード」を解くことはできない。
さて、ここである疑問を持つかもしれません。「それではどのように認証を行えば良いのか？」と。
前回までで扱ったような「双方向関数による暗号化」を使ったパスワード認証システムは以下でしたね。
y=f(x)=3x+5
この式を「x=〜」の形に直すことを「関数を解く」と呼んでいましたよね。
x=(y-5)/3
さて、単純な1次関数ならば解くことは可能ですし簡単です。コレが2次関数になってくると・・・例の「解の公式」という・・・ややこしい計算が必要になってくる。3次関数・4次関数になっても(高校数学では扱われませんが3次関数・4次関数にも「解の公式」は存在します、異常にややこしいですけど)一応解くことは可能です。しかし、この世には「解けない関数」も存在する。「計算がややこしい」とか「解くのが困難」ではなく「解けない」関数。
5次以上関数になると「解の公式」は存在しません。
y=f(x)=3x^5+2x^4+5x^3-12x^2+6x+2 (a^bは「aのb乗」)
例えば「x=5の時yはいくつ？」と言われたら代入すれば良い。けれどその逆・・・つまり、例えば「y=5の時xはいくつ？」という問いに答えること・・・はできない。「計算が大変だ」というコトではなく「解けない」。
・・・と一応書いておきますが、「何故4次までの方程式には『解の公式』が存在するのに5次以上では存在しないのか」とかいうのは数学的にややこしい話になっていくので「よく分からないけどこの世には解けない関数も存在するんだ」ということで勘弁して下さい。
そう、関数を与えられた我々は必ず「関数への代入」を行うことができる。しかし「関数を解く」ことは「必ずできる」訳ではない。こういう性質を持った関数は「一方向関数」と呼ばれます。y=f(x)だったとして、「xからyを求めることもyからxを求めること(=逆関数を求めること)もできる」というのが「双方向」、「xからyを求めることはできてもyからxを求めることはできない」というのが「一方向」。y=f(x)=3x^5+2x^4+5x^3-12x^2+6x+2 (a^bは「aのb乗」)
例えば「x=5の時yはいくつ？」と言われたら代入すれば良い。けれどその逆・・・つまり、例えば「y=5の時xはいくつ？」という問いに答えること・・・はできない。「計算が大変だ」というコトではなく「解けない」。
・・・と一応書いておきますが、「何故4次までの方程式には『解の公式』が存在するのに5次以上では存在しないのか」とかいうのは数学的にややこしい話になっていくので「よく分からないけどこの世には解けない関数も存在するんだ」ということで勘弁して下さい。
参考: よっち@ほ〜む内「高次方程式の解の公式」
一応紹介しておきます・・・。
パスワードクラック概論(2)やパスワードクラック概論(3)の「パスワード認証」の脆弱性とは
y=3x+a「暗号化」の関数を「解く」ことが可能だ、というコトです。だからこそ「パスワードデータファイルを入手」し「関数の実体を推測」したクラッカーは「ターゲットのパスワードを当該関数に代入した結果」から「ターゲットのパスワード」を推測する。
y:パスワードデータファイルに保存する文字列
x:(生の)パスワード
a:アカウント
勿論、「鍵(=暗号化関数に対するパスワード以外の入力)がアカウントである」というコトがバレてしまえばパスワードクラック概論(2)と同じ方法で「yamadaの正しいパスワード」の解読を試みられるでしょう。
x=(y-a)/3 ←上記□例1の関数を「y=〜」の形に直した式
関数の実体さえ分かれば逆関数を求めることは可能ですからね。
パスワードデータファイルの中身が「正しいパスワードを一方向関数に代入した結果」だったら？たとえ「パスワードデータファイルを入手」し「関数の実体を推測」したとしても「ターゲットのパスワードを当該関数に代入した結果」から「ターゲットのパスワード」を解くことはできない。
さて、ここである疑問を持つかもしれません。「それではどのように認証を行えば良いのか？」と。
前回までで扱ったような「双方向関数による暗号化」を使ったパスワード認証システムは以下でしたね。
同じことを「一方向関数」を使ったパスワード認証システムで行うのは不可能です。
- IDとパスワードを入力させる
- サーバー内部のデータファイルを参照し「暗号化された正しいパスワード」を解読し「正しいパスワード」を得る
- 「入力されたパスワード」と「(2で解読した)正しいパスワード」が一致ならば「ログイン成功」・不一致ならば「ログイン失敗」
サーバー内部のデータファイルを参照し「暗号化された正しいパスワード」を解読し「正しいパスワード」を得る「一方向」ってことは「解読不可能」ってことですから。よって「一方向関数を使ったパスワード認証」とは以下。
- IDとパスワードを入力させる
- サーバー内データファイルから「正しいパスワードを一方向関数に代入した結果」を参照し、また、入力されたパスワードを同じ一方向関数に代入する
- 「(データファイルから参照した)正しいパスワードを一方向関数に代入した結果」と「(2で計算した)入力されたパスワードを同じ一方向関数に代入した結果」が一致ならば「ログイン成功」・不一致ならば「ログイン失敗」
※補足
これ書くべきか書かないべきか迷ったんですが一応書いておきます。
「暗号」という言葉は定義として「解読できるから『暗号』」です。従って「一方向関数」は「暗号」ではありませんし「一方向関数への代入」は「暗号化」ではありません。
・・・まぁ上記を知らずに「一方向関数による暗号化」とかいう日本語を使うと怒る人は怒りバカにする人はバカにする気が少しするので心の隅に留めておいてもらえれば。
では、こうしたパスワード認証を破るにはどうすれば良いのか。「パスワードデータファイルを入手」し「関数の実体を推測」した上で何ができるのか。そう、「パスワード総当たり試行」しかない。これ書くべきか書かないべきか迷ったんですが一応書いておきます。
「暗号」という言葉は定義として「解読できるから『暗号』」です。従って「一方向関数」は「暗号」ではありませんし「一方向関数への代入」は「暗号化」ではありません。
・・・まぁ上記を知らずに「一方向関数による暗号化」とかいう日本語を使うと怒る人は怒りバカにする人はバカにする気が少しするので心の隅に留めておいてもらえれば。
yamada,JUhbgfd4 ←ターゲットyamadaのパスワードをある一方向関数に代入した結果
- 「takoyaki」を同じ一方向関数に代入したら「Dr5Bhgwx」だった。「JUhbgfd4」ではない。よってyamadaのパスワードは「takoyaki」ではない。
- 「tabetaii」を同じ一方向関数に代入したら「kP6Nbw8V」だった。「JUhbgfd4」ではない。よってyamadaのパスワードは「tabetaii」ではない。
- (以下略)
※補足
2chの「トリップ」は一方向関数によって生成されています。で、その一方向関数の実体は既に明らかになっています。
従って「ある特定トリップが欲しい」と思ったら総当たりで「その文字列が出力される入力」を探せば良い。「見知らぬ国のトリッパー（ｗ」というフリーソフトがその作業を自動化してくれます。
2chの「トリップ」は一方向関数によって生成されています。で、その一方向関数の実体は既に明らかになっています。
従って「ある特定トリップが欲しい」と思ったら総当たりで「その文字列が出力される入力」を探せば良い。「見知らぬ国のトリッパー（ｗ」というフリーソフトがその作業を自動化してくれます。
TrackBack
この記事へのトラックバック