패딩

패딩은 데이터에 실제 내용이 아닌 값을 덧대 정해진 크기에 맞추는 일입니다. 컴파일러가 메모리에 값을 놓을 때 이 채움이 붙습니다. 암호가 데이터를 일정한 덩어리로 자를 때도 붙습니다.

상세

택배 상자에 물건을 담고 남은 곳에 완충재를 채웁니다. 완충재는 받는 사람이 주문한 물건이 아닙니다. 상자를 정해진 모양대로 채워 두는 몫만 합니다. 받는 사람은 완충재를 걷어 내고 물건만 꺼냅니다.

패딩은 실제 내용이 아닌 값을 덧대 데이터의 크기나 위치를 정해진 단위에 맞추는 일입니다. 덧대는 바이트를 채움 바이트라고 부릅니다. 비트 단위로 채우면 채움 비트입니다.

C 언어의 구조체가 한 예입니다. 구조체는 값 여럿을 한 덩어리로 묶는 자료형입니다. 묶인 값 하나하나를 필드라고 부릅니다.

int 를 4 의 배수 주소에 놓는 기계에서 char 필드 뒤에 int 필드를 적으면 둘 사이에 세 바이트가 빕니다. 그 세 바이트가 패딩입니다.

채움이 놓이는 곳은 분야마다 다릅니다. 무엇을 맞추려는지가 다르기 때문입니다.

아래 소절은 표의 다섯 분야를 셋으로 묶습니다. 주소를 맞추는 메모리 배치, 블록을 채우는 암호와 해시, 길이를 감추는 통신입니다. 텍스트 인코딩의 실물은 예시 절에 있습니다. 이름만 같은 화면 여백을 마지막에 봅니다.

메모리 배치의 채움

구조체는 필드 여럿을 메모리에 선언한 차례대로 놓습니다. 뒤에 적은 필드일수록 주소가 큽니다. 필드는 C 언어 용어로 구성원(member)이라고도 부릅니다.

필드마다 자기 자료형에 맞는 정렬 단위가 있습니다. 필드의 주소는 그 단위의 배수여야 합니다. 앞 필드가 끝난 주소가 다음 필드의 정렬 배수에 안 맞으면 컴파일러가 사이에 이름 없는 바이트를 끼웁니다. 이 바이트가 구조체 안의 패딩입니다.

맨 앞에는 패딩이 끼지 않습니다. 구조체를 가리키는 포인터는 곧 첫 필드를 가리킵니다. 끝에는 패딩이 낄 수 있습니다.

CPU(Central Processing Unit, 중앙처리장치)는 메모리를 한 바이트씩 읽지 않습니다. 네 바이트나 여덟 바이트씩 묶어 읽습니다. 이 묶음 하나를 워드라고 부릅니다. 정렬이 안 맞는 값은 워드 둘에 걸쳐 놓일 수 있습니다. 정렬이 안 맞는 접근은 맞는 접근보다 느립니다.

block-beta
columns 8
  W1["워드 · 주소 0~3"]:4 W2["워드 · 주소 4~7"]:4
  A["char a"]:1 P["패딩 3바이트"]:3 B["int b"]:4
  A2["char a"]:1 B2["int b · 워드 둘에 걸친다"]:4 E2["빈 곳"]:3

맨 윗줄이 워드 눈금입니다. 가운뎃줄이 정렬을 맞춘 배치입니다. int 가 4 에서 시작해 워드 하나에 들어갑니다. 주소 1~3 이 패딩입니다.

아랫줄은 채움 없이 붙여 놓았을 때입니다. int 가 주소 1~4 에 놓여 워드 둘에 걸칩니다.

패딩을 일부러 넣기도 합니다. 캐시는 메모리를 캐시 라인이라는 고정 크기 덩어리째로 올리고 내립니다.

CPU 안에서 따로 계산을 도는 단위를 코어라고 부릅니다. 서로 다른 코어가 고치는 두 변수가 한 캐시 라인에 같이 놓이면 라인이 코어 사이를 오갑니다. 두 코어는 남의 변수를 건드리지 않습니다. 그래도 라인을 주고받느라 서로 기다립니다.

