퍼블릭 키 암호화 1개와 디지털 서명 알고리즘 3개가 결정됐다. 보안 분야의 새로운 발전을 촉진하는 계기일 수 있다.
양자 컴퓨터의 위력에 맞서 안전한 미래로 가는 길이 조금이나다 더 확실해졌다. 이번 주, 미국 국립표준기술원(National Institute of Standards and Technology, NIST)는 PQC(Pos-Quantum Cryptography) 표준을 위한 3차 콘테스트에서 선택된 알고리즘들을 발표했다.
NIST는 여러 가지를 발표했다. 그 핵심에는 디지털 서명을 위한 키와 CRYSTALS-Dilithium을 규명하기 위한 CRYSTALS-Kyber라는 메인 알고리즘의 선택이 있었다. 둘 다 이론적으로 같은 접근방식을 사용한다. 동시에 구현하기가 더 간단할 수 있는 셈이다. NIST는 또한 디지털 서명 알고리즘 팔콘(Falcon)과 SPHINCS+를 표준화할 것이라고 발표했다. 또한 다른 여러 알고리즘을 지속적으로 연구할 것이며 4차 콘테스트에서 추가적으로 표준화될 수 있다고 전했다.
NIST는 당초 결과가 2022년 초에 발표될 것이라고 약속했던 바 있다. 그러나 이후 기술 외적인 이유로 인해 결과가 지연됐다. 참고로 이 콘테스트는 2016년에 시작되었으며 서서히 발전하고 있다. 몇 년에 걸쳐 새 알고리즘의 약점이 드러날 수 있으며, 때로는 잠재적인 문제가 수십 년 동안 드러나지 않는다. NIST가 2명의 우승자를 선택한 가운데, 다수의 차점자를 지명한 배경이다.
2020년, 2차 대회 종료 후 NIST는 7개의 알고리즘을 결승 출전자로 선택하고 8개를 추가 연구용 대안으로 지정했다. 그 이후로 학계와 전문가들은 알고리즘을 조사하고 약점을 조사했으며 잠재적인 공격을 조사했다. NIST는 또한 NSA 같은 정부기관에게 평가를 요청했다.
이 콘테스트는 오늘날 보편적인 알고리즘 중 일부가 양자 컴퓨터의 등장으로 인해 위협받을 수 있다는 우려로 인해 시작됐다. RSA나 ‘Diffie-Hellman’ 같은 알고리즘의 경우 유한체 또는 링에서의 반복적인 누승법(repeated exponentiation in a finite field or ring)에 의존하기에, 쇼어(Shor)의 알고리즘으로 손쉽게 파훼될 수 있다. 생략된 곡선을 사용하는 다른 보편적인 암호 기법 시스템도 위협받을 수 있다.
양자 컴퓨팅에 취약할 수 있는 알고리즘 집단에는 오늘날 디지털 서명 또는 키 협상을 위해 보편적으로 사용되는 다수의 표준이 포함되어 있다. 가령 FIPS(Federal Information Processing Standard) 186-4, DSS(Digital Signature Standard) 등에는 NIST의 승인을 받은 3가지 디지털 서명 알고리즘(DSA, RSA, ECDSA)이 포함되어 있다. 모두 효과적인 양자 머신으로 파괴될 가능성을 가진다.
AES 또는 SHA256 등의 일부 대칭 알고리즘은 다른 기법을 사용하기 때문에 쇼어의 알고리즘에 덜 취약할 수 있다. 하지만 그로버(Grover)의 알고리즘 등이 부분적인 공격을 지원할 수 있다.
CRYSTALS 알고리즘이란?
왕관을 차지한 2개의 CRYSTALS(Cryptographic Suite for Algorithmic Lattices) 알고리즘은 “MLWE(Module Learning With Error) 문제”의 강도를 활용한다. 이 문제는 여러 샘플 포인트를 취할 때, 그 중 일부가 오답지가 될 수 있으며, 이를 생성하는 기능을 결정 또는 ‘학습’한다. 이는 암호 기법 알고리즘의 상대적으로 새로운 기초다. 강력한데다 충분히 다르기 때문에 이를 신속하게 해결할 수 있는 알려진 양자 알고리즘이 아직 존재하지 않는다.
CRYSTALS 알고리즘은 대수학자들에게 ‘2의 거듭제곱 원분 링’(power-of-two cyclotomic ring)으로 알려진 것에서 비롯된 포인트들의 형태(Form of points)를 이용한다. ‘2의 거듭제곱 원분 링’은 표준 CPU를 이용한 컴퓨팅을 간결하면서도 빠르게 만든다. 이 알고리즘의 평가 결과가 향후 도입 속도를 결정하게 된다.
팔콘 및 SPHINCS+ 알고리즘이란?
NIST는 또한 주요 선택지을 보완하기 위해 팔콘과 SPHINCS+라는 2개의 다른 알고리즘을 표준화했다. 팔콘은 크기가 중요한 일부 애플리케이션에 필수적일 수 있는 더 작은 디지털 서명을 제공할 수 있다.
SPHINCS+는 상태 없는 해시 기반 알고리즘으로 매우 다른 접근방식을 사용한다. 이미 사용할 수 있는 여러 표준 해시 알고리즘 중 하나를 활용하는 방식을 취한다. NIST는 다른 알고리즘에 광범위한 약점이 드러나는 경우 좋은 백업 옵션이 될 수 있을 것으로 기대하고 있다. 다른 알고리즘처럼 격자 산술에 의존하지 않아서다.
4개의 암호화 알고리즘은 여전히 연구 중
한 가지가 더 있다. 다른 4개의 알고리즘이 4차 콘테스트에 맞춰 발전하고 있다. 메인 표준 또는 심지어 제1 대안까지는 아닐 수 있지만, 위원회는 첫번째 선택지에서 약점이 드러나는 것에 대비하여 실험과 테스트를 권장하고 있다. 4개는 각각 BIKE, Classic McEliece, HQC, SIKE라고 불린다. 모두 다른 수학적 문제에 의존하기에, MLWE에 대한 공격에 영향 받지 않는다.
이 4개의 알고리즘에 대한 계획은 각기 다르다. 발표에서 NIST는 4차 프로세스 종료 후 추가 표준으로써 구조화된 코드의 문제에 기초하여 개발된 알고리즘인 BIKE 또는 HQC를 선택할 것이라고 밝혔다.
SIKE와 McEliece는 아직 완전한 표준화될 만큼 충분히 매력적이지는 않지만 가능성을 가진다. 예를 들어, SIKE는 작은 키와 암호문을 제공한다고 전해진다. NIST는 4차 대회 종료 후 둘 중 하나를 완전한 표준으로 선택할 수 있다고 밝혔다.
NIST는 CSRC(Computer Security Resource Center)에서 공개될 NISTIR(NIST Interagency 또는 Internal Report) 8413, ‘3차 NIST 후기 양자 암호 기법 표준화 프로세스에 관한 실패 보고서’에서 자세한 내용을 배포할 방침이다. 4차 NIST PQC 표준화 컨퍼런스는 2022년 11월 29일부터 12월 1일에 열릴 예정이다.
4차 프로세스에서는 앞선 3개 콘테스트에서와 마찬가지로 NIST가 업계로부터 의견을 구한 후 알고리즘을 개선하게 된다. 이와 동시에 그들은 알고리즘을 현실에 구현하기 위한 더욱 구체적인 표준을 규정된다.
그러나 이 프로세스는 끝나려면 멀었다. 발표에서 NIST는 알고리즘이 “서명 포트폴리오를 다각화하는 [새로운 제안을 요청할 것이다] 구조화된 격자에 기초하지 않는 서명 스키마가 가장 큰 관심사”라고 밝혔다.
보안 분야에 미칠 실질적인 영향은?
이제 현실의 보안팀은 새로운 표준을 선택할 수 있다. 메인 CRYSTALS 표준이 분명 관심을 받을 전망이다. 그러나 신중한 개발자라면 일부 또는 모든 대안을 지원하는 방법도 연구하려 할 가능성이 높다.
하지만 서두를 필요는 없다. 시스템을 능동적으로 방어해야 하는 사람들일지라도 현재로서는 미래 계획만 세우면 된다. Log4J 라이브러리에서 발견된 것과 같은 보편적인 코드 베이스의 결함과는 다르다. 상당한 성능을 가진 양자 컴퓨터가 등장한 이후에나 현실적인 문제로 부상할 것이기 때문이다. 이 콘테스트의 목적 또한 강력한 양자 머신이 마법처럼 등장하는 경우에 대비하여 대안을 마련하는 것이었다.
하지만 이 발표 덕분에 암호 기법 라이브러리 개발자는 앞으로 새로운 표준을 제안하기 시작할 수 있다. 물론 전통적인 표준 대신에 CRYSTALS 알고리즘을 사용하는 현실적인 옵션을 개발자들이 가지기까지는 몇 년이 소요될 수 있다.
아키텍트와 엔지니어는 기존 표준의 대안으로써 사양에 이런 새로운 알고리즘을 추가하기 시작할 수 있다. 그러면 새로운 디자인이 향후 더 큰 탄력을 받게 될 것이다.
보안 전문가들에게는 양자 하드웨어의 느린 개발 속도가 한편으로 안심이 될 것이다. 아직 보안에 직접적인 영향을 미치는 머신에 관한 발표는 사실상 없다. 구글(Google)이 ‘양자우위’에 관한 소식을 자랑스럽게 발표했지만 여기에는 쇼어의 알고리즘을 실행하는 다른 유형의 계산이 필요하다.
또 RAS를 공격 시나리오를 연구원들은 알려진 구조를 가진 정수에 집중하는 경우가 많다. 일부 비평가들이 이런 시도에 대해 계산을 시작하기 전에 답을 아는 것에 의존하는 ‘스턴트’라고 말했던 이유다. 비평가들은 유용한 이벤트이자 귀중한 실험이지만 현재의 보안을 위협하는 수준은 아닐 것이라고 지적하고 있다. 공격을 위해서는 특수한 구조 없이 임의의 큰 수를 공격할 수 있는 능력이 필요하기 때문이다.
에릭슨(Ericsson)의 보안 전문가 존 매슨은 양자 하드웨어 개발의 진행속도가 초기 약속보다 느린 양상이라고 말했다. 매슨은 “양자 컴퓨팅에 참여하는 연구원들이 다소 낙관적인 태도를 보이곤 했다. 물론, 양자 컴퓨팅을 개발하는 연구원들의 예상이 맞을 수 있지만 역사적으로 연구원들은 자신의 연구가 상업적 영향을 미칠 때 과도하게 낙관적인 경우가 많았다”라고 말했다.
즉 양자 컴퓨터는 문 앞을 배회하는 늑대만큼 위험한 수준은 아니다. 그럼에도 불구하고 이 대회는 CISO와 다른 보안 전문가가 미래에 대한 계획을 검토할 수 있는 기회를 제공한다. 이 프로세스는 새로운 알고리즘과 새로운 기법을 성숙시킬 기회를 제공한다. 이것들은 기존의 프로토콜을 갱신하고 기존의 표준에 백업 옵션을 제공할 수 있다. dl-ciokorea@foundryco.com
