Paper 2018/520
Bernstein Bound on WCS is Tight - Repairing Luykx-Preneel Optimal Forgeries
Mridul Nandi
Abstract
In Eurocrypt 2018, Luykx and Preneel described hash-key-recovery and forgery attacks against polynomial hash based Wegman-Carter-Shoup (WCS) authenticators. Their attacks require $2^{n/2}$ message-tag pairs and recover hash-key with probability about $1.34 \times 2^{-n}$ where $n$ is the bit-size of the hash-key. 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 ``chosen-plaintext model" and other in the ``known-plaintext model") which recover the hash-key (hence forges) with probability at least $\frac{1}{2}$ based on $\sqrt{n} \times 2^{n/2}$ message-tag pairs. We also extend the forgery adversary to the Galois Counter Mode (or GCM). More precisely, we recover the hash-key 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
- 2018-06-06: last of 3 revisions
- 2018-06-04: 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 Luykx-Preneel Optimal Forgeries}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/520}, year = {2018}, url = {https://eprint.iacr.org/2018/520} }