0c3e6e501bb64662d4dc9d9e74099b35bff9d2d2

19 a message it's not seen before.

27 against chosen message attack}, or SUF-CMA, for short

33 its choice, and checking some guesses, it can return a pair $(m, \tau)$

34 such that:

37 \item the tag is not one returned by the adversary's tagging oracle for

38 that message.

46 We perform the following experiment with the adversary.

56 $\tau \gets T_K(m)$; \\

72 where the maximum is taken over all adversaries $A$ running in time $t$ and

73 making $q_T$ tagging and $q_V$ verification queries.

77 SUF-CMA sense}.

84 There are a number of weaker security notions in use:

87 returning any message with which it queried its tagging oracle. The

88 strong MAC definition considers this OK, as long as the tag is different

89 from any returned by the oracle for that message.

90 \item Some definitions of MACs don't equip the adversary with a

91 verification oracle. Our definition considers these to be $(t, q_T, 0,

92 \epsilon)$-secure.

95 \item Further quantification is possible, e.g., counting the total number

96 of bytes queried, or the maximum size of a tagging query.

107 PRF, then it's also a $(t', q_T, q_V, \epsilon')$-secure MAC, with $q = q_T

110 model of computation.

112 Suppose $A$ can break $F$ used as a MAC in time $t$ and with $q_T$ and

113 $q_V$ queries to its tagging and verification oracles respectively.

115 If we can construct an adversary which distinguishes $F_K$ from a random

116 function using $A$ as an essential component, then we can prove the

117 result.

130 Oracle $T_F(m)$: \+ \\

133 Oracle $V_F(m, \tau)$: \+ \\

142 The distinguisher simulates the tagging and verification oracles for the

143 MAC forger, using its supplied oracle. If the forger succeeds, then the

144 distinguisher returns 1; otherwise it returns zero.

146 The probability that the distinguisher returns 1 given an instance $F_K$ of

149 The probability that it returns 0 given a random function depends on what

150 $A$ does when it's given a random function. But we know that the

151 probability of it successfully guessing the MAC for a message for which it

154 Let $q = q_T + q_V + 1$; then counting, rearranging, maximizing yields

164 as a MAC.

165 \item Discuss the merits of truncating MAC tags in practical situations.

169 \item The follows exactly the same pattern as the `PRFs are MACs' proof in

172 \item Obviously, truncating tags saves bandwidth. There is a trade-off

174 this term represents the probability of the adversary guessing the

175 correct tag when it's actually attacking a random function, and

176 therefore, when this occurs, the adversary has one `by accident'.

177 Including sequence numbers in packets ensures that replay of accidental

178 forgery (or honest messages) will be detected. Hence, for some

180 Perhaps more significantly, if the PRF isn't actually as good as it ought

181 to be, and (say) leaks key material very slowly, then truncating its

182 output can actually improve security.

190 (applying some sort of padding if you need to). Then we define the CBC-MAC

195 introduced the world to the concrete-security approach and, almost

196 incidentally, proved that the CBC-MAC is a PRF (and therefore a MAC) for

199 Show that the CBC-MAC is easily broken if you're allowed to choose messages

200 of different lengths.

207 forgery.

214 We can leave verification oracles out of our analysis. This simplifies

215 analysis, but produces slightly less satisfactory quantitative results.

218 MAC. Then, for any $q_V$,

222 this to do better.

226 Consider an adversary $A$ which uses $q_V$ verification queries. We assume

227 the following properties of $A$'s behaviour:

229 \item No verification query contains a message and a tag for that message

230 received from the tagging oracle.

231 \item If a verification query succeeds, the message is not given in a query

232 to the tagging oracle.

233 \item Once a verification query succeeds, all subsequent verification

234 queries also succeed and the adversary returns a correct forgery (e.g.,

235 by simply repeating the succeessful query).

237 It's clear that any adversary can be transformed into one which has these

238 properties and succeeds with probability at least as high.

