応用情報技術者 試験情報＆徹底解説

タイトルの項目の部分を復習したときに疑問が湧き、解決できません。
すっかり思考が泥沼化してしまったので、詳しい方に教えていただきたいです。
長くなるので1つづつ。

●ダイジェストで改ざんなし証明
テキストにはハッシュ関数で平文とそのダイジェストを送る図が描かれていたのですが、
送信者と受信者で同一のハッシュ関数を使って照合する必要があるはずです。となると、
予め同じハッシュ関数の情報を持つ機器またはソフトウェア同士でないと照合が
できないように思えます。どの機器とも称号が可能なように共通のハッシュ関数が
あるのなら盗聴者も同じハッシュ関数を持っているはずで、平文の改ざん後、共通の
ハッシュ関数を使ってダイジェストを偽造したうえで元のダイジェストをすり替えたら、
改ざんなしが証明できないはずです。
かといって、照合に使用するハッシュ関数を一緒に平文で送ってしまったら、盗聴者に
それを盗聴され、改ざん後に盗聴したハッシュ関数を使ってダイジェストを偽造して
置き換えるだけで改ざんなしは証明できなくなるように思えます。
それならばと、公開鍵暗号方式で平文とダイジェストを暗号化して送受信したら、
それはディジタル署名と呼ばれるもののはずです。
結局、これは何なのでしょうか？ 予め共通のハッシュ関数が設定された専用機器や
専用ソフトウェアだけで使われる暗号化されていない通信を使った
改ざんなし証明なのでしょうか？

●ハッシュ関数の不可逆性
平文をハッシュ関数でハッシュ化してダイジェストにできるが、ダイジェストからは
平文を復元できないという性質だったと記憶していますが、本当に不可逆性があるの
でしょうか？ 攻撃者がハッシュ化されたパスワードから元のパスワードを特定する
方法としてレインボー攻撃というものがありました。それを防ぐためにストレッチングを
何度もするように書かれていたのですが、これはハッシュ関数の不可逆性と矛盾して
いるように思えます。レインボー攻撃が成立するのなら、そもそもハッシュ関数に
不可逆性は存在しないはずですし、ハッシュ関数に本当に不可逆性があるのなら
レインボー攻撃は実際にはできないフィクションですし、解析の時間稼ぎのストレッチングを
する意味が不明です。レインボー攻撃があり対策としてストレッチングを
勧めていることから、不可逆性に疑問をもってしまいました。

よく分からないうちは、とにかく素直にそのまま頭に記憶したので何ら不思議にも
思わなかったのですが、復習をしてある程度理解できたらさらに分からないことが
出てしまいました。とりあえず、午後試験でもその通り答えを書いておけばよさそう
なのですが、理解できないのは気持ちがもやもやします。

「●ダイジェストで改ざんなし証明」に対してです。

改ざん検知のためのメッセージ認証には、大きく3つの方式があります。

1.鍵付きハッシュ関数(HMAC)
メッセージと通信当事者間の共通鍵を組み合わせてハッシュ関数に入力して得られたハッシュ値をメッセージ認証符号とする。

2.共通鍵暗号方式
メッセージを共通鍵で暗号化したものをメッセージ認証符号とする。

3.ディジタル署名
(略)

これらの方式だと、第三者がメッセージを改ざんした後に、それに応じたメッセージ認証符号を作成することはできません。

単なるハッシュ値をメッセージ認証符号とする方式では、改ざんは検知できません。お手元のテキストの内容のどこがおかしいかはわかりませんが。

ただし、例えばWebページの改ざん検知のために、改ざん前のWebページのハッシュ値を求めておいて、定期的にWebページのハッシュ値を計算してそれと比較する方法は有効です。改ざん前のハッシュ値をあらかじめ確保していますので。

「●ハッシュ関数の不可逆性」に対してです。

不可逆性とは、y＝f(x)(xが分かればyが求まる)のとき、x＝g(y)となる関数gがわからない(yが分かってもxは求まらない)という性質です。

例えば、ハッシュ関数として、y＝x mod 3のとき、yが2と分かってもxは2、5、8、・・・のうちどれかは求まりません。このとき、y＝x mod 3は、不可逆関数です。

レインボー攻撃は、x＝1、2、3、・・・に対してyを求めておき、yが分かったら、対応するxを見つけ出そうとするものです。yが2と分かったら、レインボー攻撃によって、xは2、5、8、・・・のうちどれかであると、候補は絞れます。