이것을 거짓 공유라고 합니다. 변수 앞뒤에 채움을 넣어 서로 다른 캐시 라인으로 밀어내면 피할 수 있습니다. 앞의 패딩은 정렬을 맞추다 생깁니다. 이 패딩은 값을 떼어 놓으려고 넣습니다.

블록을 채우는 채움

블록 암호는 데이터를 정해진 크기로 잘라 하나씩 계산합니다. 그 고정 크기의 덩어리를 블록이라고 부릅니다. 블록 암호를 여러 블록에 이어 쓰는 방법을 모드라고 부릅니다.

ECB(Electronic Codebook, 전자 코드북)는 블록마다 따로 암호화하는 모드입니다. CBC(Cipher Block Chaining, 암호 블록 연결)는 앞 블록의 암호문을 다음 블록에 섞어 암호화합니다. 이 두 모드는 평문 전체의 비트 수가 블록 크기의 배수여야 합니다. CFB(Cipher Feedback, 암호 피드백) 모드도 같은 조건을 세그먼트라는 단위로 겁니다.

평문의 마지막 블록이 모자라면 비트를 늘려야 합니다. 흔한 방법은 데이터 맨 뒤에 여분의 비트를 덧붙이는 것입니다. 이 여분이 블록 암호의 패딩입니다.

받는 쪽은 복호한 다음 어디까지가 원래 데이터인지 가려야 합니다. 그 방법은 채움 방식마다 다릅니다. 갈래 절이 방식별로 나눠 봅니다.

SHA-1 과 SHA-2 계열 해시 함수도 메시지를 블록 단위로 먹습니다. 블록 크기는 알고리즘에 따라 512비트나 1024비트입니다. 채움을 붙여 전체 길이를 그 배수로 만듭니다.

블록 단위가 없으면 이 채움도 필요 없습니다. 바이트 단위로 이어서 계산하는 스트림 암호는 모자란 끝이 안 생깁니다. 길이를 앞에 적어 두고 그만큼만 읽는 길이 접두사 방식도 마찬가지입니다.

길이를 감추는 채움

암호화는 내용을 가리지만 길이는 못 가립니다. 암호문의 길이가 원문의 길이를 거의 드러냅니다.

TLS(Transport Layer Security, 전송 계층 보안)는 데이터를 레코드라는 단위로 잘라 암호화해 보냅니다. TLS 1.3 은 암호화한 레코드마다 채움을 덧대 크기를 부풀릴 수 있게 합니다. 보내는 쪽은 이 채움으로 오가는 데이터의 크기를 지켜보는 쪽에게서 감출 수 있습니다.

채울지는 보내는 쪽이 고를 수 있습니다. 채움이 없는 레코드는 채움 길이가 0 인 레코드일 뿐입니다. 언제 얼마나 채울지를 정하는 정책은 TLS 1.3 이 정하지 않습니다. 대가는 안 보내도 될 바이트를 더 보내는 것입니다.

TLS 1.3 은 길이를 엿보는 공격을 막는 장치를 따로 두지 않습니다. 이 채움이 응용 프로그램이 꺼내 쓸 장치입니다.

화면 배치에서 쓰는 같은 이름

웹 화면을 꾸밀 때도 패딩이라는 말을 씁니다. 여기서는 내용과 테두리 사이의 안쪽 여백을 가리킵니다. CSS(Cascading Style Sheets, 종속형 시트)의 padding 속성이 그 값입니다.

크기를 정해진 단위에 맞추려는 것이 아닙니다. 글을 읽기 편하게 벌려 놓으려는 것이라 하는 일이 다릅니다. 빈 곳을 채운다는 뿌리만 같습니다.

배경

컴퓨터 안에는 고정된 단위로만 일하는 부품이 많습니다. 프로세서는 값이 자기 정렬에 맞는 주소에 있을 때 더 빨리 읽습니다. 블록 암호의 몇몇 모드는 블록 크기의 배수로만 평문을 받습니다. SHA-1 과 SHA-2 계열 해시는 512비트나 1024비트 블록으로 계산합니다.

