4
$\begingroup$

Let's say we have input data X and a hashing algorithm H that produces 256-bits of output (e.g. SHA256).

Now, let's take a second hash function G that produces 128 or more bits of output (say RIPEMD128 or SHA1). If we define our final hash function L := sub128(H(q)) + sub128(G(q)), where sub128 takes first 128 bits of the result and + is concat, so that the result is 256 bits again.

Is it now more, less, or about the same difficulty to Y such that L(X) = L(Y) compared to how difficult it is to find Y such that H(X) = H(Y)?

$\endgroup$
5
$\begingroup$

Actually, I believe that both sub128(sha256(q)) + sha128(sha1(q)) and sub128(sha256(q)) + sha128(ripemd128(q)) allow a forgery attack in about $O(2^{70})$ time; hence it would appear to be weaker than SHA-256.

Here's how it works: for both SHA1 and RIPEDM128, there are known ways to find collisions in about $O(2^{63})$ time or so; there are ways that take an intermediate state, and find two different message segments of the same length that both result in the same intermediate state after processing. So, what we do is find 64 consecutive such different message segments; this gives us a $2^{64}$ wide collision; that is, $2^{64}$ distinct messages that all result in the same hash. The effort involved is 64 times the basic collision attack, or about $O(2^{69}) time.

Once we have $2^{64}$ messages that are all collisions for SHA1/RIPEMD128 (and hence are collisions over the first 128 bits in the case of SHA1), we SHA-256 hash all of them; with good probability, we'll find a pair that collides in the first 128 bits of the SHA-256 hash.

This pair is your collision over your $L$ function...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.