Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

인터넷을 모두가 비밀 메시지를 보내려고 애쓰는 거대하고 북적이는 도시라고 상상해 보십시오. 이 메시지들을 엿보는 눈으로부터 안전하게 지키기 위해, 우리는 암호화라는 이름의 디지털 자물쇠를 사용합니다. 오랫동안 과학자들은 풀기에는 매우 어렵지만 만들기는 아주 쉬운 복잡한 수학 퍼즐을 사용하여 이러한 자물쇠를 만들어 왔습니다. 최근에는 숫자 격자를 이용한 특수한 종류의 수학을 사용하는 새로운 형태의 자물쇠가 제안되었습니다. 여기서 '계수(rank)'란 (단순히 격자 안에 실제로 얼마나 많은 정보가 채워져 있는지를 측정하는 세련된 방식입니다) 정보를 의미합니다. 이 새로운 자물쇠의 제작자들은 이 자물쇠에 '노이즈(noise)'—마치 라디오의 잡음처럼—를 추가하여, 침입자가 들어오려 할 때 자물쇠의 실제 모양을 숨겨서 무작위적인 혼돈처럼 보이게 만들었다고 생각했습니다. 그들은 이 설계가 너무나 안전해서 초고속 양자 컴퓨터조차도 이를 깨뜨릴 수 없다고 주장했으며, 미래의 보안 통신에 적합하도록 작고 효율적일 것이라고 약속했습니다.

하지만, 마치 특정 손기술에 의존하는 마술사의 속임수처럼, 이 새로운 자격에는 숨겨진 결함이 있었습니다. 타이 흥 레(Thai Hung Le)라는 연구원이 이 '노이즈'가 생각만큼 잘 숨겨주는 역할을 하지 못한다는 사실을 발견했습니다. 연구원은 영리한 추측과 대수적인 탐정 놀이를 결합하여, 정적의 층을 벗겨내고 그 아래에 숨겨진 원래의 구조를 드러내는 방법을 찾아냈습니다. 이는 마치 누군가가 비밀 설계도가 있는 카드로 만든 집을 짓고 그 위에 안개를 덮어놓았는데, 특정 각도에서 안개를 바라보니 설계도가 희미하게 여전히 보인다는 것을 깨달은 것과 같습니다. 이 발견은 매우 중요한데, 왜냐하면 이 새로운 자물쇠들이 광고된 것만큼 안전하지 않다는 것을 의미하며, 우리의 데이터를 보호하기 위해 이들을 사용하기 전에 설계자들이 그들의 설계도를 다시 생각해야 한다는 것을 의미하기 때문입니다.

논문의 핵심 발견

이 논문에서 타이 흥 레는 '강화된 가빌딘 매트릭스 코드(Enhanced Gabidulin Matrix Code, EGMC)' 암호 체계를 깨뜨리는 새로운 방법을 제시합니다. 이 체계들은 미래의 양자 컴퓨터 공격에서도 살아남을 수 있는 매우 작고 효율적인 암호 키를 만들기 위한 방법으로 최근에 도입되었습니다. 이 체계들의 보안은 특정한 구조를 가진 숫자의 격자를 가져와서 무작위 행과 열을 추가했을 때(노이즈), 실제 코드와 완전히 무작위적인 혼돈 사이의 차이를 구별하는 것이 불가능하다는 아이디어에 의존했습니다.

저자는 이 가정이 틀렸음을 보여줍니다. 모든 가능한 방식으로 노이즈를 제거하려고 무차별 대입(brute-force)을 시도하는 대신(이는 영원히 걸릴 것입니다), 이 논문은 '하이브리드(hybrid)' 공격을 도입합니다. 이것은 거대하고 뒤섞인 모자이크에서 특정 패턴을 찾는 것과 같습니다. 기존의 방식은 모든 타일의 위치를 추측하는 것이었습니다. 이 새로운 방법은 더 똑똑합니다. 단 하나의 타일 행의 위치만을 추측한 다음, 수학을 사용하여 나머지 타일들이 반드시 있어야 할 위치를 즉시 알아내는 것입니다.

논문은 두 가지 주요 방법을 상세히 설명합니다:

