Journal Archive

대규모 전자 상거래, IoT, 클라우드 컴퓨팅 등 대부분의 무선통신 기술은 공개키 암호 기반 으로 이루어져 있다. 공개키 기반으로 동작하는 대표적인 프로토콜인 TLS는 디지털 객체 간 암호화 된 통신을 제공함으로써 Data의 기밀성을 제공하고, SSL/TLS와 HTTP 프로토콜이 결합된 HTTPS 사용이 권장됨에 따라 공개키 알고리즘에 대한 수요는 계속해서 증가하고 있다. 기밀성 뿐 아니라 X.509 인증서를 통해 인증 서비스를 제공하고 있다. X.509 인증서는 두 객체 사이 제 3자 기관(CA:인증기관)에 의해 서명된 후 발급되며, 서명에 사용 되는 서명 알고리즘은 공개키 암호 알고리즘인 RSA가 사용된다. 공개키 기반 암호기반의 구분은 소인수분해의 어려움과 이산대수의 어려움에 기반을 두고 있다.[3]

공개키 암호의 중요한 요소는 Key와 디지털 서명이다. 위에서 언급한 바와 같이, 양자컴퓨팅 환경의 발전은 RSA와 같은 소인수 분해의 어려움을 기반으로 하는 공개키 암호 시스템을 불안정하게 만들 수 있다. 이를 대응하기 위한 양자 컴퓨팅환경에서 내성을 가지는 암호의 기반은 <표 3>과 같이 5가지로 분류할 수 있다. 양자내성암호는 기존 공개키 암호 시스템의 문제를 보완할 수 있고, 수학적 어려움의 기반을 두는 것이 아닌 각 양자내성암호의 기반별 특징마다 안전성을 두고 있다.본 절에서는 양자내성암호 기술(격자기반, 코드기반, 해시 기반, 다변수 기반, 아이소제니 기반)들의 특징 및 알고리즘을 분석한다.

양자컴퓨팅 환경의 발전으로 소인수 분해, 이산대수와 같은 수학적 어려움을 기반으로 두고 있는 기존의 공개키 알고리즘이 해독되는 것이 문재 됨에 따라 이에 대비하기 위한 미국 국립표준기술연구소(NIST, National Institute of Standards and Technology)는 공개 된 절차를 통해 1개 이상의 경쟁력 있는 공개키 알고리즘을 선정 하는 과정에 있으며 NIST PQC 표준화 사업이라고 한다. NIST는 PQC 표준화 사업을 통한 각 Round 과정을 통해 1개 이상의 KEM과, 디지털 서명을 지정하는 과정에 있다. NIST QPC 표준화 사업은 2017년 조건을 만족하는 69개의 후보자 알고리즘으로 Round 1이 진행 되었다. Round 1에서 선정 된 기반 별 알고리즘의 분포 수는 표 2.와 같다. Round 1은 2019년 1월까지 진행이 되었고, 이 과정을 통해 보안성과 성능 조건을 만족하는 26개의 알고리즘이 선정되었다. Round 1에 선정 된 후보 알고리즘은 각각 공개키 암호, 전자서명, KEM 중 하나를 만족하는 알고리즘이다.[5]

기존의 소인수 분해, 이산대수의 어려움을 기반을 두고 있는 수학적 기반의 알고리즘과 대비하여 NIST에서 선정한 알고리즘의 KEM(Key Encapsulation Mechanism)과 Digital Signatures은 다른 특징을 가진다.

RSA, ECC와 같은 기존 암호 알고리즘의 키교환 매커니즘은 송신자의 공개키를 이용하여 전달하고자 하는 메시지 를 암호화 하고, 수신자의 개인키를 사용하여 암호화 된 메시지를 복호화 한다. 이 방법은 양자컴퓨팅 환경에 취약한 방법이다. 이를 대응하기 위해 PQC 알고리즘의 키 교환 매커니즘은 대칭키를 사용하여 메시지를 암/복호화 한다. 송신자는 random한 난수를 생성한 후에 키 유도함수(KDF)를 사용하여 대칭키를 생성한다. 즉 패딩을 사용하지 않아 키 사이즈를 크게 줄였다. PQC 알고리즘의 디지털 서명 방식은 송신자의 개인키로 메시지에 서명하고, 수신자는 송신자의 공개키를 이용하여 서명된 메시지를 검증한다.

