10년의 데스크톱, 단일 코어 양자 암호화 알고리즘이 1시간 만에 해독됨, 암호 작성자: 너무 갑작스럽습니다.

미래의 양자 컴퓨터는 현대 암호화를 빠르게 깨뜨릴 수 있습니다. 따라서 수학자 및 암호학자들은 양자 컴퓨터 공격에 저항할 수 있는 적합한 새로운 암호화 알고리즘을 찾고 있습니다. 기존 암호화 알고리즘에 대한 양자 컴퓨터 공격에 저항할 수 있는 이 새로운 세대의 암호화 알고리즘을 "포스트 양자 암호화(PQC, PostQuantum Cryptography)" 알고리즘이라고 합니다.

그러나 최근 벨기에 루벤 대학의 연구원들은 유망한 PQC 암호화 알고리즘이 단 1시간 만에 완전히 해독될 수 있음을 발견했습니다(일부 버전은 단 4분 만에 해독될 수 있음). 문제는 이 기록이 고성능 컴퓨터가 아닌, 10년 된 CPU를 탑재하고 싱글 코어로 구동되는 데스크톱 컴퓨터에서 세운 기록이라는 점이다. 연구원들은 이 최근의 놀라운 실패가 포스트 양자 암호화가 채택되기 전에 극복해야 할 많은 장애물을 강조한다고 말합니다.

논문 링크: https://eprint.iacr.org/2022/975

이론적으로 양자 컴퓨터는 기존 컴퓨터가 해결하는 데 많은 시간이 걸리는 문제를 빠르게 해결할 수 있습니다. 예를 들어, 현대 암호화는 큰 수의 인수분해와 같은 복잡한 수학적 문제를 처리할 때 기존 컴퓨터가 직면하는 극도의 어려움에 크게 의존합니다. 그리고 양자 컴퓨터는 원칙적으로 이 암호화 기술을 빠르게 깨뜨릴 수 있는 알고리즘을 실행할 수 있습니다.

이 위협에 대처하기 위해 전 세계 암호학자들은 포스트퀀텀 암호화 알고리즘을 설계하는 데 20년을 보냈습니다. 이러한 알고리즘은 양자 컴퓨터와 고전 컴퓨터 모두에서 해결하기 어려운 새로운 수학적 문제를 기반으로 합니다.

수년간 NIST(국립표준기술연구소)와 같은 기관의 연구원들은 어떤 PQC 알고리즘이 세계가 채택할 수 있는 새로운 표준이 되어야 하는지 연구해 왔습니다. 해당 기관은 2016년에 후보 PQC 알고리즘을 찾고 있다고 발표했으며 2017년에는 82개의 제안을 받았습니다. 이후 3차례의 검토를 거친 후 NIST는 곧 표준이 될 4가지 알고리즘과 다음 검토 라운드에 가능한 경쟁자로 포함될 4가지 알고리즘을 추가로 발표했습니다.

리뷰가 아직 끝나지 않았고, 경쟁자 중 하나가 이미 다운되었으며, 10년 된 데스크탑에 의해 손상되었습니다. 이 알고리즘은 SIKE(Supersingular Isogeny Key Encapsulation)라고 하며 Microsoft, Amazon, Cloudflare 등에서 연구되었습니다. 미시간대학교 앤아버 캠퍼스의 암호학자인 크리스토퍼 페이커트는 "이번 공격은 너무 갑작스러워서 묘책(극도의 효율성을 지닌 솔루션)이었다"고 말했다.

SIKE 알고리즘이란?

SIKE는 타원 곡선과 관련된 PQC 알고리즘 제품군입니다. NIST의 수학자 Dustin Moody는 "타원 곡선은 오랫동안 수학자들의 연구 주제였습니다."라고 말했습니다. "이들은 y^2 = x^3 + Ax + B와 유사한 방정식으로 설명됩니다. 여기서 A와 B는 숫자입니다. 예를 들어 타원 곡선은 y^2 = x^3 + 3x + 2가 될 수 있습니다."

1985년에 "수학자들은 현재 널리 배포되는 타원 곡선을 포함하는 암호화 시스템을 만드는 방법을 알아냈습니다"라고 Moody는 말했습니다. "그러나 이러한 타원 곡선 암호 시스템은 양자 컴퓨터의 공격에 취약합니다."

2010년경 연구원들은 암호학에서 타원 곡선을 사용하는 새로운 방법을 발견했습니다. 이 새로운 아이디어는 양자 컴퓨터의 공격에 취약하지 않은 것으로 여겨진다.

이 새로운 방법은 타원 곡선의 두 점을 어떻게 추가하여 타원 곡선의 다른 점을 얻을 수 있는지에 대한 질문을 기반으로 합니다. 알고리즘 이름의 "동질성"은 추가 법칙을 유지하는 하나의 타원 곡선에서 다른 곡선으로의 매핑인 상동성을 의미합니다.

"이 매핑을 충분히 복잡하게 만들면 데이터 암호화의 과제는 두 개의 타원 곡선이 주어지면 둘 사이의 상동성을 찾는 것이 매우 어렵다는 것입니다."라고 연구 공동 저자인 Thomas Decru는 말했습니다. 벨기에 루벤대학교의 수학 암호학자.

SIKE는 SIDH(Super Singular Homology Diffie-Hellman) 키 교환 프로토콜을 기반으로 하는 상동성 기반 암호화의 한 형태입니다. Decru는 "SIDH/SIKE는 최초의 실용적인 원본 기반 암호화 프로토콜 중 하나입니다."라고 말했습니다.

그러나 SIKE에는 한 가지 약점이 있습니다. 작동하려면 대중에게 추가 정보, 즉 보조 트위스트 포인트를 제공해야 합니다. Moody는 "적들은 한동안 이 추가 정보를 이용하려고 시도했지만 이를 사용하여 SIKE를 물리치는 데 성공하지 못했습니다"라고 말했습니다. "그러나 이 새로운 논문은 꽤 진보된 수학적 방법을 사용하여 방법을 찾았습니다. "

이 새로운 공격을 설명하기 위해 Decru는 타원 곡선이 1차원 개체이지만 수학에서는 타원 곡선이 2차원 또는 다른 차원 개체로 시각화될 수 있다고 말했습니다. 이러한 일반화된 개체 사이에 상동체를 만들 수도 있습니다.

25년 된 정리를 적용하여 새로운 공격은 SIKE가 노출한 추가 정보를 사용하여 2차원 상동성을 구성합니다. 그런 다음 이 상동성을 사용하여 SIKE가 메시지를 암호화하는 데 사용하는 키를 재구성할 수 있습니다.

메릴랜드 대학, 칼리지 파크의 암호학자 조나단 카츠는 "나에게 가장 놀라운 것은 이번 공격이 갑자기 나타난 것 같다는 것"이라고 말했습니다. 그는 새로운 연구에 참여하지는 않았지만 "SIKE에 어떤 약점이 있다는 것을 나타내는 이전 결과가 거의 없었는데, 이 결과가 SIKE에게 완전한 키를 찾아냈기 때문에 갑자기 완전히 파괴적인 공격을 가하게 됐다"고 말했다.

공격하는데 10년 넘게 걸렸고, 크랙하는데 4분 걸렸다. 위에서 언급한 새로운 공격 방법을 기반으로 한 알고리즘을 사용해 연구진은 10년이 걸리는 컴퓨터를 탑재한 기계를 발견했다. "오래된" CPU(Intel Xeon CPU E5-2630v2)를 탑재한 데스크톱 컴퓨터에서 특정 SIKE 알고리즘으로 보호되는 키를 찾는 데는 최소 4분밖에 걸리지 않으며, SIKE 알고리즘을 깨는 데도 단 4분밖에 걸리지 않습니다. 이는 NIST 양자 보안 레벨 1 표준을 충족하는 것으로 간주됩니다. 이 실험은 CPU의 한 코어에서 실행됩니다.

