Padding Oracle Attack

Padding Oracle Attack

 

CBC 모드 암호화에서 padding 오류 메시지의 "다른 반응"을 이용해 복호화 키를 몰라도 평문을 역추론하는 공격이다.

 

CBC 복호화

$C_0 = IV$

$P_i = D_k(C_i) \oplus C_{i-1}$

 

XOR 연산 때문에 이전 블록을 조작하면 평문 결과도 달라지게 된다.

공격자가 이전 블록을 조작하면 복호화된 패딩 결과가 어떻게 달라지는지 서버가 알려준다.

 

 

$C_1, C_2$라는 블록을 CBC 모드에서 복호화하면 다음 두 블록을 얻을 수 있다.

$D_K(C_1) \oplus IV, D_K(C_2) \oplus C_1$

 

대부분의 Padding 알고리즘에서 Padding과 관련 있는 블록은 마지막 블록뿐이다.

즉, 공격자는 $ D_K(C_2) \oplus C_1$에만 신경 쓰면 된다.

 

 

Padding oracle attack은 복호화 과정에 블록 복호화를 진행한 후 패딩을 제거하는 기능이 포함되어있을 때,

패딩의 형식이 일치하는지의 여부를 통해 복호화 후의 블록 정보를 알아내는 공격이다.

 

PKCS#7 패딩을 사용해서 자세히 알아보자.

 

임의로 블록 사이즈를 8바이트라고 가정하면, 마지막 8바이트 블록의 올바른 패딩의 가능성은 8가지뿐이다.

|???? ???? ???? ??01|
|???? ???? ???? 0202|
|???? ???? ??03 0303|
|???? ???? 0404 0404|
|???? ??05 0505 0505|
|???? 0606 0606 0606|
|??07 0707 0707 0707|
|0808 0808 0808 0808|

 

따라서, 위 8가지 형식 중 단 하나의 형식과도 일치하지 않는다면 Unpad 에러를 낸다.

이 에러 여부를 통해서 $D_K(C_2)$의 모든 바이트를 알아낼 수 있다.

 

 

< 평문을 알아내는 과정>

 

우리가 알아내고 싶은 블록을 $C_i$라고 하고, 앞 블록을 $C_{i-1}$라고 하자.

 

복호화 과정 : $P_i = D_K(C_i) \oplus C_{i-1}$

 

평문을 알아내기 위해서 $C_{i-1}$을 조작한 값인 $C'_{i-1}$로 바꿔서 서버로 보낸다.

그러면 서버는 조작된 값으로 평문을 계산한다.

 

$P'_i = D_K(C_i) \oplus C'_{i-1}$

 

 

1. 마지막 바이트 알아내기

서버가 계산하는 $P'_i$의 마지막 바이트가 0x01이 되도록 $C'_{i-1}$를 조작한다.

 

마지막 바이트가 0x01이면 패딩 길이가 1이므로

서버가 유효한 패딩이라고 인식하게되어 패딩 OK 신호를 주게된다.

 

$P'_i[7] = D_K(C_i)[7] \oplus C'_{i-1}[7]$

 

우리는 $P'_i[7]$를 0x01로 만들고 싶은 것이니,

 

$P'_i[7] = 0x01= D_K(C_i)[7] \oplus C'_{i-1}[7]$

$D_K(C_i)[7] = 0x01 \oplus C'_{i-1}[7]$

 

 

[ 공격자가 하는 일 ]

1. $C_{i-1}[0..6]$ (앞 바이트)는 아무 값이나 설정 (보통 원래 값 유지)

2. $C'_{i-1}[7]$를 0~255까지 바꿔가면서 서버에 전송

3. 서버가 패딩 OK를 반환하면 그때의 $C'_{i-1}[7]$를 기록한다.

4. $D_K(C_i)[7] = 0x01 \oplus C'_{i-1}[7]$을 계산해 $D_K(C_i)$의 마지막 바이트를 계산한다.

 

 

 

