Skip to main content

Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
177 votes
7 answers
139k 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 ...
Hello World's user avatar
  • 1,887
128 votes
7 answers
241k 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")?
user avatar
110 votes
3 answers
130k 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-...
ninesalt's user avatar
  • 1,235
68 votes
2 answers
25k 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 '...
BadHorsie's user avatar
  • 813
56 votes
11 answers
22k 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 ...
James Kumar's user avatar
52 votes
2 answers
15k 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?
Andrew Tomazos's user avatar
49 votes
1 answer
40k 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}...
ritch's user avatar
  • 593
46 votes
1 answer
7k 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 ...
otus's user avatar
  • 32.2k
43 votes
4 answers
43k 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 ...
Theodor Kleynhans's user avatar
42 votes
2 answers
34k 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$?
Pacerier's user avatar
  • 1,265
41 votes
4 answers
61k 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-...
M D P's user avatar
  • 529
41 votes
3 answers
51k 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?
John Gietzen's user avatar
  • 1,505
39 votes
2 answers
59k 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 ...
user93353's user avatar
  • 2,295
37 votes
3 answers
8k 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 ...
TripeHound's user avatar
35 votes
2 answers
28k 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 ...
Rob van Laarhoven's user avatar
32 votes
3 answers
6k 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 ...
SDL's user avatar
  • 1,887
31 votes
2 answers
9k 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: ...
Nathan.Mariels's user avatar
31 votes
1 answer
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 ...
e-sushi's user avatar
  • 18k
28 votes
7 answers
11k 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, ...
Michael Goldshteyn's user avatar
28 votes
1 answer
3k 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 ...
Maarten Bodewes's user avatar
  • 93.3k
27 votes
2 answers
53k 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 ...
benj's user avatar
  • 371
26 votes
1 answer
21k 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 ...
Max's user avatar
  • 407
25 votes
4 answers
14k 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 ...
Nick wheatley's user avatar
23 votes
2 answers
11k 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, ...
rapadura's user avatar
  • 341
23 votes
1 answer
5k 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 ...
Cyan's user avatar
  • 363
22 votes
4 answers
3k 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. ...
bnsh's user avatar
  • 323
22 votes
1 answer
14k 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 ...
Dingo13's user avatar
  • 2,867
22 votes
1 answer
21k 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-...
Ari Sweedler's user avatar
20 votes
3 answers
1k 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-...
fgrieu's user avatar
  • 142k
19 votes
5 answers
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 ...
Paul's user avatar
  • 193
19 votes
2 answers
24k 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 ...
Peter's user avatar
  • 301
19 votes
1 answer
2k 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 something ...
mti's user avatar
  • 655
18 votes
1 answer
12k 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-...
kelalaka's user avatar
  • 49k
18 votes
1 answer
5k 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 ...
Akhil F's user avatar
  • 285
18 votes
1 answer
6k 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 ...
hsalin's user avatar
  • 485
18 votes
1 answer
21k 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^{...
lxgr's user avatar
  • 1,788
17 votes
3 answers
13k 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 ...
adi's user avatar
  • 175
17 votes
4 answers
5k 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), ...
Thaina's user avatar
  • 293
17 votes
2 answers
10k 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? ...
Xeoncross's user avatar
  • 663
16 votes
1 answer
4k 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 ...
QWASH's user avatar
  • 171
16 votes
2 answers
27k 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 ...
El Ronnoco's user avatar
16 votes
4 answers
5k 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?. ...
Rohith K D's user avatar
15 votes
7 answers
5k 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 ...
Mys_721tx's user avatar
  • 253
15 votes
2 answers
3k views

Mixing algorithms for password hashing good or bad?

So I've come across the following algorithm for hashing passwords ...
Luke's user avatar
  • 153
15 votes
2 answers
3k 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 ...
lxgr's user avatar
  • 1,788
14 votes
2 answers
11k views

Is PBKDF2-HMAC-SHA1 really broken?

I just read through this article which demonstrates practical (and seemingly trivial) collisions in PBKDF2-HMAC-SHA1, and provides a few examples of collisions. Am I missing something here? Is PBKDF2-...
Polynomial's user avatar
  • 3,527
14 votes
1 answer
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 ...
Luke's user avatar
  • 339
14 votes
2 answers
13k views

128 bit hash with least chance of collision?

I'm building a storage system for JSON documents where they are looked up on a 128 bit key. These JSON documents have a timestamp within them, but apart from that are user-entered data. These JSON ...
Max's user avatar
  • 275
14 votes
0 answers
226 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 ...
user avatar
13 votes
3 answers
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. ...
Maarten Bodewes's user avatar
  • 93.3k

1
2 3 4 5
15