An official website of the United States government
Motivated by the rise of quantum computers, existing public-key cryptosystems are expected to be replaced by post-quantum schemes in the next decade in billions of devices. To facilitate the transition, NIST is running a standardization process which is currently in its final Round. Only three digital signature schemes are left in the competition, among which Dilithium and Falcon are the ones based on lattices. Besides security and performance, significant attention has been given to resistance against implementation attacks that target side-channel leakage or fault injection response. Classical fault attacks on signature schemes make use of pairs of faulty and correct signatures to recover the secret key which only works on deterministic schemes. To counter such attacks, Dilithium offers a randomized version which makes each signature unique, even when signing identical messages. In this work, we introduce a novel Signature Correction Attack which not only applies to the deterministic version but also to the randomized version of Dilithium and is effective even on constant-time implementations using AVX2 instructions. The Signature Correction Attack exploits the mathematical structure of Dilithium to recover the secret key bits by using faulty signatures and the public-key. It can work for any fault mechanism which can induce single bit-flips. For demonstration, we are using Rowhammer induced faults. Thus, our attack does not require any physical access or special privileges, and hence could be also implemented on shared cloud servers. Using Rowhammer attack, we inject bit flips into the secret key s1 of Dilithium, which results in incorrect signatures being generated by the signing algorithm. Since we can find the correct signature using our Signature Correction algorithm, we can use the difference between the correct and incorrect signatures to infer the location and value of the flipped bit without needing a correct and faulty pair. To quantify the reduction in the security level, we perform a thorough classical and quantum security analysis of Dilithium and successfully recover 1,851 bits out of 3,072 bits of secret key $$s_{1}$$ for security level 2. Fully recovered bits are used to reduce the dimension of the lattice whereas partially recovered coefficients are used to to reduce the norm of the secret key coefficients. Further analysis for both primal and dual attacks shows that the lattice strength against quantum attackers is reduced from 2128 to 281 while the strength against classical attackers is reduced from 2141 to 289. Hence, the Signature Correction Attack may be employed to achieve a practical attack on Dilithium (security level 2) as proposed in Round 3 of the NIST post-quantum standardization process.
more »
« less
One-shot signatures and applications to hybrid quantum/classical authentication
We define the notion of one-shot signatures, which are signatures where any secret key can be used to sign only a single message, and then self-destructs. While such signatures are of course impossible classically, we construct one-shot signatures using quantum no-cloning. In particular, we show that such signatures exist relative to a classical oracle, which we can then heuristically obfuscate using known indistinguishability obfuscation schemes. We show that one-shot signatures have numerous applications for hybrid quantum/classical cryptographic tasks, where all communication is required to be classical, but local quantum operations are allowed. Applications include one-time signature tokens, quantum money with classical communication, decentralized blockchain-less cryptocurrency, signature schemes with unclonable secret keys, non-interactive certifiable min-entropy, and more. We thus position one-shot signatures as a powerful new building block for novel quantum cryptographic protocols.
more »
« less
- Award ID(s):
- 1749731
- PAR ID:
- 10164786
- Date Published:
- Journal Name:
- STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Secret-key distillation from quantum states and channels is a central task of interest in quantum information theory, as it facilitates private communication over a quantum network. Here, we study the task of secret-key distillation from bipartite states and point-to-point quantum channels using local operations and one-way classical communication (one-way LOCC). We employ the resource theory of unextendible entanglement to study the transformation of a bipartite state under one-way LOCC, and we obtain several efficiently computable upper bounds on the number of secret bits that can be distilled from a bipartite state using one-way LOCC channels; these findings apply not only in the one-shot setting but also in some restricted asymptotic settings. We extend our formalism to private communication over a quantum channel assisted by forward classical communication. We obtain efficiently computable upper bounds on the one-shot forward-assisted private capacity of a channel, thus addressing a question in the theory of quantum-secured communication that has been open for some time now. Our formalism also provides upper bounds on the rate of private communication when using a large number of channels in such a way that the error in the transmitted private data decreases exponentially with the number of channel uses. Moreover, our bounds can be computed using semidefinite programs, thus providing a computationally feasible method to understand the limits of private communication over a quantum network.more » « less
-
Chung, KM; Sasaki, Y (Ed.)We witness an increase in applications like cryptocurrency wallets, which involve users issuing signatures using private keys. To protect these keys from loss or compromise, users commonly outsource them to a custodial server. This creates a new point of failure, because compromise of such a server leaks the user’s key, and if user authentication is implemented with a password then this password becomes open to an offline dictionary attack (ODA). A better solution is to secret-share the key among a set of servers, possibly including user’s own device(s), and implement password authentication and signature computation using threshold cryptography. We propose a notion of augmented password-protected threshold signature (aptSIG) scheme which captures the best possible security level for this setting. Using standard threshold cryptography techniques, i.e. threshold password authentication and threshold signatures, one can guarantee that compromising up to t out of n servers reveals no information on either the key or the password. However, we extend this with a novel property, that compromising even all n servers also does not leak any information, except via an unavoidable ODA attack, which reveals the key only if the attacker guesses the password. We define aptSIG in the Universally Composable (UC) framework and show that it can be constructed very efficiently, using a black-box composition of any UC threshold signature [13] and a UC augmented Password-Protected Secret Sharing (aPPSS), which we define as an extension of prior notion of PPSS [30]. As concrete instantiations we obtain secure aptSIG schemes for ECDSA (in the case of t=n-1) and BLS signatures with very small overhead over the respective threshold signature. Finally, we note that both the notion and our generic solution for augmented password-protected threshold signatures can be generalized to password-protecting MPC for any keyed functions.more » « less
-
As post-quantum cryptography (PQC) nears standardization and eventual deployment, it is increasingly important to understand the security of the implementations of selected schemes. In this paper, we conduct such an investigation, uncovering concerning findings about many of the finalists of the NIST PQC standardization competition. Specifically, we show Rowhammer-based attacks on the Kyber and BIKE Key Exchange Mechanisms and the Dilithium Digital Signature scheme that enable complete recovery of the secret key with only a moderate amount of effort – no supercomputers, or months of precomputation. Moreover, we experimentally carry out our attacks using a combination of Rowhammer, performance degradation, and memory massaging techniques, showing that our attacks are practically feasible. Our results show that such side-channel based attacks are a critical concern and need to be considered when new cryptographic schemes are standardized, when standard implementations are developed, and when instances are deployed. We conclude with recommendations on implementation techniques that harden cryptographic schemes against Rowhammer attacks.more » « less
-
Bhasin, Shivam; Chattopadhyay, Anupam; Güneysu, Tim; Bhunia, Swarup (Ed.)Digital signature algorithms are the foundation of many secure communication protocols, including those used in Internet of Things (IoT) applications. While the current generation of signature schemes is secure against classical attacks, they are potentially vulnerable to attacks using quantum computers. Because of this threat, multiple new schemes have been developed and evaluated in recent years. From among these schemes, the National Institute of Standards and Technology standardized two and selected additional three for near-term standardization. For use in IoT, these schemes must be sufficiently efficient in terms of their public-key and signature sizes and the timing of major operations. In this paper, we analyze the choice between two primary schemes considered for extensive use in IoT, CRYSTALS-Dilithium and FALCON, from the point of view of developing efficient hardware accelerators supporting cryptographic operations performed by IoT clients and servers.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/https://doi.org/10.1145/3357713.3384304
