[논문]Ring-LWE 기반 공개키 암호시스템의 선택 암호문 단순전력분석 공격 대응법

박애선; 원유승; 한동국

doi:10.13089/jkiisc.2017.27.5.1001

Ring-LWE 기반 공개키 암호시스템의 선택 암호문 단순전력분석 공격 대응법
Countermeasure against Chosen Ciphertext Spa Attack of the Public-Key Cryptosystem Based on Ring-Lwe Problem 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.27 no.5, 2017년, pp.1001 - 1011

박애선 (국민대학교 금융정보보안학과) , 원유승 (국민대학교 금융정보보안학과) , 한동국 (국민대학교 금융정보보안학과)

초록
AI-Helper

격자 기반 암호는 양자 컴퓨터 공격에 대응 가능한 포스트 양자 암호 중 하나로 알려져 있다. 그 중 ring-LWE 문제는 LWE의 대수적 변종으로 벡터 대신 환(ring)의 원소를 이용한다. 포스트 양자 암호라 할지라도 실제 디바이스에 이를 적용 할 때 부채널 분석 취약점이 존재한다는 것은 이미 알려져 있다. 실제 2016년 Park 등은 Roy 등이 제안한 NTT를 이용한 ring-LWE 기반 공개키 암호시스템의 SPA 취약점을 보고했으며, Reparaz 등은 Roy 암호에 대한 DPA 공격 및 대응법을 2015년과 2016년에 제안하였다. 본 논문에서는 Roy 암호에 대하여 Park 등이 제안한 선택 암호문 SPA 공격이 NTT를 적용하지 않은 Lyubashevsky 암호의 경우에도 동일하게 적용 가능함을 보인다. 또한 선택 암호문 SPA 공격에 안전한 대응기법을 제안한고 실험적으로 안전성을 검증한다.

Abstract ▼ AI-Helper

A lattice-based cryptography is known as one of the post-quantum cryptographies. Ring-LWE problem is an algebraic variant of LWE, which operates over elements of polynomial rings instead of vectors. It is already known that post-quantum cryptography has side-channel analysis vulnerability. In 2016, Park et al. reported a SPA vulnerability of the public key cryptosystem, which is proposed by Roy et al., based on the ring-LWE problem. In 2015 and 2016, Reparaz et al. proposed DPA attack and countermeasures against Roy cryptosystem. In this paper, we show that the chosen ciphertext SPA attack is also possible for Lyubashevsky cryptosystem which does not use NTT. And then we propose a countermeasure against CCSPA(Chosen Ciphertext SPA) attack and we also show through experiment that our proposed countermeasure is secure.

주제어

AI 본문요약
AI-Helper

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

문제 정의

CCSPA 공격은 모듈러 덧셈 연산이 진행 될 때조건문의 수행여부가 시간(timing) 기반 단순전력분석을 통해 구별가능하다는 취약점을 이용하는 것이다. 따라서 본 논문에서는 공격을 방지하기 위해 동일 시간에 동작하는 CCSPA에 안전한 모듈러 덧셈을 제안한다.
본 논문에서는 NTT를 적용한 ring-LWE 기반 공개키 암호시스템에 대한 Park 등[7]이 제안한 선택 암호문 단순전력분석(Chosen Ciphertext Simple Power Analysis, CCSPA) 공격이 NTT를 적용하지 않을 때에도 동일한 취약점이 존재함을 보인다. 또한 CCSPA 공격을 방지하기 위한 대응법을 제안한다.
본 논문에서는 격자 기반 암호의 LWE 문제의대수적 변종인 ring-LWE 문제를 이용한 공개키 암호시스템에 대하여 부채널 분석 연구를 진행하였다. 우선 Roy 암호에만 적용되었던 시간 기반 선택 암호문 SPA 공격이 암호문 c₁의 변형을 통해 Lyubashevsky 암호에 적용 되어 질 수 있음을 보였고, CCSPA 공격에 대응하기 위한 CCSPA에 안전한 모듈러 덧셈을 제안하였다.

제안 방법

와 같다. CCSPA에 안전한 모듈러 덧셈은각 알고리즘의 2단계에서 뿐만 아니라 곱 연산 또는역 NTT 연산에 사용되는 모든 모듈러 덧셈에 적용시켜 비교하였다.
첫 번째 실험에서 우리는 조건문이 없는 모듈러 덧셈이 동작할때 실제 모듈러 연산 발생 여부에 따라 차이점이 존재하지 않는지 확인하였다. 다음으로 Lyubashevsky 암호와 Roy 암호의 복호화 부분에 제안하는 CCSPA에 안전한 모듈러 덧셈을 적용한 경우의 성능을 대응법이 적용되지 않은 암호와 비교하였다.
본 논문에서는 NTT를 적용한 ring-LWE 기반 공개키 암호시스템에 대한 Park 등[7]이 제안한 선택 암호문 단순전력분석(Chosen Ciphertext Simple Power Analysis, CCSPA) 공격이 NTT를 적용하지 않을 때에도 동일한 취약점이 존재함을 보인다. 또한 CCSPA 공격을 방지하기 위한 대응법을 제안한다.
본 논문에서는 CCSPA에 안전한 모듈러 덧셈을위해 처음 단계에서 계산된 Z를 이용하여 Zflag와 Z₀flag 계산 후 모듈러 연산에 활용한다. 여기에서 Zflag는 Z의 모든 값(즉, Z[1 ]║Z[0 ])을 이용하여계산되는 값으로 모듈러 연산이 필요한 경우(Z≥ q) 1, 모듈러 연산이 필요하지 않는 경우(0 ≤Z<q) 0의 값을 갖도록 구성한다.
ATxmega128A1 프로세서는 최대 32MHz 주파수 및 128 KB 플래시 메모리와 8 KB SRAM이 포함되어 있다. 성능 확인을 위한 구현은 128비트 보안레벨을 만족하는 경우에 대하여 디코딩을 제외한 복호화 부분을 모두 C 언어를 사용해 구현하였다. 즉, n = 256, q = 7681을 사용하였다
본 논문에서는 격자 기반 암호의 LWE 문제의대수적 변종인 ring-LWE 문제를 이용한 공개키 암호시스템에 대하여 부채널 분석 연구를 진행하였다. 우선 Roy 암호에만 적용되었던 시간 기반 선택 암호문 SPA 공격이 암호문 c₁의 변형을 통해 Lyubashevsky 암호에 적용 되어 질 수 있음을 보였고, CCSPA 공격에 대응하기 위한 CCSPA에 안전한 모듈러 덧셈을 제안하였다.
제안된 공격 기법은 Algorithm 2.의 9∼11단계의 조건문 수행 여부를 활용하여 수행되는 것으로, 두 다항식의 덧셈에서 계수별로 덧셈이 이루어질 때 덧셈의 결과 값에 대한 모듈러 연산 발생 여부를 시간(timing) 기반 단순전력분석을 통해 구별가능하다는 취약점을 이용한다.
실험은 두 가지 관점에서 진행되었다. 첫 번째 실험에서 우리는 조건문이 없는 모듈러 덧셈이 동작할때 실제 모듈러 연산 발생 여부에 따라 차이점이 존재하지 않는지 확인하였다. 다음으로 Lyubashevsky 암호와 Roy 암호의 복호화 부분에 제안하는 CCSPA에 안전한 모듈러 덧셈을 적용한 경우의 성능을 대응법이 적용되지 않은 암호와 비교하였다.

대상 데이터

ChipWhisperer - Lite에서 사용하는 공격 대상 칩은 XMEGA128D4로 8/16-bit AVR XMEGA 마이크로컨트롤러이다. 신호는 7.
성능 확인을 위해 ATxmega128A1 프로세서를 사용하는 테스트 보드를 이용하였다. ATxmega128A1 프로세서는 최대 32MHz 주파수 및 128 KB 플래시 메모리와 8 KB SRAM이 포함되어 있다.
ChipWhisperer - Lite에서 사용하는 공격 대상 칩은 XMEGA128D4로 8/16-bit AVR XMEGA 마이크로컨트롤러이다. 신호는 7.37MHz 클록 주파수 (clock frequency)로 모듈러 덧셈이 실행 될 때 발생 되는 전력신호를 29.5MHz 샘플링 레이트로 획득하였다.
제안하는 대응법이 적용된 모듈러 덧셈이 모듈러연산 발생 여부에 따라 차이점이 존재하지 않는지확인하기 위해 NewAE Technology의 ChipWhisperer - Lite를 이용하여 q = 7681 = 0x1E01인 경우에 대하여 실험을 진행하였다.
성능 확인을 위한 구현은 128비트 보안레벨을 만족하는 경우에 대하여 디코딩을 제외한 복호화 부분을 모두 C 언어를 사용해 구현하였다. 즉, n = 256, q = 7681을 사용하였다

이론/모형