데이터는 이 단위를 모르고 만들어집니다. 길이나 위치가 단위에 딱 떨어지지 않으면 모자란 만큼을 무언가로 메워야 합니다. 이렇게 모자란 만큼 덧대는 값을 패딩이라고 부릅니다.

크기를 맞출 일이 없어도 채울 때가 있습니다. 길이 자체가 정보를 흘리기 때문입니다. 암호화한 패킷의 길이와 시각만 보고 무엇이 오갔는지 짚는 트래픽 분석이 그런 공격입니다. 정해진 영상 묶음만 내주는 동영상 서버처럼 가려낼 메시지가 몇 개 안 되면 특히 쉽습니다.

예시

x86-64 System V 의 구조체 배치

System V ABI(Application Binary Interface, 응용 프로그램 이진 인터페이스)의 x86-64 판은 C 자료형마다 크기와 정렬을 정합니다. 아래는 그 표의 일부입니다.

필드가 놓이는 곳은 오프셋으로 적습니다. 오프셋은 구조체 시작에서 센 바이트 거리입니다.

구조체는 필드 중 정렬이 가장 엄한 것의 정렬을 따릅니다. 필드마다 자기 정렬에 맞는 가장 낮은 오프셋에 놓입니다. 어떤 객체든 크기는 언제나 자기 정렬의 배수입니다.

이 표와 규칙으로 아래 두 구조체의 크기를 셀 수 있습니다. 담는 값은 둘이 같습니다.

struct A { char a; int b; char c; };  // 12
struct B { int b; char a; char c; };  // 8

오른쪽 숫자는 규칙대로 셈한 sizeof 값입니다. 단위는 바이트입니다.

A 에서 a 는 오프셋 0 에 놓입니다. b 는 4 의 배수여야 해서 오프셋 4 로 갑니다. c 는 8 에 놓여 여기까지 9 바이트입니다. A 의 정렬은 int 를 따라 4 이므로 크기를 4 의 배수인 12 로 올립니다. 채움은 1~3 과 9~11 두 곳입니다.

B 는 b 가 0~3, a 가 4, c 가 5 에 놓입니다. 6 바이트를 4 의 배수로 올려 8 이 됩니다. 채움은 끝 두 바이트뿐입니다. 큰 필드를 앞에 모으면 채움이 줄어듭니다.

block-beta
columns 12
  A1["char a"]:1 A2["패딩 3"]:3 A3["int b"]:4 A4["char c"]:1 A5["패딩 3"]:3
  B1["int b"]:4 B2["char a"]:1 B3["char c"]:1 B4["패딩 2"]:2 space:4

윗줄이 A, 아랫줄이 B 입니다. B 는 8 바이트에서 끝납니다. 크기를 정렬의 배수로 맞춰 두는 덕에 구조체를 배열로 늘어놓아도 둘째 칸부터 정렬이 안 깨집니다.

채움은 구조체에만 붙지 않습니다. long double 은 16 바이트를 차지합니다. 그중 뜻 있는 바이트는 앞 10 개뿐입니다. 나머지 6 바이트는 끝 채움입니다.

이 6 바이트의 내용은 정해져 있지 않습니다. 구조체의 채움 바이트도 내용이 정해져 있지 않습니다.

SHA-256 의 abc

SHA-256 은 메시지를 512비트 블록으로 먹습니다. SHA-1 · SHA-224 도 같은 규칙으로 채웁니다.

메시지 길이가 ℓ 비트면 먼저 끝에 비트 1 을 하나 붙입니다. 이어서 0 비트를 k 개 붙입니다. k 는 ℓ + 1 + k 를 512 로 나눈 나머지가 448 이 되는 가장 작은 0 이상의 수입니다. 마지막으로 ℓ 을 64비트 이진수로 적어 붙입니다.

메시지 abc 는 8비트 글자 셋이라 24비트입니다. 비트 1 하나, 0 이 448 − (24 + 1) = 423 개, 길이 24 를 적은 64비트가 붙습니다. 모두 합쳐 512비트 한 블록이 됩니다.

