[논문]저성능 사물인터넷 상에서의 양자 내성 암호 구현

서화정

저성능 사물인터넷 상에서의 양자 내성 암호 구현 원문보기

情報保護學會誌 = KIISC review, v.30 no.1, 2020년, pp.13 - 21

서화정 (한성대학교 IT융합공학부)

초록
AI-Helper

기존 공개키 암호의 보안성을 저하시킬 수 있는 양자 컴퓨터와 양자 알고리즘의 급속한 발전으로 인해 미국의 NIST에서는 양자 내성 암호 표준화를 수행하고 있다. 전 세계에서 다양한 양자 내성 암호 표준안을 제시하였으며 현재 2 단계로 넘어가 차세대 양자 내성 암호를 다방면에서 평가하고 있다. 양자 내성 암호를 평가하는 다양한 항목 중에는 암호 보안강도와 암호 구현 효율성이 있다. 본 기고에서는 자원적인 제한사항이 많은 저성능 사물인터넷 상에서의 양자 내성 암호구현에 대해 확인해 보도록 한다.

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 고에서는 양자 내성 암호를 저성능 사물인터넷 프로세서인 32-비트 ARM Cortex-M4 상에서 구현한 최신 결과물들을 종합하여 나타내고 있다. 현재 다양한 양자 내성 암호 알고리즘들이 해당 프로세서 상에서 구현되고 있다.
특히 하드웨어의 경우 Artix-7 FPGA 보드 그리고 소프트웨어의 경우 ARM Cortex-M4 보드를 주요 타겟으로 설정하였다. 본 고에서는 저성능 프로세서인 ARM Cortex-M4 상에서 양자 내성 암호를 구현한 결과물들에 대해 확인해 보도록 한다.

제안 방법

NTRUEncrypt 역시 standard NTRU에 기반하고 있다. NTRU-HRSS-KEM이 FO transform을 사용했다면 NTRUEncrypt는 NAEP transform을 통해 시스템을 설계하였다. Saber의 경우 module-Learning With Rounding (LWR) 문제에 기반하고 있다.
ACNS’19에서 발표된 논문에서는 NTRU와 Saber에서 자주 사용되는 polynomial 곱셈을 Karatsuba와 Toom-Cook 알고리즘을 이용하여 개선하였다 [8]. polynomial 차수에 따라 다양한 알고리즘들의 성능 비교를 함과 동시에 ARM 어셈블리 명령어인 smlad와 smladx를 이용하여 16-비트 단위의 곱셈을 한번에 두 개씩 병렬 수행하였다. 세 알고리즘에 대한 연산속도와 메모리 사용량은 [표 10]과 [표 11]에 각각 비교되어 있다.
본 장에서는 ARM Cortex-M4 상에서 어셈블리 언어를 활용하여 최적화 구현한 결과물들에 대해서 종합하여 나타내도록 한다.
하지만 여전히 AES128와 cSHAKE128는 매우 높은 부하를 나타내게 된다. 이를 해결하기 위해 xoshiro128과 같은 경량 암호를 활용하여 구현함으로써 연산 성능을 높였다. FrodoKEM640의 ARM Cortex-M4 상에서의 구현 결과는 [표 5]와 같다.
초기에 NIST 공모전의 전체 일정은 총 10년으로 계획되었다. 이중 전반기 5년의 경우에는 표준 권고 알고리즘을 선정하는 작업을 하게 되며 후반기 5년 동안에는 선정된 알고리즘 구현 검증 및 산업계 확산적용을 수행하기로 계획하였다.
NTRU-HRSS-KEM은 classic NTRU 시스템에 기반을 하고 있다. 파라미터 공간을 기존 NTRU에 비해 제한함으로써 스킴을 간략화하였다. NTRUEncrypt 역시 standard NTRU에 기반하고 있다.
AES의 경우 SAC’16에서 제안된 ARMv7-M 상에서의 어셈블리 구현에 기반을 두고 있다 [3]. 해당 라이브러리에서는 AES-128, AES-192, 그리고 AES-256을 ARM Cortex-M3와 M4상에서의 최적화된 구현 결과를 제공하고 있다.

대상 데이터