240 Let $V$ be the event that at least one verification query succeeds, and let

241 $S$ be the event that $A$ succeeds. Then

247 Now consider these two adversaries:

258 \next

260 \\

266 The adversary $A'$ uses $q_V - 1$ verification queries. It ignores the

267 output of $A$, returning instead $A$'s $q_V$-th verification query. Thus,

268 by our assumptions on the behaviour of $A$, we have that $A'$ succeeds

269 precisely whenever one of $A$'s verification queries succeeds. Thus:

272 Similarly, the adversary $Z$ succeeds with precisely the same probability

273 as $A$, given that all of its verification queries failed; i.e.,

276 Because $A$ was chosen arbitrarily, we can maximize:

283 as required.

285 To show that the bound is tight, consider a random function $F$ used as a

288 q_T, q)$. We prove the claim by induction on $q$. Firstly, note that if

290 q/2^L$. We're now allowed an extra query, so rather than returning the

291 result, we feed it to the verification oracle. If it answers `yes' then we

292 return it; otherwise we guess randomly from the remaining $2^L - q$

293 possibilities. Now

299 as claimed.

307 It ought to be possible to construct a decent MAC using a hash function.

308 Many attempts have failed, however. For example, these constructions are

315 It would be nice to have a construction whose security was provably related

316 to some plausible property of the underlying hash function.

325 then we compute $H_K(x)$ as follows:

330 \item The result $H_K(x) = I_n$.

332 The NMAC (nested-MAC) construction requires two independent $k$-bit keys

333 $K_0$ and $K_1$. The construction itself is simply:

335 NMAC is deterministic, so verification consists of computing the tag and

336 comparing.

344 for any adversary $A$ constrained to run in time $t$ and permitted $q$

345 oracle queries,

350 If $H_K$ is a $(t, q_T, q_V, \epsilon)$-secure MAC on $k$-bit messages, and

351 moreover $(t, q_T + q_V, \epsilon')$-weakly collision resistant, then

359 using $q_T$ tagging queries and $q_V$ verification queries with probability

360 $\epsilon$. We construct an adversary $A'$ which forces a $H$ tag for a

361 $k$-bit in essentially the same time.

368 $A'$ might fail even though $A$ succeeded only if the message it returns,

369 $H_K(m)$, collides with one of its tagging queries. But since $H_K$ is

370 $(t, q_T + q_V, \epsilon')$-weakly collision resistant, this happens with

371 at most probability $\epsilon'$. Hence, $A'$ succeeds with probability at

378 Implementing NMAC involves using strange initialization vectors and

379 generally messing about with your hash function. HMAC is an attempt to

380 capture the provable security properties using a plain ol' hash function.

382 Suppose $H$ is an iterated hash function with a $k$-bit output and $L$-bit

385 $L/8$ times. Select a key $K$ of $L$ bits: if your key is shorter, pad it

386 by appending zero bits; if it's longer, hash it with $H$ and then pad.

388 The HMAC tagging function is then defined as

396 Comparing the two constructions, we see that

400 Here, $I$ is $H$'s initialization vector, $F$ is the compression function;

401 $H'$ denotes a keyed hash function that is `like' $H$ but performs padding

402 as if there were an extra initial block of message data for each message.

404 The proof of NMAC assumes that the two keys are random and independent.

405 This isn't the case in HMAC, but a little handwaving about pseudorandomness

406 of the compression function makes the problem go away.

412 function $H_K(x)$ as follows:

415 mapping. Break the image of $x$ under this mapping into $\ell$-bit

420 where $I$ is some fixed $t$-bit string (e.g., $I = 0^t$).

425 case consists of computing the tag and comparing to the one offered.

430 0 & otherwise

433 Decide whether each of these constructions is secure. A full proof is

434 rather hard: an informal justification would be good.

437 assumption that $F$ is a PRF.

440 is a PRF. This is actually quite involved. Given an adversary $A$

441 attacking $T^1$ as a PRF, we construct an adversary $B$ attacking $F$,

