---
_id: '6196'
abstract:
- lang: eng
  text: PMAC is a simple and parallel block-cipher mode of operation, which was introduced
    by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random
    permutation over n-bit strings, PMAC constitutes a provably secure variable input-length
    (pseudo)random function. For adversaries making q queries, each of length at most
    l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an
    upper bound on the distinguishing advantage of  Ο(σ2/2n), while the currently
    best bound is  Ο (qσ/2n).In this work we show that this bound is tight by giving
    an attack with advantage Ω (q2l/2n). 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(2n). We then investigate if the security
    of PMAC can be further improved by using τi’s that are k-wise independent, for
    k > 1 (the original distribution is only 1-wise independent). We observe that
    the security of PMAC will not increase in general, even if the masks are chosen
    from a 2-wise independent distribution, and then prove that the security increases
    to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks,
    this is the best bound one can hope for, using any distribution on the masks.
    Whether 3-wise independence is already sufficient to get this level of security
    is left as an open problem.
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: Michal
  full_name: Rybar, Michal
  id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
  last_name: Rybar
citation:
  ama: Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. <i>IACR Transactions
    on Symmetric Cryptology</i>. 2017;2016(2):145-161. doi:<a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">10.13154/TOSC.V2016.I2.145-161</a>
  apa: Gazi, P., Pietrzak, K. Z., &#38; Rybar, M. (2017). The exact security of PMAC.
    <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum. <a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>
  chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security
    of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum,
    2017. <a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>.
  ieee: P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” <i>IACR
    Transactions on Symmetric Cryptology</i>, vol. 2016, no. 2. Ruhr University Bochum,
    pp. 145–161, 2017.
  ista: Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions
    on Symmetric Cryptology. 2016(2), 145–161.
  mla: Gazi, Peter, et al. “The Exact Security of PMAC.” <i>IACR Transactions on Symmetric
    Cryptology</i>, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:<a
    href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">10.13154/TOSC.V2016.I2.145-161</a>.
  short: P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology
    2016 (2017) 145–161.
date_created: 2019-04-04T13:48:23Z
date_published: 2017-02-03T00:00:00Z
date_updated: 2023-09-07T12:02:27Z
day: '03'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.13154/TOSC.V2016.I2.145-161
ec_funded: 1
file:
- access_level: open_access
  checksum: f23161d685dd957ae8d7274132999684
  content_type: application/pdf
  creator: dernst
  date_created: 2019-04-04T13:53:58Z
  date_updated: 2020-07-14T12:47:24Z
  file_id: '6197'
  file_name: 2017_IACR_Gazi.pdf
  file_size: 597335
  relation: main_file
file_date_updated: 2020-07-14T12:47:24Z
has_accepted_license: '1'
intvolume: '      2016'
issue: '2'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 145-161
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: IACR Transactions on Symmetric Cryptology
publication_identifier:
  eissn:
  - 2519-173X
publication_status: published
publisher: Ruhr University Bochum
quality_controlled: '1'
related_material:
  record:
  - id: '838'
    relation: dissertation_contains
    status: public
status: public
title: The exact security of PMAC
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 2016
year: '2017'
...