namdicul's blog

気ままに更新します. CTFと暗号理論について勉強中です.

暗号理論(6) ~メッセージ認証コード~

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて

メッセージ認証コードで何ができるの??

前回の記事では, 一方向ハッシュ関数について説明しました.

一方向ハッシュ関数を使用することで, メッセージが改竄されたかどうかを検出することができるというメリットがありました.
例えば, AliceさんがBobさんにメッセージを送る場合を考えます. Aliceさんはメッセージとそのハッシュ値をBobさんに送信します. Bobさんはそのメッセージのハッシュ値を求め, 送られてきたハッシュ値と一致していればメッセージが改竄されていないことがわかります.

しかしここで問題があります. 能動的攻撃者MalloryがAliceさんからのメッセージとハッシュ値を取得してBobさんの手に渡らないようにし, 代わりに全く別のメッセージとそのハッシュ値をBobさんに送ることが可能です. BobさんはAliceさんからきたと思われるメッセージのハッシュ値を求め, 送られてきたハッシュ値を比較することで改竄されているか確認します. 改竄が検出されていないことを確認し, そのメッセージを受け取ります. しかしそのメッセージはMalloryからの悪意のあるメッセージなのです.

このように, 一方向ハッシュ関数ではメッセージの改竄を検出することはできますが, なりすましを検出することはできません.


これから紹介するメッセージ認証コードは, 改竄となりすましを検出するための手段の1つです.


メッセージ認証コードは, メッセージ2者間(送信者と受信者間)の共通鍵の2つを入力とし, 固定ビット長の出力を計算する関数です.このときの出力をMACと言います.

MAC値を計算するためにはあらかじめ共通鍵を知らなければいけません. よって共通鍵を知らない人はMAC値を求めることはできません.したがって, 送信されてきたメッセージと所有している共通鍵からMAC値を求めて, それが送信されてきたMAC値と一致した場合, 正しい相手から改竄されていないメッセージが送信されてきたと思ってよいわけです.

メッセージ認証コードは, 「鍵に依存した一方向ハッシュ関数」と考えることができますね.

図で表現すると以下のようになります.
f:id:tomonori4565:20181004112027p:plain

次に, メッセージ認証コードの内部の仕組みを見ていきましょう.

メッセージ認証コードの仕組み

メッセージ認証コードは, SHA-1MD5のようなハッシュ関数を使って実現することができます. ここでは, 代表的なHMACというメッセージ認証コードの仕組みを見ていきましょう.

以下の図がHMACの仕組みです.

f:id:tomonori4565:20181004115352p:plain

先ほども言ったように, メッセージ認証コードには「メッセージ」と「共通鍵」が入力されます. まずは入力された鍵について見ていきましょう.

メッセージ認証コードの内部では一方向ハッシュ関数を使用しているため, ブロック長をそのハッシュ関数に合わせてあげる必要があります. なので必要ならば入力された鍵に0をパディングしておきます.

次に, ipadとパディングした鍵のXORを取ります(この結果をipadkeyとします). ここでipadとは「ブロック長になるまで00110110を繰り返したもの」を指します. 例えばブロック長が64ビットであった場合, ipadは「00110110」× 8ということになります.

続いて, ipadkeyとメッセージを結合させ, 一方向ハッシュ関数に入力します(この結果をhash1とします).

今度は, opadとパディングした鍵のXORを取ります(この結果をopadkeyとします). ここでopadとは「ブロック長になるまで01011100を繰り返したもの」を指します.

あとは先ほどと同様に, opadkeyとhash1を結合させて一方向ハッシュ関数に入力します. その値がMAC値となるわけです.

手順をまとめると以下の通りになります.

(1) 必要ならば鍵へのパディング
(2) パディングした鍵とipadのXORをとる(結果をipadkeyとする)
(3) メッセージとipadkeyを結合し, 一方向ハッシュ関数に入力してハッシュ値を求める(このハッシュ値をhash1とする)
(4) パディングした鍵とopadのXORをとる(結果をopadkeyとする)
(5) hash1とopadkeyを結合し, 一方向ハッシュ関数に入力してハッシュ値を求める. このハッシュ値MAC値となる.

メッセージ認証コードに対する攻撃手法

再生攻撃

例えば以下のような状況を考えましょう.

MalloryはAlice銀行とBob銀行の通信を盗聴する悪い攻撃者です. MalloryはAlice銀行に行き, Bob銀行にある自分の口座に100万円を入金します. すると, Alice銀行はBob銀行に向けて以下のようなメッセージを作成するはずです.

Bob銀行へ,

口座C-5342に100万円を入金してちょうだい.

Alice銀行より.

Alice銀行はこのメッセージのMAC値を計算して, メッセージと共にBob銀行に送信しました. Bob銀行は送信されたMAC値と, 自分で計算したMAC値が一致することを確認し, データの改竄となりすましがされていないことを確認します. そのあと, Malloryの口座に100万円を入金します.


しかし, この一連のやり取りをMalloryは盗聴します. つまり, Alice銀行からBob銀行へ送信されたメッセージと正しいMAC値を盗聴して手元に保存しておきます. そしてメッセージと正しいMAC値をBob銀行へ向けて100回送信します.


するとどうなるでしょうか.


100回送信されたデータは全て同じものであり, メッセージに対する正しいMAC値が存在しているので, Bob銀行はこれらの送信されたデータは, 全てAlice銀行から送信された, データの改竄やなりすましがされていないデータだと判断してしまうのです.


すると結果的にはMalloryの口座に一億円が振り込まれてしまうことになりますね.


このような攻撃手法を「再生攻撃」と言います.

では再生攻撃を防ぐためにはどうしたら良いでしょうか. ここでは複数の手段を紹介します.


(1) データにシーケンス番号を含める.
送信メッセージにシーケンス番号という, 送信するごとに毎回1増加する番号を含めておきます. すると, メッセージ内容が一緒でも, MAC値が違ってくるので再生攻撃はできなくなります. ただ, 通信相手ごとにシーケンス番号を記憶しておく必要があるというデメリットもあります.

(2) タイムスタンプの使用
送信メッセージに現在時刻を掲載しておくことで, 再生攻撃を防ぐことができます. 過去のデータが送られてきた場合には, MAC値が正しくても無効なデータと判断します. こうすることで再生攻撃を防ぐことができます. しかし, 通信相手と自分の時計を一致させておかないと, 有効であるはずの送信データが無効になってしまう場合があります. また, 通信状態も加味して時間に余裕を持たせる必要があるので, 再生攻撃の余地が残ってしまいます.

(3) nonce
使い捨てのランダムな数値のことをnonceと言います. 受信者から送信者に向けてnonceを渡すことで, 同じメッセージでも毎回違ったMAC値を計算させることができます. しかし, 通信データ量が多くなってしまうのがデメリットです.

メッセージ認証コードでは防げない問題

三者に対する証明

メッセージ認証コードによって, なりすましとデータの改竄を検出できるようになりました. 従って, AliceからBobへデータを送信した際には, Bobは「Aliceがこのデータを送信したんだ」と解釈できるようになりました.

しかし, 第三者Victorに「Aliceがこのデータを送信したんだ」と証明することはできません. なぜならVictorは「いやいや, このデータはBobが作ったんじゃないの?」と考えることができるからです.

それもそのはず, AliceとBobは同じ共有鍵を所有しているので, BobがAliceと同じデータを作成することは「可能」なのです!

メッセージ認証コードを使用すれば, 通信し合っている2者間では, 送信されたデータは送信者Aliceのものだと解釈できます. 同じ共有鍵を使用している者のうち, その1人は自分だからです. しかし, 第三者に「このデータは送信者Aliceが本当に作成したものなんだ」と証明することは残念ながらできないのです.

次の記事で紹介する「デジタル署名」を使用すれば, 第三者に対する証明が可能となります.

否認防止

否認とは, データを送信したのちに「そんなデータ送ってないわ」と主張することを指します.

例えば, AliceがBobに「10000円貸して」というデータを送信したとします. BobはAliceに, 「なんで10000円が必要なんだい?」と尋ねます. そこでAliceは, 「そんなデータ送ってないわ」と主張できます. これを否認と言います.

メッセージ認証コードを用いただけでは, 否認を防ぐことはできません. 先ほども述べたように, 第三者に対して「このデータは本当にAliceが送ったものなんだ」と主張することはできないからです.

同様の理由で, デジタル署名を用いれば, 否認を防止することができます.

暗号技術入門 第3版

暗号技術入門 第3版

暗号技術のすべて

暗号技術のすべて