442 which simply computes $H$ as required, using the oracle supplied. To

443 complete the proof, we need to show a bound on the

444 information-theoretic security of $H$ when instantiated using a random

445 function $F$. For the sake of simplicity, we allow the adversary $A$

447 messages. We count the number $q'$ of individual message blocks.

449 As the game with $A$ progresses, we can construct a directed

451 labelled $I$. When processing an $H$-query, each time we compute $t'

452 = F(t \cat x_i)$, we add a node $t'$, and an edge $x_i$ from $t$ to

453 $t'$. The `bad' event occurs whenever we add an edge to a previously

454 existing node. We must show, firstly, that the

455 adversary cannot distinguish $H$ from a random function unless the bad

456 event occurs; and, secondly, that the bad event doesn't occur very

457 often.

459 The latter is easier: our standard collision bound shows that the bad

462 The former is trickier. This needs a lot more work to make it really

463 rigorous, but we show the idea. Assume that the bad event has not

465 same as an earlier query, then $A$ learns nothing (because it could

467 prefix of some previous query, then we must add a new edge to our

468 graph; then either the bad event occurs or we create a new node for

469 the result, and because $F$ is a random function, the answer is

470 uniformly random. Finally, we consider the case where the query is a

471 prefix of some earlier query, or queries. But these were computed at

472 random at the time.

474 At the end of all of this, we see that

477 and hence

481 Now we turn our attention to $T^1$. It's clear that we can't simulate

482 $T^1$ very easily using an oracle for $F$, since we don't know $K$

483 (and indeed there might not be a key $K$). The intuitive reason why

484 $T^1$ is insecure is that $F$ might have leak useful information if

485 its input matches its key. This doesn't affect the strength of $F$ as

486 a PRF because you have to know the key before you can exploit this

487 leakage; but $T^1$ already knows the key, and this can be exploited to

488 break the MAC.

490 To show that this is insecure formally, let $F'$ be defined as

491 follows:

494 $|p| = t$ and $|q| = \ell - k$ \\

495 F_K(x) & otherwise

497 We choose a simple injective padding scheme: if $x$ is a message then

500 is insecure as a MAC: submitting a tagging query for the empty string

501 $\emptystring$ reveals the key $K$, which can be used to construct a

502 forgery.

504 To complete the proof, we must show that $F'$ is a PRF. Let $A$ be an

505 adversary attacking $F'$. We consider a series of games; for each

507 Game~$\G0$ is the standard attack game with $A$ given an oracle for a

508 random function; game~$\G1$ is the same, except that $A$ is given an

513 immediately, and let $F_2$ be the event that this occurs. By

516 that we give $A$ an oracle for $F_K$ rather than $F'_K$. Since $F$

522 Finally, we bound the probability of $F_2$. Fix an integer $n$.

523 Consider an adversary $B$ attacking $F$ which runs as follows. It

525 then runs $A$, except that, for each oracle query $x$, it parses $x$

530 returns $0$. Clearly, if $B$ is given an instance $F_K$ of $F$ then

534 queries, and takes time $t + O(n q)$. Wrapping everything up, we get

547 \ran H$. We define

552 almost-universality is not quantified by running times.

556 insecurity: this isn't true.

576 Suppose that $H$ is $\epsilon$-almost universal. Consider this experiment:

579 $(x, y) \gets A$; \\

580 $K \getsr \keys H$; \\

584 The adversary may make random decisions before outputting its selection

586 \epsilon$.

597 Now we treat $\rho$ as a random variable, selected from some distribution

606 Thus, no adversary can succeed in producing a collision in an

608 But obviously the adversary can ignore its coin tosses and simply return

609 the best colliding pair. Hence the two notions are completely equivalent.

616 Suppose that $G$ is $\epsilon$-almost universal, and $G'$ is

638 Suppose that, instead of merely a pair $(x, y)$, our adversary was allowed

641 \inr \keys H$.

644 with $|Y| \le q$. Then

649 This is rather tedious. We use the dynamic view. Suppose $A$ returns $(x,

650 Y)$ with $|Y| = q$, and succeeds with probability $\epsilon$. Consider

652 Adversary $A'$: \+ \\

653 $(x, Y) \gets A$; \\

654 $y \getsr Y$; \\

657 The worst that can happen is that $A'$ accidentally removes the one

658 colliding element from $Y$. This occurs with probability $2/q$. So

660 Rearranging and maximzing gives

664 simple inductive argument completes the proof.

679 0 & otherwise

682 We have

685 & \le

692 We shall prove the result for $q_V = 0$ and $q_T = q$, and appeal to the

693 earlier result on verification oracles.

696 issuing $q$ tagging queries. Consider a distinguisher $D$, constructed

697 from a forger $A$:

710 Note that $A$ isn't provided with a verification oracle: that's because we

711 didn't allow it any verification queries.

713 We can see immediately that

719 \tau^*)$, and that its tagging oracle queries and their answers are $(m_i,

724 If $C$ doesn't occur, then $F$ has not been queried before at $H_K(m)$, but

726 $C$ does occur, then we just assume that the adversary wins, even though it

727 might not have guessed the right tag.

730 Then

734 The result follows.

748 0$ shows that

755 We can take a dynamic view of almost XOR-universality using the same

756 technique as for almost universal functions.

766 Using the same trick as for proving the dynamic view:

775 Since $H$ is arbitrary, this proves the lower bound on the almost

776 XOR-universality.

783 We extend our result about composition of almost-universal functions.

784 Suppose that $G$ is $\epsilon$-almost XOR universal, and $G'$ is

785 $\epsilon'$-almost universal (it doesn't have to be almost XOR-universal),

