NIST 포스트

Apr 07, 2023

에 의해

플립보드

레딧

핀터레스트

왓츠앱

왓츠앱

이메일

NIST 포스트 양자 암호화 대회에 제출된 알고리즘과 4라운드에 진출한 알고리즘이 패배했습니다. SIKE(Supersingular Isogeny Key Encapsulation) 알고리즘은 KU Leuven의 Wouter Castryck과 Thomas Decru에 의해 깨졌으며, 이 프로세스는 2022년 7월 말에 작성된 논문에 설명되어 있습니다.

암호학자들은 그러한 사건에 놀라지 않습니다. 그러나 양자 컴퓨터가 등장한 후 비밀을 보호하는 능력에 대해 우려하는 보안 리더는 그 의미를 고려해야 합니다.

암호학자의 경우

SIKE의 패배는 Supersingular Isogeny Diffie-Hellman 키 교환 프로토콜에 대한 키 복구 공격과 NIST 경쟁에서 SIKE로 인스턴스화됨에 따른 것입니다. 이 공격은 수학자 에른스트 카니(Ernst Kani)가 1997년에 개발한 '접착제와 분리' 정리에 기반을 두고 있습니다.

특히, 두 연구원은 "우리의 공격은 시작 곡선에 작은 비-스칼라 엔도모피즘(endomorphism)의 존재를 이용하고, 프로토콜 중에 Alice와 Bob이 공유하는 보조 비틀림 지점 정보에도 의존합니다"라고 말합니다.

공격은 연구원의 자체 Magma 코드를 사용하여 Bob의 비밀 키를 표적으로 삼습니다. Alice의 키를 대상으로 하는 데 사용될 수도 있지만 전자가 더 빠른 결과를 산출합니다. 이는 개별 키에 대한 무차별 대입 공격이 아니라 암호화 알고리즘에 대한 수학적 공격입니다.

공격은 단일 클래식 컴퓨터, 특히 Intel Xeon CPU에서 실행되었습니다. "단일 코어에서 실행된 추가된 Magma 코드는 Microsoft SIKE 문제를 각각 약 4분과 6분 만에 깨뜨렸습니다. 이전에 NIST의 양자 보안 레벨 1을 충족한다고 믿었던 SIKE 매개변수에 대한 실행에는 다시 약 62분이 걸렸습니다. 단일 코어에."

이번 패배로 SIKE가 NIST 경쟁에서 효과적으로 제외되었지만 알고리즘이 수정되어 경쟁에 복귀하는 것을 반드시 막지는 않습니다.

나머지 우리를 위해

SIKE는 신뢰할 수 없는 네트워크를 통해 소스에서 대상으로 키를 안전하게 전달하도록 설계된 키 캡슐화 알고리즘입니다. 이는 양자 증거로 설계되었으며 NIST 경쟁에서 가장 강력한 후보 중 하나로 생각되었습니다.

한 시간 남짓 만에 단일 PC에서 NIST 최종 후보 양자 증명 암호화 알고리즘이 패배하는 것은 극적입니다. 이는 일반적인 암호화, 특히 포스트 양자 암호화에 대한 우리의 태도를 다시 생각해 볼 필요가 있음을 시사합니다. SIKE는 퀀텀 이전 또는 이후의 다른 암호화와 다르지 않습니다. 안전하지 않을 때까지만 안전하며, 크랙이 가능해지자마자는 아닙니다.

암호화 전문가, 특히 국가로부터 자금을 지원받는 암호화 전문가는 암호화 알고리즘을 무력화할 방법을 지속적으로 모색하고 있습니다. 이론적으로는 어제 SIKE에 일어난 일이 내일 RSA에도 일어날 수 있습니다. 알고리즘 크랙이 제로데이 취약점과 다른 유일한 점은 전자에 대해 들을 가능성이 없다는 것입니다. 도난 및 저장된 데이터에 대해 국가에서 발견한 알고리즘 크랙을 사용하는 것은 대중에게 알려질 가능성이 없습니다.

따라서 사실상 암호화를 사용하는 것은 믿음의 도약입니다. 우리는 그것이 안전하다는 말을 들었고 이것을 믿지 않을 이유가 없습니다. 그러나 우리는 이것에 대한 절대적인 지식을 갖고 있지도 않고 가질 수도 없습니다. 암호화는 수학적 문제를 기반으로 하기 때문에 알고리즘이 수학적으로 공격받을 가능성이 항상 존재하며, 특히 강력한 양자 컴퓨터에 의해 공격받을 가능성이 항상 존재합니다.

새롭고 아직 시간 테스트를 거치지 않은 알고리즘을 위해 기존의 신뢰할 수 있는 알고리즘을 변경해야 하는 현재의 요구는 암호화 민첩성(crypto agility)으로 알려진 개발 관행을 촉진하고 있습니다. 사용 중인 알고리즘이 중단되면 시스템 인프라를 크게 변경하지 않고도 다른 알고리즘으로 교체할 수 있다는 아이디어입니다.

이는 좋은 관행이지만 양자 컴퓨터에서 발생하는 근본적인 '지금 수확하고 나중에 해독'하는 문제를 해결하지 못합니다. NIST 권장 알고리즘이 안전하다고 판단되어 실패할 때까지 10년 동안 사용된다면, 해당 10년 동안 공격자가 가로채고 저장한 모든 통신을 즉시 해독할 수 있습니다. 그때와 지금의 유일한 차이점은 이것이 현재의 공개 키 암호화(Shor의 알고리즘 덕분에)에 일어날 것이라는 것을 알고 있지만 새로운 포스트 양자 알고리즘에서는 그런 일이 일어나지 않을 것이라는 점을 알 수 없다는 것입니다.