Algebraic Side-Channel Attack against ECDSA Employing Table-based Scalar Multiplication
-
Sunghyun Jin (진성현, 정보보호대학원 정보보호학과)
- 주제(키워드) Side-Channel Analysis , Public-Key Cryptography , Elliptic Curve Cryptography , Digital Signature , ECDSA
- 발행기관 고려대학교 정보보호대학원
- 지도교수 홍석희
- 발행년도 2022
- 학위수여년월 2022. 8
- 학위명 박사
- 학과 및 전공 정보보호대학원 정보보호학과
- 세부분야 해당없음
- 원문페이지 124 p
- 실제URI http://www.dcollection.net/handler/korea/000000269348
- UCI I804:11009-000000269348
- DOI 10.23186/korea.000000269348.11009.0001392
- 본문언어 영어
초록/요약
ECDSA is a representative digital signature and is employed in many systems for providing security mechanisms such as integrity and authentication. Because ECDSA is implemented and operated on the semiconductor devices, it is vulnerable to SCA attacks. Out of many SCA countermeasure approaches, it is known that regular table-based scalar multiplication with appropriate window width and scalar recording provides the efficiency and practical security for ECDSA signature generation due to the infeasibility of remaining brute force on finding which table entry was used. Thus, regular table-based scalar multiplication methods are employed in many cryptographic libraries such as OpenSSL, Mbed TLS, Bouncy Castle. In this thesis, we propose a novel algebraic side-channel key recovery attack on secure ECDSA implementations, which employing regular table-based scalar multiplication, by exploiting side-channel collisions between unknown entries and then also propose how the attack's efficiency can be enhanced significantly by compressing the collision information. Because nonce and the result of scalar multiplication over it have a 1-to-1 correspondence and table-based scalar multiplication load entries from the pre-computed table and accumulate it on the result, the collision information represents direct information on the relation between nonces by the nature of table-based scalar multiplication. We propose how the collision information be used to find the linear combination of nonces resulting in zero and how the private key can be recovered from the result. Furthermore, we show that the entries can be recovered if sufficient traces are given. Our attack has a strength in the applicability even in which table entries are unknown. We explore the properties and the related issues of the our attacks from a theoretical view to a practical view. Especially, we provide the practical experimental results with the details for reproducibility. All results of this thesis imply that our attack is a real and significant threat against ECDSA signature generation employing table-based scalar multiplication.
more목차
Abstract i
Acknowledge iii
Contents v
1 Introduction 1
1.1 Motivation 3
1.2 Contributions 3
1.3 Thesis Organization 7
2 Preliminaries 9
2.1 ECDSA 10
2.2 Overview of Side-Channel Analysis against ECDSA 13
2.3 Table-based Scalar Multiplication 27
3 Algebraic Side-Channel Attack against ECDSA 31
3.1 Algebraic Side-Channel Key Recovery Attack 33
3.2 Practical Applications: Case Studies 39
3.3 Experimental Result 49
3.4 Discussions 59
4 Enhancing the Efficiency of Algebraic Side-Channel Attack against ECDSA 63
4.1 Enhanced Algebraic Side-Channel Key Recovery Attack 65
4.2 Practical Applications: Case Studies 67
4.3 Experimental Result 71
4.4 Discussions 85
5 Conclusions 87
Bibliography 91
List of Figures 111
List of Tables 115
List of Algorithms 117
List of Abbreviations 119
