Meta-PKE 구조에 의한 SABER 알고리즘의 임시 키 재사용 공격
Ephemeral Key Reuse Attack of the SABER Algorithm by Meta-PKE Structure
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
NIST PQC 표준화 Round 3에 제시된 PKE/KEM 알고리즘인 SABER 알고리즘은 격자 기반 문제 중 Module-LWR 문제를 기반으로 하는 알고리즘으로 Meta-PKE 구조로 되어 있다. 이때, 암호화 과정에서 사용되는 비밀 정보를 임시 키라고 부를 것이며 본 논문에서는 Meta-PKE 구조를 활용한 임시 키 재사용 공격에 대해 설명한다. NIST에서 요구하는 보안 강도 5, 3, 1을 만족하는 각각의 파라미터에 대해 4, 6, 6번의 쿼리를 사용하여 공격한 선행 연구에 대해 자세한 분석과 함께 이를 향상하여 3, 4, 4번의 쿼리만 사용하는 방법을 제시한다. 그리고 추가로 한 번의 쿼리를 통해 임시 키를 복원하는 계산 복잡도를 차 격자 위에서 각각의 파라미터에 대해 전수조사 복잡도인 ,, 에서 ,,으로 감소시키는 방법을 소개하며 그에 대한 결과 및 한계점을 제시한다.
Abstract
The SABER algorithm, a PKE/KEM algorithm presented in NIST PQC Standardization Round 3, is an algorithm based on the Module-LWR problem among lattice-based problems and has a Meta-PKE structure. At this time, the secret information used in the encryption process is called a ephemeral key, and in this paper, the ephemeral key reuse attack using the Meta-PKE structure is described. For each parameter satisfying the security strengths required by NIST, we present a detailed analysis of the previous studies attacked using 4, 6, and 6 queries, and improve them, using only 3, 4, and 4 queries. In addition, we introduce how to reduce the computational complexity of recovering ephemeral keys with a single query from the brute-force complexity on the -dimension lattice, ,, to ,,, for each parameter, and present the results and limitations.
참고문헌 (9)
- P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM Journal Computing, 26(5), pp.1484~1509 (1997)
- J. Bos, "CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM", 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pp.353~367 (2018)
- J. P. D'Anvers, "Saber : Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM", Progress in Cryptology -AFRICACRYPT 2018, AFRICACRYPT 2018, pp.282~305 (2018)
- E. Rescorla, "The Transport Layer Security (TLS) protocol version 1.3, RFC 8446", ~ (2018)
- E. Alkim, "Post-quantum key exchange-a new hope", 25th Usenix Security Symposium, pp.327~343 (2016), USENIX Association
- C. Liu, "Key Reuse Attack on NewHope Key Exchange Protocol", ICISC 2018, ICISC 2018, pp.163~176 (2019)
- K. Wang, "Security of two NIST candidates in the presence of randomness reuse", Provable and Practical Security, ProvSec 2020, pp.402~421 (2020)
- X. Lu, "LAC : Practical Ring-LWE Based Public-Key Encryption with Byte-Level Modulus", IACR ePrint 2018-1009, ~ (2018)
- S. Okada, "Recovery Attack on Bob's Reused Randomness in CRYSTALS-KYBER and SABER", Provable and Practical Security, ProvSec 2021, pp.155~173 (2021)