GoでPadding Oracle Attackしたい！

「 [Applibot Advent Calendar 2021](https://qiita.com/advent-calendar/2021/applibot) 」 22日目の記事になります。
前日は @ref3000 さんの [Unity でサクッと機械学習を体験してみよう【ML-Agents】](https://qiita.com/ref3000/items/40a0915fbc4478b5cadb)という記事でした。

## はじめに
業務で暗号化に興味を持ってパディングオラクル攻撃という名前に惹かれたので今回はGo言語でパディングオラクル攻撃をやっていきます。

## AES CBCモードについて
今回のパディングオラクル攻撃をする対象の暗号文はAESのCBCモードを使用して暗号化しました。AESは平文をブロック長ごとに暗号化するブロック暗号で、ブロック長が128bit、鍵長が128/192/256bitの3種類です。

CBCモードは一つ前の暗号文ブロックと平文ブロックをXORとってから暗号化する方法で前のブロックに依存するため同じ平文であっても異なる暗号文になるため推測されにくいという特徴があります。
先頭の平文ブロックの前には暗号文ブロックがないので初期化ベクトルを用いてXORとり暗号化します。

![cbc.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/893255/2d584db0-2f69-df99-2850-aa4786985828.png)


AESはブロック長が128bit(16Byte)のブロック暗号なので平文も16Byteの整数倍でないといけません、そのため足りない分を埋めるためにPKCS#7パディングという方式がよく使われます。
PKCS#7はパディング長を値として使います。パディング長が1Byteの場合は01、2Byteの場合は02 02というようになります。

![pkcs7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/893255/b7872320-c1de-bf4f-285b-f01005a3b21c.png)


### Go言語によるCBCモード暗号化

```go
package main

import (
	"bytes"
	"crypto/aes"
	"crypto/cipher"
	"crypto/rand"
	"encoding/base64"
	"fmt"
	"log"

	"golang.org/x/crypto/scrypt"
)

// pad PKCS#7パディング
func pad(data []byte) []byte {
	padSize := aes.BlockSize - (len(data) % aes.BlockSize)
	return append(data, bytes.Repeat([]byte{byte(padSize)}, padSize)...)
}

func main() {
	// 鍵を生成
	key, err := scrypt.Key([]byte("password"), []byte("salt"), 32768, 8, 1, 32)
	if err != nil {
		log.Fatal(err)
	}
	// パディング済み平文
	plainText := pad([]byte("平文"))
	cipherText := make([]byte, aes.BlockSize+len(plainText))
	// 先頭16Byteは初期化ベクトルに使う
	iv := cipherText[:aes.BlockSize]
	// 初期化ベクトルを乱数で初期化
	if _, err = rand.Read(iv); err != nil {
		log.Fatal(err)
	}
	block, err := aes.NewCipher(key)
	if err != nil {
		log.Fatal(err)
	}
	mode := cipher.NewCBCEncrypter(block, iv)
	mode.CryptBlocks(cipherText[aes.BlockSize:], plainText)
	// 暗号文をBase64エンコード
	cipherTextBase64 := base64.StdEncoding.EncodeToString(cipherText)

	fmt.Println(cipherTextBase64)
}
```

### Go言語によるCBCモード復号化

```go
package main

import (
	"crypto/aes"
	"crypto/cipher"
	"encoding/base64"
	"fmt"
	"log"

	"golang.org/x/crypto/scrypt"
)

func unpad(data []byte) []byte {
	padSize := int(data[len(data)-1])
	return data[:len(data)-padSize]
}

func main() {
	// Base64デコード
	cipherText, err := base64.StdEncoding.DecodeString("6Zcc5fKwbDAwgZ4W5ubcRP+egspMunkjCV+RJEYpKA8=")
	if err != nil {
		log.Fatal(err)
	}
	// 鍵を生成
	key, err := scrypt.Key([]byte("password"), []byte("salt"), 32768, 8, 1, 32)
	if err != nil {
		log.Fatal(err)
	}
	block, err := aes.NewCipher(key)
	if err != nil {
		log.Fatal(err)
	}
	// 先頭16Byteから初期化ベクトルを取り出す
	iv := cipherText[:aes.BlockSize]
	cipherText = cipherText[aes.BlockSize:]
	plainText := make([]byte, len(cipherText))

	mode := cipher.NewCBCDecrypter(block, iv)
	mode.CryptBlocks(plainText, cipherText)

	fmt.Println(string(unpad(plainText)))
}
```

## Padding Oracle Attack（パディングオラクル攻撃）とは
CBCモードの平文nは暗号文'n-1 ⊕ 平文'n ⊕ 暗号文n-1で求められるので攻撃者はサーバーに暗号文'を送信してパディングが不正かどうかエラーを見ながら正しいパディング（最終的には16 16...16になる）ような暗号文'を見つけます。それによって攻撃者は鍵なしで暗号文を復号することができます。
このようにパディングが正しいかどうかの情報を返すことで、その情報をもとに攻撃者が暗号文を復号、改ざんすることをパディングオラクル攻撃といいます。

### Go言語によるPadding Oracle Attack
サーバーの代わりにPKCS#7パディングを検証する`validatePadding `関数を使って鍵なしで暗号文を復号します

```go
package main

import (
	"crypto/aes"
	"crypto/cipher"
	"encoding/base64"
	"fmt"
	"log"
	"math"

	"golang.org/x/crypto/scrypt"
)

func main() {
	base64CipherText := "4oiepBFtjdj7HkHjUSLA746350IiDBHakWKQZ6Ldb+iN7RIW1ypRmETQ178JyUG2"
	cipherText, err := base64.StdEncoding.DecodeString(base64CipherText)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Println(cipherText)
	blockLen := len(cipherText) / aes.BlockSize
	plainText := make([]byte, len(cipherText)-aes.BlockSize)

	for blockIndex := 0; blockIndex < blockLen-1; blockIndex++ {
		copyCipherText := make([]byte, (blockIndex+2)*aes.BlockSize)
		copy(copyCipherText, cipherText)
		cipherBlock := copyCipherText[blockIndex*aes.BlockSize : (blockIndex+1)*aes.BlockSize]
		for i := 0; i < aes.BlockSize; i++ {
			cipherBlock[i] = 0
		}
		for i := 0; i < aes.BlockSize; i++ {
			for j := 0; j < math.MaxUint8; j++ {
				cipherBlock[aes.BlockSize-(i+1)] = byte(j)
				fmt.Println(copyCipherText)
				var ok bool
				ok, err = validatePadding(copyCipherText)
				if err != nil {
					log.Fatal(err)
				}
				if !ok {
					continue
				}
				break
			}
			if i+1 == aes.BlockSize {
				break
			}
			for k := 0; k < i+1; k++ {
				cipherBlock[aes.BlockSize-(k+1)] ^= byte(i+1) ^ byte(i+2)
			}
		}
		for i := 0; i < aes.BlockSize; i++ {
			plainText[blockIndex*aes.BlockSize+i] = copyCipherText[blockIndex*aes.BlockSize+i] ^ aes.BlockSize ^ cipherText[blockIndex*aes.BlockSize+i]
		}
	}
	fmt.Println(string(unpad(plainText)))
}

func unpad(data []byte) []byte {
	padSize := int(data[len(data)-1])
	return data[:len(data)-padSize]
}

func validatePadding(cipherText []byte) (bool, error) {
	key, err := scrypt.Key([]byte("applibot"), []byte(""), 32768, 8, 1, 32)
	if err != nil {
		log.Fatal(err)
	}
	block, err := aes.NewCipher(key)
	if err != nil {
		return false, err
	}
	iv := cipherText[:aes.BlockSize]
	cipherText = cipherText[aes.BlockSize:]
	plainText := make([]byte, len(cipherText))

	mode := cipher.NewCBCDecrypter(block, iv)
	mode.CryptBlocks(plainText, cipherText)

	padding := int(plainText[len(plainText)-1])
	if !(0 < padding && padding <= aes.BlockSize) {
		return false, nil
	}
	idx := len(plainText) - padding
	if idx < 0 || len(plainText) < idx {
		return false, nil
	}
	for _, p := range plainText[len(plainText)-padding:] {
		if int(p) != padding {
			return false, nil
		}
	}
	return true, nil
}
```

## おわりに
実行に時間がかかりますが、試してみて復号結果見てもらえると嬉しいです！

標準パッケージを使うことで簡単に暗号化できる反面、適切に実装しないと今回のように攻撃できてしまうことがわかりました。
今回、暗号と攻撃について興味を持ったのでもっと深く学んでいきたいと思います！

以上、「 [Applibot Advent Calendar 2021](https://qiita.com/advent-calendar/2021/applibot) 」 22日目の記事でした！