NIST에서는 Round 1을 통해 선정된 26개의 알고리즘으로 Round 2를 진행하였고, 최적화 된 구현과 성능을 분석하여 최종 라운드인 Round 3에 진출한 8개의 알고리즘과 추가적으로 표준화하기 위한 Alternatives Round 후보자를 선정하였다.선정된 알고리즘은 표 3.와 같다. 최종 Round에 선정 된 키교환 매커니즘으로 Classic McEliece, Crystals Kyber, NTRU, Saber 4개의 알고리즘이 선정되었으며, 디지털 서명으로 Crystals Dillithium, Falcon, Rainbow 3개의 알고리즘이 선정되었다.

TLS 1.3의 구조를 보면 다음 그림 1과 같다.[6] Handshake, Change cipher Spec, Alert, Record 프로토콜로 구성 되어있다. Handshake 프로토콜은 서버와 클라이언트의 Data 교환이 이루어지기 전 협상단계에서 수행되는 프로토콜이며, 연결을 위해 cipher Suite (암호화 알고리즘, Key 교환 알고리즘, 압축방식 등)을 협상하는 프로토콜이다. Chage cipher Spec 프로토콜은 서버와 클라이언트 간 Handshake 프로토콜에서 정해진 cipher Suite가 반영 됨을 알리는 프로토콜이다.Alert 프로토콜은 경고 역할을 하며, 두 서버간 또는 서버 와 클라이언트의 SSL/TSL 통신하는 과정에서 Error가 발생하였을 시 알리는 프로토콜이다. Record 프로토콜은 Application 계층으로부터 전달받은 Data와 TLS의 상위 프로토콜에서 적용 된 값을 이용하여 암호화/복호화, Fragmentation, 압축 등의 처리과정을 통해 Header를 추가 한 후 전송하는 역할을 하는 프로토콜이다.

Fig. 1. 
TLS protocol structure

Record 프로토콜의 TLS Header를 붙이는 과정은 그림 2과 같다. Record Protocol Data는 2^14 이상의 Data를 전송하지 못하므로 Fragment 과정이 필요하다. 단편화가 완료되면 Data를 압축한 이후에 MAC을 계산한 후 추가하여 Data를 암호화 한다. 최종적으로 암호화 된 데이터에 콘텐츠 유형, Major 버전, Minor 버전, 압축된 길이가 포함 된 Record 헤더를 추가하여 최종적인 Data를 TCP 전송한다.위 과정을 통해 수신 된 Data는 decryption, 압축된 Data를 풀고, 재조립하는 과정을 통해서 위 계층 User에게 전달한다.

Fig. 2. 
Record protocol data processing process

NIST PQC 2021에서는 ARMv8 Micro 프로세서를 대상으로 격자기반 암호 CRYSTALS-Kyber, NTRU, and Saber대한 최적화 연구가 진행되었다.[7] ARM CPU는 Embedded 단말에 많이 사용되는 프로세서이며 현재 수십억개의 단말이 Internet에 연결되어 있다. 이에 따라 이러한 Embedded 단말들 간 안전한 무선통신의 필요성이 중요한 요소이며 양자컴퓨팅환경의 발전 속에서 계산속도의 고속화 구현이 안되어 있는 경우, PQC 표준화에 채택은 늦어질 수 있다.

ARM의 가장 인기 있는 version은 ARMv8이다. 성능평가는 3.2GHz 주파수로 실행되는 4개의 ARMv8 코어를 포함한 Apple M1 환경의 맥북에어와 1.5GHz ARM72A 코어를 가진 4개의 라즈베리파이로 연구가 진행되었으며 이중 1개의 Core에서만 성능평가에 활용되었다. AVX2/neon 구현을 통해 단말 상에서 Encapsulation과 Decapsulation 속도의 향상을 달성했다.[11]

