People who code: we want your input. Take the Survey

Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
151
votes
6answers
94k 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 ...
105
votes
7answers
170k 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")?
72
votes
1answer
77k 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-...
57
votes
2answers
20k 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 '...
53
votes
11answers
19k views

How do hashes really ensure uniqueness?

This might seem an impractical and unnecessary conversation, but I feel it's something I need to clarify. Especially, as I just got my first developer job in a blockchain startup. So hashes are said ...
45
votes
2answers
11k 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?
45
votes
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 ...
39
votes
2answers
29k 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$?
38
votes
4answers
36k 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 ...
38
votes
1answer
28k views

Second pre-image resistance vs Collision resistance

From Wikipedia: Second pre-image resistance Given an input $m_1$ it should be difficult to find another input $m_2$ such that $m_1$ ≠ $m_2$ and $\operatorname{hash}(m_1) = \operatorname{hash}...
36
votes
4answers
40k 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-...
36
votes
3answers
7k 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 ...
36
votes
3answers
38k 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?
33
votes
2answers
43k views

Why is HMAC-SHA1 still considered secure?

This Q & A https://security.stackexchange.com/questions/33123/hotp-with-as-hmac-hashing-algoritme-a-hash-from-the-sha-2-family says that the security of HMAC-SHA1 does not depend on resistance to ...
31
votes
2answers
19k views

How secure is SHA1? What are the chances of a real exploit?

I read that, in February 2017, a SHA1 collision was calculated for the first time. This, and earlier theoretical proof, means that SHA1 is officially cryptographicaly insecure. But, when using SHA1 in ...
31
votes
3answers
5k views

Are common cryptographic hashes bijective when hashing a single block of the same size as the output?

It's been said that CRC-64 is bijective for a 64-bit block. It the corresponding statement true for typical cryptographic hashes, like MD5, SHA-1, SHA-2 or SHA-3? For example, would SHA-512 be ...
29
votes
2answers
8k views

Fixed point of the SHA-256 compression function

SHA256 Free Start Self Collision (Full 64 rounds) IVec: 72BF9EF1 27B82DFB F298F3B7 22B6C32C 18A54860 4C032D91 ADD7B85B 7ED1A4AC Block: ...
27
votes
1answer
2k views

Is it possible to actually verify a “sponge function” security claim?

When using a “sponge function” to create a cryptographic hash, we can look at the flat sponge claim, which flattens the claimed success probabilities of all attacks using a single parameter: the ...
26
votes
7answers
10k views

Is calculating a hash code for a large file in parallel less secure than doing it sequentially?

I would like to improve the performance of hashing large files, say for example in the tens of gigabytes in size. Normally, you sequentially hash the bytes of the files using a hash function (say, ...
24
votes
1answer
2k views

What is hardened SHA-1, how does it work and how much protection does it offer?

From the shattered website: You can use the online tool above to submit files and have them checked for a cryptanalytic collision attack on SHA-1. The code behind this was developed by Marc Stevens ...
23
votes
2answers
35k 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 ...
22
votes
1answer
14k 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 ...
22
votes
4answers
11k views

How many RSA keys before a collision?

I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a ...
21
votes
4answers
2k views

Cycles in SHA-256

Let's say I start with a particular 256 bit value. Call this $v$. I then hash that value, and get another 256 bit value. Call this $\text{SHA256}(v)$. I take this value and get another 256 bit value. ...
21
votes
2answers
8k views

What makes SHA-256 secure?

For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem. What makes SHA-256 and similar hash functions, of the same family, ...
20
votes
1answer
4k views

From hash to Cryptographic hash

After reading some excellent papers on SipHash, I understood that good non-cryptographic hashes such as MurmurHash and CityHash are not secure for MAC usage, due to a certain type of DDos attack ...
19
votes
3answers
767 views

Collision or second preimage for the ChaCha core?

Daniel J. Bernstein's ChaCha core is an evolution of the Salsa20 core. Both are functions over the set of 512-bit bitstrings, partitioned as sixteen 32-bit words. Can we exhibit collisions, or second-...
18
votes
5answers
3k views

How many hex digits do I need to compare when manually checking hash functions?

I sometimes run sha256sum on large files after transferring them from one place to another, and will just skim the hash output to verify it's correct. But, I usually just look at the first/last 5 or 6 ...
18
votes
1answer
10k 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 ...
18
votes
1answer
5k 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 ...
18
votes
1answer
20k views

How does a birthday attack on a hashing algorithm work?

A "normal", brute-force attack on a cryptographic hashing algorithm $H$ should have a complexity of about $2^{n}$ for a hash algorithm with an output length of $n$ bits. That means it takes about $2^{...
17
votes
3answers
11k views

After Google's collision attack, is RSA-SHA1 signature still safe?

Google succeeded to get a collision in SHA-1 last year in an attack called shattered. Does this fact make certificates based RSA-SHA1 Signature risky for creating fraud certificates? If RSA-SHA1 ...
17
votes
3answers
4k 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), ...
17
votes
1answer
4k views

What are the consequences of removing a single byte from a sha256 hash?

I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash. Sha256 would meet this ...
17
votes
2answers
8k 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? ...
16
votes
1answer
3k views

If a hash function $H$ is collision resistant, is it true that $H(x)\neq H(x')$ for all messages $x, x'$ with $x \neq x'$?

I am puzzled with a question that seems to be based on theory. If there is a collision resistant hash function (since it is not possible for a hash function to be collision free, this is a ...
16
votes
1answer
11k views

In 2020, SHA-1 practically broken in chosen-prefix collision (CP-collision). Can double SHA-1 hashing prevent CP-collision?

In a recent study SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust by Gaëtan Leurent and Thomas Peyrin. 2020, they showed the first practical chosen-...
15
votes
7answers
3k 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 ...
15
votes
2answers
3k views

Mixing algorithms for password hashing good or bad?

So I've come across the following algorithm for hashing passwords ...
15
votes
2answers
20k 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 ...
15
votes
4answers
4k 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?. ...
14
votes
1answer
2k 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 ...
14
votes
1answer
11k views

Are there any well-known examples of SHA-256 collisions?

The popularity of SHA-256 as a hashing algorithm, along with the fact that it has 2256 buckets to choose from leads me to believe that collisions do exist but are quite rare. Are there any well-...
14
votes
1answer
780 views

Overview of relations between cryptographic primitives?

Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives? More specifically, I am looking for ...
13
votes
3answers
1k 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. ...
13
votes
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 ...
13
votes
0answers
189 views

Space complexity of quantum collision search?

Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below ...
12
votes
3answers
2k views

SHA3-255, one bit less

I need a SHA3-255 or 511. What if I simply truncate a standard SHA3-256 or 512? Apart from the doubled probability of hash collision, are there any other things I should be aware of? I could also ...
12
votes
2answers
19k views

SHA-256 “almost unique”?

I have seen numerous references on the internet of people describing SHA-256 as generating an "almost unique" hash. Exhibit A. there are more. Is there some mathematical basis to the almost ...
12
votes
1answer
313 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?

1
2 3 4 5
12