อัปเดต: ในที่สุดฉันก็ทำให้การโจมตีขัดแตะได้ผล เนื่องจากเหตุผลที่แท้จริงค่อนข้างซับซ้อน ฉันตัดสินใจเขียนคำตอบด้านล่างเพื่ออธิบายวิธีการทำงาน ดังนั้นทุกคนที่มีคำถามคล้ายกันอาจได้รับแรงบันดาลใจจากงานของฉัน คำถามไม่ได้รับการแก้ไข
ฉันกำลังศึกษาการโจมตีตาข่ายเมื่อเร็ว ๆ นี้ ฉันพยายามใช้ข้อมูลจาก TPM-ล้มเหลว เพื่อช่วยให้ฉันเข้าใจการโจมตีนี้และพยายามใช้การโจมตีโดยใช้ "วิธีการแบบตำรา" (มีการเพิ่มประสิทธิภาพบางอย่างในสคริปต์โจมตี TPM-FAIL) ฉันมีคำถามบางอย่างเมื่ออ่านเนื้อหาที่ฉันไม่สามารถเข้าใจได้ด้วยตัวเอง โปรดช่วยฉันหากคุณมีความคิดใด ๆ
สูตรลายเซ็น DSA สามารถแปลงเป็นต่อไปนี้ได้ในที่สุด สมการ:
$k_i-s_i^{-1}r_id-s_i^{-1}H(m)\equiv 0 \pmod{n}$
โดยที่ k คือคีย์ชั่วคราว (r,s,) คือคู่ลายเซ็น d คือ
รหัสส่วนตัว H(m) เป็นข้อความสรุปตามปกติ ... คุณรู้การฝึกฝน
แล้วล่ะก็
สามารถเปลี่ยนเป็นรูปตาข่ายได้ สิ่งที่ต้องการดังต่อไปนี้
สมการ:
$k_i+A_id+B_i\equiv 0\pmod n$, ที่ไหน $A_i=-s_i^{-1}r_i$ และ $B_i=-s_i^{-1}H(ม)$
ที่ไม่เข้าใจคือทำไมต้องเป็นลบ? จริง ๆ แล้วพยายามแก้ไขสคริปต์โจมตีที่มีให้ใน TPM-FAIL ชุดข้อมูลและพบว่าการลบ -1 ใน A_i และ B_i จะทำให้การโจมตี ล้มเหลว. แต่เราสามารถเขียนสมการแรกใหม่เป็น:
$s_i^{-1}r_id+s_i^{-1}H(m)\equiv k_i\pmod{n}$
แนวคิดของการโจมตีขัดแตะควรยังคงอยู่: ถ้าขัดแตะ เวกเตอร์มีขนาดเล็ก อัลกอริธึมการลดพื้นฐานควรสร้างคำตอบ ฉันผิดอะไร
อย่างที่สองคือฉันลองใช้วิธีที่ไม่ได้ปรับให้เหมาะสม โครงตาข่าย SVP ถูกสร้างขึ้นดังนี้:
$\begin{bmatrix}n&&&&&\&n&&&&\&&\ddots&&&\&&&&n&&\A_1&A_2&\dots&A_t&K/n&\ B_1&B_2&\dots&B_t&&K\end{bmatrix}$
แต่เราจะเห็นได้ชัดว่า K/n จะเป็นเลขเศษส่วนซึ่งไม่สามารถใช้วิธี BKZ() หรือ LLL() ใน sagemath ได้ ที่ผมเข้าใจคือเราสามารถคูณทุกสิ่งในเมทริกซ์นี้ด้วย n ดังนั้นทุกอย่างในเมทริกซ์นี้เป็นจำนวนเต็ม หลังจากใช้ BKZ() เราหารทุกอย่างด้วย n เพื่อกู้คืนผลลัพธ์เดิม: คีย์ส่วนตัวควรอยู่ในคอลัมน์ที่สองสุดท้ายของแถวแรก อย่างไรก็ตาม ฉันไม่สามารถกู้คืนคีย์ส่วนตัวได้ แม้ว่าฉันจะใช้ 100 ลายเซ็นที่มีการรั่วไหล 8 บิตก็ตาม แนวทางของฉันถูกต้องหรือไม่?
ขอบคุณสำหรับความช่วยเหลือของคุณล่วงหน้า!
คำตอบสั้น ๆ คือ: ไม่มีอะไรผิดกับความคิดนี้ เหตุผลหลักที่ฉันโจมตีไม่สำเร็จหลังจากเปลี่ยนเครื่องหมายเป็นเพราะมีการเพิ่มประสิทธิภาพในเอกสาร TPM-FAIL มันกำจัดลายเซ็นแรกโดยการแปลงบางอย่าง นี่อาจลดขนาดของตาข่ายลง 1 ซึ่งจะเพิ่มความเร็วในการคำนวณเล็กน้อย ผลลัพธ์ของการเปลี่ยนแปลงคือสำหรับ $B_i$ มีสองเงื่อนไขแทนที่จะเป็นหนึ่ง ฉันเปลี่ยนเครื่องหมายได้เพียงระยะเดียว ดังนั้นการโจมตีจึงไม่สำเร็จ
โดยวิธีการที่ฉันต้องการชี้ให้เห็นเพิ่มเติมว่าในกระดาษบางสมการนี้ถูกแปลงเป็น CVP (โจทย์เวกเตอร์ที่ใกล้เคียงที่สุด) ซึ่งมีรูปแบบ $|\alpha \mathbf{t}-\mathbf{u}|_q < K$. ดังนั้นในกรณีนี้ $A_i=\mathbf{t}=s_i^{-1}r_i$ และ $B_i=\mathbf{u}=-s_i^{-1}H(ม)$
ประการที่สองมีความกังวลว่าสัญญาณอาจส่งผลต่อการกลับมาใหม่ จริง ๆ แล้วฉันไม่สามารถดูว่ามันถูกนำไปใช้อย่างไรในวิธี TPM-FAIL ในที่สุดฉันก็ใช้โครงตาข่ายแบบอื่น ดังนั้นฉันจึงหยุดการวิจัยไว้ที่นั่น
ตะแกรงสุดท้ายที่ฉันเลือกแตกต่างจากนี้เล็กน้อย มันขึ้นอยู่กับสมการนี้:
$ |ds_i^{-1}r_i - (-s_i^{-1}H(m))|_n = k_i < n/2^l$
เราสามารถสร้างโครงตาข่ายได้หลังจากกำจัดการทำงานของ mod:
$ d|s_i^{-1}r_i|_n - |(-s_i^{-1}H(m))|_n + C_i n=k_i < n/2^l$
เพื่อให้การโจมตีแบบแลตทิซทำงาน เราต้องการเท่านั้น $|k|$ ให้มีขนาดเล็กและเป็น $k$ เป็นแง่บวกเสมอ เราสามารถใช้การถอยกลับ:
$ d|s_i^{-1}r_i|_n - |(-s_i^{-1}H(m))|_n + C_i n - n/2^{l+1} =k_i - n/2^{ ล+1}$ ที่ไหน $ -n/2^{l+1} < k_i - n/2^{l+1} < n/2^{l+1}$
เพื่อให้แน่ใจว่าทุกองค์ประกอบในตารางเป็นจำนวนเต็ม เพื่อให้เราใช้ LLL หรือ BKZ ได้ สิ่งปกติที่เราทำคือคูณทั้งสองข้างด้วย $2^{ล+1}$
$ d[2^{l+1}\times |s_i^{-1}r_i|_n] - [2^{l+1}\times |(-s_i^{-1}H(m))|_n + n] + C_i\คูณ 2^{l+1}n =k_i - n/2^{l+1}$
วงเล็บเหลี่ยมอันแรกจะเป็น $A_i$ และครั้งที่สองจะเป็น $B_i$. โปรดทราบว่าคำล่าสุดจะถูกรวมเข้าไป $B_i$ จึงมีการเปลี่ยนป้าย
มีหลายสิ่งที่ต้องชี้ให้เห็น:
เราต้องระวังว่าการคูณของ $2^{ล+1}$ และ $|s_i^{-1}r_i|_n$ เป็นการคูณปกติ ไม่ใช่แบบแยกส่วน ใน sagemath ถ้าคุณเขียน
a = Mod(s_inv * r, n)
ค = ก * ข
บรรทัดที่สองจะกลายเป็นการคูณแบบแยกส่วน เพื่อให้เป็นเรื่องปกติเราต้องเขียน
a = Mod(s_inv * r, n)
c = a.lift() * ข
คำตอบที่ถูกต้องไม่จำเป็นต้องปรากฏในแถวแรก คำตอบอาจปรากฏในแถวที่สองหรือแถวที่สองสุดท้าย ทั้งนี้ขึ้นอยู่กับจำนวนและอัลกอริทึม ดังนั้นวิธีที่ดีที่สุดคือตรวจสอบคอลัมน์ที่เกี่ยวข้องในทุกแถวเพื่อดูว่ามีคำตอบที่ถูกต้องหรือไม่
ผลลัพธ์ที่ได้อาจไม่เป็นบวก บางครั้งอาจเป็นได้ $n-d \pmod n$. ดังนั้นสำหรับทุกแถว เราต้องตรวจสอบทั้งสองอย่าง Mod(คำตอบ , n) และ n- Mod (คำตอบ, n)
สำหรับแถวในช่วง (lattice.nrows ()):
# หมายเลขคอลัมน์ขึ้นอยู่กับวิธีที่คุณสร้างโครงตาข่าย ใน SVP ปกติด้วยเทคนิคการฝัง kanaan คอลัมน์ที่เกี่ยวข้องคือคอลัมน์ที่สองสุดท้าย
วิธีแก้ปัญหา = Mod(lattice[row, -2], modulo).lift()
ถ้า check_answer(แก้ไข):
โซลูชันการส่งคืน
ถ้า check_answer(modulo - วิธีแก้ปัญหา):
ส่งคืนโมดูโล - โซลูชัน
หากสิ่งเหล่านี้ได้รับการจัดการอย่างถูกต้อง คุณน่าจะประสบความสำเร็จในการโจมตี
เกี่ยวกับประโยคคำถามกำปั้น yhe ของคำถาม:
ทำไมถึงต้องเป็นลบ?
อ่านตามตัวอักษรและด้วย "มัน" เทียบกับปริมาณ $A_i$ และ $B_i$.
สมการชุดที่สองเป็นจริง (หรือสามารถเปลี่ยนเป็น) $k_i+{A_i}\,d+B_i\equiv0\pmod n$ ที่ไหน $A_i=-s_i^{-1}\,r_i\bmod n$ และ $B_i=-s_i^{-1}\,H(m)\bmod n$. เดอะ $\bmod n$ เป็นนัย ดังนั้น ในข้อนี้ $A_i$ และ $B_i$ ไม่เป็นลบ
นั่นคือตามคำจำกัดความของ $\bmod$ โอเปอเรเตอร์:
จำได้ว่า $x\equiv z\pmod n$ กำหนดให้หมายความตามนั้น $x-z$ เป็นทวีคูณของ $n$.
เราสามารถเขียนสมการแรกใหม่ได้เป็น $s_i^{-1}\,r_i+s_i^{-1}\,H(m)\equiv k_i\pmod n$. แนวคิดของการโจมตีแบบแลตทิซควรคงไว้: หากเวกเตอร์แลตทิซมีขนาดเล็ก อัลกอริทึมการลดพื้นฐานควรสร้างคำตอบ ฉันผิดอะไร
ฉันคาดคะเนปัญหาอย่างคลุมเครือว่ารหัสลดโครงตาข่ายที่ใช้ต้องการอินพุตในรูปแบบเมทริกซ์ เราสามารถจับคู่สิ่งนี้ได้โดยเขียนสมการใหม่เป็น $s_i^{-1}\,r_i+s_i^{-1}\,H(m)+k'_i\equiv 0\pmod n$ กับ $k'_i=n-k_i$. แต่โปรดจำไว้ว่าการโจมตีนั้นหมุนรอบความเป็นไปได้ของการเลือกโดยการโจมตีแบบกำหนดเวลา $i$ ดังนั้น $k_i$ เล็ก. วิธีการเลือกแบบเดียวกันจะไม่ให้ผลน้อย $k'_i$; และฉันไม่แน่ใจว่าจะใช้วิธีที่เหมาะสมได้ด้วยซ้ำ
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
