Tìm tiền giả thứ hai cho việc sử dụng hàm băm yếu này

$h'(x) := h(a_1 \parallel x \parallel b_1) \parallel h(a_2 \parallel x \parallel b_2) \parallel h(a_3 \parallel x \parallel b_3) \parallel \dots \parallel h( a_k \song song x \song song b_k)$

$a_i$ và $b_i$ là các tiền tố và hậu tố đã biết.

Nếu $h$ là MD2 hay MD4, sẽ mất bao nhiêu công sức để tìm tiền ảnh thứ hai cho $h'$?

Nói rõ hơn: Đầu ra của $h'$ tương đối dài $k$ lâu hơn nhiều lần so với đầu ra của $h$.

Các câu trả lời cho cùng một câu hỏi nhưng với hàm băm mật mã thậm chí còn yếu hơn, cũng có thể được quan tâm. Nhưng không yếu như tổng kiểm tra.

Ngây thơ tôi đã nghĩ rằng nếu nó đòi hỏi $2^n$ làm việc để tìm hình ảnh thứ hai của $h$ sau đó nó yêu cầu $2^{kn}$ làm việc để tìm hình ảnh thứ hai cho $h'$. Vì bạn cần tìm một công việc cụ thể $x$ hình ảnh tiền đề thứ hai hài lòng đó cho tất cả $h(a_i \parallel x \parallel b_i)$. Nhưng có lẽ có một cách nhanh hơn.