情報セキュリティ　 第４回 メッセージ認証コード.

Presentation on theme: "情報セキュリティ　 第４回 メッセージ認証コード."— Presentation transcript:

1 情報セキュリティ　 第４回 メッセージ認証コード

2 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄
セキュリティに対する脅威　　　　脅かされる特性　　　　　暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄 （情報が書き換えられる） 正真性 一方向ハッシュ関数 なりすまし （正しい送信者のふりをする） 認証 メッセージ認証コード 否認 （後から私じゃないと言う） 否認不可能性 デジタル署名

3 鍵Kを知っているのは送信者と受信者だけであることが前提
メッセージ認証コード（MAC） 鍵Kを知っているのは送信者と受信者だけであることが前提 目的 送信者を認証する。 メッセージ改竄を防ぐ。 モデル 送信者と受信者は鍵Ｋを共有 送信者は鍵ＫとメッセージMから認証子（Ｔag）を作成し、 MとTagの組を送信する。 受信者は、 受信したMと鍵KからTag’を再計算する。 Tag＝Tag’ならばMを受理する。 Tag≠Tag’ならばMを廃棄する。 Tag＝Tag’によって、平文Mは改竄がなく、鍵Kを知っている人から来たことが確認できる。 アルゴリズム 鍵生成アルゴリズムＧ：鍵Kを作成する。 認証子生成アルゴリズムＳ：認証子Tagを作成する。Tag=S(M,K) 鍵KでTag作成 再度、鍵KでTag’作成 平文M 送信者 (M,Tag) 受信者 Tag=Tag’の場合だけ受理 敵 敵は平文Mを途中で改竄するかもしれない Mが改竄されるとTag≠Tag’ 鍵生成 アルゴリズムG 鍵K 平文M 認証子生成 アルゴリズムS 認証子 Tag 鍵K

4 偽造とは、受信者が受理する組(M,Tag)を作ること
ＭＡＣの安全性 選択メッセージ攻撃 敵は自由に選んだメッセージM1,..,Mqに対する認証子から(M,Tag)を偽造する。 偽造とは： 受信者が受理する(M,Tag)を作成することを「偽造」と言う。 鍵Kを知らなくても偽造できる場合がある。 MACが「安全である」とは： 敵が偽造に成功する確率が無視できる程小さいならば、安全である。 MACはブロック暗号方式 ブロック暗号で使われる暗号化アルゴリズムEkは擬似ランダム置換族に属する。 選択メッセージ攻撃 認証子生成 アルゴリズムS 認証子 Tag1,..,Tagq 平文 M1,..,Mq 平文を自由に選択出来る 敵 偽造 (M,Tag) 偽造とは、受信者が受理する組(M,Tag)を作ること

5 ＣＢＣ-ＭＡＣ 認証子生成アルゴリズムS 認証子生成アルゴリズムS メッセージM=(m1,..,mt)、|mi|=n、i=1,..,t
CBCモードを使ったMAC 認証子生成アルゴリズムS 認証子生成アルゴリズムS メッセージM=(m1,..,mt)、|mi|=n、i=1,..,t C1=EK(m1) C2=EK(C1 m2) ... Ct=EK(Ct mt) Tag=Ct 安全性 メッセージ長tが固定ならばCBC-MACは安全である。 メッセージ長tが可変ならば、偽造できる。 偽造例 m∈{0,1}nのTagを得る。 このTagは、メッセージM=(m,m 　Tag)の正しい識別子である。 m m mt … EK EK EK Tag 偽造例 手順１ 手順２ m M=(m, m　　Tag) Tag m Tag = m EK EK EK 選択メッセージ攻撃 Tag Tag Tag

6 偽造出来ないようにCBC-MACを改良する
ＣＢＣ-ＭＡＣの改良 偽造出来ないようにCBC-MACを改良する EMAC（Encrypted MAC） 新しい鍵k2を使って、CBC-MACの認証子CBCk1(M)を暗号化して認証子Tag作成する。 Tag=Ek2(CBCk1(M)) 可変長メッセージに対して安全 OMAC（one-key MAC） |mt|=n（ブロック長）の場合 Tag=Ek(Ct-1 　 mt 　 (L・u)) |mt|<nの場合 Tag=Ek(Ct-1 　(mto1o0i) 　 (L・u2)) EMAC方式 m m mt … EK1 EK1 EK1 鍵k2による暗号化 EK2 Tag メッセージ長がブロック長nの整数倍でない場合 oはビット列の連結 iは|mto1o0i|=nとなるように選ぶ OMAC方式 0n m m2 … mｔまたはmｔo1o0i 鍵が1つだからone-key L・uまたはL・u2 EK EK EK EK uは拡大体GF(2n)上の要素 ・は拡大体GF(2n)上の乗算 L Tag

7 拡大体ＧＦ（2n） GF(2)の加法 GF(2)の乗法（・） y y 1 1 x x 1 1 1 1 1 GF(2n)の加法
有限体（ガロア体） 体とは、0 で割ることを除いて四則演算が自由にできる系。 有限体とは、要素数が有限個の体。 例えば、GF(2)では要素数2（0と1)の体。 ＧＦ（2n） GF(2)の拡大体（nビットに拡大） 多項式表示：　an-1un-1+・・+a1u+a0 ベクトル表示：　（an-1,..,a1,a0） 足算は排他的論理和をビット毎に行う。 掛算は、通常の掛算の後にn次の既約多項式f(u)で割った余りである。 既約多項式とは、これ以上因数分解できない多項式である。 既約多項式f(u)は１つに固定される。 GF(2)の加法 GF(2)の乗法（・） y y 1 1 x x 1 1 1 1 1 GF(2n)の加法 ベクトル表示 a b=(an-1 bn-1,..,a0 b0) 但し、a=(an-1,..,a1,a0)、b=(bn-1,..,b1,b0) GF(22)の要素 掛算は多項式表示で行う 通常の掛算。但し、係数はmod 2 　　　　　{0, 1, u, u+1} (0,0) (1,1) GF(22)の乗法 (0,1) ・(1,1) = 1・(u+1) = u+1 u+1 = (1,1) (0,1) (1,0) mod u2+u+1 f(u)で割った余り 既約多項式f(u)

8 乗算（L・u）のアルゴリズム L・uのアルゴリズム f(u)=u128+u7+u2+u+1
ブロック長n=128の場合の既約多項式f(u) L・uのアルゴリズム f(u)=u128+u7+u2+u+1 以下にL・uを計算する。但し、L=(L127,..,L1,L0) L127=0ならば、L・u=(L126,..,L0,0)=L<<1 L127=1ならば、 L・uはu128+L126u L1u2+L0uをf(u)で割った余り。 Lは128ビット 1ビット左シフトと同じ結果になる L・uをf(u)で割る（但し、 L127=1） 1 GF(2)の加法 y u128+u7+u2+1 u128+L126u127+・・+L1u2+L0u 1 x u128+u7+u2+u+1 1 1 1 L126u127+・・+L1u2+L0u -u7-u2-u-1 余り =(L<<1) (u7+u2+u+1) -1とは、1 x=0を満たすx つまり、x=1 1ビット左シフトするとキャリー・ビット(L127)が消える

9 ＭＡＣの標準化 ＥＭＡＣ ＯＭＡＣ その他のＭＡＣ ２００３年ヨーロッパの暗号技術評価プロジェクト ２００３年米国の推奨MAC方式
ＵＭＡＣ（universal-hash MAC） ＨＭＡＣ（hash MAC）