Technical Program

Paper Detail

Paper Title Breaking HK17 in Practice
Paper IdentifierTH1.R7.2
Authors Haoyu Li, Academy of Mathematics and Systems Science, Chinese Academy of Sicences; State Key Laboratory of Cryptology; University of Chinese Academy of Sciences, China; Renzhang Liu, Westone Information Industry INC, China; Qutaibah M. Malluhi, Qatar University, Qatar; Yanbin Pan, Academy of Mathematics and Systems Science, Chinese Academy of Sciences; University of Chinese Academy of Sciences, China; Yongge Wang, University of North Carolina at Charlotte, United States; Tianyuan Xie, Academy of Mathematics and Systems Science, Chinese Academy of Sciences; University of Chinese Academy of Sciences, China
Session Post-Quantum Cryptography I
Location Bièvre, Level 5
Session Time Thursday, 11 July, 09:50 - 11:10
Presentation Time Thursday, 11 July, 10:10 - 10:30
Manuscript  Click here to download the manuscript
Abstract In November 2017, Hecht and Kamlofsky submitted HK17, a quaternion(octonion)-based Diffie-Hellman key exchange protocol, to NIST post-quantum cryptography project, and thought that at least O(p^8) arithmetic operations are needed for a passive adversary to recover the shared key where p is the modulo used in the scheme. Later, Bernstein and Lange pointed out that the shared key can be recovered with O(p) arithmetic operations, which implies that HK17 with small p is not secure. However, their attack does not work in practice for the scheme with sufficiently large p, although the scheme is still efficient. In this paper, we propose an attack to show that just constant arithmetic operations, or \tilde{O}(\log{p}) bit operations, are enough to recover the shared key for a passive adversary. Note that even the legal party in the protocol needs at least \tilde{O}(\log{p}) bit operations to establish the shared key. We break HK17 completely in the practical sense.