본문으로 건너뛰기
행간을 읽지 않는 Tamarin의 KEMTLS 보안 증명
목차

행간을 읽지 않는 Tamarin의 KEMTLS 보안 증명 (2022-02)

원문 정보

  • 원문: Building Confidence in Cryptographic Protocols
  • 부제: An introduction to formal analysis and our proof of the security of KEMTLS
  • 매체 · 게시일: The Cloudflare Blog · 2022-02-24
  • 저자: Thom Wiggers, Jonathan Hoyland
  • 포스트 퀀텀 주제의 블로그 시리즈 중 한 편으로, 원문이 다른 편을 직접 번호로 가리키지는 않습니다.
  • 원문 내용을 바탕으로 재구성한 요약입니다.

설계자도 깨지 못한 암호 시스템

“아무리 애써도 깨지 못했다”는 말만으로는 새 암호 시스템을 믿기 어렵습니다. 설계자가 자기 설계를 깨지 못했다면, 그 설계를 공격할 만큼 똑똑하지 못했다는 뜻일 뿐입니다. 알려진 공격을 모두 시도하면 단순한 결함은 걸러낼 수 있어도 새로운 공격이나 기존 공격의 변형까지 없다고 보장하지는 못합니다.

상금을 걸고 다른 사람에게 맡겨도 확신은 남지 않습니다. 공격을 알아낸 사람이 상금보다 사이버 범죄자나 정부에 그 방법을 파는 쪽을 택할 수도 있기 때문입니다. 이런 한계 때문에 연구자들은 1980년대 후반부터 수학으로 프로토콜의 안전성을 증명하기 시작했습니다. 양자 컴퓨터의 공격에 안전하다는 새 알고리즘에도 같은 요구가 따릅니다.

증명은 가정에서 출발합니다. 유클리드가 공리에서 정삼각형 작도를 이끌어 냈듯, 보안 증명도 논리적 추론을 쌓아 목표 명제에 도달합니다. 가정이 맞으면 결론이 참이라는 보장입니다. 규모는 사뭇 다릅니다. 이번 KEMTLS 증명은 거의 50만 줄로, 유클리드에게 없던 컴퓨터가 사람의 안내와 자동 알고리즘을 결합해 감당한 작업입니다.

서명 대신 키 교환을 택한 KEMTLS

KEMTLS는 TLS 핸드셰이크의 인증에 키 캡슐화 메커니즘(KEM)을 쓰자는 제안입니다. 보통은 인증서의 공개키에 대응하는 개인키를 가졌음을 서명으로 증명합니다. KEMTLS에서는 인증서의 KEM 공개키로 공유 비밀을 캡슐화합니다. 인증서를 제시한 쪽이 올바른 개인키를 가져야 이를 풀 수 있고, 그래야 암호화된 트래픽을 읽습니다. 포스트 퀀텀 서명과 키 교환 사이의 절충은 이 시리즈의 다른 글에서도 다룬 주제입니다.

이 핸드셰이크에는 이미 종이와 펜으로 쓴 보안 증명이 있었습니다. 그런데 최상위 보안 학회에 논문이 게재된 뒤에도 모델의 속성을 정의한 부분에서 여러 실수가 발견됐습니다. 증명을 정확하게 쓰는 일도 어렵지만, 남이 쓴 증명을 검증하는 데도 그에 버금가는 주의가 듭니다.

임시 키 교환을 모델링할 때 겪은 시행착오도 있습니다. KEMTLS 저자들은 처음에 IND-CPA 안전성을 갖춘 KEM이면 충분하다고 가정했습니다. 시뮬레이션을 의사코드로 풀어 쓰고 나서야 디캡슐화 질의 하나에 응답할 오라클이 필요함을 알아냈습니다. 실제로 요구되는 조건은 IND-CCA의 약한 변형인 IND-1CCA 안전성이었습니다. IND-CPA만으로는 안전하지 않았습니다.

컴퓨터는 행간을 읽지 않습니다. 사람은 문장에 엄밀하게 적히지 않은 의도까지 알아서 이해하지만, 컴퓨터는 시킨 일만 합니다. 모델과 증명을 정확하게 작성하면 끝까지 실행해 검증할 수 있는 프로그램이 된다는 점이 Tamarin을 쓰는 이유입니다. 물론 모델을 잘못 만들거나 증명기 자체에 버그가 있을 가능성은 남습니다. 기계 검증은 종이 증명을 보완합니다.

서로 다른 모델을 쓰는 이점도 있습니다. 종이 증명의 계산 모델은 보안 강도의 경계를 정밀하게 제시하는 ‘고해상도’ 모델이지만, KEMTLS의 계산 증명에서는 TLS 메시지 형식을 생략했습니다. Tamarin의 기호 모델은 암호 원시 함수가 안전하다는 가정 아래 목표 충족 여부를 예·아니오로 답하는 ‘저해상도’ 모델입니다. 대신 메시지 형식까지 담아 공격자가 메시지를 바꾸거나 순서를 뒤집고 새로 만들어 넣는 경우를 분석할 수 있습니다.

확장을 함께 검토할 여지도 생깁니다. ‘사전 배포된 키’ 확장은 종이로는 단독으로만 증명됐지만, Tamarin에서는 본체와 같은 모델에 넣어 둘 사이의 상호작용에서 생길 공격을 검토할 수 있습니다. 증명의 복잡도는 지수적으로 늘어납니다. 그래도 Tamarin은 계산 자원을 더 써서 다룰 수 있고, 종이에서는 그만큼 더 세심한 검토가 요구됩니다.

가능한 실행을 모두 담은 Tamarin의 트리

공격자가 메시지를 어떻게 조작할지 일일이 나열해서는 끝이 없습니다. 프로세스 대수는 구체적인 값을 기호로 바꾸고, 상호작용하는 프로그램과 그 표현을 조작하는 규칙을 정의합니다. 개별 입력마다 실행해 보는 대신 가능한 모든 입력에 적용되는 논리를 쓸 수 있습니다. 여기에는 공격자가 일부 입력의 모든 값을 대입해 보는 일이 불가능하다는 단순화도 들어갑니다. 실제로는 실행 불가능할 만큼 비현실적이라는 뜻이며, 증명도 그 가정 아래에서 성립합니다.

Tamarin이 다루는 세계는 ‘사실의 가방’입니다. 키, 인증서, 참여자의 신원, 메시지를 사실로 표현하고, 빈 가방에서 시작해 규칙에 따라 사실을 꺼내거나 새로 넣습니다. 필요한 전제 조건이 갖춰져야 규칙을 적용할 수 있으며, 적용할 때 일어난 행동(action)도 기록합니다.

예를 들어 Register_pk는 새 값 ~ltkA로 참여자의 키 쌍을 등록하고 GenLtk 행동을 남깁니다. 공개키는 네트워크에도 내보냅니다. Tamarin의 Dolev-Yao 모델에서는 공격자가 네트워크를 제어하므로, 이렇게 내보낸 공개키는 공격자도 갖게 됩니다.

규칙을 따라가며 행동을 기록하면 한 번의 실행을 얻습니다. 어느 지점에서 적용 가능한 규칙이 여럿이면 각각을 가지로 뻗어, 가능한 모든 실행을 하나의 트리로 생각할 수 있습니다. 이제 필요한 것은 ‘나쁜 실행’의 정확한 정의입니다. 세션 키의 비밀성을 원한다면 공격자가 세션 키를 아는 상태에 도달하는 경로가 있는지 묻습니다. 이것이 도달성 보조정리입니다.

그런 경로가 없음을 증명하면 모델 안에서는 해당 보안 목표가 성립합니다. 프로토콜을 모델로 기술하고, 원하는 속성을 명시하고, 모든 실행에서 그 속성이 유지되는지 엄밀하게 증명하는 작업이 형식 분석입니다.

실행 가능성부터 확인한 KEMTLS 모델

모델은 처음부터 만들지 않았습니다. 저자들은 Cremers 등이 TLS 1.3 표준화 과정에서 만든 Tamarin 모델을 가져와, 임시 키 교환의 Diffie-Hellman 연산을 KEM 연산으로 바꿨습니다. 인증서 처리에서도 서명을 검증하는 대신 암호문을 담은 KemEncapsulation 메시지를 돌려보내도록 수정했습니다.

