Granite: A Modular Methodology for Foundational Verification of Hardware-Software Leakage Contracts
Granite는 결정론적 ISA 누설 계약(leakage contracts)과의 추적 등가성(trace equivalence)을 확립함으로써 RTL 프로세서의 기능적 정확성과 비누설성을 모두 검증하고, 이를 통해 신뢰 컴퓨팅 기반(trusted computing base)에서 중간 명세(intermediate specifications)를 제거할 수 있도록 하드웨어와 소프트웨어 증명의 구성을 가능하게 하는 모듈형의 기초적인 방법론을 도입한다.
원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기
당신이 초고속 레이스카를 만들고 있다고 상상해 보세요. 당신은 차를 믿을 수 없을 정도로 빠르게 만들고 싶어서 터보차저, 예측 조향 장치, 그리고 당신이 다음에 어떤 코너를 돌지 추측하는 시스템까지 추가했습니다. 하지만 함정이 있습니다. 만약 자동차 엔진이 왼쪽으로 회전할 때만 특정한 '덜컥' 소리를 낸다면, 옆에서 엿듣고 있는 은밀한 스파이가 그 소리만으로 당신의 전체 경로를 알아낼 수 있습니다. 컴퓨터 칩의 세계에서는 이를 '타이밍 부채널(timing side channel)'이라고 부릅니다. 수년 동안 프로그래머들은 비밀 데이터를 다룰 때는 무엇을 다루든 상관없이 정확히 동일한 시간이 걸리는 코드를 작성하려고 노력해 왔습니다. 마치 스파이가 소리를 내지 않고 복도를 지나가려는 것처럼 말이죠. 하지만 칩이 더 빠르고 똑똑해짐에 따라, 칩들은 거울을 보려고 갑자기 멈추거나 속도를 확 높이는 것과 같은 작고 예측 불가능한 소음들을 의도치 않게 만들어내기 시작했습니다. 이는 비밀을 누설하는 사고가 되었습니다. 이 논문은 당신의 코드가 완벽할지라도, 하드웨어 자체가 심장 박동의 리듬을 통해 당신의 비밀을 유출할 수도 있다는 무시무시한 아이디어를 다룹니다.
Granite라고 알려진 이 연구진은 컴퓨터 칩이 비밀을 안전하게 지키고 있음을 수학적으로 증명하는 새로운 방법을 구축했습니다. 그들은 단순히 추측하거나 테스트를 실행한 것이 아닙니다. 그들은 컴퓨터가 어떻게 행동해야 하는지에 대한 고수준 규칙(명령 세트, ISA)에서부터 아주 작은 전선과 트랜지스터(RTL)에 이르기까지를 연결하는 엄격하고 단계적인 수학적 논증을 만들어냈습니다. 그들의 주요 발견은 칩의 타이밍이 버튼을 누른 것과 같이 공개되어도 되는 요소들에 의해서만 결정되며, 암호나 암호화 키와 같은 비밀 데이터에 의해서는 절대 결정되지 않음을 증명하는 방법입니다. 그들은 단순히 칩이 제대로 작동하는 것처럼 보이거나 표준 테스트를 통과했다고 해서 신뢰할 수 있다는 생각을 명시적으로 부정하며, 이러한 특정 종류의 증명이 없다면 숨겨진 유출은 거의 확실히 존재한다는 것을 보여줍니다. 그들은 단순히 이것이 작동한다고 제안하는 데 그치지 않고, FPGA용으로 성공적으로 합성된 프로세서 설계에 대해 이를 공식적으로 증명했습니다. 다만 아직 포스트 합성(post-synthesis) 테스트를 위한 시스템 온 칩(SoC)으로 통합되지는 않은 상태였습니다.
위대한 칩 탐정 이야기
컴퓨터 프로세서를 고급 레스토랑의 북적이고 혼란스러운 주방이라고 생각해 보세요. 요리사들(하드웨어)은 고객들을 위해 요리(프로그램 실행)를 준비하고 있습니다. '명령 세트 아키텍처(ISA)'는 메뉴판이자 레시피 북입니다. 그것은 주방에 이렇게 말합니다. "버거 주문이 들어오면, 결국 버거를 내놓아야 한다." 하지만 메뉴판은 버거를 만드는 데 얼마나 오래 걸리는지, 혹은 요리사가 언제 칼을 잡는지까지는 말해주지 않습니다.
옛날에는 요리사들에게 "상수 시간(constant-time)"을 지키라는 지시가 내려졌습니다. 이는 고객이 샐러드를 주문하든 스테이크를 주문하든 요리사가 채소를 썰 때 정확히 같은 속도로 썰어야 함을 의미했습니다. 그래야 창밖에서 지켜보는 스파이가 채소 써는 리듬을 보고 무엇이 요리되고 있는지 알아낼 수 없기 때문입니다. 하지만 주방이 너무 빨라졌습니다. 요리사들은 '추측(speculation)'을 사용하기 시작했습니다. 그들은 고객의 주문이 확정되기도 전에 고객이 무엇을 원할지 추측하여 양파를 썰기 시작했습니다. 만약 추측이 틀리면, 양파를 버리고 다시 시작했습니다. 이 추측 게임은 새로운 우발적인 소음을 만들어냈습니다: 실수를 깨닫는 데 걸린 시간이나 특정 향신료를 집는 데 걸린 시간 등이 정보를 유출하기 시작한 것입니다. 스파이는 주방의 소리를 듣고 "아, 요리사가 0.0001초 동안 머뭇거렸네. 저건 분명히 비밀 양파가 들어간 요리를 하고 있는 거야!"라고 추론할 수 있게 되었습니다.
여기에 최고의 주방 검사관인 Granite가 등장합니다. Granite는 단순히 요리사를 관찰하는 것이 아니라, 비밀이 탈출하지 못하도록 주방의 규칙을 새로 씁니다.
"그림자 요리사"의 마법
Granite의 천재성은 "그림자 요리사(Shadow Chef)"를 이용한 영리한 트릭에 있습니다. 비밀 레시피를 알고 있는 진짜 요리사가 있다고 상상해 보세요. 또한 눈이 가려져 있고 공개된 주문 내용만 알고 있는 그림자 요리사도 있습니다.
Granite의 방법은 다음과 같이 말합니다: "우리는 진짜 요리사와 그림자 요리사가 완벽하게 발을 맞춰 움직인다는 것을 증명할 것이다." 만약 진짜 요리사가 양파가 커서 양파를 써는 데 5초가 걸렸다면, 그림자 요리사도 양파가 크다는 사실을 모르더라도 정확히 5초 동안 양파를 썰어야 합니다. 그림자 요리사의 타이밍은 오직 공개된 주문에 의해서만 결정됩니다. 만약 진짜 요리사의 타이밍이 비밀(예: 양파의 종류)에 의존하게 된다면, 두 요리사는 서로 맞지 않게 될 것이고 증명은 실패할 것입니다.
이를 위해 Granite는 '드라이버(Driver)'와 '위트니스(Witness)'를 도입합니다.
- **드라이버(Driver)**는 공개된 주문만을 듣는 메트로놈과 같습니다. 그것은 주방이 언제 앞으로 나아갈지를 결정하며, 주방의 동작 타이밍이 비밀 재료가 아닌 고객이 '알려지기를 원하는' 것에 의해서만 결정되도록 보장합니다.
- **위트니스(Witness)**는 주방의 무질서하고 예측 불가능한 부분들(예: 팬이 뜨거워서 발생하는 무작위 지연)을 위한 자리 표시자입니다. 위트니스는 이렇게 말합니다. "좋아요, 우리는 여기서 정확히 무슨 일이 일어나는지는 상관하지 않겠습니다. 단, 그것이 비밀에 의존하지만 않는다면 말이죠."
진짜 주방이 드라이버와 위트니스가 운영하는 주방과 똑같이 행동한다는 것을 증명함으로써, Granite는 주방의 리듬(타이밍)이 결코 비밀 재료를 드러낼 수 없음을 증명합니다.
모듈형 퍼즐
주방 전체를 점검하는 것은 너무 크기 때문에 한꺼번에 살펴보기가 매우 어렵습니다. Granite는 이 문제를 주방을 작고 독립적인 스테이션들로 나누어 해결합니다. 예를 들어 채소 써는 곳, 그릴 스테이션, 플레이팅 스테이션처럼 말이죠.
Granite는 각 스테이션이 개별적으로 안전하다는 것을 증명합니다. 예를 들어, "곱셈(Multiplier)" 스테이션(수학 계산을 수행하는 곳)은 만약 두 숫자를 곱하는 데 시간이 더 걸린다면, 그것이 숫자가 0이기 때문(이는 알려져도 되는 정보임)이지 어떤 비밀 값 때문이 아님을 확인받도록 체크됩니다. 모든 스테이션이 안전하다고 증명되면, Granite는 이들을 레고 블록처럼 조립합니다. 이 증명은 "모듈형(modular)"이기 때문에, 만약 그릴 스테이션을 더 빠른 것으로 교체한다면 전체 주방을 다시 확인할 필요 없이 새 스테이션만 확인하면 되며, 전체 시스템의 안전성은 그대로 유지됩니다.
최종 판결
연구진은 단순히 말로만 설명한 것이 아니라, 직접 프로세서 설계를 구축하고 그 위에 증명을 실행했습니다. 그들은 이미 "상수 시간"임이 알려진 소프트웨어(Salsa20이라는 암호화 프로그램)를 가져왔고, 이 프로그램이 그들의 프로세서 설계 위에서 실행될 때 타이밍을 통해 어떠한 비밀도 유출하지 않음을 증명했습니다.
이것은 우리가 무엇을 신뢰해야 하는지를 바꾸는 중요한 사건입니다. 보통 우리는 소프트웨어와 하드웨어 사이의 복잡한 계약을 신뢰해야 합니다. 하지만 Granite는 하드웨어 증명과 검증된 소프트웨어 증명을 연결하면, 하드웨어-소프트웨어 계약 자체를 신뢰 목록에서 제외할 수 있음을 보여줍니다. 다만, 이 증명은 여전히 명령어 세트 계약의 공식적 정의와 코드를 하드웨어 기술 언어로 변환하는 도구와 같은 몇 가지 핵심 구성 요소에 의존하며, 이들은 여전히 "신뢰 컴퓨팅 기반(Trusted Computing Base)"에 남아 있습니다. 그들은 심지어 자신들의 설계에서 버그를 찾아내기도 했습니다. 특정 제어 스위치(CSR)에 쓰는 동작이 정보를 유출할 수 있다는 것을 깨닫고, 증명이 완료되기 전에 이를 수정했습니다.
요약하자면, Granite는 현대 컴퓨팅의 혼란스럽고 시끄러운 주방을 침묵하며 비밀을 지키는 요새로 바꾸어 놓으며, 컴퓨터 칩이 속도와 보안을 동시에 가질 수 있음을 수학적으로 증명해 냅니다.
연구 분야의 논문에 파묻히고 계신가요?
연구 키워드에 맞는 최신 논문의 일일 다이제스트를 받아보세요 — 기술 요약 포함, 당신의 언어로.