Padding Oracle Attacks

วันนี้ผมขอเขียนเรื่อง Padding Oracle Attacks ก่อน (จริงๆ แล้วตั้งใจจะเขียนตั้งแต่เพิ่งเปิด blog) เรื่องนี้ไม่ได้เป็นเรื่องใหม่ แต่ผมเห็นว่าเป็นเรื่องที่น่าสนใจมาก เพราะเป็น cryptography attack ที่ใช้ความรู้เกี่ยวกับ cryptography ไม่เยอะ แต่มีผลกระทบกับ application framework หลายตัว เช่น JavaServer Faces (JSF), Ruby on rails, ASP.NET o.O

เทคนิคนี้ จริงๆแล้วได้มีการพูดถึงในงาน Eurocrypt 2002 โดย Serge Vaudenay โดยพูดถึงช่องโหว่เกี่ยวกับ CBC padding ของ encryption protocol ต่างๆ เช่น SSL, IPSEC, WTLS, SSH2 และเมื่อปี 2010 ที่ผ่านมา security researcher 2 คน คือ Joliano Rizzo กับ Thai Duong ได้นำเทคนิคนี้มาใช้อีกรอบ แต่เป็นการโจมตี web application โดยพูดในงาน Blackhat Europe 2010

เรามาเริ่มเนื้อหากันเลยดีกว่า เทคนิคนี้เป็นการโจมตีเมื่อใช้ encryption algorithm ที่ทำงานเป็น block ใน CBC mode ถ้าใครไม่รู้จัก CBC mode แนะนำให้หาอ่านก่อนนะครับ หรือไม่ก็ดูในบทความแรกที่ผมเขียน (CBC Bit Flipping) เผื่อจะทำให้เข้าใจ

เนื่องด้วย encryption algorithm เช่น DES, AES นั้นทำงานเป็น block ดังนั้นถ้าข้อมูลไม่ครบ block ก็จำเป็นต้อง pad ข้อมูลเข้าไปเพื่อที่จะเต็ม block แล้วทำการ encryption ได้ โดย padding scheme ที่นิยมใช้กัน จะเป็นแบบเดียวกับที่กล่าวใน PKCS#5, PKCS#7 หรือ RFC2630 (CMS) วิธีการ padding ก็คือเติมตัวเลขเท่าจำนวนที่ต้อง pad โดยต้อง pad อย่างน้อย 1 byte ตามตัวอย่างในรูป โดยสมมติว่าขนาดของ block คือ 8 bytes

เพื่อที่จะให้เข้าใจง่ายขึ้น ผมจึงได้เขียน php code ที่ใช้ run บน web server สำหรับสาธิตการทำงานของ attack นี้โดยจะมี code อยู่ 3 ไฟล์ (po_gen.php, po_check.php, po_inc.php) ไฟล์แรก po_gen.php ใช้สำหรับ encrypt ข้อมูลโดยใช้แทนการ login ที่เราใส่ username แล้วมีการส่ง token สำหรับการ request อื่นๆ และไฟล์ที่สอง po_check.php ซึ่งรับ token แล้วบอกว่าข้อความในนั้นคืออะไร ใช้แทนการตรวจสอบ token และไฟล์สุดท้าย po_inc.php เป็นไฟล์ที่ใช้ config ค่าต่างๆ สำหรับ encryption โดยผมได้กำหนดค่า IV เป็น fixed value เพื่อให้ค่าที่ผมแสดงตรงกับของทุกๆคน ซึ่งจริงๆแล้วควรเป็น random value (แก้ให้ random โดยเปลี่ยนค่า RANDOM_IV เป็น TRUE) และผมจะใช้ 3-DES ในการทำ encryption เพราะมี block size เป็น 8 bytes เขียนอธิบายได้ง่ายกว่า AES ที่มี block size เป็น 16 bytes (ถ้าใครอยากลองเป็น AES ก็แก้ค่า USE_3DES เป็น FALSE นะครับ)

สมมติว่าผมจะส่ง "user5" ไปที่ po_gen.php แล้วจะได้ encrypted data

$ curl "http://127.0.0.1/thtutz/po_gen.php?user=user5"
5f4649584544495621a7b2b00f85b47d

และถ้าผมส่ง encrypted data นี้ไปที่ po_check.php จะได้

$ curl "http://127.0.0.1/thtutz/po_check.php?user=5f4649584544495621a7b2b00f85b47d"
Data OK : user5

โดยมีค่าต่างๆในการทำ decryption ตามรูป

แต่ถ้าเราเปลี่ยน encrypted data โดยสมมติว่าเปลี่ยนค่าหลังสุดของ IV เป็น 00 จะได้

$ curl "http://127.0.0.1/thtutz/po_check.php?user=5f4649584544490021a7b2b00f85b47d"
Error: Invalid padding