바뀐 규칙 client_recv_server_cert_emit_kex는 클라이언트가 서버 인증서를 받은 뒤 새 공유 비밀을 인증서의 공개키로 캡슐화해 보내는 단계입니다. 클라이언트가 C2d 상태에 있고, 서버 핸드셰이크 키로 암호화한 인증서 메시지를 받았으며, 서버 공개키와 새 난수가 있어야 실행됩니다. 규칙을 적용하면 클라이언트는 C3로 이동하고, 자신의 핸드셰이크 키로 암호화한 캡슐화 메시지를 네트워크에 내보냅니다.

메시지를 받았다는 사실만으로 정직한 서버가 보냈다고 믿지는 않습니다. 공격자가 바꾸거나 위조했을 가능성까지 모델이 다뤄야 합니다. 가방에 든 사실도 모두 같은 방식으로 사라지지는 않습니다. !Pk처럼 !가 붙은 사실은 계속 남아 여러 번 사용할 수 있습니다.

보안을 묻기 전에 실행부터 확인했습니다. 아예 실행되지 않는 프로토콜이라면 비밀을 누설할 일도 없기 때문입니다. 첫 보조정리 exists_C2d는 exists-trace로 해당 규칙이 작동하는 경로가 최소 하나 있는지 확인합니다. 모델이 적어도 C2d까지 진행한다는 검증입니다.

공격자도 더 강하게 만들었습니다. 기호 모델의 암호는 완벽하므로 기본 공격자는 키 없이 메시지를 복호화하거나 캡슐화를 풀지 못합니다. 저자들은 장기 개인키를 공개하는 Reveal_Ltk 규칙을 추가하고, 공개 시점에 RevLtk 행동을 기록하도록 했습니다. 임시 KEM 개인키를 노출하는 능력은 RevEKemSk로 표현했습니다.

세션 종료 뒤의 키 유출까지 다룬 보조정리

secret_session_keys가 보장하는 내용에는 시점 조건이 있습니다. 참여자가 세션을 마치기 전에 상대의 장기 개인키와 양쪽의 임시 KEM 개인키가 공개되지 않았다면, 공격자는 그 참여자의 읽기 키 kr을 알지 못한다는 명제입니다.

공격자의 키 탈취 능력을 없앤 것은 아닙니다. 공격자는 해당 세션에 쓰인 키를 제외한 다른 키들을 침해할 수 있습니다. 다른 참여자를 속여 같은 임시 키를 쓰게 만드는 공격이 가능했다면 이 보조정리는 성립하지 않았을 것입니다.

세션이 끝난 뒤의 키 유출도 허용합니다. 공격자가 과거의 통신을 기록해 두었다가 나중에 새 양자 컴퓨터로 장기 키를 얻더라도, 기록한 세션을 복호화하지 못한다는 속성을 증명합니다. 이것이 전방향 비밀성(forward secrecy)입니다.

읽기 키만 등장하는 데도 이유가 있습니다. 보조정리가 모든 참여자에게 적용되며, 클라이언트의 읽기 키는 서버의 쓰기 키이고 그 역도 성립합니다. 따라서 같은 명제가 양쪽에 적용되면 두 방향의 키가 모두 보호됩니다.

작은 수정마다 되풀이한 Tamarin 검증

Tamarin에 모델과 보조정리를 건넨다고 모든 증명이 자동으로 끝나지는 않습니다. 자동 증명기가 무엇을 먼저 풀어야 할지 찾지 못하면 수동 인터페이스에서 다음 목표를 골라야 합니다. 증명이 여러 가지로 나뉘는 동안, 이미 증명된 가지는 초록색으로 표시되고 나머지 가지에서 사람이 선택을 이어 갑니다.

이 과정에서 반복되는 하위 목표를 발견하면 도우미 보조정리로 분리했습니다. 프로그램에서 함수를 추출하듯, 작은 증명을 먼저 끝내고 큰 증명에서 재사용하는 방식입니다. 덕분에 자동 증명이 가능해지기도 했습니다. 사람이 목표를 고를 때 쓰던 휴리스틱을 오라클 스크립트로 옮겨 까다로운 증명을 자동화한 경우도 있습니다.

