ブロック暗号利用モードの安全性に関する調査

２００３年１１月

茨城大学
岩田 哲

ブロック暗号利用モードの安全性に関する調査

平成 15 年 11 月
要旨： 本報告書では，現在利用されている，もしくは提案されているブロック暗号
利用モードのうち，主に認証を目的にしているものについて，安全性の観点からその特徴をまとめる．効率についても言及する．

目次
1

序論

1

2

標準化について
2.1 NIST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 ISO/IEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 金融に関するセキュリティ標準 . . . . . . . . . . . . . . . . . . . . . . .
2.4 NESSIE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 3GPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
4
4
5
5
5

3

準備
3.1 記法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 ブロック暗号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 暗号化方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 メッセージ認証コード . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 メッセージ認証つき暗号化方式 . . . . . . . . . . . . . . . . . . . . . . .

6
6
6
6
7
8

4

安全性定義
4.1 ブロック暗号の安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 擬似ランダム置換族 . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 強擬似ランダム置換族 . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3 上記以外のブロック暗号の安全性 . . . . . . . . . . . . . . . . . .
4.2 メッセージ認証コードの安全性 . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 弱偽造不可能性 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 強偽造不可能性 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 MAC-G が決定的アルゴリズムである場合の安全性 . . . . . . . .
4.2.4 上記以外の安全性 . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
9
9
10
10
11
11
12
12
13

5

CBC MAC とその変形
5.1 CBC MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 EMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 RMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 XCBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 TMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 OMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13
13
16
18
25
28
31

6

並列計算可能な MAC
6.1 XOR MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 XECB MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 PMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34
34
39
46

7

その他の MAC
7.1 f 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48
49

8

まとめ

51

参考文献

51

1

序論

本報告書では，現在利用されている，もしくは提案されているブロック暗号利用モードのうち，主に認証を目的にしているものについて，安全性の観点からその特徴をまとめる．効率についても言及する．
ブロック暗号利用モード ブロック暗号は固定長，n ビットの平文を暗号化する．多くのブロック暗号では n = 64 や，n = 128 である．ブロック暗号は，ブロック暗号利用モードのプリミティブとして用いられる．ブロック暗号利用モードの主な機能はメッセージの秘匿 (privacy) と認証 (authenticity) である．本報告書では，秘匿のためのブロック暗号
利用モードを暗号化方式 (encryption scheme), 認証のためのブロック暗号利用モードをメッセージ認証コード (message authentication code) という．また，これらの機能を併せもつブロック暗号利用モードをメッセージ認証つき暗号化方式 (authenticated encryption
scheme) という．

• 暗号化方式はブロック暗号を用いて，n ビットより長いメッセージを暗号化する．
送信者と受信者が秘密鍵 K を共有しており，送信者は暗号化アルゴリズム E を用
いて，平文 M と鍵 K から暗号文 C = EK (M ) を計算し，C を受信者に送る．Mの長さは n ビットよりも長くてよい．受信者は復号アルゴリズム D を用いて，暗号文 C と鍵 K から平文 M = DK (C) を計算する．
例として，ECB, CBC, OFB, CFB, CTR などがある．Fig. 1 参照．

K?

M - 送信者CC ← EK (M )?
- 受信者 - M

M ← DK (C)Fig. 1. 暗号化方式のモデル• メッセージ認証コードはブロック暗号を用いて，メッセージが偽造，改ざんされる
ことを防ぐ技術である．送信者と受信者が秘密鍵 K を共有しており，送信者はタ
グ生成アルゴリズム G を用いて，平文 M と鍵 K からタグ T = GK (M ) を計算し，メッセージ，タグのペア (M, T ) を受信者に送る．M の長さは，n ビットよりも長くてよい．T は固定長であり，32, 64, 96, 128 ビット程度の長さが一般的である．
(M, T ) を受け取った受信者は確認アルゴリズム V を用いて，受理信号，もしくは改ざん検出信号を出力する．V は，受け取ったメッセージに対し，T ∗ = GK (M ) を計算し，T = T ∗ なら受理信号を，そうでなければ改ざん検出信号を出力する．
例として，CBC MAC, EMAC, OMAC, PMAC などがある．Fig. 2 参照．

1

K
?

M - 送信者(M, T )?



- 受信者 -

受理信号
改ざん検出信号T ∗ ← GK (M )T ← GK (M )?

T = T∗
Fig. 2. メッセージ認証コードのモデル• メッセージ認証つき暗号化方式は，暗号化方式とメッセージ認証コードの機能を併せもつ．送信者と受信者が秘密鍵 K を共有しており，送信者は暗号化アルゴリズム
E を用いて，平文 M と鍵 K から暗号文 C = EK (M ) を計算し，C を受信者に送る．
受信者は復号アルゴリズム D を用いて，暗号文 C と鍵 K から平文 M = DK (C)を，もしくは改ざん検出信号を出力する．
例として，CCM, IAPM, OCB などがある．また，任意の暗号化方式とメッセージ
認証コードを組み合わてメッセージ認証つき暗号化方式を構成する方法が知られている．Fig. 3 参照．

K?

M - 送信者CC ← EK (M )?

- 受信者 -

M
改ざん検出信号M or 改ざん検出信号 ← DK (C)Fig. 3. メッセージ認証つき暗号化方式のモデル

ブロック暗号利用モードの安全性 Bellare, Kilian, Rogaway により，CBC MAC の安全性が数学的に示された [7]．ブロック暗号が安全な擬似ランダム置換族であれば，CBC
MAC は偽造不可能性の意味で安全であることを示している．以降，多くのブロック暗号
利用モードの安全性は，この種の証明可能安全性を根拠にしている．以下，暗号化方式，
メッセージ認証コード，メッセージ認証つき暗号化方式，それぞれについて，安全性の定義を概説する．

• 暗号化方式に対しては，いくつかの安全性定義が存在する [5] が，ランダムビット
列からの識別不能性 (indistinguishability from random strings) が一般的である．暗号文 C か，もしくは C と同じ長さのランダムビット列 R が与えられ，有意な確率でこの 2 つを見分けることができないとき，暗号化方式は安全である，という．

2• メッセージ認証コードに対しては，偽造不可能性 (unforgeability) が一般的である．
(鍵 K を知らずに) T = GK (M ) となる (M, T ) を出力できないとき，メッセージ認証コードは安全である，という．
• メッセージ認証つき暗号化方式では，暗号化方式の安全性定義とメッセージ認証コードの安全性定義の両方を考える．
– 暗号文 C か，もしくは C と同じ長さのランダムビット列 R が与えられ，有意な確率でこの 2 つを見分けることができない．
– (鍵 K を知らずに) 改ざん検出信号 = DECK (C) となる C を出力できない．
上記二つが成り立つとき，メッセージ認証つき暗号化方式は安全である，という．
ブロック暗号利用モードの効率 本報告書は，安全性を主眼においているが，効率についても述べる．主に以下の点について述べる．

• 鍵長：安全性が変わらないのであれば，短いほうがよい．
• ブロック暗号鍵スケジューリングの呼び出し回数：一般的にブロック暗号鍵スケ
ジューリングは計算時間がかかり，安全性が変わらないのであれば，少ないほうがよい．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：
安全性が変わらないのであれば，少ないほうがよい．
• 事前計算するべきブロック暗号の呼び出し回数：これらは，メッセージ M によらず実行できる．安全性が変わらないのであれば，少ないほうがよい．
• 並列処理性：ブロック暗号の並列処理が可能であれば，ハードウェア上で高速に実装できる．
本報告書の構成 2 章でブロック暗号利用モードに関連する標準の文書についてまとめる．3 章では，ブロック暗号利用モードの一般的な定義を述べる．4 章では，ブロック暗号，およびメッセージ認証コードの一般的な安全性の定義を述べる．5 章では CBC MACとその変形を扱う．CBC MAC, EMAC, RMAC, XCBC, TMAC, OMAC について，仕様と安全性，効率，標準化状況などについて述べる．6 章では並列計算可能なメッセー
ジ認証コードを扱う．XOR MAC, XECB MAC, PMAC について，仕様と安全性，効率，
標準化状況などについて述べる．7 章ではその他の MAC として，f 9 について述べる．
なお，本報告書の記述はブロック暗号利用モードの仕様を定義するものではない．これらモードの利用と実装にあたっては，各標準の文書などを参照して頂きたい．

2

標準化について本章では，標準化について述べる．

3

2.1

NIST

米国 NIST (National Institute of Standards and Technology) は，FIPS (Federal Information Processing Standard) と SP (Special Publications) を策定しており，暗号技術関連の標準も含まれている．ブロック暗号利用モードに関する主なものは以下のとおりである．

FIPS 46-2 DES ANSIFIPS 81
DES 利用モード，ECB, CBC, CFB, OFB
FIPS 113 CBC MAC
FIPS 197 AES
2001 年 11 月の AES の FIPS の策定に伴い，NIST は AES の利用モードを策定中である．2003 年 11 月現在で提案された利用モードを以下に挙げる．
暗号化方式
2DEM
ABC
CTR
IGE

メッセージ認証コード
OMAC
PMAC
RMAC
TMAC
XCBC
XECB

メッセージ認証つき暗号化方式
CCM
CWC
EAX
IACBC
IAPM
OCB
PCFB
XCBC

その他
KFB
AES-hash2003 年 11 月現在，5 つの秘匿に関する利用モードが SP800-38A [47] として定義されている．これには，FIPS 81 で定義した 4 つのモードと，あたらに CTR が加えられた．
SP800-38B のドラフト版は，メッセージ認証コードとして，RMAC を，また，SP800-38Cのドラフト版では，メッセージ認証つき暗号化方式として，CCM を定義している．以下にまとめる．
SP800-38A
SP800-38B
SP800-38C

暗号化方式 (ECB, CBC, CFB, OFB, CTR)
メッセージ認証コード (RMAC, ドラフト版である)
メッセージ認証つき暗号化方式 (CCM, ドラフト版である)

SP800-38B と，SP800-38C はドラフト版であり，今後の動向を注視する必要がある．

2.2

ISO/IEC

ISO (International Organization for Standardization), 及び，IEC (International Electrotechnical Commission) は，個々の標準の他に，一部の国際規格を共同で策定している．
日本では ISO/IEC の標準化をうけて，日本語化したものを JIS として発行している．
ブロック暗号利用モードに関する標準化文書として主なものを挙げる．

4

ISO 8372 64 ビットブロック暗号利用モードである．4 つの暗号化方式 ECB, CBC,
CFB, OFB を定めている．DES に関する FIPS 81 と ANSI X3.106 を一般化し，任意の64 ビットブロック暗号を対象としたものになっている．
ISO 9797 メッセージ認証コードである．CBC MAC を定めている．同様の標準として，ISO 8731-1, ISO 9807, ANSI X9.9, ANSI X9.19 がある．
ISO 10116 ISO 8372 を n ビットブロック暗号について定めたものである．

2.3

金融に関するセキュリティ標準

ANSI X3 ANSI (American National Standards Institute) では，以下の 2 つの標準を定めている．
ANSI X3.92 FIPS 46 で定められている DES
ANSI X3.106 FIPS 81 で定められている DES の利用モード
ANSI X9 ANSI X9 シリーズでは，以下の標準を定めている．
ANSI X9.9
ANSI X9.19
ANSI X9.23
ANSI X9.52

メッセージ認証コード, CBC MAC
メッセージ認証コード, CBC MAC
メッセージ暗号化
Triple DES と利用モード

ISO ISO の TC68 では金融サービスのためのセキュリティ標準を定めている．以下の標準を定めている．
ISO 8731-1 メッセージ認証コード, CBC MAC
ISO 10126 メッセージ暗号化

2.4

NESSIENESSIE (New European Schemes for Signatures, Integrity, and Ecnryption) [40] はヨーロッパで 2000 年 1 月に開始された 3 年間のプロジェクトで，ブロック暗号，メッ
セージ認証コード，公開鍵暗号，ハッシュ関数といった暗号プリミティブの評価を行うことを目的としている．2003 年 2 月の最終報告書が公開され，メッセージ認証コードではEMAC が portfolio に含まれた．

2.5

3GPP

3GPP (3rd Generation Partnership Project) では，ブロック暗号 KASUMI 及び，その利用モードが策定されている．暗号化方式として f 8 が，メッセージ認証コードとして
f 9 が策定されている [1, 2]．

5

3

準備

本章では本報告書で扱う記法をまとめるとともに，ブロック暗号，およびその利用モードの一般的な定義と，安全性の定義を述べる．

3.1

記法
R

A が集合である場合，a ← A は A から a を一様ランダムに選ぶことをあらわす．A がアルゴリズムである場合，a ← A は A の実行結果を a とする，ということをあらわす．A
Rが確率的アルゴリズムでれば，a ← A と表記する．整数 l に対し，{0, 1}l はすべての l ビット列の集合をあらわす．また，{0, 1}≤l は，l ビット以下のすべてのビット列の集合をあらわす．長さ 0 のビット列 ε もこれに含める．同様に，({0, 1}l )+ は，長さが l の整数倍のす
べてのビット列からなる集合をあらわす．すなわち，({0, 1}l )+ = l =1,2,... {0, 1}ll である．

同様に，{0, 1}∗ は，すべてのビット列の集合を表す．すなわち，{0, 1}∗ = l=0,1,2,... {0, 1}lである．a と b が同じ長さのビット列であれば，a ⊕ b はそれらのビットごとの排他的論
理輪をあらわす．a がビット列のとき，|a| は a のビット長をあらわす．

3.2

ブロック暗号

ブロック暗号 (block cipher) E とは，E : KE × ME → ME なる関数である．KE は，
鍵空間とよばれ，KE = {0, 1}k のとき，k を鍵長という．ME は，メッセージ空間，もしくは平文空間とよばれ，ME = {0, 1}n のとき，n をブロック長という．ただし，すべての K ∈ KE に対し，E(K, ·) は ME 上の置換でなくてはならない．E(K, ·) は ME 上の置換なので，その逆関数 E −1 (K, ·) が存在する．すべての鍵 K ∈ KE とすべての平文
X ∈ ME に対し，E −1 (K; E(K, X)) = X であり，すべての鍵 K ∈ KE とすべての暗号
文 Y ∈ ME に対し，E(K; E −1 (K, Y )) = Y である．関数 E(K; ·) を暗号化関数，関数−1
E −1 (K; ·) を復号関数という．それぞれ EK (·), EK(·) と表記する．

3.3

暗号化方式

暗号化方式 (encryption scheme) はメッセージ秘匿のためのブロック暗号利用モードである．暗号化方式 ENC は，三つのアルゴリズム ENC = (ENC-K, ENC-E, ENC-D) から成る．ENC-K を鍵生成アルゴリズム，ENC-E を暗号化アルゴリズム，ENC-D を復号
アルゴリズムという．また，メッセージ空間 MENC をもつ．
ここで，鍵生成アルゴリズム ENC-K は確率的アルゴリズムであり，入力はなく，ラR
ンダムな鍵 K を出力する．K ← ENC-K と表記する．暗号化アルゴリズム ENC-E は，確率的，決定的，状態をもつ，もしくは nonce を利用するアルゴリズムである．鍵 K
Rとメッセージ M ∈ MENC を入力とし，暗号文 C を出力する．C ← ENC-E(K; M ) や
C ← ENC-E(K; M ) と表記する．また，乱数や状態を明示的に入力に示すこともある．
暗号化アルゴリズムが確率的アルゴリズムである場合，入力 (K, M ) が与えられるた6

