Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
709
questions
173
votes
6
answers
129k
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 ...
- 1,847
127
votes
7
answers
223k
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")?
Adban
99
votes
3
answers
116k
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-...
- 1,133
67
votes
2
answers
24k
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 '...
- 803
57
votes
11
answers
21k
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 ...
- 695
50
votes
2
answers
14k
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?
- 637
48
votes
1
answer
37k
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}...
- 583
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 ...
- 31.9k
42
votes
4
answers
41k
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 ...
42
votes
4
answers
57k
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-...
- 539
40
votes
2
answers
33k
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$?
- 1,245
40
votes
3
answers
48k
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?
- 1,495
38
votes
2
answers
56k
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 ...
- 2,167
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 ...
- 473
33
votes
2
answers
26k
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 ...
32
votes
3
answers
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 ...
- 1,867
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:
...
- 319
30
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 ...
- 17.7k
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, ...
27
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 ...
- 91.2k
26
votes
2
answers
49k
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 ...
- 361
25
votes
1
answer
18k
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 ...
- 397
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 ...
- 363
23
votes
2
answers
10k
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, ...
- 341
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. ...
- 323
22
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 ...
- 353
21
votes
1
answer
13k
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 ...
- 2,827
21
votes
1
answer
18k
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-...
- 323
20
votes
3
answers
964
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-...
- 137k
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 ...
- 193
19
votes
1
answer
1k
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 ...
- 529
19
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^{...
- 1,778
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-...
- 46.5k
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 ...
- 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 ...
- 475
17
votes
4
answers
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), ...
- 293
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 ...
- 175
17
votes
2
answers
23k
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 ...
- 281
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? ...
- 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 ...
- 171
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?. ...
- 263
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 ...
- 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
...
- 153
14
votes
2
answers
26k
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 ...
- 243
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-...
- 3,517
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 ...
- 339
14
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 ...
- 1,778
14
votes
0
answers
220
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 ...
user991
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. ...
- 91.2k
13
votes
2
answers
12k
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 ...
- 265