--- _id: '1654' abstract: - lang: eng text: "HMAC and its variant NMAC are the most popular approaches to deriving a MAC (and more generally, a PRF) from a cryptographic hash function. Despite nearly two decades of research, their exact security still remains far from understood in many different contexts. Indeed, recent works have re-surfaced interest for {\\em generic} attacks, i.e., attacks that treat the compression function of the underlying hash function as a black box.\r\n\r\nGeneric security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question.\r\n\r\nIn this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing.\r\n\r\nWhile our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions. " alternative_title: - LNCS author: - first_name: Peter full_name: Gazi, Peter id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87 last_name: Gazi - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Stefano full_name: Tessaro, Stefano last_name: Tessaro citation: ama: Gazi P, Pietrzak KZ, Tessaro S. Generic security of NMAC and HMAC with input whitening. 2015;9453:85-109. doi:10.1007/978-3-662-48800-3_4 apa: 'Gazi, P., Pietrzak, K. Z., & Tessaro, S. (2015). Generic security of NMAC and HMAC with input whitening. Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Auckland, New Zealand: Springer. https://doi.org/10.1007/978-3-662-48800-3_4' chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “Generic Security of NMAC and HMAC with Input Whitening.” Lecture Notes in Computer Science. Springer, 2015. https://doi.org/10.1007/978-3-662-48800-3_4. ieee: P. Gazi, K. Z. Pietrzak, and S. Tessaro, “Generic security of NMAC and HMAC with input whitening,” vol. 9453. Springer, pp. 85–109, 2015. ista: Gazi P, Pietrzak KZ, Tessaro S. 2015. Generic security of NMAC and HMAC with input whitening. 9453, 85–109. mla: Gazi, Peter, et al. Generic Security of NMAC and HMAC with Input Whitening. Vol. 9453, Springer, 2015, pp. 85–109, doi:10.1007/978-3-662-48800-3_4. short: P. Gazi, K.Z. Pietrzak, S. Tessaro, 9453 (2015) 85–109. conference: end_date: 2015-12-03 location: Auckland, New Zealand name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security' start_date: 2015-11-29 date_created: 2018-12-11T11:53:17Z date_published: 2015-12-30T00:00:00Z date_updated: 2021-01-12T06:52:16Z day: '30' ddc: - '004' - '005' department: - _id: KrPi doi: 10.1007/978-3-662-48800-3_4 ec_funded: 1 file: - access_level: open_access checksum: d1e53203db2d8573a560995ccdffac62 content_type: application/pdf creator: system date_created: 2018-12-12T10:09:09Z date_updated: 2020-07-14T12:45:08Z file_id: '4732' file_name: IST-2016-676-v1+1_881.pdf file_size: 512071 relation: main_file file_date_updated: 2020-07-14T12:45:08Z has_accepted_license: '1' intvolume: ' 9453' language: - iso: eng month: '12' oa: 1 oa_version: Submitted Version page: 85 - 109 project: - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication_status: published publisher: Springer publist_id: '5496' pubrep_id: '676' quality_controlled: '1' scopus_import: 1 series_title: Lecture Notes in Computer Science status: public title: Generic security of NMAC and HMAC with input whitening type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9453 year: '2015' ...