1. 열(Columns) 추측하기: 공격자가 격자의 열이 어떻게 섞였는지 추측한 다음, 대수학을 사용하여 행이 어떻게 섞였는지 계산합니다.
2. 행(Rows) 추측하기: 공격자가 행이 어떻게 섞였는지 추측한 다음, 열을 계산합니다.

공격자가 섞임(shuffling)을 파악하고 나면, 그들은 무작위 노이즈를 벗겨내고 원래의 숨겨진 구조를 드러낼 수 있습니다. 논문은 이 구조가 '가빌딘 코드(Gabidulin code)'임을 증명하는데, 이는 일단 비밀 패턴을 알게 되면 상당히 풀기 쉬운 유형의 수학 퍼즐입니다.

이 논문이 실제로 깨뜨리는 것

저자는 단순히 작은 틈을 찾아낸 것이 아니라, 창문 전체를 박살 냈습니다. 논문은 이 공격이 제안된 EGMC 암호 체계의 16가지 모든 매개변수 집합에 대해 작동함을 보여줍니다. 이는 제안된 모든 버전의 자물쇠가 이제 깨진 것으로 간주됨을 의미합니다.

이 공격의 효과를 체감할 수 있도록, 논문은 128비트 보안(표준적인 안전 수준)을 제공하도록 설계되었던 특정 숫자 집합을 살펴봅니다. 저자는 이 공격이 보안 수준을 단 35비트로 낮춘다는 것을 보여줍니다. 암호화의 세계에서 이것은 백만 자리 조합이 있는 금고에서 순식간에 따버릴 수 있는 자물쇠로 변한 것과 같습니다.

논문은 이 능력에 대한 구체적인 예를 제공합니다: 연구원들은 이 방법을 사용하여 10분 미만에 128비트 보안 수준의 비밀 키를 복구할 수 있었습니다. 이것은 단순한 이론적 아이디어가 아니었습니다. 그들은 실제로 이를 수행하기 위한 컴퓨터 프로그램을 구축했습니다.

이 논문이 배제하는 것

이 논문이 작동하지 않는다고 말하는 점을 유의하는 것이 중요합니다. 저자는 이 코드들을 깨려는 이전의 시도들이 행과 열의 섞임을 동시에 추측하는 '조합론적(combinatorial)' 방법에 의존했다고 설명합니다. 논문은 이 오래된 방식이 새로운 '하이브리드' 접근 방식에 비해 너무 느리고 비효율적이라고 주장합니다.

또한, 논문은 단순히 매개변수를 크게 만드는 것(더 많은 노이즈를 추가하는 것)이 모든 경우에 문제를 해결할 것이라는 생각에 반박합니다. 저자는 이러한 유형의 코드 중 특정 유형—특히 노이즈 요인 중 하나(추가된 행 또는 추가된 열의 수)가 0인 경우—에 대해서는 공격이 '다항 시간(polynomial time)' 내에 실행될 정도로 빨라진다는 것을 보여줍니다. 이는 해당 특정 사례들에서는 자물쇠의 크기를 아무리 키우더라도 공격이 여전히 빠를 것임을 의미합니다. 논문은 이 문제를 잠재적으로 해결할 수 있는 유일한 방법은 두 노이즈 요인이 모두 0이 아니고 공격을 막을 만큼 충분히 커지도록 근본적인 설계를 변경하는 것이지만, 이 경우 키와 메시지가 너무 커져서 쓸모없어질 수 있다고 경고합니다.

얼마나 확신하는가?

논문은 자신의 결과에 매우 자신감을 보입니다. 저자는 단순히 추측한 것이 아니라, 공격이 어떻게 작동하는지에 대한 완전한 수학적 증명을 제공하고 작동하는 컴퓨터 구현으로 뒷받침했습니다. 저자는 이 공격이 제안된 모든 버전을 깨뜨린다고 명시적으로 밝혔습니다. 또한 이전의 공격들과 결과를 비교하여, 자신의 방법이 훨씬 더 빠르고 강력함을 보여주었습니다. 논문은 EGMC 암호 체계가 더 이상 사용하기에 안전하지 않으며, 보안 커뮤니티가 다른 설계로 넘어가야 한다고 결론짓습니다.