3fk93kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
Liting Zhang2 , Wenling Wu1 , Han Sui2 , and Peng Wang2
Institute of Software, Chinese Academy of Sciences State Key Laboratory of Information Security Institute of Information Engineering, Chinese Academy of Sciences {zhangliting,wwl,suihan}@is.iscas.ac.cn, wp@is.ac.cn
1
2
Abstract. Among various cryptographic schemes, CBC-based MACs belong to the few ones most widely used in practice. Such MACs iterate a blockcipher EK in the so called Cipher-Block-Chaining way, i.e. Ci = EK (Mi ⊕ Ci−1 ) , offering high efficiency in practical applications. In the paper, we propose a new deterministic variant of CBC-based MACs that is provably secure beyond the birthday bound. The new MAC 3kf9 is obtained by combining f 9 (3GPP-MAC) and EMAC sharing the same internal structure, and so it is almost as efficient as the original CBC 3 3 q lq MAC. 3kf9 offers O( l22n + 2n ) PRF-security when its underlying n-bit blockcipher is pseudorandom with three independent keys. This makes it more secure than traditional CBC-based MACs, especially when they are applied with lightweight blockciphers. Therefore, 3kf9 is expected to be a possible candidate MAC in resource-restricted environments. Keywords: MAC, Birthday Bound, CBC, Mode of Operation.
1
1.1
Introduction
Background
Birthday Bound. In cryptography, birthday attack is a generic attack that exploits no specific properties within cryptographic schemes, but just takes the advantage of birthday paradox in probability theory. This paradox says, approximately 2n/2 independently random n-bit points will collide with a probability close-to-1, where 2n/2 is called the birthday bound [28,20]. The birthday attack itself is not fatal to the practical security of cryptographic schemes, because people can choose long-enough security parameters to defend, e.g. by restricting the output length of hash functions to be no shorter than 224 bits [3], or by preventing attackers from getting sufficient number of input-output pairs, to make this attack infeasible in recent years. However, being constrained by some particular software/hardware environments, there still exist many actual applications using short security parameters. For example, the 64-bit blockcipher KASUMI is currently a standard algorithm in mobile communication systems [7]. With the rapid developments of Internet
X. Wang and K. Sako (Eds.): ASIACRYPT 2012, LNCS 7658, pp. 296–312, 2012. c International Association for Cryptologic Research 2012
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
297
of Things, several lightweight primitives have been proposed in recent years, e.g. present and PHOTON [11,14]. These algorithms take small-size internal states and output values, usually are much easier to be realized in software and require smaller area in hardware, offering better performance than normal-size ones. Unfortunately, their small sizes imply vulnerability when they are used with traditional modes of operation, most of which are only secure within the birthday bound [19,2]. To ensure practical security in such cases, those modes have to be combined with stateful or random values, or to limit the lengths of their input messages, or to update secret keys frequently, resulting in inconveniences and security risks if misused. MAC. Message Authentication Code is a widely-used cryptographic scheme for data integrity protection and data origin authentication. Practical applications usually require them to be not only secure (outputting unpredictable tags for new messages) but also efficient. A common way to design a MAC algorithm is to iterate a blockcipher E : KE ×{0, 1}n → {0, 1}n in the Cipher-Block-Chaining (CBC) manner. That is, in each step, a new chaining value Ci is obtained by encrypting the XOR result of the current message block Mi and the previous chaining value Ci−1 , i.e. Ci = EK (Mi ⊕ Ci−1 ). The CBC structure is so common in the design of many cryptographic schemes that it has been considerably studied for many years [8,27,9,16,24]. Up to now, many excellent CBC-based MACs have been proposed, e.g. EMAC, XCBC, OMAC, CMAC and GCBC [27,9,16,4,24]. Besides, PMAC takes a fully parallelizable construction and can offer extremely high speed in parallel environments [10]. All of the above MAC algorithms are deterministic (needing no stateful or random values), and provably secure when their underlying blockcipher is assumed to be a pseudorandom permutation (PRP). However, their security bounds all fall within the birthday bound, and can not be further improved because there exist birthday attacks on them, i.e. the birthday bound is tight for them [19,2]. There are also a few CBC-based MACs with provable security beyond the birthday bound. For example, RMAC replaces the second key in EMAC by XORing its first key and a random value [18,2], and MAC-R1 and MAC-R2 inject n-bit randomness into the internal states of CBC-based MACs [23]. Obviously, their high security relies on not only the PRP security of blockciphers but also the randomness of the injected values. In fact, all the deterministic blockcipher-based MACs fall within the birthday bound until Yasuda shows algorithm 6 in the ISO standard is an exception, conditioned on some restrictions on messages [1,30]. In the same paper, Yasuda also introduces SUM-ECBC to reduce the key size in algorithm 6, by XORing the results from two CBC-based MACs, providing half of the efficiency that normal CBC-based MACs offer in serial implementations (rate 2 1 ). On the other hand, Dodis and Steinberger build a MAC from unpredictable blockciphers, with
1
For each message of l blocks long, it has to call the underlying blockcipher roughly 2l times.
298
L. Zhang et al.
security beyond the birthday bound, but pay by very high efficiency cost [12]. Very recently, Yasuda proposes PMAC Plus that improves PMAC beyond the birthday bound [31]. By pre-calculating sufficiently large number (as many as the number of message blocks) of masks, this MAC would provide high efficiency due to the fully parallelizable structure in PMAC and rate-1 design. 3GPP-MAC. To promote the global system for mobile communications, the 3rd Generation Partnership Project (3GPP) proposes f9 as its first MAC algorithm, which is based on blockcipher KASUMI and produces 32-bit tags [6]. f 9 inherits the structure of original CBC MAC, but in the end encrypts the sum of all chaining values, other than the last chaining value, to obtain the tag. The analysis for f 9 tends to be tough due to this particular feature [17]. Knudsen and Mitchell are the first to give birthday attacks on f 9, which need 2(n+1)/2 known (Message, MAC) pairs and 2n/2+1 chosen (Message, MAC) pairs to make a forgery against f 9 without truncations [20]. Then, Iwata and Kohno proved that when KASUMI is secure against a special kind of related-key attacks (RKPRP), a generalized version of f 9 (named with f 9 ) is PRF-secure within the birthday bound [15]. This implies the previous birthday attack is the best one without knowledge of internal information. Despite the fact that the birthday attacks on MACs need on-line invocations, making it much more harder than those on hash functions (needing only offline computations), people still take several countermeasures for large enough security margin. For example, in the practical applications of f 9, it has been demanded that each message should be prepended with a fresh value, the length of messages should be no longer than 20000 bits, the secret key should be changed after each invocation, and the outputs should be truncated [5,6]. 1.2 Our Work
In this paper, we attempt to design a rate-1 CBC-based MAC with provable security beyond the birthday bound. A direct application of such a scheme is to enforce the security level of current CBC-based MACs, especially in the situations where small-size (lightweight) blockciphers are used, e.g. 3GPP and smart cards. Another application is to make it serve as a highly-secure pseudorandom number generator for various protocols, which therefore would improve the security level of the latter. To do this, stateful or random values (e.g. counter, fresh) can help, but we would not consider them for practical convenience. Another possible way is to enlarge the size of internal states but still output normal-size tags. As for CBCbased MACs, however, their internal states have the same size as their underlying blockcipher, so one may want to use a large-size blockcipher in CBC-based MACs and truncate their outputs. Unfortunately, the efficiency of such a solution will not be satisfying, because a large-size blockcipher usually runs no faster than a small-size one, not to mention many other costs, e.g. memory and area requirements.
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
299
Our starting point is f 9, in favor of its double-blocksize internal states providing a possible chance to resist the birthday attacks. Inspired by the design of SUM-ECBC and PMAC Plus, we append one more blockcipher invocation to the end of the f 9 structure, as illustrated in Fig. 1. The resulting MAC is named with 3kf9, for it enhances f 9 and needs three independent keys. From another point of view, it is also an extension of EMAC [27], ignoring EK3 and the last XOR operation.
M1 X1 M2 ML−1 ML
EK1 Y1
c ¤ ¤ ¤
¤ ¤
¤¤
c E⊕
X2 EK1 Y2
c ¤ ¤ ¤
¤ ¤
¤¤
E...
XL−1
c E⊕
EK1
c ¤ ¤
¤ ¤
¤¤
c E⊕
XL EK1 YL
c
YL−1
¤
Q E EK2
c E⊕
E...
c E⊕
c E ⊕ SE EK3
c E⊕ E T
Fig. 1. Illustration of 3kf9
When authenticating messages, 3kf9 can start to work without stateful values or message length information (on-line), requires no pre-computation and only two block-size memory for internal states, besides those for its underlying blockcipher. Specially, it needs no multiplications, comparing with PMAC Plus. Therefore, 3kf9 will provide high efficiency in serial implementations. A more detailed comparison with related MACs is given in Table 1.
Table 1. Comparison among 3kf9 and its related deterministic MACs key size rate structure multi. Alg. 6 in ISO std. SUM-ECBC PMAC Plus 3kf9 f9 EMAC a b c b upper bounds
4 3 q O( l22n )
bBB stands for “beyond the Birthday Bound”. It has been removed from the latest version ISO/IEC 9797-1:2011. Its second key is obtained by K2 = K1 ⊕ KM, where KM is a non-zero k-bit value.
300
L. Zhang et al.
1.3
Organization
The rest of this paper is organized as follows. Section 2 introduces necessary symbols and 3kf9 specification. Section 3 gives our provable security analysis for 3kf9, including security definitions, the main result and its proof. The proof will be completed in Section 4. In Section 5, we give some suggestions for practical usages of 3kf9. Finally, we conclude this work in Section 6.
2
Symbols and Specification
{0, 1}n is the set of all n-bit strings and {0, 1}∗ is the set of all strings. For strings a, b ∈ {0, 1}∗, a||b is a concatenation of a and b, and |a| is its length in bits. If a, b have equal lengths then a ⊕ b is their bitwise XOR. Denote Perm(n) and Rand(n, n) as the sets of all permutations and functions over {0, 1}n respectively. Rand(∗, n) stands for the set of all functions whose range belongs to {0, 1}n . If A is a set, then #A denotes the size of set A, and x ← A means that x is chosen from set A uniformly at random. A message M can be alternatively seen as a bit string M ∈ {0, 1}∗. Then, by M ← M ||10n−1−|M| mod n we mean we append a single bit “1” to the end of M , followed by as many as n − 1 − |M | mod n bit “0”s such that the length of the padded string is a multiple of n. For any such string M (|M | = nL), M1 M2 · · · ML ← Partition(M ) means we break M into L successive n-bit blocks such that M1 ||M2 || · · · ||ML = M .
MAC Algorithm 3kf9[E] Input: K1 , K2 , K3 ← K, M ∈ {0, 1}∗ Output: T ∈ {0, 1}n 01. M ← M ||10n−1−|M | mod n 02. M1 M2 · · · ML ← Partition(M ) 03. S ← 0n 04. Y0 ← 0n 05. for l ← 1 to L do 06. Xl ← Yl−1 ⊕ Ml 07. Yl ← EK1 (Xl ) 08. S ← S ⊕ Yl 09. end for 10. T ← EK2 (YL ) ⊕ EK3 (S) 11. return T Fig. 2. Specification of 3kf9
$
$
For any message M ∈ {0, 1}∗, 3kf9 takes a blockcipher E : KE × {0, 1}n → {0, 1}n as its underlying primitive, calling it iteratively as specified in Fig. 2 to deal with M , and finally outputs T ∈ {0, 1}n as a tag. If necessary, T can be truncated to be of some particular length less than n.
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
301
3kf9 needs three keys K1 , K2 and K3 , each of which should be independently selected from K = KE uniformly at random. We use 3kf9[EK1 , EK2 , EK3 ] to stand for this MAC algorithm and we also write it as 3kf9[E] for short.
3
3.1
Security Proof
Security Definitions
W need to introduce PRP/PRF definitions here, which are frequently used in the analysis of modes of operation for blockciphers [8,27,9,16,24]. These two definitions focus on the randomness of a keyed function fK , which is selected from a function family f : Kf × {0, 1}∗ → {0, 1}n by selecting a random key K. To measure its randomness, fK is compared with a random $ $ function R ← Rand(∗, n) (or a random permutation P ← Perm(n) if f consists of only permutations). The comparison is done as, informally, allowing adversaries (without knowing K) to query an oracle, which is either fK or R with equal probability. The oracle will answer with the corresponding outputs. After some number of queries, the adversaries are asked to tell what the oracle is. The precise definition is given by ⎧ $ $ ⎨ Advprf (A) def | Pr[K ← Kf : AfK (·) = 1] − Pr[R ← Rand(∗, n) : AR(·) = 1]|, = f ⎩ Advprf (t, q, μ) def max{Advprf (A)}, = f f A ⎧ def $ $ prp ⎨ Adv (A) = | Pr[K ← Kf : AfK (·) = 1] − Pr[P ← Perm(n) : AP (·) = 1]|, f ⎩ Advprp (t, q, μ) def max{Advprp (A)}, = f f
A
and the maximum is over all adversaries taking time at most t, making oracle queries at most q, whose total length is at most μ bits. If Advprf (t, q, μ) (or f Advprp (t, q, μ)) is sufficiently small, we say function family f is a pseudorandom f function (PRF) (or a pseudorandom permutation (PRP)). It has been proved that a PRF is a secure MAC [8]. 3.2 Main Results
Let 3kf9[P1 , P2 , P3 ] stand for 3kf9[EK1 , EK2 , EK3 ] when blockcipher E with three independent keys are replaced by three independently random permutations P1 , P2 and P3 , and we further write it as 3kf9[P ] for simplicity. Then, the following theorem says that 3kf9[P ] is a PRF with an upper bound beyond the birthday bound.
302
L. Zhang et al.
Theorem 1 (Main Theorem). For any computationally unbounded adversary A, after querying the oracle q times, with each query no longer than lmax blocks, $ its advantage to distinguish 3kf9[P ] from a random function R ← Rand(∗, n) is upper bounded by | Pr[A3kf9[P ] = 1] − Pr[AR = 1]| ≤ qlmax +q 2n−2
+
2q3 l3 +q3 l2 +2q3 lmax +2q3 max max . 22n−1
We conclude this theorem by the “coefficient H technique” initially proposed by Patarin [25,26]. This method is a useful tool for proving pseudorandom properties of blockcipher structures and modes of operation, and it has been frequently used before [25,13,16,24]. To simplify our proof, we also adopt the framework used in the proofs for SUM-ECBC and PMAC Plus [30,31], which separates the inputs to P2 and P3 into four cases. Taking advantage of some known results for CBC structure, f 9 and sum of PRPs [9,15,22], the first three cases can be easily upper bounded. For the last case, we prove it by Lemma 1 in the next section. Proof. Since A is computationally unbounded, w.l.o.g. we assume A is a deterministic algorithm, otherwise we can maximize A by running it over all possible cases and choose the most powerful one. Based on this, the i-th query / M i ∈ {M 1 , M 2 , · · · , M i−1 } A would make is fully determined by the previous i − 1 input-output pairs (M 1 , T 1 ), (M 2 , T 2 ), · · · , (M i−1 , T i−1 ). Then, if we fix → − a q-tuple T = (T 1 , T 2 , · · · , T q ), we know - all A’s queries are uniquely determined, - the number of queries q is uniquely determined, and - the output of A (0 or 1) is uniquely determined. → − Denote Tset1 = {(T 1 , T 2 , · · · , T q )} is the set that contains all q-tuple T = (T 1 , T 2 , · · · , T q ) such that A outputs 1, and N = #Tset1 . Then we have Evaluation for random function R. Pr[AR = 1] =
→ − T ∈Tset1
Pr[R(M i ) = T i , i = 1, 2, · · · , q] =
N 2qn .
Evaluation for 3kf9[P ]. Pr[A3kf9[P ] = 1] =
→ − T ∈Tset1
Pr[3kf9[P ](M i ) = T i , i = 1, 2, · · · , q] (Pr[3kf9[P ] outputs q random values] × ( 1 q ) ) 2n (1)
≥ =
→ − T ∈Tset1
N × Pr[3kf9[P ] outputs q random values]. 2qn
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
303
Denote CBC[P1 ] as the internal structure of 3kf9[P ], i.e. (Q, S) ← CBC[P1 ](M ), and 3kf9[P ](M ) = P2 (Q) ⊕ P3 (S) = T , as in Fig. 1. In the following analysis, we do step by step for each i = 1, 2, · · · , q. Suppose in the previous i − 1 queries, the i − 1 outputs T 1 , T 2 , · · · , T i−1 are independently random values. Let Domain[P2 ] = {Q1 , Q2 , · · · , Qi−1 } and Domain[P3 ] = {S 1 , S 2 , · · · , S i−1 }. Then, for the i-th query M i , its corresponding (Qi , S i ) ← CBC[P1 ](M i ) will definitely fall into one of the following four cases, Case A: Case B: Case C: Case D: Qi Qi Qi Qi ∈ Domain[P2 ] ∈ Domain[P2 ] / ∈ Domain[P2 ] / ∈ Domain[P2 ] and and and and Si Si Si Si ∈ Domain[P3 ], / ∈ Domain[P3 ], ∈ Domain[P3 ], / ∈ Domain[P3 ].
For Case A, Black and Rogaway have shown that the probability for any two messages to collide in CBC structure (with an independent ending blockcipher invocation, e.g. EMAC, ECBC) is upper bounded by the birthday bound, i.e. 2 Pr[Qj = Qi ] ≤ 4(lmax +1) (See Lemma 3 in [9]). In such a case, we still have 2n / randomness for T i = P2 (Qi ) ⊕ P3 (S i ) because S i ∈ Domain[P3 ] and we can do lazy sampling P3 (S i ). Since at this moment #Domain[P3 ] ≤ i − 1, the advantage to distinguish P3 (S i ) from a random value r ←{0, 1}n is no more than
$
the advantage to distinguish T i from r is upper bounded by For Case B, Iwata and Kohno have pointed out that the probability for any two messages to collide in f 9 (with an independent ending block cipher invocation) 2 +2)2 is also upper bounded by the birthday bound, i.e. Pr[S j = S i ] ≤ (2lmaxn+1 +2 = 2 (See Lemma B.1 in [15], and note that we apply σ ≤ 2lmax + 2 and q = 2 here). Then, by lazy sampling for P2 (Qi ), we know the advantage to 2l2 +4l +4 distinguish T i from r is upper bounded by i−1 max 2n max × i−1 . 2n 1 For Case C, Lucks has proved that the advantage to distinguish T i = P2 (Qi )⊕ 2 2 P3 (S i ) from r is upper bounded by (2n(i−1) 2 ≤ 4(i−1) (See the proof for −(i−1)) 22n Theorem 5 in [22]). As for Case D, we will show by Lemma 1 in the next section that Pr[∃i ∈ q 3 l3 max +q max [1, q] : Case D occurs] ≤ ql2n−2 + 22n−2 . i r] as the event that T i is not an independently random value. Denote [T Then, based on the none occurrence of Case D, we get
Pr[T i r] r|Case A] + Pr[Case B] Pr[T i r|Case C]
2 i − 1 2lmax + 4lmax + 4 i−1 4(i − 1)2 × n +1× n 2 2 22n 1
i−1 2n . Then, i−1 4(lmax +1)2 × i−1 . 2n 2n 1
2l2 +4lmax +4 max 2n
= Pr[Case A] Pr[T i Pr[Case C] Pr[T ≤ = i r|Case B] +
i−1 i − 1 4(lmax + 1)2 × n + 2n 2 1
2 (i − 1)2 (3lmax + 5lmax + 6) . 22n−1
304
L. Zhang et al.
This allows us to have Pr[3kf9[P ] doesn t output q random values] q ≤ Pr[Case D] + i=1 Pr[T i q r]
By the above analysis, we can get Pr[AR = 1] − Pr[A3kf9[P ] = 1] ≤ N N N − qn × (1 − ) ≤ qn × ≤ . 2qn 2 2
On the other side, if we define Tset0 and by similar analysis we can get Pr[AR = 0] − Pr[A3kf9[P ] = 0] ≤ , which implies (1 − Pr[AR = 1]) − (1 − Pr[A3kf9[P ] = 1]) ≤ . Thus we get Pr[A3kf9[P ] = 1] − Pr[AR = 1] ≤ . Finally, we conclude | Pr[A3kf9[P ] = 1] − Pr[AR = 1]| ≤
3 2 qlmax + q 2q 3 lmax + q 3 lmax + 2q 3 lmax + 2q 3 + . n−2 2 22n−1
Based on the main theorem, we can say that 3kf9[E] is a PRF if blockcipher E is secure. More precisely, we have Theorem 2. If blockcipher E : KE × {0, 1}n → {0, 1}n is a PRP, then 3kf9[E] is a PRF for all adversaries, who make at most q queries, each of which is no longer than lmax blocks. That is, Advprf 3kf9[E] (t, q, μ) ≤ qlmax +q 2n−2
+
2q3 l3 +q3 l2 +2q3 lmax +2q3 max max 22n−1
+ 3Advprp (t , q , μ ), E
where t = t + O(t), q ≤ q(lmax + 1), and μ ≤ μ + qn.
4
Key Lemma
The none occurrence of Case D implies the q pairs (Qi , S i ) (i = 1, 2, · · · , q) are free. By “free”, we mean for each i ∈ [1, q], either Qi is unique in its corresponding sequence Q1 , Q2 , · · · , Qq or S i is unique in its corresponding sequence
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
305
S 1 , S 2 , · · · , S q . This property is closely related to the newly appeared Cover Free i i i notion [12], which says the q outputs (N1 , N2 , · · · , Nw ) (1 ≤ i ≤ q) from a coverfree function should satisfy the following property. For each i, there exists at least q i 1 2 one j ∈ [1, w] such that Nj is unique in its own subsequence Nj , Nj , · · · , Nj . Unfortunately, the internal structure CBC[P1 ] can not satisfy the cover free property, when its outputs are made public. However, if adversaries can not get its internal states, CBC[P1 ] holds a similar property, as the following lemma says. Lemma 1. If P1 ,P2 and P3 are independently random permutations from Perm(n), then for all computationally unbounded adversaries, who querying 3kf9[P ] no more than q times, with each query no longer than lmax blocks, the probability for internal states (Qi , S i ) (i = 1, 2, · · · , q) to satisfy Case D is upper bounded by Pr[∃i ∈ [1, q] : Case D occurs] ≤ qlmax +q 2n−2
+
q 3 l3 max 22n−2 .
In the following proof, we will prove an even stronger result. That is, all the pairs (Yli , Sli ) for l = 1, 2, · · · , Li and i = 1, 2, · · · , q are free with this probability, excluding the trivial case that (Yli , Sli ) = (Ylj , Slj ) with l ≤ d for two different mesi i i sages M i and M j , which after being padded are written as M1 ||M2 || · · · ||MLi and j j j j j i i i M1 ||M2 || · · · ||MLj and having common prefix M1 ||M2 || · · · ||Md = M1 ||M2 || · · · || j Md for some d ≤ min{Li , Lj }. To do this, we check the process detail of CBC[P1 ] in dealing with the querying messages M 1 , M 2 , · · · , M q step by step, and record every Yli and Sli for l = 1, 2, · · · , Li and i = 1, 2, · · · , q with two sets YRange and SRange. By lazy sampling for P1 , we upper bound the probability for the events Yli ∈ YRange and Sli ∈ SRange to occur at the same time, and in the end we sum up all these probabilities to get the final result. Proof. For any q pairwise distinct queries M 1 , M 2 , · · · , M q , we use a program to show the process of CBC[P1 ] in dealing with them, as in Fig. 3. To better analyze the target probability, we do lazy sampling for P1 . Furthermore, we denote three flags Zero, Cover and Bad. Zero is used to identify whether there exists Yli = 0n , which may be easily used to undermine the freeness consistence of (Yli , Sli ) for l = 1, 2, · · · , Li and i = 1, 2, · · · , q. Cover is used directly to identify the freeness of (Yli , Sli ). Either [Zero = True] or [Cover = True] implies [Bad = True], so Pr[∃i ∈ [1, q] : Case D occurs] = Pr[Bad = True] ≤ Pr[Zero = True] + Pr[Cover = True]. q(lmax +1) q(lmax +1) 1 Then, it is easy to get that Pr[Zero = True] ≤ j=1 , 2n −(j−1) ≤ 2n−1 because for the q messages whose length is no more than lmax +1 blocks after being padded, we do no more than q(lmax + 1) lazy sampling for P1 , and in the j-th sam1 pling for a new output Y , Pr[Y = 0n ] ≤ 2n −(j−1) . Here we use q(lmax + 1) < 2n−1 to get the final bound. To upper bound Pr[Cover = True] for all (Yli , Sli ), we will upper bound the probability for each lazy sampling that may result in the occurrence of [Yli ∈ YRange ∧ Sli ∈ SRange] with l = 1, 2, · · · , Li and i = 1, 2, · · · , q, and then sum up them. For better understanding the following analysis, we work on a simple case first (see Fig. 4 for an illustration), and then generalize it step by step.
306
L. Zhang et al. 00. Domain[P1 ], Range[P1 ], YRange, SRange ← φ; Zero, Cover, Bad ← False; for A’s i-th query M i ∈ {0, 1}∗ , do i i i i 01. M i ← M i ||10n−1−|M | mod n ; M1 M2 · · · MLi ← Partition(M i ); i n i n 02. S0 ← 0 ; Y0 ← 0 ; 03. for l ← 1 to Li do i 04. Xli ← Yl−1 ⊕ Mli ; i 05. if Xl ∈ Domain[P1 ] then Yli ← P1 (Xli ); 06. else Yli ←{0, 1}n \ Range[P1 ]; 07. if Yli = 0n then Zero ← True; Bad ← True; end if 08. Range[P1 ] ← Range[P1 ] ∪ {Yli }; 09. Domain[P1 ] ← Domain[P1 ] ∪ {Xli }; 10. end if i i 11. Sl ← Sl−1 ⊕ Yli ; i i 12. if Yl ∈ YRange and Sl ∈ SRange and j j i i 13. j < i s.t. M1 ||M2 || · · · ||Mli = M1 ||M2 || · · · ||Mlj 14. then Cover ← True; Bad ← True; i 15. else YRange ← YRange ∪ {Yli }; SRange ← SRange ∪ {Sl }; 16. end if 17. end for Fig. 3. A program showing the process of CBC[P1 ] Mli ... i Ml+1 i Ml+2 $
c E⊕
Xli
c ¤ ¤ ¤
P1 Yli ... i Sl−1 c E⊕
¤ ¤
¤¤
i Xl+1
c E⊕ c ¤ ¤
P1
i Yl+1
¤ ¤
¤
i ¤¤ Xl+2
c E⊕ c ¤ ¤
P1
i Yl+2
¤ ¤
¤
¤¤
E ...
i Sl
c E⊕
i Sl+1
c E⊕
i Sl+2
E ...
Fig. 4. An insight view on the internal structure of CBC[P1 ]
4.1
The Most Common Case
$
For a new input Xli ∈ Domain[P1 ], we will choose a value Yli ←{0, 1}n \Range[P1 ] / by lazy sampling. Since Yli is a new output, it is definite that (Yli , Sli ) is consistent i with the previous pairs for freeness. However, if it happens that Xl+1 = Yli ⊕ i i Ml+1 ∈ Domain[P1 ], then event [Yl+1 ∈ YRange] would occur, and the freeness i consistence of pairs will rely only on the none occurrence of the event [Sl+1 ∈ SRange]. Consider the following two subcases: i i i i 1. Xl+1 = Xli . This implies Yl+1 = Yli and Sl+1 = Sl−1 , and thus undermining the freeness consistence. The probability for this event to occur is no more
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
307
1 1 i i than Pr[Xl+1 = Xli ] = Pr[Yli = Xli ⊕ Ml+1 ] ≤ 2n −#Range[P1 ] ≤ 2n−1 , where n−1 we assume #Range[P1 ] < 2 . i i 2. Xl+1 ∈ Domain[P1 ] \ {Xli }. This implies Yli ⊕ Ml+1 ∈ Domain[P1 ] \ {Xli }, and so Yli has no more than #Domain[P1 ] \ {Xli } choices. Choose any one i i i such choice and fix Yli , then Yl+1 = P1 (Xl+1 ) = P1 (Yli ⊕ Ml+1 ) would be l+1 i i fixed, so is Sl+1 = c=1 Yc . On the other hand, the elements in SRange d d j j i are c=1 Yc (1 ≤ d ≤ L , 1 ≤ j ≤ i − 1) and c=1 Yc (1 ≤ d ≤ l). i Then, event [Sl+1 ∈ SRange] implies no more than #SRange equations, all of which can be written as linear combination of Yba equals to linear i a combination of message blocks (i.e. Ml+1 ⊕ Mb+1 or 0n ) with 0 ≤ b ≤ La , 1 ≤ a ≤ i − 1 or 0 ≤ b ≤ l − 1, a = i. Specially, note that Yli is not i included here because Xl+1 ∈ Domain[P1 ] \ {Xli } implies Yli can be written i i i as Ml+1 ⊕ Xl+1 = Ml+1 ⊕ Y ⊕ M , where Y and M appear in the previous (Y, S) pairs and queries respectively (Y may be 0n if b = 0). Furthermore, notice that we have upper bounded Pr[Y = 0n ] by analyzing [Zero = True], so we can assume all Yba (b ≥ 1) are non-zero values. Then, excluding the trivial case that two different messages would collide in their common prefix part, the possibility for each of these equations to hold is no more than 1/2n−1 , because all Yba (b ≥ 1) are chosen by the previous lazy samplings, from a space with roughly 2n − #Domain[P1 ] − #Range[P1 ] − 1 ≤ 2n−1 size. 2n − #Range[P1 ] is naturally understood, “1” is respect to 0n , and “#Domain[P1 ]” is respect to the number of bad points that may result in a Yba ⊕Mb+1 ∈ Domain[P1 ]. So the linear combinations of Yba has at least 2n−1 possible values, and their real values are hidden in the internal structure CBC[P1 ], not known by adversaries. So, in this subcase, i i Pr[Yl+1 ∈ Range[P1 ] \ {Yli } ∧ Sl+1 ∈ SRange] i i = Pr[Xl+1 ∈ Domain[P1 ] \ {Xli } ∧ Sl+1 ∈ SRange] i i = Pr[Yli ⊕ Ml+1 ∈ Domain[P1 ] \ {Xli } ∧ Sl+1 ∈ SRange]
Where we apply #Range[P1 ] < 2n−1 . Notice that P1 [Xli ] = Yli ←{0, 1}n \ i Range[P1 ] is a new lazy sampling, and Sl+1 ∈ SRange is only related with i i previous lazy samplings (Xl+1 ∈ Domain[P1 ] \ {Xli } implying Yli = Ml+1 ⊕ Y ⊕M can be calculated by the previous pairs and queries), so the probability in (2) can be separated, thus we obtain inequality (3). In this most common case, the probability for lazy sampling P1[Xli ] = Yli ←{0, 1}n\ 2 1 Range[P1 ] to undermine the freeness consistence is at most 2n−1 + (#Domain[P1 ]) . 22n−2
$
$
308
L. Zhang et al.
4.2
Generalized Case 1
i The above lazy sampling may further induce the occurrence of event [Xl+2 ∈ Domain[P1 ]], so the previous analysis is not complete, and here we generalize it in this direction. $ Suppose P1 [Xli ] = Yli ←{0, 1}n \ Range[P1 ] induces series of occurrences, i.e. i i i [Xl+1 ∈ Domain[P1 ]], [Xl+2 ∈ Domain[P1 ]], · · · , [Xl+u−1 ∈ Domain[P1 ]], with i u ≤ L − l + 1, let us consider the probability to undermine the freeness con1 i sistence. First, we have Pr[Xl+1 = Xli ] ≤ 2n−1 as before. Then, conditioned i i i i i on Xl+1 = Xl , those u − 1 events imply Yl ⊕ Ml+1 ∈ Domain[P1 ] \ {Xl+1 } i i i and Yl+a ⊕ Ml+a+1 ∈ Domain[P1 ] for 1 ≤ a ≤ u − 2, and so Yl has at most i i #Domain[P1 ]\{Xl+1 } choices. Choose any one such choice and fix Yli , then Sl+a (0 ≤ a ≤ u − 1) are also fixed. To keep freeness consistence, none of the events i i [Sl+1+a ∈ SRange ∪ {Sli , Sl+1 , · · · , Sl+a }] (0 ≤ a ≤ u − 2) should occur. These events imply no more than (u − 1)#SRange+ (u−1)(u−2) equations, and each has 2 a probability of 1/2n−1 to occur, with similar reasons given in the most common case. So, here the probability for this lazy sampling to keep freeness consis#Domain[P1 ]\{Xl+1 } (u−1)#SRange+ 1 2 × 2n−1 + 2n −#Range[P1 ] 2n−1 2 u (#Domain[P1 ]+a−1) 1 ). Notice that u is the number of invocations a=1 ( 2n−1 + 22n−2 $ P1 related to lazy sampling P1 [Xli ] = Yli ←{0, 1}n \ Range[P1 ]. i (u−1)(u−2)
tence is upper bounded by
≤ to
4.3
Generalized Case 2
Since we assume adversaries can make any q pairwise distinct queries M 1 , M 2 , · · · , M q , it is possible that some queries share a common prefix. Here we gen$ eralize the probability for lazy sampling P1 [Xli ] = Yli ←{0, 1}n \ Range[P1 ] to undermine the freeness consistence in this direction. Without loss of generality, we assume M i , M i+1 , · · · , M i+v−1 share a common prefix (This can be reached by sorting the queries), and Mli is the last block i+b i+b / in their prefix. If Xl+1 = Yli+b ⊕ Ml+1 ∈ Domain[P1 ] for all b ∈ [0, v − 1], i+b i+b then Yl+1 can keep freeness consistence. However, if ∃b ∈ [0, v − 1] s.t. Xl+1 = i+b i+b i+b i+b i+b i+b i+b i Yl ⊕Ml+1 = Xl = Xl , then the events [Yl+1 = Yl ] and [Sl+1 = Sl−1 ] will occur, and thus undermine the freeness consistence. This probability is no more i+b v than Pr[∃b ∈ [0, v − 1], Xl+1 = Xli+b ] ≤ 2n−1 . Based on its none occurrence, we i+b focus on the probability of [∃b ∈ [0, v − 1], Xl+1 ∈ Domain[P1 ] \ {Xli}]. Note that i+b i some particular choices of Yl may result in several [Xl+1 ∈ Domain[P1 ] \ {Xli }] i to occur at the same time, and the number of Yl that induces v such events is i+1 i+v i no more than #Domain[P1 ]v/v . W.l.o.g. we assume Xl+1 , Xl+1 , · · · , Xl+1 −1 ∈ i i Domain[P1 ] \ {Xl } for some v ∈ [1, v]. Choose any one such Yl and fix it, i+1 i+v i+1 i+v i i then Yl+1 , Yl+1 , · · · , Yl+1 −1 would be fixed, so are Sl+1 , Sl+1 , · · · , Sl+1 −1 . The i+j i+j−1 i+1 i events [Sl+1 ∈ SRange ∪ {Sl+1 , Sl+1 , · · · , Sl+1 }] (0 ≤ j ≤ v − 1) imply no more than v #SRange + v (v2−1) equations, with probability 1/2n−1 to occur each. Then it is not hard to get the probability to keep freeness consistence in this
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
309
case is no more than
(#Domain[P1 ]+b−1)2 ). Notice that v is 22n−2 $ lazy sampling P1 [Xli ] = Yli ←{0, 1}n
2n−1
v
+ #Domain[P1 ]v/v × 2n −#Range[P1 ]
v #SRange+ v 2n−1
(v −1) 2
≤
v 1 b=1 ( 2n−1
+
the number of invocations to P1 related to \ Range[P1 ].
4.4
The Most General Case
i+b i+b i+b can be fixed by Yli . The events [Sl+a+1 ∈ SRange ∪ {Sli+b , Sl+1 , · · · , Sl+a }] with s 0 ≤ a ≤ u[b] − 2 and 0 ≤ b ≤ v − 1 imply no more than w=1 (#SRange + w − 1) equations (s = v −1 u[b]), with probability 1/2n−1 to occur each. Then we can get b=0
Based on the above, we generalize the most common case in two directions, as in Generalized case 1 and 2. The analysis here is the same as that in Generalized case 2, until Yli is fixed. i+1 i+v i and w.l.o.g. we assume Xl+1 , Xl+1 , · · · , Xl+1 −1 ∈ Domain[P1 ] \ {Xli } for some v ∈ [1, v] occurs. Then we take Generalized case 1 into account. i+b i+b i+b Suppose for Xl+1 (0 ≤ b ≤ v − 1), its following calls to P1 Xl+2 , Xl+3 , · · · , i+b i+b i+b i+b i+b Xl+u[b]−1 ∈ Domain[P1 ], with u[b] ≤ L − l + 1. Then Sl , Sl+1 , · · · , Sl+u[b]−1
the probability for lazy sampling P1 [Xli ] = Yli ←{0, 1}n \ Range[P1 ] to undermine s (#SRange+w−1) v the freeness consistence is at most 2n−1 + #Domain[P1 ]v/v × w=1 2n−1 ≤ 2n −#Range[P1 ] s 1 w=1 ( 2n−1
$
+
(#Domain[P1 ]+w−1)2 ). 22n−2
Notice that s = P1 [Xli ] =
invocations to P1 related to lazy sampling 4.5 Summing Up
v −1 b=0 u[b] is the number $ i← Yl {0, 1}n \ Range[P1 ].
of
1 mine the freeness consistence is no more than s ( 2n−1 + (#Domain[P1 ]+w−1) ), w=1 22n−2 where s is the number of invocations to P1 related to this lazy sampling. Suppose in dealing with M 1 , M 2 , · · · , M q , we do z times lazy sampling in total, and the invocations to P1 related to them are s1 , s2 , · · · , sz respectively. Thus, z
From the most common case to the most general case, we have observed that for $ every lazy sampling P1 [Xli ] = Yli ←{0, 1}n \ Range[P1 ], its probability to under2
Pr[Cover = True] ≤ j=1 z
Pr[Cover = True in lazy sampling j] sj ≤
( j=1 w=1
1 2n−1
+
(#Domain[P1 ] + w − 1)2 ) 22n−2 (w − 1)2 22n−2
q(lmax + 1) ≤ + 2n−1
q(lmax +1) w=1
3 qlmax + q q 3 lmax ≤ + 2n−2 , 2n−1 2
310
L. Zhang et al.
where we apply z sj ≤ q(lmax + 1) and note that #Domain[P1 ] is a variable j=1 growing from 0 to some value no larger than q(lmax + 1), with lazy samplings. At last, we get Pr[∃i ∈ [1, q] : Case D occurs] = Pr[Bad = True] ≤ Pr[Zero = q 3 l3 q 3 l3 max +1) max +q max +q max max True] + Pr[Cover = True] ≤ q(l2n−1 + ql2n−1 + 22n−2 = ql2n−2 + 22n−2 .
5
Some Suggestions
The key size in 3kf9 is three times of that for its underlying blockcipher, and this may be too large to be stored securely in some resource-restricted environments. For such cases, we give the following solutions: 1. Derive a master key K ← {0, 1}k , and generate Ki = EK (Csti ) (i = 1, 2, 3) − with three different constants Csti . Then we need only to store the master key K securely. The security of the resulting scheme is still guaranteed by the PRP assumption on blockcipher E. $ − 2. Derive K1 ← {0, 1}k , and generate Ki = K1 ⊕Csti for i = 2, 3, with two nonzero constants Cst2 , Cst3 . Then we need only to store K1 securely. However, this solution requires blockcipher E should be a RK-PRP (pseudorandom against a kind of related-key attacks) [15]. We warn that generating K2 = EK1 (Cst2 ) and K3 = EK1 (Cst3 ) may result in security flaws in 3kf9, because EK (K⊕·) may not reach pseudorandomness given E is a PRP [29]. 3. Adopt a beyond-birthday-bound tweakable blockcipher TBC as the underlying primitive in 3kf9. Then, we can replace EK1 , EK2 and EK3 by TBCT1 , K TBCT2 and TBCT3 , where T1 , T2 , T3 are three public tweaks. Such a TBC K K has recently been introduced by Landecker, Shrimpton and Terashima [21], but the current TBC scheme still needs key size reducing. Since CMAC has been widely used in practical applications [4], someone may want to use CMACK1 (·)⊕CMACK2 (·) to get a highly secure MAC. We note that the precise security of this proposal is still unclear [30], and it is rate-2, implying more power consumption and lower efficiency in serial implementations.
$
6
Conclusion
We propose a rate-1 CBC-based MAC 3kf9 with provable security beyond the birthday bound in this paper. 3kf9 is efficient for its rate-1 design, and highly3 3 q lq secure for its O( l22n + 2n ) PRF bound. Moreover, 3kf9 is light in the sense that it needs only XOR operations besides blockcipher invocations, and thus it immediately turns into a lightweight MAC when equipped with a lightwight blockcipher. However, its key size seems to be too large in some particular environments, requiring further improvements therefore.
3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound
311
Acknowledgments. The authors would like to thank the anonymous referees at both FSE 2012 and Asiacrypt 2012 and the attendees at ASK 2011 for their valuable comments. Special thanks to Lei Wang for pointing out a flaw in an earlier proof, to Tetsu Iwata for some technical comments, and to Yuefei Sui for some editorial comments. Furthermore, this work is supported by the National Natural Science Foundation of China (No. 61272476, 91118006, 60903219 and 61202422), and the National Grand Fundamental Research 973 Program of China .
References
1. ISO/IEC 9797-1:1999. Information technology – Security Techniques – Message Authentication Codes (MACs) – Part 1: Mechanisms Using a Block Cipher. Revised by ISO/IEC 9797-1:2011 2. Public Commnets, http://csrc.nist.gov/groups/ST/toolkit/BCM/comments.html 3. Requirements for SHA-3 by NIST, Federal Register vol. 72(212), http://csrc.nist.gov/groups/ST/hash/sha-3/index.html 4. Special Publication 800-38B. Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication. National Institute of Standards and Technology, http://csrc.nist.gov/groups/ST/toolkit/BCM/current_modes.html 5. TS 33.105. 3G Security: Cryptographic Algorithm Requirements, http://www.3gpp.org/ftp/Specs/html-info/33-series.htm 6. TS 35.201. 3G Security: Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 1: f8 and f9 Specifications, http://www.3gpp.org/ftp/Specs/html-info/35-series.htm 7. TS 35.202. 3G Security: Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 2: Kasumi Specification, http://www.3gpp.org/ftp/Specs/html-info/35-series.htm 8. Bellare, M., Kilian, J., Rogaway, P.: The Security of Cipher Block Chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–358. Springer, Heidelberg (1994) 9. Black, J., Rogaway, P.: CBC MACs for Arbitrary-Length Messages:The Three-Key Constructions. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 197–215. Springer, Heidelberg (2000) 10. Black, J., Rogaway, P.: A Block-Cipher Mode of Operation for Parallelizable Message Authentication. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 384–397. Springer, Heidelberg (2002) 11. Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M., Seurin, Y., Vikkelsoe, C.: PRESENT: An Ultra-Lightweight Block Cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007) 12. Dodis, Y., Steinberger, J.: Domain Extension for MACs Beyond the Birthday Barrier. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 323–342. Springer, Heidelberg (2011) 13. Gilbert, H., Minier, M.: New Results on the Pseudorandomness of Some Blockcipher Constructions. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 248–266. Springer, Heidelberg (2002)
312
L. Zhang et al.
14. Guo, J., Peyrin, T., Poschmann, A.: The PHOTON Family of Lightweight Hash Functions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 222–239. Springer, Heidelberg (2011) 15. Iwata, T., Kohno, T.: New Security Proofs for the 3GPP Confidentiality and Integrity Algorithms. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 427–445. Springer, Heidelberg (2004) 16. Iwata, T., Kurosawa, K.: OMAC: One-Key CBC MAC. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 129–153. Springer, Heidelberg (2003) 17. Iwata, T., Kurosawa, K.: On the Correctness of Security Proofs for the 3GPP Confidentiality and Integrity Algorithms. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 306–318. Springer, Heidelberg (2003) ´ 18. Jaulmes, E., Joux, A., Valette, F.: On the Security of Randomized CBC-MAC Beyond the Birthday Paradox Limit: A New Construction. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 237–251. Springer, Heidelberg (2002) 19. Joux, A., Poupard, G., Stern, J.: New Attacks against Standardized MACs. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 170–181. Springer, Heidelberg (2003) 20. Knudsen, L.R., Mitchell, C.J.: Analysis of 3gpp-MAC and Two-key 3gpp-MAC. Discrete Applied Mathematics 128(1), 181–191 (2003) 21. Landecker, W., Shrimpton, T., Terashima, R.S.: Tweakable Blockciphers with Beyond Birthday-Bound Security. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 14–30. Springer, Heidelberg (2012) 22. Lucks, S.: The Sum of PRPs Is a Secure PRF. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 470–484. Springer, Heidelberg (2000) 23. Minematsu, K.: How to Thwart Birthday Attacks against MACs via Small Randomness. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 230–249. Springer, Heidelberg (2010) 24. Nandi, M.: Fast and Secure CBC-Type MAC Algorithms. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 375–393. Springer, Heidelberg (2009) 25. Patarin, J.: Pseudorandom Permutations Based on the DES Scheme. In: Cohen, G.D., Charpin, P. (eds.) EUROCODE 1990. LNCS, vol. 514, pp. 193–204. Springer, Heidelberg (1991) 26. Patarin, J.: The “Coefficients H” Technique. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 328–345. Springer, Heidelberg (2009) 27. Petrank, E., Rackoff, C.: CBC MAC for Real-Time Data Sources. J. Cryptology 13(3), 315–338 (2000) 28. Preneel, B., van Oorschot, P.C.: MDx-MAC and Building Fast MACs from Hash Functions. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 1–14. Springer, Heidelberg (1995) 29. Wang, P., Feng, D., Wu, W., Zhang, L.: On the Unprovable Security of 2-Key XCBC. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 230–238. Springer, Heidelberg (2008) 30. Yasuda, K.: The Sum of CBC MACs Is a Secure PRF. In: Pieprzyk, J. (ed.) CTRSA 2010. LNCS, vol. 5985, pp. 366–381. Springer, Heidelberg (2010) 31. Yasuda, K.: A New Variant of PMAC: Beyond the Birthday Bound. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 596–609. Springer, Heidelberg (2011)