したがって、不可逆であるけど、レインボー攻撃は可能というわけです。

回答ありがとうございます。

●ダイジェストで改ざんなし証明
『情報処理教科書 出るところだけ！ 応用情報技術者（午後）』Kindle版
の271ページにある「ハッシュ関数」の項目で、暗号化をせずダイジェストのみの確認の
説明があり、改ざんなしを確かめる方法として書かれています。ただ、その説明で送信者と
受信者の間でハッシュ関数を共有する方法に触れられておらず、盗聴のことを
考えたとき、どうやってこの方法で改ざんなしを証明するのか分からなくてなっていました。
Webページの改ざん防止なら納得できます。

●ハッシュ関数の可逆性
ある値が確定したとき、別の値が一意で最終的に全部が一意に決まるときが可逆性が
あるということで、ハッシュ関数は候補を絞ることはできるが、値が最終的に一意に
定まらないということで不可逆性なのですね。レインボー攻撃は、失敗と成功を
繰り返しながら候補を絞っていき、最終的に突破する方法だと理解ができました。
ふと、またいらないことを考えてしまいました。
極端な話、h(x) = 0というハッシュ関数を使ったら、全てのハッシュ値が0になり、
これでは一意に決まらないどころではないですね。もっとも何を入力しても一致したと
判定されるので、セキュリティの意味を成さないわけですが（笑）

追記しておきます。

●改ざん防止
メッセージ認証は、「改ざん防止」のためではなく、「改ざん検知」のためです。メッセージ認証の目的は何か、と問う問題があれば、「改ざん検知」と答えないと正解になりません。

●レインボー攻撃
この内容はおそらくご存じだと思いますが、(No.4)に「失敗と成功を繰り返しながら候補を絞っていき、最終的に突破する方法」と書かれているので、念のためです。
xのハッシュ値がyであるとき(例えば、xがパスワード、yがハッシュ化パスワード)、xの全ての値に対して総当たり的にyを求め、xとyの対応テーブルを作成しておき、yのある値を入手したら、それを基にxを推測する攻撃です。
SQL風に書くと、入手したyを:yとして
SELECT x FROM TBL WHERE y = :y
です。

●ハッシュ関数の種類
例えば、SHA-256は256ビットのハッシュ値を出力しますが、SHA-256を使っていることが知られれば、誰でも平文からハッシュ値を計算できます。このため、レインボー攻撃を困難にするために、パスワードとソルト(ユーザごとに別々のランダムな値)を結合したものからハッシュ化パスワードを求める方法もあります。鍵付きハッシュ関数(HMAC)の共通鍵も、いわばソルトみたいなものです。

何度もありがとうございます。時間使わせちゃって少々申し訳ないです。

●改ざん防止
投稿を読んで、テキストを見ましたが「改ざんを確かめる」という表現が使われていました。
「防止」とは事前のことで、「検知」「確かめる」は事後のことですね。
学習中に聞けてよかったです。
自分のノートを見ましたが、ところどころ「防止」という単語が事後のことに使われて
いました。メッセージ認証は改ざんの事後のことなので「防止」は不適切な表現ですね。
事前と事後を注意して回答しなくては、、、

●レインボー攻撃
これは実は完全に勘違いしていました。候補を絞って実際に試して認証に失敗したら
さらに候補を絞っていくというイメージでした。候補を絞るというイメージを
間違えたようです。二分探索で解くハイアンドロー数字当てをもっと複雑にしたもの程度に
考えていたのですが、もっとパズル的要素が強い手段でした。
応用情報技術者試験で詳しい内容がでるかは分かりませんが、
情報セキュリティスペシャリスト試験での出題歴があるようなので、覚えておいて
損はなさそうです。攻撃の手段なのであれですが、面白いアルゴリズムですね。

●ハッシュ関数の種類
レインボー攻撃のアルゴリズムからすると、ソルトがつけられるとそれだけの
テーブルを大量に作らないといけないわけで、大文字小文字英数字で62文字。
ソルトの文字数が20文字と仮定して62^20通り。
ストレッチングされたら、1回では終わらない。それが1パスワード ごと、、、。
処理にかかる時間も数字が大きすぎて分からないです。処理が終わる前にCPUの
寿命がきそうで、そもそもそんなテーブルをメモリ上に展開できないような、、、。

ハッシュ関数は今まで、プログラムの処理でオーダを減らし高速化のために
ハッシュテーブルを使う程度でしたが、偉大ですね。