# Questions tagged [collision-resistance]

Difficulty of finding two different inputs that hash to the same value

460 questions
7answers
50k views

### Why can't we reverse hashes?

First off, I know hashes are 1 way. There are an infinite number of inputs that can result in the same hash output. Why can't we take a hash and convert it to an equivalent string that can be hashed ...
7answers
111k views

### Are there two known strings which have the same MD5 hash value?

Is there an example of two known strings which have the same MD5 hash value (representing a so-called "MD5 collision")?
2answers
15k views

### Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1?

I am from a web development background (I don't know an awful lot about cryptography or how the algorithms themselves work), so I am asking this question in simple terms. Consider a hash of the word '...
1answer
6k views

### What is a “freestart collision”?

In their work on SHA-1 collisions (cf. the EUROCRYPT-2016 paper “Freestart collision on full SHA-1” by Stevens, Karpman, and Peyrin) Stevens et al show that they are able to generate "freestart ...
2answers
10k views

### Why is SHA-1 considered broken?

Is there a known pair of distinct bit strings (A,B) such that SHA-1(A) == SHA-1(B)? If the answer is no, then how can SHA-1 be considered broken?
1answer
31k views

### Why haven't any SHA-256 collisions been found yet?

I've been thinking about this for a few days, a SHA-256 algorithm outputs 64 characters which can either be a lowercase letter or a number from 0-9. Which should mean that there are 64^36 distinct SHA-...
4answers
32k views

### Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?

I would like to maintain a list of unique data blocks (up to 1MiB in size), using the SHA-256 hash of the block as the key in the index. Obviously there is a chance of hash collisions, so what is the ...
2answers
24k views

### Are there any known collisions for the SHA (1 & 2) family of hash functions?

Are there any known collisions for the hash functions SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512? By that, I mean are there known values of $a$ and $b$ where $F(a) = F(b)$ and $a ≠ b$?
3answers
4k views

### Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?

Note: I am not advocating anyone continues using SHA1-signed certificates: they are dead as far as security is concerned and should no longer be used. I'm just trying to clarify my understanding of ...
3answers
25k views

### What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

What is "preimage resistance", and how can the lack thereof be exploited? How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?
4answers
17k views

### How can hashes be unique if they are limited in number? [duplicate]

I'm curious, how can for example SHA-256 be unique if there are only a limited number of them?! For clarification: how many MD5 hashes are there? $16^{32}$ MD5 hashes can be produced. $16^{64}$ SHA-...
1answer
19k views

1answer
7k views

### Does collision resistance imply (or not) second-preimage resistance?

I've seen contradictory results. Sometimes hash functions are collision-resistant but not necessarily second-preimage resistant. I've seen this kind of things in papers from Bart Preneel: “Security ...
1answer
4k views

### Three-way hash collision

According to the birthday paradox we need approximately $O(|T|^{1/2})$ samples from the tag-space to find a collision for a hash function $h:K\times M \to T$. But how many samples are needed to find a ...
2answers
3k views

### Mixing algorithms for password hashing good or bad?

So I've come across the following algorithm for hashing passwords ...
2answers
17k views

### What is the MD5 collision with the smallest input values?

I am interested in MD5 collisions for small input messages. The collision examples given at http://www.mscs.dal.ca/~selinger/md5collision/ show two different strings, where only a tiny amount of data ...
1answer
9k views

### What are the odds of collisions for a hash function with 256-bit output?

There are some related questions on the net but I did not understand their solutions. I am reading in a textbook about methods of finding a collision. It states to consider a collision for a hash ...
2answers
6k views

### Strength of multiple hash iterations?

Is it correct that increasing the iteration possibly decreases the cipher strength but increases the amount of time it would take to find the original hash values if using brute-force on a given hash? ...
2answers
21k views

### Is there a hash function which has no collisions?

Is there a hash function which has no collisions? To clarify: it would be some function which would produce variable-length output, and never produce the same output for differing input. It would ...
4answers
3k views

### Is using a broken SHA-1 for password hashing secure?

Recently the hashing collision issue of SHA-1 was discovered. Identical hash values for 2 separate PDF files were generated. Does that make SHA-1 any unsafe for using it only for password hashing?. ...
1answer
1k views

### Is Wikipedia's table about SHA-2 collisions correct?

I was looking a Wikipedia article on SHA-2, and the "Comparison of SHA functions" table seems to indicate that SHA-2 is less secure than SHA-1. Is this true, or is the table wrong / misleading? What ...
2answers
3k views

### Can we assume that a hash function with high collision resistance also means a highly uniform distribution?

I want to use a hash function to generate a random sequence from number 0-n. And so I would like to find a good function that results in values that are seemingly random (does not need to be secure), ...
3answers
866 views

### Counter mode secure hash algorithm

Ever since the SHA-3 competition, I've been wondering if it is possible to create a hash algorithm that is easier to parallelize. The current algorithms all seem to require building a tree of hashes. ...
6answers
2k views

### Is it theoretically possible to construct a string that contains its own hash value?

After saw the xkcd comic Self-Description, I wonder if it is theoretically possible to construct a self-descriptive string that contains its own hash value? Let's say the string's MD5 value is ...
1answer
256 views

### Why doesn't Wang's attack work on SHA-1?

Wang's (et al) differential attack works on MD5, MD4, RIPEMD and HAVAL. Why doesn't it work on SHA-1?
3answers
1k views

### Can there be two hash functions without common collisions?

Is there a way to prove/create (or are there known hash functions) two hash functions that never have the same collision? I mean, like provable in way that someone who took one cryptography class in ...
1answer
1k views

### What is a pseudo-collision attack?

In the context of cryptographic hash function collisions, what exactly is a pseudo-collision attack? E.g., pseudo-collisions are discussed here: Preimage and Pseudo-Collision Attacks on Step-Reduced ...
1answer
2k views

### Change in probability of collision when removing digits from MD5 hexadecimal hash values

I am aware that MD5 has a known collision vulnerability and should not be relied upon when uniqueness is required, but in the environment I am working on I only have access to MD5 hash function. ...
2answers
2k views

### Are cryptographic hash functions perfect hash functions?

For a cryptographic hash function and input values of shorter length than the hash function output, it's pretty obvious that there should be as few collisions as possible. But are there guaranteed to ...
1answer
2k views

### Why doesn't preimage resistance imply the second preimage resistance?

Let the preimage resistance be defined as »given a hash value $h$, it is hard to find any message $m$ such that $\operatorname{hash}(m)=h$«, and let the second preimage resistance be defined as »given ...
1answer
523 views

### Non-iterative cryptographic hash functions

Consider the following cryptographic hash function $H$ which maps a message $m$ of variable size to $b$ bits: $$H:\{0,1\}^{*} \mapsto \{0,1\}^b$$ $$y = H(m) = SPRP(IV||m||padding)\mid_{b}$$ , where: ...
1answer
605 views

### Are there any practical attacks that create a printable chosen prefix MD5 collision?

I would like to create two ASCII text messages with the same MD5. Is this possible? If not, is there a similar but less strict attack that could work? Or to rephrase my last question: what are the ...
2answers
706 views

### Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes?

I can't get an intuitive understanding of why it's $2^{(\frac{n}{2})}$ and not $2^n$, where $n$ is the number of bits of which the key consists.