Pennsylvania 대학에서는 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm)을 이용하여 양자내성암호 최적화를 위해 QAOA의 최적 p값을 찾는 연구를 진행했다. 4개의 각자 다른 QAOA Circuit을 두어 각 회로에 주어진 p값을 통해 최적의 선능을 제공하는 값을 찾아 성능결과를 제안하였다. 지금까지 대부분의 연구들은 각 단말에서 양자내성암호의 성능 및 Code의 사이즈를 최적하기 위한 연구가 수행되었다. 하지만 양자컴퓨팅환경에 대응하는 알고리즘의 실제 상용화를 위해서는 프로토콜 관점의 연구가 추가로 필요하다. 본 논문에서 양자내성암호를 적용할 프로토콜인 TLS 1.3에 적용하기 위하여 TLS 프로토콜의 구조(Handshake, Change cipher Spec, Alert, Record)를 파악하고, End-to-End 간 Handshake과정에서 사용되는 기존 X.509 인증서의 구조와 PQC X.509을 파악하여 실제 양자내성암호를 적용하기 위해 고려해야하는 사항을 분석해 실제 서버와 클라이언트간 교환되는 Data에 양자내성암호 알고리즘을 적용하여 성능결과 및 적용 가능성을 도출하는 것이 필요하다.

TLS 1.3 프로토콜에서 양자내성암호의 구현을 위해 다음과 같이 환경을 구축하였다. 구축한 실험 환경은 OS : Mac OS, CPU : M1, Mermory : 8GB 3733MHz, LPDDR4X 환경에서 OQS Openssl 라이브러리를 직접 빌드하였다. 위 환경에서 실험을 진행하며 알고리즘에 대한 성능을 먼저 분석하고,[13] 각 알고리즘별 성능 분석한 결과를 바탕으로 TLS Handshkae에 대한 지연시간을 분석한다. 따라서, 본 장에서는 제 1절에서 알고리즘에 대한 성능을 비교한다. 그 다음 제 2절에서 TLS 1.3에 PQC를 적용하여 key encapsulation Mehcanism, Digtal Signature의 Handshake 지연시간을 측정하여 성능을 비교한다.

실험 시나리오는 다음과 같다. 먼저 각 NIST Security Level에 해당하는 KEM,Digital Signature 알고리즘을 분류하여 Handshake과정에서 암/복호화, 키생성 속도를 비교하고, Digital Signature과정에서 서명속도와 검증속도를 비교하여 각 Security Level에서의 최적화 된 알고리즘을 선정한다.

먼저 TLS 1.3 프로토콜에 알고리즘 별 key encapsulation Mehcanism의 Encapsulation, Decapsulation, Keygen의 속도를 측정한다. NIST Security Level 1 에 해당하는 알고리즘 별 성능분포는 그림 4과 같다. Encapsulation 항목은 Crystals-Kyber-512가 초당 105,005번으로 가장 빠른 속도를 보였다. Decapsulation 항목은 Crystals-Kyber-512가 초당124,057번으로 가장 빠른 속도를 보였다. Keygen항목 또한 Crystals-Kyber-512가 초당136,391번으로 가장 빠른 속도를 보였다. TLS 1.3 end-to-end testing 연구에서 KEM알고리즘 중 Crystals-kyber가 Saber보다 Encapsulation, Decapsulation 항목에서 약 110%높은 성능을 보였으며, Keygen 항목에서 약 120% 높은 성능을 보임으로써 가장 좋은 성능을 나타냈다.

Fig. 4. 
NIST Security Level:1 KEM Performance Comparison