789 XOR-universal. The proof is simple, and very similar to the

790 almost-universal case.

797 The security result for the UH-based MAC contains a factor $q_T$, which

798 it'd be nice to remove. Our new scheme uses an AXU hash $H\colon \keys H

810 \next

816 Note that verification is stateless.

832 We can avoid statefulness by using randomization. This new scheme is

840 \next

855 We prove the result with $q_V = 0$ and $q_T = q$, and appeal to the result

856 on verification oracles. Let $m_i$ be the message specified in the $i$-th

861 ensures that the nonces are all distinct (we have $s_i = i$). The security

862 bound for the randomized version merely has as an extra term upper bound

863 for the probability of a nonce collision.

865 Let $A$ be an adversary attacking the MAC in time $t$, and using $q$

866 tagging queries. Then we present the following pair of adversaries:

871 $K \getsr \keys H$; \\

883 \next

884 Collision-finder $C$: \+ \\

891 $m_i \gets m$; \\

898 We need to find a lower bound on the advantage of $D$. If $F$ is chosen

899 from the PRF then $D$ returns $1$ precisely when $A$ finds a valid

900 forgery. We now examine the setting in which $F$ is a random function.

902 Let $S$ be the event that $A$ succeeds in returning a valid forgery when

903 $F$ is random, and let $N$ be the event that the nonce $s$ returned by $A$

904 is not equal to any nonce $s_i$ returned by the tagging oracle. Suppose

905 $N$ occurs: then the random function $F$ has never been queried before at

908 So suppose instead that $N$ doesn't occur. Then, since the $s_i$ are

909 distinct, there is a unique $i$ such that $s = s_i$. For $A$ to win, we

910 must have $m \ne m_i$ (for if $m = m_i$ then the only valid tag is

912 tagging oracle). If $A$'s forgery is successful then

916 but $s = s_i$, whence

918 Since the $s_i$ are distinct and $F$ is a random function, the $\sigma_i$

923 Wrapping up, we have

931 Maximizing and rearranging yields the required result.

937 handling of the XOR-collision probability.

940 \endinput

942 %%% Local Variables:

943 %%% mode: latex

944 %%% TeX-master: "ips"

945 %%% End: