Resolving an Apparent Key-Dependent Timing Side-Channel in Bouncy Castle ML-DSA-65 Signing: A Pre-Registered Discrimination

디지털 보안의 세계에서 가장 강력한 자물쇠는 종종 따는 데 가장 오래 걸리는 자물쇠입니다. 수십 년 동안 수학자들은 데이터를 안전하게 보호하기 위해 복잡한 문제에 의존하는 암호화 시스템을 설계해 왔습니다. 컴퓨터가 점점 더 강력해지고 양자 컴퓨터의 가능성이 다가옴에 따라, 과학자들은 미래의 기계조차도 깰 수 없는 새로운 자물쇠를 만들기 위해 경주하고 있습니다. 가장 유망한 새로운 설계 중 하나는 ML-DSA라고 불립니다. 이것은 계약서나 인증서 위의 친필 서명과 같은 전자적 등가물인 디지털 서명을 생성하는 방법입니다. 이러한 서명은 메시지가 특정 인물로부터 왔으며 변조되지 않았음을 증증합니다.

하지만 이러한 수학적 자물쇠와 함께 새로운 종류의 위험이 등장했습니다. 그것은 수학 자체의 결함이 아니라, 컴퓨터에서 수학이 실행되는 방식의 결함입니다. 이것은 타이밍 부채널 공격(timing side-channel attack)으로 알려져 있습니다. 올바른 조합을 입력했을 때 약간 더 크게 '딸깍' 소리가 나는 금고나, 올바른 열쇠를 사용했을 때 문이 열리는 데 아주 미세하게 더 오래 걸리는 문을 상상해 보십시오. 만약 공격자가 극도로 정밀하게 이러한 미세한 시간 차이를 측정할 수 있다면, 비밀 키를 추론해 낼 수도 있습니다. 새로운 ML-DSA 시스템을 위해 설계자들은 안전 장치를 구축했습니다. 이 과정은 많은 시행착오를 포함합니다. 컴퓨터는 서명을 생성하려고 시도하고, 그것이 유효한지 확인하며, 유효하지 않다면 그것을 버리고 다시 시도합니다. 시도 횟수가 무작위로 변하기 때문에, 메시지에 서명하는 데 걸리는 총 시간 또한 변합니다. 이 무작위성은 비밀 키를 숨겨서, 특정 지연이 비밀 키 때문인지 아니면 단순히 운이 나빴기 때문인지 알 수 없게 만드는 역할을 합니다.

아르판 샤르마(Arpan Sharma)라는 연구자는 최근 Bouncy Castle이라는 인기 있는 소프트웨어 라이브러리에서 이 안전 기능이 의도한 대로 작동하는지 조사했습니다. 이 라이브러리는 소프트웨어 업데이트부터 보안 웹 연결에 이르기까지 모든 것을 보호하기 위해 널리 사용됩니다. 샤르마가 처음 데이터를 보았을 때, 그는 누출처럼 보이는 무언가를 발견했습니다. 20개의 서로 다른 비밀 키를 사용하여 메시지에 서명하는 데 걸린 시간을 비교했을 때, 일부 키가 일관되게 다른 키보다 더 오래 걸린다는 것을 발견했습니다. 그 차이는 약 1.35% 정도로 작았지만, 보안의 세계에서는 아주 작은 일관된 차이라 할지라도 비밀이 드러나고 있다는 신호가 될 수 있습니다. 문제는 이 차이가 실제 취약점인지, 즉 비밀 키가 시간에 영향을 미치도록 허용하는 코드의 결함인지, 아니면 시스템의 무작위성으로 인해 발생하는 통계적 착시인지였습니다.

이에 답하기 위해 샤르마는 단순한 추측이나 빠른 테스트에 의존하지 않았습니다. 그는 신호와 소음을 분리하기 위해 엄격하고 계획된 실험을 설계했습니다. 그의 방법의 핵심은 단순히 최종 시간만을 보는 것이 아니라, 컴퓨터가 모든 서명을 위해 실제로 수행한 작업을 살펴보는 것이었습니다. 그는 컴퓨터가 유효한 서명을 찾을 때까지 몇 번이나 시도하고 실패했는지를 정확히 기록하는 도구를 만들었습니다. 이것은 매우 중요한데, 메시지에 서명하는 데 걸리는 시간은 컴퓨터가 얼마나 많이 재시도해야 하는지와 직접적으로 연결되어 있기 때문입니다. 만약 어떤 키가 적은 재시도를 요구하는 '운 좋은' 메시지 세트를 얻었다면, 그 키가 달라서가 아니라 그날 수학적 계산이 더 쉬웠기 때문에 더 빨리 끝났을 것입니다.

