무작위 키는 복구용 키가 아니었다. 실패를 침묵시키는 방법이었다: RFC 3218

요약

• RFC 3218은 CMS 수신자의 오류와 타이밍을 암호 인터페이스의 일부로 취급했다. 형식이 잘못된 RSAES-PKCS1-v1_5 블록을, 올바른 형식이지만 잘못된 콘텐츠 암호화 키를 담은 블록과 구분할 수 있다면, 반복 질의를 통해 보호된 키 자료가 드러날 수 있었다.
• 무작위 채우기(random filling) 대응책은 형식이 잘못된 키 풀기 결과를 예상 길이의 새 무작위 CEK로 바꾸고 콘텐츠 및 무결성 처리로 계속 진행했다. 그 대체물은 의도적으로 올바른 키가 아니었다. 목적은 앞선 실패를 뒤따르는 평범한 실패와 구분할 수 없게 만드는 것이었다.

위험한 출력은 평문이 아니었다. 그것은 수신자가 보여주기를 거부한 평문의 형태에 관한 예/아니오 답이었다.

이 구분은 RSA 암호화에 대한 공격이 왜 무해해 보이는 오류 처리에서 시작될 수 있는지를 설명한다. CMS 수신자는 RSA 개인 키를 보유했다. 공격자는 가로챈 암호화된 콘텐츠 암호화 키, 즉 CEK를 가지고 있었고 관련 암호문을 제출할 수 있었다. 수신자는 복호화된 블록을 출력할 필요가 없었다. 블록이 PKCS #1 v1.5 형식을 충족할 때와 그렇지 않을 때 서로 다른 방식으로 행동하기만 하면 되었다.

1998년 Daniel Bleichenbacher는 그 단일 비트가 어떻게 적응적 선택 암호문 공격(adaptive chosen-ciphertext attack)을 뒷받침할 수 있는지 보여주었다. 공격자는 암호문을 변형하고, 서버가 그 결과를 적합하다고 처리하는지 관찰하고, 지금까지 알아낸 모든 것에 기초해 다음 변형을 선택했다. 연속되는 작은 답들이 숨겨진 평문을 포함하는 수치 구간을 좁혀 나갔다. 개인 키는 수신자 내부에 남아 있었지만, 그 키의 판단이 공개적으로 복호화 작업을 수행한 셈이었다.

RFC 3218은 그 교훈을 Cryptographic Message Syntax로 옮겼다. 이 문서는 2002년 1월에 정보성(Informational) RFC로 발표되었으며, 새로운 암호화 형식이 아니었다. 문제는 운영적이었다. CMS 구현들은 이미 RSA PKCS #1 v1.5를 사용해 메시지 내용을 보호하는 대칭 키를 운반하고 있었다. 이미 배포된 형식을 즉시 대체할 수 없을 때 수신자는 무엇을 해야 하는가?

인코딩된 블록은 엄격한 문법을 가졌다.00 02로 시작하고, 최소 8개의 0이 아닌 무작위 패딩 옥텟이 이어지고, 0 구분자가 삽입되고, 마지막에 운반되는 값이 온다. CMS에서 그 마지막 값이 CEK였다. 따라서 개인 키 연산은 구문적으로 유효한 키 운반 블록을 반환하지 않고도 바이트를 반환할 수 있었다.

그것이 RFC 3218이 지켜야 했던 첫 번째 경계였다. RSA 거듭제곱 연산이 끝났다는 것은 인코딩된 블록이 유효하다는 것과 같지 않았다. 유효한 블록은 예상된 알고리즘과 길이의 CEK를 담고 있다는 것과 같지 않았다. 올바른 길이의 CEK가 반드시 발신자가 사용한 CEK인 것도 아니었다. 콘텐츠 복호화가 바이트를 만들어냈다고 해서 그 바이트가 무결성 검사를 통과했다는 뜻도 아니었다. 그리고 인증된 콘텐츠라고 해서 그 자체로 애플리케이션이 이를 받아들이거나 그에 따라 행동했다는 것이 증명되지는 않았다.

이 단계들을 내부적으로 하나로 뭉갠 구현은 감사하기 어려울 것이다. 이 단계들을 외부에 노출하는 구현은 오라클이 될 수 있었다.

백만 메시지 공격(Million Message Attack)이라는 이름은 운영적인 추정에서 나왔다. RFC 3218은 가로챈 암호문C와C' = C * S^e mod n형태의 변형된 값들을 설명했다. 대략 2^16번의 변형 중 한 번이 예상된 두 옥텟으로 시작하는 평문을 만들어냈다. RFC가 검토한 조건에서 전체 상호작용은 2^20 규모의 메시지와 응답이 필요할 수 있었다.

그 숫자는 자연법칙도, 모든 대상에 대한 정확한 예산도 아니었다. 그것은 위협의 형태를 표현했다. 백만 건의 요청은 각각에 대해 사람이 메시지를 열고 답해야 한다면 터무니없는 일이었다. 수신자가 메일링 리스트 에이전트나, 기계적 규모로 복호화·분류·응답하는 무인 서비스라면 이야기가 달라졌다.

