ข้อได้เปรียบใด ๆ ต่อ block cipher ซึ่งไม่สามารถย้อนกลับได้อย่างมีประสิทธิภาพ?

คำจำกัดความแบบคลาสสิกของ PRP รวมถึงการย้อนกลับที่มีประสิทธิภาพ

เนื่องจากโหมดการเข้ารหัสสมัยใหม่จำนวนมาก (อิงตาม CTR เช่น GCM) ใช้เฉพาะทิศทางไปข้างหน้าของรหัสบล็อก ดูเหมือนว่าส่วนการกลับด้านที่มีประสิทธิภาพของคำจำกัดความไม่จำเป็นสำหรับวัตถุประสงค์ในทางปฏิบัติ

การผ่อนคลายเช่นนี้จะให้ประโยชน์อะไรแก่เราหรือไม่? เช่น มีโครงสร้าง PRP ที่สามารถคำนวณได้อย่างมีประสิทธิภาพในทิศทางไปข้างหน้าแต่ไม่สามารถย้อนกลับได้หรือไม่ และแบบใดที่มีประสิทธิภาพในทิศทางไปข้างหน้ามากกว่าตัวเข้ารหัสบล็อกปัจจุบันที่มีความปลอดภัยเทียบเท่ากัน?

ฉันจะโต้แย้งว่าสำหรับนักเข้ารหัสลับหลายคน การโต้เถียงไปไกลกว่านั้น เนื่องจากโหมดการสตรีมแบบเข้ารหัสบล็อกเป็นที่นิยมสำหรับการเข้ารหัสจำนวนมาก จึงจำเป็นต้องกลับด้านหรือไม่ ถ้าใครทำตามเหตุผลในบรรทัดนี้ เราจะเห็นได้ว่าเหตุใดความนิยมของสตรีมโค้ดจึงกลับมาได้รับความนิยมอีกครั้ง โดยมี ChaCha20 เป็นตัวอย่างที่ชัดเจน แม้ว่า ChaCha20 จะสร้างเอาต์พุต 512 บิตจากสถานะ 512 บิตและอัปเดตสถานะด้วยตัวนับอย่างง่าย (เหมือนกับโหมด CTR และ GCM) แต่กระบวนการนี้ (เราเชื่อว่า) ไม่สามารถย้อนกลับได้ เป็นเรื่องจริงเช่นกันที่ ChaCha20 เป็นการออกแบบที่มีประสิทธิภาพมาก (สมมติว่าฮาร์ดแวร์รองรับการเพิ่มคำแบบ 32 บิตอย่างมีประสิทธิภาพ)

โปรดทราบว่าสำหรับการใช้งาน AES หลายครั้ง ฟังก์ชันรอบการถอดรหัสจะมีประสิทธิภาพน้อยกว่าฟังก์ชันรอบการเข้ารหัส เนื่องจากเป็นการสลับ มิกซ์คอล กระบวนการเกี่ยวข้องกับการคำนวณมากขึ้น

PRP คือ การเปลี่ยนรูปแบบสุ่มหลอก และเราต้องการให้แยกไม่ออกจากการเรียงสับเปลี่ยนแบบสุ่ม AES และ block cipher ทั้งหมดควรจะเป็น PRP การเรียงสับเปลี่ยนหมายความว่ามีการผกผันและได้รับการออกแบบให้มีอย่างใดอย่างหนึ่งและมีประสิทธิภาพ

เราต้องการโหมดการทำงานสำหรับ block ciphers และเราออกจาก CBC เนื่องจากการโจมตีจำนวนมากที่เกิดขึ้น แม้ว่าจะมี Ind-CPA ที่ปลอดภัยก็ตามปัจจุบัน การเข้ารหัส TLS 1.3 ทั้งหมดใช้โหมด CTR ที่ปลอดภัยของ Ind-CPA ภายใน (ชุดการเข้ารหัส TLS 1.3 เป็นมากกว่านั้น โดยเป็นโหมดการเข้ารหัสที่ตรวจสอบความถูกต้องทั้งหมดพร้อมข้อมูลที่ตรวจสอบความถูกต้อง)