block-beta
columns 4
  M["abc · 24비트"]:1 O["1 · 1비트"]:1 Z["0 · 423비트"]:1 L["길이 24 · 64비트"]:1
  T["합 512비트 · 블록 하나"]:4

원래 길이를 채움 끝에 함께 넣는 것이 이 채움의 특징입니다. 이렇게 채운 512비트 전체가 해시 계산에 들어갑니다.

Base64 의 =

Base64 는 바이트 셋, 곧 24비트를 글자 넷으로 바꿉니다. 글자 하나가 6비트를 나릅니다. 데이터 끝에 24비트가 안 남으면 오른쪽에 0 비트를 더해 6비트 묶음을 채웁니다. 출력 끝은 = 로 채웁니다.

BASE64("f")   = "Zg=="
BASE64("fo")  = "Zm8="
BASE64("foo") = "Zm9v"

f 는 8비트 01100110 입니다. 앞 6비트가 첫 묶음이 됩니다. 남은 2비트 뒤에 0 비트 넷을 더해 둘째 묶음을 채웁니다.

block-beta
columns 4
  F["f · 01100110 · 8비트"]:4
  G1["011001"]:1 G2["10 + 채움 0000"]:1 G3["빈 묶음"]:1 G4["빈 묶음"]:1
  Z1["Z"]:1 Z2["g"]:1 E1["="]:1 E2["="]:1

묶음 둘이 Z 와 g 가 됩니다. 빈 묶음 둘 몫은 = 두 개가 채웁니다. 채움이 묶음 안의 0 비트와 출력 끝의 = 두 겹으로 붙는 셈입니다.

fo 는 16비트라 = 하나입니다. foo 는 24비트로 딱 맞아 채움이 없습니다.

전해지는 데이터의 크기를 미리 가정할 수 없는 일반적인 경우에는 바르게 되돌리려면 = 가 필요합니다. = 를 쓰지 않거나 요구하지 않는 쓰임새도 있습니다. 어느 쓰임새가 그런지는 자료에 없습니다(미확인).

ESP 패킷의 Padding 필드

ESP(Encapsulating Security Payload, 캡슐화 보안 페이로드)는 IP(Internet Protocol, 인터넷 프로토콜) 패킷의 내용을 암호화해 싣는 규격입니다. 한 패킷 안의 Padding 필드가 크기를 맞추는 일과 정렬을 맞추는 일을 함께 맡습니다.

암호 알고리즘이 평문을 몇 바이트의 배수로 요구하면 Padding 필드가 그 크기를 채웁니다. 블록 암호의 블록 크기가 그런 요구입니다. 알고리즘과 상관없이 채움이 필요할 수도 있습니다. 암호문 끝을 4바이트 경계에 맞출 때입니다.

뒤에 무결성 검사 값(ICV, Integrity Check Value)이 붙는다면 그 값이 4바이트 경계에서 시작하게 하려는 것입니다. ICV 는 패킷이 도중에 바뀌지 않았는지 확인하는 값입니다.

보내는 쪽은 채움을 0~255 바이트 붙일 수 있습니다. 알고리즘이 채움 내용을 따로 정하지 않으면 1, 2, 3 … 으로 하나씩 커지는 값을 씁니다. 이 기본 채움을 쓸 때 받는 쪽은 Padding 필드를 검사하기를 권합니다. 바로 뒤의 Pad Length 필드가 채움 바이트 수를 적습니다. 0 이면 채움이 없습니다.

알고리즘과 정렬에 필요한 것보다 더 채워 진짜 길이를 감추는 데 쓸 수도 있습니다. 다만 Padding 필드는 255 바이트가 한계라 그 목적에는 모자랍니다. 그래서 ESP 는 TFC(Traffic Flow Confidentiality, 트래픽 흐름 기밀성) 채움이라는 별도 장치를 둡니다. 길이를 감춰야 하면 Padding 필드 대신 이것을 쓰기를 권합니다.

TFC 채움은 싣고 가는 데이터 안에 IP 패킷 길이가 적혀 있을 때만 붙일 수 있습니다. 받는 쪽은 그 길이로 진짜 끝을 알고 채움을 버립니다.