โดยมีค่าต่างๆในการทำ decryption ตามรูป

จากรูปจะเห็นว่า byte สุดท้ายเป็น 0x55 ซึ่งทำให้เจอ error ขณะทำการตรวจสอบ padding

concept ของ padding oracle attack นี้คือส่ง encrypted data ไปที่ server เพื่อให้ server บอกว่า padding ของ encrypted data นี้ถูกต้องหรือไม่ โดยใช้ error message หรือ response ต่างๆ ที่สามารถแยกได้ว่า encrypted data นี้เมื่อ server decrypt แล้ว padding ถูกหรือไม่

จากรูปการ decryption จะเห็นว่าเรารู้ค่าของ Encrypted data และ IV เท่านั้น ส่วน Intermediary Value นั้น ปกติต้องมี Encryption Key เท่านั้นจึงจะหา Intermediary Value ออกมาได้ และส่วนที่สำคัญที่สุดของเทคนิคนี้ คือสามารถหา Intermediary Value ได้โดยไม่ต้องรู้ว่า Encryption Key คืออะไร

Padding Oracle Attack เพื่อ decrypt ข้อมูล

โดยปกติ เวลาเราได้ encrypted data มาจาก server เราไม่รู้ว่าข้างในนั้นเก็บข้อมูลในรูปแบบไหน ในส่วนนี้ผมจะอธิบายวิธีการ decrypt ข้อมูลโดยสมมติว่าเราไม่รู้ข้อมูลที่เป็น plaintext และมีการส่ง request ไปที่ po_check.php เท่านั้น

วิธีก็คือ (อยากให้คิดตาม เพราะถ้าเข้าใจ จะคิดเองได้เลย)
1. เปลี่ยนค่า IV เป็น 0x00 ให้หมด (จริงๆ คือเปลี่ยนเป็นอะไรก็ได้)
2. เริ่มจาก byte หลังสุดของ block และให้จำนวนที่ต้อง pad คือ 1 byte ดังนั้น plaintext ของ byte สุดท้ายต้องเป็น 0x01
3. เปลี่ยนค่า IV ไปเรื่อยๆ จนกว่า server ไม่บอกว่า "Error: Invalid padding"
4. เมื่อได้ค่า IV และ plaintext ของ byte ที่ทำงานอยู่ ทำให้สามารถหา Intermediary Value ของ byte นั้นได้โดยการทำ xor
5. หา plaintext ของ byte ที่ทำงานอยู่ จะได้ plaintext จากการนำ Intermediary Value มา xor กับค่า IV เดิม
6. เปลี่ยนเป็น byte ถัดไปจากข้างหลัง และเปลี่ยนจำนวนที่ต้อง pad เป็นค่าถัดไป จนกว่าจะครบ block
7. เปลี่ยน IV ของ byte หลังที่จะหา เป็น pad value ที่ถูกต้อง โดยนำ pad value ที่ต้องให้เป็นไป xor กับ Intermediary Value ที่หาได้ และไปทำที่ข้อ 3

อ่านวิธีอาจจะงง มาดูตัวอย่างกันดีกว่า เริ่มต้นที่เปลี่ยนค่า IV เป็น 0 ซึ่งจะได้ค่าต่างๆ ในการทำ decryption ตามรูป

จากนั้นเราก็ส่ง request ไปที่ po_check.php โดยเปลี่ยนค่า IV ไปเรื่อยๆ ดังนี้

$ curl "http://127.0.0.1/thtutz/po_check.php?user=000000000000000021a7b2b00f85b47d"
Error: Invalid padding
$ curl "http://127.0.0.1/thtutz/po_check.php?user=000000000000000121a7b2b00f85b47d"
Error: Invalid padding
$ curl "http://127.0.0.1/thtutz/po_check.php?user=000000000000000221a7b2b00f85b47d"
Error: Invalid padding
...
$ curl "http://127.0.0.1/thtutz/po_check.php?user=000000000000005421a7b2b00f85b47d"
Data OK : *5,*pGJ

ได้ค่า IV ของ byte สุดท้ายที่ทำให้ plaintext ออกมาเป็น 0x01 คือ 0x54 ทำให้ได้ Intermediary Value เป็น 0x01 ^ 0x54 = 0x55 ตามรูปข้างล่าง ซึ่ง plaintext ของ byte นี้ก็คือ 0x55 ^ 0x56 = 0x03

หลังจากนั้น ก็ทำ byte ถัดไป โดย padding value ต้องเป็น 0x02 จำนวน 2 bytes โดย IV ที่จะทำให้ค่า byte สุดท้ายของ block เป็น 0x02 คือ 0x02 ^ 0x55 = 0x57 และทำการส่ง request โดยเปลี่ยนค่า IV ตามนี้

