# Tag Info

1

Theoretically, since the domain of SHA-256 contains $2^{2^{64}-1}$ different messages and the value set only contains $2^{256}$ different message digests, there must exist at least one possible output that has more than one possible pre-image. Another important point is that SHA-256 is a deterministic function. This means that if you hash the same message ...

0

Depends on how you define the function. A perfect hash function is a bijection from an input set onto a set of integers. However, that set of integers is not necessarily a continuous range, unless you have a minimal perfect hash function. So if you define the function as mapping a particular set to e.g. $\mathbb{N}$ or $[1, n]$ where $n$ is larger than the ...

1

The injective hash function wikipedia referes to is not a secure hash function for cryptographic purposes. It is a hash function used for fast database access. An ideal secure hash function is a random oracle and a random oracle is not injective with very high probability.

2

No, it is not always bijective. A perfect hash guarantees that no two inputs (from the set of valid inputs) collides, so it is clearly a 1 to 1 mapping. However, in the case where the output range contains more possible values than there were valid inputs, there will be outputs which do not map back to inputs. hence it is not bijective. If you restrain ...

0

Assume we are given a one-way function $f: \{0,1\}^m \rightarrow \{0,1\}^n$. Now consider the function $f': \{0,1\}^{m+1} \rightarrow \{0,1\}^n$ that simply applies $f$ to the first $m$ input bits and ignores the last bit. This function is still one-way / preimage resistant as a preimage finder $A$ for $f'$ immediately leads a preimage finder $A'$ for $f$ ...

0

No, the implication is wrong. Pre-image resistance means that it is not possible to calculate a pre-image from the image alone. But this does not exclude the existence of an algorithm, which calculates a second pre-image, given the image and the first pre-image.

0

SHA-1 is not a perfect hash function for the input set that is identical to the output set. Moreover, it is not designed to be one. So basically we can see the output of SHA-1 as a random bit string. SHA-1 and modern hashes simply rely on the output size to be reasonably sure that there won't be any collisions; it simply takes to long - on average - to ...

1

No. And it's probably a good thing that that's not the case. All cryptographic hashes (inc. SHA-1) are designed to have no obvious correlation between their input and output. If there is too much of a correlation, then they are considered broken. If each string of 160 bits produced a different output, that would be a correlation. That would also mean that ...

5

The first publication of an MD5 collision was on 17-Aug-2004 17:44 UTC on the eprint archive server: Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (third version). The results where fresh: the authors had just corrected IV endianness, that they got reversed in two earlier versions. Like 8 ...

5

I don't understand why this is important, but just want to note that the collision was first presented at the rump session at CRYPTO 2004, and was then later published. The earliest time-stamp is an ePrint report by Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu, called Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. The date is ...

7

Even though Dobbertin could not provide a real collision of MD5, I would say that Hans Dobbertin first publicly described MD5 collision(s) in "The Status of MD5 After a Recent Attack" (PDF) – that was in 1996. To the best of my knowledge he was one of the first who recommended to no longer use MD5 when collision-resistance is needed/expected/required. On ...

3

A random 128 bit value has a tiny ($2^{-85}$) probability of being a perfect cube, and so that doesn't look like a viable approach. And, you can't control the output of MD5, and so it'll give you effectively random values. A better way may be to collect a large number of signatures (with their messages); that is, $S_i = M_i^3 \bmod N$ values (where $M_i$ ...

Top 50 recent answers are included