오늘날의 암호화 프로토콜이 실패하면 기밀 메시지를 보내거나 안전한 금융 거래를 하거나 데이터를 인증하기 위해 온라인 연결을 보호하는 것이 불가능합니다. 누구나 무엇이든 액세스할 수 있습니다. 누구나 누군가를 가장할 수 있습니다. 디지털 경제가 무너질 것입니다.
언제(또는 if) 완전한 기능을 갖춘 양자 컴퓨터를 사용할 수 있게 된다면 바로 그런 일이 일어날 수 있습니다. 그 결과 2017년에 미국 정부의 NIST(National Institute of Standards and Technology)는 "포스트 퀀텀" 암호화를 달성하는 가장 좋은 방법을 찾기 위한 국제 대회를 시작했습니다.
지난 달, 기관은 첫 번째 우승자 그룹을 선택했습니다. XNUMX가지 프로토콜은 약간의 수정을 거쳐 양자 보호막으로 배포될 것입니다. 또한 아직 검토 중인 XNUMX명의 추가 후보자를 발표했습니다.
그런 다음 30월 XNUMX일에 한 쌍의 연구원이 그 후보 중 하나를 깨뜨렸다 노트북에서 한 시간 안에. (그 이후로 다른 사람들은 공격을 더욱 빠르게 만들어 몇 분 만에 프로토콜을 깨뜨렸습니다.) "너무 드라마틱하고 강력한 공격은 ... 꽤 충격이었습니다."라고 말했습니다. 스티븐 갤브레이스, 뉴질랜드 오클랜드 대학의 수학자이자 컴퓨터 과학자. 공격의 기저에 깔린 수학은 놀라웠을 뿐만 아니라 (매우 필요한) 양자 후 암호화의 다양성을 줄여 NIST 경쟁의 대다수 체계와 매우 다르게 작동하는 암호화 프로토콜을 제거했습니다.
"좀 어리둥절하다"고 말했다. 크리스토퍼 파이커트, 미시간 대학의 암호학자.
그 결과는 포스트 퀀텀 암호화 커뮤니티를 흔들고 격려했습니다. 이 공격(그리고 이전 경쟁 라운드의 또 다른 공격)이 갑자기 디지털 강철 문처럼 보였던 것을 젖은 신문으로 바꿨기 때문입니다. "그것은 갑자기 나왔다"고 말했다. 더스틴 무디, NIST 표준화 노력을 주도하는 수학자 중 한 명. 그러나 암호화 체계가 손상될 경우 야생에서 사용되기 훨씬 전에 발생하는 것이 가장 좋습니다. "당신을 통과하는 많은 감정이 있습니다"라고 말했습니다. 데이비드 자오, 캐나다 워털루 대학의 수학자이자 IBM 연구원 루카 데 페오, 2011년에 프로토콜을 제안했습니다. 확실히 놀라움과 실망이 그 중 하나입니다. "하지만 또한," Jao가 덧붙였다. "적어도 지금은 망가졌습니다."
곡선 사이의 비밀 산책
Jao와 De Feo는 잘 알려진 프로토콜과 유사하면서도 적절하게 구별되는 암호화 시스템의 기회를 보았습니다. SIDH(Supersingular isogeny Diffie-Hellman protocol)라고 하는 그들의 계획은 타원 곡선을 처리했습니다. 이는 오늘날 배포되는 가장 널리 사용되는 암호화 유형 중 하나에 사용되는 것과 동일한 수학적 개체입니다. 그러나 완전히 다른 방식으로 사용했습니다. 그것은 또한 NIST가 고려하고 있는 가장 컴팩트한 계획이었습니다(다른 많은 후보보다 느리다는 단점이 있습니다).
그리고 "수학적으로 보면 정말 우아합니다."라고 Jao는 말했습니다. “당시에는 멋진 아이디어처럼 보였습니다.”
Alice와 Bob이라는 두 당사자가 잠재적인 공격자의 감시 아래서도 비밀리에 메시지를 교환하려고 한다고 가정해 보겠습니다. 그래프라고 하는 모서리로 연결된 점 모음으로 시작합니다. 각 점은 다른 타원 곡선을 나타냅니다. 하나의 곡선을 특정 방식으로 다른 곡선으로 변환할 수 있는 경우(등원성이라는 맵을 통해) 점 쌍 사이에 가장자리를 그립니다. 결과 그래프는 거대하고 길을 잃기 쉽습니다. 가장자리를 따라 비교적 짧은 산책을 하면 완전히 무작위로 보이는 어딘가에 있게 될 것입니다.
Alice와 Bob의 그래프는 모두 같은 점을 가지고 있지만 모서리는 다릅니다. 서로 다른 등가에 의해 정의됩니다. Alice와 Bob은 같은 지점에서 시작하여 각자 자신의 그래프에서 임의의 가장자리를 따라 이동하며 한 지점에서 다른 지점으로의 경로를 추적합니다. 그런 다음 각각은 종료 위치를 공개하지만 경로는 비밀로 유지합니다.
이제 그들은 장소를 바꿉니다. Alice는 Bob의 마지막 지점으로 이동하고 Bob은 Alice의 지점으로 이동합니다. 각자의 은밀한 산책을 반복합니다. 그들은 둘 다 같은 지점에서 끝나는 방식으로 이 작업을 수행합니다.
이 위치는 비밀리에 발견되었으므로 Alice와 Bob은 서로의 메시지를 안전하게 암호화하고 해독할 수 있는 정보인 비밀 키로 이 위치를 사용할 수 있습니다. 공격자는 Alice와 Bob이 서로 보내는 중간 지점을 보더라도 Alice 또는 Bob의 시크릿 워크를 알지 못하므로 최종 엔드포인트를 파악할 수 없습니다.
그러나 SIDH가 작동하도록 하려면 Alice와 Bob도 걷기에 대한 몇 가지 추가 정보를 교환해야 합니다. 그 추가 정보가 SIDH의 몰락으로 이어졌습니다.
오래된 수학에 대한 새로운 트위스트
토마스 데크루 SIDH를 깨려고 하지 않았습니다. 그는 이를 기반으로 다른 유형의 암호화를 향상시키는 방법을 일반화하려고 했습니다. 그것은 효과가 없었지만 아이디어를 촉발했습니다. 그의 접근 방식이 SIDH를 공격하는 데 유용할 수 있습니다. 그래서 그는 다가갔다. 우터 캐스트릭, 벨기에 루벤 가톨릭 대학교의 동료이자 그의 전 박사 학위 고문 중 한 명과 두 사람은 관련 문헌에 대해 자세히 알아보았습니다.
그들은 수학자가 발표한 논문을 우연히 발견했습니다. 에른스트 카니 Castryck은 "SIDH에 거의 즉시 적용할 수 있는" 정리였습니다. "우리가 깨달았을 때 ... 공격이 하루나 이틀 만에 매우 빨리 왔다는 것을 깨달았습니다."
궁극적으로 Alice의 비밀 보행(따라서 공유 키)을 복구하기 위해 Castryck과 Decru는 두 개의 타원 곡선의 곱을 조사했습니다. Alice의 시작 곡선과 그녀가 Bob에게 공개적으로 보낸 곡선. 이 조합은 abelian 표면이라고 하는 일종의 표면을 생성합니다. 그런 다음 그들은 이러한 아벨 곡면, Kani의 정리(아벨 곡면을 타원 곡선과 관련시킴) 및 Alice가 Bob에게 제공한 추가 정보를 사용하여 Alice가 취한 각 단계를 알아내었습니다.
Jao는 "이는 [특정 abelian 표면]에 고정할 수 있도록 하는 귀환 신호와 거의 비슷합니다."라고 말했습니다. "그리고 그 신호는 이것이 올바른 [비밀 산책]을 찾기 위해 다음 단계를 밟기 위해 가야 할 길임을 알려줍니다." 이는 곧 Alice와 Bob의 공유 키로 연결되었습니다.
Jao는 "매우 예상치 못한 접근 방식으로 더 복잡한 개체를 사용하여 더 단순한 개체에 대한 결과를 도출할 수 있습니다."라고 말했습니다.
"이 기술이 사용되는 것을 보고 매우 기뻤습니다."라고 말했습니다. 크리스틴 라우터, Meta AI Research의 수학자이자 암호학자로, 등원성 기반 암호화 개발을 도왔을 뿐만 아니라 아벨 표면에서도 작업했습니다. "그것을 [그것]을 부수는 방법으로 생각하지 않은 것이 너무 부끄럽습니다."
Castryck and Decru의 공격은 SIDH 프로토콜의 가장 낮은 보안 버전을 62분 만에, 가장 높은 보안 수준을 단 하루 만에 깨뜨렸습니다. 그리고 얼마 지나지 않아 또 다른 전문가가 낮은 보안 버전을 깨는 데 10분, 높은 보안 버전을 깨는 데 몇 시간이 소요되도록 공격을 조정했습니다. 더 일반적인 공격 지난 몇 주 동안 게시됨 SIDH가 구제될 가능성을 배제합니다.
“특별한 느낌이었어요.” 캐스트릭이 비록 씁쓸하면서도 말했다. "우리가 가장 좋아하는 시스템 중 하나를 죽였습니다."
분수령 순간
시스템이 무조건적으로 안전하다고 보장하는 것은 불가능합니다. 그 대신, 암호 작성자는 충분한 시간 경과와 자신감을 느끼기 위해 문제를 해결하기 위해 노력하는 충분한 사람들에 의존합니다. "그것은 내일 일어나서 누군가가 그것을 수행하는 새로운 알고리즘을 발견했다는 것을 발견하지 못할 것이라는 의미는 아닙니다."라고 말했습니다. 제프리 호프스타인, 브라운 대학의 수학자.
따라서 NIST와 같은 대회가 중요한 이유입니다. NIST 경쟁의 이전 라운드에서 IBM의 암호학자인 Ward Beullens는 다음과 같은 공격을 고안했습니다. Rainbow라는 계획을 깨뜨렸다 주말에. Castryck 및 Decru와 마찬가지로 그는 근본적인 수학적 문제를 다른 각도에서 본 후에야 공격을 준비할 수 있었습니다. 그리고 SIDH에 대한 공격과 마찬가지로 이 공격은 대부분의 제안된 양자 후 프로토콜과 다른 수학에 의존하는 시스템을 깨뜨렸습니다.
"최근 공격은 분수령이었다" 토마스 퍼스트, 스타트업 PQShield의 암호학자. 그들은 포스트 퀀텀 암호화가 얼마나 어려운지, 그리고 다양한 시스템의 보안을 연구하기 위해 얼마나 많은 분석이 필요할 수 있는지 강조합니다. "수학적 객체는 어떤 관점에서는 명백한 구조가 없을 수 있고 다른 관점에서는 악용 가능한 구조를 가질 수 있습니다."라고 그는 말했습니다. "어려운 부분은 올바른 새로운 관점을 식별하는 것입니다."
