ECDSA 서명 생성에 대한 격자 기반 공격 방법의 비교
Comparative Study on Lattice-Based CryptoAttacks against ECDSA Signature Generation
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
ECDSA 서명 생성에 사용되는 난수(nonce)의 랜덤성에 문제가 생기면 ECDSA의 안전성은 심각하게 훼손될 수 있다. 예를 들어 서로 다른 서명 생성에 동일한 난수가 사용되면 ECDSA의 개인키는 쉽게 복구된다. 또한 여러 가지 이유로 난수의 일부가 공개되거나 난수 확률 분포에 편향이 생기면 ECDSA의 안전성에 심각한 문제가 발생할 수 있음이 알려져 있으며 이 때 격자 기반 암호 분석 방법이 자주 사용된다. 격자 기반 암호 분석 방법은 암호시스템의 안전성과 관련된 문제를 격자의 최소 벡터나 최근접 벡터를 찾는 문제로 변환한 후 LLL, BKZ 등의 알고리즘을 사용하여 해당 문제를 해결하며, 대표적으로 HNP와 Howgrave-Graham 방법 등이 제안되었다. 하지만 HNP와 Howgrave-Graham 방법은 격자를 사용한다는 공통점에도 불구하고 그 적용 방식이 다르며, 따라서 직접적인 성능 비교가 쉽지 않다. 본 논문에서는 ECDSA 서명 생성의 안전성 분석과 관련된 매우 특수한 형태의 문제에 HNP와 Howgrave-Graham 방법을 적용한 후 두 방법의 성능을 실험을 통해 비교한다.
Abstract
ECDSA is a well-established signature scheme and highly relies its security on a freshly generated per-message nonce. And, it is well-known that, if the nonce is not guaranteed to be random the ECDSA security is severely damaged. For example, if the same nonce is repeatedly used for distinct signatures, the ECDSA private key can easily be recovered. Also, if some portion of the nonce is leaked or the nonce is somewhat biased, it is also known that the security can be compromised via the lattice-based cryptanalysis. The lattice-based cryptanalysis converts problems related to the security analysis of cryptographic systems into the shortest vector problem or the closest vector problem over lattices and then finds adequate solutions using algorithms such as LLL or BKZ. Representative examples of lattice-based cryptanalysis include HNP and the Howgrave-Graham methods. Although the HNP and Howgrave-Graham methods both share a reliance on lattice-based techniques, they are employed in distinct cryptanalytic scenarios so the direct comparison of their performance is nontrivial. In this paper, we apply the HNP and Howgrave-Graham methods to a specific problem derived from the security analysis of the ECDSA signature algorithm, and compare their performance through empirical evaluation.