c12.go

package main

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

// decryptOracleSecret implements a byte-at-a-time decryption attack, aka
// padding oracle attack.
// It decrypts a secret by iteratively guessing each byte of the plain text.
// It first crafts plain texts, then asks the oracle to encrypt them, and
// finally compares the resulting cipher text blocks to the target cipher text.
// This sort of input manipulation allows it to deduce each byte of the secret
// one at a time, thus reconstructing it without needing the encryption key.
// This method exploits the deterministic nature of block ciphers and the
// feedback from the oracle to reveal the hidden data.
// See file example_byte_at_a_time.txt for a visual example of this method.
// Challenge 12 of set 2.
func decryptOracleSecret(encryptionOracle aesOracle) ([]byte, error) {

	var (
		blockSize   = aes.BlockSize
		shortBlocks = make([][]byte, blockSize)
	)
	// craft blocks of known bytes shorter than a full AES block.
	// These will push the unknown byte(s) of the secret into a predictable
	// position within the ciphertext block.
	// For example, if the block is of length 15 (blockSize - 1), the
	// encrypted output will have the first 15 bytes as 'A' and the 16th byte
	// will be the first byte of the secret. With length 14, the encrypted
	// output will have the first 15 bytes as 'A' and the 15th and 16th will be
	// the first 2 bytes of the secret.
	for size := 0; size < blockSize; size++ {
		block := make([]byte, size)
		for i := range block {
			block[i] = 'A'
		}
		shortBlocks[size] = block
	}

	// this will return a cipher text where only the secret has been encrypted
	// (shortBlocks[0] stores an empty block, therefore the oracle will
	// encrypt [{}||secret]).
	// We do this to know the number of blocks we have to decrypt.
	encryptedSecret, err := encryptionOracle(shortBlocks[0])
	if err != nil {
		return nil, err
	}

	var (
		nBlocks = len(encryptedSecret) / blockSize
		secret  = make([]byte, 0, len(encryptedSecret))
	)
	for blockIdx := range nBlocks {
		for size := blockSize - 1; size >= 0; size-- {
			knownBytes := shortBlocks[size]

			// these could be cached, as the encryption of a given short block
			// is always the same cipher text.
			cipherText, err := encryptionOracle(knownBytes)
			if err != nil {
				return secret, err
			}

			var (
				// boundaries of the cipher text block being targeted for
				// decryption.
				start = blockIdx * blockSize
				end   = blockIdx*blockSize + blockSize

				// the cipher text block being targeted for decryption.
				targetBlock = cipherText[start:end]

				// a combination of known bytes, previously
				// decrypted bytes of the secret, and the byte currently being
				// guessed (the +1, which we will brute force in the loop
				// below).
				forged = make([]byte, len(knownBytes)+len(secret)+1)
			)
			copy(forged, knownBytes)
			copy(forged[len(knownBytes):], secret)

			// the "byte-at-a-time" part of the attack.
			// This loop is responsible for guessing the value of the unknown
			// byte of the secret by iterating through all possible byte values
			// (0 to 255) and checking which one produces a ciphertext block
			// that matches the target block.
			// Basically, what we are doing is asking the oracle to encrypt all
			// the possible byte sequences obtained by changing their last byte.
			// For example:
			// oracle("AAAAAAAAAAAAAAAA")
			// oracle("AAAAAAAAAAAAAAAB")
			// oracle("AAAAAAAAAAAAAAAC")
			// oracle("AAAAAAAAAAAAAAAD")
			// .....
			// until the resulting cipher text matches the target block.
			// If the cipher text generated by oracle("AAAAAAAAAAAAAAAD")
			// matches, then 'D' is a byte of the secret.
			// On the next round we will try all possible byte sequences like
			// this:
			// oracle("AAAAAAAAAAAAAADA")
			// oracle("AAAAAAAAAAAAAADB")
			// oracle("AAAAAAAAAAAAAADC")
			// oracle("AAAAAAAAAAAAAADD")
			// .....
			// until the resulting cipher text matches the target block.
			// If the cipher text generated by oracle("AAAAAAAAAAAAAADA")
			// matches, then 'A' is the next byte of the secret.
			// And so on until we decrypted the entire secret.
			for i := range 255 {
				char := byte(i)

				forged[len(forged)-1] = char

				sampleCipherText, err := encryptionOracle(forged)
				if err != nil {
					const formatStr = "trying byte %d (%c): %s"
					return secret, fmt.Errorf(formatStr, i, char, err)
				}

				if bytes.Equal(sampleCipherText[start:end], targetBlock) {
					secret = append(secret, char)
					break
				}
			}
		}
	}

	return secret, nil
}

// ecbEncryptionOracle returns an aesOracle that appends the secret to the
// plain text before encrypting it with the same (randomly generated) key.
func ecbEncryptionOracle(secret []byte) (aesOracle, error) {
	key, err := randomBytes(aes.BlockSize, aes.BlockSize)
	if err != nil {
		return nil, fmt.Errorf("generating random AES key: %s", err)
	}

	encOracle := func(plainText []byte) ([]byte, error) {
		padded := make([]byte, len(plainText)+len(secret))
		copy(padded, plainText)
		copy(padded[len(plainText):], secret)

		return encryptAesEcb(padded, key)
	}

	return encOracle, nil
}