Breaking HK17 in Practice

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(p8) 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( { 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( { p} ) bit operations to establish the shared key. We break HK17 completely in the practical sense. - 2019 IEEE.