# (The exact security of) Message Authentication Codes

##### By: Rybar, Michal.

Material type: BookPublisher: IST Austria 2017Item type | Current location | Call number | Status | Date due | Barcode | Item holds |
---|---|---|---|---|---|---|

Book | Library | Available | AT-ISTA#001526 |

Thesis

Abstract

About the author

List of publications

List of abbreviations

1 Introduction

2 Preliminaries

3 Message Authentication Codes

4 Exact Security of HMAC

5 Exact Security of PMAC

6 Paper 1

7 paper 2

Bibliography

In this thesis we discuss the exact security of message authentications codes HMAC,

NMAC, and PMAC. NMAC is a mode of operation which turns a fixed input-length keyed

hash function f into a variable input-length function. A practical single-key variant of

NMAC called HMAC is a very popular and widely deployed message authentication code

(MAC). PMAC is a block-cipher based mode of operation, which also happens to be the

most famous fully parallel MAC.

NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to

be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions.

Unfortunately, for many instantiations of HMAC one of them has been found to be wrong.

To restore the provable guarantees for NMAC, Bellare [Crypto’06] showed its security

without this assumption.

PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with

a pseudorandom permutation over n-bit strings, PMAC constitutes a provably secure

variable input-length PRF. For adversaries making q queries, each of length at most ` (in

n-bit blocks), and of total length σ ≤ q`, the original paper proves an upper bound on

the distinguishing advantage of O(σ 2 /2 n ), while the currently best bound is O(qσ/2 n ). In

this work we show that this bound is tight by giving an attack with advantage Ω(q 2 `/2 n ).

In the PMAC construction one initially XORs a mask to every message block, where the

mask for the ith block is computed as τ i := γ i · L, where L is a (secret) random value,

and γ i is the i-th codeword of the Gray code. Our attack applies more generally to any

sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ).

As for NMAC, our first contribution is a simpler and uniform proof: If f is an ε-secure

PRF (against q queries) and a δ-non-adaptively secure PRF (against q queries), then

NMAC f is an (ε + `qδ)-secure PRF against q queries of length at most ` blocks each. We

also show that this ε + `qδ bound is basically tight by constructing an f for which an

attack with advantage `qδ exists.

Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and

Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows

for an information-theoretic analysis. We carry out such an analysis, obtaining a tight

`q 2 /2 c bound for this step, improving over the trivial bound of ` 2 q 2 /2 c .

Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s

that are k-wise independent, for k > 1 (the original has k = 1). We observe that the

security of PMAC will not increase in general if k = 2, and then prove that the security

increases to O(q 2 /2 n ), if the k = 4. Due to simple extension attacks, this is the best

bound one can hope for, using any distribution on the masks. Whether k = 3 is already

sufficient to get this level of security is left as an open problem.

There are no comments for this item.