びに乱数を選び，それを用いて暗号文 C を計算する．アルゴリズムが呼び出されるたびに乱数を選びなおす．同じ入力で 2 度アルゴリズムを呼び出したとしても，同じ出力になるとは限らない．
暗号化アルゴリズムが状態をもつアルゴリズムである場合，まずある定められた方法に従って状態を初期化する．入力 (K, M ) が与えられると，(K, M ) と現在の状態に応じて暗号文 C を計算し，状態を更新し，新しい状態を保持する．多くの場合，状態は単な
るカウンタである．
暗号化アルゴリズムが nonce を用いるアルゴリズムである場合，メッセージごとに異なる値である nonce を用いる．メッセージを数えるカウンタは，メッセージごとに異なる値であるので，nonce として用いることができる．ただし，nonce はカウンタのように値が増える (あるいは減る) 必要はなく，単に異なるメッセージに対しては，異なる値であればよい．
復号アルゴリズム ENC-D は，決定的アルゴリズムであり，鍵 K と暗号文 C を入力とし，メッセージ M を出力する．M ← ENC-D(K; C) と表記する．
全ての鍵 K と全てのメッセージ M に対し，

ENC-D(K; ENC-D(K; M ))) = M
でなければならない．
ENC-E(K; ·) と ENC-D(K; ·) を，ENC-EK (·) や ENC-DK (·) と表記する．
例として，一般的な ECB, CBC, OFB, CFB, CTR [47], ディスク暗号化用の NR [39],
CMC [22], 3GPP の f 8 [1, 2] などがある．

3.4

メッセージ認証コード

メッセージ認証コード (Message Authentication Code, MAC) MAC は，メッセージ認証のためのブロック暗号利用モードである．メッセージ認証コード MAC は，三つのアルゴリズム MAC = (MAC-K, MAC-G, MAC-V) から成る．MAC-K を鍵生成アルゴリズ
ム，MAC-G をタグ生成アルゴリズム，MAC-V を確認アルゴリズムという．また，メッセージ空間 MMAC とタグ空間 TMAC をもつ．
鍵生成アルゴリズム MAC-K は確率的アルゴリズムであり，入力はなく，鍵 K を出力Rする．K ← MAC-K と表記する．
タグ生成アルゴリズム MAC-G は，確率的，決定的，もしくは状態をもつアルゴリズ
ムである．鍵 K とメッセージ M ∈ MMAC を入力とし，タグ T ∈ TMAC を出力する．
R
T ← MAC-G(K; M ) や T ← MAC-G(K; M ) と表記する．また，乱数や状態を明示的に入力に示すこともある．
MAC-G が確率的アルゴリズムである場合，入力 (K, M ) が与えられるたびに乱数を選び，それを用いてタグ T を計算する．アルゴリズムが呼び出されるたびに乱数を選びなおす．同じ入力で 2 度アルゴリズムを呼び出したとしても，同じ出力になるとは限らない．
MAC-G が状態をもつアルゴリズムである場合，まずある定められた方法に従って状態を初期化する．入力 (K, M ) が与えられると，(K, M ) と現在の状態に応じてタグ T を7

計算し，状態を更新し，新しい状態を保持する．多くの場合，状態は単なるカウンタである．
確認アルゴリズム MAC-V は，決定的アルゴリズムであり，鍵 K, メッセージ M ∈MMAC , タグ T ∈ TMAC を入力とし，accept or reject を出力する．MAC-V(K; M ; T ) =accept や，MAC-V(K; M ; T ) = reject と表記する．
全ての鍵 K と全てのメッセージ M に対し，

MAC-V(K; M ; MAC-G(K; M ))) = accept
でなければならない．
MAC-G(K; ·) と MAC-V(K; ·; ·) を，MAC-GK (·) や MAC-VK (·, ·) と表記する．
例として，CBC MAC [7], EMAC [10, 42], RMAC [29, 30, 31], XCBC [12], TMAC [36],
OMAC [26], XOR MAC [6], XECB MAC [20], PMAC [14], f 9 [1, 2] などがある．

3.5

メッセージ認証つき暗号化方式

メッセージ認証つき暗号化方式 (authenticated encryption scheme) はメッセージ秘匿とメッセージ認証の機能を併せ持つブロック暗号利用モードである．メッセージ認証つ
き暗号化方式 AE は，三つのアルゴリズム AE = (AE-K, AE-E, AE-D) から成る．AE-K
を鍵生成アルゴリズム，AE-E を暗号化アルゴリズム，AE-D を復号アルゴリズムという．また，メッセージ空間 MAE をもつ．
ここで，鍵生成アルゴリズム AE-K は確率的アルゴリズムであり，入力はなく，ランダR
ムな鍵 K を出力する．K ← AE-K と表記する．暗号化アルゴリズム AE-E は，確率的，決定的，状態をもつ，もしくは nonce を利用するアルゴリズムである．鍵 K とメッセージRM ∈ MAE を入力とし，暗号文 C を出力する．C ← AE-E(K; M ) や C ← AE-E(K; M )と表記する．また，乱数や状態を明示的に入力に示すこともある．
復号アルゴリズム AE-D は，決定的アルゴリズムであり，鍵 K と暗号文 C を入力とし，メッセージ M , もしくは改ざん検出信号を出力する．M ← AE-D(K; C) や，
改ざん検出信号 ← AE-D(K; C) と表記する．
全ての鍵 K と全てのメッセージ M に対し，

AE-D(K; AE-D(K; M ))) = M
でなければならない．
AE-E(K; ·) と AE-D(K; ·) を，AE-EK (·) や AE-DK (·) と表記する．
例として，IACBC, IAPM [33], OCB [46], XCBC [20], CCM [51, 32], CWC [34], EAX[9] などがある．

4

安全性定義
本章では，ブロック暗号とメッセージ認証コードの一般的な安全性定義を述べる．

8

4.1

ブロック暗号の安全性

ブロック暗号の代表的な安全性の定義として，擬似ランダム置換 (pseudorandom permutation) としての安全性と強擬似ランダム置換 (super-pseudorandom permutation, あ
るいは strong-pseudorandom permutation) としての安全性がある．

4.1.1

擬似ランダム置換族

ブロック暗号 E : KE × ME → ME は，ME 上の置換族 {EK (·) ∈ Perm(ME ) | K ∈KE } と捉えることができる．ここで，Perm(ME ) は ME 上のすべての置換の集合である．
直感的に，「あるブロック暗号が擬似ランダム置換族である」とは，適応的選択平文攻撃を行う任意の敵が，置換族 {EK (·) ∈ Perm(ME ) | K ∈ KE } と ME 上のすべての置換の集合 Perm(ME ) を区別できないことをいう．
より厳密には，敵 A として，オラクルにアクセスできるアルゴリズムを考える．何回かの質問の後，A は 1 ビットを出力する．ブロック暗号 E : KE × ME → ME の，敵 A
prpに対する，擬似ランダム置換としての安全性は，アドバンテージ AdvE (A) によって評価される．ここで，


R
R
def 

EK (·)P (·)
Advprp
(A)
=
←
K
:
A
=
1)
−
Pr(P
←
Perm(M
)
:
A
=
1)
Pr(K


E
E
E
と定義され，AEK (·) は質問 X に対し，Y = EK (X) を返すオラクル EK (·) を持つ敵 Aを表し，AP (·) は質問 X に対し，Y = P (X) を返すオラクル P (·) を持つ敵 A を表す．
特に断りがなければ，質問は適応的に行う．すなわち，ある質問に対する答えを得た後，次の質問を行う．
Perm(ME ) から一様ランダムにえばられた P を ME 上のランダム置換，あるいは単に，ランダム置換という．
計算量理論的安全性 上記の定義はある一つの敵に対する評価である．一般的に，敵が利用できる資源をパラメータにし，そのパラメータを利用するすべての敵の最大のアドバンテージを考える．ブロック暗号の擬似ランダム置換族としての安全性を考える場合に扱う資源は，実行時間 t とオラクルへの質問回数 q である．ここで，実行時間に関しては，ある計算のモデルが固定されているとする．その単位時間によって，ランダムにK を選ぶ時間や，EK (X) の計算にかかる時間があらわせるものとする．また，実行時間
t には，A の記述に要する長さ (A を記述するプログラムの長さ) が含まれているものとし，また，A の実行に関するすべての時間が含まれる．これにはランダムに K を選ぶ時
間や，(オラクルとの) 入出力にかかる時間，等も含まれる．以降のすべての実行時間 tは同様に定義される．
def
prp
AdvprpE (t, q) = max {Adv E (A)}Aと定義される．ただし，最大値は実行時間 t, オラクルへの質問回数 q のすべての敵 A についてとる．
この定義においては，正確には「安全な擬似ランダム置換族」という概念は存在しな
prp
い．すべてのブロック暗号 E は，ある大きさの AdvE (t, q) をもつ置換族である．
「E が9

安全な擬似ランダム置換族である」や，「E が擬似ランダム置換族である」という表現や仮定は，「適当に大きい t と q に対し，Advprp
E (t, q) が十分小さい」ということを意図している．厳密な安全性の定理を言う場合にはこれらの表現は用いない．

4.1.2

強擬似ランダム置換族「あるブロック暗号が強擬似ランダム置換族である」とは，適応的選択平文暗号文攻撃を行う任意の敵が，置換族 {EK (·) ∈ Perm(ME ) | K ∈ KE } と ME 上のすべての置換の集合 Perm(ME ) を区別できないことをいう．
より厳密には，敵 A として，2 つのオラクルにアクセスできるアルゴリズムを考える．
何回かの質問の後，A は 1 ビットを出力する．ブロック暗号 E : KE × ME → ME の，
敵 A に対する，強擬似ランダム置換としての安全性は，アドバンテージ Advsprp
E (A) によって評価される．ここで，


−1
R
R
def 

EK (·),EK(·)
P (·),P −1 (·)
Pr(KAdvsprp
(A)
=
←
K
:
A
=
1)
−
Pr(P
←
Perm(M
)
:
A
=
1)


E
E
E
−1

と定義され，AEK (·),EK (·) は質問 X に対し，Y = EK (X) を返す暗号化オラクル EK (·) と，−1−1−1
質問 Y に対し，X = EK(Y ) を返す復号オラクル EK(·) を持つ敵 A を表し，AP (·),P (·)
は質問 X に対し，Y = P (X) を返す暗号化オラクル P (·) と，質問 Y に対し，X = P −1(Y )を返す復号オラクル P −1 (·) を持つ敵 A を表す．特に断りがなければ，質問は適応的に行う．すなわち，ある質問に対する答えを得た後，次の質問を行う．
計算量理論的安全性 ブロック暗号の強擬似ランダム置換族としての安全性を考える場
合に扱う資源は，実行時間 t, 暗号化オラクルへの質問回数 qe , 復号オラクルへの質問回
数 qd である．
def
sprp
Advsprp
E (t, qe , qd ) = max {Adv E (A)}Aと定義される．ただし，最大値は実行時間 t, 暗号化オラクルへの質問回数 qe , 復号オラ
クルへの質問回数 qd のすべての敵 A についてとる．
一般に，「E が安全な強擬似ランダム置換族である」や，「E が強擬似ランダム置換族でsprpある」という表現は，「適当に大きい t, qe , qd に対し，AdvE (t, qe , qd ) が十分小さい」ということを意図している．

4.1.3

上記以外のブロック暗号の安全性

上記以外にもブロック暗号の安全性定義がいくつか存在する．鍵関連攻撃を考慮した安全性定義 [8] などがこれに含まれる．
また，理想的ブロック暗号モデル (ideal-block cipher model) というブロック暗号のモデル化がある．ハッシュ関数のランダムオラクルに対応するものであり，RMAC [29, 30]の安全性解析に用いられた．

10

4.2

メッセージ認証コードの安全性

メッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) の安全性には，弱偽造不可
能性 (weak unforgeability) と強偽造不可能性 (strong unforgeability) がある．
どちらの場合も，敵 A として，タグ生成オラクルと確認オラクルにアクセスできる
アルゴリズムを考える．AMAC-GK (·),MAC-VK (·,·) は，メッセージ M に対し，タグ T =MAC-GK (M ) を返すタグ生成オラクル MAC-GK (·) と，メッセージ，タグのペア (M, T )に対し，accept or reject = MAC-VK (M, T ) を返す確認オラクル MAC-VK (·, ·) をもつ敵をあらわす．質問は適応的に行う．すなわち，ある質問に対する答えを得た後，次の質問
を行う．

4.2.1

弱偽造不可能性

弱偽造不可能性の意味でメッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) を破ろうとする敵 A が，タグ生成オラクルに q 個のメッセージ M1 , . . . , Mq を質問し，その答え T1 , . . . , Tq を得たとする．また，確認オラクルに q  個のメッセージ，タグのペア(M1 , T1 ), . . . , (Mq  , Tq ) を質問したとする．
ある i に対し，MAC-VK (Mi , Ti) = accept であり，Mi ∈ {M1 , . . . , Mj } であれば，Aは弱偽造不可能性の意味で偽造に成功した，という．ここで，{M1 , . . . , Mj } は，(Mi , Ti )を確認オラクルに質問する以前に，タグ生成オラクルに送った質問である．
直感的には，見たことのないメッセージに対するタグを出力できたらなば，偽造に成功したことになる．
メッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) の，敵 A に対する，弱偽造不可能性の意味での安全性は，アドバンテージ Advw-uf
E (A) によって評価される．こ
こで，
def

R

MAC-GK (·),MAC-VK (·,·)
Advw-ufがMAC (A) = Pr(K ← MAC-K : A
弱偽造不可能性の意味で偽造に成功)と定義される．
計算量理論的安全性 メッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) の，弱偽造不可能性の意味での安全性を考える場合に扱う資源は，実行時間 t, タグ生成オラク
ルへの質問回数 q, それら質問の長さ σ (ビット単位，もしくはブロック単位)，確認オラ
クルへの質問回数 q  , それら質問の長さ σ  (ビット単位，もしくはブロック単位) である．
実行時間 t はブロック暗号と同様に定義される．



w-uf

 def
Advw-uf
MAC (t, q, σ, q , σ ) = max AdvMAC (A)Aと定義される．ただし，最大値は実行時間 t, タグ生成オラクルへの質問回数 q, それら質問の長さ σ, 確認オラクルへの質問回数 q  , それら質問の長さ σ  のすべての敵 A につい
てとる．

11

4.2.2

強偽造不可能性

強偽造不可能性の意味でメッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) を破ろうとする敵 A が，タグ生成オラクルに q 個のメッセージ M1 , . . . , Mq を質問し，その答え T1 , . . . , Tq を得たとする．また，確認オラクルに q  個のメッセージ，タグのペア(M1 , T1 ), . . . , (Mq  , Tq ) を質問したとする．
ある i に対し，MAC-VK (Mi , Ti ) = accept であり，(Mi , Ti ) ∈ {(M1 , T1 ), . . . , (Mj , Tj )}であれば，A は強偽造不可能性の意味で偽造に成功した，という．{(M1 , T1 ), . . . , (Mj , Tj )}は，(Mi , Ti) を確認オラクルに質問する以前に，タグ生成オラクルに送った質問とその答えである．
直感的には，見たことのないメッセージ，タグのペアを出力できたらなば，偽造に成功したことになる．タグが異なっていれば，メッセージ自体は見たことがあってもよい．
メッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) の，敵 A に対する，強偽造不可能性の意味での安全性は，アドバンテージ Advs-uf
E (A) によって評価される．ここで，
def

R

MAC-GK (·),MAC-VK (·,·)
Advs-ufがMAC (A) = Pr(K ← MAC-K : A
強偽造不可能性の意味で偽造に成功)と定義される．
計算量理論的安全性 メッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) の，強偽造不可能性の意味での安全性を考える場合に扱う資源は，弱偽造不可能性の場合と同
様である．


s-uf

 def
Advs-uf
MAC (t, q, σ, q , σ ) = max AdvMAC (A)Aと定義される．ただし，最大値は実行時間 t, タグ生成オラクルへの質問回数 q, それら質問の長さ σ, 確認オラクルへの質問回数 q  , それら質問の長さ σ  のすべての敵 A につい
てとる．

4.2.3

MAC-G が決定的アルゴリズムである場合の安全性

MAC-G が決定的アルゴリズムの場合，弱偽造不可能性の意味での安全性と強偽造不可能性の意味での安全性は同一の定義となる．また，この場合，タグ生成オラクルが確
認オラクルのかわりになり得る．すなわち，タグ生成オラクルに Mi を質問し，Ti を得たなら，確認オラクルは質問 (Mi , Ti ) に対しては accpet を返し，質問 (Mi , Ti) (ただしTi = Ti ) に対しては reject を返す．したがって，q  と σ  のパラメータを用いないで，qと σ にこれらを含めるのが一般的である．MAC-G が決定的アルゴリズムの場合，弱偽造不可能性と強偽造不可能性とを区別せず，単に偽造不可能性 (unforgeability) という．
敵 A として，タグ生成オラクルにアクセスできるアルゴリズムを考える．AMAC-GK (·)
は，メッセージ M に対し，タグ T = MAC-GK (M ) を返すタグ生成オラクル MAC-GK (·)
をもつ敵をあらわす．質問は適応的に行う．すなわち，ある質問に対する答えを得た後，次の質問を行う．

12

偽造不可能性の意味でメッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) を破ろうとする敵 A がタグ生成オラクルにメッセージ M1 , . . . , Mj を質問し，その答え
T1 , . . . , Tj を得たとする．タグ生成オラクルへの質問の途中，A は偽造文 (Mj+1 , Tj+1 ) を出力する．
MAC-VK (Mj+1 , Tj+1 ) = accept であり，Mj+1 ∈ {M1 , , . . . , Mj } であれば，A は偽造不可能性の意味で偽造に成功した，という．{M1 , . . . , Mj } は，(Mj+1 , Tj+1 ) を出力する
以前に，タグ生成オラクルに送った質問である．ある偽造文が reject された場合でも，
A はさらにタグ生成オラクルに質問を続け，あたらな偽造文を出力してよい．ただし，(Mj+1 , Tj+1 ) はタグ生成オラクルに対する質問として数える．
直感的には，見たことのないメッセージに対するタグを出力できたらなば，偽造に成功したことになる．
メッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) の，敵 A に対する，偽造不可能性の意味での安全性は，アドバンテージ Advmac
MAC (A) によって評価される．ここで，MAC-GK (·)
Advmacが偽造不可能性の意味で偽造に成功)
MAC (A) = Pr(K ← MAC-K : A
defRと定義される．
計算量理論的安全性 メッセージ認証コード MAC = (MAC-K, MAC-G, MAC-V) の，偽造不可能性の意味での安全性を考える場合に扱う資源は，実行時間 t, タグ生成オラクル
への質問回数 q (M  を含む), それら質問の長さ σ (ビット単位，もしくはブロック単位，
M  の長さも含む) である．実行時間 t はブロック暗号と同様に定義される．
defmac
Advmac
MAC (t, q, σ) = max {Adv MAC (A)}Aと定義される．ただし，最大値は実行時間 t, タグ生成オラクルへの質問回数 q, それら質問の長さ σ のすべての敵 A についてとる．

4.2.4

上記以外の安全性

上記以外にもいくつかの安全性定義が存在する．それらについては，そのつど説明をする．

5

CBC MAC とその変形本章では，CBC MAC とその変形として，CBC MAC, EMAC, RMAC, XCBC, TMAC,
OMAC について述べる．

5.1

CBC MACCBC MAC には，パディングの方法や，最終ブロックの処理など，いくつもの仕様がある．次に述べる仕様は，最も単純なものである．

13

方式 CBC MAC はブロック暗号 E, タグ長 τ , (メッセージ長を規定する) 定数 m をパラ
メータとする．ブロック長 n のブロック暗号 E : KE × {0, 1}n → {0, 1}n を用いた場合は，
τ ≤ n でなくてはならない．これらのパラメータを用いた CBC MAC を CBC[E, τ, m]と表記する．CBC[E, τ, m] = (CBC-K, CBC-G, CBC-V) の鍵生成アルゴリズム CBC-K,
タグ生成アルゴリズム CBC-G, 確認アルゴリズム CBC-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム CBC-K は確率的アルゴリズムであり，K ← KE を出力する．
• タグ生成アルゴリズム CBC-G : KE × {0, 1}mn → {0, 1}τ は決定的アルゴリズムであり，鍵空間は KE , メッセージ空間は {0, 1}mn, タグ空間は {0, 1}τ である．すなわ
ち，鍵 K ∈ KE とメッセージ M ∈ {0, 1}mn を入力とし，タグ T = CBC-GK (M ) ∈{0, 1}τ を出力する．Fig. 4, Fig. 5 にあるように動作する．Fig. 5 において，trunc
は n ビットの入力のうち，左 τ ビットを出力する．
Algorithm CBC-GK (M )Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← EK (X[i])T ← the left most τ bits of Y [m]return T
Fig. 4. CBC MAC のタグ生成アルゴリズム CBC-GK (·).
M [1]
?

K- E

M [2]

M [3]

-?
g

-?
g

?

K- E

?

K- E

?

τ - trunc?

T

Fig. 5. M = M [1]M [2]M [3] の場合の CBC-GK (M ) の動作．

• 確認アルゴリズム CBC-V : KE × {0, 1}mn × {0, 1}τ → accept or reject は決定的ア
ルゴリズムであり，鍵 K ∈ KE , メッセージ M ∈ {0, 1}mn, タグ T ∈ {0, 1}τ を入力とし，accept or reject = CBC-VK (M, T ) を出力する．Fig. 6 にあるように動作する．
安全性 Bellare, Kilian, Rogaway により，安全性が解析されている [7]. ブロック暗号 Eが安全な擬似ランダム置換族であれば，CBC[E, τ, m] = (KCBC , GCBC , VCBC ) は，偽造不14Algorithm CBC-VK (M, T )T  ← CBC-GK (M )if T = T  then return accept
else return rejectFig. 6. CBC MAC の確認アルゴリズム CBC-VK (·, ·).
可能性の意味で安全な MAC であることが示されている．(タグ生成アルゴリズムは決定的なので，この場合，弱偽造不可能性と強偽造不可能性は同一の定義になる．) 以下の定理が示されている．
定理 5.1 n, m ≥ 1 を整数，t, q を qm ≤ 2(n+1)/2 なる整数とする．E : KE × {0, 1}n →{0, 1}n をブロック暗号とする．このとき，

2q 2 m2prp  mac
AdvCBC[E,τ,m] (t, q, mq) ≤ AdvE (t , q ) +
+
n
2

1
2τ

である．ただし，q  = mq, t = t + O(nmq) であり，質問の長さはブロック単位である．
直感的に，定理 5.1 は，以下のことを示している： 実行時間 t, 高々 q 回の質問の後，AdvmacCBC[E,τ,m] (A) = 
で偽造に成功する敵が存在すると仮定する．このとき，実行時間 t = t + O(nmq), 高々
q  = mq 回の質問の後，
2q 2 m2
1
Advprp
(B)
≥

−
− τ
E
n
2
2
なる敵 B が存在する．
しかし，上記の定理はメッセージ空間が，ある定数 m に対し，{0, 1}mn となっていな
ければならない．そうでない場合，特に可変長のメッセージ空間 (たとえば ({0, 1}n )+ )に対しては，CBC MAC は安全な MAC ではなくなる．たとえば，図 7 の敵 A は，メッセージ空間を ({0, 1}n )+ とした CBC MAC を偽造不可能性の意味で破る敵である．また，その成功確率は 1 である．

Algorithm ACBC-GK (·)
M ← 0nT ← CBC-GK (M )M  ← (M, T )return (M  , T )Fig. 7. ACBC-GK (·) .

15

効率

CBC MAC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号の鍵 K ∈ KE 一つのみである．
• ブロック暗号鍵スケジューリングの呼び出し回数：1 回である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：(|M |/n) 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：必要ない．
• 並列処理性：並列処理はできない．
標準化状況 広範囲にわたって標準化されている．FIPS 113, ISO 9797, ISO 8731-1, ISO
9807, ANSI X9.9, ANSI X9.19 に含まれている．
なお，メッセージ長の問題を解決するために，パディング，最終出力の前に暗号化を施すなど，いくつかの変形がある．正確な仕様については，各標準の文書を参照されたい．

5.2

EMAC

方式 EMAC はブロック暗号 E とタグ長 τ をパラメータとする．ブロック長 n のブ
ロック暗号 E : KE × {0, 1}n → {0, 1}n を用いた場合は，τ ≤ n でなくてはならな
い．これらのパラメータを用いた EMAC を EMAC[E, τ ] と表記する．EMAC[E, τ ] =(EMAC-K, EMAC-G, EMAC-V) の鍵生成アルゴリズム EMAC-K, タグ生成アルゴリズ
ム EMAC-G, 確認アルゴリズム EMAC-V はそれぞれ以下のように動作する．
R

R• 鍵生成アルゴリズム EMAC-K は確率的アルゴリズムであり，K1 ← KE と K2 ← KEを出力する．
• タグ生成アルゴリズム EMAC-G : (KE )2 × ({0, 1}n )+ → {0, 1}τ は決定的アルゴリ
ズムであり，鍵空間は (KE )2 , メッセージ空間は ({0, 1}n )+ , タグ空間は {0, 1}τ である．すなわち，鍵 K1 , K2 ∈ KE とメッセージ M ∈ ({0, 1}n )+ を入力とし，タグ T = EMAC-GK1 ,K2 (M ) ∈ {0, 1}τ を出力する．Fig. 8, Fig. 9 にあるように動作する．
• 確認アルゴリズム EMAC-V : (KE )2 × ({0, 1}n)+ × {0, 1}τ → accept or reject は決定的アルゴリズムであり，鍵 K1 , K2 ∈ KE , メッセージ M ∈ ({0, 1}n )+ , タ
グ T ∈ {0, 1}τ を入力とし，accept or reject = EMAC-VK1 ,K2 (M, T ) を出力する．
Fig. 10 にあるように動作する．
安全性 Petrank, Rackoﬀ により，安全性が解析されている [42]. ブロック暗号 E が安
全な擬似ランダム置換族であれば，EMAC[E, τ ] = (EMAC-K, EMAC-G, EMAC-V) は，
偽造不可能性の意味で安全な MAC であることが示されている．以下の定理が示されている．

16

Algorithm EMAC-GK1 ,K2 (M )Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← EK1 (X[i])T ← the left most τ bits of EK2 (Y [m])return T
Fig. 8. EMAC のタグ生成アルゴリズム EMAC-GK1 ,K2 (·).
M [1]
?

K1- E

M [2]

M [3]

-?
g

-?
g

?

K1- E

?

K1- E

?

K2- E

?

τ - trunc?

T

Fig. 9. M = M [1]M [2]M [3] の場合の EMAC-GK1 ,K2 (M ) の動作．

Algorithm EMAC-VK1 ,K2 (M, T )T  ← EMAC-GK1 ,K2 (M )if T = T  then return accept
else return rejectFig. 10. EMAC の確認アルゴリズム EMAC-VK1 ,K2 (·, ·).

17

定理 5.2 n, τ ≥ 1 を整数，t, q, σ ≥ 1 を σ 2 ≤ 2(n+1)/2 なる整数とする．E : KE ×{0, 1}n →{0, 1}n をブロック暗号とする．このとき，

3σ 2
prp  mac
AdvEMAC[E,τ ] (t, q, σ) ≤ 2AdvE (t , q ) + n +
2

1
2τ −1

である．ただし，q  = σ, t = t + O(nσ) であり，質問の長さはブロック単位である．
定理 5.2 は，以下のことを示している： 実行時間 t, 高々 q 回の質問をし，それらの質問が合計で高々 σ ブロックであり，Advmac
EMAC[E,τ ] (A) = 
なる敵 A が存在すると仮定する．このとき，実行時間 t = t + O(nσ), 高々 q  = σ 回の
質問の後，
3σ 2

1
−
Advprp
(B)
≥
− τ
E
n+1
2 2
2
なる敵 B が存在する．
効率

EMAC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号の鍵 K1 , K2 ∈ KE の二つである．
• ブロック暗号鍵スケジューリングの呼び出し回数：2 回である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：(|M |/n) + 1 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：必要ない．
• 並列処理性：並列処理はできない．
標準化状況 ISO/IEC 9797-1 に含まれている [25]．また，NESSIE の portfolio にも含まれている [40]．実装が容易であること，証明可能安全であること，効率と鍵スケジューリングが妥当であることなどが挙げれている [40]．

5.3

RMAC

RMAC にはいくつかのバージョンが存在する．Jaulmes, Joux, Vallete によって提案されたオリジナルの RMAC [29, 30] と NIST が SP800-38B のドラフト版 [48] で提案した RMAC である．それぞれ RMAC-JJV と RMAC-NIST と表記することにする．
Jaulmes, Joux, Vallete によって NIST に提案された文書 [31] には 2 の方式が提案されている．メッセージのパディングの仕方が異なり，それぞれ，RMAC-JJV1, RMAC-JJV2と表記する．

18

方式 (RMAC-JJV1)

はじめに，RMAC-JJV1 について述べる．

RMAC-JJV1 = (RMAC-JJV1-K, RMAC-JJV1-G, RMAC-JJV1-V)の鍵生成アルゴリズム RMAC-JJV1-K, タグ生成アルゴリズム RMAC-JJV1-G, 確認アルゴリズム RMAC-JJV1-V はそれぞれ以下のように動作する．
Perm(n) を n ビット上のすべての置換の集合とし，r を整数とする．ランダム置換 f1
Rとは，Perm(n) から一様ランダムに選んだ f1 である．f1 ← Perm(n) と表記する．置換族 F2 を以下のように定義する．


(R)
(R)
F2 = f2 | R ∈ {0, 1}r , f2 ∈ Perm(n)(R)

すなわち，各 R ∈ {0, 1}r に対し，インデックス R を持つ置換 f2集合である．

∈ Perm(n) からなるR

• 鍵生成アルゴリズム RMAC-JJV1-K は確率的アルゴリズムであり，f1 ← Perm(n)Rと，各 R ∈ {0, 1}r に対し，f2 (R) ← Perm(n) を出力する．
すなわち，鍵空間は Perm(n) × F2 であり，鍵は，(0,...,0)f1 , f2(0,...,1,0), f2(1,...,1), . . . , f2となる．

• タグ生成アルゴリズム RMAC-JJV1-G : (Perm(n) × F2 ) × {0, 1}∗ → ({0, 1}n ×{0, 1}r ) は確率的アルゴリズムであり，鍵空間は Perm(n) × F2 , メッセージ空間は(R){0, 1}∗, タグ空間は {0, 1}n × {0, 1}r である．鍵 f1 ∈ Perm(n), f2 (R ∈ {0, 1}r )とメッセージ M ∈ {0, 1}∗ を入力とし，タグ T = RMAC-JJV1-Gf1 ,f (R) (M ) ∈2{0, 1}n × {0, 1}r を出力する．Fig. 11, Fig. 12 にあるように動作する．
(R)

まず，2 行目で r ビットの乱数 R を生成し，この R をインデックスにもつ f2 を
最終ブロックの暗号化の際に用いる．3 行目では，M に 1 を連結してから，全体が n ビットの倍数になるよう 0 を連結する．すなわち，

M ← M 10n−1−|M | mod nとする．M がすでに n の整数倍である場合は，10n−1 を連結する．

• 確認アルゴリズム RMAC-JJV1-V : (Perm(n) × F2 ) × {0, 1}∗ × ({0, 1}n × {0, 1}r ) →(·)
accept or reject は決定的アルゴリズムであり，鍵 f1 ∈ Perm(n), f2 ∈ F2 , メッ
セージ M ∈ {0, 1}∗, タグ T ∈ ({0, 1}n × {0, 1}r ) を入力とし，accept or reject =RMAC-JJV1-Vf1 ,f (R) (M, T ) を出力する．Fig. 13 にあるように動作する．
2

方式 (RMAC-JJV2) RMAC-JJV2 は，パディングの仕方が RMAC-JJV1 とは異なる．メッセージ長が n の倍数の場合は，10n−1 を連結する必要がなく，ブロック暗号の呼び出し回数を 1 回削減できる．
(R)
メッセージ長が n の倍数である場合は，f2 を，そうでない場合は，それとは異なる(R)f  2 を用いる．

19

Algorithm RMAC-JJV1-Gf1 ,f (R) (M )2RR ← {0, 1}r
Pad M
Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← f1 (X[i])(R)T ← f2 (Y [m])T ← (T  , R)
return T
Fig. 11. RMAC-JJV1 のタグ生成アルゴリズム RMAC-JJV1-Gf1 ,f (·) (·).
2

M [1]

?

f1

M [2]

M [3]

h
- ?

h
- ?

?

?

f1

f1

?
(·)
R f
2

?

T

Fig. 12. M = M [1]M [2]M [3] の場合の RMAC-JJV1-Gf1 ,f (R) (M ) の動作．
2

Algorithm RMAC-JJV1-Vf1 ,f (R) (M, (T  , R))2

Pad M
Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← f1 (X[i])(R)
T  ← f2 (Y [m])if T  = T  then return accept
else return rejectFig. 13. RMAC-JJV1 の確認アルゴリズム RMAC-JJV1-Vf1 ,f (·) (·, ·).
2

20

AES を用いた方式 (RMAC-JJV1) ブロック暗号として AES を用いた場合の RMACJJV1 の実装方法が提案されている．まず，r = 128 として，128 ビット乱数 R を生成す
る．K1 を 128 ビット鍵，K2 を 128 ビット，もしくは 256 ビット鍵とする．f1 として，
(R)
AESK1 を，f2 として，AESK2 ⊕R (K2 が 128 ビットの場合)，もしくは AESK2 ⊕(R0128 )(K2 が 256 ビットの場合) とする．
AES を用いた方式 (RMAC-JJV2) ブロック暗号として AES を用いた場合の RMACJJV2 の実装方法が提案されている．まず，K1 を 128 ビット鍵，K2 を 192 ビット，もしくは 256 ビット鍵とする．RMAC-JJV2 では K2 の長さが R の長さよりも長くなくてはならないので，128 ビットの K2 を用いることはできない．
r = 128 として，128 ビット乱数 R を生成する．f1 として，AESK1 をもちいる．メッ(R)
セージ長が n の倍数の場合，f2 として，AESK2 ⊕R , R = (R 1063 ) (K2 が 192 ビットの場合) もしくは AESK2 ⊕R , R = (R 10127 ) (K2 が 256 ビットの場合) とする．
(R)
メッセージ長が n の倍数ではない場合，f  2 として，AESK2 ⊕R , R = (R 0063 ) (K2が 192 ビットの場合) もしくは AESK2 ⊕R , R = (R 00127 ) (K2 が 256 ビットの場合) とする．
方式 (RMAC-NIST) NIST は SP800-38B のドラフト版で RMAC を提案した．R の扱いがオリジナルとは異なる．オリジナルでは，R が乱数であったのに対し，NIST の提案ではカウンタになることが許されていた．また，RMAC-JJV1 に対応する提案のみであり，RMAC-JJV2 に対応する提案はなかった．
RMAC-NIST はパラメータとして，ブロック暗号 E : {0, 1}k × {0, 1}n → {0, 1}n , タ
グ長 τ , R の長さ r をとる．これらのパラメータを用いた場合，RMAC-NIST[E, τ, r] と表記する．
RMAC-NIST[E, τ, r] = (RMAC-NIST-K, RMAC-NIST-G, RMAC-NIST-V) の鍵生成
アルゴリズム RMAC-NIST-K, タグ生成アルゴリズム RMAC-NIST-G, 確認アルゴリズ
ム RMAC-NIST-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム RMAC-NIST-K は確率的アルゴリズムであり，K1 , K2 ←{0, 1}k を出力する．
• タグ生成アルゴリズム RMAC-NIST-G : ({0, 1}k )2 × {0, 1}r × {0, 1}∗ → {0, 1}r ×{0, 1}τ ) は決定的アルゴリズムであり，鍵空間は ({0, 1}k )2 , メッセージ空間は {0, 1}∗ ,タグ空間は {0, 1}r × {0, 1}τ である．さらに NIST の仕様では R はタグ生成アルゴリズムへの入力として扱われる．すなわち，鍵 K1 , K2 ∈ {0, 1}k , R ∈ {0, 1}r ,メッセージ M ∈ {0, 1}∗ を入力とし，タグ T = RMAC-NIST-GK1 ,K2 (R, M ) ∈{0, 1}r × {0, 1}τ を出力する．Fig. 14, Fig. 15 にあるように動作する．
3 行目では，M に 1 を連結してから，全体が n ビットの倍数になるよう 0 を連結する．すなわち，M ← M 10n−1−|M | mod nとする．M がすでに n の整数倍である場合は，10n−1 を連結する．

