メッセージ認証コード PC-MAC-AES

峯松 一彦 （日本電気株式会社）概要▐ ブロック暗号AESをベースとしたメッセージ認証コード（MessageAuthentication Code, MAC)
 カウンターなどの初期値は不要 （deterministic MAC）

▐ CBC-MAC同様の反復処理，ただしAESとその短縮段（4段）による処理を組み合わせることで高速化
 推奨パラメータにおいて，CBC-MAC-AESから1.4から2倍ほどの高速化が可能▐ 証明可能安全：AESが安全ならメッセージの偽造は困難
 CMAC-AESなどと同じ仮定，同じ安全性基準

Page 2© NEC Corporation 2010

技術仕様
▐ 秘密鍵 : AES 128ビット鍵K, 128ビット副鍵L (計256ビット）▐ パラメータ : オーダー d，タグ長 π ビット
 dは正整数（5以下を推奨）
 π は128以下の正整数（64以上を推奨）▐ 構成要素：AES暗号化関数 EK, 4段AES関数GU Uは後半3段分の段鍵（※）：計384ビット
 UはEKを用いた鍵スケジュールによりd個生成する（後述）
U(1)

B

S

M

B : SubBytes
S : ShiftRows
M : MixColumns
Page 3© NEC Corporation 2010

U(2)

B

S

M

U(3)

B

S

4段AES関数GU（U=(U(1)||U(2)||U(3))）

M

B

SM

※AESの正式な仕様に従えば“前半3段分の鍵”とも言える

全体構成▐ 鍵スケジュールKeySch タグ生成の前に行う事前処理 d個の384ビット鍵Uとd-1個の128ビット鍵Kxorを生成（計384d + 128(d-1) ビット）▐ タグ生成TagGen 任意長メッセージMに対してπ ビットのタグTを生成▐ タグ検証TagVer

 受信したメッセージとタグのペアが正当かどうか検証
 TagGenで求めたタグと受信したタグの比較
K, LKeySchM

TagGenT

TagVerM
TK, LKeySchTagGen
T’=?
Accept / Reject

Page 4© NEC Corporation 2010

鍵スケジュール KeySch▐ EKによるカウンターモード（Lを初期値とする）▐ d個の384ビット鍵Uとd-1個の128ビット鍵Kxorを生成 計384d + 128(d-1) ビット, d=1のときはUのみ生成
L⊕ [1] L⊕ [2]

L
K

E
U(1)1

K

E K

E

U(2)1

U(3)1

L⊕ [3d-3] L⊕ [3d-2]
…

U(1)d

U(2)dU1

Ud
L⊕ [4d-2]

L⊕ [3d] L⊕ [3d+1]
K

E
Kxor1

Page 5© NEC Corporation 2010

E

KE

KK

E
Kxor2

…

K

E
Kxord-1

L⊕ [3d-1]
KE
U(3)dタグ生成 TagGen▐ 任意長のメッセージMについてπビットタグTを計算▐ CBC-MACと類似した反復処理，EK, GU1,…,GUdが周期的にコールされる▐ 最終ブロックはLによるマスキングの後EKで暗号化
 マスク形式はCMACと同様（有限体上の2倍算）
M1

M2

M3

K1xorM

M54

M6

K1xor

M7
mul2(L)

K

E

U1

GU2

GKE

U1

GU2

GK

E
T

７ブロックメッセージの処理の例（d=2, π=128, |M7|=128）※検証手続きTagVerは通常処理なので省略
Page 6© NEC Corporation 2010

安全性評価▐ AESの擬似ランダム性のみを仮定とした証明可能安全性（選択平文攻撃による偽造困難性）を有する
 通常のブロック暗号モードによるMACと同じ仮定，同じ安全性基準• IACR主催の国際学会（Fast Software Encryption 2006）にて発表済み

 4段AESを用いた類似のMAC（alpha-MAC, Pelican）では不可能• これらは証明可能安全性を有さないため，AESそのものの安全性とは独立に攻撃が発見される可能性がある

 安全性証明において既知の4段AESの差分確率上界を利用▐ 安全性上界：おおよそq<<256回の選択平文攻撃と不正な検証に対する安全性を保証
 CMACなどではq<<264 攻撃報告があるが，上界を越えた質問回数で証明と矛盾しない• 285.5の選択平文，2128の計算量で鍵回復（Yuan et al. CRYPTO ’09）

Page 7© NEC Corporation 2010

実装性評価▐ 基本的にはAESの暗号モード
 AES段関数にアクセスできれば実装可能（例：AES-NI （インテルCPU専用AES命令））▐ 効率：CBC-MAC-AES（など）より1.4から最大2.5倍
 推奨パラメータの範囲では1.4から2.0倍の高速化
 少ないプラットフォーム依存性 10段処理1ブロック＋4段処理dブロック → 平均して4+6/(d+1)段処理／ブロック
 事前計算量とメモリはdについて線形に増加（事前計算量と速度のトレードオフ）▐ CMAC同様のパディング処理により，短いメッセージでも良い実行効率

Page 8© NEC Corporation 2010

ソフトウェア実装▐ パブリックドメインのAESソース利用の実装例
 CPU : Intel Core Duo 1.66GHz
 OS : Microsoft Windows XP Professional
 記述言語 : ANSI C
 コンパイラ : Microsoft Visual C++ 2008 Express Edition
 最適化 : 速度最適化（/O2オプション指定）
平均サイクル数（32 ブロックメッセージ）
MAC

KeySchTagGenPC-MAC-AES (d=1)

1532

10158

PC-MAC-AES (d=2)

3101

9204

PC-MAC-AES (d=3)

4601

8803

PC-MAC-AES (d=4)

6327

8614

PC-MAC-AES (d=5)

7711

8396

CMAC-AES

759

12991

※可読性と移植性重視のため, FSE’06での実装よりCMAC-AESとの性能比で若干劣る
Page 9© NEC Corporation 2010

ハードウェア実装▐ AESのハードウェア記述言語（HDL）を利用して効率よく実装することが可能▐ 実装例（Verilog-HDL） ターゲットデバイス : Virtex5 xc5vlx50-3
 設計ツール : Xilinx ISE ver9.2i
 合成オプション: 速度優先，effort high指定，そのほかはデフォルト▐ 合成結果 スライス数 : 4356
 最高動作周波数 : 128MHz

Message

K-key register
MUX

Standard
AES keyscheduler
U1-key registerU2-key registerU3-key register

MUX

Standard
AES data path+++MUX

Data register
MAC register

MAC value

Page 10© NEC Corporation 2010

L-key registerライセンス情報▐ 民間企業等による営利目的の使用の場合を除き，無償とする予定
 有償の場合は妥当かつ非差別的条件で実施を許諾する

Page 11© NEC Corporation 2010

開発チーム▐ 技術統括：角尾 幸保 （NEC）▐ 設計者：峯松 一彦 （NEC）▐ SW実装：久保 博靖，洲崎 智保，茂 真紀，齊藤 照夫，川幡 剛嗣，中川 弘勝 （NECソフトウェア北陸）、辻原 悦子（ワイ・デー・ケー）▐ HW実装：森岡 澄夫 （NEC）

Page 12© NEC Corporation 2010