ฉันกำลังอ่านหนังสือเรียนและในนั้นพวกเขาอธิบายคุณสมบัติของฟังก์ชันแฮช โดยเฉพาะอย่างยิ่ง พวกเขาให้ตัวอย่างว่าไม่น่าเป็นไปได้ที่จะพบค่าอินพุตที่สองที่ตรงกับเอาต์พุตแฮชของอินพุตดั้งเดิม นี่คือตัวอย่าง:
ตอนนี้เราแสดงให้เห็นแล้วว่าออสการ์สามารถเปลี่ยนความสามารถของเขาในการค้นหาการชนกันได้อย่างไร (แก้ไข สองข้อความ) เข้าสู่การโจมตี เขาเริ่มต้นด้วยสองข้อความ เช่น: $x_1 = \text{ โอน \$10 เข้าบัญชีของออสการ์ } \ x_2 = \text{ โอน \$10,000 เข้าบัญชีออสการ์} $
ตอนนี้เขาเปลี่ยนไป $x_1$ และ $x_2$ ที่ตำแหน่งที่ "มองไม่เห็น" เช่น เขาแทนที่ช่องว่างด้วยแท็บ เพิ่มช่องว่าง ฯลฯ ความหมายของข้อความเหมือนกัน (เช่น สำหรับธนาคาร) แต่แฮชเปลี่ยนไป
ออสการ์พยายามจนหมดสภาพ $h(x_1)=h(x_2)$. โปรดทราบว่าหากผู้โจมตีมี เช่น $64$ สถานที่ที่เขาสามารถเปลี่ยนแปลงหรือไม่ก็ได้ $2^{64}$ รุ่นของข้อความเดียวกันกับ $2^{64}$ ค่าแฮชที่แตกต่างกัน
ใครช่วยอธิบายหน่อยว่าพวกเขาหมายถึงอะไร $2^{64}$ รุ่นของข้อความเดียวกัน? สิ่งนี้บินอยู่เหนือหัวของฉันอย่างสมบูรณ์ ฉันรู้ว่าฟังก์ชันแฮช (เช่น SHA-256) สร้างเอาต์พุต 64 ดังนั้นตัวอย่าง:
SHA256(โอนเงิน $10 เข้าบัญชีของ Oscar)=250e62ddffbdf20a0ea40d69287327e8aff58b6ad49c03dab3f714b596804dc1
ฉันเข้าใจว่าออสการ์ต้องการปรับเปลี่ยน โอนเงิน 10,000 ดอลลาร์เข้าบัญชีของออสการ์ เพื่อให้เอาต์พุตเมื่อเสียบเข้ากับฟังก์ชัน SHA-256 จะได้เอาต์พุตเหมือนกับด้านบน แต่หมายความว่าอย่างไรที่ผู้โจมตีสามารถ "เปลี่ยนแปลงหรือไม่" ของสถานที่ทั้ง 64 แห่งได้ และการ "เปลี่ยนแปลงหรือไม่" นี้จะส่งผลอย่างไร $2^{64}$ รุ่นของข้อความเดียวกัน?
ข้อความที่ยกมาดูเหมือนจะพูดถึงการค้นหาการชนกันของฟังก์ชันแฮช 128 บิตกับการโจมตีวันเกิด ในการโจมตีวันเกิด หนึ่งสร้างรอบ $\sqrt{2^{128}} = 2^{64}$ ข้อความเพื่อให้พวกเขาคาดหวังว่าจะพบคู่ที่ชนกันด้วยความน่าจะเป็น 1/2
ในการโจมตีที่อธิบายไว้ Oscar ต้องการสร้างข้อความเฉพาะ 2 ข้อความที่มีค่าแฮชเดียวกัน
$x_1$= โอนเงิน \$10 เข้าบัญชีของออสการ์
$x_2$= โอนเงิน \$10,000 เข้าบัญชีของออสการ์
เพื่อที่จะสร้าง $2^{64}$ ข้อความหนึ่งสามารถใช้อักขระที่มองไม่เห็นเช่น ช่องว่าง และ แท็บ. หากคุณต่อท้าย 64 ตัวอักษร $x_1$ หรือ $x_2$ สิ่งเหล่านี้เป็นแท็บหรือช่องว่างจากนั้นคุณจะได้รับ 64 ตำแหน่ง สิ่งนี้ทำให้ $2^{64}$ ข้อความที่มีความหมายเหมือนกันแต่อาจมีแฮชต่างกันสูง
การแก้ไขที่มองไม่เห็นนี้ใช้ทั้งสองอย่าง $x_1$ และ $x_2$.
สร้าง $2^{64}$ สตริงที่แตกต่างกันสำหรับ $x_1$ และ $x_2$ และนำมารวมกันเป็นชุด ชุดนี้เราคาดหวังการปะทะกัน โปรดทราบว่าด้วยวิธีนี้ เราอาจมีการปะทะกันภายในตัวแปรของ $x_1$ (หรือ $x_2$).
ตอนนี้ออสการ์หาทางหลอกลวงคุณ ออสการ์ส่งข้อความถึงคุณ $x_1$ ด้วยกระบวนทัศน์แฮชและเซ็นและคุณยืนยัน ต่อมาออสการ์อ้างว่าพวกเขาส่งคุณมา $x_2$. พวกเขาแสดงให้คุณเห็นว่าลายเซ็นเหมือนกันกับก่อนหน้านี้ และที่นี่เรามีข้อขัดแย้งที่ต้องแก้ไข
สำหรับตัวอย่างอื่นๆ ของการใช้การชนกันของแฮชในการโจมตีจริง โปรดดูคำถามนี้
การโจมตีแบบปะทะกับการโจมตีด้วยภาพล่วงหน้าครั้งที่สอง
ใน การโจมตีการปะทะกัน เรากำลังมองหาสองข้อความ $m_1$ และ $m_2$ กับ $m_1 \neq m_2$ เช่น $h(m_1) = ชั่วโมง(m_2)$. ในการโจมตีแบบปะทะกัน ผู้โจมตีสามารถเลือกค่าแฮชได้ฟรี พวกเขาค้นหาเพียงสองข้อความที่มีค่าแฮชเท่ากัน ความเป็นอิสระนี้ช่วยลดต้นทุนการโจมตี ค่าใช้จ่ายทั่วไปของการชนกันคือ $\mathcal{O}(\sqrt{2^{n/2}})$-เวลาสำหรับ $n$ฟังก์ชันแฮชเอาท์พุตบิต
ในบางสถานการณ์ ผู้โจมตีต้องการ การโจมตีด้วยภาพล่วงหน้าครั้งที่สอง; ได้รับข้อความ $m$ และมันคือค่าแฮช $x=h(ม)$ค้นหาข้อความอื่น $m' \neq ม$ ดังนั้น $h(m)=h(m')$. นี่คือสถานการณ์ที่ผู้โจมตีสร้างการปลอมแปลงลายเซ็นดิจิทัล (แฮชและเซ็น) เมื่อได้รับลายเซ็น พวกเขาพยายามค้นหาข้อความอื่น $m'$ ให้ลงลายมือชื่อตรงกับที่ให้ไว้
ค่าใช้จ่ายทั่วไปสองประการของการโจมตีด้วยภาพล่วงหน้าแบบทุติยภูมิคือ $\mathcal{O}(\sqrt{2^n})$-เวลาสำหรับ $n$- ฟังก์ชันแฮชบิต
คำจำกัดความที่เป็นทางการสามารถพบได้ใน
ถึง: ["The",""] First International Bank ["ปานามา",""] เรื่อง: ["เงิน",""] ["โอนเงิน","โอน"] ["สั่งซื้อ",""] จากบัญชีของฉัน ["จำนวน","#"]1234[".",""]
ฉัน ["ได้ยินจาก","ต้องการ"] สั่ง ["คุณ ",""] ให้ ["โอน","โอน","ย้าย"] ["ผลรวม","จำนวนเงิน"] ของ [" หนึ่งล้าน","1,000,000"] ["USD","$"] ถึง ["ต่อไปนี้",""] บัญชี ["num","#"] 3456
เป็นต้น ข้างบนนี้มี "$2^{14}*3$" ชุดค่าผสมสำหรับเฉพาะส่วนเริ่มต้นของข้อความที่เกี่ยวข้อง โดยไม่ต้องเล่นกับช่องว่าง
ถ้าฉันรับข้อความใดๆ ฉันสามารถต่อท้ายอักขระเว้นวรรคหรืออักขระแท็บเพื่อรับข้อความที่แตกต่างกันสองข้อความ แต่ละอันจากสองอันนั้น ฉันสามารถเพิ่มช่องว่างหรือแท็บอื่นเพื่อรับข้อความที่เป็นไปได้สี่ข้อความ อักขระตัวที่สามให้ 8 ข้อความที่เป็นไปได้ จากนั้น 16 และต่อๆ ไป
ถ้าฉันเลือก "ส่ง 10,000" และต่อท้ายด้วยอักขระ 64 ตัว และแต่ละตัวเป็นอักขระเว้นวรรคหรือแท็บ ฉันจะได้รับข้อความที่แตกต่างกัน 2^64 ข้อความ และด้วยแฮช 64 บิต มีโอกาสที่ดีที่ข้อความใดข้อความหนึ่งเหล่านี้จะมีรหัสแฮชเดียวกันกับข้อความ "ส่ง 10"
เหตุผลที่ต้องเพิ่มช่องว่างหรือแท็บ ไม่ใช่แค่อักขระใดๆ ก็คือผู้อ่านจะไม่เห็นอักขระเหล่านี้ ถ้าฉันได้รับ "ส่ง 10,000 xlfe13^" ฉันคงจะสงสัย
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