21

Algorithm RMAC-NIST-GK1 ,K2 (R, M )Pad M
Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← EK1 (X[i])if r = 0 then K3 ← K2
else K3 ← K2 ⊕ (R0k−r )T  ← the left most τ bits of EK2 (Y [m])T ← (R, T  )return T
Fig. 14. RMAC-NIST のタグ生成アルゴリズム RMAC-NIST-GK1 ,K2 (·, ·).
M [1]
?

K1- E

M [2]

M [3]

g
-?

g
-?

?

K1- E

?

K1- E

?

(R0k−r ) ⊕K2- E?

T  (the left most τ bits)

Fig. 15. M = M [1]M [2]M [3] の場合の RMAC-NIST-GK1 ,K2 (R, M ) の動作．

22

• 確認アルゴリズム RMAC-NIST-V : ({0, 1}k )2 × {0, 1}∗ × ({0, 1}r × {0, 1}τ ) →accept or reject は決定的アルゴリズムであり，鍵 K1 , K2 ∈ {0, 1}k , メッセージM ∈ {0, 1}∗ , タグ T ∈ ({0, 1}r × {0, 1}τ ) を入力とし，
accept or reject = RMAC-NIST-VK1 ,K2 (M, T )を出力する．Fig. 16 にあるように動作する．

Algorithm RMAC-NIST-VK1 ,K2 (M, (R, T  ))Pad M
Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← EK1 (X[i])if r = 0 then K3 ← K2
else K3 ← K2 ⊕ (R0k−r )T  ← the left most τ bits of EK2 (Y [m])if T  = T  then return accept
else return rejectFig. 16. RMAC-NIST の確認アルゴリズム RMAC-NIST-VK1 ,K2 (·, ·).

パラメータについて RMAC-NIST はパラメータとして，ブロック暗号 E : {0, 1}k ×{0, 1}n → {0, 1}n , タグ長 τ , R の長さ r をとる．E としては，AES-128, AES-192, AES256, Triple DES-112, Triple DES-168 のいずれかを，τ と r については，Fig. 17 を提案している．

ParameterSetn = 128rnn = 64
r n

I
II
III
IV
V

0
32
0
64
16 80
64 96
128 128

0 32
64 64
n/a
n/a
n/a

Fig. 17. RMAC-NIST のパラメータ．
Parameter Set II 〜 V は一般的な使用に適している，と述べられている．

23

(R)

安全性 ランダム置換 f1 とランダム置換族 f2 (R ∈ {0, 1}R ) を用いた RMAC-JJV1と RMAC-JJV2 について安全性が解析されている [29, 30]．安全性の定義は，一般的な
強偽造不能性に近いが，タグが異なっていなければならない点が異なる．
敵は，タグ生成オラクルと確認オラクルをもつ．タグ生成オラクルに q 個のメッセー
ジ M1 , . . . , Mq を質問し，その答え T1 , . . . , Tq を得たとする．また，確認オラクルに q 
個のメッセージ，タグのペア (M1 , T1 ), . . . , (Mq  , Tq ) を質問したとする．
ある i に対し，MAC-VK (Mi , Ti ) = accept であり，Ti ∈ {T1 , . . . , Tj } であれば，A は偽造に成功した，という．{T1 , . . . , Tj } は，(Mi , Ti ) を確認オラクルに質問する以前に，
タグ生成オラクルから返ってきた答えである．
直感的には，メッセージは見たことがあってもよいが，タグは見たことがあってはならない．たとえば，タグ生成オラクルに M1 を送り，T1 を得たとする．次に，タグ生成
オラクルに M2 を送り，T2 を得たとする．強偽造不能性の定義では (M1 , T2 ) を偽造文として許すが，上記安全性の定義では，これは偽造文ではない．
ここで，アドバンテージ Advrmac-uf (A) を以下のように定義する．
(R) R

R

def

Advrmac-uf (A) = Pr(f1 ← Perm(n), f2
RMAC-JJV-G

A

f1 ,f

← F2 :(R) (·),RMAC-JJV-V(R) (·,·)
f1 ,f
2
2

が上記の意味で偽造に成功)

以下の定理が示されている [29, 30]．
定理 5.3 n ≥ 2 を整数，r = n とする．A を高々 σ ブロックの質問をする敵とする．このとき，4nσ + 4σ + 2
Advrmac-uf (A) ≤2nである．
上記の安全性のバウンドはほかに比べ，非常に小さいことがわかる．σ ≈ 2n/2 とすると，XCBC や OMAC のバウンドは 1 を超えるのに対し，上記のアドバンテージは小さい値のままである．
ただし，上記の定理は帰着を示していない．ランダム置換やランダム置換族を鍵として持つのは，非現実的である．
AES を用いた実装に対しても安全性解析がなされている [29, 30] が，該当箇所には議論の不備が指摘されている [45]．XCBC や OMAC のように，ブロック暗号の擬似ラン
ダム性に安全性を帰着させる結果は知られていない．[45] では帰着することは不可能である，と述べられている．
また，NESSIE でも考慮されたが，最終的には portfolio には含まれなかった [40]．
効率

RMAC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号の鍵 K1 , K2 ∈ KE の二つである．

24

• ブロック暗号鍵スケジューリングの呼び出し回数：鍵生成アルゴリズム実行時に 1回必要であり，さらにタグ生成アルゴリズム，もしくは確認アルゴリズムを呼び出すごとに 1 回必要である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：(|M |/n) + 1 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：必要ない．
• 並列処理性：並列処理はできない．
標準化状況 NIST に提案され，2002 年 10 月，SP800-38B のドラフト版 [48] が提案された．
これに対し，いくつかのコメントが寄せられた．Knudsen は，Triple DES を用いたときの安全性の問題点を指摘した [35]．Rogaway [45], Wagner [50], Black [11] は，いずれも，ブロック暗号の擬似ランダム性に RMAC の安全性が帰着できない点を指摘した．また，そもそも birthday bound をこえる安全性への疑問も出された．MAC は多くの場合，暗号化方式と組み合わせて使用される．多くの暗号化方式，たとえば CTR や CBC はbirthday bound をこえる安全性を有していない．これらの暗号化方式は birthday boundに到達すると，平文に関する情報を漏洩する．これらのコメントはいずれも，RMAC の決定を見直すべきだと主張している．
NIST は 2003 年 6 月，RMAC の決定を見直し，OMAC を提案すると発表した [41]．

5.4

XCBC

方式 XCBC はブロック暗号 E とタグ長 τ をパラメータとする．ブロック長 n のブ
ロック暗号 E : KE × {0, 1}n → {0, 1}n を用いた場合は，τ ≤ n でなくてはならな
い．これらのパラメータを用いた XCBC を XCBC[E, τ ] と表記する．XCBC[E, τ ] =(XCBC-K, XCBC-G, XCBC-V) の鍵生成アルゴリズム XCBC-K, タグ生成アルゴリズム
XCBC-G, 確認アルゴリズム XCBC-V はそれぞれ以下のように動作する．
R

R• 鍵生成アルゴリズム XCBC-K は確率的アルゴリズムであり，K1 ← KE , K2 ←R
{0, 1}n , K3 ← {0, 1}n を出力する．
• タグ生成アルゴリズム XCBC-G : (KE × ({0, 1}n )2 ) × {0, 1}∗ → {0, 1}τ は決定的ア
ルゴリズムであり，鍵空間は KE × ({0, 1}n )2 , メッセージ空間は {0, 1}∗, タグ空間は{0, 1}τ である．すなわち，鍵 K1 ∈ KE , K2 , K3 ∈ {0, 1}n とメッセージ M ∈ {0, 1}∗を入力とし，タグ T = XCBC-GK1 ,K2 ,K3 (M ) ∈ {0, 1}τ を出力する．Fig. 18, Fig. 19にあるように動作する．XCBC は M の長さが n の倍数でなくてもよい．Fig. 18の 3 行目において，
M = M [1]M [2] · · · M [m − 1]M [m]は，|M [1]| = |M [2]| = · · · = |M [m − 1]| かつ 1 ≤ |M [m]| ≤ n となるように分割される．M = ε のときは例外である．この場合，|M [m]| = 0 となる．

25

Algorithm XCBC-GK1 ,K2,K3 (M )Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m − 1 do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← EK1 (X[i])X[m] ← padn (M [m]) ⊕ Y [m − 1]
if |M [m]| = n then X[m] ← X[m] ⊕ K2
else X[m] ← X[m] ⊕ K3
T ← the left most τ bits of EK1 (Y [m])return T
Fig. 18. XCBC のタグ生成アルゴリズム XCBC-GK1 ,K2,K3 (·).
M [1]
?

K1- E

M [2]

M [3]

-?
g

-?
gK2

?

K1- E

?

K1- E

?

M [1]

M [2]
-?
g

?

K1- E

τ - trunc

?

K1- E

M [3] 10i

-?
gK3
?

K1- E

?

τ - trunc

?

?

T

T

Fig. 19. M = M [1]M [2]M [3] の場合の XCBC-GK1 ,K2,K3 (M ) の動作．

26

また，Fig. 18 の 7 行目の関数 padn : {0, 1}≤n → {0, 1}n は以下のように定義される．a を長さが高々 n ビットのビット列とする (a = ε でもよい)．ことのき，

a10n−|a|−1 if |a| < n,(1)padn (a) =a
if |a| = n.

