Paper 2018/1201
Subversion in Practice: How to Efficiently Undermine Signatures
Joonsang Baek, Willy Susilo, Jongkil Kim, and Yang-Wai Chow
Abstract
Algorithm substitution attack (ASA) on signatures should be treated seriously as the authentication services of numerous systems and applications rely on signature schemes and compromising them has a significant impact on the security of users. We present a somewhat alarming result in this regard: a highly efficient ASA on the Digital Signature Algorithm (DSA) and its implementation. Compared with the generic ASAs on signature schemes proposed in the literature, our attack provides fast and undetectable subversion, which will extract the user's private signing key by collecting maximum three signatures arbitrarily. Moreover, our ASA is proven to be robust against state reset. We implemented the proposed ASA by replacing the original DSA in Libgcrypt (a popular cryptographic library used in many applications) with our subverted DSA. Experiment shows that the user's private key can readily be recovered once the subverted DSA is used to sign messages. In our implementation, various measures have been considered to significantly reduce the possibility of detection through comparing the running time of the original DSA and the subverted one (i.e. timing analysis). To our knowledge, this is the first implementation of ASA in practice, which shows that ASA is a real threat rather than only a theoretical speculation.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- cryptanalysisdigital signaturesimplementation
- Contact author(s)
- baek @ uow edu au
- History
- 2018-12-18: received
- Short URL
- https://ia.cr/2018/1201
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/1201, author = {Joonsang Baek and Willy Susilo and Jongkil Kim and Yang-Wai Chow}, title = {Subversion in Practice: How to Efficiently Undermine Signatures}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/1201}, year = {2018}, url = {https://eprint.iacr.org/2018/1201} }