1. KeyGen(a) : 두 개의 오류 다항식 r₁ , r₂를 이산정규 분포에서 랜덤하게 추출 후 a, r_1, r₂에 NTT 알고리즘을 적용한다.
실험에 사용된 알고리즘은 Algorithm 1. 및 Algorithm 5.
Enc((ã,p̃),m) : 메시지 m을 Lyubashevsky 암호와 동일한 방법으로 Rq의 원소 (= #)로 인코딩 후, 암호문 (c̃₁, c̃₂)를 다음의 방법을 이용해 계산한다. 이산 정규 분포에서 오류 다항식 e₁, e₂,e₃를 추출 후, e₁, e₂에 NTT 알고리즘을 적용한다.

성능/효과

기존의 ring-LWE 기반 공개키 암호시스템에 대한 부채널 분석 및 대응법 연구는 Roy 암호에 대해서만 진행되어 왔다. 본 논문에서는 간단한 아이디어를 통해 Park 등이 제안한 공격이 Lyubashevsky 암호에도 적용 가능함을 보인다.
그림에서 볼 수 있듯이 기존모듈러 덧셈에서는 두 부분의 시간차이가 존재하나제안하는 모듈러 덧셈에서는 동일한 시간에 동작함을 확인 하였다. 즉, 기존 덧셈에서는 모듈러 연산발생 여부에 따라 포인트의 차이가 발생하나 제안하는 모듈러 덧셈은 모듈러 연산 발생 여부에 상관없이 항상 일정한 값을 지닌다.

후속연구

특히 Roy 암호에 대한 연구가 주를 이룰 뿐 Lyubashevsky 암호에 대한 연구는 아직 미비하다. 향후 Roy 암호의고차 부채널 취약점 연구와 함께 Lyubashevsky 암호에 대한 부채널 분석 관점 연구가 진행 되어야 할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	LWE를 사용할 때 단점은 무엇인가?	LWE는 암호학적 프리미티브(primitive)의 구성에 사용되는 다양한 문제로 사용된다. 그러나 LWE를 사용하면 키 크기가 커지는 단점이 있다. 한편, ring-LWE 문제는 LWE 의 대수적 변종으로 벡터 대신 환(ring)의 원소를 이용한다.
	격자 기반 암호는 격자의 특징으로 인해 어떤 문제점이 존재하는가?	격자 기반 암호는 양자 컴퓨터 공격에 대응 가능한 포스트 양자 암호 중 하나로 알려져 있다. 격자는 기저벡터 집합의 정수 계수로 표현할 수 있는 점들의 그룹으로 기저벡터에 의해 충분히 정의되었다 할지라도 동일한 격자를 표현 할 수 있는 무수히 많은 수의 다른 기저벡터가 존재한다. 이러한 특징으로 인해 임의의 기저벡터로 구성된 격자가 주어졌을 때 격자의 벡터 중 0이 아닌 가장 짧은 벡터를 찾는 SVP(Shortest Vector Problem), 임의의 벡터 v 가 주어졌을 때 v와 가장 가까운 격자 벡터를 구하는 CVP(Closest Vector Problem)와 노이즈가 추가된 선형 방정식으로부터 생성된 벡터를 균등한 랜덤 벡터로부터 구별하는 LWE(Learning With Error) 등의 어려운 문제가 존재한다. LWE는 암호학적 프리미티브(primitive)의 구성에 사용되는 다양한 문제로 사용된다.
	ring-LWE 기반 공개키 암호시스템는 어떻게 구분되는가?	Lyubashevsky 등에 의해 제안된 ring-LWE 기반 공개키 암호시스템은 기존의 공개키 시스템과 같이키 생성, 암호화 그리고 복호화 세 단계로 구분된다[8]. 본 절에서는 Lyubashevsky 등이 제안한 키 생성 및 암·복호화 방법과 Roy 등이 제안한 NTT를 이용한 방법에 대해 간단히 언급한다.

참고문헌 (10)

P. Shor, "Algorithms for quantum computation: Discrete logarithms and factoring," Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124-134, Nov. 1994.
P. Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems," Proceedings of the 16th Annual International Cryptology Conference, pp. 104-113, Aug. 1996.
C. Chen, T. Eisenbarth, I.V. Maurich, and R. Steinwandt, "Differential Power Analysis of a McEliece Cryptosystem," Proceedings of the 13th International Conference on Applied Cryptography and Network Security, pp. 538-556, Jun. 2015.
M.K. Lee, J.E. Song, D.H. Choi, and D.G. Han, "Countermeasures against the power analysis attack for the NTRU public key cryptosystem," IEICE Transactions on Fundamentals of Electronics on Communications and Computer Sciences, vol.E93-A, no.1, pp.153-163, Jan. 2010.

상세보기
O. Reparaz, S. Roy, F. Vercauteren, and I. Verbauwhede, "A masked ring-LWE implementation," Proceedings of the 17th Workshop on Cryptographic Hardware and Embedded Systems, pp. 683-702, Sep. 2015.
O. Reparaz, R. de Clercq, S. Roy, F. Vercauteren, and I. Verbauwhede, "Additively homomorphic ring-LWE masking," Proceedings of the 7th International Conference on Post-Quantum Cryptography, pp. 233-244, Feb. 2016.
A. Park and D,G. Han, "Chosen ciphertext Simple Power Analysis on software 8-bit implementation of ring-LWE encryption," Proceedings of the Hardware-Oriented Security and Trust (AsianHOST), pp. 1-6, Dec. 2016.
V. Lyubashevsky, C. Peikert, and O. Regev, "On Ideal Lattices and Learning with Errors over Rings," Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 1-23, Jun. 2010.
S. Roy, F. Vercauteren, N. Mentens, D. Chen, and I. Verbauwhede, "Compact ring-LWE cryptoprocessor," Proceedings of the 16th Workshop on Cryptographic Hardware and Embedded Systems, pp. 371-391, Sep. 2014.
N. Gottert, T. Feller, M. Schneider, J. Buchmann, and S. Huss, "On the Design of Hardware Building Blocks for Modern Lattice-Based Encryption Schemes," Proceedings of the 14th Workshop on Cryptographic Hardware and Embedded Systems, pp. 512-529, Sep. 2012.

저자의 다른 논문 :

LOADING...

표제어: 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

연합인증