잠재적인 암호화 알고리즘을 쉽게 무력화하는 새로운 공격

Apr 14, 2023

댄 구딘, 아르스 테크니카

양자 컴퓨터 시대의 데이터를 보호하기 위한 미국 정부의 지속적인 캠페인에서 단일 기존 컴퓨터를 사용하여 4차 후보를 완전히 무너뜨린 새롭고 강력한 공격은 차세대 암호화 알고리즘 표준화와 관련된 위험을 강조합니다.

이 이야기는 원래 기술 뉴스, 기술 정책 분석, 리뷰 등을 제공하는 신뢰할 수 있는 소스인 Ars Technica에 게재되었습니다. Ars는 WIRED의 모회사인 Condé Nast가 소유하고 있습니다.

지난달 미국 국립표준기술원(NIST)은 양자 컴퓨팅 공격을 견딜 수 없는 RSA, Diffie-Hellman, 타원 곡선 Diffie-Hellman 등의 알고리즘을 대체할 양자 컴퓨팅 이후 암호화 알고리즘 4종을 선정했다. 컴퓨터.

같은 움직임으로 NIST는 추가 테스트를 기다리는 잠재적인 대체 알고리즘으로 4개의 추가 알고리즘을 발전시켰습니다. 그 중 하나 이상이 포스트퀀텀 세계에서 적합한 암호화 대안이 될 수 있기를 바랍니다. 새로운 공격은 후자의 4가지 추가 알고리즘 중 하나인 SIKE를 깨뜨립니다. 이 공격은 NIST가 승인된 표준으로 선택한 4가지 PQC 알고리즘에 영향을 미치지 않으며, 모두 SIKE와 완전히 다른 수학적 기술을 사용합니다.

Supersingular isogeny key encapsulation(초특이성 키 캡슐화)의 약어인 SIKE는 지난 주말에 KU Leuven의 컴퓨터 보안 및 산업 암호화 그룹 연구원들이 발표한 연구 덕분에 더 이상 운영되지 않을 가능성이 높습니다. "SIDH(예비 버전)에 대한 효율적인 키 복구 공격"이라는 제목의 이 논문에서는 복잡한 수학과 기존 단일 PC를 사용하여 SIKE로 보호되는 트랜잭션을 보호하는 암호화 키를 복구하는 기술을 설명합니다. 전체 과정에는 약 1시간 정도만 소요됩니다. 이 업적으로 연구원인 Wouter Castryck과 Thomas Decru는 NIST로부터 50,000달러의 보상을 받을 수 있게 되었습니다.

SIKE의 공동 발명가이자 워털루 대학의 교수인 David Jao는 이메일을 통해 "새로 발견된 약점은 분명히 SIKE에 큰 타격입니다."라고 썼습니다. "공격은 정말 예상치 못한 일입니다."

1970년대 공개 키 암호화의 출현은 획기적인 발전이었습니다. 한 번도 만난 적이 없는 당사자들이 적에 의해 해독될 수 없는 암호화된 자료를 안전하게 거래할 수 있었기 때문입니다. 공개 키 암호화는 메시지를 해독하는 데 사용되는 하나의 개인 키와 암호화에 사용되는 별도의 공개 키를 사용하는 비대칭 키를 사용합니다. 사용자는 자신의 공개 키를 널리 사용할 수 있도록 합니다. 개인 키가 비밀로 유지되는 한 체계는 안전하게 유지됩니다.

실제로 공개 키 암호화는 다루기 힘든 경우가 많으므로 많은 시스템이 이전에 만난 적이 없는 당사자들이 인터넷과 같은 공개 매체를 통해 대칭 키에 공동으로 동의할 수 있도록 하는 키 캡슐화 메커니즘에 의존합니다. 대칭 키 알고리즘과 달리 오늘날 사용되는 키 캡슐화 메커니즘은 양자 컴퓨터에 의해 쉽게 깨집니다. 새로운 공격 이전에 SIKE는 초특이성 동질성 그래프(supersingular isogeny graph)로 알려진 복잡한 수학적 구성을 사용하여 이러한 취약점을 방지하는 것으로 생각되었습니다.

SIKE의 초석은 초특이성 동질성 Diffie-Hellman의 약자인 SIDH라는 프로토콜입니다. 주말에 발표된 연구 논문은 SIDH가 1997년 수학자 Ernst Kani가 개발한 "접착제 분리"라는 정리와 동료 수학자 Everett W. Howe, Franck Leprévost 및 Bjorn이 고안한 도구에 어떻게 취약한지를 보여줍니다. Poonen, 2000. 새로운 기술은 2016년 논문에 설명된 GPST 적응형 공격을 기반으로 구축되었습니다. 최신 공격의 배후에 있는 수학은 수학자가 아닌 대부분의 사람들이 뚫을 수 없다는 것이 보장됩니다. 당신이 얻을 수있는 가장 가까운 것은 다음과 같습니다.

오클랜드 대학교 수학 교수이자 GPST 적응형 공격의 "G"인 스티븐 갤브레이스(Steven Galbraith)는 짧은 글에서 "이 공격은 SIDH에 보조 지점이 있고 비밀 동질성 정도가 알려져 있다는 사실을 이용합니다"라고 설명했습니다. 새로운 공격에 대해. "SIDH의 보조 지점은 항상 성가심이자 잠재적인 약점이었으며 결함 공격, GPST 적응형 공격, 비틀림 지점 공격 등에 악용되었습니다."