CBC Bit Flipping

encryption algorithm โดยทั่วไป จะทำการเข้ารหัสเป็น block เช่น AES จะมี block size เป็น 128 bits (16 bytes) ซึ่งถ้าเรานำ key มาเข้ารหัสข้อมูลทีละ block ก็จะเรียก mode นี้ว่า ECB (Electronic CodeBook) ตามรูปข้างล่าง (รูปจาก http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation)

รูปข้างบนสำหรับ encryption และรูปข้างล่างสำหรับ decryption ปัญหาของ mode นี้ไม่ขอกล่าวในนี้ เพราะว่าน่าจะมีอยู่แล้วในหนังสือ cryptography ทั่วไป

สิ่งที่ผมต้องการจะพูดถึงคือ CBC (Cipher Block Chaining) mode ซึ่งมีการเข้ารหัสตามภาพข้างล่าง (รูปจาก) http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation)

IV (Initialization Vector) คือค่าเริ่มต้น โดยปกติจะได้จากการ random ขนาดเท่ากับ block operation ของ algorithm นั้นๆและเพื่อให้ง่ายต่อการอธิบายต่อ ผมจะขอเรียกผลลัพธ์จากการ decryption ที่ยังไม่ทำ XOR ว่า "Intermediate value"

ใน mode นี้ ก่อนที่จะนำข้อมูลไปเข้ารหัส จะไปทำ XOR กับผลลัพธ์จากการเข้ารหัสของ block ก่อนหน้า ส่วน block แรกจะทำการ XOR กับ IV ส่วนการทำ decryption ก็จะทำในทางกลับกัน ตามรูปข้างบน

เมื่อเข้าใจ CBC mode กันแล้ว คราวนี้ก็มาถึง attack หนึ่งเพื่อทำ bit flipping ซึ่ง attack ที่ขั้นตอนการทำ XOR โดย XOR มีคุณสมบัติดังนี้ (สำหรับคนที่ยังไม่รู้)

A xor 0 = A
A xor 1 = not A
ถ้า A xor B = C แล้ว B xor C = A, C xor A = B

จากรูปการ decryption ของ CBC mode ถ้าเราสนใจใน block ที่ 3 จะเห็นว่า intermediate value ของ block ที่ 3 จะทำการ XOR กับ encrypted block ที่ 2 ได้ผลลัพธ์ออกมา ดังนั้นถ้าเราแก้ค่าใน encrypted block ที่ 2 ไป 1 bit ผลของการ decryption ใน block ที่ 3 ก็จะเปลี่ยนไป 1 bit แต่ผลของการ decryption ใน block ที่ 2 จะเปลี่ยนแปลงทั้งหมด ตามรูปข้างล่าง

attack นี้จะทำได้ เราต้องรู้ว่า plaintext บางส่วน(หรือทั้งหมด) แล้วเราต้องการเปลี่ยนค่าบ้างค่า และที่สำคัญข้อมูลใน block ที่ถูกเปลี่ยนแปลงทั้งหมดนั้น เป็นเพียงข้อมูล ที่ไม่ผลต่อการทำงานของโปรแกรมที่อ่านข้อมูล

ถ้าเรารู้ข้อมูล plaintext และตำแหน่งทั้งหมด เราสามารถที่จะเปลี่ยนข้อมูลได้ทั้ง block เนื่องจากเราสามารถหา intermediate value ของ block ที่เราจะเปลี่ยนได้จากการ XOR กันของ plaintext กับ encrypted block ก่อนหน้า และนำ plaintext ที่เราต้องการจะให้เป็นไป XOR กับ intermediate value ก็จะได้ encrypted block ก่อนหน้าที่เราต้องเปลี่ยน

ถึงแม้ว่า attack นี้จะมีมานานแล้ว แต่ถือว่าเป็นตัวอย่างที่ดีว่า การทำ encryption ช่วยได้เฉพาะเรื่องความลับของข้อมูล (Confidential) แต่ไม่ได้ป้องกันเรื่อง ความถูกต้องของข้อมูล (Integrity)