การค้นหาภาพที่สองสำหรับการใช้แฮชที่อ่อนแอนี้

$h'(x) := h(a_1 \ขนาน x \ขนาน b_1) \ขนาน h(a_2 \ขนาน x \ขนาน b_2) \ขนาน h(a_3 \ขนาน x \ขนาน b_3) \ขนาน \จุด \ขนาน h( a_k \ขนาน x \ขนาน b_k)$

$a_i$ และ $b_i$ เป็นคำนำหน้าและคำต่อท้ายที่รู้จักกัน

ถ้า $h$ เป็น MD2 หรือ MD4 ต้องใช้ความพยายามมากเพียงใดในการค้นหาพรีอิมเมจที่สอง $h'$?

เพื่อให้ชัดเจน: ผลลัพธ์ของ $h'$ ค่อนข้างยาว $k$ นานกว่าเอาต์พุตของ $h$.

คำตอบสำหรับคำถามเดียวกันแต่มีแฮชการเข้ารหัสที่อ่อนกว่านั้นอาจเป็นที่สนใจเช่นกัน แต่ไม่อ่อนแอเท่าการตรวจสอบ

ฉันคิดอย่างไร้เดียงสาว่าถ้ามันต้องการ $2^n$ ทำงานเพื่อค้นหาภาพพจน์ที่สองของ $h$ แล้วมันต้องการ $2^{kn}$ ทำงานเพื่อค้นหาภาพพจน์ที่สอง $h'$. เนื่องจากคุณต้องค้นหาเฉพาะ $x$ ที่สร้างความพึงพอใจให้กับทุกคน $h(a_i \ขนาน x \ขนาน b_i)$. แต่อาจมีวิธีที่เร็วกว่านี้