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

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

鍵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

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

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

偽造出来ないように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方式 m1 m2 mt … EK1 EK1 EK1 鍵k2による暗号化 EK2 Tag メッセージ長がブロック長nの整数倍でない場合 oはビット列の連結 iは|mto1o0i|=nとなるように選ぶ OMAC方式 0n m1 m2 … mｔまたはmｔo1o0i 鍵が1つだからone-key L・uまたはL・u2 EK EK EK EK uは拡大体GF(2n)上の要素 ・は拡大体GF(2n)上の乗算 L Tag

拡大体ＧＦ（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)

乗算（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+L126u127+..+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)が消える

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