JDK 의 필드 채움

JDK(Java Development Kit, 자바 개발 도구) 8 에는 거짓 공유를 줄이려는 제안 JEP(JDK Enhancement Proposal, JDK 개선 제안) 142 가 들어갔습니다. 이 제안은 경합이 심할 필드를 개발자가 지정하는 방법을 정합니다. 지정한 필드는 JVM(Java Virtual Machine, 자바 가상 머신)이 다른 필드나 다른 객체와 캐시 라인을 나눠 쓰지 않게 놓습니다.

두 코어가 쓰는 두 메모리 위치가 한 캐시 라인에 놓일 때가 있습니다. 그중 적어도 한쪽 코어가 쓰기를 하면 메모리 경합이 생깁니다. 이 경합이 상세 절에서 본 거짓 공유입니다. 경합이 심한 위치에서는 성능과 확장성에 심각한 문제가 될 수 있습니다.

이 제안이 노리는 것은 적어도 개발 중에 쉽게 짚어낼 수 있는 필드에서만이라도 그 경합을 피하는 것입니다. 어느 필드를 지정할지는 사람이 고릅니다.

JVM 은 지정한 필드 앞뒤에 채움을 넣습니다. 다른 필드나 다른 객체가 같은 캐시 라인에 못 오게 하려는 것입니다. 채움 크기는 객체 정렬이 보장되지 않는 일반적인 경우라면 그 기계의 캐시 라인 크기와 같아야 합니다. 이 채움은 클래스를 불러올 때 빈 필드를 넉넉히 끼워 넣는 식으로 비교적 쉽게 만들 수 있습니다.

block-beta
columns 8
  L1["캐시 라인 하나"]:8
  X1["필드 x"]:1 Y1["필드 y"]:1 R1["한 라인에 같이 놓였다"]:6
  L2["캐시 라인 1"]:4 L3["캐시 라인 2"]:4
  X2["필드 x"]:1 PD["패딩"]:3 Y2["필드 y"]:1 R2["다른 라인에 놓였다"]:3

위 두 줄이 채움을 넣기 전입니다. 아래 두 줄이 넣은 뒤입니다.

갈래

갈래를 가르는 축은 받는 쪽이 어디까지가 채움인지 어떻게 아느냐입니다. 채움 값과 끝을 찾는 법이 함께 정해집니다.

블록 크기가 8바이트일 때 마지막 블록에 데이터가 5바이트면 3바이트를 채워야 합니다. 방식마다 그 3바이트가 이렇게 다릅니다. 값은 16진수로 적은 바이트입니다. 80 은 비트로 적으면 1 뒤에 0 일곱 개입니다.

채움 값이 자기 길이를 말하는 방식

블록 크기가 k 바이트일 때 모자란 바이트 수를 n 이라 하면 값이 n 인 바이트를 n 개 붙입니다. 한 바이트 모자라면 01, 두 바이트면 02 02 입니다. 입력이 이미 블록 크기의 배수여도 채웁니다. 이때는 값이 k 인 바이트 k 개, 곧 블록 하나가 전부 채움입니다.

모든 입력에 채움이 붙습니다. 어느 채움도 다른 채움의 꼬리가 아닙니다. 그래서 받는 쪽은 맨 끝 바이트만 보고 걷어 낼 양을 압니다. 바이트 하나에 길이를 적으므로 k 가 256 보다 작을 때만 잘 정의됩니다.

block-beta
columns 8
  B1["블록 1 · 데이터로 꽉 찼다"]:8
  D1["블록 2 · 데이터 5바이트"]:5 P1["03 03 03"]:3
  B2["블록 1 · 데이터로 꽉 찼다"]:8
  D2["블록 2 · 데이터 8바이트로 꽉 찼다"]:8
  P2["블록 3 · 08 을 여덟 개 · 전부 채움"]:8

위 두 줄은 마지막 블록이 모자랄 때입니다. 아래 세 줄은 데이터가 블록에 딱 맞을 때입니다.

