Cryptology ePrint Archive: Report 2020/971

QuantumHammer: A Practical Hybrid Attack on the LUOV Signature Scheme

Koksal Mus and Saad Islam and Berk Sunar

Abstract: Post-quantum schemes are expected to replace existing public-key schemes within a decade in billions of devices. To facilitate the transition, the US National Institute for Standards and Technology (NIST) is running a standardization process. Multivariate signatures is one of the main categories in NIST's post-quantum cryptography competition. Among the four candidates in this category, the LUOV and Rainbow schemes are based on the Oil and Vinegar scheme, first introduced in 1997 which has withstood over two decades of cryptanalysis. Beyond mathematical security and efficiency, security against side-channel attacks is a major concern in the competition. The current sentiment is that post-quantum schemes may be more resistant to fault-injection attacks due to their large key sizes and the lack of algebraic structure. We show that this is not true.

We introduce a novel hybrid attack, QuantumHammer, and demonstrate it on the constant-time implementation of LUOV currently in Round 2 of the NIST post-quantum competition. The QuantumHammer attack is a combination of two attacks, a bit-tracing attack enabled via Rowhammer fault injection and a divide and conquer attack that uses bit-tracing as an oracle. Using bit-tracing, an attacker with access to faulty signatures collected using Rowhammer attack, can recover secret key bits albeit slowly. We employ a divide and conquer attack which exploits the structure in the key generation part of LUOV and solves the system of equations for the secret key more efficiently with few key bits recovered via bit-tracing.

We have demonstrated the first successful in-the-wild attack on LUOV recovering all 11K key bits with less than 4 hours of an active Rowhammer attack. The post-processing part is highly parallel and thus can be trivially sped up using modest resources. QuantumHammer does not make any unrealistic assumptions, only requires software co-location (no physical access), and therefore can be used to target shared cloud servers or in other sandboxed environments.

Category / Keywords: public-key cryptography / Rowhammer attack, fault attacks, post-quantum cryptography, multivariate cryptography, algebraic attack

Original Publication (with minor differences): CCS '20
DOI:
10.1145/3372297.3417272

Date: received 8 Aug 2020, last revised 17 Aug 2020

Contact author: koksalmus at gmail com

Available format(s): PDF | BibTeX Citation

Note: Doi is updated.

Version: 20200818:082316 (All versions of this report)

Short URL: ia.cr/2020/971


[ Cryptology ePrint archive ]