Paper 2019/435

A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope

Yue Qin, Chi Cheng, and Jintai Ding

Abstract

In CT-RSA 2019, Bauer et al. have analyzed the case when the public key is reused for the NewHope key encapsulation mechanism (KEM), a second-round candidate in the NIST Post-quantum Standard process. They proposed an elegant method to recover coefficients ranging from -6 to 4 in the secret key. We repeat their experiments but there are two fundamental problems. First, even for coefficients in [-6,4] we cannot recover at least 262 of them in each secret key with 1024 coefficients. Second, for the coefficient outside [-6,4], they suggested an exhaustive search. But for each secret key on average there are 10 coefficients that need to be exhaustively searched, and each of them has 6 possibilities. This makes Bauer et al.'s method highly inefficient. We propose an improved method, which with 99.22% probability can recover all the elements ranging from -6 to 4 in the secret key. Then, inspired by Ding et al.'s key mismatch attack, we propose an efficient strategy which with a probability of 96.88% succeeds in recovering all the coefficients in the secret key. Experiments show that our proposed method is very efficient, which completes the attack in about 137.56 ms using the NewHope parameters.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ESORICS 2019
DOI
10.1007/978-3-030-29962-0_24
Keywords
Post-quantum cryptographyKey exchangeRing learning with errorsKey mismatch attack
Contact author(s)
chengchi @ cug edu cn
History
2020-06-21: last of 4 revisions
2019-04-29: received
See all versions
Short URL
https://ia.cr/2019/435
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/435,
      author = {Yue Qin and Chi Cheng and Jintai Ding},
      title = {A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope},
      howpublished = {Cryptology ePrint Archive, Paper 2019/435},
      year = {2019},
      doi = {10.1007/978-3-030-29962-0_24},
      note = {\url{https://eprint.iacr.org/2019/435}},
      url = {https://eprint.iacr.org/2019/435}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.