Welcome to the resource topic for 2018/520
Title:
Bernstein Bound on WCS is Tight - Repairing Luykx-Preneel Optimal Forgeries
Authors: 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.
ePrint: https://eprint.iacr.org/2018/520
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .