IACR News item: 23 December 2015
Mohamed Ahmed Abdelraheem, Peter Beelen, Andrey Bogdanov, Elmar Tischhauser
ePrint Report
Polynomial hashing as an instantiation of universal hashing
is a widely employed method for the construction of MACs and authenticated
encryption (AE) schemes, the ubiquitous GCM being a prominent
example. It is also used in recent AE proposals within the CAESAR competition
which aim at providing nonce misuse resistance, such as POET.
The algebraic structure of polynomial hashing has given rise to security
concerns: At CRYPTO 2008, Handschuh and Preneel describe key recovery
attacks, and at FSE 2013, Procter and Cid provide a comprehensive
framework for forgery attacks. Both approaches rely heavily on the ability
to construct forgery polynomials having disjoint sets of roots, with
many roots (\weak keys") each. Constructing such polynomials beyond
nave approaches is crucial for these attacks, but still an open problem.
In this paper, we comprehensively address this issue. We propose to
use twisted polynomials from Ore rings as forgery polynomials. We show
how to construct sparse forgery polynomials with full control over the
sets of roots. We also achieve complete and explicit disjoint coverage of
the key space by these polynomials. We furthermore leverage this new
construction in an improved key recovery algorithm.
As cryptanalytic applications of our twisted polynomials, we develop the
rst universal forgery attacks on GCM in the weak-key model that do
not require nonce reuse. Moreover, we present universal weak-key forgery
attacks for the recently proposed nonce-misuse resistant AE schemes
POET, Julius, and COBRA.
Additional news items may be found on the IACR news page.