On the collision and preimage security of MDC-4 in the ideal cipher model

摘要: We present a collision and preimage security analysis of MDC-4, 24-years-old construction for transforming an n-bit block cipher into 2n-bit hash function. start with MDC-4 based on one single cipher, prove that any adversary query access to the underlying requires at least $$2^{5n/8}$$ queries (asymptotically) find collision. For resistance, we surprising negative result: target image same left right half, full function can be found in $$2^n$$ queries. Yet, restricted images different halves, $$2^{5n/4}$$ are required preimage. Next, consider two independent ciphers, model is less general but closer original design, bound apply compression design. With these results, first formally confirm offers higher level provable compared MDC-2.