KyberSlash attacks Archives - Dev, Hack & Debug

공개키 암호

공개키 암호^{(public-key cryptography)}¹ 방식은 비대칭 암호^{(asymmetric cryptography)}라고 부르기도 한다. 이는 보통 ‘암호’라고 하면 떠올리는 ‘비밀번호‘ 하나를 가지고 암호화 및 복호화 과정 모두에 사용하는 대칭형 암호화가 아니기 때문이다. 공개키 암호 방식은 수학적 난제를 기반으로 만들어진 공개키^(public-key), 개인키^{(private-key)} 두 개를 사용해 각각 암호화 및 복호화 과정에 사용한다.

단어 그대로 공개키는 모든 사람에게 공개될 수 있는 암호키로, 공개키로 암호화된 메시지는 그에 대응하는 개인키(혹은 비밀키)로만 복호화 할 수 있다. 이와 반대도 마찬가지로, 개인키로 암호화 한 메시지는 공개키로만 복호화 된다. 이러한 특성에 기반해 누구나 공개된 키를 사용해 암호화 된 메시지를 보낼 수 있지만, 해당 메시지를 복호화 하려면 특정 개인이 가진 개인키로만 복호화 할 수 있으므로, 전달 과정의 도청이나 조작 가능성의 걱정 없이 안전한 메시지 전달이 가능하다.

소인수 분해 문제

공개키 암호화 알고리즘의 강력함은 수학적 난제에 기반해 있다. 바로 ‘소인수 분해 문제‘와 ‘대수적 문제‘다.

소인수 분해 문제는, 사람에게도 어렵지만 컴퓨터에게도 어렵다는 큰 수를 소수의 곱으로 분해^{(prime factorization)}하는 문제다. 키를 생성하는 사람(출제자)은 소수 두 개의 곱으로 매우 큰 숫자(문제)를 만들고 이 정보를 공개키(문제), 개인키(관련 정보)의 형태로 만들어 가지고 있기 때문에, 암복호화 과정을 무난히 수행할 수 있다. 하지만 암호화 된 메시지를 도청하거나 조작하려는 공격자는 소인수 분해 문제를 해결하기 위해 막대한 컴퓨팅 자원과 시간을 소모해야 하므로 공격이 어려워지며, 이러한 특성으로 메시지의 안전성이 확보된다.

대수적 문제

대수적 문제는 이런 공개키와 개인키가 서로 어떤 수학적 관계인지를 알아내는 문제로, 이름만큼이나 그냥 어려운 문제다. 솔직히 수업으로도 들었고 여러 해 동안 이슈들을 봐왔으면서도, 이건 잘 모르겠다. 전세계 수학자들이 어렵다고 보장하는 만큼 정말 어렵다.🙄 어려운 문제라고만 정리해보자.

어려움!=불가능

키 해독의 ‘어려움’

위와 같이 강력한 안전성을 자랑하는 공개키 암호 방식은 수학 문제 풀이의 ‘어려움‘에 기반해 있다. 중요한 점은, 여기서 ‘어려움‘이 ‘불가능‘을 의미하지 않는다는 것이다. 정확히 말하자면, ‘그만한 비용과 시간을 들이기엔 가치가 떨어지는‘이라고 해석해야 한다. 암호 해독은 가용한 자원(=일반적으로 컴퓨팅 능력, 돈, 시간)을 소모하더라도 암호 해독으로 얻을 수 있는 정보가 투입된 자원 그 이상의 가치가 있는지의 문제이기 때문이다.

일반적인 표현으로 ‘개인이 PC로 풀기엔 수억년이 걸리는 강력한 암호화’라고 한다. 하지만, 해독이 ‘불가능‘한 암호화가 아니라 ‘(그만한 자원 투입 가치가 없어) 풀기 어려운‘ 암호화다. 해독 된 결과로 얻을 수 있는 정보가 투입 가능한 자원을 넘어서는 순간 이 ‘어려움‘은 의미가 없어진다. 그래서 이 수학적 난제에 기반한 암호 시스템은 현재의 컴퓨팅 환경 기반에서는 안전했고, 아직 까지도 안전하다. 하지만, ‘양자 컴퓨팅‘이란 새로운 개념에 의해 이 ‘어려움’에 대한 정도가 달라지게 된다.

양자 컴퓨팅과 Q-day

전통적인 컴퓨팅 방식과 달리 양자 컴퓨팅²은 말만 들어도 어려운 양자역학을 이용해 더 빠르게 복잡한 계산을 수행할 수 있다. 여기서 ‘더 빠르게‘의 수준이 기존 컴퓨팅 시스템의 몇십, 몇백 정도의 빠르기가 아니다. 2019년 구글에서 선보인 53큐비트^(qubit) 성능의 시카모어 프로세서는 현존하는 가장 뛰어난 슈퍼컴퓨터 연산능력을 뛰어넘으면서 ‘양자우월성‘ 단계에 도달했음을 보여줬다. 슈퍼컴퓨터로 1만년 걸리는 문제를 3분 20초에 풀 수 있었다.

수학적으로 암호를 풀 수는 있지만, 해독했을 땐 시간이 흘러 해당 정보의 가치가 없어지는 기존의 암호 알고리즘이 무력해질 수 있는 순간이 가까워 오는 것이다. 이러한 양자 취약점^{(QV, Quantum Vulnerability)}으로 양자 컴퓨터가 현재 암호화 시스템을 해독할 수 있게 되는 날을 양자 컴퓨터의 날^(Q-day)라고 한다. 양자 컴퓨터 기술이 계속 발전하는 만큼 ‘Q-day‘를 늦추기 위해 양자 컴퓨터를 사용한 공격에서도 안전할 수 있는 양자 내성 암호³^{(PQC, Post-Quantum Cryptography)}를 만들려는 노력도 현재 진행중이다.

양자 내성 암호

이미 오래 전 부터 양자내성암호의 필요성에 대한 인식이 있었다. 그래서 미국 국립표준기술연구소^(NIST)에서는 양자컴퓨터가 상용화 되고 이를 이용해 암호 시스템을 공격해도, 안전할 수 있는 양자내성 알고리즘 공모를 2016년부터 진행해 왔다. 그리고 2023년 8월 NIST는 양자내성암호^{(PQC, Post-Quantum Cryptography)} 알고리즘 표준 초안⁴을 발표한 바 있다.⁵

NIST의 PQC 초안

2016년 부터 양자내성 알고리즘 공모를 진행해 온 NIST에서, 2023년 8월에 발표한 PQC 표준 초안에는 공개 키 캡슐화 매커니즘, 디지털 서명 체계가 포함되었다. 공개 키 캡슐화 매커니즘은 크리스탈 카이버^{(CRYSTALS-KYBER)}이며, 디지털 서명 체계에는 크리스탈 딜리슘^{(CRYSTALS-Dilithium)}, 팔콘^(FALCON), 스핑크스^(SPHINCS)가 있다.

NIST에서 공모한 양자내성 알고리즘은 양자 컴퓨터 환경을 이용한 공격에 대비한 알고리즘이다. 당연히 현재의 시스템에서도 사용할 수 있는 알고리즘이고, Q-day가 오는 날 취약해질 기존 알고리즘들을 대체할 수 있는 예방안이다. 그리고 양자내성암호 전환을 위한 시나리오와 로드맵도 계속적으로 발표되고 있다.⁶

취약점

KyberSlash

최근 이슈가 된 KyberSlash 공격⁷은 PQC 초안 중 CRYSTALS-Kyber 키 캡슐화 메커니즘^{(KEM, Key Encapsulation Mechanism)}의 구현체^{(implementations)}들에서 발견된 취약점이다. KyberSlash⁸는 시간기반^{(timing-based)} 공격으로, Kyber를 구현한 서비스에서 같은 키 쌍에 대해 다중 작업 요청^{(multiple operation requests)}이 가능할 경우 비밀키를 복원해 낼 수 있다.

Kyber의 구현 문제이기 때문에 어떤 구현체⁹를 사용하느냐에 따라 취약여부가 나뉘게 된다. KyberSlash 사이트에서 취약성이 확인된 라이브러리 목록과 패치 현황¹⁰을 제공하므로, 만약 Kyber 라이브러리를 사용중이라면 확인해 봄이 좋겠다.

TL;DR

NIST에서 발표한 양자내성암호^{(PQC, Post-Quantum Cryptography)} 알고리즘 초안에 포함된 CRYSTALS-Kyber 키 캡슐화 메커니즘^(KEM)의 구현체^{(implementation)}들 중 타이밍 공격으로 비밀키를 복구할 수 있는 취약점이 확인되었다. 알고리즘 자체 취약점이 아닌, 구현체에 존재하는 취약점이므로 취약점 사이트의 라이브러리 목록을 확인해 취약한 버젼은 패치할 수 있도록 하자.

참고자료

공개키 암호 방식_{(위키피디아)}
https://en.wikipedia.org/wiki/Public-key_cryptography ↩︎
양자 컴퓨터_{(위키피디아)}
https://en.wikipedia.org/wiki/Quantum_computing ↩︎
양자 내성 암호_{(위키피디아)}
https://en.wikipedia.org/wiki/Post-quantum_cryptography ↩︎
양자 내성 암호 초안 발표_(NIST)
https://www.nist.gov/news-events/news/2023/08/nist-standardize-encryption-algorithms-can-resist-attack-quantum-computers ↩︎
美 NIST, 포스트 양자 암호화 표준 3종 초안 발표_(CIOKorea)
https://www.ciokorea.com/news/304981 ↩︎
KISA 차세대암호_(KISA)
https://seed.kisa.or.kr/kisa/ngc/pqc.do ↩︎
KyberSlash attacks put quantum encryption projects at risk _{(BleepingComputer)}
https://www.bleepingcomputer.com/news/security/kyberslash-attacks-put-quantum-encryption-projects-at-risk/ ↩︎
KyberSlash
http://kyberslash.cr.yp.to/ ↩︎
KyberSlash – libraries
http://kyberslash.cr.yp.to/libraries.html ↩︎
KyberSlash – libraries
http://kyberslash.cr.yp.to/libraries.html ↩︎

[태그:] KyberSlash attacks

KyberSlash 비밀키 복구 취약점

목차