2. 끝에서 두 번째 바이트 알아내기

 

이번에는 마지막 2바이트가 0x02 0x02가 되도록 $C'_{i-1}$을 조작한다.

 

$P'_i[7] = D_K(C_i)[7] \oplus C'_{i-1}[7] = 0x02$

$P'_i[6] = D_K(C_i)[6] \oplus C'_{i-1}[6] = 0x02$

 

우리는 이미 $D_K(C_i)[7]$ 값을 알고 있기 때문에

따라서 마지막 바이트를 $C'_{i-1}[7] = D_K(C_i)[7] \oplus 0x02$로 마지막 바이트를 고정하고,

앞서와 같은 방식으로 $C'_{i-1}[6]$만 0~255 범위로 시도해서

패딩 OK가 나오는 경우를 찾는다.

 

패딩 OK가 나오면  $D_K(C_i)[6] = 0x02 \oplus C'_{i-1}[6]$을 계산에 마지막에서 두 번째 바이트를 얻는다.

 

 

이와 같은 과정을 반복해 $D_K(C_i)$의 모든 바이트를 알아낸다.

 

 

<예시>

이해를 더 쉽게 하기 위해서 예시로 확인해보자.

 

먼저, $C_1$을 NULL바이트 7개와 마지막에 0~255의 존재하는 모든 바이트를 이어붙인

256가지의 경우의 수에 대해 패딩 성공 여부를 확인한다.

이 중에서 패딩 오류가 나지 않은 $C_1$의 마지막 바이트를 통해서 $D_K(C_2)의 마지막 바이트를 계산할 수 있다.

 

$D_K(C_2)$의 값이 b"AmoNando" = [65, 109, 111, 78, 97, 110, 100, 111]이라고 가정하자.

 

 

$C_1$이 [0,0,0,0,0,0,0,110]일 때, $D_K(C_2) \oplus C_1$의 마지막 바이트가 0x01임을 알 수 있다.

 

$D_K(C_1)$의 마지막 바이트 = 0x01 $\oplus$ $C_1$의 마지막 바이트

 

따라서 $D_K(C_1)$의 마지막 바이트는 110 $\oplus$ 1 = 111임을 알 수 있다.

 

 

$D_K(C_2)$의 마지막에서 두 번째 바이트를 구하기 위해서는

마지막 두 바이트가 0202와 일치하는 $D_K(C_2) \oplus C_1$를 찾아야한다.

 

마지막 바이트의 값이 111임을 이미 알고 있기 때문에 $C_1$의 마지막 바이트를 111 $\oplus$ 2 = 109로 설정하면

$D_K(C_2) \oplus C_1$의 마지막 바이트가 02가 된다.

따라서 마지막에서 두 번째 바이트만 앞에서와 동일하게 256가지 시도를 통해 02가 되는 경우를 찾는다.

 

 

$C_1$이 [0,0,0,0,0,0,102,109]일 때, $D_K(C_2) \oplus C_1$의 마지막 두 바이트가 02 02임을 알 수 있다.

이렇게 $D_K(C_2)$의 마지막에서 두 번째 바이트가 102 $\oplus$  2 = 100임을 알 수 있다.

 

이와 같은 과정을 반복해  $D_K(C_2)$의 모든 바이트를 복구한다.

 

 

[ 예외처리 ]

$D_K(C_2)$가 [10, 20, 30, 40, 50, 3, 3, 10]이라고 가정하고 Padding oracle attack을 해보면

 

마지막 바이트가 0x01인 것을 찾는 과정이었는데 마지막 3바이트가 3 3 3이 되면서 패딩 성공해서

두 가지의 경우가 성공하게 되었다.

 

이렇게 두 가지 경우가 성공할 경우가 높지는 않지만, 예외 상황을 완벽하게 방지하기 위해서는

마지막에서 두 번째 바이트를 다른 값으로 바꿔서 시도해보면 된다.