# Tag Info

## New answers tagged collision-resistance

2

Generally, SHA-3 is build to offer $2^{n/2}$ collision resistance (and $2^n$ preimage resistance). You haven’t specified which SHA-3 you are talking about (SHA3-224/256/384/512), but even when looking at the smallest of them (SHA3-224) and assuming correct implementation, the chance of a collision is more of a theoretical nature. Talking about ...

0

Must the bit length of the hash value be long enough to cover N number of messages? Yes. Does it not simply make a perfect hash function as a specified lookup table for a set of predetermined message? Yes, but it is an efficient lookup table. If you used e.g. binary search for the lookup, you would need space proportional to the ...

2

How does a perfect hash function have collision-resistant in this case? Well, when we select a perfect hash function, we take as inputs a set of messages $M_1, M_2, M_3, ..., M_n$, and use them to select a hash function for which $H(M_i) \ne H(M_j)$ (if $i \ne j$) Now, according to the pigeon hole principle, the output of $H$ must be at least $\log_2 ... 14 Definition In the Damgard-Merkle construction for hash functions the compression function takes as input: a message block and a chaining value. For the very first block there is not previous "chaining value". Instead a particular value, called an initialisation vector (IV) is given. A freestart collision is a collision where the attacker can choose ... 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 ...

Top 50 recent answers are included