Full-Key Recovery and Forgery from One MQOM v2.1 Signature

당신이 친구에게 비밀 메시지를 보내려고 노력하고 있다고 상상해 보세요. 하지만 당신은 언젠가 존재할지도 모르는 초고속 컴퓨터(양자 컴퓨터라고 불리는)가 존재하는 세상에 살고 있습니다. 이 미래의 기계들은 오늘날 우리의 비밀을 안전하게 지켜주는 대부분의 자물쇠를 부술 수 있습니다. 이를 대비하기 위해, 과학자들은 "포스트 퀀텀 서명(post-quantum signatures)"이라 불리는 특수한 종류의 강력한 디지털 자물쇠를 만들고 있습니다. 이것은 편지에 찍는 특별한 종류의 밀랍 인장과 같습니다. 설령 도둑이 일반적인 자물쇠를 부술 수 있는 마법 망치를 가지고 있더라도, 이 새로운 밀랍 인장은 그 형태를 유지할 수 있는 재질로 만들어져야 합니다.

이러한 새로운 자물쇠 중 가장 유망한 것 중 하나는 MQOM이라고 불리는 것입니다. 이것은 거대하고 복잡한 퍼즐처럼 작동합니다. 메시지에 서명하기 위해, 송신자는 비밀 "증인"(숨겨진 키)을 사용하여 많은 변수가 포함된 수학 문제를 해결합니다. 비밀을 보여주지 않고도 문제를 풀었다는 것을 증명하기 위해, 그들은 "MPC-in-the-head"라고 불리는 영리한 기술을 사용합니다. 이는 송신자가 마치 비밀의 아주 작은 조각들을 각각 들고 있는 하나의 팀인 것처럼 행동하는 것을 상상해 보세요. 그들은 팀이 함께 퍼즐을 풀었다는 것을 증명할 수 있을 만큼만 정보를 드러내되, 실제 비밀 조각들을 드러내지는 않는 게임을 수행합니다. 만약 수학적 계산이 성립한다면, 그 서명은 유효한 것이 됩니다. 우리가 이것에 관심을 갖는 이유는, 만약 이 새로운 자물쇠에 숨겨진 균열이 있다면, 우리가 그 시대에 도달하기도 전에 우리의 미래 디지털 안전이 무너질 수 있기 때문입니다.

이제 이 논문의 이야기를 해보겠습니다. 호세 루이스 델가도(José Luis Delgado)라는 연구자는 특정 버전의 MQOM 자물쇠(버전 2.1)를 면밀히 조사했고, 이를 깨뜨릴 수 있는 놀라울 정도로 단순한 방법을 찾아냈습니다. 이 논문은 만약 공격자가 시스템으로부터 단 하나의 유효한 서명을 얻게 된다면, 전체 비밀 키를 알아내어 원하는 어떤 메시지에 대해서도 새로운 서명을 위조할 수 있다고 주장합니다. 이것은 마치 도둑이 당신이 현관문을 한 번 여는 것을 보고, 그 단 한 번의 훔쳐보기만으로 당신의 집 모든 문을 열 수 있는 마스터 키를 만드는 것과 같습니다.

이 "마법의 기술"이 어떻게 작동하는지 이야기를 통해 설명하겠습니다. 비밀 키가 긴 숨겨진 보물 지도라고 상상해 보세요. MQOM 시스템은 이 지도를 가지가 많은 거대한 나무 안에 숨깁니다. 당신이 메시지에 서명할 때, 시스템은 당신에게 나무를 타고 올라가는 경로를 특정 숨겨진 잎(지도의 한 지점)까지 보여주지만, 그 잎 자체는 가려진 상태로 유지합니다. 그러나 시스템은 "형제 경로(sibling path)"—즉, 숨겨진 잎 옆에 있는 가지들의 목록—도 함께 제공합니다. 나무가 구축된 방식 때문에, 만약 당신이 잎 옆의 가지들을 알고 있다면, 비밀 지도의 작은 접두사(prefix)를 알고 있을 때 그 숨겨진 잎이 무엇이 될지를 알아낼 수 있습니다.

