Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Universal hash function, weak key, Wegman-Carter scheme, authenticated encryption, BRW polynomials, Grain-128a

Date: received 20 May 2017

Contact author: zhengkaiyan at iie ac cn, wp@is ac cn

Available format(s): PDF | BibTeX Citation

Version: 20170522:215229 (All versions of this report)

Short URL: ia.cr/2017/436

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]