การต่อรหัสบล็อก $N$ กับคีย์ที่รู้จักจะปลอดภัยมากขึ้นได้อย่างไร

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

การทำให้เข้าใจง่าย:

• เราพิจารณาเฉพาะ block-cipher ซึ่งคล้ายกับ AES
• แทน $N$ block-cipher ที่แตกต่างกัน เราใช้ block-cipher หนึ่งตัวด้วย $N$ ปุ่มต่างๆ (หรือมากกว่านั้น)
• block-cipher ถ่ายโอนอินพุตหนึ่งไปยังอีกอินพุตหนึ่งเท่านั้น (ดังนั้นพวกมันจึงทำงานในโหมด ECB)

สิ่งที่เป็นที่รู้จัก:
หากเราใช้รหัสบล็อก $BC$ ไปยังอินพุตที่กำหนด $m$ ซ้ำแล้วซ้ำอีกเราจะเข้าถึงข้อมูล ณ จุดใดจุดหนึ่งอีกครั้ง $$BC^l(m,k) = m$$

สำหรับอินพุตสุ่มที่กำหนด $m$ และที่สำคัญ $k$ ความยาวรอบ $l$ ได้ทุกความยาวตั้งแต่ $1$ ถึงขนาดโดเมนของ $m$ ด้วย (ในกรณีที่เหมาะสมที่สุด) ในแต่ละค่าความน่าจะเป็นที่เท่ากัน

(ค่อนข้างแน่ใจว่าเป็นกรณีนี้ด้วย :)
ถ้าเราใช้ $N$ คีย์ที่แตกต่างกันและเชื่อมต่อรหัสบล็อกด้วยคีย์เหล่านั้นบนกันและกัน (ลำดับเดียวกันเสมอ & เสมอหลายตัว $N$ ขั้นตอน) เราส่งผลให้มีความยาวรอบ $N$ ครั้ง $[1,..,D]$ กับ $D$ ขนาดของโดเมน m

$$BC(....BC(...BC(..BC(BC(BC(m,k_0),k_1),k_2)..,k_{N-1})...,k_{i \mod{N}})....,k_{l \equiv N-1 \mod{N}}) = m$$

เราสามารถเห็นการต่อแบบนี้เป็นการใช้รอบภายใน BC เดียว

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

ตัวอย่างเช่นค่า $วี$ สามารถคำนวณออกมาเป็นมูลค่าได้ $W$ กับ: $$BC(BC(BC(BC(W,k_5),k_2),k_3,k_5,k_1,k_1) =V$$

ฝ่ายตรงข้ามรู้ $V,W$ และเคยคีย์เองด้วยแต่อยากทราบคำสั่งรันคีย์ $5,2,3,5,1,1$ หรือคำสั่งอื่นใดที่ทำงานด้วย

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

ทดลองใช้โซลูชัน 1 (ล้มเหลว):

หากฝ่ายตรงข้ามต้องการค้นหาคำสั่งดำเนินการที่ถ่ายโอน $W \ลูกศรขวา V$ เขาสามารถคำนวณ $N$ ค่าถัดไปที่เป็นไปได้ของ $W$ และ $N$ ค่าก่อนหน้าที่เป็นไปได้ของ $วี$ กับ BC ผกผัน เขาสามารถทำซ้ำได้จนกว่าจะพบเครื่องจักร

ด้วยวิธีนี้เขาควรค้นหาคำสั่งดำเนินการโดยประมาณ $\sqrt{D}$ ขั้นตอนที่ไม่ปลอดภัยเพียงพอ

โซลูชันทดลองใช้ 2 (ล้มเหลว):

เพื่อความปลอดภัยที่สูงขึ้น เราจำกัดผลลัพธ์ $วี$ เป็นค่าที่คำนวณโดยใช้ $i$คีย์ -th ในการคำนวณ BC ครั้งล่าสุด

ฝ่ายตรงข้ามสามารถใช้ BC ผกผันได้ที่นี่ $วี$ กับเป้าหมาย $i$-th และทำเช่นเดียวกับในการทดลองแก้ปัญหา 1

ทดลองใช้โซลูชัน 3 (คำถาม/แก้ไข: ล้มเหลว...):

เพื่อความปลอดภัย เราสามารถจำกัดจำนวนการดำเนินการได้หลายรายการ $E$ ขั้นตอนและด้วยสิ่งนี้ยังเปลี่ยนคีย์ของแต่ละความลึก

นอกจากการใช้ $i$-th BC คีย์สำหรับการคำนวณของ $วี$ ตอนนี้ยังต้องเป็นผลคูณของ $E$ ก้าวไปข้างหน้า $W$

ในตัวอย่างของเราจากด้านบนด้วย $E=3$ นั่นจะเป็น: $$BC(BC(BC(BC(BC(W,k_5^0),k_2^1),k_3^2,k_5^0,k_1^1,k_1^2) =V$$

ดังนั้นสำหรับที่กำหนด $วี$ กับ $i$-th คีย์สุดท้ายที่ระดับความลึก $d$ ฝ่ายตรงข้ามสามารถคำนวณความสัมพันธ์กับที่กำหนด $W$ ด้วยความลึก $d$:

คำนวณส่วนผกผันของ $วี$: $$BC^{-1}(V,k_i^{d-1 \mod E}) = V'$$

และคำนวณค่าทีละขั้นตอนเหมือนที่เขาทำในการทดลองโซลูชัน 1

ควรใช้เวลาประมาณนี้ $N^{\lfloor{\frac{E-1}{2}}\rfloor}$ การทดลองถ้าเขาทำมันกำลังดุร้าย
ถ้ายกตัวอย่าง $D=2^{128}, N=2^{16}, E=2^{5}$ นี่จะเป็น $2^{16 \cdot 15} = 2^{240}$ การทดลอง

.... หลังจากเขียนข้อความทั้งหมดนี้ ฉันสังเกตเห็นว่าเขาไม่จำเป็นต้องคำนวณทุกส่วนของทุกความลึกและเพียงแค่ต้องการ $\sqrt{D}$ ก้าวอีกครั้ง...

=====> คำถาม: มีใครมีความคิดอื่นอีกไหมว่าการต่อรหัสบล็อกจะปลอดภัยมากขึ้นได้อย่างไร (ใกล้กับ $D$)?

ฮิสทรอย

• $D$ ขนาดของชุดอินพุตและเอาต์พุต
• $V,W$ ค่าสุ่มที่สามารถมีได้ถึง $D$ ค่าที่แตกต่างกัน
• $E$ จำนวนรวมของการดำเนินการเข้ารหัสบล็อกต้องมีจำนวนมากกว่า $E$
• $N$ จำนวนคีย์รหัสบล็อกที่แตกต่างกันสำหรับแต่ละความลึก
• $k_a^b$ ตัวแปรสำคัญที่ใช้สำหรับ block-cipher พร้อมดัชนี $a,ข$ กับ $a\in\{0,N-1\}, b\in\{0,E-1\}$