この記事は「脆弱性"&'<<>\ Advent Calendar 2015」23日目の記事です。

ブロック暗号モードのひとつであるCBC modeには、Padding oracle attackと呼ばれる攻撃手法が存在することが知られている。これは、繰り返し復号を行うことができ、かつ復号の成否が観測可能なとき、バイトごとのブルートフォースにより暗号文が復元できるというものである。ここでは、実際に簡単なコードを用いてこれを確認してみる。

環境

Ubuntu 14.04.3 LTS 64bit版、Ruby 1.9.3

$ uname -a
Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 14.04.3 LTS
Release:        14.04
Codename:       trusty

$ ruby --version
ruby 1.9.3p484 (2013-11-22 revision 43786) [x86_64-linux]

Padding oracle attackの概要

AESなどのブロック暗号アルゴリズムは、固定長のブロックに対して暗号化を行う。任意の長さの平文を暗号化する場合は、平文を固定長のブロックに分割した上で暗号化を行うことになるが、このとき平文がブロック長の定数倍となるよう末尾にpaddingがつけ加えられる。 paddingのつけ加え方にはさまざまなものが考えられるが、一般にはRFC 5652で定義されているPKCS#7由来の方法が用いられている。具体的には次のように、定数倍となるまでに足りないバイト数の値が埋められる。

         01 -- if lth mod k = k-1
      02 02 -- if lth mod k = k-2
          .
          .
          .
k k ... k k -- if lth mod k = 0

また、平文がちょうどブロック長の定数倍だった場合はすべてのバイトがpaddingのブロックが付け加えられる。したがって、どのような暗号文であっても復号すると必ずpaddingが現われるようになっている。

ブロック暗号アルゴリズムを用いて複数のブロックを暗号化する方法を、ブロック暗号化モードという。ブロック暗号化モードのひとつであるCBC modeでは、次のように一つ前のブロックの結果を用いる形で暗号化・復号を行う。

Encryiption:
C[1]   = E(P[1] xor IV)
C[2]   = E(P[2] xor C1)
...
C[k]   = E(P[k] xor C[k-1])

Decryiption:
P[1]   = D(C[1]) xor IV
P[2]   = D(C[2]) xor C[1]
...
P[k]   = D(C[k]) xor C[k-1]

P[k]、C[k]はk番目の平文、暗号文ブロック、Eは暗号化関数、Dは復号関数、IVは初期化ベクトルである。

ここで、最後の復号の式の C[k-1] に対して適当な C'[k-1] を考え、対応する平文を P'[k] とすると次の関係が成り立つ。

P'[k]  = D(C[k]) xor C'[k-1]
<=> P'[k]  = D(E(P[k] xor C[k-1])) xor C'[k-1]
<=> P'[k]  = P[k] xor C[k-1] xor C'[k-1]

適当な C'[k-1] を与えたとき C'[k-1] + C[k] が正しく復号できるのであれば、P'[k] の末尾には正しいpaddingがついているはずである。 xorがバイトごとの演算であることを考えると、正しく復号できる C'[k-1] の最後の1バイトが見つかったとき、これに対応する P'[k] の最後の1バイトは 0x01 となる。すなわち、最後の1バイトについて

0x01 = P[k] xor C[k-1] xor C'[k-1]
<=> P[k] = 0x01 xor C[k-1] xor C'[k-1]

となり、P[k] の最後の1バイトを特定することができる。

ここからさらに、

最後の2バイトが 0x02 0x02 となるように、C'[k-1] の最後から1バイト目を調整した後、C'[k-1] の最後から2バイト目を特定
最後の3バイトが 0x03 0x03 0x03 となるように、C'[k-1] の最後から1～2バイト目を調整した後、C'[k-1] の最後から3バイト目を特定
……

と繰り返していくことで、P[k] のすべてのバイトを特定することができる。

P[k] の復元は一つ前の暗号文ブロック C[k-1] にのみ依存しているため、この手順を各 P[k] に対して行うことで P[1] を除くすべてのブロックを復元することができる。 paddingに関する前提知識をもとに特定していくことから、この手法はPadding oracle attackと呼ばれる。

プログラムコードを書いてみる

