การวิเคราะห์ความแตกต่าง (Differential Cryptanalysis)
- ผู้เสนอ
- Eli Biham
- ปี
- 1990
- ประเภท
- statistical attack on block ciphers
- กลุ่มวิธี
- Cryptanalytic technique
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การวิเคราะห์ความแตกต่าง (Differential cryptanalysis) เป็นเทคนิคการโจมตีแบบสถิติบนรหัสลับแบบบล็อกสมมาตร (symmetric block ciphers) ที่วิเคราะห์ความแตกต่างของข้อมูลนำเข้าและผลลัพธ์เพื่อกู้คืนคีย์ลับ การวิเคราะห์ความแตกต่างซึ่งถูกนำเสนอโดย Eli Biham และ Adi Shamir ในปี 1990 เป็นการโจมตีแบบใช้งานได้จริงครั้งแรกต่อ DES ที่มีประสิทธิภาพเหนือกว่าการค้นหาแบบ brute force เทคนิคนี้ใช้ประโยชน์จากคุณสมบัติที่ไม่สุ่มของการแปลงรหัสลับโดยการศึกษาว่าการเปลี่ยนแปลงเล็กน้อยในข้อความธรรมดา (plaintext) แพร่กระจายผ่านรอบการเข้ารหัส (cipher rounds) อย่างไร การวิเคราะห์ความแตกต่างได้กำหนดรูปแบบการออกแบบรหัสลับมานานกว่าสามทศวรรษ
แนวคิดเบื้องหลังวิธีการ
การวิเคราะห์ความแตกต่างทำงานโดยการศึกษาคู่ข้อความธรรมดา (plaintext pairs) ที่มีความแตกต่างเฉพาะและสังเกตว่าความแตกต่างเหล่านี้มีวิวัฒนาการอย่างไรผ่านรอบการเข้ารหัส หากความแตกต่างบางอย่างมีแนวโน้มที่จะแพร่กระจายในลักษณะเฉพาะ ความไม่สุ่มนี้สามารถนำมาใช้ประโยชน์เพื่อกู้คืนบิตคีย์ได้ ผู้โจมตีเลือกคู่ข้อความธรรมดาที่ออกแบบมาเพื่อเพิ่มความน่าจะเป็นของความแตกต่างของผลลัพธ์ที่มีประโยชน์ให้สูงสุด จากนั้นจึงใช้ความแตกต่างของผลลัพธ์ที่สังเกตได้เพื่อจำกัดวงของคีย์ที่เป็นไปได้
ประวัติศาสตร์
การวิเคราะห์ความแตกต่างถูกนำเสนอในปี 1990 โดย Biham และ Shamir ซึ่งเปิดเผยการโจมตีที่ใช้งานได้จริงต่อ DES โดยต้องการการดำเนินการ 2^47 ครั้ง และคู่ข้อความธรรมดา-ข้อความเข้ารหัส 2^47 คู่ การโจมตีแสดงให้เห็นว่า DES อ่อนแอกว่าที่คาดไว้ และกระตุ้นให้เกิดการยอมรับเกณฑ์การออกแบบที่เข้มงวดมากขึ้น AES และรหัสลับสมัยใหม่อื่นๆ ได้รับการออกแบบโดยคำนึงถึงความต้านทานต่อความแตกต่างโดยเฉพาะ ซึ่งเป็นการยกระดับมาตรฐานสำหรับคลาสการโจมตีนี้อย่างมาก
ควรใช้เมื่อใด
การวิเคราะห์ความแตกต่างถูกใช้ในการวิเคราะห์รหัสลับเพื่อประเมินความแข็งแกร่งของรหัสลับ ผู้ออกแบบรหัสลับใช้การวิเคราะห์ความแตกต่างเพื่อตรวจสอบความต้านทานต่อการโจมตีแบบความแตกต่าง รหัสลับสมัยใหม่รวมเอาการหมุนรอบ (rounds) และการแปลง (transformations) ที่ออกแบบมาโดยเฉพาะเพื่อต้านทานการวิเคราะห์ความแตกต่าง
ข้อจำกัดและข้อควรพิจารณา
- ต้องการคู่ข้อความธรรมดา-ข้อความเข้ารหัสจำนวนมาก ซึ่งมักไม่สามารถใช้งานได้จริง
- รหัสลับสมัยใหม่ (AES) ได้รับการออกแบบอย่างระมัดระวังเพื่อต้านทานการวิเคราะห์ความแตกต่าง
- ต้นทุนการคำนวณในการดำเนินการโจมตีอาจสูงเกินไป
- ประสิทธิภาพขึ้นอยู่กับการค้นพบคุณลักษณะความแตกต่างที่แข็งแกร่ง ซึ่งจะยากขึ้นสำหรับจำนวนรอบที่ยาวขึ้น
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- การโจมตีที่ใช้งานได้จริงต่อรหัสลับบางชนิด โดยต้องการการดำเนินการน้อยกว่า 2^64 (เหนือกว่า brute force สำหรับคีย์ 64 บิต)
- รากฐานทางคณิตศาสตร์ที่เข้าใจดี ช่วยให้สามารถวิเคราะห์ความปลอดภัยของรหัสลับได้อย่างเข้มงวด
- ชี้นำการออกแบบรหัสลับ ความต้านทานต่อการวิเคราะห์ความแตกต่างเป็นเป้าหมายการออกแบบมาตรฐาน
- เปิดเผยจุดอ่อนเชิงโครงสร้างในการออกแบบรหัสลับที่เทคนิคอื่นอาจมองข้าม
การประยุกต์ใช้
- การวิเคราะห์รหัสลับของรหัสลับแบบบล็อกในการวิจัยการเข้ารหัสลับและสิ่งพิมพ์ทางวิชาการ
- การออกแบบและการประเมินรหัสลับ เพื่อให้แน่ใจว่ามีจำนวนรอบและการแปลงที่เพียงพอต่อการโจมตีแบบความแตกต่าง
- การตรวจสอบความถูกต้องของการเข้ารหัสลับในหน่วยงานกำหนดมาตรฐาน (NIST, ETSI) ซึ่งต้องการการวิเคราะห์ความต้านทาน
- การประเมินความปลอดภัยของรหัสลับรุ่นเก่า เพื่อระบุจุดอ่อนและแจ้งการตัดสินใจปลดประจำการ
วิธีการทำงาน
วิธีการทำงาน
ระบุคุณลักษณะความแตกต่าง (differential characteristics): ลำดับของความแตกต่างผ่านรอบการเข้ารหัสที่มีความน่าจะเป็นสูงที่จะเกิดขึ้นสำหรับคีย์ใดๆ
ประมาณจำนวนคู่ข้อความธรรมดาที่จำเป็นในการแยกแยะรหัสลับออกจากข้อมูลสุ่มและกู้คืนบิตคีย์
ใช้คู่ข้อความธรรมดา-ข้อความเข้ารหัส (plaintext-ciphertext pairs) ที่แสดงความแตกต่างที่ต้องการเพื่อทดสอบค่าคีย์ที่คาดเดา กำจัดคีย์ที่ไม่สอดคล้องกับการสังเกต
วิเคราะห์ต้นทุนการคำนวณและปริมาณข้อมูลที่ต้องการ การโจมตีที่ใช้งานได้จริงจะเปรียบเทียบสิ่งเหล่านี้กับการค้นหาคีย์แบบ brute force
ข้อผิดพลาดที่พบบ่อย
- การประเมินความยากในการค้นหาคุณลักษณะสำหรับรหัสลับสมัยใหม่ต่ำเกินไป
- การประเมินความเป็นไปได้ของการโจมตีที่ใช้งานได้จริงสูงเกินไปเมื่อข้อกำหนดข้อมูลทางทฤษฎีมีขนาดใหญ่เกินกว่าจะใช้งานได้จริง
- การสันนิษฐานว่าความปลอดภัยต้องการเพียงความต้านทานต่อการวิเคราะห์ความแตกต่างเท่านั้น ต้องพิจารณาเวกเตอร์การโจมตีหลายอย่าง
คำถามที่พบบ่อย
คุณลักษณะความแตกต่าง (differential characteristic) คืออะไร?
คุณลักษณะความแตกต่างคือลำดับของความแตกต่างของข้อมูลนำเข้าและผลลัพธ์ในแต่ละรอบการเข้ารหัสที่มีความน่าจะเป็นที่ระบุ การค้นหาคุณลักษณะที่มีความน่าจะเป็นสูงเป็นกุญแจสำคัญในการดำเนินการโจมตีแบบความแตกต่างที่ประสบความสำเร็จ
AES ต้านทานการวิเคราะห์ความแตกต่างได้อย่างไร?
AES ใช้การแปลง (การแทนที่และการผสม) ที่ทำให้แน่ใจว่าความแตกต่างของข้อมูลนำเข้าเพียงหนึ่งบิตจะแพร่กระจายไปยังบิตผลลัพธ์อย่างน้อย 25 บิตหลังจากเพียงสามรอบ การแพร่กระจายอย่างรวดเร็วนี้ทำให้การโจมตีแบบความแตกต่างเป็นไปไม่ได้
การวิเคราะห์ความแตกต่างสามารถถอดรหัสลับสมัยใหม่ได้หรือไม่?
ในทางปฏิบัติไม่ได้ รหัสลับสมัยใหม่เช่น AES ต้องการปริมาณข้อความธรรมดาและทรัพยากรการคำนวณจำนวนมหาศาล ซึ่งเกินกว่าการค้นหาคีย์แบบ brute force อย่างมาก
การวิเคราะห์ความแตกต่างเหมือนกับการวิเคราะห์เชิงเส้น (linear cryptanalysis) หรือไม่?
ไม่ การวิเคราะห์ความแตกต่างศึกษาความแตกต่างของข้อมูลนำเข้า-ผลลัพธ์ ในขณะที่การวิเคราะห์เชิงเส้นศึกษาการประมาณค่าเชิงเส้น ทั้งสองเป็นคลาสการโจมตีที่สำคัญ รหัสลับต้องต้านทานทั้งสองอย่าง
ฉันจะประเมินความต้านทานของรหัสลับต่อการโจมตีแบบความแตกต่างได้อย่างไร?
วิเคราะห์ S-boxes และการแปลงรอบของรหัสลับสำหรับความน่าจะเป็นความแตกต่างสูงสุด ใช้เครื่องมืออัตโนมัติและการวิเคราะห์ด้วยมือเพื่อค้นหาคุณลักษณะ เผยแพร่ผลลัพธ์ในแหล่งที่ผ่านการตรวจสอบโดยผู้เชี่ยวชาญ (peer-reviewed venues) เพื่อการตรวจสอบโดยชุมชน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Biham, E., & Shamir, A. (1990). Differential cryptanalysis of DES-like cryptosystems. In Advances in Cryptology - CRYPTO 1990, LNCS 537, pp. 2-21.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วKnudsen, L. R. (2005). Block ciphers and public key cryptosystems. In Information Security and Cryptography, pp. 1-25.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว