การก่อสร้าง S-Box ในปัจจุบัน

ฉันกำลังดำเนินการเกี่ยวกับการติดตั้งฮาร์ดแวร์ (พร้อม verilog) ของ PRESENT-80 เพื่อวัตถุประสงค์ในการวิจัย เนื่องจากเป้าหมายของเราในการเสริมความปลอดภัยของ PRESENT-80 ด้วยการปิดบังและการตรวจจับข้อผิดพลาด ฉันจำเป็นต้องเข้าใจว่า S-Box ได้รับการออกแบบมาอย่างไร

ใน ปัจจุบัน: Block Cipher ที่มีน้ำหนักเบาเป็นพิเศษ S-Box 4x4 ระบุไว้ง่ายๆ เป็นตารางค้นหา:

มีใครเข้าใจ/รู้ลึกเกี่ยวกับ PRESENT และสามารถอธิบายให้ฉันฟังได้ว่า S-Box ออกแบบมาอย่างไร

เหตุผลในการออกแบบ S-box ระบุไว้ในหัวข้อ 4.3 ของบทความ ฉันจะพยายามขยายเหตุผล

S-box ประเภทที่แย่ที่สุดคือฟังก์ชันเชิงเส้น นั่นคือฟังก์ชันที่ทุกบิตของเอาต์พุตเป็นเพียง XOR ของอินพุตบางบิต เนื่องจากส่วนที่เหลือของฟังก์ชันรอบปัจจุบันเกี่ยวข้องกับการย้ายบิตไปรอบๆ และการ XORing ของคีย์กลม S-box เชิงเส้นจะนำไปสู่รหัสที่แต่ละบิตของเอาต์พุตคือ XOR ของบิตอินพุตและบิตคีย์กลมการรวบรวมอินพุตและเอาต์พุตที่ตรงกันจำนวนหนึ่งจะทำให้สามารถแบ่งรหัสได้ง่ายๆ โดยใช้พีชคณิตเชิงเส้น

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

การวิเคราะห์เชิงเส้น

มันคงไม่ดีถ้า XOR คอลเลกชั่นบิตอินพุตและคีย์บิตจำนวนหนึ่งมีค่าเท่ากับ XOR ของคอลเลกชั่นเอาต์พุตบิตหนึ่งอย่างมีนัยสำคัญมากกว่าครึ่งหนึ่งของเวลา รายละเอียดที่แน่นอนของวิธีเปลี่ยนสิ่งนี้ให้กลายเป็นการโจมตีนั้นมีความยาว แต่มันจะเกี่ยวข้องกับการรวบรวมคู่อินพุต/เอาต์พุตที่ตรงกันจำนวนมาก คำนวณ XOR ที่เกี่ยวข้อง และดูว่าส่วนใหญ่ตรงกันหรือไม่ตรงกัน สิ่งนี้จะให้ข้อมูลเกี่ยวกับบิตคีย์แบบกลม เพื่อหลีกเลี่ยงสถานการณ์นี้ cryptographers มองหา S-box ซึ่งสำหรับชุดย่อยของบิตอินพุตและชุดย่อยของบิตเอาต์พุต XOR จะเท่ากันเพียงครึ่งเดียว (หรือใกล้เคียงที่สุด) เกณฑ์ 3 ของกระดาษระบุว่าสำหรับกล่อง S-ปัจจุบัน XOR จะเท่ากันอย่างน้อย 4 ครั้งจาก 16 ครั้ง และมากที่สุด 12 ครั้งจาก 16 ครั้ง สิ่งต่างๆ อาจแย่กว่านี้ถ้าชุดย่อยที่เราเลือกในแต่ละกรณีเป็นบิตเดียว ในกรณีนี้ เราสามารถเชื่อมโยงอินพุตบิตเดียวกับเอาต์พุตบิตเดียวโดยการติดตามผ่าน S-box เพียงตัวเดียวในแต่ละรอบ สิ่งนี้กระตุ้นเกณฑ์ 4 ซึ่งระบุว่าเมื่อเซ็ตย่อยประกอบด้วยบิตเดียว พวกมันจับคู่ 6 ครั้งจาก 16 ครั้งหรือ 10 ครั้งจาก 16 ครั้งพอดี