• 確認アルゴリズム XCBC-V : (KE ×({0, 1}n )2 )×{0, 1}∗ ×{0, 1}τ → accept or rejectは決定的アルゴリズムであり，鍵 K1 ∈ KE , K2 , K3 ∈ {0, 1}n , メッセージ M ∈{0, 1}∗, タグ T ∈ {0, 1}τ を入力とし，accept or reject = XCBC-VK1 ,K2,K3 (M, T ) を出力する．Fig. 20 にあるように動作する．
Algorithm XCBC-VK1 ,K2 ,K3 (M, T )T  ← XCBC-GK1 ,K2,K3 (M )if T = T  then return accept
else return rejectFig. 20. XCBC の確認アルゴリズム XCBC-VK1 ,K2 ,K3 (·, ·).

安全性 Black, Rogaway により，安全性が解析されている [12]. ブロック暗号 E が安全な擬似ランダム置換族であれば，XCBC[E, τ ] = (XCBC-K, XCBC-G, XCBC-V) は，偽造不可能性の意味で安全な MAC であることが示されている．以下の定理が示されている[27]．
定理 5.4 n, τ ≥ 1 を整数，t, q, σ ≥ 1 を σ 2 ≤ 2(n+1)/2 なる整数とする．E : KE ×{0, 1}n →{0, 1}n をブロック暗号とする．このとき，
prp  AdvmacXCBC[E,τ ] (t, q, σ) ≤ AdvE (t , q ) +

3σ 2
1
+
2n
2τ

である．ただし，q  = σ, t = t + O(nσ) であり，質問の長さはブロック単位である．
定理 5.4 は，以下のことを示している： 実行時間 t, 高々 q 回の質問をし，それらの質問が合計で高々 σ ブロックであり，AdvmacXCBC[E,τ ] (A) = 
なる敵 A が存在すると仮定する．このとき，実行時間 t = t + O(nσ), 高々 q  = σ 回の
質問をし，
3σ 2
1
Advprp
(B)
≥

−
− τ
E
n
2
2
なる敵 B が存在する．

27

効率

XCBC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号の鍵 K1 ∈ KE と n ビットの鍵 K2 , K3 ∈ {0, 1}n の計 3 つが必要である．
• ブロック暗号鍵スケジューリングの呼び出し回数：1 回である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：
max{1, |M |/n } 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：必要ない．
• 並列処理性：並列処理はできない．
標準化状況

5.5

NIST に提案されている [41]．また，[19] や [23] で議論されている．

TMAC

方式 TMAC はブロック暗号 E とタグ長 τ をパラメータとする．ブロック長 n のブ
ロック暗号 E : KE × {0, 1}n → {0, 1}n を用いた場合は，τ ≤ n でなくてはならな
い．これらのパラメータを用いた TMAC を TMAC[E, τ ] と表記する．TMAC[E, τ ] =(TMAC-K, TMAC-G, TMAC-V) の鍵生成アルゴリズム TMAC-K, タグ生成アルゴリズ
ム TMAC-G, 確認アルゴリズム TMAC-V はそれぞれ以下のように動作する．
R

R• 鍵生成アルゴリズム TMAC-K は確率的アルゴリズムであり，K1 ← KE と K2 ←{0, 1}n を出力する．
• タグ生成アルゴリズム TMAC-G : (KE × {0, 1}n ) × {0, 1}∗ → {0, 1}τ は決定的ア
ルゴリズムであり，鍵空間は KE × {0, 1}n , メッセージ空間は {0, 1}∗ , タグ空間は{0, 1}τ である．すなわち，鍵 K1 ∈ KE , K2 ∈ {0, 1}n とメッセージ M ∈ {0, 1}∗ を入力とし，タグ T = TMAC-GK1 ,K2 (M ) ∈ {0, 1}τ を出力する．Fig. 21, Fig. 22 にあるように動作する．Fig. 21, Fig. 22 において，K2 · u は，GF(2n ) 上の乗算である．一般的に a ∈ {0, 1}n に対し，
a1
if msb(a) = 0,
(2)
a·u=
(a
1) ⊕ Cstn otherwiseとなる．ここで，(2) において，a
1 は a の左 1 ビットシフトを表し，a =an−1 an−2 · · · a1 a0 と a をビット表現した場合，a
1 = an−2 an−3 · · · a0 0 となる．すなわち，最上位ビットはなくなり，最下位ビットに 0 が補充される．また，msb(a)は a の最上位ビットを表し，Cstn は n ビットの定数である．たとえば，Cst128 =
0120 10000111 であり，Cst64 = 059 11011 である．TMAC も XCBC と同様，M の長さが n の倍数でなくてもよい．Fig. 21 の 3 行目において，

M = M [1]M [2] · · · M [m − 1]M [m]28

Algorithm TMAC-GK1 ,K2 (M )Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m − 1 do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← EK1 (X[i])X[m] ← padn (M [m]) ⊕ Y [m − 1]
if |M [m]| = n then X[m] ← X[m] ⊕ K2 · uelse X[m] ← X[m] ⊕ K2
T ← the left most τ bits of EK1 (Y [m])return T
Fig. 21. TMAC のタグ生成アルゴリズム TMAC-GK1 ,K2 (·).
M [1]
?

K1- E

M [2]

M [3]

-?
g

-?
gK2 · u

?

K1- E

?

K1- E

?

M [1]

-?
g
?

K1- E

τ - trunc

M [2]
?

K1- E

M [3] 10i

-?
gK2
?

K1- E

?

τ - trunc

?

?

T

T

Fig. 22. M = M [1]M [2]M [3] の場合の TMAC-GK1 ,K2 (M ) の動作．

29

は，|M [1]| = |M [2]| = · · · = |M [m − 1]| かつ 1 ≤ |M [m]| ≤ n となるように分割される．M = ε のときは例外でり，この場合，|M [m]| = 0 となる．
また，Fig. 21 の 7 行目の関数 padn : {0, 1}≤n → {0, 1}n は (1) のように定義される．

• 確認アルゴリズム TMAC-V : (KE × {0, 1}n) × {0, 1}∗ × {0, 1}τ → accept or rejectは決定的アルゴリズムであり，鍵 K1 ∈ KE , K2 ∈ {0, 1}n , メッセージ M ∈ {0, 1}∗ ,タグ T ∈ {0, 1}τ を入力とし，accept or reject = TMAC-VK1 ,K2 (M, T ) を出力する．
Fig. 23 にあるように動作する．
Algorithm TMAC-VK1 ,K2 (M, T )T  ← TMAC-GK1 ,K2 (M )if T = T  then return accept
else return rejectFig. 23. TMAC の確認アルゴリズム TMAC-VK1 ,K2 (·, ·).

安全性 Kurosawa, Iwata により，安全性が解析されている [36]. ブロック暗号 E が安
全な擬似ランダム置換族であれば，TMAC[E, τ ] = (TMAC-K, TMAC-G, TMAC-V) は，
偽造不可能性の意味で安全な MAC であることが示されている．以下の定理が示されている [27]．
定理 5.5 n, τ ≥ 1 を整数，t, q, σ ≥ 1 を σ 2 ≤ 2(n+1)/2 なる整数とする．E : KE ×{0, 1}n →{0, 1}n をブロック暗号とする．このとき，

3σ 2
prp  mac
AdvTMAC[E,τ ] (t, q, σ) ≤ AdvE (t , q ) + n +2

12τ

である．ただし，q  = σ, t = t + O(nσ) であり，質問の長さはブロック単位である．
定理 5.5 は，以下のことを示している： 実行時間 t, 高々 q 回の質問をし，それらの質問が合計で高々 σ ブロックであり，AdvmacTMAC[E,τ ] (A) = 
なる敵 A が存在すると仮定する．このとき，実行時間 t = t + O(nσ), 高々 q  = σ 回の
質問をし，
3σ 2
1
Advprp
(B)
≥

−
− τ
E
n
2
2
なる敵 B が存在する．

30

効率

TMAC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号の鍵 K1 ∈ KE と n ビットの鍵 K2 ∈ {0, 1}n の計 2 つが必要である．
• ブロック暗号鍵スケジューリングの呼び出し回数：1 回である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：
max{1, |M |/n } 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：必要ない．
• 並列処理性：並列処理はできない．
標準化状況

5.6

NIST に提案されている [41]．

OMAC

OMAC は 2 つの方式 OMAC1 と OMAC2 の総称である．
方式 (OMAC1) OMAC1 はブロック暗号 E とタグ長 τ をパラメータとする．ブロック長 n のブロック暗号 E : KE × {0, 1}n → {0, 1}n を用いた場合は，τ ≤ n でな
くてはならない．これらのパラメータを用いた OMAC1 を OMAC1[E, τ ] と表記する．
OMAC1[E, τ ] = (OMAC1-K, OMAC1-G, OMAC1-V) の鍵生成アルゴリズム OMAC1-K,
タグ生成アルゴリズム OMAC1-G, 確認アルゴリズム OMAC1-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム OMAC1-K は確率的アルゴリズムであり，K ← KE を出力する．
• タグ生成アルゴリズム OMAC1-G : KE × {0, 1}∗ → {0, 1}τ は決定的アルゴリズムであり，鍵空間は KE , メッセージ空間は {0, 1}∗, タグ空間は {0, 1}τ である．すなわち，
鍵 K ∈ KE とメッセージ M ∈ {0, 1}∗ を入力とし，タグ T = OMAC1-GK (M ) ∈{0, 1}τ を出力する．Fig. 24, Fig. 25 にあるように動作する．Fig. 24, Fig. 25 において，L · u は (2) によって得られ，L · u2 は (L · u) · u として，(2) によって得られる．OMAC1 も XCBC, TMAC と同様，M の長さが n の倍数でなくてもよい．
Fig. 24 の 3 行目において，
M = M [1]M [2] · · · M [m − 1]M [m]は，|M [1]| = |M [2]| = · · · = |M [m − 1]| かつ 1 ≤ |M [m]| ≤ n となるように分割される．M = ε のときは例外でり，この場合，|M [m]| = 0 となる．
また，Fig. 24 の 7 行目の関数 padn : {0, 1}≤n → {0, 1}n は (1) のように定義される．

31

Algorithm OMAC1-GK (M )L ← EK (0n )Y [0] ← 0n
Partition M into M [1] · · · M [m]for i ← 1 to m − 1 do
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← EK (X[i])X[m] ← padn (M [m]) ⊕ Y [m − 1]
if |M [m]| = n then X[m] ← X[m] ⊕ L · uelse X[m] ← X[m] ⊕ L · u2
T ← the left most τ bits of EK (Y [m])return T
Fig. 24. OMAC1 のタグ生成アルゴリズム OMAC1-GK (·).
M [1]
?

K- E

M [2]

M [3]

-?
g

-?
gL · u

?

K- E

?

K- E

?

M [1]

M [2]
-?
g

?

K- E

τ - trunc?

K- E

M [3] 10i
-?
g L · u2
?

K- E

?

τ - trunc

?

?

T

T

Fig. 25. M = M [1]M [2]M [3] の場合の OMAC1-GK (M ) の動作．

32

• 確認アルゴリズム OMAC1-V : KE × {0, 1}∗ × {0, 1}τ → accept or reject は決定的
アルゴリズムであり，鍵 K ∈ KE , メッセージ M ∈ {0, 1}∗, タグ T ∈ {0, 1}τ を入力とし，accept or reject = OMAC1-VK (M, T ) を出力する．Fig. 26 にあるように動作する．
Algorithm OMAC1-VK (M, T )T  ← OMAC1-GK (M )if T = T  then return accept
else return rejectFig. 26. OMAC1 の確認アルゴリズム OMAC1-VK (·, ·).

方式 (OMAC2) OMAC2 は OMAC1 とほぼ同様である．OMAC1 中の L · u2 を L · u−1としたものが OMAC2 である．一般に a ∈ {0, 1}n に対し，
a1
if lsb(a) = 0,(3)
a · u−1 =(a1) ⊕ Cstn otherwise.
となる．ここで，上記 (3) において，a
1 は a の右 1 ビットシフトを表す．a =an−1 an−2 · · · a1 a0 と a をビット表現した場合，a1 = 0an−1 an−2 · · · a2 a1 となる．すな
わち，最下位ビットはなくなり，最上位ビットに 0 が補充される．また，lsb(a) は a の
最下位ビットを表し，Cstn は n ビットの定数である．たとえば，Cst128 = 10120 1000011
である．
安全性 Iwata, Kurosawa により，安全性が解析されている [26]. ブロック暗号 E が安
全な擬似ランダム置換族であれば，OMAC1[E, τ ] = (OMAC1-K, OMAC1-G, OMAC1-V)と OMAC2[E, τ ] = (OMAC2-K, OMAC2-G, OMAC2-V) は，偽造不可能性の意味で安全な MAC であることが示されている．以下の定理が示されている [27]．
定理 5.6 n, τ ≥ 1 を整数，t, q, σ ≥ 1 を σ 2 ≤ 2(n+1)/2 なる整数とする．E : KE ×{0, 1}n →{0, 1}n をブロック暗号とする．このとき，

4σ 2
1

prp  mac
 AdvOMAC1[E,τ ] (t, q, σ) ≤ AdvE (t , q ) + n + τ
2
2
2

4σ
1

prp   Advmac+ τ
OMAC2[E,τ ] (t, q, σ) ≤ AdvE (t , q ) +n22である．ただし，q  = σ, t = t + O(nσ) であり，質問の長さはブロック単位である．
定理 5.6 は，以下のことを示している： 実行時間 t, 高々 q 回の質問をし，それらの質問が合計で高々 σ ブロックであり，Advmac
OMAC1[E,τ ] (A) = 

33

なる敵 A が存在すると仮定する．このとき，実行時間 t = t + O(nσ), 高々 q  = σ 回の
質問をし，
4σ 2
1
Advprp
(B)
≥

−
− τ
E
n
2
2
なる敵 B が存在する．OMAC2 についても同様である．
効率

OMAC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号の鍵 K ∈ KE の一つのみである．
• ブロック暗号鍵スケジューリングの呼び出し回数：1 回である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：
max{1, |M |/n } 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：L = EK (0n ) を計算するのに 1 回必要である．
• 並列処理性：並列処理はできない．
標準化状況 NIST に提案されている [41]．NIST は 2003 年 6 月，RMAC の決定を見直し，OMAC を提案すると発表した [41]．2003 年 11 月現在，OMAC1 を提案予定である，としている．

並列計算可能な MAC

6

本章では，並列計算可能な MAC として，XOR MAC, XECB MAC, PMAC について述べる．CBC MAC とその変形では，ブロック暗号の並列計算ができないのに対し，本章で挙げる MAC では，ブロック暗号の並列計算が可能である．

6.1

XOR MAC

2 つの方式が提案されており，一つは乱数を用いる XMACR 方式，もう一つはカウンタを用いる XMACC 方式である．どちらも関数族 F : {0, 1}k × {0, 1}n → {0, 1}n を用いる．F としてブロック暗号を用いてもよいが，入力長 n と出力長 n は異なってもよい．
XMACR, XMACC どちらも，パラメータとして，F と整数 b をとる．ただし，b ≤ n − 1
でなくてはならない．メッセージ M は |M | ≤ b · 2n−b−1 であり，長さが b の整数倍になるようにパディングされているとする．たとえば，
M ← M 10(b−|M |−1) mod b(4)
とする．関数 tag : {0, 1}k × ({0, 1}b)+ × {0, 1}n−1 → {0, 1}n を以下のように定義する．
def

