Retrofit or Redesign? Hardware-Validated Constant-Time Defense and Cost Analysis for the M-Step Side-Channel on TrustZone-M

당신이 비밀 금고의 수호자라고 상상해 보십시오. 이 금고를 여는 유일한 방법은 복잡한 수학 퍼즐을 푸는 것입니다. 디지털 보안의 세계에서, 이 퍼즐은 종종 메시지를 잠그고 해제하는 데 사용되는 "모듈러 역원(modular inversion)" 계산으로 나타납니다. 수년 동안 전문가들은 만약 퍼즐을 푸는 데 걸리는 시간을 매번 동일하게 만든다면, 아무도 비밀을 훔칠 수 없다고 믿었습니다. 이것을 "상수 시간(constant-time)" 보안이라고 부릅니다. 아이디어는, 도어가 열리는 시간을 보고 당신이 열심히 고민 중인지 아니면 그냥 추측하고 있는지를 도둑이 알아낼 수 없다면 안전할 것이라는 것이었습니다.

하지만 "싱글 스태핑 공격(single-stepping attack)"이라는 아주 교활한 새로운 기술이 있습니다. 도둑이 단순히 문이 열리기를 기다리는 것이 아니라, 마법의 스톱워치를 사용하여 당신의 퍼즐 해결 과정 중 매 단계마다 시간을 멈출 수 있다고 상상해 보십시오. 그들은 당신이 어떤 경로를 통과하는지 정확히 지켜볼 수 있습니다. 만약 당신의 미로에 정답을 알고 있을 때만 통과하는 비밀 지름길이 있다면, 도둑은 당신이 지름길을 이용하는 것을 보고 당신의 비밀을 알아낼 것입니다. 이 논문은 보안 엔지니어들이 직면한 중대한 선택을 탐구합니다. 취약점이 발견되었을 때, 낡고 누출이 있는 미로를 균일해 보이도록 보수(retrofit)해야 할까요, 아니면 처음부터 지름길이 없는 완전히 새로운 미로를 설계(redesign)해야 할까요? 답은 단순히 어느 쪽이 더 빠른가가 아니라, 어느 쪽이 실제로 도둑이 당신의 비밀을 보는 것을 막을 수 있느냐에 달려 있습니다.

---

위대한 미로 보수 작업: 리트로핏(Retrofit) vs 리디자인(Redesign)

이 연구에서 Arash Razban과 그의 팀은 스마트 카드나 의료 기기와 같은 소형 임베디드 컴퓨터에서 데이터를 보호하는 데 사용되는 유명한 라이브러리에서 발견된 실제 보안 구멍(CVE-2025-54764로 알려짐)을 다루었습니다. 이 구멍은 비밀 키를 처리하는 수학 엔진인 "이진 GCD(binary GCD)" 및 "모듈러 역원" 루틴에 있었습니다. "M-Step"이라는 기술을 사용하는 해커는 컴퓨터를 매 명령 단계마다 멈추고 수학이 지나가는 경로를 관찰하여 비밀 키를 훔칠 수 있었습니다.

연구진은 실제 실리콘 하드웨어(Cortex-M33 칩)에서 헤드 투 헤드 대결을 설정하여, 어떤 방어 전략이 더 효과적인지 확인했습니다: 리트로핏(The Retrofit) 또는 리디자인(The Redesign).

리트로핏 (보수 작업):
팀은 기존의 누출이 있는 수학 루틴을 고치려고 시도했습니다. 그들은 비밀에 따라 경로가 달라지는 지름길(마치 숨겨진 문이 있는 미로와 같은)이 있는 원래의 코드를 가져와서, 매번 동일한 경로를 걷도록 강제했습니다. 그들은 코드가 필요하지 않은 단계까지도 모든 단계를 거치도록 만들고, 실제로 어떤 경로가 선택되었는지 숨기기 위해 "브랜치리스(branchless)" 기법을 사용했습니다. 이는 마치 러너가 출구가 어디든 상관없이 집 안의 모든 방을 통과하여 조깅하도록 강제하여, 관찰자가 그가 실제로 어느 방에서 나갔는지 알 수 없게 만드는 것과 같습니다.

리디자인 (새로운 구축):
대안은 기존의 수학을 완전히 버리고, 처음부터 지름길이 없도록 설계된 새로운 알고리즘(safegcd)으로 교체하는 것이었습니다. 이 새로운 미로는 비밀이 무엇이든 관계없이 항상 동일한 고정된 경로를 가집니다.

충격적인 결과: 속도와 은밀한 누출

연구진은 두 가지를 측정했습니다: 이 방어책을 실행하는 데 드는 비용(시간과 에너지)과, 이것이 실제로 도둑을 막을 수 있는지 여부입니다.

1. 패치의 비용
결과는 놀라웠습니다. "리디자인"은 매우 효율적이었습니다. 그러나 "리트로핏"은 속도 측면에서 재앙이었습니다.

• GCD 루틴의 경우, 리트로핏은 리디자인보다 192배 느렸습니다.
• 모듈러 역원의 경우, 리트로핏은 532배 느렸습니다.

이를 체감해 보자면, 테스트된 하드웨어에서 리디자인된 루틴은 실행하는 데 밀리초(ms) 단위가 걸렸습니다. 그렇다면 리트로핏된 루틴은 어땠을까요? 무려 초(seconds) 단위가 걸렸습니다. 구체적으로, 리트로핏된 GCD는 호출당 약 4.5초가 걸렸고, 모듈러 역원은 무려 25초가 걸렸습니다. 문을 즉시 열거나 메시지에 서명해야 하는 장치에게 25초를 기다리게 하는 것은 사실상 쓸모가 없는 일입니다. 리디자인은 단순히 더 나은 수준이 아니라, 장치를 사용 가능하게 만드는 유일한 옵션이었습니다.

2. "유령" 누출 (The "Ghost" Leak)
여기서 이야기는 정말 흥ًا해집니다. 연구진은 리트로핏이 성공적이라고 생각했습니다. 전체 실행 시간을 측정했을 때, 리트로핏은 완벽해 보였습니다. 시간이 서로 다른 비밀값 사이에서 2% 미만으로 변동했는데, 이는 보통 "안전함"으로 간주되는 수준입니다.

하지만 그들은 매우 정밀한 도구를 사용하여 컴퓨터가 실행하는 정확한 명령 단계를 단계별로 점검했습니다. 그들은 "유령 누출"을 발견했습니다.

• 리트로핏에서는 수학 프로세스의 맨 마지막 부분에 아주 작은 숨겨진 루프가 있었습니다. 대부분의 입력에 대해서는 정해진 횟수만큼 실행되었습니다. 하지만 특정 비밀값 하나에 대해서는 한 번 더 실행되었습니다.
• 이 추가된 단계는 불과 수십 번의 클록 사이클만을 더했습니다. 전체 실행 시간이 워낙 컸기 때문에(수십억 사이클), 이 미세한 차이는 표준 타이밍 테스트에서는 완전히 보이지 않았습니다. 이는 마치 25초짜리 영화에서 도둑이 눈 한 번 깜빡이는 짧은 순간을 포착하는 것과 같았습니다.
• 매 단계를 관찰하는 M-Step 공격자는 이 추가된 깜빡임을 보고 정확히 어떤 비밀인지 알아낼 수 있었을 것입니다.
• 연구진은 진정으로 문을 닫기 위해 이 작은 루프를 수정하여 고정된 시퀀스로 교체해야 했습니다.

결론: 새로 만들어라, 패치하지 말고

논문은 보안 엔지니어들에게 명확한 메시지를 전달하며 끝을 맺습니다: 이러한 유형의 수학 루틴을 패치하려고 하지 마십시오.

1. 리디자인이 승리한다: "설계에 의한 상수 시간(constant-time-by-design)" 접근 방식(리디자인)이 압도적으로 우월합니다. 기존 코드를 패치하려는 노력보다 약 두 자릿수(100배) 더 빠릅니다.
2. 타이밍 테스트는 거짓말을 한다: 표준 타이밍 테스트가 패치가 안전하다는 것을 알려준다고 믿어서는 안 됩니다. 패치는 스톱워치상으로는 완벽해 보일 수 있지만, "싱글 스태핑" 공격자가 볼 수 있는 아주 미세하고 착취 가능한 누출을 여전히 가지고 있을 수 있습니다.
3. 시계가 아닌 단계를 확인하라: 방어책이 제대로 작동하는지 확인하려면, 단순히 총 소요 시간이 아니라 정확한 명령 시퀀스(지나온 경로)를 검증해야 합니다.

연구진은 이 유령 누출을 수정한 후에도 미세한 시간 변동성(약 2%)이 남아 있음을 발견했습니다. 그러나 그들은 이것이 비밀 누출이 아니라, 하드웨어가 처리하는 숫자에 따라 하드웨어 자체가 다르게 동작하는 현상, 즉 최고의 소프트웨어로도 제거할 수 없는 "하드웨어 바닥(hardware floor)"임을 입증했습니다. 하지만 결정적으로, 이제 컴퓨터가 지나가는 경로는 매번 동일했으므로, 도둑은 단계를 관찰함으로써 비밀을 알아낼 수 없게 되었습니다.

요약하자면, 이러한 중요한 수학적 비밀을 다룰 때는 기존의 집을 보수하려 하지 마십시오. 집을 허물고 처음부터 보안이 되도록 설계된 새 집을 지으십시오. 그것이 더 빠르고, 더 안전하며, 패치가 남길 수 있는 미세한 틈도 놓치지 않는 길입니다.