논문은 또한 시스템이 숨겨진 잎을 담고 있는 봉투와 같은 "커밋먼트(commitment)"를 남긴다는 점을 발견했습니다. 연구자는 형제 경로(가지들)와 봉투를 결합하면 하나의 거대한 방정식을 쓸 수 있다는 사실을 깨달았습니다. 이 방정식에는 하나의 미지수, 즉 비밀 지도의 작은 접두사가 들어 있습니다. 공격자는 전체 지도를 추측할 필요가 없습니다. 그저 이 하나의 방정식을 풀어 이 작은 접두사를 찾기만 하면 됩니다.

일단 이 접두사를 찾으면, 이미 가지고 있는 서명은 "여기에 당신이 방금 찾은 접두사와 함께 사용할 나머지 지도가 있습니다"라고 말하는 작은 메모인 "교정 접미사(correction suffix)"를 제공합니다. 이 접두사와 메모를 결합함으로써, 공격자는 전체 비밀 지도(전체 서명 키)를 재구성할 수 있습니다. 이 키를 가지고 있으면, 그들은 어떤 새로운 메시지에도 서명할 수 있습니다.

이 논문은 단순히 이것이 작동할 것이라고 추측하는 데 그치지 않습니다. 그들은 수학적 계산과 컴퓨터 작업을 실제로 수행하여 이를 증명했습니다. 그들은 이 방정식을 푸는 데 얼마나 많은 컴퓨팅 파워가 필요한지 다양한 보안 등급(Category I, III, V)에 대해 계산했습니다. 그 결과, 세 가지 카테고리 모두에서 요구되는 노력은 NIST가 이 자물쇠들에 설정한 보안 한계치보다 낮음을 발견했습니다.

가장 쉬운 단계(Category I)의 경우, 공격에는 약 $2^{142.335112}$ 번의 연산이 필요합니다. 중간 단계(Category III)의 경우, 지도를 얼마나 스캔하느냐에 따라 약 $2^{206.774558}$ 또는 $2^{206.988685}$ 번의 연산이 필요합니다. 가장 어려운 단계(Category V)의 경우, 약 $2^{271.794162}$ 번의 연산이 필요합니다. 모든 경우에서 공격자가 수행해야 하는 단계의 수는 자물쇠가 안전하기 위해 요구되었던 단계의 수보다 적었습니다.

연구자들은 수학 작업에서 멈추지 않았습니다. 그들은 실제로 공격을 실행하는 컴퓨터 프로그램을 구축했습니다. 그들은 실제 서명을 가져와서 방정식을 풀고, 바이트 단위로 정확한 비밀 키를 복구한 다음, 그 키를 사용하여 새로운 메시지에 서명했습니다. 시스템의 검증기는 새 서명을 확인하고 "네, 유효합니다!"라고 답했습니다. 이는 이 공격이 종이 위에서뿐만 아니라 실제 세상에서도 작동한다는 것을 증명했습니다.

논문은 일부 설정을 변경하는 것이 문제를 해결할 수 있는지도 살펴보았습니다. 그들은 단순히 "소금(salt, 무작위 숫자)"을 과정에 추가하는 것이 방정식의 숫자를 바꾸기는 하지만, 공격을 막지는 못한다는 것을 발견했습니다. 방정식은 여전히 존재하며, 단지 모습이 약간 달라질 뿐입니다. 이를 진정으로 고치려면 설계자들이 나무 경로와 비밀 사이의 관계, 잎이 커밋되는 방식, 또는 교정 메모가 생성되는 방식을 변경해야 합니다.

요약하자면, 이 논문은 현재 버전의 MQOM 자물쇠에 걸어 다닐 수 있을 만큼 큰 구멍이 있음을 보여줍니다. 단 하나의 서명을 마스터 키로 바꾸어 놓음으로써, 공격자가 설계된 보안 수준보다 적은 노력으로 메시지를 위조할 수 있게 만듭니다. 저자는 다른 사람들이 자신의 작업을 확인할 수 있도록 코드와 결과를 공유했으며, MQOM 설계자들이 이 시스템이 미래에 안전하다고 간주되기 전에 이러한 특정 부분들을 반드시 패치해야 한다고 제안합니다.