tag(K, M, r) = FK (0r) ⊕ FK (11n−b−1M [1]) ⊕ · · · ⊕ FK (1mn−b−1M [m])34ただし，M = M [1] · · · M [m] はパディングされていて，各 M [1], . . . , M [m] は b ビット，rは (n − 1) ビット，in−b−1 は整数 i の (n − b − 1) ビット表現である．以下，tag(K, M, r)
を tagK (M, r) と表記する．Fig. 27 参照．
n−1


r

0

?

K- F

n−b−1



n−b−1

b


11n−b−1 M [1]b
12n−b−1 M [2]

?

?

K- F

K- F

?
- j

?
- j

n−b−1



b


13n−b−1 M [3]
?

K- F

?
- j
?

tagK (M, r)

Fig. 27. M = M [1]M [2]M [3] の場合の tagK (M, r) の動作．

方式 (XMACR) XMACR は，関数族 F とブロック長 n をパラメータとする．関数族 F : {0, 1}k × {0, 1}n → {0, 1}n を用いた場合は，b ≤ n − 1 でなくてはならない．
これらのパラメータを用いた XMACR を XMACR[F, b] と表記する．XMACR[F, b] =(XMACR-K, XMACR-G, XMACR-V) の鍵生成アルゴリズム XMACR-K, タグ生成アル
ゴリズム XMACR-G, 確認アルゴリズム XMACR-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム XMACR-K は確率的アルゴリズムであり，K ← {0, 1}k を出力する．
• タグ生成アルゴリズム XMACR-G : {0, 1}k × {0, 1}∗ → ({0, 1}n−1 × {0, 1}n ) は確
率的アルゴリズムであり，鍵空間は {0, 1}k , メッセージ空間は {0, 1}∗ , タグ空間は
({0, 1}n−1 × {0, 1}n ) である．すなわち，鍵 K ∈ {0, 1}k とメッセージ M ∈ {0, 1}∗

を入力とし，タグ T = XMACR-GK (M ) ∈ ({0, 1}n−1 ×{0, 1}n ) を出力する．Fig. 28にあるように動作する．
Algorithm XMACR-GK (M )Pad M
Rr ← {0, 1}n−1
T  ← tagK (M, r)
T ← (r, T  )return T
Fig. 28. XMACR のタグ生成アルゴリズム XMACR-GK (·).

ただし，2 行目は M ∈ {0, 1}∗ に対しパディングを施し，M ∈ ({0, 1}n )+ となるよ
うにする．たとえば，(4) のようにする．3 行目では n − 1 ビットの乱数 r を選ぶ．

35



• 確認アルゴリズム XMACR-V : {0, 1}k × {0, 1}∗ × ({0, 1}n−1 × {0, 1}n ) → accept
or reject は決定的アルゴリズムであり，鍵 K ∈ {0, 1}k , メッセージ M ∈ {0, 1}∗ ,
タグ T ∈ ({0, 1}n−1 × {0, 1}n ) を入力とし，accept or reject = XMACR-VK (M, T )を出力する．Fig. 29 にあるように動作する．
Algorithm XMACR-VK (M, (r, T  ))Pad M
T  ← tagK (M, r)
if T  = T  then return accept
else return rejectFig. 29. XMACR の確認アルゴリズム XMACR-VK (·, ·).
ただし，2 行目は M ∈ {0, 1}∗ に対し，(4) のようにする．
方式 (XMACC) XMACC は，XMACR と同様，関数族 F とブロック長 n をパラ
メータとする．関数族 F : {0, 1}k × {0, 1}n → {0, 1}n を用いた場合は，b ≤ n −1 でなくてはならない．これらのパラメータを用いた XMACC を XMACC[F, b] と表記する．XMACC[F, b] = (XMACC-K, XMACC-G, XMACC-V) の鍵生成アルゴリズム
XMACC-K, タグ生成アルゴリズム XMACC-G, 確認アルゴリズム XMACC-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム XMACC-K は確率的アルゴリズムであり，K ← {0, 1}k を出力する．
• タグ生成アルゴリズム XMACC-G : {0, 1}k × {0, 1}∗ × Count → (Count× {0, 1}n ) は
決定的アルゴリズムであり，鍵空間は {0, 1}k , メッセージ空間は {0, 1}∗, タグ空間は(Count × {0, 1}n ) である．さらに入力として，カウンタ C ∈ Count をとる．Countはカウンタの空間であり，Count = {0, 1, . . . , 2n−1 − 1} である．カウンタは送信者により保持されており，0 に初期化され，タグ生成アルゴリズムによって更新される．
受信者はこれを保持しない．すなわち，鍵 K ∈ {0, 1}k , メッセージ M ∈ {0, 1}∗ ,
カウンタ C ∈ Count を入力とし，タグ T = XMACC-GK (M ) ∈ (Count × {0, 1}n )を出力する．Fig. 30 にあるように動作する．
ただし，Cn−1 はカウンタ C の (n − 1) ビット表現であり，2 行目は M ∈ {0, 1}∗に対し，(4) のようにしてから，M = M [1] · · · M [m] とする．
• 確認アルゴリズム XMACC-V : {0, 1}k × {0, 1}∗ × (Count × {0, 1}n ) → accept or
reject は決定的アルゴリズムであり，鍵 K ∈ {0, 1}k , メッセージ M ∈ {0, 1}∗ , タ
グ T ∈ (Count × {0, 1}n ) を入力とし，accept or reject = XMACC-VK (M, T ) を出力する．Fig. 31 にあるように動作する．

36

Algorithm XMACC-GK (M, C)
Pad M
C ←C +1
T  ← tagK (M, Cn−1 )T ← (C, T )
return T
Fig. 30. XMACC のタグ生成アルゴリズム XMACC-GK (·).
Algorithm XMACC-VK (M, (C, T  ))T  ← tagK (M, C)
if T  = T  then return accept
else return rejectFig. 31. XMACC の確認アルゴリズム XMACC-VK (·, ·).
安全性 Bellare, Guérin, Rogaway により，安全性が解析されている [6]. 関数族 F が安全な擬似ランダム関数族であれば，XMACR[F, b] = (XMACR-K, XMACR-G, XMACR-V)と XMACC[F, b] = (XMACC-K, XMACC-G, XMACC-V) は，強偽造不可能性の意味で安全な MAC であることが示されている．
「F が擬似ランダム関
擬似ランダム関数族 関数族 F : {0, 1}k ×{0, 1}n → {0, 1}n に対し，数族である」とは，適応的選択平文攻撃を行う任意の敵が，関数族 {FK (·) ∈ Rand(n, n ) |K ∈ {0, 1}k } と {0, 1}n から {0, 1}n へのすべての関数の集合 Rand(n, n ) を区別できな
いことをいう．
より厳密には，敵 A として，オラクルにアクセスできるアルゴリズムを考える．何回

かの質問の後，A は 1 ビットを出力する．関数族 F : {0, 1}k × {0, 1}n → {0, 1}n の，敵A に対する，擬似ランダム関数としての安全性は，アドバンテージ Advprf
F (A) によって評価される．ここで，


R
R
def 

k
FK (·)R(·)
Pr(KAdvprf
(A)
=
←
{0,
1}
:
A
=
1)
−
Pr(R
←
Rand(n,
n
)
:
A
=
1)


F
と定義され，AFK (·) は質問 X に対し，Y = FK (X) を返すオラクル FK (·) を持つ敵 A を表し，AR(·) は質問 X に対し，Y = R(X) を返すオラクル R(·) を持つ敵 A を表す．
計算量理論的安全性 関数族 F の擬似ランダム関数族としての安全性を考える場合に扱う資源は，実行時間 t とオラクルへの質問回数 q である．


def
prf
Advprf
(t,
q)
=
max
(A)
Adv
F
E
A

と定義される．ただし，最大値は実行時間 t, オラクルへの質問回数 q のすべての敵 A についてとる．

37

XMACR の安全性 Advs-uf
XMACR[F,b] (t, qg , qv , m) を


def
s-uf
Advs-uf
XMACR[F,b] (t, qg , qv , m) = max AdvXMACR[F,b] (A)Aと定義する．ただし，最大値は実行時間 t, タグ生成オラクルへ高々 qg 回，確認オラク
ルへ高々 qv 回，それぞれの質問の長さが高々 m ブロックであるすべての敵 A についてとる．
XMACR については，以下の定理が示されている [6]．
定理 6.1 n, n ≥ 1 を整数，b を b ≤ n − 1 なる整数，t, qg , qv , m ≥ 1 を整数とする．

F : {0, 1}k × {0, 1}n → {0, 1}n を関数族とする．このとき，prf  Advs-uf
XMACR[F,b] (t, qg , qv , m) ≤ AdvF (t , q ) +2qs2 2qv2
+ n
2n
2

である．ただし，q  = (qg + qv ) · (m + 1), t = t + O((n + n )q  ) である．
定理 6.1 は，以下のことを示している： 実行時間 t, タグ生成オラクルに高々 qg 回，確認オラクルに高々 qv 回の質問をし，それぞれの質問が高々 m ブロック (1 ブロックは bビット) であり，
Advs-uf
XMACR[F,b] (A) = 
なる敵 A が存在すると仮定する．このとき，実行時間 t = t + O((n + n )q  ), 高々 q  =(qg + qv ) · (m + 1) 回の質問をし，

2qg2 2qv2
prp
AdvE (B) ≥  − n − n22なる敵 B が存在する．

XMACC の安全性 Advs-uf
XMACC[F,b] (t, qg , qv , m) を


def
s-uf
Advs-uf
XMACC[F,b] (t, qg , qv , m) = max AdvXMACC[F,b] (A)Aと定義する．最大値のとりかたは，XMACR と同様である．
XMACC については，以下の定理が示されている [6]．
定理 6.2 n, n ≥ 1 を整数，b を b ≤ n − 1 なる整数，t, qg , qv , m ≥ 1 を qg ≤ 2n−1 なる
整数とする．F : {0, 1}k × {0, 1}n → {0, 1}n を関数族とする．このとき，prf  Advs-uf
XMACC[F,b] (t, qg , qv , m) ≤ AdvF (t , q ) +

2qv2
2n

である．ただし，q  = (qg + qv ) · (m + 1), t = t + O((n + n )q  ) である．

38

定理 6.2 は，以下のことを示している： 実行時間 t, タグ生成オラクルに高々 qg 回，確認オラクルに高々 qv 回の質問をし，それぞれの質問が高々 m ブロック (1 ブロックは bビット) であり，
Advs-uf
XMACC[F,b] (A) = 
なる敵 A が存在すると仮定する．このとき，実行時間 t = t + O((n + n )q  ), 高々 q  =(qg + qv ) · (m + 1) 回の質問をし，

Advprp
E (B) ≥  −

2qv2
2n

なる敵 B が存在する．
XMACC は，送信者がカウンタを保持しなければならない代わりに，安全性のバウン
ドが qg に依存しない，という利点を持っている．
効率

XMACR, XMACC の効率は，以下のようにまとめられる．

• 鍵長：関数族 F (ブロック暗号) の鍵 K ∈ {0, 1}k の一つのみである．
• F の鍵スケジューリングの呼び出し回数：1 回である．
• メッセージ M に対するタグを生成するのにかかる F の呼び出し回数：パディン
グの定義により異なるが，(4) のようにした場合は， (|M | + 1)/b + 1 回必要である．F として，ブロック暗号を用いた場合，CBC MAC では |M |/n なので，CBC
MAC と比べ，n/b 倍程度必要である．たとえば，b = n/2 とした場合，およそ 2倍の呼び出し回数が必要である．
• 事前計算するべき F の呼び出し回数：XMACC における送信者は FK (0C) を計算できる．
• 並列処理性：並列処理可能である．CBC MAC とその変形は，ブロック暗号の並列処理ができない．
標準化状況

6.2

標準化された実績はない．

XECB MAC

3 つの方式：乱数を用いる XECB$-MAC 方式，送信者が状態を用いる XECBC-MAC
方式，状態と乱数を用いる XECBS-MAC 方式が提案されている．
どの方式もブロック暗号 E : KE × {0, 1}n → {0, 1}n を用いる．

39

方式 (XECB$-MAC) XECB$-MAC は乱数を用いる方式である．XECB$-MAC は，
ブロック暗号 E をパラメータとする．これを XECB$-MAC を XECB$-MAC[E] と表記する．XECB$-MAC[E] = (XECB$-K, XECB$-G, XECB$-V) の鍵生成アルゴリズム
XECB$-K, タグ生成アルゴリズム XECB$-G, 確認アルゴリズム XECB$-V はそれぞれ
以下のように動作する．
R• 鍵生成アルゴリズム XECB$-K は確率的アルゴリズムであり，K ← KE を出力する．
• タグ生成アルゴリズム XECB$-G : KE ×{0, 1}∗ → ({0, 1}n ×{0, 1}n ) は確率的アルゴ
リズムであり，鍵空間は KE , メッセージ空間は {0, 1}∗, タグ空間は ({0, 1}n ×{0, 1}n )である．すなわち，鍵 K ∈ KE とメッセージ M ∈ {0, 1}∗ を入力とし，タグ T =XECB$-GK (M ) ∈ ({0, 1}n × {0, 1}n) を出力する．Fig. 32 にあるように動作する．
Algorithm XECB$-GK (M )R

r0 ← {0, 1}ny0 ← EK (r0 )z0 ← EK (r0 + 1)
Partition M into M [1] · · · M [m]if |M [m]| = n then Z ← z0
else Z ← z0
M [m] ← padn (M [m])M [m + 1] ← Z
for i ← 1 to m + 1 do
X[i] ← M [i] ⊕ i × y0
Y [i] ← EK (X[i])T ← Y [1] ⊕ · · · ⊕ Y [m + 1]
T ← (r0 , T  )return T
Fig. 32. XECB$-MAC のタグ生成アルゴリズム XECB$-GK (·).

ただし，+ や × の演算は mod 2n 上で行われる．2 行目の r0 は n ビットの乱数である．6 行目の z0 は z0 のビットごとの反転である．8 行目の padn (·) は (1) で定義されている．

• 確認アルゴリズム XECB$-V : KE × {0, 1}∗ × ({0, 1}n × {0, 1}n ) → accept or rejectは決定的アルゴリズムであり，鍵 K ∈ KE , メッセージ M ∈ {0, 1}∗, タグ T ∈({0, 1}n × {0, 1}n ) を入力とし，accept or reject = XECB$-VK (M, T ) を出力する．
Fig. 33 にあるように動作する．
r0 を用いてタグ生成を行い，一致していれば accpet を返す．

40

Algorithm XECB$-VK (M, (r0 , T  ))y0 ← EK (r0 )z0 ← EK (r0 + 1)
Partition M into M [1] · · · M [m]if |M [m]| = n then Z ← z0
else Z ← z0
M [m] ← padn (M [m])M [m + 1] ← Z
for i ← 1 to m + 1 do
X[i] ← M [i] ⊕ i × y0
Y [i] ← EK (X[i])T ← Y [1] ⊕ · · · ⊕ Y [m + 1]
T  ← (r0 , T  )if T  = T  then return accept
else return rejectFig. 33. XECB$-MAC の確認アルゴリズム XECB$-VK (·, ·).
方式 (XECBC-MAC) XECBC-MAC は，送信者が状態を用いる方式である．XECB$MAC と同様，ブロック暗号 E をパラメータとする．これを，XECBC-MAC[E] と表記する．XECBC-MAC[E] = (XECBC-K, XECBC-G, XECBC-V) の鍵生成アルゴリズム
XECBC-K, タグ生成アルゴリズム XECBC-G, 確認アルゴリズム XECBC-V はそれぞれ
以下のように動作する．
R• 鍵生成アルゴリズム XECBC-K は確率的アルゴリズムであり，K ← KE を出力する．
• タグ生成アルゴリズム XECBC-G : KE × {0, 1}∗ × Count → (Count × {0, 1}n ) は
決定的アルゴリズムであり，鍵空間は KE , メッセージ空間は {0, 1}∗, タグ空間は(Count × {0, 1}n ) である．さらに入力として，カウンタ C ∈ Count をとる．Countはカウンタの空間であり，Count = {1, 2, . . .} である．カウンタは送信者により保持されており，1 に初期化され，タグ生成アルゴリズムによって更新される．受信者はこれを保持しない．すなわち，鍵 K ∈ KE , メッセージ M ∈ {0, 1}∗, カウンタ
C ∈ Count を入力とし，タグ T = XECBC-GK (M ) ∈ (Count × {0, 1}n ) を出力す
る．Fig. 34 にあるように動作する．
ただし，C  は更新されたカウンタの値であり，+ と × の演算は， mod 2n 上で行われる．

• 確認アルゴリズム XECBC-V : KE × {0, 1}∗ × (Count × {0, 1}n ) → accept or rejectは決定的アルゴリズムであり，鍵 K ∈ KE , メッセージ M ∈ {0, 1}∗, タグ T ∈(Count × {0, 1}n ) を入力とし，accept or reject = XMACC-VK (M, T ) を出力する．
Fig. 35 にあるように動作する．

41

Algorithm XECBC-GK (C, M )y0 ← EK (C)z0 ← EK (y0 )Partition M into M [1] · · · M [m]if |M [m]| = n then Z ← z0
else Z ← z0
M [m] ← padn (M [m])M [m + 1] ← Z
for i ← 1 to m + 1 do
X[i] ← M [i] ⊕ i × y0
Y [i] ← EK (X[i])T ← Y [1] ⊕ · · · ⊕ Y [m + 1]
C ← C + 1
T ← (C, T )
return T
Fig. 34. XECBC-MAC のタグ生成アルゴリズム XECBC-GK (·).

Algorithm XMACC-VK (M, (C, T  ))y0 ← EK (C)z0 ← EK (y0 )Partition M into M [1] · · · M [m]if |M [m]| = n then Z ← z0
else Z ← z0
M [m] ← padn (M [m])M [m + 1] ← Z
for i ← 1 to m + 1 do
X[i] ← M [i] ⊕ i × y0
Y [i] ← EK (X[i])T ← Y [1] ⊕ · · · ⊕ Y [m + 1]
if T  = T  then return accept
else return rejectFig. 35. XECBC の確認アルゴリズム XECBC-VK (·, ·).

42

方式 (XECBS-MAC) XECBS-MAC は状態と乱数を用いる方式である．これも，ブロック暗号 E をパラメータとする．XECBS-MAC[E] と表記する．XECBS-MAC[E] =(XECBS-K, XECBS-G, XECBS-V) の鍵生成アルゴリズム XECBS-K, タグ生成アルゴリ
ズム XECBS-G, 確認アルゴリズム XECBS-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム XECBS-K は確率的アルゴリズムであり，K ← KE を出力する．
• タグ生成アルゴリズム XECBS-G : KE × {0, 1}∗ × Count → (Count × {0, 1}n ) は
決定的アルゴリズムであり，鍵空間は KE , メッセージ空間は {0, 1}∗, タグ空間は(Count × {0, 1}n ) である．さらに入力として，カウンタ C ∈ Count をとる．Countはカウンタの空間であり，Count = {1, 2, . . .} である．カウンタは送信者により保持されており，1 に初期化され，タグ生成アルゴリズムによって更新される．受信者はこれを保持しない．すなわち，鍵 K ∈ KE , メッセージ M ∈ {0, 1}∗, カウンタ
C ∈ Count を入力とし，タグ T = XECBS-GK (M ) ∈ (Count × {0, 1}n ) を出力する．
さらにアルゴリズム内部では，状態 R と R∗ を用いる．これらは，n ビットのビット列であり，鍵ごとに更新される．メッセージごとに更新されるわけではない．この状態は送信者だけでなく，受信者も保持している．秘密鍵 K から導出してもよ
いと記されている [20]．Fig. 36 にあるように動作する．
Algorithm XECBS-GK (C, M )Partition M into M [1] · · · M [m]if |M [m]| = n then Z ← Relse Z ← R
M [m] ← padn (M [m])M [m + 1] ← Z
for i ← 1 to m do
X[i] ← M [i] ⊕ C × Z ⊕ i × R∗
Y [i] ← EK (X[i])T ← Y [1] ⊕ · · · ⊕ Y [m]C ← C + 1
T ← (C, T )
return T
Fig. 36. XECBS-MAC のタグ生成アルゴリズム XECBS-GK (·).

ただし，C  は更新されたカウンタの値であり，+ と × の演算は， mod 2n 上で行われる．

• 確認アルゴリズム XECBS-V : KE × {0, 1}∗ × (Count × {0, 1}n ) → accept or rejectは決定的アルゴリズムであり，鍵 K ∈ KE , メッセージ M ∈ {0, 1}∗, タグ T ∈(Count × {0, 1}n ) を入力とし，accept or reject = XMACC-VK (M, T ) を出力する．

43

さらにアルゴリズム内部では，状態 R と R∗ を用いる．これらは，n ビットのビット列であり，鍵ごとに更新される．メッセージごとに更新されるわけではない．この状態は，受信者も保持している．Fig. 37 にあるように動作する．

Algorithm XMACC-VK (M, (C, T ))
Partition M into M [1] · · · M [m]if |M [m]| = n then Z ← Relse Z ← R
M [m] ← padn (M [m])M [m + 1] ← Z
for i ← 1 to m do
X[i] ← M [i] ⊕ C × Z ⊕ i × R∗
Y [i] ← EK (X[i])T ← Y [1] ⊕ · · · ⊕ Y [m]if T  = T  then return accept
else return rejectFig. 37. XECBS の確認アルゴリズム XECBS-VK (·, ·).

安全性 Glogor, Donescu により，安全性が解析されている [20]. ブロック暗号 E が安全な擬似ランダム置換族であれば，XECB$-MAC[E] = (XECB$-K, XECB$-G, XECB$-V),
XECBC-MAC[E] = (XECBC-K, XECBC-G, XECBC-V), および，XECBS-MAC[E] =(XECBS-K, XECBS-G, XECBS-V) は，いずれも，強偽造不可能性の意味で安全な MAC
であることが示されている．

XECB$-MAC の安全性 Advs-uf
XECB$-MAC[E] (t, qg , µg , qv , µv ) を


def
s-uf
Advs-uf
XECB$-MAC[E] (t, qg , µg , qv , µv ) = max AdvXECB$-MAC[E] (A)Aと定義する．ただし，最大値は実行時間 t, タグ生成オラクルへ高々 qg 回の質問を合計
で高々 µg ブロック，確認オラクルへ高々 qv 回の質問を合計で高々 µv ブロックであるすべての敵 A についてとる．
XECB$-MAC については，以下の定理が示されている [20]．
定理 6.3 n ≥ 1 を整数，t, qg , µg , qv , µg ≥ 1 を整数とする．E : KE × {0, 1}n → {0, 1}nをブロック暗号とする．このとき，Advs-uf
XECB$-MAC[E] (t, qg , µg , qv , µg )µv ((log µv ) + 3) qg µ2v µg  µg ((log µv ) + 3)
prf  ≤ AdvE (t , q ) ++ n + qg + 2qv +
n
n+1
2

2

である．ただし，µs + µg ≤ q  , t ≤ t である．

44

2

2



バウンドは最後の項が最も大きく，ほかの MAC と比べると，通常の birthday paradox
バウンドよりも log スケールで悪いことがわかる．

XECBS-MAC の安全性 Advs-uf
XECBS-MAC[E] (t, qg , µg , qv , µv ) も XECB$-MAC[E] と同様に定義する．
XECBS-MAC については，以下の定理が示されている [20]．
定理 6.4 n ≥ 1 を整数，t, qg , µg , qv , µg ≥ 1 を整数とする．E : KE × {0, 1}n → {0, 1}nをブロック暗号とする．このとき，

Advs-uf
XECBS-MAC[E] (t, qg , µg , qv , µg )qv
µv ((log µv ) + 3)
+
2n
2n+1
qs ((log qs ) + 3)
µg ((log µv ) + 3)
+ (qv + µg )+ (qv + µg )
n+1
2
2n+1
である．ただし，µs + µg ≤ q  , t ≤ t である．
 ≤ Advprf
E (t , q ) +XECBC-MAC の安全性 Advs-uf
XECBC-MAC[E] (t, qg , µg , qv , µv ) も上記二つと同様に定義する．
XECBC-MAC については，以下の定理が示されている [20]．
定理 6.5 n ≥ 1 を整数，t, qg , µg , qv , µg ≥ 1 を整数とする．E : KE × {0, 1}n → {0, 1}nをブロック暗号とする．このとき，

Advs-uf
XECBC-MAC[E] (t, qg , µg , qv , µg )µ2v
qv
µv ((log µv ) + 3)
+ n+
n+1
2
2
2n+1
µ2g
qg ((log qg ) + 3)
µg ((log µv ) + 3)
+ (qv + µg )+ (qv + µg )
+ n+1
2n+1
2n+1
2


である．ただし，µs + µg ≤ q , t ≤ t である．
 ≤ Advprf
E (t , q ) +効率

XECB MAC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号 E の鍵 K ∈ KE の一つのみである．
• E の鍵スケジューリングの呼び出し回数：1 回である．
• メッセージ M に対するタグを生成するのにかかる F の呼び出し回数：XECB$-MACと XECBC-MAC では， |M |/n + 3 回，XECBS-MAC では， |M |/n 回必要である．しかし，XECBS-MAC では，R と R∗ の生成にブロック暗号を呼び出す必要がある場合がある．
• 事前計算するべき F の呼び出し回数：XECBS-MAC では，R と R∗ の生成にブロック暗号を呼び出す必要がある場合がある．
• 並列処理性：並列処理可能である．

45

標準化状況

6.3

NIST に提案されている [41]．

PMAC

方式 PMAC はブロック暗号 E とタグ長 τ をパラメータとする．ブロック長 n のブ
ロック暗号 E : KE × {0, 1}n → {0, 1}n を用いた場合は，τ ≤ n でなくてはならな
い．これらのパラメータを用いた PMAC を PMAC[E, τ ] と表記する．PMAC[E, τ ] =(PMAC-K, PMAC-G, PMAC-V) の鍵生成アルゴリズム PMAC-K, タグ生成アルゴリズ
ム PMAC-G, 確認アルゴリズム PMAC-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム PMAC-K は確率的アルゴリズムであり，K ← KE を出力する．
• タグ生成アルゴリズム PMAC-G : KE ×{0, 1}∗ → {0, 1}τ は決定的アルゴリズムであり，鍵空間は KE , メッセージ空間は {0, 1}∗, タグ空間は {0, 1}τ である．すなわち，鍵K ∈ KE とメッセージ M ∈ {0, 1}∗ を入力とし，タグ T = PMAC-GK (M ) ∈ {0, 1}τ
を出力する．Fig. 38, Fig. 39 にあるように動作する． PMAC は M の長さが n の倍数でなくてもよい．Fig. 38 の 3 行目において，
M = M [1]M [2] · · · M [m − 1]M [m]は，|M [1]| = |M [2]| = · · · = |M [m − 1]| かつ 1 ≤ |M [m]| ≤ n となるように分割される．M = ε のときは例外である．この場合，|M [m]| = 0 となる．

5 行目の γi · L は，以下のように計算される．

γ1 · L = L
γi · L = (γi−1 · L) ⊕ (L · untz(i) ) (i ≥ 2)
ここで，ntz(i) は，i をビット表現したときの，最下位ビットから連続して並ぶ 0の個数である．もしくは，ntz(i) は，2z が i を割り切る最大の z である．たとえば，ntz(7) = 0, ntz(8) = 3 である．

γi · L は事前計算でいくつか計算しておいてもよいし，必要に応じて計算してもよい．
また，Fig. 38 の 7 行目の関数 padn : {0, 1}≤n → {0, 1}n は (1) と同様である．8
行目の L · u−1 は，(3) のように計算される．

• 確認アルゴリズム PMAC-V : KE × {0, 1}∗ × {0, 1}τ → accept or reject は決定的ア
ルゴリズムであり，鍵 K ∈ KE , メッセージ M ∈ {0, 1}∗, タグ T ∈ {0, 1}τ を入力とし，accept or reject = PMAC-VK (M, T ) を出力する．Fig. 40 にあるように動作する．
安全性 Black, Rogaway により，安全性が解析されている [14]. ブロック暗号 E が安全な擬似ランダム置換族であれば，PMAC[E, τ ] = (PMAC-K, PMAC-G, PMAC-V) は，偽
造不可能性の意味で安全な MAC であることが示されている．以下の定理が示されている [14]．

46

Algorithm PMAC-GK (M )L ← EK (0n )Partition M into M [1] · · · M [m]for i ← 1 to m − 1 do
X[i] ← M [i] ⊕ γi · L
Y [i] ← EK (X[i])Σ ← Y [1] ⊕ Y [2] ⊕ · · · ⊕ Y [m − 1] ⊕ padn (M [m])if |M [m]| = n then X[m] ← Σ ⊕ L · u−1
else X[m] ← ΣT ← the left most τ bits of EK (X[m])return T
Fig. 38. PMAC のタグ生成アルゴリズム PMAC-GK (·).
M [1]

M [2]

M [3]

M [1]

?
f γ1 · L ?
f γ2 · L
?
?
K- E
K- E
-?
f

L·u

M [2]

M [3] 10i?
f γ2 · L?
f γ1 · L
?
?
K- E
K- E

?
f
?
−1- f

-?
f

?
f
n- ?
f

0

?

?

K- E

K- E

τ - truncτ - trunc

?

?

?

?

T

T

Fig. 39. M = M [1]M [2]M [3] の場合の PMAC-GK (M ) の動作．

Algorithm PMAC-VK (M, T )T  ← PMAC-GK (M )if T = T  then return accept
else return rejectFig. 40. PMAC の確認アルゴリズム PMAC-VK (·, ·).

47

定理 6.6 n, τ ≥ 1 を整数，t, q, σ ≥ 1 を整数とする．E : KE × {0, 1}n → {0, 1}n をブロック暗号とする．このとき，
prp  AdvmacPMAC[E,τ ] (t, q, σ) ≤ AdvE (t , q ) +1.5σ  21+
2n2τ

である．ただし，σ  = σ + q + 1, q  = σ + 1, t = t + O(nσ) であり，質問の長さはブロッ
ク単位である．
定理 6.6 は，以下のことを示している： 実行時間 t, 高々 q 回の質問をし，それらの質問が合計で高々 σ ブロックであり，AdvmacPMAC[E,τ ] (A) = 
なる敵 A が存在すると仮定する．σ  = σ+q+1 とする．このとき，実行時間 t = t+O(nσ),
高々 q  = σ 回の質問をし，

Advprp
E (B) ≥  −1.5σ  21−
2n
2τ

なる敵 B が存在する．
効率

