Paper 2018/520
Bernstein Bound on WCS is Tight  Repairing LuykxPreneel Optimal Forgeries
Mridul Nandi
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 least $\frac{1}{2}$ based 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.
Note: ..
Metadata
 Available format(s)
 Publication info
 A minor revision of an IACR publication in CRYPTO 2018
 Keywords
 AuthenticatorWCSGCMPolynomial hashAXUkey recoveryforgery.
 Contact author(s)
 mridul nandi @ gmail com
 History
 20180606: last of 3 revisions
 20180604: received
 See all versions
 Short URL
 https://ia.cr/2018/520
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/520, author = {Mridul Nandi}, title = {Bernstein Bound on WCS is Tight  Repairing LuykxPreneel Optimal Forgeries}, howpublished = {Cryptology ePrint Archive, Paper 2018/520}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/520}}, url = {https://eprint.iacr.org/2018/520} }