การเข้ารหัสเชิงอนุพันธ์

อีกวิธีในการแสดงคุณสมบัติเชิงเส้นของรหัสคือการบอกว่าสำหรับอินพุตทั้งหมด $a$ และ $ข$ เรามี $\mathrm{Enc}(a\oplus b)=\mathrm{Enc}(a)\oplus\mathrm{Enc}(b)$. อีกครั้ง หากคุณสมบัติที่คล้ายกันปรากฏขึ้นในรหัสของเราในสัดส่วนที่สำคัญของเวลา ก็จะสามารถใช้ประโยชน์ได้ นักเข้ารหัสจึงพยายามออกแบบรหัสลับสำหรับความแตกต่างที่แน่นอนของอินพุต $\เดลต้า x$ และผลต่างคงที่ของเอาต์พุต $\เดลต้า y$ สมการ $\mathrm{Enc}(x\oplus\Delta x)=\mathrm{Enc}(x)\oplus\Delta y$ วิธีแก้ปัญหาเพียงวิธีเดียว $x$ (ประมาณสองวิธีแก้ปัญหาครึ่งหนึ่งของเวลาและไม่มีวิธีแก้ปัญหาครึ่งหนึ่งของเวลา) อีกครั้ง เนื่องจาก S-box เป็นส่วนเดียวที่ไม่ใช่เชิงเส้นของรหัส ดังนั้นสิ่งนี้จึงกลายเป็นข้อกำหนดที่ความแตกต่างของอินพุตและเอาต์พุตใน S-box ควรมีความสัมพันธ์กันน้อยที่สุด เกณฑ์ที่ 1 บอกว่าจากความแตกต่างของอินพุตและเอาต์พุตที่เป็นไปได้ทั้งหมด ความสัมพันธ์สูงสุดคือการหาความแตกต่างของอินพุตที่สร้างความแตกต่างของเอาต์พุตที่เหมือนกันสำหรับ 4 จาก 16 อินพุตที่เป็นไปได้ (เช่น สองคู่) อีกครั้งที่คุณสมบัติบิตเดียวนั้นอันตรายกว่าเนื่องจากความแตกต่างจะแพร่กระจายไปทั่วรอบ โดยผ่าน S-box เดียวในแต่ละรอบ ดังนั้น จึงเพิ่มเกณฑ์ 2 ซึ่งระบุว่าสำหรับอินพุตใดๆ ที่แตกต่างกันเพียงบิตเดียว เอาต์พุตจะไม่แตกต่างกันเพียงบิตเดียว

เพราะมีเพียง 16 เท่านั้น! S-box แบบ 4 บิตที่เป็นไปได้และความสมมาตรอย่างมากระหว่าง S-box บางคลาส จึงเป็นไปได้ที่จะทดสอบ S-boxes ที่เป็นไปได้ทั้งหมดอย่างละเอียดถี่ถ้วนสำหรับคุณสมบัติที่อธิบายไว้ข้างต้น การวิเคราะห์นี้เสร็จสิ้นแล้ว ช่วยให้นักเข้ารหัสสามารถเลือก S-box ขนาดนี้โดยรู้ว่าเหมาะสมที่สุดในแง่ของคุณสมบัติเชิงเส้นและเชิงอนุพันธ์ ยังมี S-box หลายตัวที่ตรงตามข้อกำหนดเหล่านี้ และทีมงานของ PRESENT อ้างว่าได้เลือกหนึ่งตัวที่เหมาะสมอย่างยิ่งกับการนำฮาร์ดแวร์ไปใช้ ฉันถือว่าสิ่งนี้หมายความว่าฟังก์ชันที่แสดงโดย S-box สามารถประเมินได้ด้วยเกทจำนวนน้อยหรือด้วยความลึกของวงจรเล็กน้อย (ฉันไม่มีรายละเอียดเกี่ยวกับประเด็นนี้โดยเฉพาะ)