Paper 2017/436

A Uniform Class of Weak Keys for Universal Hash Functions

Kaiyan Zheng and Peng Wang

Abstract

In this paper we investigate weak keys of universal hash functions (UHFs) from their combinatorial properties. We find that any UHF has a general class of keys, which makes the combinatorial properties totally disappear, and even compromises the security of the UHF-based schemes, such as the Wegman-Carter scheme, the UHF-then-PRF scheme, etc. By this class of keys, we actually get a general method to search weak-key classes of UHFs, which is able to derive all previous weak-key classes of UHFs found by intuition or experience. Moreover we give a weak-key class of the BRW polynomial function which was once believed to have no weak-key issue, and exploit such weak keys to implement a distinguish attack and a forgery attack against DTC - a BRW-based authentication encryption scheme. Furthermore in Grain-128a, with the linear structure revealed by weak-key classes of its UHF, we can recover any first $(32+b)$ bits of the UHF key, spending no more than $1$ encryption and $(2^{32} + b)$ decryption queries.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Universal hash functionweak keyWegman-Carter schemeauthenticated encryptionBRW polynomialsGrain-128a
Contact author(s)
zhengkaiyan @ iie ac cn
wp @ is ac cn
History
2017-05-22: received
Short URL
https://ia.cr/2017/436
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/436,
      author = {Kaiyan Zheng and Peng Wang},
      title = {A Uniform Class of Weak Keys for Universal Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/436},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/436}},
      url = {https://eprint.iacr.org/2017/436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.