"보통 암호화폐 시스템에 대한 심각한 공격은 시스템이 제안된 직후 또는 시스템이 처음으로 모든 사람의 관심을 끌었을 때 발생합니다. 시간이 지남에 따라 공격은 점차 강해지거나 시스템이 크게 약화됩니다. 그러나 거기에 있었습니다. Peikert는 이 공격에 대한 경고가 없었고 암호화 시스템이 갑자기 완전히 깨졌다고 말했습니다. "SIDH가 처음 제안된 이후 이 완전한 돌파구가 나올 때까지 지난 12년 동안 SIDH/SIKE에 대한 공격은 거의 진전이 없었습니다.

.

연구원들이 SIKE를 10년 넘게 테스트해 왔음에도 불구하고 SIKE가 표준으로 선택되지 않은 이유 중 하나는 너무 새롭고 충분히 연구되지 않았다는 우려였습니다. 오클랜드 대학의 수학자 스티븐 갤브레이스(Steven Galbraith)는 "사람들은 SIKE가 대규모 공격의 위험에 처할 수 있다고 걱정했는데, 결과적으로 그들의 생각이 옳았다"고 말했습니다. Galbraith는 새로운 공격이 "매우 진보된 수학을 적용"하는 것이 중요한 이유라고 믿습니다. Katz는 "PQC의 기본 수학과 필요한 암호화 지식을 모두 갖춘 사람은 전 세계에 50명 미만인 것으로 생각됩니다."라고 말했습니다. 또한 PQC 스타트업 Sandbox AQ의 암호화 전문가인 David Joseph은 한 번은 다음과 같이 말했습니다. "구현 관점과 이론적 관점 모두에서 동일한 기원 문제는 "악명이 높으며" 나중에 근본적인 결함이 발견될 가능성이 더 높습니다.

또한 "또한 주목해야 합니다. NIST가 여러 차례의 스크리닝 검토를 수행하기 전에는 분석에 사용할 수 있는 PQC 알고리즘이 많았기 때문에 연구 노력이 엷게 분산되었습니다. 여러 차례의 스크리닝 후에 연구자들은 소수의 알고리즘에 집중할 수 있었습니다."라고 Joseph은 말했습니다.

SIKE의 발명자 중 한 명이자 캐나다 워털루 대학교 교수인 David Jao는 다음과 같이 말했습니다. "이 새로운 결과는 놀라운 작품이라고 생각하며 저자에게 최고의 찬사를 보냅니다. 처음에는 SIKE의 크래킹에 대해 회의적이었습니다. 수학적으로 매우 우아한 솔루션이기 때문에 슬프죠."

"하지만 새로운 발견은 과학이 어떻게 작동하는지를 반영할 뿐입니다. 우리는 시스템을 생각해냈고 당시에는 모두가 그것이 좋아 보인다고 생각했습니다. 그런 다음 누군가가 그것을 분석했습니다. 약점을 발견하는 데 10년이 넘게 걸렸는데, 이는 특이한 일이지만 그 외에는 일반적인 과학적 진보의 영역을 벗어나는 것은 아니다”라고 David Jao는 덧붙였습니다.

Jao의 의견으로는 SIKE가 이제 크랙된 것은 다행이지만, 결국 널리 배포되지는 않았습니다.

SIKE가 크랙되면 무슨 뜻인가요?

SIKE는 올해 해독된 두 번째 NIST PQC 후보 알고리즘입니다. 올해 2월, 취리히에 있는 IBM Research의 암호학자인 Ward Beullens는 NIST 검토의 3차 라운드에 참여하여 자신의 노트북을 사용하여 Rainbow 알고리즘을 해독할 수 있다고 밝혔습니다. Katz는 "이는 모든 PQC 옵션에 추가 연구가 필요하다는 것을 의미합니다."라고 말했습니다.

그러나 Moody는 SIKE가 크랙되었지만 CSIDH나 SQIsign과 같은 상동성을 기반으로 한 다른 암호화 시스템은 크랙되지 않았다고 지적했습니다. "어떤 사람들은 상동성을 기반으로 한 암호화가 죽었다고 생각할 수도 있지만 진실은 멀었습니다. " 그렇지 않으면 상동성 기반 암호학에 대해서는 아직 연구할 것이 많다고 생각합니다."라고 Decru는 말했습니다.

또한, 이 새로운 작업은 NIST의 PQC 연구 수준을 반영하지 않을 수도 있습니다. Decru가 언급했듯이 SIKE는 NIST가 받은 82개 제안 중 유일한 상동성 기반 암호화 시스템이었고 Rainbow는 해당 제출물 중 유일한 다변량 알고리즘이었습니다.

NIST가 "표준"으로 채택했거나 4차 검토에 들어간 알고리즘은 오랫동안 암호학자들이 연구하고 분석한 수학적 아이디어를 기반으로 한다고 Galbraith는 말했습니다. "그것이 안전하다는 것을 보장하는 것은 아닙니다. 단지 더 오랫동안 공격을 견딜 수 있다는 의미입니다."

Moody는 "암호화 시스템을 해독하기 위한 놀라운 돌파구가 항상 발견되고 있습니다."라고 말했습니다. 우리가 말할 수 있는 가장 좋은 점은 많은 똑똑한 사람들이 광범위한 연구를 한 후에도 이 암호화 시스템에서 어떤 취약점도 발견하지 못했다는 것입니다. "우리 프로그램은 그렇게 하도록 설계되었습니다. 공격과 해킹을 허용합니다."라고 Moody는 말했습니다. "우리는 모든 평가에서 이러한 현상을 확인했습니다. 이것이 안전에 대한 확신을 얻을 수 있는 유일한 방법입니다." Galbraith는 이와 같은 연구가 "효과가 있다"고 동의했습니다.

그럼에도 불구하고 Decru는 “Rainbow와 SIKE의 종말로 인해 더 많은 사람들이 NIST의 포스트 양자 표준화 프로세스에서 나오는 모든 승자를 위한 백업 계획의 필요성을 진지하게 고려하게 될 것이라고 생각합니다.”라고 말했습니다. "수학적 개념이나 체계에만 의존하는 것은 너무 위험할 수 있습니다. 이것은 또한 NIST 자신의 생각이기도 합니다. 그들의 주요 체계는 아마도 격자 암호화(격자 기반)를 기반으로 할 것입니다. 그러나 그들은 선택을 준비하기 위해 비격자 암호화 체계를 원합니다."

Decru는 다른 연구원들이 이러한 새로운 유형의 공격을 예방할 수 있다고 믿는 새로운 버전의 SIDH/SIKE 개발을 시작했다고 언급했습니다. Decru는 "공격이 확대되고 사람들이 SIDH/SIKE를 패치하려고 하면 어떤 일이 일어날지 예상했습니다."라고 말했습니다.

대체로 이 새로운 공격의 출발점은 "암호화와 전혀 관련이 없는" 정리이며 "암호화 시스템을 이해하기 위해 순수 수학에서 기초 연구를 수행하는 것이 중요함을 드러낸다"고 Galbraith는 말했습니다.

Decru는 "수학에서는 모든 것이 즉시 적용 가능한 것은 아닙니다. 어떤 것들은 실제 상황에 거의 적용되지 않습니다. 그렇다고 해서 연구가 이러한 모호한 주제로 이어지도록 해서는 안 된다는 의미는 아닙니다." "

위 내용은 10년의 데스크톱, 단일 코어 양자 암호화 알고리즘이 1시간 만에 해독됨, 암호 작성자: 너무 갑작스럽습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!