Score:9

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

ธง mk

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

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

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

fgrieu avatar
ng flag
ชื่อเรื่องและเนื้อหาของคำถามถามถึงสิ่งที่แตกต่างกัน ใน [คำถามที่เกี่ยวข้อง](https://crypto.stackexchange.com/q/14338/555) ฉันถามคำถามของชื่อเรื่อง มันยาก และในบรรดาข้อเสนอต่างๆ ที่เสนอมานั้น ไม่มีอะไรที่เป็นไปอย่างรวดเร็วในทิศทางข้างหน้า เกี่ยวกับคำถามในเนื้อหา (ที่ฉันอ่านว่า: เราสามารถสร้างรหัสบล็อกที่เร็วขึ้นโดยไม่ถามว่ามันกลับด้านได้อย่างมีประสิทธิภาพหรือไม่): สังเกตว่า AES ในซอฟต์แวร์นั้นเร็วกว่าอย่างเห็นได้ชัดในทิศทางไปข้างหน้า และการเร่งความเร็วนั้นเป็นไปโดยเจตนา แต่สิ่งที่ตรงกันข้ามยังคงพลิกกลับได้อย่างมีประสิทธิภาพ
eddydee123 avatar
mk flag
ฉันแก้ไขชื่อเรื่อง (เพื่อให้ความคิดเห็นของ Francois สมเหตุสมผล ต้นฉบับคือ "Block cipher ซึ่งไม่สามารถแปลงกลับได้อย่างมีประสิทธิภาพ")
Score:9
ธง ru

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

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

Gilles 'SO- stop being evil' avatar
âฟังก์ชันรอบการถอดรหัสมีประสิทธิภาพน้อยกว่าฟังก์ชันรอบการถอดรหัสâ ฉันคิดว่า *การถอดรหัส* ตัวที่สองควรเป็น *การเข้ารหัส* มันเป็นเรื่องธรรมดาจริงเหรอ? ในการใช้งานที่ไร้เดียงสา MixCol ค่อนข้างสมมาตร
Daniel S avatar
ru flag
ขอบคุณสำหรับการแก้ไข ตอนนี้ฉันได้แก้ไขแล้ว เว้นแต่ว่าผู้คนกำลังใช้งาน T-table วิธีการทั่วไปคือการคูณเมทริกซ์ที่สอดคล้องกัน และ [เมทริกซ์ผกผัน](https://en.wikipedia.org/wiki/Rijndael_MixColumns#InverseMixColumns) มีรายการที่น่าอึดอัดใจมากกว่า ` เมทริกซ์ MixCol` ที่รายการทั้งหมดคือ 1, $x$ หรือ $1+x$
Score:6
ธง in

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 ในตัวและมีซอฟต์แวร์ที่รวดเร็วมาก

Score:5
ธง in

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

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

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

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

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

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

poncho avatar
my flag
โปรดทราบว่าการเข้ารหัสแบบฟองน้ำใช้ตัวเลือก 'การตัดทอนเอาต์พุต' อย่างมีประสิทธิภาพ (โดยไม่ส่งออก 'ความจุ')
fgrieu avatar
ng flag
_"PRF เหมาะสมกว่า PRP"_ เบี่ยงเบนไปจากคำถามตามที่ใช้กันอยู่ในปัจจุบัน ซึ่งถามอย่างชัดเจนถึง _permutation_ ที่คำนวณได้อย่างมีประสิทธิภาพ และสิ่งที่เราได้รับเมื่อเราลบข้อจำกัดที่ว่าการเปลี่ยนลำดับย้อนกลับนั้นคำนวณได้อย่างมีประสิทธิภาพ ตามที่ยกตัวอย่างโดย AES เป็นไปได้ว่าเราได้รับเพียงเล็กน้อย ฉันเห็นด้วยที่เราได้รับมากขึ้นโดยการลดข้อกำหนดที่ว่าฟังก์ชันเป็นการเรียงสับเปลี่ยน และด้วยขนาดบล็อกที่ใหญ่พอที่เราสามารถหลีกเลี่ยงได้ในทางปฏิบัติ แต่ฉันยังคงพบความสนใจในคำถาม

โพสต์คำตอบ

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