Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
150
questions
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
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,847
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
9
votes
1
answer
2k
views
Security levels in NIST Post-quantum project: e.g. AES-128 vs SHA-256
In an article about NIST Post-quantum Standardization project I read about the security criteria of the proposed schemes and there was this table (Level I lowest security, level V highest):
Level I: ...
- 167
36
votes
2
answers
53k
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,211
39
votes
3
answers
46k
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,485
15
votes
7
answers
4k
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
123
votes
7
answers
214k
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
8
votes
1
answer
4k
views
How hard is it to generate a simultaneous MD5 and SHA1 collision?
I was recently reading that MD5 is "broken" because it's pretty easy to generate collisions (like 2^(L/2)). And the SHA1 (theoretically) fares no better. The ...
- 435
0
votes
2
answers
2k
views
What is the probability of any two users generating the same 128, 256, 2048 bit key?
There are some protocols that require the user to generate some random key locally (client-side) with no server authority to "approve" or "reject" their key and are based on the assumption that it's ...
- 21
49
votes
2
answers
13k
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?
- 627
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
24
votes
4
answers
13k
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 ...
- 353
5
votes
1
answer
1k
views
Is there are a metric based on collisions to compare bad hash functions?
Bad hash functions are not so perfect as in the "general collision probability" hypothesis... And a general concept of "collision resistence" not need the constraint of independence between the ...
- 193
170
votes
6
answers
124k
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,817
56
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 ...
- 685
20
votes
3
answers
912
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-...
- 132k
18
votes
1
answer
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 ...
- 285
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
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-...
- 45.7k
17
votes
2
answers
9k
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
11
votes
2
answers
3k
views
How many trials does it take to break HMAC-MD5?
I know that you can find collision in MD5 with $2^{64}$ trials using Birthday paradox. Now everyone is saying that HMAC-MD5 is significantly more secure. How can I quantify this security? My question ...
- 213
9
votes
2
answers
2k
views
Keys in HMAC and NMAC
I'm quite new to this topic and have several questions concerning HMAC and NMAC:
Why does NMAC need two keys? How can it be attacked if we just used some sort of initialization vector instead of the ...
- 193
45
votes
1
answer
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 ...
- 31.8k
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
21
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 ...
- 343
20
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,797
17
votes
2
answers
22k
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
12
votes
1
answer
3k
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 ...
- 763
9
votes
3
answers
3k
views
Are there MD5 collisions for inputs of different length?
There are many examples of MD5 collisions (some of them can be found here Are there two known strings which have the same MD5 hash value?). But as far as I know two inputs should have the same length ...
- 191
97
votes
3
answers
109k
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,113
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
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 ...
- 519
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. ...
- 89.2k
11
votes
2
answers
4k
views
Is HMAC-MD5 still secure for commitment or other common uses?
MD5 collisions have been out for some time. In spite of this, HMAC-MD5 is still secure for authenticating data1. This illustrates a strength of the HMAC construction, it does not require that the hash ...
- 38.2k
8
votes
2
answers
1k
views
What are other good attack examples that use the hash collision?
When we consider the security of a cryptographic hash function with $n$ bit output, we simply say that it must have at least $\mathcal{O}(2^{n/2})$-time security against the (generic) collision attack ...
- 45.7k
1
vote
2
answers
2k
views
Does the double-hash H(H(x)) have greater collision probability than H(x)?
Let $H$ be a collision resistant hash function and $P_c[H](S)$ the collision probability about a sample set $S$ of input elements (eg. random numbers). It increases with double hash? That is, $P_c[H\...
- 193
26
votes
2
answers
46k
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
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
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
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,768
11
votes
1
answer
1k
views
Collision resistance of hash function built on modular exponentiation
Consider the following hash function family for hashing integers:
$Gen(1^k)$: generate 2 $k$-bit primes p,q. Let $n = pq$. Choose random $y \rightarrow QR_n$ and output $n,y$.
$H_{(n,y)}(x) = y^x \...
- 394
9
votes
4
answers
5k
views
Compare two hashes with different salt
I'm storing the salted hash of a credit card number in a database. What I'd like to be able to do is determine if two different entries in the same database correspond to the same credit card.
...
- 193
9
votes
3
answers
1k
views
What is the reason to separate domains in the internal hash algorithm of a merkle tree hash?
From rfc 6962 It is stated that:
Note that the hash
calculations for leaves and nodes differ. This domain separation is
required to give second preimage resistance.
That means that whenever the ...
- 6,062
8
votes
3
answers
2k
views
What was the first MD5 collision ever constructed?
We all know that MD5's collision resistance is severly broken.
But when thinking of "random" strings with great cryptographic importance I've come up with NIST's curve seeds and MD5 collisions. But ...
- 45.3k
6
votes
1
answer
6k
views
Pre-image attack on MD5 hash
I read somewhere MD5 is broken in terms of collision, but I am wondering if it is broken in terms of pre-image resistance?
Given a hash of Md5, is it possible to find the original message of it? If ...
- 81
6
votes
2
answers
484
views
What is the complexity of finding SHA-1 collisions?
Given the recent news about SHA-1 collisions, what is the complexity of finding a SHA-1 collision?
Marc Steven's HashClash is still detailing about 260. Does the previous complexity still hold?
user10496
4
votes
1
answer
1k
views
Does Composition of compressing Collision Resistant Hash Functions $H^{*}=H_2(H_1(x))$ is Collision Resistant?
I'm trying to solve the following problem:
Given two CRHF $H_1:2^{4n}\to2^{2n}$, $H_2:2^{2n}\to 2^n$, construct the following hash function $H^{*}=H_2(H_1(x))$ compressing from $2^{4n}\to 2^n$.
We ...
- 43
3
votes
2
answers
1k
views
Are there attacks that break collision resistance but not preimage resistance?
Are there any examples of attacks on hash functions which:
break collision resistance and second preimage resistant, or
break collision resistance and preimage resistant?
I have looked at Rogaway's ...
- 33
47
votes
1
answer
35k
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}...
- 573