มีวิธีที่เป็นมาตรฐานในการประเมินความปลอดภัยของอัลกอริทึมการแลกเปลี่ยนคีย์หรือไม่?

ตอนนี้ฉันกำลังพยายามออกแบบอัลกอริทึมการเปลี่ยนคีย์ที่ปลอดภัยยิ่งขึ้นเพื่อแทนที่ DH ที่ใช้กันอย่างแพร่หลาย

อย่างไรก็ตาม ฉันสามารถพิสูจน์ได้ว่าอัลกอริทึมของฉันปลอดภัยกว่าเท่านั้น มีเหตุผลซึ่งหมายความว่าฉันสามารถพิสูจน์ได้จาก การให้เหตุผล ค่อนข้างมากกว่า ทางคณิตศาสตร์ ทัศนคติ.

ดังนั้นฉันสงสัยว่ามี ขั้นตอนที่ได้มาตรฐาน ที่ผมสามารถใช้ประเมินผลงานได้

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

ไม่ หากระบบของคุณแตกต่างอย่างมากเกี่ยวกับการแลกเปลี่ยนคีย์ DH ก็ไม่เกี่ยวข้องจริงๆ ที่จะต้องสังเกตว่าการโจมตีที่ออกแบบมาโดยเฉพาะกับโปรโตคอล Diffie-Hellman นั้นไม่มีประสิทธิภาพกับระบบของคุณ

มีสามวิธีในการเปรียบเทียบโปรโตคอลของคุณกับโปรโตคอลอื่น:

• อันดับแรก จะเป็นการดีที่จะพิสูจน์โดยการเขียน หลักฐานความปลอดภัย อย่างน้อยที่สุดโปรโตคอลของคุณก็ปลอดภัยพอๆ กับปัญหาอัลกอริทึมที่บางคนรู้ และถ้าปัญหาเป็นที่รู้จักหนักกว่าปัญหา Diffie-Hellman มันอาจจะน่าสนใจ แต่คุณต้องสังเกตว่าปัญหา Diffie-Hellman (การตัดสินใจหรือการคำนวณ) เป็นปัญหาแบบพารามิเตอร์ และความแข็งของปัญหาเหล่านี้ขึ้นอยู่กับการเลือกพารามิเตอร์อย่างมาก (เรียกว่าพารามิเตอร์ความปลอดภัยและชื่อ $\แลมบ์ดา$ ในงานวิจัย).ดังนั้น ถ้าคุณต้องการพูดตามตรง คุณต้องเลือกพารามิเตอร์ที่เกี่ยวข้องเพื่อเปรียบเทียบปัญหาทั้งสอง (เช่น คุณสามารถเปรียบเทียบกับพารามิเตอร์ที่ทำให้ประสิทธิภาพของโปรโตคอลทั้งสองเท่ากัน)

• ความเป็นไปได้อื่น ๆ คุณอ้างว่าโปรโตคอลของคุณตรวจสอบคุณสมบัติบางอย่างที่แข็งแกร่งกว่าการแลกเปลี่ยนคีย์ DH จากนั้นจะเป็นการดีที่จะโต้แย้งการอ้างสิทธิ์ของคุณด้วยหลักฐานด้านความปลอดภัยและแสดงว่า DH-KE ไม่ได้ตรวจสอบคุณสมบัตินี้ (เช่น แสดงการโจมตี)

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

levgeni ให้คำตอบที่ค่อนข้างดี มีบางจุดที่ฉันคิดว่าฉันสามารถเพิ่มได้:

ตอนนี้ฉันกำลังพยายามออกแบบอัลกอริทึมการเปลี่ยนคีย์ที่ปลอดภัยยิ่งขึ้นเพื่อแทนที่ DH ที่ใช้กันอย่างแพร่หลาย

ก่อนอื่น เป็นไปได้ค่อนข้างมากว่า "อัลกอริธึมการแลกเปลี่ยนคีย์" ใหม่ของคุณจะอ่อนแอ ฉันไม่ได้บอกว่าจะใจร้ายเท่านั้น [1] แต่ยังอ้างอิงจากประวัติของอัลกอริทึมการเข้ารหัสที่เสนอ (รวมถึงการแลกเปลี่ยนคีย์) - ส่วนใหญ่กลายเป็นจุดอ่อน และนี่เป็นเรื่องจริงโดยเฉพาะอย่างยิ่งสำหรับการออกแบบที่ทำโดยการเข้ารหัส สามเณร และแม้ว่านักเข้ารหัสที่มีประสบการณ์จะเสนอระบบใหม่ พวกเขาจะไม่มีวันอ้างว่าระบบนั้นปลอดภัย [2] - เราพูดเสมอว่าจำเป็นต้องมีการตรวจสอบ

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

