Padding Oracle Attack

개요

Padding Oracle은 복호화 시스템에 암호문을 넣었을 때 복호화 된 문자열에 대한 Padding의 올바름 유무를 검사하는 암호 시스템이라고 볼 수 있습니다.

 

Padding Oracle Attack은 Padding의 올바름 유무를 검사하는 과정을 악용하여 Intermediate Value(IV^Plain Text or Cipher Text[n]^Plain Text)를 획득하고 Cipher Text^termediate을 통해 평문을 알아내는 공격을 의미합니다.

---

Block 암호 방식에서 사용되는 Padding이란?

먼저 해당 공격은 DES, 3DES, AES_CBC 모드와 같은 블록 암호화 기법에서 발견되며(확실치 않음), 각 블록은 일정한 크기를 가지고 있습니다.

 

즉, 블록의 크기가 8Byte의 경우 모든 암호문이 8Byte 배수의 길이를 가지고 있으며, 16Byte의 경우 16Byte 배수의 길이를 가지고 있습니다.

평문	암호문 (Block Size 16Byte)
123456790	\x0f\x03\x07\x1c\x07\xec\x93\xd6\xb5V6[vb\xd2\xb9 (16Byte)
12345678901234567	k\xc7\x96]\xc0g\xc7\xac\xed\\\xe8\x10x\x1a\xd8G\xe1\x1bV\x13\xecJh^\x1c\xc8%y`\x1b\xc3\x05 (32Byte)

 

표에 들어있는 평문은 모두 10과 17의 길이를 가지고 있는 반면, 암호문은 16 배수의 길이를 가지고 있습니다. 이때 사용되는 것이 Padding이며, 여러 Padding 중 pkcs#7을 기준으로 설명을 하겠습니다.

 

pkcs#7는 패딩 데이터에 패딩의 길이를 입력하는 방식입니다. "1234567890"의 경우 아래와 같은 구조로 16Byte의 블록이 구성됩니다.

"1234567890"의 Padding 구조

 

16길이가 넘는 "12345678901234567"의 경우 아래와 같은 구조로 32Byte의 블록이 구성됩니다.

"12345678901234567"의 Padding 구조

 

여기서 주의해야할 점이 있습니다. 16Byte 길이의 평문은 과연 몇 Byte 길이로 암호화 될까요?

 

만약, 아래와 같이 "TEST1234567890!"에 Padding이 추가되었을 때 "TEST1234567890!\x01"과 Padding된 데이터를 구분할 수 있을까요?

Padding이 포함된 ""TEST1234567890!"와 "TEST1234567890!\01" 비교

 

당연히 두 데이터를 구분할 수 없기 때문에 16Byte의 Padding이 추가되어 32Byte의 Padding된 데이터가 나오게 됩니다.

16Byte의 Padding이 추가된 "TEST1234567890!\01"

---

XOR 연산

당연히 이 글을 읽으시는 분들께서는 XOR 연산을 알고 있으리라 생각합니다. XOR 연산이 갖고 있는 성질은 아래와 같습니다.

- A ⊕ A = 0
- A ⊕ 0 = A
- A ⊕ B = B ⊕ A
- (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
- ∴ A ⊕ B ⊕ B = A ⊕ (B ⊕ B) = A ⊕ 0 = A

 

XOR 연산에 대해서 모르시거나 최소 위에서부터 3개의 연산이 이해가 안되시는 분들은 관련 공부를 먼저 진행하시고 참고하시기를 권고드립니다.

---

CBC(Cipher Block Chaining) 모드

블록 암호 방식은 데이터를 일정 블록으로 나눠 암호화 시키는 방식인데, 이렇게만 진행하면 동일한 키를 가지고 데이터를 암호화할 경우 항상 동일한 암호문을 갖게 됩니다.

 

이런 불상사를 막기 위해 사용되는 것이 CBC 모드인데, 암호화에 사용되는 Key를 제외하고도 IV라는 초기 벡터 값을 가지고 있으며, 해당 값은 첫 블록을 암호화할 때 Key와 함께 사용됩니다. 이후, 2번째 평문 블록은 암호화된 첫 블록을 이용하여 암호화되며, 그렇게 생성된 다음 암호 블록은 다음 평문 블록을 암호화할 때 사용됩니다.
(IV는 첫 암호화에만 사용되며, 이후에는 생성된 암호 블록을 이용하여 다음 평문 블록을 암호화한다고 정리할 수 있음)

 

그림을 통해 CBC 모드의 암호화 과정을 더 자세히 확인해보면, Plaintext를 IV와 XOR로 연산한 뒤 암호화를 통해 Ciphertext를 생성하며, 생성된 Ciphertext는 다음 블록의 Plaintext와 XOR로 연산하는 데 사용되는 것을 확인할 수 있습니다.

암호화 과정

 

복호화 과정에서는 IV와 Ciphertext를 이용하여 복호화된 데이터를 XOR로 연산하여 Plaintext를 확인하는 것을 볼 수 있습니다.

복호화 과정

---

Padding Oracle Attack

자 이제 본격적으로 Padding Oracle Attack에 대해서 알아보도록 하겠습니다. 앞서 설명드렸지만, 해당 공격은 Padding의 올바름 유무를 검사하는 과정을 악용하여 평문의 데이터를 확인하는 공격입니다.

 

해당 공격을 공부하면서 찾아보게 된 많은 자료들이 서버에 IV와 함께 암호화된 데이터를 보내는 것을 기준으로 작성되었는데 IV는 Key와 함께 암호화되는 데이터를 결정하는 중요한 값으로써 보통 서버 내부에 보관하는 것이 일반적이기 때문에 그런 부분들을 꼭 인지하셨으면 좋겠습니다.

(블로그와 자료를 통해 관련 지식들을 전수해주신 부분은 너무나도 감사한 일이며, 그런 분들이 없었다면 관련 공부조차 시작하지 못했을 거라고 생각합니다.)

 

해당 취약점이 발생하기 위해서는 전제 조건은 아래와 같습니다.

1. 3DES, CBC 모드 등 일부 블록 암호 방식을 이용하여 암호화가 진행되어야 함
2. 서버의 응답 값을 통해 Padding이 올바르지 않을 경우와 Padding은 정상적이지만 복호화가 잘못되었을 경우로 구분할 수 있어야 함

즉, CBC와 3DES와 같은 암호 방식을 사용하면서 서버의 응답 값을 통해 Padding의 올바름 여부를 판단할 수 있어야만 발생하는 취약점입니다.

 

서버의 응답 값을 통해 Padding의 올바름 여부를 판단할 수 있다고 가정하고 어떻게 Ciphertext를 통해 Plaintext를 알아낼 수 있을까요?

 

먼저, 아래의 표와 같이 SECRETDATA!!!!!!hacksms.tistory.com를 암호화했다고 가정해보겠습니다. 먼저 첫 번째 블록은 Padding 없이 IV와 XOR 연산 후 암호화가 진행됩니다.

Plaintext 및 IV를 통한 Ciphertext 생성

 

두 번째 블록의 평문 역시 Padding 없이 첫 번째 블록의 암호문과 XOR 연산 후, 암호화가 진행됩니다.

첫 번째 블록의 암호문을 이용한 두 번째 평문 암호화

 

세 번째 블록의 평문은 Padding을 추가하여 두 번째 블록의 암호문과 XOR 연산 후, 암호화가 진행됩니다.

(첫 번째 블록을 제외한 나머지 블록들은 이전 블록의 암호문을 이용하여 평문을 XOR 연산하는데, 이 과정이 매우 중요한 부분입니다.)

두 번째 블록의 암호문을 이용한 세 번째 평문 암호화

 

지금까지 그림을 통해 AES CBC 모드의 암호화 과정을 간단하게 설명드렸습니다. 이제 복호화 과정을 통해 암호화된 데이터를 가지고 평문의 데이터를 획득할 것인데요. IV도 Key도 모르는 상황에서 어떻게 평문의 데이터를 획득할 수 있을까요?

 

맨 처음에 Padding Oracle을 복호화된 문자열에서 Padding의 올바름 유무를 확인하는 과정이라고 말씀드렸습니다. CBC 모드의 복호화 과정은 암호문을 복호화할 경우 나오게 되는 Plaintext ⊕ Ciphertext 값을 이전 블록의 Ciphertext와 XOR 연산하여 평문의 데이터를 획득하도록 동작합니다.

세 번째 블록의 복호화 과정

 

세 번째 블록은 마지막 블록이기 때문에 반드시 Padding이 포함된 문자열일 수 밖에 없습니다. 즉, 암호 시스템은 마지막 블록의 암호문을 복호화한 뒤, 이전 블록의 Ciphertext와 XOR 연산 후 Padding을 검사할 수 밖에 없다는 뜻입니다.

(이해가 안되신다면 맨 위의 "Block 암호 방식에서 사용되는 Padding이란?" 부분을 다시 읽고 오세요.)

 

공격을 수행하려면 사용자가 조작할 수 있는 데이터가 당연히 필요하겠죠? 세 번째 블록의 복호화 과정에서는 사용자가 조작할 수 있는 데이터가 있는데 그것은 바로 두 번째 블록의 암호문입니다. 두 번째 블록의 암호문의 마지막 Byte를 수정해서 서버에 전송하면 어떤 일이 발생할까요?

 

두 번째 블록의 암호문은 복호화 된 세 번째 블록의 데이터와 XOR 연산을 하기 때문에 마지막 Byte의 값이 달라지게 됩니다. 세 번째 블록의 마지막 데이터는 반드시 Padding 데이터일 수 밖에 없기 때문에 Padding이 올바르지 않다는 에러가 발생하게 됩니다.
(16Byte의 블록에서 Padding이 가질 수 있는 최대 값은 0x10인데 0xFD가 있다는 것은 Padding이 올바르지 않다는 뜻 이겠죠?)

두 번째 블록의 암호문을 조작했을 경우

 

Padding 데이터가 올바르게 나오기 위해서는 마지막 Byte가 0x01이어야 하는데, Plaintext ⊕ Ciphertext를 모르기 때문에 어떤 값을 넣어야 XOR 값이 0x01이 나올 지 알 수 없습니다. 만약, 0x00~0xFF까지 Brute Force를 한다면 어떤 값을 넣었을 때 0x01이 나오게 됩니다. Plaintext의 마지막 Byte가 0x01이 나오는 순간 Padding이 올바르다고 암호 시스템은 판단할 것이고 실제 복호화 된 결과는 다르기 때문에 서버의 응답 값을 통해 0x01이 나오는 마지막 Byte를 구할 수 있을 겁니다.

 

Brute Force를 통해 두 번째 블록의 마지막 Byte가 0xFC일 때 Padding이 올바르다는 응답을 받았습니다. 이후, 0xFC에 0X01을 XOR하면 Plaintext ⊕ Ciphertext 값을 구할 수 있습니다.

(이해가 안되신다면 XOR을 다시 공부하세요.)

Padding의 올바름 유무를 통한 Plaintext ⊕ Ciphertext 16번째 데이터 확인

 

이번에는 15번째 Byte의 Plaintext ⊕ Ciphertext 값을 구해보겠습니다. 여기서 주의해야 할 점은 15번째 Byte까지 Padding이 되었다고 시스템이 판단해야 하기 때문에 Plaintext ⊕ Ciphertext의 마지막 Byte를 0x02로 XOR 한 값을 마지막 Byte에 입력해줘야 합니다.

 

이후, Brute Force를 통해 15번째 Byte가 0x4F일 때 Padding이 올바르다는 응답을 받았습니다. 다시 0x4F에 0x02를 XOR하면 Plaintext ⊕ Ciphertext의 15번째 Byte 값을 구할 수 있습니다.

Padding의 올바름 유무를 통한 Plaintext ⊕ Ciphertext 15번째 데이터 확인

 

동일한 방식으로 모든 Plaintext ⊕ Ciphertext 값을 구할 수 있습니다.

Padding의 올바름 유무를 통한 Plaintext ⊕ Ciphertext 데이터 확인

 

이렇게 구한 Plaintext ⊕ Ciphertext를 이전 블록의 Ciphertext와 XOR하면 Plaintext를 구할 수 있습니다. 왜냐고 물어보신다면 복호화 이후의 과정을 참고하시라고 말씀드리고 싶네요.

XOR 연산을 통한 평문 획득

 

지금까지 두 번재 블록의 암호문 조작을 통해 세 번째 블록의 평문 데이터를 획득할 수 있었습니다. 이와 같은 방식으로 두 번째 블록의 평문 데이터도 획득할 수 있는데요. 여기에는 주의해야할 점이 한 가지 있습니다.

 

그것은 바로 세 번째 블록의 암호문을 제거한 암호문을 조작하여 서버에 전송해야한다는 점입니다. 마지막 블록의 데이터에만 Padding이 포함되기 때문에 두 번째 블록의 평문을 획득하기 위해서는 두 번째 블록이 마지막 블록이 되어야합니다.

 

두 번째 블록이 마지막 블록이 되도록 만든 후, 동일한 공격을 수행하면 아래와 같이 두 번째 블록의 평문 데이터를 확인할 수 있습니다.

Padding의 올바름 유무를 통한 Plaintext ⊕ Ciphertext 데이터 확인

 

XOR 연산을 통한 평문 획득

 

평문 데이터인 SECRETDATA!!!!!!hacksms.tistory.com 중에서 SECRETDATA!!!!!!를 제외한 모든 암호문을 복호화할 수 있었습니다. SECRETDATA!!!!!!를 볼 수 있는 방법은 없을까요? 

 

복호화 과정을 다시 살펴보면 알 수 있듯이 IV 값을 조작할 수 있다면, 첫 번째 블록 역시 IV와 Key 값을 모르는 상태에서도 평문의 데이터를 획득할 수 있을 것 같습니다.

(사실 그래서 많은 자료들에서 IV를 조작할 수 있다고 가정하고 내용을 쓴 것입니다.)

복호화 과정

 

앞서 IV는 서버 내부에 저장되는 것이 보통이기 때문에 일반적인 사용자가 확인하거나 조작할수 없다고 말씀드렸습니다. 만약, 조작할 수 있다면 동일한 공격 방식을 IV에 적용하여 평문의 데이터를 알아낼 수 있다고 생각하시면 됩니다.

 

Padding Oracle Attack에 대해서 이해가 되셨다면, 좋은 문제가 있으니 풀어보시기를 권고드립니다.

Padding Oracle