Security Evaluation of PC-MAC-AES

February, 2011

Lei Wang (University of Electro-Communications)Kazuo Sakiyama (University ofElectro-Communications)
Iwamasa Nishikado (Cyber Creative Institute)Kazuo Ohta (University of Electro-Communications)目次
1. PC-MAC-AES の効率と安全性のトレードオフについての要旨
2. PC-MAC-AES の安全性評価（本文）PC-MAC-AES の効率と安全性のトレードオフについての要旨

Summary On Eﬃciency/Security Tradeoﬀ of PC-MAC-AES

PC-MAC-AES の効率と安全性のトレードオフについての要旨

本報告書では PC-MAC-AES 技術の妥当性を検証するために次の観点で検討した．

PC-MAC 構成法の安全性について
MAC 構成技術の歴史的な流れにそって，MAC 構成技術を図４のグループに分けて，PC-MAC に適用可能な攻撃法を網羅した（表１). PC-MAC 固有の攻撃方法
Subkey-Recovery Attack と DIS-PC-MACEK (·),RP attack (Section 7 参照) を発見した。
提案された PC-MAC-AES では，高速化を実現するために 4 ラウンドの AES（本来の AES は 10 ラウンド）を構成要素として使用するので，PA-MAC の構成
で 4 round AES を使った場合の安全性についても検討した．
その結果，第 8 章に示す新しい攻撃法を発見した．この攻撃法は図 4 で示す
CBC MAC 配下のすべての構成法に対して有効であり，今回発見した攻撃方法は，
PC-MAC 構成に対する固有の脆弱性ではない．
なお，今後も，PC-MAC-AES 固有の攻撃方法が発見される可能性は残されている．
補足: 本報告書で指摘したすべての攻撃法の計算量は，設計者によって与えられた安全性証明のバウンド，すなわち如何なる攻撃に要する攻撃の下限値よりも大きな値であった．よって，これらの攻撃法は PC-MAC-AES の安全証明と矛盾する，あるいはそれを否定するものではない．

PC-MAC-AES の効率について
ブロック長 l であるメッセージに対し、PC-MAC-AES は AES を 0.4 ∗ l ∼ 0.7 ∗ l
回使う。CBC MAC は AES を l 回使う。PC-MAC-AES は CBC MAC より 1.4∼ 2.5 倍速い。

CRYPTREC 候補とするかの判断について
CMAC [16] と比較して，その優位性が確認できれば，CRYPTREC に採用してよいと考える．
安全性の観点からは，Subkey-Recovery Attack と DIS-PC-MACEK (·),RP attack (Section 7 参照) が可能なので，PC-MAC 構成は劣っている．速度の観点か
らは，PC-MAC-AES は CMAC に比べて 1.4 ∼ 2.5 倍高速である1 ．
1 CMAC は一部で 4 ラウンドの AES を使うと、CMAC の方がコンパクトな実装が可能と思われるが、安全性証明ができなくなると思われる。両方式の比較は継続検討が必要と思われる．

4

Summary On Eﬃciency/Security Tradeoﬀ of
PC-MAC-AES

In order to contribute to a fair judgment on PC-MAC-AES, we will make acomparison between PC-MAC-AES [15] and three other MACs based on AES:EMAC [1], MacDES [11]2 and TMAC [12], which are described in Figures 1, 2
and 3, respectively. We refer the speciﬁcation of PC-MAC-AES to main bodyof this report (Section 2). The reasons why we select these three MACs are:I. each of these MACs uses two independent keys, which is the same with PCMAC-AES;
II. the diﬀerences between these MACs will be used by us to separate CBC
MAC variants into several groups (see Figure 4). We will discuss thediﬀerence of the security margin (by proposing concrete attacks) among
these groups, whose result is summarized in Table 1.

1. High Eﬃciency of PC-MAC-AES
Among these MACs, the most eﬃcient MAC is PC-MAC-AES, and the slowest
one is MacDES. The detailed argument is as follows.
Suppose that an input message (after padding) is l blocks long. We willcount the number of executions of AES (full version: 10 rounds). Moreover,
we will consider the complexity on average, and thus ignore the complexity of
pre-process.
• MacDES: l + 2 executions.
• EMAC-AES: l + 1 executions.
• TMAC-AES: l executions.
• PC-MAC-AES: suppose l = (d + 1) × t + s, where d is a positive integer asla parameter of PC-MAC-AES, t and s are positive integers, t ≤ d+1
ands ≤ d. The number of executions of AES is (1 + 0.4 ∗ d) ∗ t + 0.4 ∗ (s − 1) + 1≤ (1+0.4∗d)∗l+ 0.4 ∗ d + 1. Loosely speaking, PC-MAC-AES needs 0.4 ∗ ld+1∼ 0.7 ∗ l executions, which depends the value of d.
Therefore PC-MAC-AES is about 1.4 to 2.5 times faster than the other three
MACs.

2 MacDES is designed based on the block cipher DES. Here for a comparison, we willconsider a MacDES variant which is based on AES.

5

K and K ′ are two independent secret keys.
Figure 1: EMAC

K and K ′ are two independent secret keys, and K ′′ is derived from K ′ .
Figure 2: MacDES

K and K ′ are two independent secret keys.
Figure 3: TMAC

6

2. Security Margin Loss of PC-MAC-AES
Improving eﬃciency is usually with a loss of security margin. First of all, we
will discuss the security margin loss of PC-MAC [13], compared with EMAC [1],MacDES [11] and TMAC [12]. Then we will discuss the security margin loss of
CBC MAC variants based on 4-round AES, compared with those based on fullround AES. Finally we make a comparison between PC-MAC-AES and CMAC
[16], which was recommended for block-cipher-based authentication mode by
NIST in 2005, on the eﬃciency/security tradeoﬀ.

2.1 Security Margin Loss of PC-MAC
PC-MAC seems not designed completely from scratch. It seems to have adopted
several design features of priorly proposed MACs. The historical developmentfrom original CBC MAC [2] to PC-MAC is shown in Figure 4.

Figure 4: Historical Development of CBC MAC Variants

We will separate the security margin loss of PC-MAC into two cases.
• Loss because of adopting prior design features.
Namely the security loss is not restricted to just PC-MAC, but sharedwith other priorly proposed MACs. We have summarized several featuresof PC-MAC.
– On-the-ﬂy. This feature is from original CBC MAC, and shared withall its variants.
Loosely speaking, on-the-ﬂy structure means that
1) message is divided to blocks;2) blocks is hashed sequentially; and3) each block is hashed only once.

7

– Suﬃx. This feature is from EMAC, and shared with its variants suchas XCBC [4], TMAC and OMAC [8]. EMAC and its variants diﬀer
from original CBC MAC only in the last block cipher operation.
Loosely speaking, suﬃx structure means that the iteration sequencesof block ciphers for processing message M2 and for part M2 of M1 ||M2 ,where M1 is a message of multiple-block length, are the same.
EMAC is a suﬃx MAC, while MacDES is a suﬃx-free MAC. And
the reason is explained in Figures 5 and 6.

The iteration sequences of block ciphers to process m1 ||m2 are the same:
EK ||EK ||EK ′ .
Figure 5: EMAC is suﬃx

The iteration sequences of block ciphers to process m1 ||m2 are diﬀerent:
EK ||EK ′ ||EK ||EK ′′ and EK ||EK ||EK ′′ .
Figure 6: MacDES is suﬃx-free.

8

– Tweaking key. This feature is from XCBC, and shared with its variants such as TMAC and OMAC [8].
Loosely speaking, tweaking key means that a secret key is used to
XOR the input of the last block cipher operation.
XCBC uses two independent tweaking keys: one is for messages withmultiple blocks length and the other one is for messages with nonmultiple block length. Later TMAC made a modiﬁcation, which uses
only one secret tweaking key, and the other tweaking key is derived
from it. PC-MAC follows the same way with TMAC.
• Loss because of new design features of PC-MAC-AES.
Namely the security loss is restricted to PC-MAC. We have summarize
one new feature of PC-MAC.
– Subkey generation algorithm. All the keys of auxiliary permutations
are generated by using the tweaking key and the block cipher.

In the following, we will discuss the security margin loss of PC-MAC indetail. Again in order to contribute to a fair judgment on PC-MAC, we will
discuss the security margin loss (by pointing out concrete attacks) from original
CBC MAC to PC-MAC, which is also summarized in Table 1.
2.1.1 Security Margin Loss of CBC MAC and MacDES
With a complexity of the birthday bound, an attacker is able to carry out• Distinguishing MAC from a random function. (Section 4.1 )Attacker will identify an oracle of being either MAC or a random function.
• Existential Forgery Attack. (Section 4.2)
Attacker will provide a message/tag pair, where the message was not priorly queried to MAC.
• Selective Forgery Attack. (Section 4.3)
Attacker will select a message she needs, and then forge a valid tag without
directly querying it to MAC.
2.1.2 Security Margin Loss of EMAC
With a complexity of the birthday bound, besides the above attacks, anattacker is further able to carry out• Internal-State-Recovery Attack. (Section 5.1)
Attacker will recover the value of an internal state of some message.