다음 그림 5은 NIST Security Level 1에 해당하는 DS 알고리즘 별 성능분포표이다. Verify 항목은 Dilithium2가 초당 35,579.2번으로 가장 빠른 속도를 보였다. Signature 항목은 Dilithium2가 초당 12,615번으로 가장 빠른 속도를 보였다. 다음 그림 6은 NIST Security Level 5에 해당하는 DS 알고리즘 별 성능분포표이다. Verify 항목은 Falcon-1024가 초당 16,634번으로 가장 빠른 속도를 보였다. Signature 항목은 Dilithium5가 초당 6214.4번으로 가장 빠른 속도를 보였다.

Fig. 5. 
NIST Security Level:1,5 DS Performance Comparison

Fig. 6. 
Performance comparison for KEM Handshake

TLS 1.3 end-to-end testing 연구에서 DS 알고리즘 중 Falcon가 Dilithium보다 Verify 항목에서 약 120%높은 성능을 보였으며, 반대로 Signature 항목에서 Dilithium가 Falcon보다 약 430% 높은 성능을 보임으로써 Dilithium과 Falcon은 Trade-off 관계임을 확인했다.

위에서 분석한 각 Security Level 에서의 key encapsulation Mechanism 알고리즘의 성능결과를 나타낸 것으로, Key EncyptionTLS 1.3 프로토콜에서 Handshake 과정에서의 성능분포표는 그림 6과 같다.

측정항목은 TLS Connection의 수, Handshake 소요시간, 초당 맺어진 Connection의 수를 측정했다. KEM의 정확한 측정을 위해 전사서명방식은 Dilithium2 알고리즘으로 고정하고 각 KEM 알고리즘의 성능을 측정하였다.격자기반 암호인 Crystals-Kyber 와 Saber 알고리즘이 각 Security Level에서 타 알고리즘에 비해 연결되는 Connection의 수가 많았으며,같은 시간을 비교해 보았을 때 초당 맺어지는 Connection의 수가 많아 좋은 성능을 나타내는 것을 확인할 수 있었다. 그 중 Crystals-Kyber 알고리즘이 Saber 알고리즘보다 10% 나은 성능을 보였으며 Handshake 성능비교에서 분석 된KEM 알고리즘 중 가장 좋은 성능을 나타냈다.

다음 그림 7은 각 Security Level에서의 Digital Signature알고리즘의 성능결과를 나타낸 것으로, Key EncyptionTLS 1.3 프로토콜에서 Handshake 과정에서의 성능분포표이다. 위 실험과같이 측정항목은 TLS Connection의 수, Handshake 소요시간, 초당 맺어진 Connection의 수를 측정했다. Digital Signature 알고리즘의 정확한 측정을 위해 KEM 알고리즘은 Crystals-Kyber 512로 고정하여 측정하였다. 위 KEM Handshake 성능분석과 마찬가지로 격자기반 암호인 Dilithium 알고리즘이 각 Security Level에서 타 알고리즘에 비해 연결되는 Connection의 수가 많았으며,같은 시간을 비교해 보았을 때 초당 맺어지는 Connection의 수가 많아 좋은 성능을 나타내는 것을 확인할 수 있었다. 추가로 Web환경에서는 Falcon 알고리즘의 성능도 좋은 성능결과 지표를 나타냈다. 본 연구를 통해 Kyber와 Dilithitum알고리즘이 각 KEM/DS에서 좋은 성능을 가진 알고리즘으로 확인할 수 있었다. NIST에서 진행하는 PQC 표준화 사업의 표준 발표 당시 Crystals 알고리즘을 주요 알고리즘으로 중용한 점을 고려하면 위 성능 결과를 통해 key encapsulation Mechanism의 Crystals-Kyber 알고리즘과, Digital Signature의 Crystals-Dilithium알고리즘이 기존에 사용이던 공개키 기반의 RSA,ECDDH와 같은 수학적 문제에 기반을 두고 있는 알고리즘을 대체하여 양자컴퓨팅환경에서 안전한 알고리즘 구현의 가능성을 확인할 수 있었다.

Fig. 7. 
Performance comparison for DS Handshake