Another Look at Tightness

Sanjit Chatterjee; Alfred Menezes; Palash Sarkar

Paper 2011/442

Another Look at Tightness

Sanjit Chatterjee, Alfred Menezes, and Palash Sarkar

Abstract

We examine a natural, but non-tight, reductionist security proof for deterministic message authentication code (MAC) schemes in the multi-user setting. If security parameters for the MAC scheme are selected without accounting for the non-tightness in the reduction, then the MAC scheme is shown to provide a level of security that is less than desirable in the multi-user setting. We find similar deficiencies in the security assurances provided by non-tight proofs when we analyze some protocols in the literature including ones for network authentication and aggregate MACs. Our observations call into question the practical value of non-tight reductionist security proofs. We also exhibit attacks on authenticated encryption and disk encryption schemes in the multi-user setting.

Note: Removed some inaccuracies in the description and analysis of Attack 1.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Also available at http://anotherlook.ca
Contact author(s): ajmeneze @ uwaterloo ca
History: 2013-04-01: last of 7 revisions; 2011-08-15: received; See all versions
Short URL: https://ia.cr/2011/442
License: CC BY

BibTeX

@misc{cryptoeprint:2011/442,
      author = {Sanjit Chatterjee and Alfred Menezes and Palash Sarkar},
      title = {Another Look at Tightness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/442},
      year = {2011},
      url = {https://eprint.iacr.org/2011/442}
}