국방 환경에 적합한 양자내성 암호 설계 및 구현

Abstract

As the threat of public-key cryptography by a quantum-computer is emerging, NIST is going on a post-quantum cryptography standardization process. On the other hand, In the military, it is an urgency to adopt post-quantum cryptography, but related studies are insufficient. Civilians can switch to post-quantum cryptography without deploy issues using international standard algorithms selected through the NIST competition. But the military can not easily. Because the military requires algorithms to be applied to various weapons and communication systems, excellent algorithms are required in terms of performance, bandwidth, correctness, and security. Besides, there is a lack of countermeasures against the side-channel attack that considers lost cryptographic equipment during military operations. Also, legislation that allows only domestic cryptography to be used to protect military secrets imposes restrictions on the use of international standard algorithms selected by NIST. Therefore, we propose a Key Encapsulation Mechanism and public-key encryption scheme suitable military. It called LizarMong, which is based on RLizard. LizarMong combines the merit of NIST's candidate algorithms and state-of-the-art studies such as countermeasures against known side-channel attacks. As a result, it achieves up to 85% smaller bandwidth and 3.3 times faster performance compared with RLizard. Compared with the NIST's candidate algorithms with a similar security, the bandwidth is about 5-42% smaller, and the performance is about 1.2-4.1 times faster. Also, LizarMong resists the known side-channel attacks.

양자컴퓨터로 인한 공개키 암호 해독 위협이 가시화 되면서, 양자내성 암호 표준화 공모가 미국 표준기술연구원(National Institute of Standards and Technology, NIST)를 중심으로 이뤄지고 있다. 반면, 군에서는 양자내성 암호 도입이 더욱 시급함에도 불구하고 관련 연구가 미진한 실정이다.

민간에서는 NIST 주관 공모전을 통해 선택된 국제표준 알고리즘을 사용하면 소프트웨어 업데이트 또는 장비의 교체 과정만 감내하면 양자내성 암호로 전환할수 있지만, 군은 그렇지 못하다. 왜냐하면, 국방 환경에서는 다양한 무기 및 통신체계에 적용될 알고리즘이 필요하기 때문에 성능, 대역폭, 정확성 및 안전성 측면에서 보다 엄격한 기준이 요구된다. 하지만, 현재까지 NIST 주관 표준화 공모에 제출된 후보 알고리즘들은 성능, 대역폭, 정확성 및 안전성 측면에서 저마다의 장단점을 갖고 있어 모든 측면에서 탁월한 알고리즘 하나를 선택하기 어렵다. 또한, 군사작전 간 분실 및 피탈 상황에서도 암호장비(또는 소프트웨어) 내부의 비밀 키 등이 탈취되지 않도록 부채널 공격에도 대응해야 하지만 방어대책이 부족하다. 게다가, 국산 암호만을 군사 비밀 보호에 사용할 수 있는 국내 법규도 향후 NIST에서 선정한 국제 표준 알고리즘을 사용할수 없는 제한사항이 된다.

따라서, 이 연구에서는 국방 환경에 적합한 양자내성 암호 알고리즘을 설계하고 성능을 평가한다. 본 연구에서 설계한 알고리즘은 LizarMong이라고 명명했으며, 국산 양자내성 암호 알고리즘인 RLizard [1]를 기반으로 개선한 체계이다. LizarMong은 128bit 보안강도인 Comfort와 256bit 보안강도인 Strong 버전으로 사용할수 있으며, 공격자가 평문을 선택할수 있는 상황 하에서의 구별 공격(Indistinguishability under chosen-plaintext attack, IND-CPA)에 안전한 공개 키 암호 알고리즘(Public-key Encryption, PKE)과 가장 강력한 공격자 가정인 적응형 선택 암호문 상황하 구별 공격(Indistinguishability under adaptive chosen ciphertext attack, IND-CCA2)에도 안전한 키 교환 매커니즘(Key Encapsulation Mechanism, KEM)을 지원한다.

LizarMong의 기반이 된 RLizard는 우수한 성능과 안정적인 보안성과 정확성을 갖고 있지만, 국방 환경에 사용하기에는 대역폭이 크고 부채널 공격에 비교적 많이 노출된 단점이 있다. LizarMong은 RLizard의 문제점을 해소하기 위해 NIST 주관 표준화 공모 후보 알고리즘들의 장점들을 조합하고, 최신 부채널 공격 대응기법 등을 종합하여 설계하였다. 구체적으로, 대역폭 감소를 위해 Ring-Learning With Error(RLWE)에 사용되는 법(modulus)인 q를 2^8으로 대폭 감소시키고 암호문 및 공개키 압축 기법을 적용하였다. 이로 인해 감소하는 알고리즘의 정확성을 보상하기 위해 오류 정정 부호화 기법인 XE5 [2]를 도입했다. 또한, 부채널 공격 저항성을 갖기 위해 공격 표면(attack surface)을 줄이고 대응 기법을 삽입하였다. 공격 표면을 줄이기 위해 알려진 캐시 공격 및 타이밍 공격들이 취약점으로 악용한 법 연산(modulus operation)과 오류 샘플링에서의 표 탐색 기법을 제거하였다. 즉, 법(modulus)을 2의 지수 승으로 선택하고 에러 샘플링 방법을 기존의 누적확률분포표(Cumulative Distribution Table, CDT)를 탐색하는 방법에서 중심이항분포(centered binomial distribution) 계산 방법으로 변경하였다. 또한, 다항식 곱셈 연산과 에러 및 비밀값 생성 과정을 악용하는 오류주입 및 전력분석 공격 대응을 위한 방어기법을 내재하였다.

결과적으로 LizarMong은 알려진 여러 부채널 공격으로부터 저항성을 갖을 뿐만 아니라, RLizard와 유사한 정확성과 안전성 수준에서 최대 85% 작은 대역폭과 3.3배 빠른 성능을 보인다. NIST 주관 표준화 공모 후보 알고리즘들과 비교해도 유사한 정확성과 안전성을 갖고도 대역폭은 약 5-42% 작으며, 성능은 약 1.2-4.1배 빠르다.

따라서, LizarMong은 성능, 대역폭, 정확성과 안전성 모든 측면에서 우수할 뿐만 아니라 부채널 공격에 저항하며, 국내에서 설계된 알고리즘이므로, 국방 환경에 적합하게 사용할 수 있다.