9• Universal Forgery Attack. (Section 5.2)
Attacker is able to forge valid tags for any given message without querying
it to MAC.
• Low Complexity-on-Average Universal Forgery Attack. (Section 5.2)
Here by complexity-on-average, we mean the attacker will forge more than
one message, and we count the complexity of forging one message on
average.
Moreover, the attacker is also able to carry out• Full-Key Recovery Attack. (Section 5.3)
Suppose the master key has k bits, and the tweaking key has n bits.
It takes 2n/2+1 queries, 2n/2+1 memory and 2k+1 + 2k computations torecover both of them, which is faster than the brute-force attack.
2.1.3 Security Margin Loss of TMAC
With a complexity of the birthday bound, besides all the above attacks, anattacker will further be able to carry out• Partial-key Recovery Attack. (Section 6.1)
The secret key, which is used to tweak the last block, will be recovered.
• Low Complexity-on-Average Internal-State Recovery Attack.
6.3)(Section

Moreover, the attacker will be able to carry out• Full-Key Recovery Attack Faster than the Attacks on EMAC. (Section
6.4)
There are two improved key-recovery attacks. The ﬁrst approach is to savememory, which needs 2 queries, 2 memory and 2k+1 computations. The
second approach is to save time complexity, which needs 2n/2+1 queries,
2n/2+1 memory and 2k + 2k/2+1 computations.
2.1.4 Security Margin Loss of PC-MAC
With a complexity of the birthday bound, besides the above attacks, anattacker will be able to carry out• Subkey-Recovery Attacks. (Section 7.1)
All the keys of auxiliary permutations will be recovered.
• Distinguishing a PC-MAC based on a dedicated block cipher, e.g. AES,
from PC-MAC based on random permutations. (Section 7.2)

10

Table 1: On Security Margin Loss of CBC MAC Variants
Birthday Bound Attacks (2n/2 )Features
Applicable MACs
Attack Scenario
On-the-ﬂy;
Most CBC MAC
DISMAC,RF ;variants
Existential forgery attack;Selective forgery attack;On-the-ﬂy;
EMAC; XCBC;DISMAC,RF ;Suﬃx;
ANSI retail MAC; [3] Existential forgery attack;
TMAC, CMAC [16];Selective forgery attack;
PC-MACInternal-state recovery attack;
Universal forgery attack;Low complexity-on-average
universal forgery attack;On-the-ﬂy;
XCBC; TMAC;DISMAC,RF ;
Suﬃx;
CMAC;
Existential forgery attack;Tweaking key; PC-MAC
Selective forgery attack;Internal-state recovery attack;
Universal forgery attack;Low complexity-on-average
universal forgery attack;
TMAC, CMAC;
Low complexity-on-average
PC-MAC;Internal-State-Recovery Attack
TMAC;
Partial-key Recovery Attack;
PC-MAC;Speciﬁc Attacks on PC-MAC:
Subkey-Recovery Attack;Subkey Generation Algorithm
DIS-PC-MACEK (·),RP ;On-the-ﬂy;
Suﬃx;

Attack beyond Birthday Bounds (2k )EMAC; XCBC;
Full-key recovery attack;
ANSI retail MAC;
(complexity: 2k+1 )TMAC; PC-MAC;
TMAC; PC-MAC;
Full-key recovery attack;(complexity: 2k )On-the-ﬂy;
Suﬃx;
Tweaking key;
We refer DISMAC,RF to as distinguishing a MAC from a random function,
and DIS-PC-MACEK (·),RP to as distinguishing PC-MAC based on E (·) fromK

PC-MAC based on random permutations. Denote the length of tag and key asn and k respectively.
Statement. All these attacks have complexities larger than the security boundproved by the designers. Thus, these attacks don’t contradict with or disprove
the provable security bound of PC-MAC-AES.

11

2.2 Security Margin Loss of Using 4-Round AES
For a CBC MAC variant using 4-round AES, besides the attacks listed in Table
1, with a complexity of the birthday bound, an attacker is able to carry out• Internal-state-recovery attack. (Section 8.3)
• Subkey-recovery attack. (Section 8.2)
The attacker is able to recover the round keys of 4-round AES.
Of course these attacks are applicable to PC-MAC-AES.

2.3 Comparison between CMAC and PC-MAC on Eﬃciency/Security Tradeoﬀ
NIST has recommended CMAC [16] for block-cipher-based authentication in2005. Here we brieﬂy make a comparison between CMAC and PC-MAC.
• On eﬃciency. For l blocks long messages, CMAC based on AES needs l
executions, while PC-MAC-AES needs 0.4 ∗ l ∼ 0.7 ∗ l executions. Thus
PC-MAC-AES is 1.4 ∼ 2.5 times faster than AES-based CMAC.
• On security. As shown in Figure 4, CMAC also have features: on-theﬂy, suﬃx and tweaking key. Thus the security margin diﬀerence between CMAC and PC-MAC will be the attacks based on new featuresof PC-MAC, which are subkey-recovery and DIS-PC-MACEK (·),RP attacks. Note CMAC does not have subkeys. Thus the security margin loss
from CMAC to PC-MAC will be DIS-PC-MACEK (·),RP attacks.

12

PC-MAC-AES の安全性評価（本文）

Security Evaluation of PC-MAC-AES(Main Body)

Contents
1 Backgrounds
21
1.1 Security Requirements on MAC . . . . . . . . . . . . . . . . . . . 21
1.2 Common Attacks on MAC . . . . . . . . . . . . . . . . . . . . . . 22
2 PC-MAC-AES
23
2.1 Speciﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.1 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.2 PC-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.3 PC-MAC-AES . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Hash-to-PRF to Build VIL-PRF . . . . . . . . . . . . . . 26
2.2.2 CBC Iteration to Build AUHF . . . . . . . . . . . . . . . 27
2.2.3 Novelty Design of PC-MAC . . . . . . . . . . . . . . . . . 27
3 Comparison Between PC-MAC-AES and Other Block-CipherBased MACs
29
3.1 On-the-ﬂy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Suﬃx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Tweaking Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 New Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 Type I of Attacks: Weakness of on-the-ﬂy Structure31
4.1 DISPC-MAC-AES, RF Attacks . . . . . . . . . . . . . . . . . . . 31
4.1.1 Approach Using Internal Collisions . . . . . . . . . . . . . 31
4.1.2 Approach Using Bijection of Permutation . . . . . . . . . 32
4.2 Existential Forgery Attack . . . . . . . . . . . . . . . . . . . . . . 33
4.3 Selective Forgery Attack . . . . . . . . . . . . . . . . . . . . . . . 33
5 Type II of Attacks: Weakness of Suﬃx Structure35
5.1 Internal-State-Recovery Attack . . . . . . . . . . . . . . . . . . . 35
5.2 Low Complexity-on-Average Universal Forgery Attack . . . . . . 36
5.3 Key Recovery Attack . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.3.1 Approach Using Internal Collisions . . . . . . . . . . . . . 37
5.3.2 Approach Using Internal-State-Recovery Attacks . . . . . 38
6 Type III of Attacks: Weakness of Tweaking Keys
39
6.1 Partial-Key-Recovery Attack . . . . . . . . . . . . . . . . . . . . 39
6.2 Universal Forgery Attack . . . . . . . . . . . . . . . . . . . . . . 40
6.3 Low Complexity-on-Average Internal-State-Recovery Attack . . . 41
6.4 Full Key Recovery Attack . . . . . . . . . . . . . . . . . . . . . . 41
6.4.1 Approach of Saving Memory . . . . . . . . . . . . . . . . 41
6.4.2 Approach of Saving Time . . . . . . . . . . . . . . . . . . 42

14

7 Attack of Type IV: Weakness of Subkey Generation Algorithm 43
7.1 Subkey-Recovery Attack . . . . . . . . . . . . . . . . . . . . . . . 43
7.2 DIS-PC-MACAES, RP Attacks . . . . . . . . . . . . . . . . . . . . 44
8 Attacks of Type V: Weakness of AES-4R
46
8.1 Minimum Available Information . . . . . . . . . . . . . . . . . . 46
8.2 Subkey-Recovery Attacks . . . . . . . . . . . . . . . . . . . . . . 47
8.2.1 Useful Properties of AES . . . . . . . . . . . . . . . . . . 48
8.2.2 How to Recover K4 . . . . . . . . . . . . . . . . . . . . . 49
8.2.3 Detailed Procedure of Recovering K4 . . . . . . . . . . . . 50
8.2.4 How to Recover K3 . . . . . . . . . . . . . . . . . . . . . 52
8.2.5 How to Recover K2 . . . . . . . . . . . . . . . . . . . . . 53
8.3 Internal-State Recovery Attack . . . . . . . . . . . . . . . . . . . 54
9 Conclusion
55
9.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 55
9.2 For CRYPTOREC Committee . . . . . . . . . . . . . . . . . . . 56

15

Abstract of Main Body
This report will evaluate the security of PC-MAC-AES and its underlying
components. This report consists of 9 sections.
Section 1 will brieﬂy introduce the backgrounds of Message Authentication
Code (MAC). More precisely, we will introduce the security requirements on
MAC, and common attack models on MAC.
Section 2 will brieﬂy recall the speciﬁcation of PC-MAC-AES and its design
rationale, which has been included in the designers’ report.
Section 3 will make a comparison between PC-MAC-AES and other blockcipher-based MACs, and derives several interesting features: on-the-ﬂy, suﬃx,
Tweaking key, which are shared by PC-MAC-AES and other MACs. On eachfeature, we will specify MACs which share it with PC-MAC-AES. Moreover, wederive new features of PC-MAC. This will contribute to a fair understanding of
the meaning of our attacks on PC-MAC-AES in Section 4 ∼ 7.
Sections 4 ∼ 7 will evaluate the security of PC-MAC-AES, which is the mainpart of this report. We will describe distinguishing, forgery, internal-staterecovery, and key-recovery attacks on PC-MAC-AES.
Previous Works. Strictly speaking, so far only two papers were published explicitly on the evaluation of PC-MAC-AES. One was published by Yuan
et al. in CRYPTO 2009 [20], which proposed internal-state-recovery andfull-key-recovery attacks. The other one was published by Jia et al. in
CANS 2009 [9], which proposed a forgery attack. However, PC-MAC-AES
shares similar structures with other MACs such as TMAC and CMAC.
Therefore previous published attacks on other MACs may also be applicable to PC-MAC-AES.
• The designers have mentioned the possible applicability ofprevious attacks, which were published to attack other MACs
instead of PC-MAC-AES, in their report. However, they
did not state which previous attacks can be adapted to attack PC-MAC-AES and how much the complexity will be.
Our Works. We divide our evaluations into two cases.
Case I. We will summarize and describe several attacks including distinguishing, forgery and key-recovery attacks on PC-MAC-AES, mostof which were previously proposed to attack other prior MACs. Interestingly, our full-key-recovery attacks on PC-MAC-AES are more
eﬃcient than Yuan et al.’s attack [20]. 3
Case II. We will propose several novel attacks on PC-MAC-AES, which
are based on its new features.
3 On the other hand, Yuan et al.’s attack seems to have wider applications.

16

1. Subkey-recovery attacks.
xor
Subkeys {U1 , U2 , . . . , Ud , K1xor , . . . , Kd−1
} are generated by using
L and EK (·). We showed that after obtaining the knowledge ofL, these subkeys can be easily recovered. The complexity is justone chosen query for each subkey.
2. Distinguish PC-MAC-AES from PC-MAC-RP.
We will propose an attack procedure, which can distinguish PCMAC-AES from another PC-MAC instantiation with a Random
Permutation (RP).
Section 8 will focus on an interesting question:
what potential weakness will the usage of 4-round AES introduce toCBC-MACs including PC-MAC-AES and its variants?
As we can see, the most attractive design point of PC-MAC-AES is using
4-round AES permutations instead of the full-round AES to process partial message blocks, which will improve the eﬃciency, but still keep provable security.
The theoretical foundation of such replacement is that 4-round AES with independent round keys have similar diﬀerential property with full-round AES.
Besides PC-MAC-AES, several other MACs such as Pelican-MAC [6] are alsousing 4-round AES to improve the eﬃciency. On the other hand, a question willarise: will such replace weaken the security of CBC-MACs from any sense?
Our answer is yes. We will propose an attack on generic CBC-MAC variants
based on 4-round AES with independent round keys. More precisely, we areable to recover the round keys and the internal state value with a complexity of
267 online queries and 240 oﬄine computations.
Our attack implies an upper bound of subkey-recovery resistance for CBCMAC variants based on 4-round AES.
Section 9 will conclude this report.

17

Abbreviations and Notations
AES• AES · · · · · · Advanced Encryption Standard• P · · · · · · Plaintext• C · · · · · · Ciphertext• SB · · · · · · SubByte• SR · · · · · · ShiftRow• MC · · · · · · MixColumn• ARK · · · · · · AddRoundKey• AES-4R · · · · · · 4-Round AES with independent round keys
• Byte order of 4 × 4 byte matrix:• Internal state notation {S1 , S2 , . . . , S16 } in AES-4R:• Si,j · · · · · · Byte j of Si• ∆Si,j · · · · · · Diﬀerence at byte Si,j

PC-MAC-AES• MAC · · · · · · Message Authentication Code• UF-CMA · · · · · · UnForgeability against Chosen Message Attack• CBC · · · · · · Cipher Block Chaining• PCH · · · · · · Periodic CBC Hash
• TGK (·) · · · · · · Tag Generation oracle• VFK (·, ·) · · · · · · tag VeriFication oracle18

• M · · · · · · Message• T · · · · · · Tag• K · · · · · · Secret key• EK (·) · · · · · · AES with the seret key as K
• L · · · · · · Tweaking key• {G1 , . . . , Gd } · · · · · · AES-4R in PC-MAC-AES• Ui (= Ui1 ||Ui2 ||Ui3 ) · · · · · · Round keys in Gi
xor• {K1xor , . . . , Kd−1
} · · · · · · Mask keys

Others• ⊕ · · · · · · Bitwise XOR• ≪ 1 · · · · · · Left shift by 1 bit• a||b · · · · · · a concatenated with b• |a| · · · · · · bit length of a
• [t] · · · · · · 128-bit binary encode of integer t• MDP · · · · · · Maximum Diﬀerential Probability• MEDP · · · · · · Maximum Expected Diﬀerential Probability• AUHF · · · · · · Almost Universal Hash Function• RF · · · · · · Random Function• PRF · · · · · · Pseudo-Random Function• RP · · · · · · Random Permutation• A · · · · · · Attacker• DISMAC,RF · · · · · · Distinguish MAC from RF• DIS-PC-MACAES,RP · · · · · · Distinguish PC-MAC-AES from PCMAC-RP

19

List of Figures
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

EMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MacDES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
TMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Historical Development of CBC MAC Variants . . . . . . . . . .
EMAC is suﬃx . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MacDES is suﬃx-free. . . . . . . . . . . . . . . . . . . . . . . . .
One AES Round Operation ARK ◦ MC ◦ SR ◦ SB(·) . . . . . . .
Key Schedule Algorithm . . . . . . . . . . . . . . . . . . . . . . .
Periodic CBC Hash . . . . . . . . . . . . . . . . . . . . . . . . . .
Auxiliary permutation Gi . . . . . . . . . . . . . . . . . . . . . .
CBC iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
AUHF based on permutations with small MEDP . . . . . . . . .
Selective forgery attack . . . . . . . . . . . . . . . . . . . . . . .
Internal state recovery attack . . . . . . . . . . . . . . . . . . . .
Universal Forgery Attack . . . . . . . . . . . . . . . . . . . . . .
Partial-key Recovery Attack . . . . . . . . . . . . . . . . . . . . .
Universal Forgery Attack . . . . . . . . . . . . . . . . . . . . . .
Internal State Recovery Attack . . . . . . . . . . . . . . . . . . .
Recover U11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
AES-4R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
AES-4R to process i-th block . . . . . . . . . . . . . . . . . . . .
2-Round Diﬀerential Path with a Probability 1 . . . . . . . . . .
4-Round Diﬀerential Path Used in Our Attacks . . . . . . . . . .
First Diﬀerential path for recovering K3 . . . . . . . . . . . . . .
Second Diﬀerential path for recovering K3 . . . . . . . . . . . . .
Diﬀerential path for recovering K2 . . . . . . . . . . . . . . . . .

20

6
6
6
7
8
8
23
24
24
25
27
28
33
35
36
39
40
41
43
46
47
48
49
52
53
54

1

Backgrounds

This section consists of• Security requirements on MAC• Common attacks on MAC

Message Authentication Code (MAC) is a symmetric-key cryptosystem, which
provides a short tag for a message to protect both its integrity and its authenticity. Suppose Alice and Bob share a common key K, and agree on a tag
generation protocol T GK (·). When Alice sends a message M to Bob, she will
send both M and T GK (M ). When Bob receives the message/tag pair, he willcompute T GK (M ) using his own copy of K, and check whether it matches withthe tag from Alice. If it matches, Bob is assured that
1) the message is from Alice; and2) the message is not modiﬁed by a third party.

1.1

Security Requirements on MAC

The most important security requirement on MAC is unforgeability: it should
be hard for a third party without the knowledge of the secret key K to generate
a valid tag for a message. The following is the formal deﬁnition of Unforgeability
against Chosen Message Attack (UF-CMA).
Deﬁnition 1.1.0.1 Let TG: {0, 1}k × {0, 1}∗ −→ {0, 1}n be a message authentication code. For a randomly chosen key K ←− {0, 1}k , denote by TGK (·)
the tag generation oracle. Denote by V FK (·, ·) the tag veriﬁcation oracle, which
outputs 1 if the message/tag pair is valid, and outputs 0 otherwise. If within
practical resource (time, memory etc) no attacker A with access to TGK (·) andVFK (·, ·) can produce a message/tag pair of (M, T ) satisfying the following two
conditions with a non-negligible probability:• VFK (M, T ) = 1; and• A did not priorly query M to TGK (·),
we will say this MAC satisﬁes Unforgeability against Chosen Message Attack(UF-CMA).
A random function (RF) surely can satisfy UF-CMA, because the successprobability of any attacker forging RF is at most 2−n . Due to the following
theorem, if a MAC is proven indistinguishable from RF, it satisﬁes UF-CMA.
21

Theorem 1.1.0.1 Denote by Advuf-cma (q, σ) the upper bound of success probability of a forgery attacker, where q and σ are the number of queries and the total
number of queried message blocks made by the attacker. Denote by Advprf (q, σ)
the upper bound of success probability of an attack distinguishing MAC from arandom function. The following relation holds.
Advuf-cma (q, σ) ≤ Advprf (q, σ) + 2qn
Thus, a stronger security property on MAC is Pseudo-Random Function.
The formal deﬁnition is as follows.
Deﬁnition 1.1.0.2 Let TG: {0, 1}k × {0, 1}∗ −→ {0, 1}n be a message authentication code. For a randomly chosen key K ←− {0, 1}k , denote by TGK (·) the
tag generation oracle. Let RF (·) be a random function having the same domain
and range with TGK (·). If within practical resource no distinguisher can distinguish TGK (·) from RF (·) with a non-negligible probability, we will say thisMAC satiﬁes Pseudo-Random Function (PRF).

1.2

Common Attacks on MAC

There are several types of attacks on MACs. Denote by A the attacker.
• DISMAC,RF : A will identify an oracle of either TGK (·) or RF. Namely
A aims to evaluate the PRF property of MAC.
• DISMAC-BC, MAC-RP : suppose a MAC iterates a block cipher (BC).A
will distinguish a block cipher (BC) from a random permutation (RP) under the MAC environment. Namely, A will identify an oracle of MAC
iterating either BC or a RP.
• Forgery attack: A is able to access to TGK (·) and VFK (·, ·), and willproduce a valid tag T for a message M , which was not priorly queried to
TGK (·).
There are three types of forgery attacks.
– Existential forgery attack: no constraint is set on M . Thus M
could be any message, e.x. without any particular meaning.
– Selective forgery attack: M is selected by A.
– Universal forgery attack: for any message M , A can forge a valid
tag.
• Internal-state recovery attack: A is able to access to TGK (·), andwill recover an intermediate state of some message.
• Key recovery attack: A is able to access to TGK (·), and will recover
the secret key K.

22

2

PC-MAC-AES

This section consists of• Speciﬁcation of PC-MAC-AES• Design rationale of PC-MAC-AES• Comparison with other MACs

2.1

Speciﬁcation

2.1.1

AES

The Advanced Encryption Standard (AES) [7] is a block cipher adopting theSubstitution-Permutation Network. AES has three variants diﬀering in the key
size and the number of rounds. We will mainly deal with one variant, whichuses a 128-bit key and consists of 10 rounds. In the rest of this paper, we refer
AES to as this variant.
The plaintext block size is 128 bits and represented by a byte matrix ofsize 4 × 4. The state matrix will go through a serial of rounds. Each roundapplies the following four operations to update the state matrix., which is also
illustrated by Fig. 7.
SubBytes (SB) : apply a 8-bit to 8-bit S-box on each byte of the state matrix;
ShiftRows (SR) : cyclic left shift the i-th row of the state matrix by i bytes(0 ≤ i ≤ 3);
MixColumns (MC) : multiply each column of the state matrix by a constant4 × 4 matrix.
AddRoundKeys (ARK) : XOR the state with a 128-bit subkey;

Figure 7: One AES Round Operation ARK ◦ MC ◦ SR ◦ SB(·)

23

Moreover, the ﬁrst round applies an additional ARK operation for whitening
the plaintext, which becomes ARK ◦ MC ◦ SR ◦ SB ◦ ARK(·). The last roundomits the MC operation, which becomes ARK ◦ SR ◦ SB(·).
AES transforms the 128-bit key k to eleven128-bit subkeys {k0 , k1 , . . . , k10 }. The algorithm is
as follows, which is also illustrated in Fig. 8. k
is divided into four 32-bit words W0 ||W1 ||W2 ||W3 ,which is expanded to W0 || · · · ||W43 , and regrouped
to construct ki : W4i ||W4i+1 ||W4i+2 ||W4i+3 . The
expansion algorithm is as follows.
for i = 4 to 43 do
if i = 0 mod 4 thenWi = Wi−4 ⊕ Rotate(SB(Wi−1 )) ⊕ C
else
Wi = Wi−1 ⊕ Wi−4
end ifend for
where Rotate(·) rotates the word by 8-bits, andFigure 8: Key Schedule
C is predetermined constant.
Algorithm
2.1.2

PC-MAC

PC-MAC [13] splits a message M into blocks m1 ||m2 || · · · ||ml . If ml is short ofa full block, it will be padded a single bit ‘1’ and a number of of ‘0’s.
PC-MAC iterates a structure named Periodic CBC Hash (PCH), which
is built by using a block cipher EK (·), a set of keyed auxiliary permutations
xor},{G1 , G2 , . . . , Gd } (d: a positive integer) and a set of mask keys {K1xor , . . . , Kd−1
to hash m1 || · · · ||ml−1 . Denote the output as Y . PCH is described in Figure 9.

Figure 9: Periodic CBC Hash

PC-MAC uses a sub-key L to process the last block ml . If ml is a full block,a tag T is computed as EK (Y ⊕ (L • u) ⊕ ml ). Otherwise, T is EK (Y ⊕ (L •u2 ) ⊕ (ml ||10 · · · 0)).
Note on secret keys. PC-MAC uses two independent keys K and L. {U1 , U2 ,24

xor
. . . , Ud , K1xor , . . . , Kd−1
} are all generated by using EK (·) and L, where Ui is
the secret key in Gi .

2.1.3

PC-MAC-AES

PC-MAC-AES [15] instantiates EK (·) as AES with a 128-bit key and Gi as a 4round AES permutation with independent round keys (AES-4R). Gi is describedin Figure 10, which shows that Ui consists of 3 round keys, and thus is 384 bits
long.

Figure 10: Auxiliary permutation Gi
Uij and Kixor are generated as follows:• Uij = EK (L ⊕ [3 ∗ (i − 1) + j − 1]), and• Kixor = EK (L ⊕ [3d + j − 1]),
where [t] is 128-bit binary encode of integer t.
L • u in ﬁnite ﬁeld GF(2128 ) is detailed as below, and denoted as mul2(L) in
the rest of this report.
{
L≪1
if msb(L) = 0
mul2(L) =120(L ≪ 1) ⊕ (0 ||10000111) else
A pseudo-code description of PC-MAC-AES is shown below in Algorithm 1.

25

Algorithm 1 PC-MAC-AES(K, L, M )Pre-process:for i = 1 to d do
Ui1 → EK (L ⊕ [3 ∗ (i − 1)])Ui2 → EK (L ⊕ [3 ∗ (i − 1) + 1])
Ui3 → EK (L ⊕ [3 ∗ (i − 1) + 2])
end forfor i = 1 to d − 1 do
Kixor = EK (L ⊕ [3d + i − 1])
end for
Generate tag:m1 ||m2 || · · · ||ml ← M
if l = 1 thenh ← pad(m1 )elses ← 0128
for i = 1 to l − 1 dow ← (i − 1) mod (d + 1)
if w = 0 thens ← EK (s ⊕ mi )else if w = 1 thens ← G1 (s ⊕ mi )else
xor
⊕ mi )s ← Gi (s ⊕ Kw−1
end ifend forend ifif ml is 128 bit long thenh ← mul2(L) ⊕ helseh ← mul2(mul2(L)) ⊕ h
end ifT ← EK (h)return T

2.2

Rationale

2.2.1

Hash-to-PRF to Build VIL-PRF

A well-known approach, usually named Hash-to-PRF, to build a variable-inputlength pseudo-random function (VIL-PRF) is concatenating an Almost-Universal
Hash Function (AUHF) deﬁned below and a ﬁxed-input-length pseudo-randomfunction (FIL-PRF).

26

Deﬁnition 2.2.1.1 Let H be a function: {0, 1}k × {0, 1}∗ → {0, 1}n . For two
messages M and M ′ , the colliding probability on H is
ΣK∈{0,1}k Pr[H(K, M ) = H(K, M ′ )].
2k
If CollH (M, M ′ ) ≤ ϵ holds for any two messages M and M ′ , we will saythat H is an ϵ-almost universal hash function (ϵ-AUHF).
CollH (M, M ′ ) =Loosely speaking, for a new messages inputted into AUHF, the output will
be diﬀerent from previous queried messages with an overwhelming probability. Then after the re-mapping of PRF, the ﬁnal output will be random anduniformly distributed.
2.2.2

CBC Iteration to Build AUHF

An approach to build an AUHF is Cipher Block Chaining (CBC) iteration,
which is shown in Figure 11. CBC iteration has been proven to be AUHF
assuming F is a RF [4].

Figure 11: CBC iteration

2.2.3

Novelty Design of PC-MAC

Adopting Hash-to-PRF and CBC iteration, one can build a provable VIL-PRF,
which is a secure MAC. However, the assumption on F is too strong. When such
a MAC is practically implemented, one have to instantiate F to a complicatedfunction to preserve the security conﬁdence.
PC-MAC introduces extra mask keys to reduce the assumption on the underlying component to a weaker property Uniformly Diﬀerential. PC-MAC
requires that auxiliary permutations Gi has a negligible Maximum ExpectedDiﬀerential Probability (MEDP).
Deﬁnition 2.2.3.1 Let G be a keyed permutation: {0, 1}k × {0, 1}n → {0, 1}n .
Maximum expected diﬀerential probability of G, denoted as MEDPG is deﬁned
as follows:
MEDPG = max∆̸=0,∆′

ΣK∈{0,1}k Pr[G(K,M )⊕G(K,M ⊕∆)=∆′ ]2kwhere M is uniformly sampled in {0, 1}n .
27,

One can build a AUHF using a set of permutations {Gi }, which have small
MEDP, as shown in Figure 12. Loosely speaking, with the usage of mask keys, anattacker can only control the input diﬀerence of Gi , but without the knowledgeof the exact values. Since Gi has a small MEDP, the probability that an attacker
will produce a collision becomes small.

Figure 12: AUHF based on permutations with small MEDP

However, such an AUHF has a disadvantage. Numerous mask keys arenecessary if the input message is long. Thus PC-MAC proposes PCH. By setting
a parameter d, an execution of EK (·), which is assumed to be PRF, will be
involved every d + 1 message blocks. Thanks to PRF EK (·), PC-MAC canrepeadly use d auxiliary permutations {Gi }, without inﬂuencing the collisionresistance of AUHF.
As a summary, PC-MAC is proven to be PRF under two assumptions [13]:• EK (·) is a psuedo-random permutation; and• Gi (·) has a small MEDP.

PC-MAC-AES. AES is U.S. government standard and the most widely implemented block cipher, which is a plausible instantiation of EK (·). Moreover,
AES-4R has been proven to be with a MEDP comparable to full AES [17, 10, 18],
and thus is a proper instantiation of Gi (·).

28

3Comparison Between PC-MAC-AES and Other
Block-Cipher-Based MACs

This section will compare PC-MAC-AES with other CBC MAC
variants. Particularly we derive four features.
• on-the-ﬂy: shared with all CBC MAC variants.
• suﬃx: shared with EMAC and its variants.
• tweaking key: shared with XCBC and its variants.
• new features of PC-MAC-AES.

This section will make a comparison between PC-MAC-AES and other blockcipher-based MACs. More precisely, we will derive several feature of PC-MACAES, and pointed out which MACs share the same features. Such a comparison
will contribute to a fair understanding of the weakness of PC-MAC-AES, which
will be discussed in Sections 4 ∼ 8.

3.1

On-the-ﬂy

On-the-ﬂy structure is deﬁned as follows:• a message will be splited into small blocks, which will be hashed sequentially; and• each block will be hashed only once.
Almost all the block-cipher-based MACs are variants of CBC MAC [2]. They
all share this feature.

3.2

Suﬃx

Suﬃx is deﬁned as follows:• for any message M1 ||M2 , where M1 is a message of multiple-block length,
the iteration sequence of block ciphers for processing M2 will not change.
This feature is shared with EMAC [1] and its variants such as XCBC [4],TMAC [12] and OMAC [8].

29

3.3

Tweaking Key

Tweaking key is deﬁned as follows:• one secret key will be used to XOR the input of the last block cipher
operations.
XCBC MAC [4] ﬁrstly introduced the usage of tweak keys. It uses two independent tweak keys for full-last-block and non-full last block cases separately.
After that, TMAC [12] proposed a reﬁnement to XCBC: only one tweak key L
is used, and the other tweak key is computed as L • u. PC-MAC follows thesame way with TMAC to tweak the last block, except that it actually uses L • uand L • u2 .

3.4

New Features

We will list two new features of PC-MAC-AES.
• Gi is AES-4R.
• Ui and Kjxor are generated by EK (·) and L.

30

Statement.
Most attacks in Sections 4 ∼ 7 have been published to attack other MACs, whichwere proposed earlier than PC-MAC (refer to papers [19], [5],[14],[9] etc.). We
mainly try to list all the attacks which are applicable to PC-MAC-AES, anddescribe them in detail. Moreover, in order to contribute to a fair judgment on
the meaning of these attacks, we describe the security margin loss following thedevelopment history from original CBC MAC to PC-MAC.

4Type I of Attacks: Weakness of on-the-ﬂy
Structure

This section consists of• distinguishing attacks– DISPC−MAC−AES,RF• forgery attacks– existential forgery attack– selective forgery attack

Attacks of Type I are based on the weakness of on-the-ﬂy structure, which
are shared by CBC MAC and its variants, and thus applicable to these CBC
MAC variants.

4.1

DISPC-MAC-AES, RF Attacks

We will describe two attack approaches, which distinguish PC-MAC-AES from
RF.
4.1.1

Approach Using Internal Collisions

PC-MAC-AES has one property due to the on-the-ﬂy structure.
• If two diﬀerent messages M and M ′ collide on PC-MAC-AES, namely
they have the same tag value. M ||m and M ′ ||m will also collide on it,
where || means concatenation and m can be any message.

31

However, RF does not have such a property. Thus PC-MAC can be distinguished from RF when a pair of colliding messages is found. Attack procedure isdetailed below. Suppose A is given an oracle O(·) of being either PC-MAC-AES
or RF.
1. Initialize a table T as empty.
2. Select a random message M , query it to O(·), and obtain a response T .
3. Check whether T has been included in T .
• Yes: derive the corresponding message/tag pair (M ′ , T ) in T .
• No: store (M, T ) in T and repeat Steps 2 and 3.
4. Select a random message m.
5. Query M ||m to O(·), and obtain a response T1 .
6. Query M ′ ||m to O(·), and obtain a response T2 .
7. If T1 = T2 , O(·) is PC-MAC. Otherwise, O(·) is RF.
Complexity. Due to the birthday attack, Steps 2 and 3 will be repeated 264
times to generate a colliding pair with a success probability 0.33.
4.1.2

Approach Using Bijection of Permutation

If the domain of PC-MAC-AES is restricted to {0, 1}128 , it actually becomes a
permutation, and thus has no colliding message pairs. However, RF does nothave such a property. Thus PC-MAC-AES can be distinguished from RF whena pair of 128 bits long colliding messages is found. Attack procedure is detailed
as below. Suppose A is given an oracle O(·) of being either PC-MAC-AES orRF.
1. Initialize a table T as empty.
2. Initialize a counter C as 0.
3. Query C to O(·), and obtain a response T .
4. Check whether T has been included in T .
• Yes: O(·) is RF.
• No: if C ≤ 264 , C ← C + 1, and repeat Steps 3 and 4. Otherwise,O(·) is PC-MAC-AES.
Complexity. It needs 264 queries with a success probability 0.33.
Remark. Interestingly, this attack is not highly related to on-the-ﬂy structure,but can be regarded as weakness of using block ciphers.
32

4.2

Existential Forgery Attack

The distinguishing attack in Section 4.1.1 can be converted to an existential
forgery attack. After a pair of colliding messages M and M ′ is generated, A isable to forge M ||m by querying M ′ ||m to PC-MAC-AES, where m can be any
message. Attack procedure is detailed below.
1. Initialize a table T as empty.
2. Select a random message M , query it to PC-MAC-AES, and obtain a
response T .
3. Check whether T is included in T .
• Yes: derive the corresponding message/tag pair (M ′ , T ) in T .
• No: store (M, T ) in T and repeat Steps 2 and 3.
4. Select a random message m.
5. Query M ′ ||m to PC-MAC-AES, and obtain a response T1 .
6. Output a valid tag T1 for M ||m, which was not priorly queried.
Complexity. It needs 264 queries with a success probability 0.33.

4.3

Selective Forgery Attack

Without loss of generality, suppose A selects a 2 blocks long message M (=m1 ||m2 ). If a pair of colliding messages, as shown in Figure 13, are generated,
A has EK (m1 )⊕m = EK (m′ )⊕m2 , which implies EK (m1 )⊕m2 = EK (m)⊕m′ .
Thus A is able to forge m1 ||m2 by querying m||m′ to PC-MAC-AES. Attack
procedure is detailed below.

Figure 13: Selective forgery attack
1. Initialize a table T as empty.
2. Select 264 random 128 bits long messages m (m ̸= m2 ), query m1 ||m to
PC-MAC-AES, and store the message/tag pairs in T .
33

3. Select a random 128 bits long message m′ (m′ ̸= m1 ), query m′ ||m2 to
PC-MAC-AES, and obtain a response T .
4. Check whether T has been included in T .
• Yes: derive the message pair (m1 ||m, T ) from T ;• No: repeat Steps 3 and 4.
5. Query m||m′ to PC-MAC-AES, and obtain a response T1
6. Output a valid tag T1 for m1 ||m2 , which was not priorly queried.
Complexity. Steps 3 and 4 will be repeated 264 times with a success probability
0.63. The overall complexity is 265 queries.
Remark. This attack is a selective forgery attack, since A is able to select amessage M , which is longer than 128 bits, and forge a valid tag without querying
it to PC-MAC-AES. However, this attack cannot forge 128 bits long messages,
and thus it is not a universal forgery attack.

34

5

Type II of Attacks: Weakness of Suﬃx StructureThis section consists of• internal-state-recovery attack• forgery attack– low complexity-on-average universal forgery attack• full-key recovery attack

Attacks of Type II are based on the weakness of suﬃx structure, which areshared by EMAC and its variants, and thus applicable to them.

5.1

Internal-State-Recovery Attack

Without loss of generality, suppose A will recover the internal state right after
m1 of a message M (= m1 || · · · ), which is more precisely EK (m1 ). If a pair ofcolliding messages, as shown in Figure 14, is generated, A has EK (m1 )⊕m = m′ ,which implies EK (m1 ) = m⊕m′ . Thus A will know the value of EK (m1 ), whichis the internal state right after m1 . Attack procedure is detailed below.

Figure 14: Internal state recovery attack
1. Initialize a table T as empty.
2. Select 264 random 128 bits long messages m, query m1 ||m to PC-MACAES, and store the message/tag pairs in T .
3. Select a random 128 bits long message m′ , query m′ to PC-MAC-AES,
and obtain a response T .
35

4. Check whether T is included in T .
• Yes: derive the message pair (m1 ||m, T ) from T ;• No: repeat Steps 3 and 4.
5. Output m ⊕ m′ as the value of EK (m1 ).
Complexity. Steps 3 and 4 will be repeated 264 times with a success probability
0.63. The overall complexity is 265 queries.

5.2

Low Complexity-on-Average Universal Forgery Attack

Without loss of generality, suppose A is going to forge a one-block message m.
Let M (= m1 || · · · ||md+1 ) be a random (d + 1)-block message. As shown in
Figure 15, M ||(PCH(M ) ⊕ m) and m are a collision on PC-MAC-AES. Thus A
can forge a valid tag for m by querying M ||(PCH(M ) ⊕ m). Attack procedure
is detailed below.

Figure 15: Universal Forgery Attack

1. Select a random (d + 1)-block message M , and another random message
M ′.
2. Recover the internal state right after M of PC-MAC-AES(M ||M ′ ), which
is PCH(M ). Refer to Section 5.1 for the detailed procedure.
3. Query M ||(PCH(M ) ⊕ m) to PC-MAC-AES, and obtain a response T .
4. Output a valid tag T for m, which was not priorly queried.

36

Complexity. The dominant complexity is from Step 2. Thus A makes 265
queries with a success probability 0.63.
Complexity on average. After PCH(M ) is recovered, A only needs 1 query
to forge a message. Thus A is able to forge a heavy number of message with only
a negligible increasement of complexity, which will make the average complexity
low.

5.3

Key Recovery Attack

PC-MAC-AES has two 128-bit keys K and L. Thus a trivial attack will need
2256 computations to recover both K and L. However, it only needs around 2128
computations to recover them. There are two attacks based on the weakness ofthe suﬃx iteration.
Remark. Besides suﬃx, these two attacks seem to also take advantage that
EMAC and its variants only use the second secret key to remodel the last block
operation of original CBC MAC.
5.3.1

Approach Using Internal Collisions

When a pair of colliding messages m1 ||m2 and m′1 ||m′2 , which are 2 blocks
long, is generated, A has EK (m1 ) ⊕ m2 = EK (m′1 ) ⊕ m′2 . Thus A is able toexhaustively recover K without the knowledge of L. After K is recovered, A
will further exhaustively recover L using 1 message/tag pair. Attack procedure
is detailed below.
1. Generate a pair of 2-block long colliding messages m1 ||m2 and m′1 ||m′2 on
PC-MAC-AES. Refer to Section 4.1.1 for the detailed procedure.
2. Set a counter C as 0128 .
3. Check whether AESC (m1 ) ⊕ m2 = AESC (m′1 ) ⊕ m′2 holds.
• Yes: K = C.
• No: C ← C + 1. Repeat Step 3.
4. Query a one-block message m to PC-MAC-AES, and obtain a response T .
5. Set C as 0128 .
6. Compute PC-MAC-AES(m) using recovered K and C as L, and check
whether it will be equal to T .
• Yes: L = C.
• No: C ← C + 1. Repeat Step 6.

37

7. Output K and L.
Complexity. Step 1 needs 265 queries with a success probability 0.63. Step 3
will be repeated 2128 times in the worst case. Similarly Step 6 will be repeated2128 times in the worst case. Finally the overall complexity is 265 online queries
and 2129 oﬄine computations.
5.3.2

Approach Using Internal-State-Recovery Attacks

When the internal state right after m1 of 2 blocks long message m1 ||m2 isrecovered, A is able to exhaustively recover K, and then exhaustively recover
L. Attack procedure is detailed below.
1. Select a random 2 blocks long message m1 ||m2 , and recover the value ofEK (m1 ). The procedure is detailed in Section 5.1.
2. Set C as 0128 .
3. Check whether EC (m1 ) = EK (m1 ).
• Yes: K = c• No: C → C + 1 and repeat Step 3.
4. Exhaustively recover L. Refer to the attack procedure (Steps 5 and 6) inSection 5.3.1.
5. Output K and L.
Complexity. Step 1 needs 265 online queries. Step 3 will be repeated 2128
times. Refer to Section 5.3.1, it needs 2128 computations to recover L. Overall,it needs 265 queries and 2129 computations.

38

6Type III of Attacks: Weakness of Tweaking
Keys

This section consists of• partial-key-recovery attack• forgery attacks– (new) universal forgery attack• low complexity-on-average internal-state-recovery attack• (better) full-key recovery attack

Attacks of Type III are based on the weakness of using a secret key to tweak
the last block, which are shared by TMAC and its variants, and thus applicableto them.

6.1

Partial-Key-Recovery Attack

When a pair of colliding messages, as shown in Figure 16, is generated, A hasm ⊕ mul2(L) = (m′ ||10 · · · 0) ⊕ mul2(mul2(L)), where m is 128 bits long, but
m′ is short of 128 bits long. Denote mul2(L) by X, and then X ⊕ mul2(X) =m ⊕ (m′ ||10 · · · 0) holds. A will get X = (m ⊕ (m′ ||10 · · · 0) • (u + 1)−1 , andfurther L = (m ⊕ (m′ ||1 · · · 0)) • (u + 1)−2 . The attack procedure is detailed
below.

Figure 16: Partial-key Recovery Attack
1. Initialize a table T as empty.
2. Select 264 random 128-bit messages, query them to PC-MAC-AES, andstore the message/tag pairs in T .
39

3. Select a random message m′ , which is short of 128 bits, query it to PCMAC-AES, and obtain a response T .
4. Check whether T has been included in T .
• Yes: derive the message/tag (m, T ) in T .
• No: repeat Steps 3 and 4.
5. Output L = (m ⊕ (m′ ||1 · · · 0)) • (u + 1)−2 .
Complexity. Steps 3 and 4 will be repeated 264 times with a success probability
0.63. Th overall complexity is 265 queries with a success probability 0.63.

6.2

Universal Forgery Attack

After A has the knowledge of L, universal forgery attack becomes trivial. Without loss of generality, suppose A will forge a non-full one block long message
m′ , more precisely short of 128 bits. As shown in Figure 17, m ⊕ ∆ and m′ is apair of colliding messages on PC-MAC-AES. Thus A can forge m′ by queryingm ⊕ ∆ to PC-MAC-AES. Attack procedure is detailed below.

∆ means mul2(L) ⊕ mul2(mul2(L)), and m = m′ ||10 · · · 0.
Figure 17: Universal Forgery Attack

1. Recover L. The procedure is detailed in Section 6.1.
2. Compute ∆ as mul2(L) ⊕ mul2(mul2(L)).
3. Query m ⊕ ∆ to PC-MAC-AES, and obtain a response T .
4. Output T as a valid tag for m′ , which was not priorly queried.
Complexity. The dominant complexity is from Step 1. The complexity is 265
queries with a success probability 0.63.

40

6.3

Low Complexity-on-Average Internal-State-Recovery
AttackAfter L is recovered, A can obtain internal state of a message trivially. Without
loss of generality, suppose A will recover the internal state after m1 for a 2
blocks long message m1 ||m2 . As shown in Figure 18, A can query m1 ⊕ mul2(L)to PC-MAC-AES, which is actually EK (m1 ). Thus A has recovered the internal
state after m1 for m1 ||m2 . Attack procedure is detailed below.

Figure 18: Internal State Recovery Attack

1. Recover L. The procedure is detailed in Section 6.1.
2. Query m1 ⊕ mul2(L), and obtain a response T .
3. Output T as the internal state EK (m1 ).
Complexity. The dominant complexity is from Step 1. The overall complexity
is 265 queries with a success probability 0.63.
Complexity on average. After L is recovered, A only needs 1 query to obtainan internal-state value of a message. Thus A is able to recover internal-statevalues of a heavy number of messages with only a negligible increasement ofcomplexity, which makes the average complexity low.

6.4

Full Key Recovery Attack

L can be trivially computed after K is recovered. Thus there is better time/memory
tradeoﬀ compared with full-key-recovery attack of Type I.
6.4.1

Approach of Saving Memory

Guessing the value of K, A can compute the corresponding value of L by using one message/tag pair, and verify the correctness of guess by using anothermessage/tag pair. By exhaustively guessing K, A will recover both K and
L. Throughout the attack, A only needs to memorize two message/tag pairs.
Attack procedure is detailed below.
41

1. Select two random 128 bits long messages m and m′ , query them to PCMAC-AES, and obtain responses T and T ′ respectively.
2. Set a counter C as 0128 .
−1
3. Compute (EC(T ) ⊕ m) • u−1 .
−1
4. Check whether T ′ = EC (m′ ⊕ (EC(T ) ⊕ m)) holds.
−1• Yes. K = C, and L = (EC(T ) ⊕ m) • u−1 .

• No. C ← C + 1, and repeat Steps 3 and 4.
5. Output K and L.
Complexity. Steps 3 and 4 will be repeated 2128 times in the worst case, andeach times needs 2 computations. Overall, the complexity is 2129 . Interestingly,
A only needs to memorize 2 message/tag pairs.
6.4.2

Approach of Saving Time

A will follow the procedures in Section 5.3 to recover K ﬁrst, and then computethe value of L trivially. Attack procedure is detailed below.
1. Recover K using internal-state-recovery attacks. Refer to Section 5.3.2 fordetailed procedure.
−1
2. Compute L as (EK(T ) ⊕ m) • u−1 , where (m, T ) is a message/tag pair of
PC-MAC-AES.

3. Output K and L.
Complexity. The complexity is reduced to 2128 . A has to memorize 265
message/tag pairs.

42

7

Attack of Type IV: Weakness of Subkey Generation Algorithm

This section consists of• Subkey-recovery attack• DIS-PC-MACAES, RP attack

Attacks of Type IV will discuss the weakness introduced by new feature of
PC-MAC-AES.

7.1

Subkey-Recovery Attack

After L is recovered, A can recover {Ui } and {Kixor } trivially. Here pick U1
as an example. U1 (= U11 ||U12 ||U13 ) is generated as follows: U11 = EK (L);U12 = EK (L ⊕ [1]), and U13 = EK (L ⊕ [2]) respectively. A can query a one-block
message L ⊕ mul2(L) to PC-MAC-AES, which is shown in Figure 19, to obtainthe value of U11 . Similarly A will recover U12 and U13 . Thus U1 is recovered.
Attack procedure is detailed below.

Figure 19: Recover U11
1. Recover L. The procedure is detailed in Section 6.1.
2. Set i as 1.
3. Recover Ui as follows.
(a) Query L ⊕ [3 ∗ (i − 1)] ⊕ mul2(L) to PC-MAC-AES, and obtain a
response as Ui1 .
43

(b) Query L ⊕ [3 ∗ (i − 1) + 1] ⊕ mul2(L) to PC-MAC-AES, and obtaina response as Ui2 .
(c) Query L ⊕ [3 ∗ (i − 1) + 2] ⊕ mul2(L) to PC-MAC-AES, and obtaina response as Ui3 .
4. Set i ← i + 1. If i ≤ d, repeat Steps 3 and 4.
5. Set j as 1.
6. Query L⊕ [3 ∗ (d − 1)+j] ⊕ mul2(L) to PC-MAC-AES to obtain a response
as Kjxor .
7. Set j ← j + 1. If j ≤ d − 1, repeat Steps 6 and 7.
8. Output {Ui } and {Kixor }.
Complexity. The dominant complexity is from recovering L. The overall
complexity is 265 queries.

7.2

DIS-PC-MACAES, RP Attacks

A is able to trivially distinguish PC-MAC-AES from PC-MAC-RP after recovering L, {Ui } and {Kixor }. Since A knows the value of L, she will be able torecover internal state EK (m) for a 2 blocks long message m||m′ easily. With
the knowledge of {U1 } and {Kixor }, A is able to generate a colliding message
pair on PC-MAC-AES. However, PC-MAC-RP does not have such a property.
Thus A will be able to distinguish PC-MAC-AES from PC-MAC-RP. Attack
procedure is detailed below. Denote the given oracle as O(·), which is either
being PC-MAC-AES or PC-MAC-RP.
1. Suppose O(·) is PC-MAC-AES. Recover L, {Ui } and {Kixor }. Procedure
is detailed in Sections 6.1 and 7.1.
2. Select a random 128 bits message m1 , query m1 ⊕ L to O(·), and obtaina response t.
3. Select a random 128-bit message m2 , and compute y = G1 (m2 ⊕ t).
4. Select another random 128-bit message m′2 (m′2 ̸= m2 ), and computey ′ = G1 (m′2 ⊕ tT ).
5. Select a random 128-bit message m3 , and compute m′3 = m3 ⊕ y ⊕ y ′ .
6. Query m1 ||m2 ||m3 and m1 ||m′2 ||m′3 to O(·), and obtain responses T and
T ′.
7. Check where T = T ′ holds.
• Yes: O(·) is PC-MAC-AES.
44

• No: O(·) is PC-MAC-RP.
Complexity. The dominant complexity is from recovering L. Thus the overall
complexity is 265 queries.

45

8

Attacks of Type V: Weakness of AES-4R

This section consists of• a subkey-recovery attack on a CBC MAC variant using AES-4R• an internal-state-recovery attack

Attacks of Type V is to deal with an interesting question:Will using AES-4R weaken the security of a CBC MAC variant from any
sense?
Our answer is yes. We will propose a subkey recovery attack on a CBC MAC
variant using AES-4R. AES-4R is detailed in Figure 20. More precisely we will
recover the subkeys K2 , K3 and K4 .

Figure 20: AES-4R

8.1

Minimum Available Information

All CBC MACs share a common character on-the-ﬂy structure. Suppose a CBC
MAC will use AES-4R to process i-th block of input messages, which is shownin Figure 21.

46

Figure 21: AES-4R to process i-th block

We will show how to obtain the output diﬀerence of AES-4R for a chosen
input diﬀerence with a complexity of 265 queries. The main idea is to generatea pair of colliding messages, which only diﬀers at i-th and (i + 1)-th blocks, anddiﬀerence of i-th block is equal to the chosen input diﬀerence of AES-4R. We
can get that the corresponding output diﬀerence of AES-4R should be equal tothe diﬀerence of (i+1)-th blocks. Attack procedure is detailed belwow. Suppose
the chosen input diﬀerence of AES-4R is ∆.
1. Initialize a table T as empty.
2. Select i random blocks m1 , . . ., mi .
3. Compute m′i = mi ⊕ ∆.
4. Select 264 random block m, and query m1 ||m2 || · · · ||mi−1 ||mi ||m to MAC,
and obtain corresponding tags. Store the message/tag pairs in T .
5. Select a random block m′ , and query m1 ||m2 || · · · ||mi−1 ||m′i ||m′ to MAC,
and obtain a corresponding tag T .
6. Check whether T has been included in T .
• Yes: derive the message/tag pair (m1 ||m2 || · · · ||mi−1 ||mi ||m, T ) fromT.
• No: repeat Steps 5 and 6.
7. Output m ⊕ m′ as the corresponding output diﬀerence of AES-4R.
Complexity. Steps 5 and 6 will be repeated 264 times with a success probability
0.63. The overall complexity is 265 queries with a success probability 0.63.

8.2

Subkey-Recovery Attacks

With the knowledge of output diﬀerence for a chosen input diﬀerence on AES4R, we will show how to recover subkeys.
47

8.2.1

Useful Properties of AES

We will list several properties of AES which will be used in our attacks.
Property 1. The branch number of MC is 5.
Property 2. Any 4 byte diﬀerences of input and output of MC will uniquelydetermine the remaining 4 byte diﬀerences.
Property 3. The following 2 round diﬀerential path in Figure 22 is with a probability 1, where byte in white color has no diﬀerence and byte in grey color has
a non-zero diﬀerence.

Figure 22: 2-Round Diﬀerential Path with a Probability 1

Hereafter, we will refer non-active byte to as byte with a zero diﬀerence, andactive byte to as byte with a non-zero diﬀerence.
Property 4. For the 2-round diﬀerential path in Figure 22, the output byte
diﬀerences after 2nd MC essentially only depend on bytes 0, 5, 10 and 15 of thepair inputs.
Proof. Let (x1 , x′1 ) and (x2 , x′2 ) be two pairs of inputs satisfying• each pair diﬀers at byte 0;• the diﬀerences at byte 0 are equal for the two pairs;• bytes 0, 5, 10 and 15 are equal for x1 and x2 .
From the above conditions, we can trivially get that bytes 0, 7, 10 and 13 ofinternal state after 2nd SR are still equal for x1 and x2 . The same situation
happens for x2 and x′2 . Thus we get that the byte diﬀerences after 2nd SR are
equal for the two pairs. Due to linearity of MC transformation, the byte diﬀerences after 2nd MC will also be equal for the two pairs. Therefore Property 4
has been proven.
Property 5. for a pair of input diﬀerence ∆i and output diﬀerence ∆o , 2 corresponding values X satisfying SB(X)⊕ SB(X ⊕ ∆i ) = ∆o can be derived with aprobability of nearly 0.5 by looking up the diﬀerential distribution table of S-box.

48

8.2.2

How to Recover K4

Our attack is based on a 4-round diﬀerential path in Figure 23, which has aprobability 1 following Property 3. The main novelty of our attack is as follows.

Figure 23: 4-Round Diﬀerential Path Used in Our Attacks
Let (m1 , m′1 ), (m2 , m′2 ) and (m3 , m′3 ) be three pairs satisfying the following
three conditions.
• each pair diﬀers at byte 0; Thus the diﬀerential propagation for each pairfollowing the path in Figure 23.
• the diﬀerence at byte 0 are equal for the three pairs;• the values of bytes 0, 5, 10 and 15 are equal for m1 , m2 and m3 .
From Property 4, these pairs share the same byte diﬀerences at State S8 .
We extend (m1 , m′1 ), (m2 , m′2 ) and (m3 , m′3 ) to ﬁve pairs {(m1 , m′1 ), (m2 , m′2 ),(m3 , m′3 ), (m1 , m2 ), (m1 , m3 )}, and obtain the byte diﬀerence at State S16 foreach pair.
Then we will compute the byte diﬀerence at State S14 for these ﬁve pairs
due to the linearity of SR−1 ◦ M C −1 (·).
Finally we will recover State S14 and k4 column by column. Following thedotted computation in Figure 23, by guess one column of S14 and K4 , we will
be able to compute diﬀerences of byte 0, 5, 10 and 15 of State S9 for three pairs(m1 , m′1 ), (m2 , m′2 ) and (m3 , m′3 ), which should be equal. For a false guess, theprobability of satisfying the property is 2−64 . In total, there are 264 freedom.

49

Therefore only the correct value will be left. Similarly we can recover the othercolumns. Thus K4 will be recovered.
Moreover, we use two ideas to reduce the complexity.
Idea I. We do not need to guess a column of K4 . First we will compute thebyte diﬀerence of a diagonal at State S10 by guessing one column of S14 .
Then we determine the value of each byte independently. Finally we cancompute the value of the column of K4 . In such a manner, the complexity
becomes 240 from 264 .
Idea II. After one column is recovered, actually the byte diﬀerence at State 9
has been uniquely determined. Thus it will be much easier to recover thefollowing three columns.
8.2.3

Detailed Procedure of Recovering K4

Notations. (m1 , m′1 ), (m2 , m′2 ) and (m3 , m′3 ) are three pairs following thediﬀerential path in Figure 23. Moreover, m1 , m2 and m3 share the same values
1,of bytes 0, 5, 10, and 15. Denote States of m1 , m′1 , m2 , m′2 , m3 and m′3 as S1∼16
3′
3
2′
2
1′
S1∼16 , S1∼16 , S1∼16 , S1∼16 and S1∼16 respectively. Denote Byte j of State Sit ast. Denote State diﬀerence of pairs (m1 , m′1 ), (m2 , m′2 ), (m3 , m′3 ), (m1 , m2 ),
Si,j
1,3
1,2
3,3
2,2
1,1
respectively. Denoteand ∆S1∼16, ∆S1∼16, ∆S1∼16, ∆S1∼16(m1 , m3 ) as ∆S1∼16
t1 ,t2
t1 ,t2
diﬀerence of byte j in ∆Si
as ∆Si,j .
Attack Procedure.
1. Select three message pairs (m1 , m′1 ), (m2 , m′2 ) and (m3 , m′3 ) satisfying theconditions detailed in Section 8.2.2.
1,1
2,2
3,3
1,2
1,3
2. Obtain ∆S16
, ∆S16, ∆S16, ∆S16and ∆S16. The procedure is detailedin Section 8.1.
1,1
2,2
3,3
1,2
1,3
3. Inversely compute ∆S14
, ∆S14, ∆S14, ∆S14and ∆S14
.
1
1
1
1
.
, S14,4, S14,8and S14,12
4. Guess the values of bytes S14,01
1
11, S13,8and S13,12.
, S13,4
5. Compute the values of bytes S13,0
′

′

′

′

1,1
1
1
1
1
6. Compute the values of bytes S14,0, S14,4, S14,8and S14,12
since ∆S14
isknown.
′

′

′

′

1
1
1
1
7. Compute the values of bytes S13,0, S13,4, S13,8and S13,12
.
1,1
1,1
1,1
1,1
8. Compute ∆S13,0, ∆S13,4, ∆S13,8
and ∆S13,12
.
1,1
1,1
1,1
1,1
9. Compute ∆S10,0, ∆S10,5, ∆S10,10
and ∆S10,15
due to the linearity of SR,
MC and ARK.
1,2
2
2
2
2
10. Compute the values of bytes S14,0, S14,4, S14,8and S14,12
since ∆S14
isknown.

50

′

′

′

′

2,2
2
2
2
2
11. Compute the values of bytes S14,0, S14,4, S14,8and S14,12
since ∆S14
isknown.
2,2
2,2
2,2
2,2
, similarly with Steps 5 ∼ 9.
and ∆S10,15
12. Compute ∆S10,0, ∆S10,5, ∆S10,10
1,2
1,2
1,2
1,2
, ∆S10,10
and ∆S10,15.
, ∆S10,5
13. Compute ∆S10,0
1,3
3
3
3
3
14. Compute the values of bytes S14,0, S14,4, S14,8and S14,12
since ∆S14
isknown.
′

′

′

′

3,3
3
3
3
3
15. Compute the values of bytes S14,0, S14,4, S14,8and S14,12
since ∆S14
isknown.
3,3
3,3
3,3
3,3
16. Compute ∆S10,0, ∆S10,5, ∆S10,10
and ∆S10,15
.
1,3
1,3
1,3
1,3
17. Compute ∆S10,0, ∆S10,5, ∆S10,10
and ∆S10,15.
1
18. Guess the value of byte S10,0
.
′

′

′

3
3
2
2
1
.
and S10,0, S10,0, S10,0, S10,019. Compute the values of bytes S10,0
′

′

′

3
2
3
1
2
1
and S9,0.
, S9,0, S9,0, S9,0, S9,020. Compute the values of bytes S9,0
1,1
2,2
3,3
21. Check whether ∆S9,0= ∆S9,0= ∆S9,0holds.
1
at Step 18 is correct.
• Yes: the guess of S10,01
at Step 18 is wrong.
• No: the guess of S10,0
1
has been tried, the guess of theIf every candidate value of S10,0
1
is wrong. Guess next candidate value at Step 4 andcolumn of S14
repeat Steps 4 ∼ 21.
Otherwise, guess next candidate value at Step 18, and repeat Steps
19 ∼ 21.
1
11
similarly with Step
and S10,15, S10,10
22. Recover the values of bytes S10,5
1
1
1, S14,8
and, S14,418 ∼ 21, which also determines the values of bytes S14,01
S14,12 .

23. Recover bytes 0, 4, 8 and 12 of K4 .
1
1
1
1
, S9,10and S9,15.
, S9,524. Compute the values of bytes S9,0′

25. Compute the values of these bytes of S91 .
1,1
1,1
1,1
1,1
1,1
26. Compute the values of ∆S9,0, ∆S9,5, ∆S9,10and ∆S9,15. Then ∆S8,0
,
1,1
1,1
1,1
∆S8,5 , ∆S8,10 and ∆S8,15 are known.

5127. Determine the values of ∆S81,1 (=∆S91,1 ).
MCThis is because of Property 2. For the diﬀerence propagation ∆S71,1 −−−→
1,1
S8 in Figure 23, 4 byte diﬀerences of each column has been determined,
and thus the remaining four byte diﬀerence can be computed. For exam1,1
1,1
1,1
1,1
ple, for the ﬁrst column, ∆S7,4, ∆S7,8, ∆S7,12and ∆S8,0
are determined.
1
28. Recover the values of the remaining bytes of S14
and K4 similarly with
Steps 4 ∼ 23.

Note that the values of ∆S91,1 has been determined at Step 27. Thus when1
recover the other bytes of S10, there is no need to carry out guess-the-verify
approach (Steps 18 ∼ 21). Instead, it will be recovered by looking up thediﬀerential distribution table of S-box. This will save time complexity.
1
29. Output the values of K4 and S14.

Complexity. At Step 2, less than 267 queries is necessary. The memory requirement is less than 266 . At Steps 4 ∼ 23, the time complexity is around240 . At Steps 28, the time complexity is around 232 . Overall, the complexity ofrecovering K4 is 267 online queries and 240 oﬄine computations. The memory
requirement is 266 .
Remark. This attack is also an internal-state-recovery attack.
8.2.4

How to Recover K3

After K4 is recovered, we will recover K3 using two diﬀerential paths in Figures 24 and 25. The main novelty of our attacks is as follows.

Figure 24: First Diﬀerential path for recovering K3

52

Figure 25: Second Diﬀerential path for recovering K3

Let m be a message used for recovering K4 . We know that during recovering
K4 , the internal states S9∼16 of m are also recovered. Select two pairs (m, m′ )and (m, m′′ ) satisfying the input diﬀerences of diﬀerential paths in Figures 24
and 25 respectively. For the pair (m, m′ ), ﬁrst recover the output diﬀerence
following the procedure in Section 8.1, which also determine the diﬀerence atState S6 . Then guess the value of bytes S1,0 , S1,4 , S1,8 and S1,12 of m, which
will determine the diﬀerence at State S5 . By checking the input and output
SB
diﬀerences of S-box during S5 −−→ S6 , 216 candidate values for S5 and S6 ofm will be left with a probability 2−16 . In total, by exhaustively guessing bytes
S1,0 , S1,4 , S1,8 and S1,12 of m, 232 candidate values for S5 and S6 of m will be
left. Each candidate value will contribute to a candidate value of K3 . Finally
we carry out similar procedure for the other pair (m, m′′ ), and obtain another
232 candidate values of K3 . The colliding value will be the correct value of K3 .
Moreover, we have also recovered the values of S1,0 , S1,1 , S1,4 , S1,5 , S1,8 , S1,9 ,S1,12 and S1,13 of m.
Comlexity. It needs 266 online queries, and 232 computations. The memory
requirement is 264 .
8.2.5

How to Recover K2

After K3 and K4 are recovered, we will recover K2 using the diﬀerential pathin Figure 26. The main novelty is as follows.

53

Figure 26: Diﬀerential path for recovering K2

Let m be a message used for recovering K4 or K3 . The internal state S5∼16
for m has been recovered. Moreover, bytes S1,0 , S1,1 , S1,4 , S1,5 , S1,8 , S1,9 , S1,12
and S1,13 for m have been recovered. Select two message pairs (m, m′ ) and(m, m′′ ) satisfying the input diﬀerence of the diﬀerential path in Figure 26. For
the pair (m, m′ ), ﬁrst recover the output diﬀerence following the procedure in
Section 8.1, which also determine the diﬀerence at State S2 . By checking theSBinput and output diﬀerences of S-box during S1 −−→ S2 , 28 candidate values
for S1 and S2 of m will be left, and each candidate value will contribute to a
candidate value of K2 . Finally we carry out similar procedure for the other pair(m, m′′ ), and obtain another 28 candidate values of K2 . The colliding value willbe the correct value of K2 .
Complexity. It needs 266 online queries and negligible oﬄine computations.
The memory requirement is 264 .

8.3Internal-State Recovery Attack

Refer to Remark in Section 8.2.3.

54

9

Conclusion

This section consists of• summarization of our contributions.
• words for CRYPTOREC Committee.

This report has evaluated the security of PC-MAC-AES and its underlying
component AES-4R.

9.1

Our Contributions

The high-level overview of our contributions is as follows.
First of all, we listed all the attacks applicable to PC-MAC-AES. Strictly speaking, so far only two papers were published explicitly on the evaluation of PCMAC-AES to our best knowledge. One is published by Yuan et al. in CRYPTO
2009 [20], which proposed internal-state-recovery and full-key-recovery attacks.
The other one is published by Jia et al. in CANS 2009 [9], which proposed aforgery attack. However, PC-MAC shares similar structure with other MACs
such as EMAC and TMAC. Therefore previous published attacks on other
MACs may be also applicable to PC-MAC-AES.
• The designers have mentioned such event in their submission
report [15]. However, they did not state which previous attacks
can be adapted to attack PC-MAC-AES and how much the complexity will be.
We summarized and formalized several attacks including distinguishing, forgery
partial-key-recovery and full-key-recovery attacks on PC-MAC-AES. Interestingly, our full-key-recovery attacks on PC-MAC-AES are more eﬃcient than
Yuan et al.’s attack [20].
Moreover, we successfully ﬁnd several attacks based on the weakness of newfeature of PC-MAC-AES, which reveals the security margin loss of PC-MACAES compared with previous proposed MACs. The details are given below.
1. Subkey-recovery attacks.
xor
Subkeys {U1 , U2 , . . . , Ud , K1xor , . . . , Kd−1
} are generated by using L and
EK (·). We showed that after obtaining the knowledge of L, these subkeys
can be easily recovered. The complexity is just one chosen query for eachsubkey.

55

2. Distinguish PC-MAC-AES from PC-MAC-RP.
We will ﬁrstly propose an attack procedure, which can distinguish PCMAC-AES from another PC-MAC instantiation with a Random Permutation (RP).

Secondly, we discuss about an interesting question:
what potential weakness will the usage of 4-round AES introduce toCBC-MACs including PC-MAC-AES and its variants?
As we can see, the most attractive design point of PC-MAC-AES is using
4-round AES permutations instead of the full-round AES to process partial message blocks, which will improve the eﬃciency, but still keep provable security.
The theoretical foundation of such replacement is that 4-round AES with independent round keys have similar diﬀerential property with full-round AES.
Besides PC-MAC-AES, several other MACs such as Pelican-MAC are also using
4-round AES to improve the eﬃciency. On the other hand, a question will arise:
will such replace weaken the security of CBC-MACs from any sense?
Our answer is yes. We proposed an attack on generic CBC-MAC variants
based on 4-round AES with independent round keys. More precisely, we areable to recover the round keys and the internal state value with a complexity of
267 online queries and 240 oﬄine computations.
Interestingly, our results imply an upper bound of subkey-recovery resistancefor CBC-MACs based on 4-round AES.

9.2

For CRYPTOREC Committee

We made a comparison between CMAC [16], which was recommended by NIST
for block-cipher-based authentication in 2005, and PC-MAC-AES.
• From the view of security.
From our subkey-recovery and DIS-PC-MACEK (·),RP . attacks, PC-MACAES has a weaker security margin than CMAC.
• From the view of eﬃciency.
PC-MAC-AES is about 1.5 ∼ 2.5 times faster than CMAC.

56

References[1] Integrity Primitives for Secure Information Systems, Final Report of RACE
Integrity Primitives Evaluation RIPE-RACE 1040, volume 1007 of Lecture
Notes in Computer Science. Springer, 1995.
[2] ISO/IEC 9797-1. Information technology – security techniques – message
authentication codes (macs) – part 1: Mechanisms using a block cipher.
Technical report, International Organization for Standards.
[3] American Bankers Association. Ansi x9.19, ﬁnancial institution retail message authentication. 1986.
[4] John Black and Phillip Rogaway. Cbc macs for arbitrary-length messages:
The three-key constructions. In Mihir Bellare, editor, CRYPTO, volume1880 of Lecture Notes in Computer Science, pages 197–215. Springer, 2000.
[5] Karl Brincat and Chris J. Mitchell. New cbc-mac forgery attacks. In Vijay
Varadharajan and Yi Mu, editors, ACISP, volume 2119 of Lecture Notes
in Computer Science, pages 3–14. Springer, 2001.
[6] Joan Daemen and Vincent Rijmen. The pelican mac function. Cryptology
ePrint Archive, Report 2005/088. http://eprint.iacr.org/.
[7] Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES - The
Advanced Encryption Standard. Springer, 2002.
[8] Tetsu Iwata and Kaoru Kurosawa. Omac: One-key cbc mac. In Thomas
Johansson, editor, FSE, volume 2887 of Lecture Notes in Computer Science,
pages 129–153. Springer, 2003.
[9] Keting Jia, Xiaoyun Wang, Zheng Yuan, and Guangwu Xu. Distinguishingand second-preimage attacks on cbc-like macs. In Juan A. Garay, Atsuko
Miyaji, and Akira Otsuka, editors, CANS, volume 5888 of Lecture Notes in
Computer Science, pages 349–361. Springer, 2009.
[10] Liam Keliher and Jiayuan Sui. Exact maximum expected diﬀerential andlinear cryptanalysis for two-round advanced encryption standard. Cryptology ePrint Archive, Report 2005/321, 2005. http://eprint.iacr.org/
2005/321.
[11] Lars R. Knudsen and Bart Preneel. Macdes: A mac based on des. In
Electronics Letter, volume 34, pages 871–873, 1998.
[12] Kaoru Kurosawa and Tetsu Iwata. Tmac: Two-key cbc mac. In Marc Joye,
editor, CT-RSA, volume 2612 of Lecture Notes in Computer Science, pages
33–49. Springer, 2003.

57

[13] Kazuhiko Minematsu and Yukiyasu Tsunoo. Provably secure macs from
diﬀerentially-uniform permutations and aes-based implementations. In
Matthew J. B. Robshaw, editor, FSE, volume 4047 of Lecture Notes in
Computer Science, pages 226–241. Springer, 2006.
[14] Chris J. Mitchell. Partial key recovery attacks on xcbc, tmac and omac. In
Nigel P. Smart, editor, IMA Int. Conf., volume 3796 of Lecture Notes in
Computer Science, pages 155–167. Springer, 2005.
[15] NEC. メッセージ認証コード pc-mac-aes.
[16] NIST. Recommendation for block cipher modes of operation: The
cmac mode for authentication. http://csrc.nist.gov/publications/
nistpubs/800-38B/SP_800-38B.pdf.
[17] Sangwoo Park, Soo Hak Sung, Seongtaek Chee, E-Joong Yoon, and Jongin
Lim. On the security of rijndael-like structures against diﬀerential andlinear cryptanalysis. In Yuliang Zheng, editor, ASIACRYPT, volume 2501
of Lecture Notes in Computer Science, pages 176–191. Springer, 2002.
[18] Sangwoo Park, Soo Hak Sung, Sangjin Lee, and Jongin Lim. Improving
the upper bound on the maximum diﬀerential and the maximum linear
hull probability for spn structures and aes. In Thomas Johansson, editor,
FSE, volume 2887 of Lecture Notes in Computer Science, pages 247–260.
Springer, 2003.
[19] Bart Preneel and Paul C. van Oorschot. Mdx-mac and building fast macsfrom hash functions. In Don Coppersmith, editor, CRYPTO, volume 963
of Lecture Notes in Computer Science, pages 1–14. Springer, 1995.
[20] Zheng Yuan, Wei Wang, Keting Jia, Guangwu Xu, and Xiaoyun Wang.
New birthday attacks on some macs based on block ciphers. In Shai Halevi,
editor, CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages
209–230. Springer, 2009.

58