포스트 퀀텀 암호화 – "60분 만에 사라진" 새로운 알고리즘

우리는 PQC에 대해 썼습니다. 포스트 양자 암호화, 전에 여러 번.

소위 양자 컴퓨팅에 대한 지난 몇 년간의 모든 미디어 흥분을 놓쳤다면…

… 그것은 (일부 전문가들이 아마도 무모한 과도하게 단순화한다고 생각할 것을 용서한다면) 추적할 수 있는 컴퓨팅 장치를 구축하는 방법입니다. 여러 가능한 결과 동시에 계산합니다.

많은 주의와 약간의 운이 있으면 가능한 모든 결과를 시도하고 테스트하지 않고도 올바른 답을 찾기 위해 일부 유형의 알고리즘을 다시 작성하거나 적어도 많은 오답을 올바르게 버릴 수 있음을 의미합니다. 하나씩.

적절하게 강력하고 신뢰할 수 있는 장치를 실제로 구성할 수 있다고 가정하면 양자 컴퓨팅 장치를 사용하여 두 가지 흥미로운 암호 분석 속도 향상이 가능합니다.

• Grover의 양자 탐색 알고리즘. 일반적으로 무작위로 정렬된 답변 세트를 검색하여 귀하의 답변이 목록에 있는지 확인하려는 경우 최종 답변을 얻기 전에 최악의 경우 전체 목록을 샅샅이 뒤져야 합니다. 예를 들어, 문서의 스크램블을 해제하기 위해 128비트 AES 암호 해독 키를 찾으려면 다음에서 시작하여 가능한 모든 키 목록을 검색해야 합니다. 000..001, ..2, ..3, 등등, 모든 방법 FFF..FFF (16바이트의 FF), 문제를 완료하는지 확인합니다. 즉, 2가지를 모두 시도하려면 예산을 세워야 합니다.¹²⁸ 올바른 키를 찾거나 존재하지 않는 것으로 결정하기 전에 가능한 키. 그러나 Grover의 알고리즘은 충분히 크고 강력한 양자 컴퓨터를 사용하여 동일한 위업을 완료할 수 있다고 주장합니다. 제곱근 이론상 단 2분만에 코드를 해독할 수 있습니다.⁶⁴ 대신 시도합니다.
• 쇼어의 양자 인수분해 알고리즘. 여러 현대 암호화 알고리즘은 두 개의 큰 소수를 빠르게 곱할 수 있다는 사실에 의존하는 반면, 해당 곱을 처음 시작했던 두 개의 숫자로 다시 나누는 것은 불가능합니다. 이에 대한 느낌을 얻으려면 펜과 종이를 사용하여 59×87을 곱해 보십시오. 그것을 꺼내는 데 5133분 정도 걸릴 수 있지만(4171이 답입니다) 그렇게 어렵지 않습니다. 이제 다른 방법을 시도하십시오. 예를 들어 43을 다시 두 가지 요소로 나눕니다. 훨씬 더 열심히! (97×600입니다.) 이제 600자리 숫자로 이 작업을 수행한다고 상상해 보십시오. 느슨하게 말해서, 잭팟이 터지거나 답이 없다는 것을 발견할 때까지 300자리 숫자를 가능한 모든 XNUMX자리 소수로 나누려고 애쓰는 데 매진하고 있습니다. 그러나 Shor의 알고리즘은 이 문제를 다음과 같이 해결할 것을 약속합니다. 로그 평소의 노력. 따라서 2048개의 이진 숫자를 인수분해하는 데 1024비트 숫자를 인수분해하는 것보다 두 배만 더 오래 걸리고 2047비트 숫자를 인수분해하는 것보다 두 배는 더 오래 걸리지 않습니다. 이는 엄청난 속도 향상을 나타냅니다.

위협 대응

Grover 알고리즘의 위협은 사용 중인 숫자의 크기를 제곱함으로써 간단히 대응할 수 있습니다. 이는 암호화 해시 또는 대칭 암호화 키의 비트 수를 두 배로 늘리는 것을 의미합니다. (즉, 지금 SHA-256이 괜찮다고 생각한다면 대신 SHA-512를 사용하는 것이 PQC 내성 대안을 제공할 것입니다.)

그러나 Shor의 알고리즘은 그렇게 쉽게 반박될 수 없습니다.

2048비트의 공개 키는 단순히 제곱하는 것이 아니라 기하급수적으로 크기를 늘려야 하므로 2×2048=4096비트의 키 대신 불가능한 크기 2의 새 키가 필요합니다.²⁰⁴⁸ 비트…

… 그렇지 않으면 Shor의 알고리즘이 적용되지 않은 완전히 새로운 종류의 양자 후 암호화 시스템을 채택해야 합니다.

음, 미국 표준 기구인 NIST가 운영하고 있습니다. PQC "경쟁" 2017 년 말부터.

이 프로세스는 모든 참가자를 환영하고 모든 알고리즘이 공개적으로 게시되며 공개 조사가 가능할 뿐만 아니라 모든 사람에게 공개되었습니다. 적극적으로 격려:

제안을 요청하십시오. [2017-11-30 마감]. [...] 새로운 공개 키 암호화 표준은 전 세계적으로 사용 가능하고 민감한 정부 정보를 보호할 수 있는 하나 이상의 추가 미분류 공개 디지털 서명, 공개 키 암호화 및 키 설정 알고리즘을 지정하기 위한 것입니다. 양자 컴퓨터의 출현 이후를 포함하여 예측 가능한 미래까지.

XNUMX차례의 제출과 토론 끝에 NIST 발표, 2022-07-05에 즉시 효과가 있는 "표준"으로 간주되는 XNUMX가지 알고리즘을 선택했으며 모두 유쾌한 이름을 가졌습니다. CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON및 SPHINCS+.

첫번째 (CRYSTALS-KYBER)라고 하는 것으로 사용됩니다. 키 동의 메커니즘 (KEM), 공개 통신 채널의 양 끝이 세션 가치의 데이터를 기밀로 교환하기 위해 일회성 개인 암호화 키를 안전하게 구성합니다. (간단히 말해서: 스누퍼는 양배추를 갈가리 찢기 때문에 대화를 엿들을 수 없습니다..)

나머지 세 가지 알고리즘은 다음을 위해 사용됩니다. 디지털 서명, 이렇게 하면 끝에서 얻은 데이터가 보낸 사람이 다른 사람에게 넣은 것과 정확히 일치하는지 확인하여 변조를 방지하고 무결성을 보장할 수 있습니다. (간단히 말해서: 누군가 데이터를 손상시키거나 엉망으로 만들려고 하면.)

더 많은 알고리즘이 필요함

NIST는 새로운 표준을 발표함과 동시에 네 번째 라운드 가능한 대안 KEM으로 앞으로 XNUMX개의 알고리즘을 추가로 제시합니다. (이 글을 쓰는 시점에서 우리는 이미 XNUMX개의 승인된 디지털 서명 알고리즘 중에서 선택할 수 있지만 공식 KEM은 하나만 있음을 기억하십시오.)

이것들은: BIKE, Classic McEliece, HQC 과 SIKE.

흥미롭게도, McEliece 알고리즘 1970년대에 미국 암호학자 로버트 맥 엘리스(Robert Mc Eliece)가 2019년에 세상을 떠났습니다.

그러나 오늘날 인기 있는 대안인 Diffie-Hellman-Merkle 알고리즘(DHM 또는 때로는 그냥 DH)에 비해 엄청난 양의 키 자료가 필요했기 때문에 결코 인기를 끌지 못했습니다.

불행히도, 세 가지 라운드 XNUMX 알고리즘 중 하나, 즉 SIKE, 금이 간 것 같습니다.

라는 제목의 뇌를 뒤틀린 논문에서 SIDH에 대한 효율적인 키 복구 공격(예비 버전), 벨기에 암호학자 Wouter Castryk와 Thomas Decru가 SIKE 알고리즘에 치명적인 타격을 가한 것 같습니다.

궁금한 점이 있으시면 SIKE는 Supersingular Isogeny 키 캡슐화, SIDH는 초특이 등원성 Diffie-Hellman, 특정 용도 SIKE 알고리즘 이로써 통신 채널의 두 끝은 DHM과 같은 "암호화"를 수행하여 각 끝이 일회용 비밀 암호화 키로 사용할 개인 값을 도출할 수 있는 많은 공개 데이터를 교환합니다.

우리는 여기에서 공격을 설명하려고 하지 않을 것입니다. 우리는 단지 그 논문이 주장하는 바를 반복할 것입니다:

매우 느슨하게 말해서 여기 입력에는 프로세스에서 사용되는 미리 결정된(따라서 공개적으로 알려진) 매개변수와 함께 키 설정 암호 댄스의 참가자 중 한 명이 제공한 공개 데이터가 포함됩니다.

그러나 추출된 출력( 동질성 φ 위)는 프로세스의 한 번도 공개되지 않은 부분(소위 개인 키)으로 간주됩니다.

즉, 키 설정 중에 공개적으로 교환된 데이터와 같은 공개 정보만으로도 암호 작성자는 참가자 중 한 명의 개인 키를 복구할 수 있다고 주장합니다.

그리고 일단 내 개인 키를 알게 되면 쉽게 감지할 수 없는 방식으로 나를 가장할 수 있으므로 암호화 프로세스가 중단됩니다.

분명히 키 크랙 알고리즘은 일상적인 랩톱에서 찾을 수 있는 처리 능력을 가진 단일 CPU 코어를 사용하여 작업을 수행하는 데 약 XNUMX시간이 걸립니다.

이는 NIST의 기본 암호화 보안 등급인 레벨 1을 충족하도록 구성된 SIKE 알고리즘에 위배됩니다.

무엇을해야 하는가?

아무것도!

(좋은 소식입니다.)

논문의 저자가 제안한 바와 같이, 그들의 결과는 아직 예비적이라는 점을 지적한 후, "현재 상황에서 SIDH는 공개적으로 생성된 기본 곡선에 대해 완전히 깨진 것으로 보입니다."

(그건 나쁜 소식이야.)

그러나 SIKE 알고리즘이 아직 공식적으로 승인되지 않았다면 이제 이 특정 공격(저자들이 가능하다고 인정한 것)을 막기 위해 조정되거나 완전히 삭제될 수 있습니다.

SIKE에 마지막으로 무슨 일이 일어나든 이것은 왜 자신의 암호화 알고리즘을 발명하려는 시도가 위험에 처해 있는지를 잘 일깨워주는 것입니다.

또한 독점 암호화 시스템이 왜 알고리즘 자체의 비밀에 의존 2022년에는 보안을 유지하기 위해 절대 용납할 수 없습니다.

SIKE와 같은 PQC 알고리즘이 공개 조사 대상이 될 수 있도록 구체적으로 공개되었음에도 불구하고 전 세계 전문가들의 설득과 검증을 XNUMX년 이상 견뎌냈다면…

...그렇다면 집에서 만든 숨겨진 암호화 알고리즘이 야생에 출시될 때 얼마나 잘 작동할 것인지 자문할 필요가 없습니다!