การวิเคราะห์ความแตกต่างของ SPN

อ้างอิง : บทช่วยสอนโดย HM Heys

หากเราพบความแตกต่างที่มีความน่าจะเป็นที่ไม่สำคัญสำหรับ n-1 รอบสำหรับโครงสร้าง SPN n รอบ เราก็สามารถกู้คืนบิตของคีย์ย่อยของรอบสุดท้ายได้

จะเกิดอะไรขึ้นเมื่อเราจัดการเส้นทางที่แตกต่างซึ่งมีความน่าจะเป็นที่ไม่สำคัญเพียงไม่กี่รอบ R โดยที่ R < n-1 เราจะดำเนินการอย่างไรในกรณีดังกล่าวเพื่อทำการโจมตีเพื่อกู้คืนคีย์

ฉันจะขอบคุณคำแนะนำบางอย่างที่จะคิดเกี่ยวกับเรื่องนี้

การศึกษาด้วยตนเอง

ฉันไม่เห็นด้วยกับคำตอบของ @kodlu ในการวิเคราะห์ดิฟเฟอเรนเชียลแบบคลาสสิก เราไม่จ่าย "ความน่าจะเป็น" สำหรับรอบสุดท้าย แต่เราจ่ายสำหรับการแจกแจงของคีย์บิตที่เกี่ยวข้อง กล่าวอีกนัยหนึ่ง การถอดรหัสไม่ใช่สถิติ

และนั่นคือสิ่งที่ทำให้การใช้งานมีขนาดเล็กลง $R$ ยาก: คีย์เดา Ciphers มีการแพร่กระจายที่ดีและในแต่ละรอบพิเศษเพื่อถอดรหัสบางส่วนในตอนท้าย จำนวนของคีย์บิตที่จำเป็นในการเดาเพื่อตรวจสอบความแตกต่างของเอาต์พุต (ตอนนี้ ตามสถิติแล้ว ต่อการเดาคีย์แต่ละครั้ง) จะเพิ่มขึ้นอย่างรวดเร็วมาก

นอกจากนี้ รูปร่าง ความแตกต่างของเอาต์พุตมีความสำคัญเช่นกัน: หากมีน้ำหนักสูง (เปิดใช้งาน S-box จำนวนมากในรอบที่ตามมา) จำเป็นต้องเดาบิตคีย์เพิ่มเติม

โปรดทราบว่า $R$ และจำนวนของคีย์บิตที่ต้องเดานั้นอยู่ในการแลกเปลี่ยน: น้อยกว่า $R$ เพิ่มความน่าจะเป็นเชิงอนุพันธ์ แต่ยังเพิ่มจำนวนคีย์บิตที่ต้องเดาด้วย โดยปกติแล้ว การได้รับค่าความน่าจะเป็นเชิงอนุพันธ์โดยเริ่มจาก $R=n-1$ ถึง $R=n-2$ ไม่สมดุลกับการเพิ่มความซับซ้อนในการเดาคีย์เมื่อถอดรหัสบางส่วน 2 รอบแทนที่จะเป็น 1 รอบ

เหตุผล $R=n-1$ (หรือ $R=1,$ นำไปใช้กับการแมปการถอดรหัส) ที่ใช้มีดังต่อไปนี้ การประมาณเชิงอนุพันธ์ส่วนบุคคลทั้งหมดตลอดจนเส้นทางเชิงอนุพันธ์ซึ่งถูกเลือกไว้เหนือ $R$ ผลผลิตรอบ ทางสถิติ ความสัมพันธ์

อย่างไรก็ตาม ตอนนี้เราสามารถใช้เอาต์พุตไซเฟอร์เท็กซ์ รัน Sboxes ในรอบที่แล้วแบบย้อนกลับ และ มีเงื่อนไขในการเดาแต่ละครั้ง สำหรับแป้นกลม XORed ลงในอินพุตของ $n^{th}$ รอบ Sboxes มี การคาดเดาที่ไม่สุ่มและแน่นอน สำหรับผลลัพธ์ของ Sboxes เป้าหมายจากรอบ $n-1.$ ซึ่งหมายความว่าสามารถทำการทดลองทางสถิติที่เชื่อถือได้ และคำนวณความน่าจะเป็นเชิงอนุพันธ์เชิงประจักษ์ของผลต่างอินพุตเอาต์พุตที่เลือกได้อย่างน่าเชื่อถือ

ในขั้นตอนนี้ เมื่อได้รับคู่ P/C ที่เพียงพอ การคาดเดาหลักที่ส่งผลให้เกิดความน่าจะเป็นเชิงประจักษ์ที่ใหญ่ที่สุดจะได้รับการประกาศให้เป็นการเดาหลักที่น่าจะเป็นไปได้มากที่สุด

ดูคำตอบของฉันสำหรับคำถามต่อไปนี้สำหรับรายละเอียดเพิ่มเติม

บทช่วยสอนการเข้ารหัสเชิงอนุพันธ์ของ Howard M. Heys

แก้ไข: ขอบคุณ @fractalice ที่จับส่วนสุดท้ายของคำตอบของฉันที่เลอะเทอะ แน่นอนว่าความซับซ้อนในการคำนวณของการคาดเดาคีย์ของ Sbox ที่ "ใช้งานอยู่" ในรอบที่แล้วนั้นมีความสำคัญ ดังนั้น ความน่าจะเป็นเชิงอนุพันธ์ของ $\epsilon$ ของ $n-1$ ลักษณะความแตกต่างหมายความว่าคุณต้องใช้อย่างคร่าวๆ $c/\epsilon$ P/C จับคู่สำหรับคุณลักษณะที่จะเป็นลักษณะเด่นในเชิงประจักษ์ และถ้ามี $k$ Sboxes ที่ใช้งานในรอบที่แล้วคุณจะต้องลอง $2^{4k}$ (เนื่องจาก Sboxes กว้าง 4 บิต) คีย์เดาในขณะที่พยายามตัดสินใจว่าคีย์เดาใดที่เป็นไปได้มากที่สุด