Score:2

อัลกอริทึม Grover สำหรับการเข้ารหัสคีย์สาธารณะ - FrodoKEM

ธง in

ฉันสงสัยว่าใครสามารถใช้อัลกอริทึม Grover กับไฟล์ กลไกการห่อหุ้มที่สำคัญ เพื่อถอดรหัสคีย์ที่ใช้ร่วมกัน

ตัวอย่างเช่น FrodoKEM เป็นโปรโตคอลการสร้างคีย์ที่ใช้ร่วมกัน 128 บิตสำหรับพารามิเตอร์บางตัว

เราสามารถทำลายมันโดยใช้ Grover ได้หรือไม่? เช่น ลดเป็น $2^{64}$ การดำเนินงาน?

ข้อมูลอ้างอิงสำหรับ FrodoKEM: https://frodokem.org/files/FrodoKEM- specification-20171130.pdf

kelalaka avatar
in flag
คุณกำลังถามโดยใช้ Grover's Against FrodoKem หรือ Against the symmetric key encryption ที่ FrodoKem สร้างขึ้น การเข้ารหัสแบบสมมาตรใดที่อยู่ภายใต้การใช้งานหลังจาก FrodoKem พิจารณาเช่น RSA-KEM (กลไกการห่อหุ้มคีย์) + AES-GCM (กลไกการห่อหุ้มข้อมูล (DEM)) Grover จะเอาชนะ AES-128 ในอนาคตอันใกล้ แต่ไม่ใช่ AES-256
C.S. avatar
in flag
ขอบคุณ @kelalaka แล้วการทำลาย FrodoKEM ด้วยตัวเองล่ะ? อัลกอริทึมของ Grover เป็นไปได้หรือไม่?
kelalaka avatar
in flag
แน่นอนว่ายังไม่เป็นที่ชัดเจนว่าเราจะเรียก $\sqrt{2^n}$ Grover Oracles ในชีวิตจริงได้อย่างไร มีค่าใช้จ่ายเท่าไร ( timexmoney ) ในการเตรียม Oracle ถัดไป...
kelalaka avatar
in flag
[การวิเคราะห์เวลา Grover อย่างง่ายอยู่ที่นี่](https://crypto.stackexchange.com/a/67677/18298) และ [ความไร้ประสิทธิภาพของเครื่อง Grover คู่ขนานอยู่ที่นี่](https://quantumcomputing.stackexchange.com/q/4531 /4866)
Score:6
ธง my

ฉันสงสัยว่าใครสามารถใช้อัลกอริทึม Grover กับกลไกการห่อหุ้มคีย์เพื่อถอดรหัสคีย์ที่ใช้ร่วมกัน

นี่คือวิธีการทำงานของอัลกอริทึมของ Grover (แบบง่าย): คุณใช้ฟังก์ชัน 'ฟิตเนส' (ซึ่งคาดเดาค่าที่คุณกำลังค้นหาและประเมินค่าเป็น '1' หากการคาดเดาถูกต้อง และ '0' หากไม่ใช่ - สำหรับ AES ฟังก์ชันฟิตเนสอาจเป็น 'ใช้การเดาเป็นคีย์ AES และเข้ารหัสบล็อกข้อความธรรมดาที่รู้จัก และตรวจสอบว่าผลลัพธ์เป็นบล็อกข้อความไซเฟอร์ที่รู้จักหรือไม่)

จากนั้น ให้คุณใช้ฟังก์ชันฟิตเนสนี้ (และการดำเนินการควอนตัมอื่นๆ) และวนซ้ำหลายๆ ครั้ง ถ้าคุณวนซ้ำในจำนวนครั้งที่ถูกต้อง เมื่อคุณวัดผลลัพธ์ มีความเป็นไปได้สูงที่ค่าฟิตเนส ฟังก์ชันประเมินเป็น 1

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

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

ตอนนี้ การโจมตีนี้ไม่ได้มีอยู่ในการเข้ารหัสหลังควอนตัม มันไม่ทำงานโดยการโจมตีความลับที่ใช้ร่วมกัน 128 บิตโดยตรง แต่แทนที่จะใช้วิธีที่ชุดพารามิเตอร์นี้ของ Frodo สร้างการแบ่งปันคีย์โดยใช้ค่าสุ่ม 128 บิตเป็น 'secret seed' สิ่งที่โฟรโดทำคือใช้เมล็ดพันธุ์ลับ 128 บิตนั้นและขยายโดยใช้ SHAKE เพื่อสร้างการแบ่งปันและข้อผิดพลาดที่ยาวขึ้นมาก นักออกแบบของ Frodo อาจใช้เมล็ดลับที่ยาวกว่านั้น และขยายไปยัง SHAKE ซึ่งจะทำให้ Grover ยากขึ้นมาก (เพราะเมล็ดลับที่จะกู้คืนนั้นยาวกว่ามาก และการพยายามกู้คืนสถานะ SHAKE ภายในหรือลำดับของเอาต์พุต SHAKE จะ ใช้เวลานานเกินไป) นักออกแบบของ Frodo ไม่ได้ทำเช่นนี้ อาจเป็นเพราะมันไม่ได้ปรับปรุงความปลอดภัยอย่างแท้จริง

ในทางที่สาม เรามักทำบางอย่างกับคีย์ที่ใช้ร่วมกัน เราอาจป้อนข้อมูลนั้นลงใน KDF (อาจร่วมกับข้อมูลสาธารณะบางอย่าง เช่น nonces) แล้วใช้ผลลัพธ์นั้นเป็นคีย์ AES เราสามารถสร้างฟังก์ชันฟิตเนสจากสิ่งนั้นได้ ดังนั้น Grover's จึงนำไปใช้กับระบบนั้น - เป็นไปได้มากว่า โครงสร้าง KDF/AES นี้จะนำไปใช้ภายใน Quantum Computer ได้ง่ายกว่ากระบวนการ Frodo public key (หรือการห่อหุ้ม) ดังนั้นจึงเป็นไปได้ง่ายกว่าที่จะโจมตีระบบที่นั่น (หากเป็นเพียงปัจจัยคงที่)

ประการที่สี่ มีเหตุผลที่จะถามว่า Grover's เป็นภัยคุกคามต่อความลับ 128 บิตจริงหรือไม่ - การประเมินฟังก์ชันการออกกำลังกายทั้งหมดนี้ทำตามลำดับ และการประเมินฟังก์ชันใดๆ นั้นเป็นไปไม่ได้ $2^{64}$ ครั้งติดต่อกัน และในขณะที่คุณสามารถพยายามแก้ไขปัญหานี้ได้โดยเรียกใช้ Grover's บนคอมพิวเตอร์ควอนตัมจำนวนมากโดยการแบ่งพื้นที่ลับ เราจะสูญเสียข้อได้เปรียบของ Grover ไปส่วนหนึ่งหากเราทำเช่นนั้น และท้ายที่สุดเราก็ใช้ มาก ของควอนตัมคอมพิวเตอร์

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

Fleeep avatar
br flag
เหตุใดคุณจึงไม่สามารถโจมตี (= สร้างฟังก์ชันฟิตเนส) เมล็ดเริ่มต้น (ซึ่งมี 128 บิตด้วย) ที่ใช้สร้างคู่ (sk, pk) โดยใช้ Grover สิ่งนี้จะถือว่าการค้นหา sk (หรือมากกว่าเมล็ดที่ขยายเป็น sk) ซึ่งส่งผลให้ pk เดียวกันช่วยให้คุณสามารถถอดรหัสได้สำเร็จ
poncho avatar
my flag
@Fleeep: ขอโทษ; ฉันคิดว่า Frodo-640 ใช้เมล็ดพันธุ์ลับที่ยาวกว่านั้น - ตรวจสอบซ้ำแล้วซ้ำอีก ฉันพบว่าไม่ใช่ จากนั้น ใช่ คุณสามารถใช้ Grover's เพื่อกู้คืนได้ ในทางกลับกัน ฉันสงสัยว่านั่นจะเป็นปัจจัยคงที่ที่ซับซ้อนกว่าการโจมตีระบบสมมาตรที่ใช้เมล็ด แต่ก็เป็นไปได้อย่างแน่นอน (หากทำไม่ได้ ดูด้านบน)
poncho avatar
my flag
@Fleeep: ตกลง ฉันแก้ไขคำตอบเพื่อจัดการกับการโจมตีทางเลือกนี้

โพสต์คำตอบ

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