자동화는 공격자의 자원을 인내심에서 트래픽으로 바꾸었다. 반복을 공급한 것은 수신자였다.

CMS는 제출된 래핑된 키가 도착한 뒤 여러 가지 결과를 낼 수 있었다. RSA 블록이 형식에 어긋날 수 있었다. 형식은 맞지만 가짜 CEK를 담고 있을 수 있었다. 가짜 CEK는 무결성 실패로 이어질 수 있었다. 콘텐츠에 인증된 무결성이 없다면 무작위처럼 보이는 평문이 우연히 겉보기에 유효한 CBC 패딩을 만들어낼 수도 있었다. 진짜 CEK가 복구될 수도 있었지만, 변형된 공격 질의에 대해 그런 결과가 나오는 것은 극히 드문 일이었다.

공격은 그 모든 결과가 보일 것을 요구하지 않았다. 잘못된 PKCS #1 형식이라는 첫 번째 결과를, 형식은 올바르지만 키가 틀린 데서 비롯된 이후 결과들과 구분할 수 있기만 하면 되었다. 서로 다른 진단 문구로도 가능했다. 응답 대 침묵, 연결 재설정, 메일 반송, 서명 오류 통지, 반복 가능한 타이밍 차이도 마찬가지였다.

RFC 3218의 주된 대응책은 무작위 채우기였다. PKCS #1 디코딩이 실패하면 수신자는 그 분기에서 멈추지 않았다. 선택된 콘텐츠 암호화 알고리즘이 기대하는 길이의 암호학적으로 무작위한 CEK를 생성하고, 마치 RSA 키 풀기가 그 값을 만들어낸 것처럼 계속 진행했다.

그다음 수신자는 콘텐츠 복호화를 시도했다. 메시지에 사용 가능한 통상의 서명, MAC, 패딩 또는 애플리케이션 검사를 수행했다. 결국 만들어진 키는 거의 확실히 평범한 하류 실패를 일으켰다. 외부에 보고되는 오류와 그 오류에 도달하기까지 걸린 시간은, 올바른 형식의 블록이 잘못된 CEK를 담고 있을 때 지나는 경로와 비슷해야 했다.

따라서 무작위 키는 백업 비밀이 아니었다. 발신자의 CEK를 복구하지도, 메시지를 보존하지도, 암호문을 사용 가능하게 만들지도 않았다. 그것은 공격자의 관찰 표면에서 하나의 분기를 지우기 위해 도입된 일회용 상태였다. 그 키의 올바름은 정확히 예측 불가능하고 거의 확실히 틀리다는 데 있었다.

그렇기 때문에 고정된 대체 키는 재앙이 될 것이다. 개발자는 상수 하나를 선호할 수 있다. 테스트하기 쉽고 오류 경로에서 무작위 생성기를 호출하지 않아도 되기 때문이다. 그러나 그 상수를 알아내거나 추측한 공격자는 그 값으로 CMS 콘텐츠를 암호화하고, 그 콘텐츠를 형식이 잘못된 RSA 래핑 키와 결합해 제출할 수 있다. 수신자가 대체 분기로 들어가면 콘텐츠가 성공적으로 복호화될 수 있다. 들어가지 않으면 패키지는 실패할 것이다. 그렇게 주장된 대응책은 더 강력한 오라클을 만들어낼 뿐이다.

RFC 3218은 새롭고 암호학적으로 무작위한 자료를 요구했다. 재사용은 실패 분기에 안정적인 의미적 정체성을 부여할 것이다. 공격자는 패딩이 유효한지 묻는 것을 멈추고, 수신자가 알려진 대체물을 선택했는지 묻기 시작할 수 있었다.

새로운 무작위성조차도, 실패 후에만 생성되고 그 생성이 관찰 가능하게 느리다면 유출될 수 있었다. 그래서 RFC는 덜 직관적인 구현 전략을 제안했다. 필요한지 알기 전에 모든 메시지에 대해 무작위 후보를 생성하고, 유효한 키 풀기 후에는 이를 폐기하는 것이다. 그러면 성공 경로와 실패 경로가 비슷한 무작위 생성 비용을 치른다.

이것은 상수 시간에 대한 보편적 증명이 아니었다. 메모리 접근, 파싱, 로깅, 네트워크 동작, 이후의 애플리케이션 작업은 여전히 달라질 수 있었다. 그것은 오류 문자열이 균일하다고 자축하는 대신, 명백한 타이밍 분기 하나를 제거하라는 지침이었다.

길이는 또 다른 숨은 분기를 만들었다. 일반적인 RSA/PKCS #1 계층은 인코딩된 블록이 구문적으로 유효하다는 것을 알 수 있지만, 애플리케이션이 8바이트, 16바이트, 24바이트, 32바이트 중 어느 CEK를 기대하는지는 알 수 없을 수 있었다. 그 하위 계층이 값을 반환하고 상위 CMS 계층이 잘못된 길이를 눈에 띄게 다른 방식으로 거부한다면, 오라클은 그저 위로 이동했을 뿐이다.

