CryptoDB
Bernstein Bound on WCS is Tight
Authors:  

Download: 

Presentation:  Slides 
Conference:  CRYPTO 2018 
Abstract:  In Eurocrypt 2018, Luykx and Preneel described hashkeyrecovery and forgery attacks against polynomial hash based WegmanCarterShoup (WCS) authenticators. Their attacks require $$2^{n/2}$$ messagetag pairs and recover hashkey with probability about $$1.34\, \times \, 2^{n}$$ where n is the bitsize of the hashkey. Bernstein in Eurocrypt 2005 had provided an upper bound (known as Bernstein bound) of the maximum forgery advantages. The bound says that all adversaries making $$O(2^{n/2})$$ queries of WCS can have maximum forgery advantage $$O(2^{n})$$ . So, Luykx and Preneel essentially analyze WCS in a range of query complexities where WCS is known to be perfectly secure. Here we revisit the bound and found that WCS remains secure against all adversaries making $$q \ll \sqrt{n} \times 2^{n/2}$$ queries. So it would be meaningful to analyze adversaries with beyond birthday bound complexities.In this paper, we show that the Bernstein bound is tight by describing two attacks (one in the “chosenplaintext model” and other in the “knownplaintext model”) which recover the hashkey (hence forges) with probability at leastbased on $$\sqrt{n} \times 2^{n/2}$$ messagetag pairs. We also extend the forgery adversary to the Galois Counter Mode (or GCM). More precisely, we recover the hashkey of GCM with probability at least $$\frac{1}{2}$$ based on only $$\sqrt{\frac{n}{\ell }} \times 2^{n/2}$$ encryption queries, where $$\ell $$ is the number of blocks present in encryption queries. 
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto201828839, title={Bernstein Bound on WCS is Tight}, booktitle={Advances in Cryptology – CRYPTO 2018}, series={Lecture Notes in Computer Science}, publisher={Springer}, volume={10992}, pages={213238}, doi={10.1007/9783319968810_8}, author={Mridul Nandi}, year=2018 }