NIST 양자 내성 암호 2단계 표준안 후보로 채택된 알고리즘의 수는 총 26개이다. 이 중에서 17개는 키 교환 알고리즘 그리고 9개는 전자 서명 알고리즘에 각각 포함된다.
현재 NIST에서는 소프트웨어 그리고 하드웨어 두 환경 모두에 대한 성능 평가를 요구하고 있다. 특히 하드웨어의 경우 Artix-7 FPGA 보드 그리고 소프트웨어의 경우 ARM Cortex-M4 보드를 주요 타겟으로 설정하였다. 본 고에서는 저성능 프로세서인 ARM Cortex-M4 상에서 양자 내성 암호를 구현한 결과물들에 대해 확인해 보도록 한다.

이론/모형

하지만 해당 논문에서는 이를 직접 C로 구현하여 동작시킨 결과를 나타내고 있다. 메모리 최적화를 위해서는 Schoolbook 기법을 활용하여 곱셈을 구현한다. 속도 최적화를 위해서는 Karatsuba 알고리즘을 활용하여 연산 복잡도를 낮추었다.
메모리 최적화를 위해서는 Schoolbook 기법을 활용하여 곱셈을 구현한다. 속도 최적화를 위해서는 Karatsuba 알고리즘을 활용하여 연산 복잡도를 낮추었다. 연산 속도와 메모리 사용량의 비교는 [표 14] 그리고 [표 15]에 각각 나타나 있다.
따라서 파라미터의 크기가 크고 느린 속도를 가지고 있다. 속도 향상을 위해 해당 구현에서도 NTT 성능 향상을 위해 Montgomery reduction을 적용하였다. Dilithium III의 연산 속도와 메모리 사용량은 [표 8]과 [표 9]에 각각 나타나 있다 [7].
Falcon 상에서 많은 메모리를 소모하는 부분은 fast Fourier sampling에서 사용되는 tree를 구성하는 부분이다. 이를 효과적으로 대체하기 위해 tree를 항상 유지하는 대신 on-the-fly 방식으로 sampling을 취하는 방법론을 적용하였다. 만약 고정된 키를 사용하는 경우에는 tree를 구성하지 않아도 되기 때문에 연산 성능이 좋아지게 된다.

성능/효과

해당 구현에서는 핵심연산인 NTT 연산을 효율적으로 계산하기 위해 signed Montgomery multiplication을 구현하였으며 이는 기존의 unsigned 구현에 비해 높은 성능을 나타냄을 확인하였다 [6]. NTT의 성능이 개선됨에 따라 Kyber의 성능 역시 개선됨을 확인할 수 있었다. 이와 더불어 기존 C 코드 상에서 메모리 할당을 무분별하게 해놓은 부분을 최적화함으로써 전체 소모되는 메모리의 양을 줄일 수 있었다.
NTT의 성능이 개선됨에 따라 Kyber의 성능 역시 개선됨을 확인할 수 있었다. 이와 더불어 기존 C 코드 상에서 메모리 할당을 무분별하게 해놓은 부분을 최적화함으로써 전체 소모되는 메모리의 양을 줄일 수 있었다. 연산 속도에 대한 비교는 [표 6]와 같으며 연산에 사용되는 메모리 사용량은 [표 7]과 같다.
현재 다양한 양자 내성 암호 알고리즘들이 해당 프로세서 상에서 구현되고 있다. 해당 결과들을 살펴보면 키 크기와 연산 속도가 구현에 있어 가장 어려운 문제로 작용하고 있음을 확인할 수 있다. 아직도 많은 양자 내성 암호 후보군들이 ARM Cortex-M4 상에서 구현이 되지 못한 상황이다.
여기서 q = 7681 = 2¹³ - 2⁹ + 1 이고 R_q = Z₇₆₈₁/ (X²⁵⁶ + 1)을 모든 보안 레벨에서 사용하고 있다. 해당 구현에서는 핵심연산인 NTT 연산을 효율적으로 계산하기 위해 signed Montgomery multiplication을 구현하였으며 이는 기존의 unsigned 구현에 비해 높은 성능을 나타냄을 확인하였다 [6]. NTT의 성능이 개선됨에 따라 Kyber의 성능 역시 개선됨을 확인할 수 있었다.
하지만 기본적인 구현은 메모리 레이아웃을 고려하지 않아 연산 속도가 느려지는 단점이 있다. 해당 프로세서의 메모리 레이아웃을 고려한 구현을 제공함으로써 연산 성능을 효과적으로 높일 수 있다. 하지만 여전히 AES128와 cSHAKE128는 매우 높은 부하를 나타내게 된다.

후속연구

이러한 문제점을 해결하기 위해서는 키 크기를 줄이기 위한 알고리즘 혹은 구현 아키텍처 관점에서의 접근이 필요할 것으로 보이며 외부 라이브러리를 제외한 구현도 필요하다. 또한 기본 C언어 구현에서는 최적화된 성능을 얻을 수 없기 때문에 이를 어셈블리 언어로 변환하고 Karatsuba와 같은 알고리즘을 적용하여 연산 성능을 실용적인 단계까지 향상 시켜 나가야 할 것으로 보인다.

질의응답

핵심어	질문	논문에서 추출한 답변
	NIST에서 양자 내성 암호 알고리즘이 수행 가능한 연산은 어떠한 것이 포함되는가?	NIST에서 진행 중인 양자 내성 암호 공모전에 제안된 양자 내성 암호 알고리즘이 수행 가능한 연산으로는 전자서명 그리고 키 교환을 포함한다. 보안 등급은 AES-128 (level 1), AES-192 (level 3), AES-256 (level 5), SHA-256 (level 2), 혹은 SHA-384 (level 4)와 동일한 등급을 만족하기를 권장하고 있다.
	SIKE란?	SIKE는 아이소지니 기반 키교환 프로토콜을 KEM으로 확장한 프로토콜로써 ECC의 프리미티브 연산에 기반을 두고 있는 양자 내성 암호이다. SIKE는 매우 작은 키와 암호문의 크기를 가지지만 연산 속도가 느린 단점을 가지고 있다.
	양자 컴퓨터의 발전이 빠르게 진행됨으로 인해서 불안감을 일으키는 이유는?	하지만 양자 컴퓨터의 발전이 유수의 IT 기업들(IBM 그리고 Google)의 공격적인 투자와 함께 기존 예상과는 달리 매우 빠르게 진행되고 있다. 이는 대표적인 공개키 암호 시스템인 RSA와 ECC의 붕괴를 더 빠르게 가지고 올 수 있다는 불안감을 야기 시키고 있다. 이와 같은 사회적인 변화에 NIST도 빠르게 반응하여 애초 계획과는 달리 해당 공모전의 일정을 앞당기고 있다.

참고문헌 (12)

NIST. "Post-Quantum Cryptography," (https://cs rc.nist.gov/Projects/Post-Quantum-Cryptography).
M. Kannwischer, J. Rijneveld, P. Schwabe, K. Stoffelen, "PQM4: Post-quantum crypto library for the ARM Cortex-M4," 2018.
P. Schwabe, K. Stoffelen, "All the AES you need on Cortex-M3 and M4," In International Conference on Selected Areas in Cryptography, pp. 180-194, 2016.
J. Bos, S. Friedberger, M. Martinoli, E. Oswald, M. Stam, "Fly, you fool! Faster Frodo for the ARM Cortex-M4," IACR Cryptology ePrint Archive, 2018.
J. Howe, T. Oder, M. Krausz, T. Guneysu, "Standard lattice-based key encapsulation on embedded devices," IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 372-393, 2018.
L. Botros, M. Kannwischer, P. Schwabe, "Memory-efficient high-speed implementation of Kyber on Cortex-M4," In International Conference on Cryptology in Africa pp. 209-228, 2019.
T. Guneysu, M. Krausz, T. Oder, J. Speith, "Evaluation of lattice-based signature schemes in embedded systems," In 2018 25th IEEE International Conference on Electronics, Circuits and Systems, pp. 385-388, 2018.
M. Kannwischer, J. Rijneveld, P. Schwabe, "Faster multiplication in Z2m [x] on Cortex-M4 to speed up NIST PQC candidates," Cryptology ePrint Archive, Report 2018/1018, 2018.
A. Karmakar, I. Verbauwhede, "Saber on ARM. CCA-secure module lattice-based key encapsulation on ARM," IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 243-266, 2018.
T. Oder, J. Speith, K. Holtgen, T. Guneysu, "Towards Practical Microcontroller Implementation of the Signature Scheme Falcon," In International Conference on Post Quantum Cryptography, pp. 1-17, 2019.
J. Lablanche, L. Mortajine, O. Benchaalal, P. Cayrel, & N. El Mrabet, "Optimized implementation of the NIST PQC submission ROLLO on microcontroller," Cryptology ePrint Archive, Report 2019/787, 2019.
H. Seo, A. Jalali, R. Azarderakhsh, "SIKE round 2 speed record on ARM Cortex-M4," In International Conference on Cryptology and Network Security, pp. 39-60, 2019.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

저성능 사물인터넷 상에서의 양자 내성 암호 구현 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

저성능 사물인터넷 상에서의 양자 내성 암호 구현 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

초록
AI-Helper

AI 본문요약
AI-Helper