부채널 공격에 안전한 전자서명 알고리즘 연구

국문 초록 (Abstract)

부채널 공격은 수학적으로 증명된 암호 알고리즘의 안전성을 손상시킬 수 있는 강력한 기술이다. 본 논문에서는 국제 표준 디지털 서명 알고리즘인 DSA(Digital Signature Algorithm)에 대한 부채널 공격 방법과 기존 대응 방법 중 가장 안전한 Kim 등이 제안한 알고리즘을 분석 하였다. 또한, Kim 등이 제안한 알고리즘의 문제점을 개선하여 안전성은 높이고 연산량은 줄이는 새로운 DSA 서명 알고리즘을 제안한다. Kim 등이 제안한 알고리즘은 모든 오류 주입 공격에 안전하지만 전력 분석 공격에 대해서는 고려되지 않았으며, 연산량이 크다는 단점이 있다. 본 논문에서 제안하는 알고리즘은 난수 2개를 사용하여 Kim 등의 대응 방법과 유사하지만, 기존 알고리즘과 달리 서명 연산 중 비밀키 값이 난수와의 곱셈으로 수행되기 때문에 오류 주입 공격뿐만 아니라 전력 분석 공격에도 안전하며, 연산 효율은 약 34% 향상 되었다.

다국어 초록 (Multilingual Abstract)

Side channel attack is a powerful technique that can threaten the security of mathematically proven cryptographic algorithms. In this paper, side channel attack methods for DSA(Digital Signature Algorithm) and an algorithm proposed by Kim, the safest among existing countermeasures, were analyzed. In addition, a new DSA signature algorithm was proposed that increases safety and computational efficiency by improving the problems of Kim’s algorithm. The Kim’s algorithm is secure against all fault injection attacks, but it’s not considered for power analysis attacks and requires a lot of computation. The new algorithm proposed in this paper is similar to the Kim’s algorithm by using two nonce, but it’s secure against not only fault injection attacks but also power analysis attacks, because secret key is multiplied by a nonce and used to generate the signature. Also, the computational efficiency was improved by about 34% compared to the Kim’s algorithm.

목차 (Table of Contents)

• 요약
• ABSTRACT
• Ⅰ. 서론
• Ⅱ. DSA 알고리즘의 부채널 공격 및 기존 대응 방법 분석
• Ⅲ. 제안하는 DSA 서명 알고리즘
• Ⅳ. 결론
• References

참고문헌 (Reference)

1 정철조, "오류주입을 이용한 DSA 서명 알고리즘 공격 및 대응책" 한국산학기술학회 11 (11): 3045-3052, 2010

2 김태원, "오류 주입 공격에 안전한 전자서명 대응법" 한국정보보호학회 22 (22): 515-524, 2012

3 P. Kocher, "Timing Attacks on Implementations of DiffieHellman, RSA, DSS,and Others Systems" CRYPTO 1109 : 104-111, 1996

4 P. Nguyen, "The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces" 30 (30): 201-217, 2003

5 M. Bellare, "Pseudo-Random Number Generation Within Cryptographic Algorithms : The DDS Case" 277-291, 1997

6 T. Messerges, "Power Analysis Attacks and Countermeasures for Cryptographic Algorithms" Univ. of Illinois at Chicago 2000

7 D. Boneh, "On the Importance of Checking Cryptographic Protocols for Faults" EUROCRYPT 1233 : 37-51, 1997

8 J. Coron, "On Boolean and Arithmetic Masking against Differential Power Analysis" 231-237, 2000

9 "National institute of standards and technology"

10 "NIST CAVP: FIPS 186-2 DSA CAVS"

11 P. Nguyen, "Lattice Reduction in Cryptology: An Update" 85-112, 2000

12 P. Kocher, "Introduction to differential power analysis and related attacks"

13 C. Giraud, "Fault Attacks on Signature Schemes" ACISP 3108 : 478-491, 2004

14 D. Naccache, "Experimenting with Faults, Lattices and the DSA" PKC 3386 : 16-28, 2005

15 M. Nikodem, "Error Prevention, Detection and Diffusion Algorithms for Cryptographic Hardware" 127-134, 2007

16 C.P. Schnorr, "Efficient Identification and Signatures for Smart cards" 239-251, 2001

17 M. Nikodem, "DSA Signature Scheme Immune to the Fault Cryptanalysis" CARDIS 5189 : 61-73, 2008

18 F. Bao, "Breaking Public Key Cryptosystems on Tamper Resistant Devices in the Presence of Transient Faults" 115-124, 1997

19 J. Schmidt, "A Fault Attack on ECDSA" 93-99, 2009