Normal view MARC view ISBD view

(The exact security of) Message Authentication Codes

By: Rybar, Michal.
Material type: materialTypeLabelBookPublisher: IST Austria 2017
Contents:
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
Summary: 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.
List(s) this item appears in: IST Austria Thesis 2018
Tags from this library: No tags from this library for this title. Log in to add tags.
    average rating: 0.0 (0 votes)
Item type Current location Call number Status Date due Barcode Item holds
Book Book Library
Available AT-ISTA#001526
Total holds: 0

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.

Log in to your account to post a comment.

Powered by Koha

//