thesis
(The exact security of) Message authentication codes
ISTA Thesis
published
Michal
Rybar
author 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
KrPi
department
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 i th 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. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC.
https://research-explorer.ista.ac.at/download/838/4799/IST-2017-828-v1+3_2017_Rybar_thesis.pdf
application/pdfno
https://research-explorer.ista.ac.at/download/838/6202/2017_Thesis_Rybar_source.zip
application/zip
Institute of Science and Technology Austria2017
eng
2663-337X10.15479/AT:ISTA:th_828
86
https://research-explorer.ista.ac.at/record/2082 https://research-explorer.ista.ac.at/record/6196
Rybar M. (The exact security of) Message authentication codes. 2017. doi:<a href="https://doi.org/10.15479/AT:ISTA:th_828">10.15479/AT:ISTA:th_828</a>
Rybar, M. (2017). <i>(The exact security of) Message authentication codes</i>. Institute of Science and Technology Austria. <a href="https://doi.org/10.15479/AT:ISTA:th_828">https://doi.org/10.15479/AT:ISTA:th_828</a>
Rybar, Michal. “(The Exact Security of) Message Authentication Codes.” Institute of Science and Technology Austria, 2017. <a href="https://doi.org/10.15479/AT:ISTA:th_828">https://doi.org/10.15479/AT:ISTA:th_828</a>.
Rybar, Michal. <i>(The Exact Security of) Message Authentication Codes</i>. Institute of Science and Technology Austria, 2017, doi:<a href="https://doi.org/10.15479/AT:ISTA:th_828">10.15479/AT:ISTA:th_828</a>.
M. Rybar, (The Exact Security of) Message Authentication Codes, Institute of Science and Technology Austria, 2017.
M. Rybar, “(The exact security of) Message authentication codes,” Institute of Science and Technology Austria, 2017.
Rybar M. 2017. (The exact security of) Message authentication codes. Institute of Science and Technology Austria.
8382018-12-11T11:48:46Z2023-09-07T12:02:28Z