PMAC の効率は，以下のようにまとめられる．

• 鍵長：ブロック暗号の鍵 K ∈ KE の計 1 つが必要である．
• ブロック暗号鍵スケジューリングの呼び出し回数：1 回である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：
max{1, |M |/n } 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：1 回である．
• 並列処理性：並列処理可能である．
標準化状況

7

NIST に提案されている [41]．

その他の MAC
本章では，その他の MAC として，f 9 について述べる．

48

7.1

f9

方式 f 9 はブロック暗号 KASUMI : {0, 1}128 × {0, 1}64 → {0, 1}64 を用いる．鍵生成ア
ルゴリズム f 9-K, タグ生成アルゴリズム f 9-G, 確認アルゴリズム f 9-V はそれぞれ以下のように動作する．
R• 鍵生成アルゴリズム f 9-K は確率的アルゴリズムであり，K ← {0, 1}128 を出力する．
• タグ生成アルゴリズム f 9-G : KE × {0, 1}∗ → {0, 1}τ は決定的アルゴリズムであり，鍵空間は {0, 1}64 , メッセージ空間は {0, 1}∗, タグ空間は {0, 1}32 である．さらに，32 ビットのカウンタ COUNT, 32 ビットの乱数 FRESH, 1 ビットの direction
identiﬁer DIRECTION を入力にもつ．これらは，送受信者の間で共有されている．
Fig. 41, Fig. 42 にあるように動作する．
Algorithm f 9-GK (COUNT, FRESH, DIRECTION, M )M ← pad64 (COUNT, FRESH, DIRECTION, M )Break M into 64-bit blocks M [1] · · · M [m]Y [0] ← 064
For i = 1 to m do:
X[i] ← M [i] ⊕ Y [i − 1]
Y [i] ← KASUMIK (X[i])T ← KASUMIK⊕KM (Y [1] ⊕ · · · ⊕ Y [m])T ← the leftmost 32 bits of T
Return T
Fig. 41. f 9 のタグ生成アルゴリズム f 9-GK (·).
COUNTFRESH
?

M [1]
?
K E
•

MESSAGE

?

M [2]

-?
e
?
K E
•

-?
e

?

DIRECTION10 . . . 0
?

M [3]

-?
e
?
K E
•

-?
e

M [m]

···

-?
e
?
K E

-?
e
?
K ⊕ KM E···?

T (the leftmost 32 bits)

Fig. 42. f 9-GK (M ) の動作．E は KASUMI である．

2 行目の pad64 (COUNT, FRESH, DIRECTION, M ) は以下のように動作する：まず，COUNT, FRESH, M , DIRECTION を連結し，次に 1 ビットの “1” を連結し，

49

最後に，全体の長さが 64 ビットの整数倍になるように，“0” を連結する．すなわち，

pad64 (COUNT, FRESH, DIRECTION, M )= COUNTFRESHM DIRECTION1063−(|M |+1 mod 64) .
とする．KM は，128 ビットの定数であり，KM = 0xAA...AA である．

• 確認アルゴリズム f 9-V : {0, 1}64 × {0, 1}∗ × {0, 1}32 → accept or reject は決定的
アルゴリズムであり，鍵 K ∈ {0, 1}64 , メッセージ M ∈ {0, 1}∗ , タグ T ∈ {0, 1}32を入力とし，accept or reject = f 9-VK (M, T ) を出力する．さらに，送受信者の間で共有されている 32 ビットのカウンタ COUNT, 32 ビットの乱数 FRESH, 1 ビットの direction identiﬁer DIRECTION を入力にもつ．
Fig. 43 にあるように動作する．
Algorithm f 9-VK (COUNT, FRESH, DIRECTION, M, T )T  ← f 9-GK (COUNT, FRESH, DIRECTION, M )if T = T  then return accept
else return rejectFig. 43. f 9 の確認アルゴリズム f 9-VK (·, ·).

安全性 Hong, Kang, Preneel, Ryu により，KASUMI が安全な擬似ランダム置換であれ
ば，f 9 が偽造不能性の意味で安全な MAC であることが主張された [24] が，証明の不備が指摘されている [28]．
効率

f 9 の効率は，以下のようにまとめられる．

• 鍵長：KASUMI の鍵 K ∈ {0, 1}64 一つのみである．
• ブロック暗号鍵スケジューリングの呼び出し回数：K と K ⊕ KM の 2 回である．
• メッセージ M に対するタグを生成するのにかかるブロック暗号の呼び出し回数：|M |/n + 2 回の呼び出しである．
• 事前計算するべきブロック暗号の呼び出し回数：必要ない．
• 並列処理性：並列処理はできない．
標準化状況

3GPP により標準化されている [1, 2]．

50

8

まとめ

本報告書では，メッセージ認証に関するブロック暗号利用モードについて，主に安全性の観点からその特徴をまとめるとともに，効率についても言及した．本報告書では，証明可能安全性に焦点をあてたが，実装に関する攻撃などはこの範疇ではない．そういった環境も考慮した新たな安全性の概念も次々に提案されている．また，新たなブロック
暗号利用モードも数多く提案されている．NIST も含めた標準化作業も活動中であり，その動向を注視していく必要がある．また，ブロック暗号利用モードの選択に当たっては，
安全性，効率，そして本報告書では触れなかった知的所有権の問題等を勘案し，十分な注意が必要である．

参考文献[1] 3GPP TS 35.201 v 3.1.1. Speciﬁcation of the 3GPP conﬁdentiality and integrity
algorithms, Document 1: f 8 and f 9 speciﬁcation. Available at http://www.3gpp.
org/tb/other/algorithms.htm.
[2] 3GPP TS 35.202 v 3.1.1. Speciﬁcation of the 3GPP conﬁdentiality and integrity
algorithms, Document 2: KASUMI speciﬁcation. Available at http://www.3gpp.
org/tb/other/algorithms.htm.
[3] ANSI X3.106, American National Standard for Information Systems — Data Encryption Algorithm — Modes of Operation, American National Standard Institute,
1983.
[4] ANSI X3.92, American National Standard for Information Systems — Data Encryption Algorithm, American National Standard Institute, 1981.
[5] M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A concrete security treatment ofsymmetric encryption. Proceedings of The 38th Annual Symposium on Foundationsof Computer Science, FOCS ’97, pp. 394–405, IEEE, 1997.
[6] M. Bellare, R. Guérin, and P. Rogaway. XOR MACs: New methods for message authentication using ﬁnite pseudorandom functions. Advances in Cryptology— CRYPTO ’95, LNCS 963, pp. 15–28, Springer-Verlag, 1995.
[7] M. Bellare, J. Kilian, and P. Rogaway. The security of the cipher block chaining message authentication code. JCSS, Vol. 61, No. 3, pp. 362–399, 2000. Earlier version in
Advances in Cryptology — CRYPTO ’94, LNCS 839, pp. 341–358, Springer-Verlag,
1994.
[8] M. Bellare, and T. Kohno. A theoretical treatment of related-key attacks: RKAPRPs, RKA-PRFs, and applications. Advances in Cryptology — EUROCRYPT
2003, LNCS 2656, pp. 491–506, Springer-Verlag, 2003.

51

[9] M. Bellare, P. Rogaway, and D. Wagner. A conventional authenticated-encryption
mode. NIST submission, 2003. Available at
http://csrc.nist.gov/CryotoToolKit/modes/proposedmodes/.
[10] A. Berendschot, B. den Boer, J. P. Boly, A. Bosselaers, J. Brandt, D. Chaum,
I. Damgård, M. Dichtl, W. Fumy, M. van der Ham, C. J. A. Jansen, P. Landrock,
B. Preneel, G. Roelofsen, P. de Rooij, and J. Vandewalle. Final Report of RACE
Integrity Primitives. LNCS 1007, Springer-Verlag, 1995.
[11] J. Black. Comments on the RMAC algorithm. Comments to NIST. Available at
http://csrc.nist.gov/CryptoToolkit/modes/comments/.
[12] J. Black and P. Rogaway. CBC MACs for arbitrary-length messages: The three key
constructions. Advances in Cryptology — CRYPTO 2000, LNCS 1880, pp. 197–215,
Springer-Verlag, 2000.
[13] J. Black and P. Rogaway. Comments to NIST concerning AES modes of operations: A suggestion for handling arbitrary-length messages with the CBC MAC.
Second Modes of Operation Workshop. Available at http://www.cs.ucdavis.edu/~rogaway/.
[14] J. Black and P. Rogaway. A block-cipher mode of operation for parallelizable message
authentication. Advances in Cryptology — EUROCRYPT 2002, LNCS 2332, pp.
384–397, Springer-Verlag, 2002.
[15] National Institute of Standards and Technology, Federal Information Processing
Standards Publication 46-3, Data Encryption Standard (DES).
[16] National Institute of Standards and Technology, Federal Information Processing
Standards Publication 81, DES modes of operation (DES), 1980.
[17] National Institute of Standards and Technology, Federal Information Processing
Standards Publication 113, Computer data authentication, 1994.
[18] National Institute of Standards and Technology, Federal Information Processing
Standards Publication 197, Advanced Encryption Standard (AES), 2001.
[19] S. Frankel, and H. Herbert. The AES-XCBC-MAC-96 algorithm and its use with
IPsec. Available at http://www.ieft.org/.
[20] V. G. Gligor, and P. Donescu. Fast encryption and authentication: XCBC encryption
and XECB authentication modes. Fast Software Encryption, FSE 2001, LNCS 2355,
pp. 92–108, Springer-Verlag, 2002.
[21] O. Goldreigh, S. Goldwasser and S. Micali. How to construct random functions. J.
ACM, Vol. 33, No. 4, pp. 792–807, October 1986.

52

[22] S. Halevi, and P. Rogaway. A tweakable enciphering mode. Advances in Cryptology— CRYPTO 2003, LNCS 2729, pp. 482–499, Springer-Verlag, 2003.
[23] P. Hoﬀman. The AES-XCBC-PRF-128 algorithm for IKE. Available at http://www.ieft.org/.
[24] D. Hong, J-S. Kang, B. Preneel, and H. Ryu. A concrete security anallysis for 3GPPMAC. Fast Software Encryption, FSE 2003, LNCS 2887, pp. 154–169, SpringerVerlag, 2003.
[25] ISO/IEC 9797-1. Information technology — security techniques — data integrity
mechanism using a cryptographic check function employing a block cipher algorithm. International Organization for Standards, Geneva, Switzerland, 1999. Second
edition.
[26] T. Iwata and K. Kurosawa. OMAC: One-Key CBC MAC. Fast Software Encryption,
FSE 2003, LNCS 2887, pp. 129–153, Springer-Verlag, 2003.
[27] T. Iwata and K. Kurosawa. Stronger security bounds for OMAC, TMAC and XCBC.
Progress in Cryptology — INDOCRYPT 2003, LNCS 2904, pp. 402–415, 2003.
[28] T. Iwata and K. Kurosawa. On the correctness of security proofs for the 3GPP
conﬁdentiality and integrity algorithms. Ninth IMA International Conference on
Cryptography and Coding, LNCS 2898, pp. 306–318, Springer-Verlag, 2003.
[29] É. Jaulmes, A. Joux, and F. Valette. On the security of randomized CBC-MAC
beyond the birthday paradox limit: A new construction. Fast Software Encryption,
FSE 2002, LNCS 2365, pp. 237–251, Springer-Verlag, 2002.
[30] É. Jaulmes, A. Joux, and F. Valette. On the security of randomized CBC-MAC
beyond the birthday paradox limit: A new construction. Full version. Available at
Cryptology ePrint Archive, Report 2001/074, http://eprint.iacr.org/.
[31] É. Jaulmes, A. Joux, and F. Valette. RMAC, A randomized MAC beyond thebirthday paradox limit. Second Modes of Operation Workshop, 2001. Available at
http://csrc.nist.gov/CryptoToolkit/modes.
[32] J. Jonsson. On the security of CTR + CBC-MAC. Selected Areas in Cryptography,
SAC 2002, LNCS 2595, pp. 76–93, Springer-Verlag, 2002.
[33] C.S. Jutla. Encryption modes with almost free message integrity. Advances in
Cryptology — EUROCRYPT 2001, LNCS 2045, pp. 529–544, Springer-Verlag, 2001.
[34] T. Kohno, J. Viega, and D. Whiting. The CWC authenticated encryption (associated data) mode. NIST submission, 2003. Available at http://csrc.nist.gov/
CryotoToolKit/modes/proposedmodes/.

53

[35] L.R. Knudsen. Analysis of RMAC. Comments to NIST. Available at http://csrc.
nist.gov/CryptoToolkit/modes/comments/.
[36] K. Kurosawa and T. Iwata. TMAC: Two-Key CBC MAC. Topics in Cryptology —CT-RSA 2003, LNCS 2612, pp. 33–49, Springer-Verlag, 2003.
[37] R. Lidl and H. Niederreiter. Introduction to ﬁnite ﬁelds and their applications,revised edition. Cambridge University Press, 1994.
[38] M. Luby and C. Rackoﬀ. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput., Vol. 17, No. 2, pp. 373–386, April 1988.
[39] M. Naor and O. Reingold. On the construction of pseudorandom permutations:
Luby-Rackoﬀ revised. J. Cryptology, vol. 12, no. 1, pp. 29–66, Springer-Verlag,
1999.
[40] http://www.cosic.esat.kuleuven.ac.be/nessie/[41] http://www.nist.gov/modes[42] E. Petrank and C. Rackoﬀ. CBC MAC for real-time data sources. J.Cryptology,
Vol. 13, No. 3, pp. 315–338, Springer-Verlag, 2000.
[43] B. Preneel and P. C. van Oorschot. On the security of two MAC algorithms. Advancesin Cryptology — EUROCRYPT ’96, LNCS 1070, pp. 19–32, Springer-Verlag, 1996.
[44] P. Rogaway. Bucket hashing and its application to fast message authentication.
Advances in Cryptology — CRYPTO ’95, LNCS 963, pp. 29–42, Springer-Verlag,
1995.
[45] P. Rogaway. Comments on NIST’s RMAC proposal. Comments to NIST. Available at http://www.cs.ucdavis.edu/~rogaway/xcbc/index.html. Also available
at http://csrc.nist.gov/CryptoToolkit/modes/comments/.
[46] P. Rogaway, M. Bellare, J. Black, and T. Krovetz. OCB: a block-cipher mode ofoperation for eﬃcient authenticated encryption. Proceedings of ACM Conference on
Computer and Communications Security, ACM CCS 2001, ACM, 2001.
[47] M. Dworkin, NIST Special Publication 800-38A. Recommendation for block cipher
modes of operation. Available at http://csrc.nist.gov/CryptoToolkit/modes.
[48] M. Dworkin, NIST Special Publication 800-38B. Draft recommendation for blockcipher modes of operation: the RMAC authentication mode. Available at http://csrc.nist.gov/CryptoToolkit/modes.

54[49] M. Dworkin, NIST Special Publication 800-38C. Draft recommendation for blockcipher modes of operation: the CCM mode for authentication and conﬁdentiality.
Available at http://csrc.nist.gov/CryptoToolkit/modes.
[50] D. Wagner. Comments on RMAC. Comments to NIST. Available at http://csrc.
nist.gov/CryptoToolkit/modes/comments/.
[51] D. Whiting, R. Housley, and F. Ferguson, Counter with CBC-MAC (CCM). NIST
submission, 2002. Available at http://csrc.nist.gov/CryotoToolKit/modes/
proposedmodes/.

55