도우미가 많다고 늘 좋은 것은 아닙니다. Tamarin이 특정 도우미 보조정리에 이끌려 관련 없는 추론을 길게 이어 가면, 그 보조정리를 숨겨야 자동 증명기가 나머지를 풀기도 합니다. 도구가 어느 보조정리를 적용 중인지 명확하지 않아, 눈에 띄는 고유한 변수 이름으로 목표의 출처를 추적하는 요령까지 필요했습니다.

자동화의 가치는 다시 실행할 때 드러났습니다. 모델이나 보조정리, 재사용하는 보조정리 중 하나라도 조금 바뀌면 전부 다시 증명해야 합니다. 매번 수작업을 반복했다면 이 작업은 완료에 한참 못 미쳤을 것이라고 저자들은 설명합니다.

실제로 TLS 1.3 모델의 session_key_agreement 보조정리에서 버그 두 개를 찾았습니다. 증명을 마친 뒤의 리팩터링이 겉보기에는 무해했지만 명제의 의미를 바꿔 버린 경우였습니다. 원래 정의는 올바른 보안 속성을 다뤘으므로 보안 문제로 이어지지는 않았습니다. 그래도 원인을 찾는 데 많은 시간을 썼고, 그 과정을 거쳐 KEMTLS가 설정한 보안 목표를 달성한다는 증명을 완성했습니다.

증명에서 빠져 있던 인증서 재사용

증명에 적힌 가정과 실제 프로토콜이 허용하는 동작 사이에는 틈이 생길 수 있습니다. TLS 1.3 증명의 초기 명세는 클라이언트와 서버가 같은 인증서를 쓰지 않는다고 가정했습니다. 그러나 프로토콜 명세는 그 사용을 금지하지 않았습니다. 이 차이에서 클라이언트를 속여 자기 자신에게 접속하게 만드는 ‘Selfie’ 취약점이 나왔고, 자원 고갈 공격으로 이어질 가능성이 생겼습니다.

Needham-Schroeder도 BAN 논리로 안전성을 증명한 뒤, Lowe가 그 논리에서 다루지 않은 경우의 공격을 찾아냈습니다. 기계가 검증한 증명이라도 우리가 의도한 속성을 증명하는지, 필요한 상황을 모델에 담았는지까지 저절로 보장하지는 않습니다. 증명 자체에 실수가 있을 가능성도 남습니다.

그렇다고 형식 분석의 성과가 작았던 것은 아닙니다. TLS 1.3을 설계할 때는 심각한 보안 결함을 여러 건 찾아 표준화 전에 수정했습니다. 그 성과와 별개로, 프로토콜 설계의 증명은 특정 구현이 설계를 정확히 따르는지 알려 주지 않습니다. 저자들은 이 구현 문제를 다른 블로그 글에서 다루겠다고 예고합니다.

남은 작업에는 명세와 도구도 있습니다. 저자들은 새 보안 프로토콜 제안에 기계 검증된 보안 증명이 따라야 한다고 봅니다. 자연어 명세에서 피하기 어려운 해석 차이를 줄이기 위해 형식 명세 언어도 고려하자는 입장입니다.

프로토콜을 만드는 산업계도 직접 참여해야 합니다. 학계만으로 끝낼 수 있는 일이 아닙니다. 아직 비전문가가 쓰기에 도구가 충분히 편리하지 않다는 점은 저자들도 인정하며, 산업계와 학계가 함께 접근성을 높이는 작업을 기대합니다.

증명의 규모와 검증 항목
항목값
KEMTLS 증명 규모거의 500,000줄
사용 도구Tamarin (기호 모델, Dolev-Yao 공격자)
기반 모델Cremers 등의 TLS 1.3 Tamarin 모델
바꾼 부분Diffie-Hellman을 KEM 연산으로, 서명 검증을 KemEncapsulation 메시지로
도달성 보조정리exists_C2d (exists-trace)
핵심 보안 보조정리secret_session_keys (전방향 비밀성 포함)
공격자 능력RevLtk(장기키 공개), RevEKemSk(임시 KEM 개인키 공개)
필요한 KEM 안전성IND-CPA로는 부족, IND-1CCA 필요
종이 증명의 모델계산 모델 (이 글의 Tamarin 분석은 기호 모델)
모델에서 발견한 버그session_key_agreement 보조정리 2건 (보안 문제는 아님)
마지막 수정 일자