上の内容をもとに、AES-256-CBCで暗号化されたデータの復元を試みるプログラムコードを書くと次のようになる。 AESアルゴリズムのブロック長は128 bit（16バイト）であり、鍵長は256-bit AESの場合256 bit（32バイト）である。

# paddingoracle.rb
require 'openssl'

def encrypt(data)
  c = OpenSSL::Cipher::Cipher.new('aes-256-cbc')
  c.encrypt
  c.key = "secret".ljust(32)
  c.iv = "unknown".ljust(16)
  return c.update(data) + c.final
end

def try_decrypt(data)
  begin
    c = OpenSSL::Cipher::Cipher.new('aes-256-cbc')
    c.decrypt
    c.key = "secret".ljust(32)
    c.iv = "unknown".ljust(16)
    c.update(data)
    c.final
    return true
  rescue OpenSSL::Cipher::CipherError
    return false
  end
end

def attack(ciphertext)
  blocksize = 16
  blocks = ciphertext.scan(/[\s\S]{#{blocksize}}/)

  (blocks.length-1).downto(1) do |k|
    plain = "?" * blocksize
    iv = "\x00" * blocksize

    1.upto(blocksize) do |n|
      0.upto(255) do |i|
        iv[-n] = i.chr
        data = iv + blocks[k]

        if try_decrypt(data) then
          plain = iv.bytes.zip(blocks[k-1].bytes).map { |x,y| n ^ x ^ y }.pack("C*")
          p plain
          iv = plain.bytes.zip(blocks[k-1].bytes).map { |x,y| (n+1) ^ x ^ y }.pack("C*")
          break
        end
      end
    end

    blocks[k] = plain
  end

  blocks[0] = "?" * blocksize
  return blocks.join
end

plaintext = 'In cryptography, a padding oracle attack is an attack which is performed using the padding of a cryptographic message. In cryptography, variable-length plaintext messages often have to be padded (expanded) to be compatible with the underlying cryptographic primitive. The attack relies on having a "padding oracle" who freely responds to queries about whether a message is correctly padded or not. Padding oracle attacks are mostly associated with CBC mode decryption used within block ciphers. Padding modes for asymmetric algorithms such as OAEP may also be vulnerable to padding oracle attacks.'
ciphertext = encrypt(plaintext)

p plaintext
p attack(ciphertext)

上のコードにおいて、try_decrypt関数は復号結果そのものは返さず、復号の成否のみを返す関数である。 attack関数は、このtry_decrypt関数の結果のみを用いて復元を試みる。

実際に実行してみると次のようになる。

$ ruby paddingoracle.rb
"In cryptography, a padding oracle attack is an attack which is performed using the padding of a cryptographic message. In cryptography, variable-length plaintext messages often have to be padded (expanded) to be compatible with the underlying cryptographic primitive. The attack relies on having a \"padding oracle\" who freely responds to queries about whether a message is correctly padded or not. Padding oracle attacks are mostly associated with CBC mode decryption used within block ciphers. Padding modes for asymmetric algorithms such as OAEP may also be vulnerable to padding oracle attacks."
"S#[\xC1\xD0\x1An\x89\xC7\xD8y\xAF\xE2-\xD8\v"
"S#[\xC1\xD0\x1An\x89\xC7\xD8y\xAF\xE2-\v\v"
"S#[\xC1\xD0\x1An\x89\xC7\xD8y\xAF\xE2\v\v\v"
"S#[\xC1\xD0\x1An\x89\xC7\xD8y\xAF\v\v\v\v"
"S#[\xC1\xD0\x1An\x89\xC7\xD8y\v\v\v\v\v"
"S#[\xC1\xD0\x1An\x89\xC7\xD8\v\v\v\v\v\v"
"S#[\xC1\xD0\x1An\x89\xC7\v\v\v\v\v\v\v"
"S#[\xC1\xD0\x1An\x89\v\v\v\v\v\v\v\v"
"S#[\xC1\xD0\x1An\v\v\v\v\v\v\v\v\v"
"S#[\xC1\xD0\x1A\v\v\v\v\v\v\v\v\v\v"
"S#[\xC1\xD0\v\v\v\v\v\v\v\v\v\v\v"
"S#[\xC1.\v\v\v\v\v\v\v\v\v\v\v"
"S#[s.\v\v\v\v\v\v\v\v\v\v\v"
"S#ks.\v\v\v\v\v\v\v\v\v\v\v"
"Scks.\v\v\v\v\v\v\v\v\v\v\v"
"acks.\v\v\v\v\v\v\v\v\v\v\v"
"\xEC\xA8\x8DC?H\xC2 \xC2\xEE?\x01\xD2\xDB\xE1t"
"\xEC\xA8\x8DC?H\xC2 \xC2\xEE?\x01\xD2\xDBtt"
"\xEC\xA8\x8DC?H\xC2 \xC2\xEE?\x01\xD2att"
"\xEC\xA8\x8DC?H\xC2 \xC2\xEE?\x01 att"
"\xEC\xA8\x8DC?H\xC2 \xC2\xEE?e att"
"\xEC\xA8\x8DC?H\xC2 \xC2\xEEle att"
"\xEC\xA8\x8DC?H\xC2 \xC2cle att"
"\xEC\xA8\x8DC?H\xC2 acle att"
"\xEC\xA8\x8DC?H\xC2racle att"
"\xEC\xA8\x8DC?Horacle att"
"\xEC\xA8\x8DC? oracle att"
"\xEC\xA8\x8DCg oracle att"
"\xEC\xA8\x8Dng oracle att"
"\xEC\xA8ing oracle att"
"\xECding oracle att"
"dding oracle att"
(snip)
"\x96f2\xCB\x19\xE5PX\xA3\xEF,\xFA\xE7\xCB\xB9l"
"\x96f2\xCB\x19\xE5PX\xA3\xEF,\xFA\xE7\xCBcl"
"\x96f2\xCB\x19\xE5PX\xA3\xEF,\xFA\xE7acl"
"\x96f2\xCB\x19\xE5PX\xA3\xEF,\xFAracl"
"\x96f2\xCB\x19\xE5PX\xA3\xEF,oracl"
"\x96f2\xCB\x19\xE5PX\xA3\xEF oracl"
"\x96f2\xCB\x19\xE5PX\xA3g oracl"
"\x96f2\xCB\x19\xE5PXng oracl"
"\x96f2\xCB\x19\xE5Ping oracl"
"\x96f2\xCB\x19\xE5ding oracl"
"\x96f2\xCB\x19dding oracl"
"\x96f2\xCBadding oracl"
"\x96f2padding oracl"
"\x96f padding oracl"
"\x96a padding oracl"
" a padding oracl"
"???????????????? a padding oracle attack is an attack which is performed using the padding of a cryptographic message. In cryptography, variable-length plaintext messages often have to be padded (expanded) to be compatible with the underlying cryptographic primitive. The attack relies on having a \"padding oracle\" who freely responds to queries about whether a message is correctly padded or not. Padding oracle attacks are mostly associated with CBC mode decryption used within block ciphers. Padding modes for asymmetric algorithms such as OAEP may also be vulnerable to padding oracle attacks.\v\v\v\v\v\v\v\v\v\v\v"

上の結果から、最初のブロックを除くすべてのブロックを復元できていることが確認できる。

認証付き暗号（AEAD）

現在では、CBC modeに代わる暗号利用モードとしてGCM modeが広く利用されている。 GCM modeは認証付き暗号（AEAD）と呼ばれる暗号方式のひとつであり、暗号化と同時にメッセージ認証コード（MAC）を計算する。 AEADでは復号時にMACが一致するかどうかの検証が行われるため、Padding oracle attackのような攻撃は難しいとされている。

AEADはTLS 1.2以降で使えるようになっており、GCM modeの他にはCTR modeの派生であるCCM modeが利用できる。また、TLS 1.3の現行のdraftではAEADの利用が必須となり、RC4に代表されるストリーム暗号やCBC modeはサポートされない予定となっている。

ももいろテクノロジー

CBC modeに対するPadding oracle attackをやってみる

環境

Padding oracle attackの概要

プログラムコードを書いてみる

関連するSSL 3.0/TLS 1.0攻撃手法

認証付き暗号（AEAD）

関連リンク