HOME»情報処理安全確保支援士掲示板»レインボーテーブルと還元関数に関して
投稿する

レインボーテーブルと還元関数に関して [1728]

 AP2さん(No.1) 
ChatGPTにも聞いてみたのですが、いまいち構造が分かりません。
初めに例えば1万回ハッシュ化して、最初の値と最後の値を格納すると思います。
攻撃者がパスワードをハッシュ化した値を入手します。
例えば9998回目にハッシュ化した値と一致するなら、9998回ハッシュ化を繰り返すことになります。
であるならば、何のために最初に1万回ハッシュ化したのでしょう?
最初の値と最後の値があっても、結局一致するまでハッシュ化を繰り返すなら…初めの処理の意味が理解できません。
2024.09.19 18:59
こんな感じかなぁさん(No.2) 
もしハッシュ化を1回だけやっていたら、攻撃者がすぐにパスワードを見つけられるかもしれません。でも、1万回繰り返していると、攻撃者はそれに何千回、何万回とハッシュ化を繰り返さなければならなくなり、攻撃するのがとても難しくなるんです。
攻撃者が、9998回目のハッシュ化の結果を見つけても、そこから残りの2回を見つけるのは簡単じゃないんです。なぜなら、攻撃者が最初のパスワードを知らないからです。そして、そもそも1万回のハッシュ化をするのに時間がかかるため、それを1回1回試すのは、ものすごく手間がかかります。ハッシュ化を何度も繰り返すことで、攻撃者がパスワードを見破るのに時間がかかるようにして、パスワードを守っているんです。
1回ハッシュ化するだけだと、攻撃者がすぐに解読してしまうかもしれませんが、1万回やるとすごく時間がかかるので、解読が難しくなります。
何度もハッシュ化することで、パスワードを安全に保つための「時間のカギ」をかけているんです!
2024.09.19 22:53
 AP2さん(No.3) 
ありがとうございます。
参考書には、レインボーテーブルの最後のハッシュ化パスワードと照合すれば前のパスワードを解析できると書いてあり。
しかしハッシュ化したものは、前に戻せないですものね?
ここで還元関数とやらを使うのだと思うのですが…謎が深まるばかりです(´・ω・`; )
2024.09.20 07:04
むぐむぐさん(No.4) 
レーンボーテーブルのチェイン周りの話ですね。私もそこまで詳しいわけではないですが…

(ハッシュ化:→  、還元関数:⇒)としてみてください
まずはチェインを作成します。
チェインA:平文A1 → ハッシュA1 ⇒ 平文A2 → ハッシュA2 ⇒ 平文A3 → ハッシュA3 ⇒ 平文A4 → ハッシュA4 ⇒ 平文A5
チェインB:平文B1 → ハッシュB1 ⇒ 平文B2 → ハッシュB2 ⇒ 平文B3 → ハッシュB3 ⇒ 平文B4 → ハッシュB4 ⇒ 平文B5
チェインC:平文C1 → ハッシュC1 ⇒ 平文C2 → ハッシュC2 ⇒ 平文C3 → ハッシュB3 ⇒ 平文C4 → ハッシュC4 ⇒ 平文C5

そのチェインの最初の平文と末尾の平文残して削除します。
チェインA:平文A1  平文A5
チェインB:平文B1  平文B5
チェインC:平文C1  平文C5


解析方法:
手順1.上記のようにチェインを用意する

手順2.解析したいハッシュに対して
  ハッシュ○4 ⇒ 平文○5 を求めた還元関数を使用
  末尾の平文○5と比較して一致した場合、パスワードの存在するチェインが特定できる。
  特定できた場合、手順4へ


手順3.特定できなかった場合、解析したいハッシュに
  ハッシュ○3 ⇒ 平文○4とする還元関数を使いその結果にハッシュ関数を使う、さらにその結果に  ハッシュ○4 ⇒ 平文○5を求めた還元関数を使う
(つまり平文A3 → ハッシュA3 ⇒ 平文A4 → ハッシュA4 ⇒ 平文A5  の生成時と同じ処理をする。もしも、解析したいハッシュ=平文A3  だとしたら、同じ計算を行うため最終的には平文A5に変換されるということ)
  末尾の平文○5と比較して一致した場合、パスワードの存在するチェインが特定できる。特定できた場合、手順4へ

できなかった場合さらに最後から1つ前に戻りハッシュ○2 ⇒ 平文○3のところから、平文○5を求めるまでの処理をおこなう。
チェインの先頭まで戻って処理を行っても平文○5と一致しなかった場合、どのチェインにも存在しないので、レインボーテーブル内に答えの平文は含まれていないということになる

手順4.チェインが特定できたのでそのチェインを復元すると、その中から解析したいハッシュの平文が特定できる。


これを行うことで、チェインAの中にパスワードと平文の組が1万個あっても1億個あっても、チェイン1つあたり平文2つの容量で保存できることになり、大幅にリソースの節約ができます。
2024.09.20 10:02
 AP2さん(No.5) 
とても詳しい説明、誠にありがとうございます。
私の頭が追い付いてこないです…。
先頭の1と末尾の5の平文を残し。
そこでチェインを使ってハッシュ関数?還元関数?を使って何回も計算する。
となると、やはり1万回・1億回計算してると思うので、この手法の何が良いところなのか分からないです。
5→4→3…と、ハッシュ化の逆のことができるのがメリットな訳ではないですよね?
済みません、頭がフリーズしてしまってます。。
2024.09.20 17:23
むぐむぐさん(No.6) 
この投稿は投稿者により削除されました。(2024.09.20 17:49)
2024.09.20 17:49
むぐむぐさん(No.7) 
効率などを考えていると思われますが、観点がおそらく違います。
メリットはリソース面で、効率ではないです。

テキストファイルにすべての平文とハッシュの組を用意しておき、解析したいハッシュ値を検索すれば早いのですが…

ざっくり計算になりますが8桁の英小文字+数字のみの総当たりでも2兆種類以上あります。
ハッシュ値+平文の組み合わせで1つあたり40バイトと仮定します。
すると2兆×40バイトで80テラバイトになります。
この超巨大ファイルでは扱いに困ってしまいます。そこで、レインボーテーブルを1つのチェインにすると、最小で平文2個の16バイトになります。

しかし、これでは処理がものすごく遅いですし、サイズを16バイトまで削る必要もないので、チェインを複数用意して並列で検証できるようにします。
これによって効率とリソースのいいとこどりを狙った仕組みになっているのだと思われます。
2024.09.20 17:50
 AP2さん(No.8) 
なるほど…観点がぶれていたかもしれません。
平文A1 → ハッシュA1 ⇒ 平文A2
としたときの平文A2ですが、現実的に人が考え付く(普通に付けそうな)パスワードになりますでしょうか?
私が思うに全くランダムな値が生成されると思うので、そんな人が付与しなさそうな平文がどれだけ作られたとしても、それは一致しなくて意味をなさないような気もしていて…。
根本が理解できてないと思われご迷惑かけて申し訳ないですが、何か良いアドバイス頂けますと幸いです。
2024.09.20 19:17
mickey39さん(No.9) 
<前提>
・ハッシュ関数 … ある文字列を入力すると特定のアルゴリズムで短く変換した値(ハッシュ値)を出力する関数。アルゴリズムは複数種類ある。
・還元関数 … ハッシュ関数に入力される前の文字列(の候補)の値を出力する関数

<攻撃者の状況>
・攻撃対象のサービスからPWのハッシュ値Xを入手できた
・ハッシュ値Xをもとに、PWの平文が知りたい
・ただしハッシュ値Xは何回ハッシュ化されているか・どのハッシュ関数が使われたか等はわからない

そこで、攻撃者はレインボーテーブルを使ってPWの平文に辿り着こうとする。
ハッシュの種類やハッシュ値の長さ等に応じた、
「よく使われるPW:◯回目にハッシュ化→還元関数を使った文字列」
…という組み合わせを列挙したレインボーテーブルを、いくつか用意する。

■ レインボーテーブルA(アルゴリズムA用・10回、ハッシュ関数→還元関数を繰り返す)
・password123: 10回目に還元関数を使った文字列(チェインA①)
・pswd:10回〃(A②)
・dragon:10回〃(A③)


■ レインボーテーブルB(アルゴリズムB用・1000回〃繰り返す)
・password123: 1000回ハッシュして還元関数を使った文字列(チェインB①)
・pswd: 1000回〃(B②)
・dragon: 1000回〃(B③)


<レインボーテーブルを使った照合の流れ>
まずは手元のハッシュ値Xを還元関数にかける。得られた値を、
チェインA①、A②、A③…などと順に照合していく。

合致すれば、そのチェインに手元のハッシュ値に対応する文字列があると分かるので、
遡って計算を行っていくことで、Xをハッシュ化するまえの平文を取得することができる。

合致しなかったら、還元関数にかけたハッシュ値Xに対して
さらにハッシュ化→還元関数を使い、
各チェインでも同様に、ひとつ前段階の文字列を求めていく。
それをさらにXと比較する。これを繰り返す。

遡って検証した結果、対象文字列がレインボーテーブルAにないことがわかれば、
次にレインボーテーブルBでも同様に計算→照合を行っていく。
これを、目的の平文が得られるまで繰り返す。

<補足>
攻撃対象のサービスからハッシュ値を奪取したとしても、
そのサービスがPWを保存しているにあたって何回ハッシュしているのかや
ハッシュ関数の種類が攻撃者側で分からない。

そのとき、
  ・ひとつの平文:ハッシュ値A
  ・ハッシュ値A:還元した文字列A
  ・還元した文字列A:ハッシュ値B …
というような、膨大な組み合わせ表を用意しておくのは現実的ではない。

ハッシュ→還元→ハッシュ…というのを◯回繰り返す中で、
目的の平文が1度でも見つかれば攻撃成功となるため、
その計算に「必要な材料だけ」を保存してあるのがレインボーテーブル。

1万回ハッシュ化した値をレインボーテーブルに充てるというのは、例えばの話。
攻撃者の持っているマシン性能などによってレインボーテーブルの値に
何回ハッシュ化→還元関数にかけた文字列を使うかは変わってくる。
(これは各チェインの計算状況を保っておくのに、メモリを使うため)

――――
私も勉強途中なのですがこういう理解です。
有識者の方、補足ください🙏
2024.09.20 19:22
pixさん(No.10) 
SC ダイヤモンドマイスター
シンプルに考えるのが良いかと思います。
ハッシュを1万回繰り返したレインボーテーブルは、テーブルを圧縮してコンパクトに
したようなものです。
もしコンパクトでない生のレインボーテーブルは数百テラバイトになるかもしれません。
数百テラバイトのデータを保持しておくのは、ディスクも費用もかかってしまい、
現実的ではありません。

これとは逆に最近はコンピュータの能力を調達することは容易です。
最近のコンピュータのCPUは強力です。1万回くらいのハッシュ計算は即時に実行
できるでしょう。
また、クラウドなどで仮想マシンを調達し、コンテナ技術で仮想マシンを
オートスケールでデプロイすれば、一時的に数百台のコンピュータを用意することも
可能です。
そうすれば単純に1台の時に比べて数百倍の処理速度が稼げます。

また、攻撃者が一人ではなく複数いるということも考えられます。
攻撃者に協力者が10人いれば10倍の処理が可能になります。

もっと進んだ考え方では、レインボーテーブルとコンピュータをクラウドでレンタル
するサービスを提供する悪人がいることも考えられます。
こうなると攻撃者は事前の準備は不要でサービスをレンタルするだけで攻撃が可能に
なります。
ダークネットにはこのような悪事をする者が組織または国単位で存在しているとの
もっぱらの噂です。
2024.09.20 20:15
むぐむぐさん(No.11) 
AP2さん
レインボーテーブルは元々総当たりが目的なので、通常人が使わない文字列も探索の対象としていいのです。
人が使う文字列のみを使用したい場合は、辞書攻撃やパスワードリスト攻撃など別の手法の話になります。

mickey39さん
概要までは過去に調べて把握しているのですが、実際の細かい挙動まではわかりません。申し訳ないです。
2024.09.20 20:29
 AP2さん(No.12) 
皆様どうもありがとうございました!
書き込み頂いたものを入念に読み直すことで、ようやくぼんやりとイメージが湧いてきたかもしれません!!
これを元に更に理解が深まるよう勉強を進めて参ります。
とても助かりました(*`・ω・)ゞ
2024.09.20 21:11
返信投稿用フォーム

お名前

顔アイコン


本文(コミュニティガイドライン⇱を順守して適切な投稿を心がけましょう)

🔐投稿削除用のパスワード

投稿プレビュー
※SQL文は全角文字で記載してください。
※宣伝や迷惑行為を防止するため、当サイトとIPAサイト以外のURLを含む文章の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2014-2024 情報処理安全確保支援士ドットコム All Rights Reserved.

Pagetop