พื้นฐานการวิเคราะห์การเข้ารหัสเชิงอนุพันธ์

การวิเคราะห์รหัสลับเชิงผลต่าง (Biham และ Shamir, 1990) เป็นการโจมตีด้วยข้อความธรรมดาที่เลือก ซึ่งวิเคราะห์ว่าผลต่างในคู่ข้อความธรรมดาแพร่ผ่านรหัสลับอย่างไร โดยค้นหาผลต่างอินพุตที่ทำให้เกิดผลต่างเอาต์พุตที่คาดการณ์ได้ด้วยความน่าจะเป็นสูง ผู้โจมตีสามารถกู้คืนบิตของคีย์ได้ในเชิงสถิติ

สำหรับรหัสลับที่ใช้ XOR: ผลต่าง ΔX = X XOR X' สำหรับรหัสลับที่ใช้การบวก: ผลต่าง ΔX = X - X' mod 2^n ผลต่างแบบ XOR พบบ่อยที่สุด เพราะ XOR สลับที่ได้กับการเข้ารหัสด้วยคีย์แบบ XOR (ผลจากตารางคีย์จะหักล้างกันในคู่เชิงผลต่าง)

คู่เชิงผลต่าง (P, P') มีผลต่างอินพุต ΔP = P XOR P' หลังการเข้ารหัส จะได้ (C, C') ซึ่งมีผลต่างเอาต์พุต ΔC = C XOR C' ผลต่างที่มีประโยชน์คือ ΔP → ΔC ซึ่งเกิดขึ้นด้วยความน่าจะเป็นสูง p — หมายความว่าคู่ (P, P') จำนวนมากที่มีผลต่าง ΔP จะให้ผลต่างเอาต์พุต ΔC

DDT (ตารางการกระจายผลต่าง) นับจำนวนอินพุต x ที่ทำให้ S(x) XOR S(x XOR Δx) = Δy สำหรับผลต่างอินพุต Δx และผลต่างเอาต์พุต Δy แต่ละคู่ หารด้วย 2^n เพื่อให้ได้ความน่าจะเป็น กล่อง S ที่ดีมีค่า DDT สูงสุดเป็น 2 (ความน่าจะเป็น 1/2^{n-1}) จึงไม่มีผลต่างที่เด่นชัด

สำหรับรหัสลับแบบบล็อกที่มี r รอบ ให้ค้นหาลำดับ ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} โดยการเปลี่ยนผ่านในแต่ละรอบมีความน่าจะเป็นที่ทราบค่า คูณความน่าจะเป็นของทุกรอบเข้าด้วยกัน: ความน่าจะเป็นรวม p = p1 * p2 * ... * p_{r-1} การโจมตีใช้คู่จำนวน 2/p เพื่อกู้คืนคีย์ของรอบสุดท้าย

เมื่อมีผลต่างของ r-1 รอบที่มีความน่าจะเป็นสูง ให้รวบรวมคู่ข้อความธรรมดา N = 2/p คู่ สำหรับคีย์รอบสุดท้ายที่เป็นไปได้แต่ละค่า K' ให้ถอดรหัสข้อความเข้ารหัสทั้งสองเป็นเวลาหนึ่งรอบ ใช้ XOR กับผลลัพธ์ แล้วตรวจสอบว่าผลต่างตรงกับ ΔU_{r-1} หรือไม่ K' ที่ถูกต้องจะตรงกันประมาณ N/2 ครั้ง ส่วนคีย์ที่ผิดจะตรงกันประมาณ N/2^{bit_size} ครั้ง

กล่อง S ของ AES คืออินเวอร์สการคูณเหนือ GF(2^8) ตามด้วยการแปลงแอฟฟีน ค่า DDT สูงสุดคือ 4 จากทั้งหมด 256 ทำให้ความน่าจะเป็นเชิงผลต่างต่อกล่อง S ไม่เกิน 4/256 = 1/64 AES มีกล่อง S 4 กล่องต่อรอบ แต่การออกแบบ Wide Trail ทำให้เส้นทางเชิงผลต่างเต็มรูปแบบมีความน่าจะเป็นต่ำกว่า 2^{-100}

การออกแบบ Wide Trail ของ Joan Daemen (ใช้ใน AES/Rijndael): กำหนดจำนวนกิ่ง B ของ MixColumns ผลต่างที่ไม่เป็นศูนย์ทุกเส้นทางผ่านหนึ่งรอบจะเปิดใช้กล่อง S อย่างน้อย B กล่อง 4 รอบ × กล่อง S 4 กล่องต่อรอบ รับประกันว่าจะมีกล่อง S ที่ทำงานอย่างน้อย 25 กล่อง → ความน่าจะเป็น < 2^{-100}

ผลต่างแบบตัดทอนจะระบุเพียงบางส่วนของผลต่าง เช่น ระบุเฉพาะว่าคอลัมน์ใดทำงานอยู่ ไม่ได้ระบุค่าผลต่างที่แน่นอน ทำให้โจมตีรหัสลับได้หลายรอบขึ้นเมื่อผลต่างแบบเต็มอ่อนเกินไป วิธีนี้ใช้กับ AES ที่ลดจำนวนรอบ, SERPENT และรหัสลับ SPN อื่น ๆ

ผลต่างที่เป็นไปไม่ได้คือคู่ (ΔP, ΔC) ที่ไม่สามารถเกิดขึ้นได้ไม่ว่าจะใช้คีย์ใดก็ตาม คีย์ใดก็ตามที่ทำให้คู่ที่สังเกตได้ (P, P') ซึ่งมีผลต่างนี้เกิดขึ้น จะถูกตัดออก เมื่อรวบรวมคู่ได้มากพอ คีย์ที่ผิดทั้งหมดจะถูกตัดออก เหลือคีย์ที่ถูกต้อง

การโจมตีแบบบูมเมอแรง (Wagner, 1999) รวมผลต่างสั้นสองชุดเข้าด้วยกันเป็นการโจมตีแบบเลือกข้อความธรรมดาและข้อความเข้ารหัสอย่างปรับตัวได้ โดยแยกรหัสลับออกเป็นสองครึ่ง แต่ละครึ่งมีผลต่างสั้นที่มีความน่าจะเป็นสูง ทำให้โจมตีรหัสลับได้หลายรอบกว่าที่ผลต่างชุดเดียวจะรองรับได้

DDT (ตารางการกระจายผลต่าง) มีจุดประสงค์อะไรในการวิเคราะห์รหัสลับ

การวิเคราะห์รหัสลับเชิงผลต่างใช้ประโยชน์จากการแพร่ของผลต่างอินพุตไปยังเอาต์พุตที่มีความน่าจะเป็นสูง AES ต้านทานการโจมตีนี้ด้วยกล่อง S ที่เหมาะสมที่สุดตาม DDT และการออกแบบ Wide Trail บทถัดไป: การวิเคราะห์รหัสลับเชิงเส้นและตารางการประมาณค่า