รูหนอนการตรวจสอบดังกล่าวเป็นที่รู้จักหรือเป็นไปได้หรือไม่

1. สถานการณ์

สมมติว่าเรามีแหล่งที่มาที่สร้างค่าสุ่มหนึ่งค่าต่อนาที ดังนั้นเราจึงมีค่าสุ่ม $x_1$ ใน $1$นาทีที่ $x_2$ ใน $2$นาทีที่ $\ldots$, $x_n$ ใน $n$นาทีที่ th เป็นต้น

การกระจายของค่า $x_1, x_2, \ldots$ ไม่ใช่การสุ่มที่เหมือนกันทั้งหมด แต่เป็นไปตามกฎต่อไปนี้: สำหรับใดๆ $i \ge 1$, $x_i = (y_i, y_{i+1})$, ที่ไหน, $y_i$ เป็นตัวระบุเฉพาะของ $x_i$, และ $y_{i+1}$ เป็นตัวระบุที่ไม่ซ้ำใครที่กำลังจะมาถึง $x_{i+1}$ ที่จะมาถึงในนาทีถัดไป

กล่าวอีกนัยหนึ่งใดก็ตาม $i$นาทีที่ปัจจุบัน $x_i$และต่อไป $x_{i+}$ เป็นที่รู้กันแต่หนหลัง $x_{i+2}$ ไม่เป็นที่รู้จักอย่างแน่นอนหรือสุ่ม ด้านล่างนี้คือตัวอย่าง:

นาทีที่ 1: x_1 = (334234 , 234829129 )
นาทีที่ 2: x_2 = (234829129, 983220 )
นาทีที่ 3: x_3 = (983220 , 831231236347)
...
นาทีที่ n: x_n = (643532754, 3534611 )

วิธีหนึ่งในการแฮชเหล่านั้น $n$ ค่า ตามลำดับ คือการแฮชแต่ละค่าเมื่อมาถึง เช่น $h_1 = ฉ(x_1)$แล้วโยงเข้ากับตัวที่เพิ่งมาถึงตัวถัดไป เช่น $h_2 = f(x_2 \ขนาน h_1)$.

กล่าวอีกนัยหนึ่งคือแฮชของรายการอินพุตที่เรียงลำดับใน $n$นาทีที่ถูกกำหนดซ้ำเป็น $h_n = f(x_n \ขนาน h_{n-1})$โดยมีกรณีฐานเป็น $h_1 = ฉ(x_1)$.

ข้อดีของแนวทางนี้คือ ไม่ว่าใครก็ตามที่เรียกใช้กระบวนการนี้ตั้งแต่เริ่มต้น ในทุก ๆ นาที ทั้งรันไทม์และสเปซไทม์จะอยู่ใน $O(1)$เนื่องจากเขาสามารถแคชแฮชจากนาทีก่อนหน้าได้

ข้อเสียของวิธีนี้คือ สำหรับคนที่ไม่ได้ทำตามขั้นตอนและต้องการตรวจสอบว่า $h_n$ เป็นแฮชของลำดับทั้งหมด เขาจะต้องเริ่มต้นใหม่ตั้งแต่ต้น $h_1$และทำซ้ำทั้งห่วงโซ่จนสุด $h_n$. กระบวนการตรวจสอบนี้จะใช้อย่างมีประสิทธิภาพ $O(n)$ พื้นที่และ $O(n)$ เวลา.

2. รูหนอน

มันคงจะดีถ้าเป็นไปได้ว่าทุกๆ $n$ hashed chain จำนวนมาก เราสามารถค้นพบ รูหนอน $w_n$ ที่มีคุณสมบัติดังนี้

• เมื่อ $n$แฮช, $h_n$ถูกคำนวณออกอย่างถูกต้องตามกฎหมาย $h_1$ โดยทำตามการเรียกซ้ำทั้งหมดก่อนหน้านี้เท่านั้น จากนั้นรูหนอน $w_n$ กลายเป็นการค้นพบ มิฉะนั้นการค้นหา $w_n$ เป็นไปไม่ได้ในทางปฏิบัติ
• สำหรับที่กำหนด $h'_n$ แฮชที่อ้างว่าเป็น $h_n$, รูหนอนสามารถลัดการตรวจสอบได้ดังนี้:

