ฉันศึกษาการเข้ารหัสด้วยตนเองจาก หลักสูตรบัณฑิตศึกษาในการเข้ารหัสประยุกต์โดย Boneh and Shoup (เวอร์ชัน 0.5) และฉันมีปัญหาในการดูผลลัพธ์ในแบบฝึกหัด 6.7
ในหนังสือเล่มนี้ระบบ MAC ที่ปลอดภัยถูกกำหนดให้อยู่ในเกมโจมตีที่ฝ่ายตรงข้ามสามารถดำเนินการเซ็นชื่อบนข้อความโดยพลการเพื่อรับแท็ก ฝ่ายตรงข้ามส่งข้อความ $m_1, m_2, \ldots, m_Q$ แก่ผู้ท้าชิงและรับแท็ก $t_1, t_2, \ldots, t_Q$. ความปลอดภัยจะวัดจากความน่าจะเป็นที่ฝ่ายตรงข้ามจะชนะโดยการนำเสนอคู่แท็กข้อความปลอมแปลง $(ม., เสื้อ)$ คู่ไหน $(m, t) \notin \{(m_1, t_1), \ldots, (m_Q, t_Q)\}$. ต่อมา เกมโจมตีใหม่จะถูกสร้างขึ้นโดยที่ฝ่ายตรงข้ามสามารถดำเนินการตรวจสอบยืนยันซึ่งฝ่ายตรงข้ามเสนอคู่แท็กข้อความ $(ม., เสื้อ)$ และรับอย่างใดอย่างหนึ่ง $\textsf{ยอมรับ}$ หรือ $\textsf{ปฏิเสธ}$ ขึ้นอยู่กับว่าคู่นั้นถูกต้องหรือไม่ ความปลอดภัยจะวัดจากความเป็นไปได้ที่ฝ่ายตรงข้ามจะได้รับ $\textsf{ยอมรับ}$ สำหรับคู่แท็กข้อความ $(m, t) \notin \{(m_1, t_1), \ldots, (m_Q, t_Q)\}$.
ทฤษฎีบท 6.1 ในหนังสือแสดงให้เห็นว่าการรักษาความปลอดภัยภายใต้เกมการโจมตีครั้งแรกหมายถึงความปลอดภัยภายใต้เกมการโจมตีครั้งที่สอง แบบฝึกหัด 6.7 ขอให้แสดงผลนี้ไม่ถือถ้าเราแก้ไขเงื่อนไขการชนะเพื่อนำเสนอ $(ม., เสื้อ)$ ปลอมแปลงที่ไหน $m \ไม่อยู่ใน \{m_1, m_2, \ldots, m_Q\}$. ภายใต้เงื่อนไขใหม่นี้ เราได้รับคำนิยามของการรักษาความปลอดภัยที่อ่อนแอโดยมี/ไม่มีการสืบค้นการยืนยัน คำแนะนำคือการใช้ PRF ที่ปลอดภัยซึ่งสามารถ "ก่อวินาศกรรม" ได้
ฉันมีปัญหาในการทำความเข้าใจว่าผลลัพธ์ของการรักษาความปลอดภัยที่อ่อนแอนี้เป็นอย่างไร เมื่อดูที่การพิสูจน์ทฤษฎีบท 6.1 มันไม่ชัดเจนว่าทำไมการพิสูจน์นั้นจึงไม่สามารถครอบคลุมถึงการรักษาความปลอดภัยที่อ่อนแอของ MAC ได้เนื่องจากการพิสูจน์ดูเหมือนจะไม่เคยใช้อย่างชัดเจน $(m, t) \notin \{(m_1, t_1), \ldots, (m_Q, t_Q)\}$ เงื่อนไข. ดังนั้นฉันเดาอย่างไร้เดียงสาว่าการพิสูจน์ทฤษฎีบท 6.1 จะยังคงใช้งานได้ เหตุใดการพิสูจน์นี้จึงล้มเหลวสำหรับ MAC ที่มีความปลอดภัยต่ำ
จากการดูคำใบ้ สิ่งเดียวที่อยู่ในใจของฉันคือการถูกปฏิเสธจากการตรวจสอบอาจเปิดเผยข้อมูลเกี่ยวกับ PRF ที่ใช้สร้าง MAC ดังนั้นฉันจึงต้องสร้าง PRF ที่สูญเสียความปลอดภัยหลังจากที่ฝ่ายตรงข้ามเรียนรู้ถึงการปฏิเสธบางประเภท ฉันหลงทางว่าการก่อสร้างดังกล่าวจะทำงานได้อย่างไร ฉันยังมีความรู้สึกว่าฉันจะต้องสร้าง MAC ที่ไม่ได้กำหนดขึ้นมา แต่ก็ยังไม่ชัดเจนสำหรับฉันว่าฉันจะสร้าง MAC ที่เกี่ยวข้องได้อย่างไร
ขอบคุณ ซามูเอล เนเวส ที่ชี้ทางที่ถูกต้องให้ฉัน. ฉันดูที่ การอ้างอิงที่กล่าวถึงและสัมผัสกับวิธีที่ทฤษฎีบท 6.1 ล้มเหลวเนื่องจากการรักษาความปลอดภัยที่อ่อนแอ นอกจากนี้ยังครอบคลุมถึง MAC ที่มีความปลอดภัยต่ำโดยไม่มีการสืบค้นเพื่อยืนยัน แต่สูญเสียการรักษาความปลอดภัยเมื่อมีการค้นหาการยืนยัน
ฉันพบว่าความละเอียดอ่อนเกิดขึ้นในการกำหนดเกมรุก ฝ่ายตรงข้ามสามารถส่งแท็กข้อความคู่ใดก็ได้ $(ม., เสื้อ)$ สำหรับการตรวจสอบตราบเท่าที่ไม่ได้อยู่ในคู่ที่ลงนามก่อนหน้านี้ สิ่งที่สำคัญคือในนิยามเดิมของการรักษาความปลอดภัย ฝ่ายตรงข้ามจะชนะเกมการโจมตี ถ้าและถ้า ฝ่ายตรงข้ามส่งคู่แท็กข้อความที่ถูกต้องและไม่เคยเห็นมาก่อนเพื่อตรวจสอบ ความเท่าเทียมกันตามมาจากคำจำกัดความของเงื่อนไขการชนะ
อย่างไรก็ตามภายใต้การรักษาความปลอดภัยที่อ่อนแอ ทิศทางไปข้างหน้ายังคงมีอยู่ (การส่งที่ถูกต้อง $(ม., เสื้อ)$ คู่ไหน $m$ ไม่เคยเห็นมาก่อนอย่างชัดเจนในรูปแบบคู่ที่ถูกต้องไม่เคยเห็นมาก่อน) แต่ทิศทางย้อนกลับล้มเหลว ทิศทางที่ถอยหลังอาจล้มเหลวได้เนื่องจากฝ่ายตรงข้ามสามารถได้รับ $(ม, ต)$ จับคู่จากแบบสอบถามการลงนามแล้วส่งที่ถูกต้อง $(M, \bar{T})$ จับคู่โดยแก้ไขแท็ก $T$. $(M, \bar{T})$ เป็นคู่ที่ถูกต้องและไม่เคยเห็นมาก่อน แต่ฝ่ายตรงข้ามไม่สามารถชนะได้เนื่องจากทั้งคู่เกี่ยวข้องกับข้อความที่เซ็นชื่อไว้ก่อนหน้านี้
โดยที่ทฤษฎีบท 6.1 ล้มเหลวเนื่องจากการรักษาความปลอดภัยที่อ่อนแอคือเมื่อผู้เขียนยืนยัน $\text{Pr}[W_0] = \text{MAC}^\text{vq}\text{adv}[\mathcal{A, I}]$ ซึ่งถือว่าการชนะเกมโจมตีนั้นเทียบเท่ากับการนำเสนอคู่แท็กข้อความที่ถูกต้องและไม่เคยเห็นมาก่อน ในตัวอย่างสุดโต่งข้างต้น นี่ไม่ใช่กรณีที่เป็นไปได้ $W_0$ ที่จะเกิดขึ้น แต่ไม่ชนะเกมโจมตีความปลอดภัยที่อ่อนแอ
สำหรับวิธีสร้างระบบ MAC ที่มีการรักษาความปลอดภัยอย่างอ่อนโดยไม่มีการสอบถามเพื่อยืนยัน แต่ไม่ปลอดภัยอย่างอ่อนแอด้วยการสอบถามการยืนยัน โดยพื้นฐานแล้วคุณสร้างระบบที่หลังจากได้รับ $(ม, ต)$ จากแบบสอบถามการลงนาม ฝ่ายตรงข้ามสามารถสร้างความถูกต้องได้อย่างง่ายดาย $(M, \bar{T})$ คู่ โดยการนำเสนอคู่ที่ถูกต้องแต่ไม่ชนะ ฝ่ายตรงข้ามจะเรียนรู้ข้อมูลเพียงพอที่จะทำลายระบบ MAC
อนุญาต $\mathcal{K} = \{0,1\}^\ell$ และ $|\mathcal{T}|$ เป็นซุปเปอร์โพลี อนุญาต $F$ เป็น PRF ที่กำหนดไว้ $(\mathcal{K, M, T})$, $k \stackrel{R}{\gets} \mathcal{K}$ และ $\mathcal{I} = (S, V)$ เป็น MAC ที่กำหนดมากกว่า $(\mathcal{K, M, T} \times \{\perp, 0,\ldots,\ell-1\})$. อัลกอริทึมการลงนามถูกกำหนดให้เป็น $S(m) = (F(k, m), \perp)$ และอัลกอริทึมการตรวจสอบคือ
V(ม., (เสื้อ, ผม))
// ตรวจสอบแท็กกับ PRF
d = F(k, m) == เสื้อ
ถ้า !d หรือ i == â
กลับ d ? ยอมรับ : ปฏิเสธ
// ส่งคืนบิตของคีย์
กลับ k[i] == 1 ? ยอมรับ : ปฏิเสธ
คุณสมบัติความถูกต้องถือเพราะองค์ประกอบที่สองของ $S(ม.)$ เป็น $\perp$ ซึ่งเข้าสู่คำสั่ง if โดยพื้นฐานแล้วระบบ MAC นี้เป็นระบบ MAC เชิงกำหนดที่ได้มาจาก $F$ แต่มีช่องดัชนีพิเศษ
ก่อนอื่นเราสังเกตเห็นว่า $\คณิตศาสตร์แคล{I}$ มีความปลอดภัยต่ำโดยไม่ต้องสอบถามการตรวจสอบความถูกต้อง หากฝ่ายตรงข้ามชนะ ฝ่ายตรงข้ามจะส่งคู่ที่ถูกต้อง $(m, (t, i))$ ที่ไหน $m$ ไม่เคยเห็นมาก่อน นี่หมายความว่า $\textsf{ยอมรับ}$ ถูกส่งกลับซึ่งมีความหมายว่า $d$ เป็นจริงใน $V(m, (t, i)))$ (ไม่ว่าจะป้อนคำสั่ง if ที่ใด $\textsf{ยอมรับ}$ ถูกส่งคืนหรือคำสั่ง if ไม่ดำเนินการซึ่งหมายถึง $d$ ไม่เป็นเท็จ) สิ่งนี้เกิดขึ้นด้วยความน่าจะเป็นเล็กน้อยโดยทฤษฎีบท 6.2 เป็น $d$ การเป็นจริงหมายถึงการปลอมแปลงขึ้นกับ MAC เชิงกำหนดที่ได้มาจาก $F$ (MAC นี้มีความปลอดภัยภายใต้คำจำกัดความของการรักษาความปลอดภัยที่เข้มงวดกว่า)
อย่างไรก็ตาม, $\คณิตศาสตร์แคล{I}$ ไม่ปลอดภัยอย่างอ่อนแอด้วยข้อความค้นหาการยืนยัน ศัตรูที่ทำลายความมั่นคงคือ
ให้ m เป็นข้อความโดยพลการ
ได้รับ (m, (t, â)) จากผู้ท้าชิง
กิโล[0..l-1] = 0
สำหรับ i = 0 .. l-1
ให้ r เป็นคำตอบของผู้ท้าชิงต่อแบบสอบถามการตรวจสอบ (m, (t, i))
ถ้า r == ยอมรับ
กิโล[i] = 1
อื่น
กิโล[i] = 0
// คีย์ถูกสร้างขึ้นใหม่
ให้ m' เป็นข้อความตามอำเภอใจที่ไม่เท่ากับ m
// คำนวณแท็กของ m' ด้วยคีย์ที่สร้างขึ้นใหม่
ให้ t' = S(m')
ส่งคำถามตรวจสอบความถูกต้อง (m', (t', â)) ไปยังผู้ท้าชิง
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
