和文

暗号技術仕様書
PC-MAC-AES
日本電気株式会社
1
目次
目次
1
概要
2
2
暗号アルゴリズム仕様
2
2.1
記法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.2
基本関数および変数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.3
全体構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.4
鍵スケジュール
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.5
認証タグ生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6
タグ検証 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.7
バージョン情報
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3
推奨用途
8
1 概要
2
1 概要
この文書はメッセージ認証コード PC-MAC-AES の仕様を説明するものである．
PC-MAC-AES は，カウンターなどの初期値を必要としない，決定的（deterministic）MAC 関数である．
AES をベースとしており，メッセージ認証を目的としたブロック暗号モードの一種といえるが，AES の段関
数を取り出して部品として用いる点が CBC-MAC など従来のモードと異なる．具体的には AES そのものと
その 4 段関数を用いている．これにより，AES ベースの CBC-MAC などより 1.4 から 2.5 倍ほど（推奨パラ
メータにおいては 1.4 から 2 倍ほど）高速に処理が可能でとなる．同様のアイディアに基づくメッセージ認
証コードの提案は過去に alpha-MAC[7] や Pelican[8] などがあったが，これらと異なり，PC-MAC-AES は
CMAC[4] などと同等の証明可能安全性を持つ，すなわちその安全性が純粋に AES そのものの安全性に帰着可
能であるという利点がある．実装性に関しては，基本的に AES の段関数があれば実装可能であり，GF(2128 )
上の乗算など付加的な代数演算を必要としないため，実装規模を小さく抑えることが可能である．処理構造は
CBC-MAC と類似しており，シンプルである．さらに，ブロック暗号の鍵と独立な鍵を用いて，終端処理に
おいて TMAC[13]，CMAC などと同様のマスク処理を用いており，これにより，メッセージパディングによ
り発生しうる冗長な暗号関数の呼び出しがないように設計されている．これは特にメッセージが短いときに効
果的である．
2 暗号アルゴリズム仕様
2.1 記法
本稿で用いる記法を定義する．バイナリ系列はすべて big endian 表記とする．
• |x| : バイナリ系列 x のビット長
• ∥ : データ連結
• ⊕ : 排他的論理和
• x ≪ 1 : x を 1 ビット左論理シフト（x = x1 ∥x2 ∥ . . . ∥xn ，|xi | = 1 なら x ≪ 1 = x2 ∥x3 ∥ . . . xn ∥0)
• msb(x) : x の最上位ビット
• 0s : ビット 0 の s 個の連結，s = 0 のときは空（x∥00 = x)
• [i] : 非負整数 i について，i の 128 ビット表現，例えば [2] = 00 . . . 10．
また，本稿での AES はすべて 128 ビット鍵の AES を指すものとする．
2.2 基本関数および変数
本稿で用いる基本的関数と変数を定義する．
• M : 任意長のメッセージ
• T : 認証に用いるタグ
• K : AES の 128 ビット鍵
• L : K と独立な 128 ビット鍵
2 暗号アルゴリズム仕様
3
• d : オーダ（PC-MAC-AES が用いるパラメータ（正整数））
• π : タグのビット長
• EK : 128 ビットの K を鍵とした AES の暗号化関数
• GU : 4 段 AES 関数，ただし 1 段目の鍵は全ゼロ，384 ビットの U = U (1) ∥U (2) ∥U (3) が鍵，U (j) は
j + 1 段目の 128 ビット段鍵（図 1 参照）
• Kixor : 128 ビット補助鍵（i = 1, . . . , d − 1）
• cutπ (x) : x の最上位ビットから π （1 ≤ π ≤ |x|）ビットを取り出した系列
• mul2(x) : 128 ビットの x を有限体 GF(2128 ) 上の元とした 2 倍算
{
x≪1
if msb(x) = 0
mul2(x) =
(x ≪ 1) ⊕ (0120 ∥10000111) otherwise
• pad(x) : 長さが 128 ビット以下の入力 x について
{
x
pad(x) =
x∥1∥0128−|x|−1
if |x| = 128
if |x| < 128.
2.3 全体構成
以下に PC-MAC-AES の全体構成を述べる．PC-MAC-AES は AES と 4 段 AES 関数をモジュールとす
る決定的（deterministic）MAC であり，カウンターなどの初期値は必要としない．PC-MAC-AES の鍵は，
AES の 128 ビット鍵 K と，これと独立な 128 ビット鍵 L の合計 256 ビットである．パラメータとして，タ
グの長さ π およびオーダと呼ぶ正整数 d を用いる．π は 1 ≤ π ≤ 128 を満たすが，推奨値として 64 以上を，
d は実装性の観点から 1 から 5 までを推奨する．
4 段 AES 関数 GU は図 1 に示される 384 ビットの U = (U (1) ∥U (2) ∥U (3) ) を鍵とした鍵付き置換である．
AES の 1 段目の段鍵加算を省略し，以後，SubBytes 関数，ShiftRows 関数，MixColumns 関数，段鍵加算
をこの順序で 3 回行い，最後に SubBytes 関数，ShiftRows 関数，MixColumns 関数を適用する（各関数の詳
細は文献 [3] 参照のこと）
．それぞれ，U (1) が 2 段目の鍵，U (2) が 3 段目の鍵，U (3) が 4 段目の鍵として使用
される．
パ ラ メ ー タ (π, d) を 持 つ PC-MAC-AES を PC-MAC-AES(π,d) と 表 記 す る ．特 に π の 指 定 を せ ず
PC-MAC-AES(d) と書いたときは π = 128 として扱う．さらに，d と π を特に指定する必要がないか，文脈
から明らかな場合には単に PC-MAC-AES と表記する．
PC-MAC-AES(π,d) は AES を用いた鍵スケジュール処理 KeySch を事前処理として実行する．鍵スケ
ジュール処理 KeySch が終了したのち，実際の任意長メッセージ M *1 に付与する認証タグ（以降は単にタグ
と呼ぶ）を生成できるようになる．タグ生成処理を TagGen とし，これを用いて π ビットタグ T を生成す
る．メッセージ M の送信者は (M, T ) を送信する．受信者はこれを受け取った後，検証手続き TagVer を
用いて，受信したメッセージが正当なものかどうかを検証する．TagVer の入力は (M, T ) および π ，d であ
り，出力はバイナリ値であり，1 ならば受理（正当と判断）
，0 ならば棄却を意味する．以下，それぞれの処理
について説明する．
*1
現在の仕様ではいわゆる empty string（長さ 0 のメッセージ）には未対応である．
2 暗号アルゴリズム仕様
4
SubBytes
ShiftRows
MixColumns
U(1)
SubBytes
ShiftRows
MixColumns
U(2)
GU
U=U(1)|| U(2) || U(3)
SubBytes
ShiftRows
MixColumns
U(3)
SubBytes
ShiftRows
MixColumns
図1
4 段 AES 関数 GU
2.4 鍵スケジュール
鍵スケジュール処理 KeySch は AES の暗号化関数 EK と，K と独立な鍵 L を用いて 4 段 AES 関数の d
xor
（合計 384 · d + 128 · (d − 1) ビット）を
個の鍵 U1 , . . . , Ud と，d − 1 個の 128 ビット補助鍵 K1xor , . . . , Kd−1
生成するものであり，形式的には d, K, L を入力として以下のように行う．
まず 4 段 AES 関数の 384 ビット鍵を d 個生成する．これは，
EK (L ⊕ [0])∥EK (L ⊕ [1])∥ . . . ∥EK (L ⊕ [3d − 1])
(1)
という 384 · d ビット系列を求め，先頭から 384 ビットづつを鍵とする．つまり i = 1, . . . , d について
(1)
(2)
(3)
Ui = (Ui ∥Ui ∥Ui ) = (EK (L ⊕ [3(i − 1)])∥EK (L ⊕ [3(i − 1) + 1])∥EK (L ⊕ [3(i − 1) + 2])) とする．次
xor
に d − 1 個の 128 ビット補助鍵 K1xor , . . . , Kd−1
を，
xor
K1xor = EK (L ⊕ [3d]), K2xor = EK (L ⊕ [3d + 1]), . . . , Kd−1
= EK (L ⊕ [4d − 2])
(2)
として生成する．
なお d = 1 の場合，補助鍵は存在せず，4 段 AES 関数の 384 ビット鍵 U1 のみを生成することになる．
具体的な鍵スケジュール KeySch は Algorithm 2.1 に従って行われる．
2.5 認証タグ生成
鍵スケジュール KeySch の後，TagGen を用いて任意のバイナリ系列メッセージ M に対して π ビッ
トの認証タグを生成する．TagGen は形式的には d, π, K, L, M および KeySch の出力 U1 , . . . , Ud と
xor
を入力とする．
K1xor , . . . , Kd−1
2 暗号アルゴリズム仕様
5
Algorithm 2.1: KeySch(d, K, L)
for i ← 1 to d
 (1)

Ui ← EK (L ⊕ [3(i − 1)])



U (2) ← E (L ⊕ [3(i − 1) + 1])
K
i
do
(3)

Ui ← EK (L ⊕ [3(i − 1) + 2])




(1)
(2)
(3)
Ui ← Ui ∥Ui ∥Ui
for j ← 1 to d − 1
do Kjxor ← EK (L ⊕ [3d + j − 1])
xor
return (U1 , U2 , . . . , Ud , K1xor , K2xor , . . . , Kd−1
)
xor
関数として用いるのは AES 暗号化関数 EK および GU1 ，i = 2, . . . , d について Ui と Ki−1
を鍵とした
xor
G⊕
Ui (x) = GUi (Ki−1 ⊕ x)
という鍵付き関数である．
ま ず M を 先 頭 か ら 128 ビ ッ ト 単 位 に 分 割 し て ，M1 , M2 , . . . , Mm を 得 る ．こ こ で ，M
=
M1 ∥M2 ∥ . . . Mm−1 ∥Mm で あ り ，ま た i = 1, . . . , m − 1 に つ い て |Mi | = 128，1 ≤ |Mm | ≤ 128 で
ある．
次に Ch 関数を，
Ch[F1 , . . . , Fm−1 ](M ) = pad(Mm ) ⊕ Fm−1 (Mm−1 ⊕ Fm−2 (. . . F2 (M2 ⊕ F1 (M1 )) . . . )
として定義する（文献 [14] における同名の関数と定義が細部で異なる点に注意）．ただし Fi は 128 ビット入
出力を持つ鍵付き関数で，i = 1, . . . , d について
⊕
F(d+1)(i−1)+1 = EK , F(d+1)(i−1)+2 = GU1 , F(d+1)(i−1)+3 = G⊕
U2 , . . . , F(d+1)(i−1)+d+1 = GUd
とおく．
タグ生成は，
h = Ch[F1 , . . . , Fm−1 ](M1 ∥M2 ∥ . . . ∥Mm−1 ∥pad(Mm ))
という 128 ビット値 h を計算し，π ビットタグ T を，
{
cutπ (EK (mul2(L) ⊕ h))
if |xm | = 128
T =
cutπ (EK (mul2(mul2(L)) ⊕ h)) if |xm | < 128
として出力する．
具体的なタグ生成は Algorithm 2.2 に従って行われる．ただし，TagGen の入力のうち KeySch 出力の
xor
部分 U1 , . . . , Ud , K1xor , . . . , Kd−1
の記載は省略してある．
また，d = 1 と d = 2 でのタグ生成の例を図 2 と図 3 に示す．
2 暗号アルゴリズム仕様
6
Algorithm 2.2: TagGen(d, π, K, L, M )
Partition M into M1 , M2 , . . . , Mm
if m = 1
then 
h ← pad(M1 )

s ← 0128






for i ←

 1 to m − 1





w ← (i − 1) mod (d + 1)











if w = 0






else
then s ← EK (s ⊕ Mi )

do






 else if w = 1







 then s ← GU1 (s ⊕ Mi )







 else s ← G (s ⊕ K xor ⊕ M )


Uw
i
w−1



h ← s ⊕ pad(M )
m
if |Mm | mod 128 = 0
then h ← mul2(L) ⊕ h
else h ← mul2(mul2(L)) ⊕ h
T ← cutπ (EK (h))
return (T )
M1
M3
M2
M5
M4
M7
M6
mul2(L)
K
E
U1
G
K
E
U1
G
K
E
U1
G
K
E
T
M1
M2
M3
M6
M5
M4
M7|| 100..0
mul2(mul2(L))
K
E
U1
G
K
E
U1
G
K
E
U1
G
K
E
T
図2
PC-MAC-AES(128,1) のタグ生成の例（上：|M7 | = 128 のとき，下：|M7 | < 128 のとき．）
2.6 タグ検証
タグの検証手続き TagVer は一般的な決定的 MAC 関数のケースと同様である．すなわち，受信したメッ
セージとタグの対 (M, T ) から M を取り出し，これに対して TagGen を適用して得た結果 T ′ と受信した T
が一致すれば受理として 1 を出力し，そうでなければ棄却として 0 を出力する．TagGen 同様に KeySch
2 暗号アルゴリズム仕様
7
M1
M2
K1xorM
M3
M5
4
M6
K1xor
M7
mul2(L)
U1
E
K
G
U2
G
K
E
U1
G
U2
G
K
E
T
M1
M2
M3
K1xorM
M5
4
M6
K1xor M || 100..0
7
mul2(mul2(L))
K
E
U1
G
U2
G
K
E
U1
G
U2
G
K
E
T
図 3 PC-MAC-AES(128,2) のタグ生成の例（上：|M7 | = 128 のとき，下：|M7 | < 128 のとき）
xor
と，
を事前処理として必要とし，入力は d, π, K, L, M と KeySch 出力である U1 , . . . , Ud , K1xor , . . . , Kd−1
受信したタグ T となる．手続きを Algorithm 2.3 に記す．ただし TagVer と TagGen の入力のうち，
xor
は記載を省略してある．
U1 , . . . , Ud , K1xor , . . . , Kd−1
Algorithm 2.3: TagVer(d, π, K, L, M, T )
T ′ ← TagGen(d, π, K, L, M )
if T = T ′
then return (1)
else return (0)
2.7 バージョン情報
文献 [14] に記載の PC-MAC との相違について述べる．ここでは，簡便のため文献 [14] に記載の PC-MAC
をオリジナル PC-MAC と呼ぶことにする．オリジナル PC-MAC はそもそもブロック暗号の段間数を部分的
に取り出して使用するものであり，AES に限ったアルゴリズムではなく，原則的にはどのような（段構造を持
つ）ブロック暗号でも使用できる．また文献 [14] ではオリジナル PC-MAC を AES で実装する際に 4 段 AES
の最後の ShiftRows と MixColumns を省略して使用することが提案されているが，ここでは省略をしない．
この理由は，典型的なソフトウェア実装では SubBytes，ShiftRows，MixColumns をまとめた表を作成して
効率化を図っており，SubBytes のみの取り出しが困難あるいは可能であっても速度の低下や実装コストの増
加につながる可能性があるからである．ShiftRows と MixColumns は線形処理であり，一般的にハードウェ
ア・ソフトウェア問わず処理の負担はごくわずかである．さらに PC-MAC-AES の安全性証明は用いる部分
段関数の差分確率の上界にのみ依存している．また，部分段関数の最後の処理に ShiftRows と MixColumns
があっても差分確率の上界にはまったく影響がないため，この変更は安全性証明にも全く影響を及ぼさない
（自己評価書 [1] 参照のこと）．上記の，4 段 AES 関数の最後の ShiftRows と MixColumns を省略したバー
3 推奨用途
8
ジョンと PC-MAC-AES とは互換性はない．
また，文献 [14] ではタグ長がブロックサイズで固定であるが，汎用性を鑑みてここではタグ長をパラメータ
とし 128 ビットよりも短い値を取りうるとした．この変更による証明可能安全性への影響については自己評
価書 [1] で述べる．
3 推奨用途
推奨用途としては，比較的小規模のハードウェアや，ソフトウェア実装において省メモリ性と高速性の両
立を求めるケース，あるいはコードが動作する環境が様々に変わる環境（Java など），ハードウェア・ソフト
ウェアが混在するネットワーク，または AES-NI[2] など専用 AES 命令があるプラットフォームにおける高速
なメッセージ認証が考えられる．また，AES 以外の特別な関数を用いたユニバーサルハッシュ関数をベース
としたメッセージ認証コードと比べて，AES の実装環境のみで実装できることによる性能の予測のしやすさ，
実装の容易性が利点としてあげられる．
参考文献
[1] 自己評価書 PC-MAC-AES, 日本電気株式会社, 2010.
[2] Intel Advanced Encryption Standard (AES) Instructions Set - Rev 3,
http://software.intel.com/en-us/articles/
intel-advanced-encryption-standard-aes-instructions-set/
[3] NIST FIPS-197. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[4] NIST Special Publication 800-38B,
Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication.
http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf
[5] B. den Boer, J.P. Boly, A. Bosselaers, J. Brandt, D. Chaum, I. Damgå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,
RIPE Integrity Primitives, final report of RACE Integrity Primitives Evaluation. 1995.
[6] D. J. Bernstein. “The Poly1305-AES Message-Authentication Code.” Fast Software Encryption,
FSE’05, LNCS 3557, pp. 32-49, 2005.
[7] J Daemen and V. Rijmen. “A New MAC Construction ALRED and a Specific Instance ALPHAMAC.” Fast Software Encryption, FSE’05, LNCS 3557, pp. 1-17, 2005.
[8] J Daemen and V. Rijmen. “The Pelican MAC Function.” IACR ePrint Archive, 2005/088.
[9] S. Halevi and H. Krawczyk. “MMH:Software Message Authentication in the Gbit/second rates.”
Fast Software Encryption, FSE’97, LNCS 1267, pp. 172-189, 1997.
[10] T. Iwata and K. Kurosawa. “OMAC: One-Key CBC MAC.” Fast Software Encryption- FSE’03,
LNCS 2887, pp. 129-153, 2003.
[11] L. Keliher and J. Sui. “Exact Maximum Expected Differential and Linear Probability for 2-Round
Advanced Encryption Standard (AES).” IACR ePrint Archive, 2005/321.
[12] L. Keliher and J. Sui. “Exact maximum expected differential and linear cryptanalysis for two-round
Advanced Encryption Standard.” IET Information Security, Vol. 1, No. 2, pp. 53-57, June. 2007.
参考文献
9
[13] K. Kurosawa and T. Iwata. “TMAC: Two-Key CBC MAC.” Topics in Cryptology- CT-RSA 2003,
LNCS 2612, pp. 33-49, 2003.
[14] K. Minematsu and Y. Tsunoo. “Provably Secure MACs From Differentially-uniform Permutations
and AES-based Implementations.” Fast Software Encryption, FSE ’06, LNCS 4047, 2006.