샤르마는 각 20개의 키에 대해 120만 개 이상의 서명을 생성하는 대규모 캠페인을 실행했습니다. 그런 다음 그는 정확한 작업량에 따라 서명을 그룹화했습니다. 그는 간단한 질문을 던졌습니다. 만약 두 서명이 정확히 같은 횟수의 재시도를 요구하고 정확히 같은 단계를 거쳤다면, 여전히 어떤 키를 사용하느냐에 따라 걸리는 시간이 달라지는가? 대답은 명확하게 '아니오'였습니다. 재시도 횟수를 고려하자 키에 따른 시간 차이는 사라졌습니다. 남아 있는 미세한 변동은 비밀 키 자체가 아니라 컴퓨터 프로세서와 메모리의 자연스러운 무작위 변동으로 설명될 수 있을 만큼 매우 작았습니다.

이 연구는 결과가 특정 컴퓨터나 소프트웨어가 메모리에 로드되는 방식의 우연이 아님을 보장하기 위해 더 나아갔습니다. 샤르마는 새로운 키 세트와 새로운 메시지 세트로 실험을 반복했습니다. 또한 그는 컴퓨터가 데이터를 처리하는 순서를 섞는 제어 테스트를 실행했습니다. 만약 타이밍 차이가 비밀 키에 의해 발생했다면 키의 순서는 중요하지 않을 것입니다. 만약 차이가 데이터가 컴퓨터의 메모리에 배치되는 위치에 의해 발생했다면 순서가 결과에 영향을 줄 것입니다. 실험 결과, 타이밍 차이는 키를 따르지 않고 메모리 레이아웃을 따랐습니다. 이는 겉으로 드러난 타이밍 차이가 코드의 보안 결함이 아니라 컴퓨터 환경의 산물임을 확인시켜 주었습니다.

연구는 또한 데이터에 따라 약간 달라질 수 있는 것으로 알려진 코드의 한 부분을 살펴보았습니다. 소프트웨어는 프로세스 중에 숫자의 크기를 확인하며, 숫자가 너무 크면 즉시 나머지 목록의 확인을 중단합니다. 이는 시간을 절약하기 위한 표준적인 최적화이지만, 이는 컴퓨터가 어떤 입력에 대해서는 다른 입력보다 더 빨리 멈출 수 있음을 의미합니다. 샤르마는 이 지름길의 영향을 측정했고, 그것이 약 1나노초의 지연만을 기여한다는 것을 발견했습니다. 이는 10억 분의 1초라는 시간 단위로, 공격자가 키를 훔치기 위해 현실적으로 측정하거나 이용할 수 있는 임계값보다 훨씬 낮은 수준입니다.

이 연구 결과는 서로 다른 보안 수준에 사용되는 더 작거나 큰 버전들을 포함하여, 이 새로운 디지털 서명 표준의 전체 제품군에 적용되었습니다. 모든 경우에 결과는 동일했습니다. 소프트웨어 구현은 깔끔했습니다. 겉으로 드러난 타이밍 차이는 비밀 키가 유출되고 있다는 신호가 아니었습니다. 대신, 그것은 비밀 키를 보호하기 위해 작업량을 변화시키도록 설계된 시스템의 자연스러운 결과였습니다. 연구는 Bouncy Castle 라이브러리가 이러한 특정 유형의 공격으로부터 안전하다는 결론을 내렸습니다. 처음에 경보를 울렸던 1.35%의 시간적 확산은 비밀 키가 유출되는 신호가 아니라, 단순히 20개의 서로 다른 키가 무작위 분포에서 20개의 서로 다른 샘플을 추출하면서 나타난 통계적 메아리였습니다.

이 조사는 시스템이 안전하다는 것을 증명하는 것이 얼마나 어려운지를 상기시켜 줍니다. 과거에는 연구자들이 첫 번째 타이밍 차이의 징후를 보고 취약점이라고 선언하며 멈췄을 수도 있습니다. 이 연구는 복잡하고 무작위적인 시스템에서 첫 번째 징후는 종종 시스템이 제 역할을 수행하고 있다는 신호일 뿐이라는 점을 보여줍니다. 작업 수행량을 정밀하게 측정하고 환경을 통제함으로써, 연구자는 실제 유출과 통계적 착시를 구별해 낼 수 있었습니다. 결과는 새로운 디지털 서명이 견고하다는 것을 확인해 주었으며, 속도의 무작위 변동은 결함이 아니라 하나의 특징입니다. 이 서명을 사용하여 보안을 유지하는 수백만 대의 기기들에게 메시지는 명확합니다. 자물쇠는 견고하며, 열쇠를 돌리는 데 걸리는 시간은 그 안의 비밀에 대해 아무것도 말해주지 않습니다.