Padding Oracle Attack

cbcモード pkcs#7 padding_oracle_encryption_attack

以下の条件を満たすとき、暗号文から平文を復元できる

  • CBCモード で暗号化されている

  • PKCS#7 でパディングされている

  • 復号の成否がわかる

  • 何度でも復号できる

原理

CBCモードでは暗号化は次のように行われる

C_1 = E(M_1 \oplus IV), C_2 = E(M_2 \oplus C_1), \dots, C_N = E(M_N \oplus C_{N-1})

同様に復号はこう

M_N = D(C_N) \oplus C_{N-1}, \dots, M_2 = D(C_2) \oplus C_1, M_1 = D(C_1) \oplus IV

ここで偽物のデータ C'_{N-1}を与えて復号してみる。すると以下のようになることがわかる。

M'_N = D(C_N) \oplus C'_{N-1} = M_N \oplus C_{N-1} \oplus C'_{N-1}

C'_{N-1}の最下位バイトを探索して M'_Nの最下位バイトを0x01にできれば復号は成功する（それ以外はたいてい失敗する）。この時 M'_{N,16}, C_{N-1}, C'_{N-1}はわかっているので、

M_{N,16} = M'_{N,16} \oplus C_{N-1,16} \oplus C'_{N-1,16} = 1 \oplus C_{N-1,16} \oplus C'_{N-1,16}

同様に、 M'_Nの下位2バイトが0x02, 0x02となって復号が成功するように C'_{N-1,15}を探索する。 C'_{N-1,16}は M_{N,16} \oplus C_{N-1,16} \oplus 0x02として求まるので探索する必要がない。

これを繰り返すことで M_{N,16}から M_{N,1}まで、すなわち M_Nがすべて求まる。同じ手順を繰り返すと M_N, M_{N-1}, ..., M_2, M_1が求まる。

Padding Oracle Encryption Attack

Padding Oracle Attackが使えるとき、好きな平文に復号される暗号文を作ることができる。以下の手順

  • C_N は適当にやる

  • C_{N-1} の値を探索してpadding oracle attackみたいにする

    • まず16バイト目を探索する。 M_{N,16} = D_{16}(C_{N}) \oplus C'_{N-1,16} = 0x01 となるような C'_{N-1,16} を求める

    • 続いて15バイト目を探索する。 C'_{N-1,16} は C'_{N-1,16} \oplus 0x01 \oplus 0x02 とすれば M_{N,16} = 0x02 とできるので探索する必要はない

    • 同様にして C'_{N-1} を全て求める

  • C'_{N-1} を使うと適当に決めた C'_N を好きな平文 M_{N} として復号させられる

    • D_{16}(C_{N}) \oplus C'_{N,16} \oplus 0x01 \oplus X = X = M_{N,16}

  • ただし C'_{N-1} の復号結果は当然壊れるので、これもすきな平文に復号させられるように C'_{N-2} を探索する

  • 同様にしていくとIVを探索して C'_{1} の復号結果を好きに決められる。結果的に全ての平文を好きに復号できた