CryptoDB
Bernstein Bound on WCS is Tight
| Authors: | |
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2018 |
| 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 leastbased 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. |
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28839,
title={Bernstein Bound on WCS is Tight},
booktitle={Advances in Cryptology – CRYPTO 2018},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={10992},
pages={213-238},
doi={10.1007/978-3-319-96881-0_8},
author={Mridul Nandi},
year=2018
}