$ curl "http://127.0.0.1/thtutz/po_check.php?user=000000000000005721a7b2b00f85b47d"
Error: Invalid padding
$ curl "http://127.0.0.1/thtutz/po_check.php?user=000000000000015721a7b2b00f85b47d"
Error: Invalid padding
...
$ curl "http://127.0.0.1/thtutz/po_check.php?user=000000000000485721a7b2b00f85b47d"
Data OK : *5,*pG

ได้ค่า IV ที่ทำให้ plaintext ออกมาเป็น 0x02 คือ 0x48 ทำให้ได้ Intermediary Value เป็น 0x02 ^ 0x48 = 0x4a ตามรูปข้างล่าง ซึ่ง plaintext ของ byte นี้ก็คือ 0x4a ^ 0x49 = 0x03

และทำแบบนี้ไปเรื่อยๆ จนครบทั้ง block จะได้ plaintext ออกมา ซึ่งผมได้เขียน code เป็น python (po_decrypt.php) สำหรับการ decrypt นี้ ซึ่งเมื่อ run จะได้ตามนี้ (ซึ่งอาจต้อง ip กับ url ใน code ก่อน run นะครับ)

$ python po_decrypt.py 8 5f4649584544495621a7b2b00f85b47d
text[7]:  
text[6]:  
text[5]:  
text[4]: 5
text[3]: r
text[2]: e
text[1]: s
text[0]: u
finished
Data: user5   

ที่ผมกล่าวไปนั้นเป็นการ decrypt ข้อมูลเพียงแค่ block เดียว สำหรับการ decrypt ข้อมูลหลายๆ block เรามาดูค่าต่างๆ ของการ decrypt ข้อมูลจำนวน 2 block กันก่อนดีกว่า

จากรูปจะเห็นว่า IV ของ block ถัดไปก็คือ encrypted data ของ block ก่อนหน้า ดังนั้นวิธีการ decrypt ในแต่ละ block จะเหมือนกัน เพียงแค่เปลี่ยนค่า IV กับ encrypted data ของ block นั้นๆ และถ้าข้อมูลมีจำนวน block เยอะๆ เราก็สามารถที่จะทำ หลายๆ block พร้อมกันได้

Padding Oracle Attack เพื่อ encrypt ข้อมูล

จากหัวข้อการ decryption จะเห็นว่าเราสามารถเทคนิคนี้หา Intermediary Value จาก encrypted data ใดๆ ได้ ดังนั้นวิธีการ encrypt ข้อมูลจำนวน 1 block ก็คือสุ่ม encrypted data แล้วหา Intermediary Value (โดยปกติเราจะต้องทำขั้นตอนของการ decryption ก่อน ดังนั้นเราสามารถหยิบ encrypted data กับ Intermediary Value จาก block ไหนก็ได้มา) หลังจากนั้นนำมา xor กับ plaintext เพื่อหาค่า IV (แค่นี้แหละครับครับ ง่ายมั้ย xD)

สำหรับกรณีที่มีหลายๆ block เราจะต้องทำการหาจาก block สุดท้ายก่อน แล้วนำ IV ที่ได้มาเป็น encrypted data ใน block ก่อนหน้า มาดูตัวอย่างกันดีกว่า สมมติว่าผมต้องการ encrypt คำว่า administrator โดยกำหนดให้ encrypted data ใน block สุดท้ายเป็น 0x01 0x02 ... 0x08 เริ่มต้นเราจะตั้งตารางเป็นดังนี้

จะเห็นว่า เราจะต้องจัดเรียงข้อมูลของเราให้ตรง block พร้อมทั้งมี padding ด้วย และทำการหา Intermediary Value กับ IV ของ Block ที่ 2 ซึ่งได้ผมตามรูป

เมื่อได้ค่า IV ใน block ที่ 2 ก็นำมาเป็น encrypted data ใน block ที่ 1 โดยผมได้เขียนโปรแกรมไว้แล้ว (po_encrypt.py) ซึ่งเมื่อ run จะได้ตามนี้

$ python po_encrypt.py 8 administrator
...
Encrypted Data (Hex): 8fde9c453db873f81498a22ea1caa3460102030405060708

จบแล้วนะครับ สำหรับ concept หลักของ Padding Oracle Attacks ทีเหลือคือการประยุกต์ใช้กับ application จริง ซึ่งไม่ง่ายเหมือนในตัวอย่างผมหรอกนะครับ แต่ถ้าเข้าใจตรงนี้แล้ว ผมว่าไม่ยากมากที่จะทำความเข้าใจกับ tool สำหรับเทคนิคนี้

Reference:
- http://netifera.com/research/poet/PaddingOracleBHEU10.pdf
- http://www.gdssecurity.com/l/b/2010/09/14/automated-padding-oracle-attacks-with-padbuster/