1 비트 뒤에 0 을 잇는 방식

데이터 끝에 비트 1 을 하나 붙입니다. 이어서 마지막 블록이 찰 때까지 0 비트를 붙입니다. 0 이 하나도 안 붙을 수도 있습니다. 받는 쪽은 뒤에서부터 0 을 걷어 내다가 처음 만난 1 까지 걷습니다.

이렇게 걷으려면 받는 쪽이 이 메시지에 채움이 있다는 것을 알아야 합니다. 이미 꽉 찬 메시지에도 블록 하나만큼 채움을 붙이면 됩니다. 아니면 메시지 길이 표시처럼 채움이 있는지 확실히 알 수단을 따로 둡니다.

SHA-1 과 SHA-2 계열 해시의 채움도 비트 1 뒤에 0 을 잇습니다. 그 뒤에 원래 메시지 길이를 더 붙입니다. 다만 해시에는 채움을 걷어 내는 받는 쪽이 없습니다. 채움이 든 블록까지 해시 계산에 들어갑니다.

채움 길이를 따로 적는 방식

채움 값과 별개로 채움 길이를 한 곳에 적어 두는 방식입니다. 받는 쪽은 그 길이만 읽고 그만큼 걷습니다. 채움 길이를 마지막 바이트에만 적고 앞은 0 으로 채우는 변형(00 00 03)이 있습니다. 나머지를 무작위 값으로 채우고 마지막 바이트만 길이로 두는 변형도 있습니다.

ESP 는 채움을 1, 2, 3 … 으로 하나씩 커지는 값으로 채웁니다. 채움 길이는 바로 뒤 Pad Length 필드에 따로 적습니다.

0 으로 채우고 끝 표지를 두는 방식

TLS 1.3 레코드는 내용 뒤에 내용 유형 한 바이트를 둡니다. 내용 유형은 레코드에 실린 것이 어떤 종류의 메시지인지 알리는 값이고 0 이 아닙니다. 채움은 그 뒤에 붙는 0 바이트입니다. 채움 바이트는 암호화하기 전에 반드시 전부 0 이어야 합니다.

block-beta
columns 6
  C["내용"]:3 T["내용 유형 · 0 아님"]:1 Z["00 00 · 채움"]:2
  S["받는 쪽은 끝에서 앞으로 훑다가 0 이 아닌 첫 바이트에서 멈춘다"]:6

받는 쪽은 복호한 뒤 끝에서부터 앞으로 훑어 0 이 아닌 첫 바이트를 찾습니다. 그 바이트가 내용 유형입니다. 이 방식은 새 내용 유형을 들이지 않고도 레코드 크기 한도 안에서 아무 길이로나 채울 수 있습니다. 채움이 전부 0 이어야 하므로 채움 오류를 빨리 잡아낼 수 있습니다.

무작위를 섞는 방식

RSA(Rivest–Shamir–Adleman, 만든 세 사람의 이름을 딴 공개 키 암호) 암호화의 채움은 메시지 앞에 붙습니다. 크기를 맞추는 것 말고도 무작위 바이트를 섞어 안전을 돕습니다. PKCS(Public-Key Cryptography Standards, 공개 키 암호 표준) #1 v1.5 방식은 메시지 앞에 00 02, 0 이 아닌 무작위 바이트열, 00 을 차례로 둡니다. 무작위 바이트열에는 0 이 없으므로 그 뒤 첫 00 이 채움의 끝입니다.

무작위 바이트열은 적어도 8 바이트입니다. 가능한 암호화 블록을 전부 시도해 데이터를 되찾는 일을 어렵게 하는 안전 조건입니다.

OAEP(Optimal Asymmetric Encryption Padding, 최적 비대칭 암호화 패딩)는 해시 값 lHash, 0 바이트열, 01 한 바이트, 메시지를 차례로 잇습니다. 0 바이트열 뒤의 01 이 채움의 끝입니다. 이 배치는 무작위 씨앗으로 만든 마스크에 덮여 나갑니다. 마스크는 원래 값을 가리려고 겹쳐 씌우는 값입니다.

block-beta
columns 6
  A["00"]:1 B["02"]:1 PS["무작위 · 0 아님 · 8바이트 이상"]:2 E["00 · 채움의 끝"]:1 M["메시지"]:1
  H["lHash"]:1 Z["00 … 00"]:2 O["01 · 채움의 끝"]:1 M2["메시지"]:2

윗줄이 v1.5 방식, 아랫줄이 마스크를 덮기 전의 OAEP 배치입니다.

실패

패딩은 받는 쪽이 채움을 걷다가 무엇이 틀렸는지 밖으로 흘릴 때 깨집니다. 채움 바이트에 남은 값이 밖으로 나갈 때도 깨집니다.

패딩 오라클

이 소절은 CBC 로 암호화한 메시지를 받는 쪽이 채움을 검사하는 경우를 봅니다. 받는 쪽은 복호한 뒤 채움이 규칙에 맞는지 확인합니다. 맞으면 걷어 냅니다. 맞지 않으면 그 메시지를 처리하지 않습니다.

받는 쪽은 대개 확인 응답이나 오류 메시지를 돌려줍니다. 오류를 따로 알리지 않아도 처리하지 않았다는 사실이 채움이 맞았는지 한 비트를 흘립니다. 이 한 비트를 대답해 주는 상대를 오라클이라고 부릅니다. 이 대답으로 원문을 알아내는 것이 패딩 오라클 공격입니다.

XOR(eXclusive OR, 배타적 논리합)은 두 비트가 같으면 0, 다르면 1 을 내는 연산입니다. CBC 는 복호할 때 이번 암호문 블록을 블록 복호한 값에 앞 암호문 블록을 XOR 해 평문을 얻습니다.

flowchart TD
    C2["이번 암호문 블록"] --> D["블록 복호"]
    D --> X["XOR"]
    C1["앞 암호문 블록"] --> X
    X --> P["복호된 평문 블록"]
    P --> K["채움 검사"]

그래서 앞 암호문 블록의 한 바이트를 바꾸면 복호된 평문 블록의 같은 위치 바이트가 그만큼 바뀝니다. 공격자는 앞 블록의 끝 바이트를 바꿔 가며 서버에 보냅니다. 정상이라는 대답이 나오면 평문 끝 바이트가 채움 규칙에 맞는 값, 이를테면 01 이 된 것입니다.

공격자는 그 값과 자기가 바꿔 넣은 바이트를 압니다. 둘을 XOR 하면 블록 복호한 값의 끝 바이트가 나옵니다. 이것을 원래의 앞 암호문 바이트와 XOR 하면 원문 끝 바이트가 됩니다.

sequenceDiagram
    participant 공격자
    participant 서버
    loop 끝 바이트 하나를 확정할 때까지
        공격자->>서버: 끝 바이트를 바꾼 암호문
        서버-->>공격자: 채움 오류 또는 정상
    end
    Note over 공격자: 정상이 나온 값으로 원문 한 바이트를 셈한다

바이트 값은 256 가지라 평균 128 번쯤 바꿔 보면 끝 바이트가 나옵니다. 채움 값을 다르게 정해도 비슷한 공격이 성립합니다. 채움 길이를 마지막 바이트에만 적고 앞을 0 으로 채운 방식, ESP 의 01 02 03 …, 1 비트 뒤 0 이 모두 그렇습니다. 마지막 바이트만 길이로 두고 나머지를 무작위로 채워도 블록마다 마지막 바이트는 여전히 풀립니다.

Lucky Thirteen 과 POODLE

TLS 1.2 까지의 판은 메시지 인증 코드를 먼저 붙이고 암호화하는 설계입니다. 메시지 인증 코드는 메시지가 도중에 바뀌지 않았는지 확인하는 값입니다. 이 설계에서 받는 쪽은 복호해 채움을 걷어 낸 뒤에야 인증 코드를 검사합니다. 그 결과로 패딩 오라클이 생깁니다.