ดังนั้น เว้นแต่ว่าอัลกอริทึมของคุณจะเป็นแบบ Quantum Resistant นั่นคือไม่สามารถถูกทำลายได้แม้ว่าจะมีผู้โจมตีด้วย Quantum Computer แต่ก็ไม่น่าจะมีใครสนใจมัน แม้ว่าคุณจะสามารถแสดงได้ว่าปลอดภัยจากศัตรู คอมพิวเตอร์. และวิธีหนึ่งในการดูว่าอัลกอริทึมไม่ทนต่อควอนตัม" คือการพิจารณาฝ่ายตรงข้ามที่มี Magic Box ที่สามารถแยกตัวประกอบและคำนวณบันทึกแยกกันได้ หากฝ่ายตรงข้ามดังกล่าวสามารถทำลายระบบของคุณได้ แสดงว่าคุณไม่ใช่ผู้ต่อต้านควอนตัม แน่นอน มันไม่ได้ไปในทางอื่น - เพียงเพราะอัลกอริทึมของคุณมีภูมิคุ้มกันต่อแฟคตอริ่งและการคำนวณการโจมตีแบบแยกส่วนไม่ได้หมายความว่ามันทนทานต่อควอนตัม - คอมพิวเตอร์ควอนตัมสามารถทำสิ่งอื่นได้เช่นกัน

อย่างไรก็ตาม ฉันสามารถพิสูจน์ได้ว่าอัลกอริทึมของฉันปลอดภัยกว่าเท่านั้น มีเหตุผลซึ่งหมายความว่าฉันสามารถพิสูจน์ได้จาก การให้เหตุผล ค่อนข้างมากกว่า ทางคณิตศาสตร์ ทัศนคติ.

สิ่งที่คุณหมายถึงคือคุณมีข้อโต้แย้งที่น่าเชื่อถือว่าอัลกอริทึมของคุณปลอดภัย ข้อโต้แย้งที่น่าเชื่อถือย่อมดีกว่าไม่มีอะไรเลย อย่างไรก็ตามมันไม่ได้ดีกว่ามากการพิสูจน์ทางคณิตศาสตร์คือสิ่งที่คาดหวัง...

ดังนั้นฉันจึงสงสัยว่ามีขั้นตอนมาตรฐานที่ฉันสามารถใช้ในการประเมินผลงานของฉันได้หรือไม่

ดังที่เลฟเกนีกล่าวไว้ วิธีมาตรฐานคือการระบุ 'ปัญหายาก' (หรืออาจเป็นปัญหาหนักหลายข้อ) จากนั้นสร้างหลักฐานว่าถ้าคุณสามารถทำลายการแลกเปลี่ยนคีย์ของคุณได้ [3] เขาก็จะแก้ปัญหายากได้ [4] . เมื่อคุณทำเสร็จแล้ว คุณสามารถลองประเมินว่า 'ปัญหาหนัก' ของคุณยากเพียงใด (และดูว่ายากกว่าปัญหาหนักที่ DH อิงตามหรือไม่ ซึ่งจะเป็นปัญหา CDH หรือ DDH)

เว้นแต่คุณจะทำอย่างนั้น มันยากมากที่จะให้ใครมาสนใจงานของคุณอย่างจริงจัง

แน่นอน แม้ว่าคุณจะทำอย่างนั้นแล้ว (และใช่ นั่นเป็นงานที่ต้องทำมาก) มันก็ยังคงเป็นการต่อสู้ที่ยากเย็นแสนเข็ญ - คุณยังคงต้องให้นักวิเคราะห์ด้านการเข้ารหัสตรวจสอบดู ถ้าคุณมีทุกอย่างที่เขียนแล้ว คุณสามารถใส่มันลงใน eprint (และมันก็จะอยู่ที่นั่น); คุณสามารถส่งไปยังการประชุม (หากเป็นเรื่องใหม่และหลังควอนตัม PQC https://pqcrypto.org/conferences.html อาจเป็นทางออกที่ดีที่สุดของคุณ) - แม้ว่าบทความจะไม่ได้รับการยอมรับ แต่บทวิจารณ์ที่คุณได้รับอาจทำให้เข้าใจได้

[1]: นั่นไม่ใช่เหตุผลเดียว...

[2]: ข้อยกเว้นประการหนึ่งคือหากเขามีหลักฐานในมือว่าความแข็งแกร่งของระบบสามารถลดลงจนเป็นปัญหายากที่ยอมรับได้ อย่างไรก็ตาม แม้ในกรณีเหล่านั้น เขามักจะแนะนำให้ใครสักคนผ่านการพิสูจน์อย่างถี่ถ้วน...

[3]: ตามหลักการแล้ว การทำลายหมายถึง "หากคุณสามารถให้ผู้โจมตีแบ่งปันคีย์ที่แลกเปลี่ยนและ 'ความลับที่แบ่งปัน' สมมุติ เขามีข้อได้เปรียบในการแยกแยะว่า 'ความลับที่แบ่งปัน' นั้นเป็นค่าจริงหรือค่าสุ่มที่ดึงออกมา จากการแจกแจงแบบสุ่มที่เหมาะสม"

[4]: บันทึกคำสั่ง - การทำลายระบบของคุณหมายถึงการทำลายปัญหาที่ยาก ฉันเคยเห็นเอกสารที่พยายามไปในทิศทางอื่น - "ถ้าคุณแก้ปัญหายากนี้ได้ คุณสามารถทำลายระบบของฉันได้" ซึ่งไม่ได้แสดงอะไรเลย