การผ่อนคลายเช่นนี้จะให้ประโยชน์อะไรแก่เราหรือไม่?

ทำให้เรามีโอกาสมากมาย เราไม่จำเป็นต้องจำกัดตัวเองให้อยู่เฉพาะ PRP ในโหมด CTR ซึ่งได้รับการออกแบบมาสำหรับสิ่งนี้แล้ว ฟังก์ชันสุ่มหลอก (PRF); โหมด CTR ไม่ต้องการส่วนผกผันของฟังก์ชัน ด้วย PRF เราสามารถใช้ฟังก์ชันได้หลากหลายที่ไม่จำเป็นต้องมีผกผัน (มี $2^น!$ PRP และ $(2^n)^{2^n}$ PRF สำหรับรหัสบล็อก n-บิต แม้แต่เราสามารถใช้ฟังก์ชันแฮชและแปลงเป็นการเข้ารหัส CTR ได้ ซัลซ่า. เราอาจออกแบบตารางเวลาที่สำคัญโดยมีค่าใช้จ่ายเกือบเป็นศูนย์เช่นกัน

การใช้ PRP ในโหมด CTR อาจทำให้เกิด ตัวแยกข้อความยาว และเราสามารถกำจัดสิ่งนี้ได้โดยใช้ PRF หากเราใช้ PRP ในโหมด CTR เราจำเป็นต้องจำกัดจำนวนบล็อกการเข้ารหัสเนื่องจากการสลับบทแทรกของ PRP-PRF

นอกจากนี้ โหมด CTR ยังไม่ต้องการการเติม ดังนั้นจึงมีภูมิคุ้มกันต่อการโจมตีจาก Oracle

ChaCha20 และ Salsa20 เป็นตัวอย่างที่รู้จักกันดีซึ่งมีต้นทุนกำหนดการคีย์เป็นศูนย์ การออกแบบ ARX ที่เป็นมิตรกับ CPU พวกเขามีโหมด CTR ในตัวและมีซอฟต์แวร์ที่รวดเร็วมาก

แท้จริงแล้ว PRF นั้นเหมาะสมกว่า PRP สำหรับโหมดต่างๆ เช่น CTRปัญหาคือเราไม่รู้ว่าสร้าง PRF ที่ดีนอกเหนือจาก PRP ได้อย่างไร

1. วิธีหนึ่งก็คือการแสร้งทำเป็นว่า PRP ของเราเป็น PRF และนี่คือความจริง มีการให้ข้อมูลมากถึงจำนวนหนึ่ง (วันเกิดที่ผูกไว้ ดูบทแทรกการสลับ PRP/PRF)

2. อีกวิธีหนึ่งที่ใช้บ่อยคือการคำนวณ PRP/การเรียงสับเปลี่ยน และเพิ่มอินพุตไปยังเอาต์พุต มันไม่ได้ปรับปรุงขอบเขตวันเกิด แต่เคล็ดลับนี้ทำให้ฟังก์ชันไม่สามารถเปลี่ยนกลับได้ ซึ่งเป็นสิ่งสำคัญในการใช้งานบางอย่าง (เช่น ChaCha ที่ @Daniel S พูดถึง) นอกจากนี้ยังใช้ในฟังก์ชันแฮชสไตล์ Merkle-Damgard เพื่อสร้างฟังก์ชันการบีบอัด (Davis-Meyer)

3. การเพิ่ม/xoring การเรียงสับเปลี่ยนสองครั้งเป็น PRF ที่ดี แต่มีค่าใช้จ่ายสูง

4. การตัดทอนเอาต์พุตอย่างเพียงพอก็เป็น PRF ที่ดีเช่นกัน แต่ก็มีค่าใช้จ่ายสูงเช่นกัน

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