Montgomery Ladder 멱승 알고리듬에 대한 입력 충돌 기반 상관 전력분석 공격 및 대응 빙산

Input Collision-Based Correlation Power Analysis attack on Montgomery Ladder Exponentiation Algorithm and its Countermeasure

최근 RSA와 같은 공개 키 암호 시스템에 사용되는 멱승(exponentiation)알고리듬을 암호용 디바이스에 구현시 누설되는 소비 전력 정보를 이용하여 비밀 키를 찾아낼 수 있는 부채널 공격들이 등장하게 되었다. 또한, 멱승 연산에 사용되는 두 번의 모듈러 곱셈에서 입력이 동일한 경우 상관 전력 분석 공격을 통해 비밀 키를 추출하는 공격이 제안되기도 하였다. 본 논문에서는 Montgomery Ladder 멱승 알고리듬이 입력 충돌에 기반한 전력 분석 공격에 의해 비밀 키를 누설할 수 있음을 보이고 대응책을 제안한다. 제안 방식에서는 하나의 입력을 갖는 자승 연산을 서로 다른 두 입력을 갖는 곱셈 연산으로 대체함으로써 입력 충돌을 회피하도록 알고리듬을 설계하였다.

R ecently, m any pow er analysis attacks on cryptograpm c devices were presented in order to recover a secret key using leakage pow er consum ption info rm atio n w m ch is occurred in case o f naive im plem entatio n o f exponentiation algorithm used in p u b lic key cryptosystem such as R S A . In ad d itio n, a new correlation pow er analysis attack, w hich can ap p lied w hen the inputs o f tw o m o d ular m u ltip lica tio n s are sam e, is proposed in order to retrieve the secret key. In this paper, w e fin d o ut that the M ontgom ery Ladder exponentiation alg o rith m is vulnerable to the in p u t collision-based C P A (C o rrelation Pow er A naly sis) attack and propose a new counterm easure to resist this attack. The core idea o f o ur m ethod is based o n the fact that the squaring w ith one in p u t can be replaced the m u ltip lic a tio n w ith tw o d ifferent inputs.