Skip to content
กลับไปยังผลการค้นหา

การวิเคราะห์ความแตกต่าง (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) ซึ่งต้องการการวิเคราะห์ความต้านทาน
  • การประเมินความปลอดภัยของรหัสลับรุ่นเก่า เพื่อระบุจุดอ่อนและแจ้งการตัดสินใจปลดประจำการ

วิธีการทำงาน

วิธีการทำงาน

1

ระบุคุณลักษณะความแตกต่าง (differential characteristics): ลำดับของความแตกต่างผ่านรอบการเข้ารหัสที่มีความน่าจะเป็นสูงที่จะเกิดขึ้นสำหรับคีย์ใดๆ

2

ประมาณจำนวนคู่ข้อความธรรมดาที่จำเป็นในการแยกแยะรหัสลับออกจากข้อมูลสุ่มและกู้คืนบิตคีย์

3

ใช้คู่ข้อความธรรมดา-ข้อความเข้ารหัส (plaintext-ciphertext pairs) ที่แสดงความแตกต่างที่ต้องการเพื่อทดสอบค่าคีย์ที่คาดเดา กำจัดคีย์ที่ไม่สอดคล้องกับการสังเกต

4

วิเคราะห์ต้นทุนการคำนวณและปริมาณข้อมูลที่ต้องการ การโจมตีที่ใช้งานได้จริงจะเปรียบเทียบสิ่งเหล่านี้กับการค้นหาคีย์แบบ brute force

ข้อผิดพลาดที่พบบ่อย

  • การประเมินความยากในการค้นหาคุณลักษณะสำหรับรหัสลับสมัยใหม่ต่ำเกินไป
  • การประเมินความเป็นไปได้ของการโจมตีที่ใช้งานได้จริงสูงเกินไปเมื่อข้อกำหนดข้อมูลทางทฤษฎีมีขนาดใหญ่เกินกว่าจะใช้งานได้จริง
  • การสันนิษฐานว่าความปลอดภัยต้องการเพียงความต้านทานต่อการวิเคราะห์ความแตกต่างเท่านั้น ต้องพิจารณาเวกเตอร์การโจมตีหลายอย่าง

คำถามที่พบบ่อย

คุณลักษณะความแตกต่าง (differential characteristic) คืออะไร?

คุณลักษณะความแตกต่างคือลำดับของความแตกต่างของข้อมูลนำเข้าและผลลัพธ์ในแต่ละรอบการเข้ารหัสที่มีความน่าจะเป็นที่ระบุ การค้นหาคุณลักษณะที่มีความน่าจะเป็นสูงเป็นกุญแจสำคัญในการดำเนินการโจมตีแบบความแตกต่างที่ประสบความสำเร็จ

AES ต้านทานการวิเคราะห์ความแตกต่างได้อย่างไร?

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

การวิเคราะห์ความแตกต่างสามารถถอดรหัสลับสมัยใหม่ได้หรือไม่?

ในทางปฏิบัติไม่ได้ รหัสลับสมัยใหม่เช่น AES ต้องการปริมาณข้อความธรรมดาและทรัพยากรการคำนวณจำนวนมหาศาล ซึ่งเกินกว่าการค้นหาคีย์แบบ brute force อย่างมาก

การวิเคราะห์ความแตกต่างเหมือนกับการวิเคราะห์เชิงเส้น (linear cryptanalysis) หรือไม่?

ไม่ การวิเคราะห์ความแตกต่างศึกษาความแตกต่างของข้อมูลนำเข้า-ผลลัพธ์ ในขณะที่การวิเคราะห์เชิงเส้นศึกษาการประมาณค่าเชิงเส้น ทั้งสองเป็นคลาสการโจมตีที่สำคัญ รหัสลับต้องต้านทานทั้งสองอย่าง

ฉันจะประเมินความต้านทานของรหัสลับต่อการโจมตีแบบความแตกต่างได้อย่างไร?

วิเคราะห์ S-boxes และการแปลงรอบของรหัสลับสำหรับความน่าจะเป็นความแตกต่างสูงสุด ใช้เครื่องมืออัตโนมัติและการวิเคราะห์ด้วยมือเพื่อค้นหาคุณลักษณะ เผยแพร่ผลลัพธ์ในแหล่งที่ผ่านการตรวจสอบโดยผู้เชี่ยวชาญ (peer-reviewed venues) เพื่อการตรวจสอบโดยชุมชน

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Biham, E., & Shamir, A. (1990). Differential cryptanalysis of DES-like cryptosystems. In Advances in Cryptology - CRYPTO 1990, LNCS 537, pp. 2-21.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Knudsen, L. R. (2005). Block ciphers and public key cryptosystems. In Information Security and Cryptography, pp. 1-25.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว