情報セキュリティ

情報セキュリティ
第４回
メッセージ認証コード
脅威と暗号技術
セキュリティに対する脅威
脅かされる特性
暗号技術
共通鍵暗号
盗聴
（秘密が漏れる）
機密性
公開鍵暗号
改竄
（情報が書き換えられる）
正真性
一方向ハッシュ関数
なりすまし
（正しい送信者のふりをする）
認証
メッセージ認証コード
否認
（後から私じゃないと言う）
否認不可能性
デジタル署名
メッセージ認証コード（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作成
平
文
M
再度、鍵KでTag’作成
送
信
者
(M,Tag)
敵は平文Mを
途中で改竄す
るかもしれない
平
文
M
敵
受
信
者
Tag=Tag’
の場合だ
け受理
Mが改竄され
るとTag≠Tag’
鍵生成
アルゴリズムG
鍵K
認証子生成
アルゴリズムS
認証子
Tag
鍵K
ＭＡＣの安全性
 選択メッセージ攻撃
 敵は自由に選んだメッセージ
M1,..,Mqに対する認証子から
(M,Tag)を偽造する。
 偽造とは：
 受信者が受理する(M,Tag)を
作成することを「偽造」と言う。
 鍵Kを知らなくても偽造できる
場合がある。
 MACが「安全である」とは：
 敵が偽造に成功する確率が
無視できる程小さいならば、
安全である。
 MACはブロック暗号方式
 ブロック暗号で使われる暗号
化アルゴリズムEkは擬似ラン
ダム置換族に属する。
選択メッセージ攻撃
認証子生成
アルゴリズムS
平文
M1,..,Mq
認証子
Tag1,..,Tagq
敵
平文を自由に
選択出来る
偽造
(M,Tag)
偽造とは、受信者が受理する
組(M,Tag)を作ること
ＣＢＣ-ＭＡＣ
CBCモードを
使ったMAC
認証子生成アルゴリズム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が可変ならば、
偽造できる。
 偽造例
1. m∈{0,1}nのTagを得る。
2. このTagは、メッセージ
M=(m,m Tag)の正しい識
選択メッセージ
別子である。
攻撃

認証子生成アルゴリズムS
m1
m2 …
mt
EK
EK
EK
Tag
偽造例
手順２
手順１
m
M=(m,
m
Tag)
Tag
=m
EK
Tag
EK
Tag
EK
Tag
m
Tag
偽造出来ないように
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))
メッセージ長がブロック長n
の整数倍でない場合
EMAC方式
…
m1
m2
EK1
EK1
鍵k2による暗号化
EK1
EK2
Tag
oはビット列の連結
OMAC方式
m2 …
0n m1
mt
iは|mto1o0i|=nとなるように選ぶ
mｔまたはmｔo1o0i
L・uまたはL・u2
鍵が1つだから
one-key
EK
L
EK
EK
EK
Tag
uは拡大体GF(2n)上の要素
・は拡大体GF(2n)上の乗算
拡大体ＧＦ（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)の加法
y 0 1
x
0 0 1
1 1 0
1 0 1
GF(2n)の加法
GF(22)の要素
(0,0)
(1,1)
{0, 1, u, u+1}
(0,1) ・(1,1) = 1・(u+1) = u+1
(0,1)
mod u2+u+1
f(u)で割った余り
u+1 = (1,1)
ベクトル表示
a b=(an-1 bn-1,..,a0 b0)
但し、a=(an-1,..,a1,a0)、b=(bn-1,..,b1,b0)
通常の掛算。但し、
係数はmod 2
GF(22)の乗法
GF(2)の乗法（・）
y 0 1
x
0 0 0
既約多項式f(u)
(1,0)
乗算（L・u）のアルゴリズム
ブロック長n=128の場合の
既約多項式f(u)
 L・uのアルゴリズム
Lは128ビット
 f(u)=u128+u7+u2+u+1
 以下にL・uを計算する。但し、L=(L127,..,L1,L0)
1ビット左シフトと
 L127=0ならば、L・u=(L126,..,L0,0)=L<<1
同じ結果になる
128+L
127+..+L u2+L uをf(u)で割った余り。
 L127=1ならば、 L・uはu
126u
1
0
L・uをf(u)で割る（但し、 L127=1）
GF(2)の加法
y 0 1
x
0 0 1
1
u128+u7+u2+1 u128+L126u127+・・+L1u2+L0u
u128+u7+u2+u+1
余り
L126u127+・・+L1u2+L0u -u7-u2-u-1
=(L<<1) (u7+u2+u+1)
1ビット左シフトするとキャリー・ビット(L127)が消える
-1とは、1
つまり、x=1
1 1 0
x=0を満たすx
ＭＡＣの標準化
 ＥＭＡＣ

２００３年ヨーロッパの暗号技術評価プロジェクト
 ＯＭＡＣ

２００３年米国の推奨MAC方式
 その他のＭＡＣ


ＵＭＡＣ（universal-hash MAC）
ＨＭＡＣ（hash MAC）

Download Report