길이를 인식하는 계층도 무작위화해야 했다. 선택된 콘텐츠 암호에 맞지 않는 CEK를 담은 올바른 형식의 블록 역시 동일한 은폐된 하류 경로로 들어가야 했다. 설계 책임은 소프트웨어 경계를 넘어섰다. 암호 기본 요소가 모든 무효 사례를 인식하는 데 필요한 알고리즘 맥락을 갖지 못한다면, 그것만으로 전체 방어를 제공할 수 없었다.

RFC 3218은 공격자의 작업량을 늘리는 방법으로 더 강한 검증을 논의했다. 선두의00 02만이 아니라 요구되는 모든 패딩 옥텟을 확인하라. CEK 길이를 확인하라. DES 계열 알고리즘이라면 해당되는 경우 키 패리티를 확인하라. 조건이 하나 늘어날 때마다 무작위로 변형된 블록이 통과할 가능성은 줄어들었다.

그러나 더 엄격한 검사가 지배 규칙을 바꾸지는 않았다. 더 희귀해진 오라클도 여전히 오라클이었다. 수신자가 어느 조건이 실패했는지 알려준다면, 공격자는 비용이 더 들 뿐 계속 그 비트를 수집할 수 있었다.

인증되지 않은 CBC 콘텐츠는 하류 경로를 특히 모호하게 만들었다. 무작위 복호화가 패딩처럼 보이는 바이트로 끝날 수 있었다. 구현이 마지막 옥텟을 절단 길이로 그대로 신뢰한다면, RFC 3218은 겉보기 성공 확률을 약 32분의 1로 추정했다. 모든 패딩 옥텟이 요구된 값을 담고 있는지 검증하면 그 확률은 255분의 1 수준으로 낮아졌다.

그 확률들이 무작위 평문을 의미 있게 만들지는 않았다. 그것들은 왜 복호화기가 패딩된 버퍼를 반환했다는 사실이 약한 수락 사건인지를 보여주었다. MAC이나 서명은 더 강한 이후의 거부 지점을 제공했다. 그러나 인증된 콘텐츠조차도 수신자가 앞선 패딩 결과를 별도로 노출하도록 허용하지 않았다. 방어 전체가 최초의 분기를 질의 응답으로 만들지 않는 데 달려 있었다.

OAEP는 더 깔끔한 암호학적 방향을 제시했다. PKCS #1 v2.0은 RSAES-OAEP를 규정했고, RFC 3218은 논의 중인 공격이 OAEP에는 적용되지 않는다고 밝혔다. 그러나 OAEP는 PKCS #1 v1.5와 전송 형식 면에서 호환되지 않았다. 발신자와 수신자가 새 인코딩에 합의해야 했지만, 이미 설치된 CMS 소프트웨어, 인증서, 알고리즘 식별자, 상호운용성 기대는 옛 방식에 붙어 있었다.

따라서 전환 문제는 더 나은 기본 요소의 이름을 부르는 것으로 해결되지 않았다. 구 형식이 여전히 존재하는 동안 운영 중인 시스템에는 안전한 행동이 필요했다. RFC 3218은 호환성 대응책이었다. 배포가 이동할 수 있을 때까지 레거시 수신자가 드러내는 것을 제한하는 것이다.

TLS는 RSA로 암호화된 premaster secret과 관련해 같은 계열의 위험을 겪었다. 그 규격들은 서버에게 암호화된 secret의 형식이 잘못되었는지 또는 버전이 틀렸는지를 드러내지 않고 무작위 자료로 계속 진행하라고 지시했다. 유사성은 시사적이지만, 그 근거는 프로토콜별이었다. CMS 메일 처리기와 TLS 핸드셰이크는 서로 다른 이후 동작, 상태 기계, 애플리케이션 결과를 노출했다.

그 규율은 코드 패턴보다 넓었다. 초기 파서가 외부 프로토콜이 안전하게 답할 수 없는 질문에 답하게 두지 말라. 외부 프로토콜이 어떤 실패를 드러낼 수 있는지, 얼마나 많은 작업이 여전히 수행되어야 하는지, 어떤 이후 사건이 최종 거부를 담당할 수 있는지를 결정해야 한다.

RFC 3218은 무작위 채우기가 메시지를 인증한다거나, 모든 타이밍 채널을 막는다거나, 손상된 개인 키를 복구한다거나, 구현이 안전함을 증명한다고 주장하지 않았다. 배포 현황 조사를 발표하지도 않았다. 그 성과는 더 좁고 더 오래갔다. 수신자로 하여금 침묵은 설계되어야 한다는 점을 인정하게 만든 것이다. 하나의 내부 구분이 반복적으로 질의될 수 있다면, 오류 처리는 암호 시스템의 일부다.