Padding Oracle Attack 分かりやすく解説したい
Padding Oracle Attack, AESを使うCTF問題で一番難しいのではないのでしょうか。僕もこれがあるせいでAES問題に強い苦手意識がありました。僕と同じような方も、この記事で得意になってくれると嬉しいです！Padding Oracle Attackが理解できると、どんなAES問題も強気で解きにいけると思います！
AESとは
いつもの。
ブロック暗号の代表格ですね。あまり言うと違うよとお叱りを受けそうなのですが、DESに脆弱性が発見されてからAESが主流となり推奨されているといった感じです。
ブロック暗号とは、平文をN文字ずつ分けそれぞれ暗号化するような感じです。AESでは16文字ごと分けています。その暗号化の方式はいくつかあり、AESではECB, CBC, CFBモードなどがあります。
AESのCBCモードとは
暗号化
平文を16文字ずつに分け、各ブロックをkeyというバイト列によって暗号化します。自分の理解ではkeyの値を知っていたとしてもどのように暗号化されるかは分からないです。pythonのpycryptodomeモジュールでは簡単にできますが、まあできないもんとしていても大丈夫だと思います。
keyとは別にivというバイト列も用意します。平文の第1ブロックをivとxorし、その値をkeyによって暗号化したのが暗号文の第1ブロックになります。続いて、平文の第2ブロックとivではなく暗号文の第1ブロックとxorしたのをkeyによって暗号化したのが暗号文の第2ブロックとなります。
以降は [平文の第kブロック] xor [暗号文の第k-1ブロック] -> (key) -> [暗号文の第kブロック] となります。
これがAESのCBCモードです。CTFでは他にECBモードが良く使われます。ECBは平文をただkeyによって暗号化するだけなので、同じ平文ブロックがあると同じ暗号文ブロックになるという欠点があります。その点、CBCモードは前の暗号文ブロック(もしくはiv)とxorするので、同じ平文ブロックがあっても異なる暗号文ブロックになります。
復号
復号方式は、暗号化方式の手順を逆にしたものです。
まず第1暗号文ブロックをkeyによってdecryptし、ivとxorしたのが第1平文ブロックです。以降はkeyによってdecryptするのは同じですが、xorするのはその一つ前の暗号文ブロックとです。
CBCモードの暗号化/復号方式はこんな感じです。不慣れな方はじっくり勉強しましょう！
CBCモードのCTF問題で、Padding Oracle Attackを使わないものですが、これが分かるとよりこの攻撃が理解しやすくなると思います！
ångstromCTF 2021 writeup - Attack All Around
Padding方式 PKCS #7とは
AESでは、ある平文を暗号化する際に平文を16文字ずつ分けますが、その平文の長さが16の倍数でない時はどうなるのでしょうか。答えは平文の後ろに詰め物をして強引に16の倍数にします。この詰め物をパディングといいます。
ではPKCS #7がどのようにパディングしているかというと、パディングしている長さを値としてパディングします。はい、よく分からないですよね。具体例を出しましょう。
b"0123456789abcde" という平文を暗号化したいと思います。長さが15なので16の倍数にするには1つパディングする必要があります。その場合、PKCS #7方式では「b"0123456789abcde\x01"」となります。1つパディングするのでb"\x01"が1つあります。
では、b"0123456789abcd" という平文を暗号化したい場合のパディングは、どうなるのでしょうか。答えは「b"0123456789abcd\x02\x02"」です。2つパディングするのでb"\x02"が2つあります。
こんな感じで、3個のパディングはb"\x03\x03\x03", 11個パディングするにはb"0x0b"×11となります。このようにパディングがどれだけされているかがパディング値で分かるようになっています。これでどこまでが平文でどれが詰め物かが分かるようになりますね。
pythonのpycryptodomeでは、Crypto.Cipher モジュールにpad関数が実装されています。pad(byte列, 1ブロックの長さ(=基本16) )とするとPKCS #7方式でパディングしてくれます。style = で指定するパターンもあります。
加えて、unpad関数も実装されています。pad関数と同様に、unpad(byte列, 16)でパディングを消してくれます。ここで重要なのが、unpad関数は第一引数のbyte列がこのPKCS #7方式でパディングしていない場合、エラーを吐きます。まず一番後ろの1byteを見て、b"\x01" ~ b"\x10"でないならエラー吐きますし、そうであってもその長さ分同じものが続いていないとエラーを吐きます。
エラーを吐く例
- b"abcdefghijklmnop"
- b"abcdefghijklmno\x02"
- b"abcdefghijkl\x04\x04\x03\x03"
- b"abcdefghijkl\x04\x03\x04\x04"
エラーを吐かない例
- b"abcdefghijklmn\x02\x02"
- b"abcdefghijklmnop" + b"\x10"×16
- b"abcdefghijklm\x03\x02\x01" -> パディングが1つとして扱われる
このunpad関数でのパディングが上手くいかなかった時のエラー、これを通信相手に教えてしまうとPadding Oracle Attackが出来てしまう環境となってしまいます。次の節で具体的に解説していきます！
用意した自作サーバ
GitHub - ksbowler/PaddingOracleAttack
こちらのgithubにも載せていますが、公開サーバーだけ載せますね。
import socketserver import socket, os from Crypto.Cipher import AES from Crypto.Util.Padding import pad,unpad from binascii import unhexlify, hexlify from secret import FLAG, MSG import base64 key = os.urandom(16) iv = os.urandom(16) def encrypt_data(data): pt = pad(data.encode(),16,style='pkcs7') cipher = AES.new(key, AES.MODE_CBC,iv) enc = cipher.encrypt(pt) return enc.hex() def decrypt_data(encryptedParams): assert len(encryptedParams) >= 32 IV = encryptedParams[:32] data = encryptedParams[32:] cipher = AES.new(key, AES.MODE_CBC,unhexlify(IV)) paddedParams = cipher.decrypt( unhexlify(data)) pt = unpad(paddedParams,16,style='pkcs7') return pt def send_msg(s, msg): enc = msg.encode() s.send(enc) def main(s): wlcm_msg = "Welcome to practice for Padding Oracle Attack\n" send_msg(s, wlcm_msg) msg = base64.b64encode(MSG.encode()).decode() send_msg(s, "Guest ciphertext: " + encrypt_data(msg)+'\n') IV = hexlify(iv).decode() send_msg(s, "IV : "+IV+"\n") while True: #任意の暗号文を復号できる send_msg(s, 'What ciphertext do you want to decrypt? (hex): ') ct = s.recv(4096).decode().strip() try: check = decrypt_data(ct) send_msg(s, "check you can login\n") #print("check :",check) except Exception as e: send_msg(s, str(e) + '\n') continue try: pt = base64.b64decode(check).decode() if pt[:25] == MSG[:25]: send_msg(s, "You can login!\n") if pt[25:] == "admin": clear_msg = "OK! You are admin! Here is flag\n" send_msg(s, clear_msg) send_msg(s, FLAG+"\n") else: guest_msg = "However, because you are not admin, we can not send you flag\n" send_msg(s, guest_msg) else: invalid_msg = "We can not recognize your input for our service\n" send_msg(s, invalid_msg) except Exception as e: send_msg(s, str(e) + '\n') class TaskHandler(socketserver.BaseRequestHandler): def handle(self): main(self.request) if __name__ == '__main__': socketserver.ThreadingTCPServer.allow_reuse_address = True server = socketserver.ThreadingTCPServer(('0.0.0.0', 3000), TaskHandler) server.serve_forever()
流れとしては、
- 変数MSGにある文字列をbase64で暗号化し、AESのCBCモードで暗号化したものが送られる。
- この暗号化に使われたIVが送られる。
- 任意の文字列を復号してくれる。IVも自身で決められる。
3-a. 復号時に失敗すると、エラー文が送られる。
3-b. 復号しbase64decodeしたものと、変数MSGの前25文字と比較する。
3-b-1. 合致し且つ残りが"admin"だとflagがゲット。 (目標はここ)
3-b-2. 合致するが残りが"admin"でないと、loginできないと言われる。
3-b-3. 合致しないと認識できないと言われる。
この3-aが脆弱性なんです。次節で説明していきますね。
平文を手に入れる Decryption Attack
それでは本題の攻撃アルゴリズムについて書いていきます。
Padding Oracle Attackを簡単に言うと、暗号文ブロックc_iをkeyによってdecryptionした値Dec(c_i)が分かれば、そこから貰った暗号文ブロックc(i-1)とxorすれば平文ブロックp_iが分かるし、任意の平文ブロックp_iに対する暗号文ブロックc(i-1)をxorすることで作成できます。だからDec(c_i)を求めようという感じです。
githubにも載せているスライドに合わせて進めていきます。
この問題の目的は上記の3-b-1になることです。そのためにはまず、変数MSGがどんな文字列が分からないといけません。変数MSGがbase64 encodeされた値がCBCモードで暗号化されています。その暗号文から元の平文を求めていくのがDecryption Attackです。
まずは、平文の最終ブロックを求めていきます。今回は暗号文が16進数で96桁なので3blocksあります。なのでp3を求めていきます。
p3 = Dec(c3) xor c2 という式で復号されます。ここでDecとはkeyによって復号された値です。p3を求める前にこのDec(c3)を求めます(スライドではc2となっています)。
本問のサーバは復号文は教えてくれませんし、Dec(c3)の値も教えてくれません。しかし、復号時にPaddingがきちんとされてないとエラー文を送ってくれます。それを使ってDec(c3)を求めます。
c2の16bytesを全てb"\x00"にして送ります。理由は後述します。そこから最後1byteを0x00から0xffまで全て試します。そうすると、一回だけPadding incorrectと出ない時があります。復号されたp3の最後1byteがb"\x01"となった時ですね。そうなった時に何を送ったかを覚えておきます。例えばそれが"f6"だったとします。そうなると、Dec(c3)の最後1byteが、0xf6 xor 0x01 = 0xf7であることが分かります！
次に、Dec(c3)の最後2byte目を求めます。次はp3の最後2byteをb"\x02\x02"となるようにしたいです。まず、p3の下位1byteをb"\x02"にするには、0xf7 xor 0x02 = 0xf5をc2の下位1byteとします。そして、c2の下位2byte目を0x00から0xffまで全て試して、padding incorrectが出ないものを見つけます。先と同様にDec(c3)の2byte目を求めます。
ここまで来るとお分かりでしょうが、次はDec(c3)の下位3byte目を求めます。下位2bytesをb"\x03\x03"になるようc2の下位2bytesを調整し、c3の下位3byte目をbrute forceします。
これを繰り返していくと、Dec(c3)の16bytes全て求めることが出来ます。そこからp3は簡単に分かります。1. で貰ったMSGの暗号文と求めたDec(c3)より、p3 = Dec(c3) xor c2の式に当てはめるとp3が求められましたね。
本問では、以下のような平文となりました。
m = b'PWd1ZXN0\x08\x08\x08\x08\x08\x08\x08\x08'
base64decodeすると、"=guest"となりました。文字列になったことから正しく動作していることが分かりますね。
先程少し触れた「c2の16bytesを全てb"\x00"にする」理由ですが、もらったc2の上位15bytesをそのまま使うとpadding incorrectと言われない時が二回ある可能性があります。平文のpaddingとごっちゃになってしまう場合に注意です。
p3が求められたので、次はp2を求めていきます。サーバに送る暗号文はIVとc1, c2とし、c3は送りません。c2を最終ブロックとすることで、p2のpaddingがどうか先程と同じようにしてDec(c2)→p2を求めていきます。
以上を繰り返して、平文全てを求めます。平文の先頭ブロックを求める時はIVを変えていきます。やり方は上のと変わりません。
b'bTF6MHIzX2xvZ2luX3NlcnZpY2U6IElEPWd1ZXN0\x08\x08\x08\x08\x08\x08\x08\x08'
base64 decode : b'm1z0r3_login_service: ID=guest'
IDがguestではloginできませんね。adminにしてloginできるように、Encryption Attackを行いましょう。
任意の平文に対する暗号文を手に入れる Encryption Attack
Decryption Attackは複雑で難しいと思いますが、これが理解できればEncryption Attackは大して難しくありません。やっていることはDecryption Attackとさほど変わりません。
Encryption Attackは、padding incorrectを教えてくれる時に、復号したら欲しい平文となる暗号文を作ることが出来る攻撃です。
本問では、b'm1z0r3_login_service: ID=admin'をbase64 encodeした平文、つまり「b'bTF6MHIzX2xvZ2luX3NlcnZpY2U6IElEPWFkbWlu\x08\x08\x08\x08\x08\x08\x08\x08'」が欲しいです。これの暗号文を作っていきましょう。
Encryption Attackの手順は、初めにDecryption Attackと同じようにDec(c_i)を求めます。c3はMSGの暗号文と変える必要はありません。そのDec(c3)を求めたら、b'PWFkbWlu\x08\x08\x08\x08\x08\x08\x08\x08'とxorした値をc2とします。c2とDec(c3)をxorしたらこの欲しい平文になりますよね。
では、次にこの新しいc2のDec(c2)を求めるためにc1をいじくります。Decryption Attackと同じようにしてOKです。Dec(c2)が求まったら、欲しい平文の後ろから2つ目とブロックとxorしてそれをc1とします。同じようにしてIVも求めます。
IVとc1~c3を送ると、それが欲しい平文と復号されるので、adminとしてloginが出来てflagが手に入りました！
m1z0r3{Padding_Oracle_Attack_is_so_difficult}
おわりに
githubにsolver.pyと公開サーバのserver.pyと作問者しか見られないsecret.py, そして解説資料のpdfを載せています。そちらもご覧ください。
GitHub - ksbowler/PaddingOracleAttack
Padding Oracle Attackを使う問題は多くはないですが、理解できるとほとんどのAES問題は解けると思います。はじめにも書きましたが、私もこれがあるからAES問題は好きではなかったのですが、分かると楽しくなりました！
crypto問題面白いけど実生活に活きることあるのだろうか、と考えながらCTFを解いているこの頃…。解けると楽しいんだよなぁ。でもタスクもある…。と苛まれている次第です。ご査収ください。
参考文献
- Padding Oracle AttackによるCBC modeの暗号文解読と改ざん - security etc...
この文献を理解できるようになるまでしばらくかかりました。この記事でより早く理解できたということがあると嬉しいです！
