A Closer Look at HMAC.
Krzysztof Pietrzak · 2013
Abstract. Bellare, Canetti and Krawczyk [BCK96] show that cascading an ε-secure (fixed input length) PRF gives an O(εnq)-secure (variable input length) PRF when making at most q prefix-free queries of length n blocks. We observe that this translates to the same bound for NMAC (which is the cascade without the prefix-free requirement but an additional application of the PRF at the end), and give a matching attack, showing this bound is tight. This contradicts the O(εn) bound claimed by Koblitz and Menezes [KM12]. Definitions. For a keyed function F: {0, 1} c × {0, 1} b → {0, 1} c we denote with cascF: {0, 1} 2c ×{0, 1} b ∗ → {0, 1} c (where {0, 1} b ∗ = ⋃ z∈N {0, 1}bz) the cascade (aka. Merkle-Damg˚ard) construction build from F as casc F (k, m1 ‖... ‖mn) = yn where y0 = k and for i ≥ 1: yi = F(yi−1, mi) nmac F is casc F with an additional application of F at the end (using some padding if b> c). nmac F ((k1, k2), M) = F(k2, casc F (k1, M)) A variable input length function G: {0, 1} 2c × {0, 1} b ∗ → {0, 1} c is a (ε, t, q, n)-secure PRF (for fixed input length functions we omit the parameter n) if for any adversary A of size t, making q queries, each of length at most n (in b-bit blocks) and R denoting a uniformly random function with the same domain