Lucky Thirteen 은 공격자가 만든 암호문에 오류 메시지가 돌아오는 시각의 작은 차이를 재서 원문을 되찾습니다. 특정 구현의 버그가 아니라 TLS 규격의 결함에서 나옵니다. TLS 에서 함께 쓰는 암호 알고리즘 조합을 암호 묶음이라고 부릅니다. CBC 를 쓰는 TLS 암호 묶음은 전부 이 공격에 당할 가능성이 있습니다.

인증 암호를 쓰거나 암호화한 뒤에 인증 코드를 붙이면 완화할 수 있습니다. 암호화한 뒤에 붙이면 받는 쪽이 복호하기 전에 인증 코드부터 검사합니다.

POODLE 은 SSL 3.0 을 노립니다. SSL 3.0 의 CBC 채움은 1 바이트에서 블록 크기까지 붙습니다. 채움 값은 정해져 있지 않습니다. 블록 하나가 전부 채움일 때가 가장 노리기 쉽습니다.

이때 마지막 바이트만 길이 값입니다. 앞 바이트는 아무 값입니다. 채움을 인증 코드가 덮지 않아서 복호할 때 채움이 온전한지 끝까지 확인할 수 없습니다.

노리는 값은 요청에 실려 가는 쿠키입니다. 쿠키는 웹 서버가 브라우저에 맡겨 두고 요청마다 돌려받는 값입니다.

공격자는 쿠키가 든 암호문 블록을 레코드의 마지막 블록, 곧 전부 채움인 블록 자리에 옮겨 넣습니다. 서버는 이렇게 바꾼 레코드를 대개 거부합니다. 평균 256 번에 한 번은 받아들입니다. 그때마다 쿠키의 모르는 바이트 하나가 드러납니다.

이 공격에는 알려진 완화책이 없습니다.

구조체의 채움 바이트

C 에서는 구조체 필드를 초기화해도 채움 바이트까지 초기화된다는 보장이 없습니다. 운영체제 커널이 구조체를 사용자 공간으로 복사하는 아래 코드가 그런 경우입니다.

struct test { int a; char b; int c; };
struct test arg = {.a = 1, .b = 2, .c = 3};
copy_to_user(usr_buf, &arg, sizeof(arg));

예시 절의 x86-64 System V 규칙으로 세면 b 뒤에 채움 3바이트가 낍니다. 이 채움 바이트에 민감한 정보가 남아 있을 수 있습니다. 구조체를 복사하면 그 정보가 사용자 공간으로 샐 수 있습니다.

같은 까닭으로 구조체를 memcmp 로 바이트째 비교하면 틀린 결과가 나올 수 있습니다. 채움 바이트의 값이 정해져 있지 않아 같은 필드 값을 담은 두 구조체가 다르다고 나올 수 있습니다. static 이나 스레드 지역 객체가 암묵적으로 초기화될 때만은 채움 비트가 0 으로 채워집니다.

관련 항목

패딩이 크기를 맞춰 주는 데이터 단위

바이트 · 워드 · 블록 · 캐시 라인 · 레코드 · 페이지 · 비트

메모리에서 값의 주소를 정하는 규칙

정렬 · 오프셋 · 구조체 · 필드 · 메모리 레이아웃 · 엔디언 · 워드 크기 · ABI

마지막 블록을 채워야 도는 암호 알고리즘

블록 암호 · AES · CBC · ECB · 해시 함수 · SHA-256 · 머클-담고르 구조 · RSA · OAEP · 인증 암호 · AEAD

패딩을 잘못 다뤄 터지는 공격

패딩 오라클 공격 · Lucky Thirteen · POODLE · 사이드 채널 공격 · 타이밍 공격 · 트래픽 분석 · 상수 시간 비교

패딩을 실제로 실어 나르는 프로토콜과 포맷

TLS · IPsec · ESP · Base64 · 직렬화 · 고정 길이 레코드 · 비트 필드

패딩이 더 쓰게 만드는 자원

메모리 · 대역폭 · 처리량 · 메모리 단편화 · 압축

캐시 경합을 피하려고 값을 떼어 놓는 기법

거짓 공유 · 캐시 정렬 · 코어 · 구조체 재배치 · 메모리 경합