$$ w_n(h_1, h'_n) = \begin{กรณี} 1 & \text{if $h'_n = h_n$}\ 0 & \text{else}\ \end{กรณี} $$

• รันไทม์ที่แย่ที่สุดแบบซีมโทติคและพื้นที่ที่แย่ที่สุดแบบซีมโทติคสำหรับการประมวลผล $w_n(h_1, h'_n)$ ไม่เลวร้ายไปกว่า $O(\logn)$. ถ้าเข้าได้ $O(1)$ที่จะดีกว่าแน่นอน

บันทึก. ซึ่งแตกต่างจาก ภาพก่อน การโจมตีของฟังก์ชันแฮช ข้อแตกต่างดังนี้

• การโจมตีด้วยภาพล่วงหน้าทำให้ผู้โจมตีสามารถปลอมแปลง ตามอำเภอใจ อินพุตที่ให้แฮชเป้าหมายที่ต้องการ

• รูหนอนนี้ $w_n$ ไม่อนุญาตให้ปลอมแปลงอินพุตใด ๆ โดยพลการ แต่จะเปิดเผยเส้นทางลัดที่ซ่อนอยู่ซึ่งใช้งานได้สำหรับการเชื่อมโยงอินพุตเฉพาะที่อนุญาตให้เชื่อมโยงเท่านั้น $h_n$ กลับไป $h_1$และวิธีเดียวที่จะค้นพบรูหนอนดังกล่าวคือการคำนวณอย่างถูกกฎหมาย $h_n$ แรก.

• บางทีเราอาจเรียกรูหนอนดังกล่าวว่าเป็นการโจมตีแบบพรีอิมเมจแบบมีเงื่อนไขซึ่งไม่เกิดประโยชน์ต่อฝ่ายตรงข้าม

3. คำถาม

รูหนอนการตรวจสอบดังกล่าวเป็นที่รู้จักหรือเป็นไปได้หรือไม่

แก้ไข: ชี้แจงคำตอบโดยใช้ Merkle tree เป็นตัวอย่าง

สำหรับรายการค่า $x_1,\ldots,x_n$คุณสามารถคำนวณต้นไม้ Merkle ด้วยรากได้ $h_n$. สำหรับที่กำหนด $h_n'$ อ้างว่าเป็น $h_n$คุณสามารถย่อการตรวจสอบให้สั้นลงได้โดยการเปิดเผย เส้นทางการรับรองความถูกต้อง ความยาว $log_2(n)-1$ ระหว่างแฮชลีฟที่รู้จัก $ฉ(x_i)$ และที่กล่าวอ้าง $h_n'$.

โดยการกำหนดรูหนอน $w_{i,n}$ เป็นเส้นทางการตรวจสอบระหว่าง $ฉ(x_i)$ และ $h_n$คุณสามารถตรวจสอบได้ว่า $h_n' = h_n$ ใน $log_2(n)$ โทร $f$. เป็นรหัสหลอก:

def ตรวจสอบ (f_x_i, w, h_n):
    h_i = f_x_i
    สำหรับ h_j ใน w:
        h_i = ฉ(h_i + h_j)
    กลับ h_i == h_n

จากนั้นคุณสามารถโทร ตรวจสอบ(f(x_i), w_i_n, h_n'). โดยเฉพาะเพื่อตรวจสอบ $h_n'$ ไม่ต้องการการแฮชก่อนหน้านี้ทั้งหมด มีเพียงส่วนย่อยของขนาดลอการิทึมที่เรียกว่าเส้นทางการตรวจสอบสิทธิ์

ข้อเสียของการใช้ Merkle tree ในที่นี้คือเราต้องคิดว่ามันมีความสมดุลอย่างสมบูรณ์ กล่าวคือ $n = 2^k$ สำหรับบางคน $k$และการต่อท้ายจำเป็นต้องสร้างต้นไม้ใหม่ ดังนั้นจึงไม่ได้รับประโยชน์ ต่อท้ายของคุณ $h_i$ ถึง ก เทือกเขา Merkle แต่มีบางสิ่งที่คล้ายกับเส้นทางการตรวจสอบสิทธิ์เพื่อแสดงว่าเส้นทางนั้นอยู่ภายใต้ชุดของ ยอดเขา แทนที่จะอยู่ใต้รากเดียว