255 votes

Why can't we reverse hashes?

Take a simple mathematical operation like addition. Addition takes 2 inputs and produces 1 output (the sum of the two inputs). If you know the 2 inputs, the output is easy to calculate - and there's ...
user avatar
  • 2,154
132 votes

How do hashes really ensure uniqueness?

The simple answer is that hashes don't ensure uniqueness. Very broadly, hashes behave like "deterministic random numbers" – deterministic in the sense that hashing the same data always ...
user avatar
66 votes
Accepted

Second pre-image resistance vs Collision resistance

The difference is in the choice of $m_1$. In the first case (second preimage resistance), the attacker is handed a fixed $m_1$ to which he has to find a different $m_2$ with equal hash. In particular,...
user avatar
  • 10.9k
60 votes
Accepted

How can hashes be unique if they are limited in number?

how can for example SHA-256 be unique if there is only a limited number of them?! Where your issue occurs is that they're not unique. It's just very improbable that they'll reoccur. Unique in ...
user avatar
  • 13.8k
57 votes

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

Just to show you how easy it is today to create collisions on MD5: One could create collisions using Marc Steven's HashClash on AWS and estimated the the cost of around $0.65 per collision. ...
user avatar
  • 731
54 votes
Accepted

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

Actually SHA-1 has been "officially insecure" for a longer time, since an attack method was published in 2011. The 2017 collisions was just the first known case of actually running the attack. But ...
user avatar
52 votes
Accepted

Does "Shattered" actually show SHA-1-signed certificates are "unsafe"?

Yes, SHA1-signed certificates are unsafe. The SHAttered paper is instructive. From the introduction: The MD-SHA family of hash functions is the most well-known hash function family, which ...
user avatar
39 votes

Why can't we reverse hashes?

Cryptographically secure hashes were specifically build to (among other things) make what you're asking hard! Now, you could try to create an appropriate dictionary of all hashes, hoping to find ...
user avatar
  • 17.3k
38 votes
Accepted

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'$?

As you correctly observed, for any function $H\colon \{0,1\}^\ast\to\{0,1\}^n$ collisions must exist, simply because $\{0,1\}^\ast$ is an infinite set and $\{0,1\}^n$ is finite. One could define "hash ...
user avatar
  • 10.9k
35 votes
Accepted

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

Define $H(x) = \operatorname{SHA-256}(x) \mathbin\| 1$; that is, append a single 1 bit to SHA-256. Can you find a collision under $H$? Does $H$ have anything resembling uniform distribution? This ...
user avatar
34 votes
Accepted

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

Birthday problem for cryptographic hashing, 101. Let $p_n$ be the probability of collision for a number $n$ of random distinct inputs hashed to $k$ possible values (that is, probability that at least ...
user avatar
  • 122k
34 votes
Accepted

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

The answer is "not safe". But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice. Google found one collision based on some existing, ...
user avatar
32 votes
Accepted

What is a "freestart collision"?

Definition In the Damgard-Merkle construction for hash functions the compression function takes as input: a message block and a chaining value. For the very first block there is not previous "...
user avatar
  • 3,225
32 votes

Fixed point of the SHA-256 compression function

SHA-256 is based on a Davies–Meyer compression function. Easy to find fixed-points are a known property of this construction. A notable property of the Davies–Meyer construction is that even if the ...
user avatar
32 votes

Does "Shattered" actually show SHA-1-signed certificates are "unsafe"?

The existence of the SHAttered result is not, I think, in itself a surprise: everyone knows that in theory you can create two streams of bytes that hash to the same value. Google's achievements (which ...
user avatar
  • 84.5k
32 votes

How do hashes really ensure uniqueness?

Firstly, some definitions; Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to ...
user avatar
  • 42.9k
31 votes
Accepted

Why is HMAC-SHA1 still considered secure?

In the first section of this answer I'll assume that through better hardware or/and algorithmic improvements, it has become routinely feasible to exhibit a collision for SHA-1 by a method similar to ...
user avatar
  • 122k
31 votes

How can hashes be unique if they are limited in number?

You are right, hashes won't be all unique as you already have shown. The important part are practical collisions - how many SHA-512 hashes can the whole earth generate in its lifetime? Definitely much ...
user avatar
  • 3,820
30 votes
Accepted

Cycles in SHA-256

$\text{SHA256}$ is designed to behave as a random function. Under that assumption, it is expected that for most 256-bit $v$, there is no positive integer $n$ with $\text{SHA256}^n(v)$ equal to $v$. ...
user avatar
  • 122k
29 votes
Accepted

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

a. No such double hashing doesn't do a bit of good. Anything which collides after a single hash will definetly collide after a double hash. It preserves all collisions and adds new ones. We might ...
user avatar
  • 10.4k
26 votes
Accepted

SHA-256 "almost unique"?

Theoretically, since the domain of SHA-256 contains $2^{2^{64}-1}$ different messages and the value set only contains $2^{256}$ different message digests, there must exist at least one possible output ...
user avatar
26 votes
Accepted

Mixing algorithms for password hashing good or bad?

Does this look like it's done by someone who knows what they're doing or is it just a case of someone throwing all the algorithms they find together and hoping it's a good solution? This is obviously ...
user avatar
25 votes

Why can't we reverse hashes?

Strictly speaking, you can, and it stands to reason that you can. A SHA-1 hash has $2^{160}$ possible values. If we just consider $100$ byte binary plaintexts, well, there are $2^{800}$ possible ones ...
user avatar
  • 351
24 votes
Accepted

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

With the definitions that a function $F$ is collision-resistant when a [computationally bounded] adversary can't [with sizable odds] exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$; first-preimage-...
user avatar
  • 122k
24 votes
Accepted

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

Does this bias the hash in any way? We want the avalanche criteria on the output bits, that is a change in the any of input bit must randomly affect half of the output bits. Each bit of the hash ...
user avatar
  • 42.9k
23 votes
Accepted

What makes SHA-256 secure?

It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core. Basically what you are asking is identical to ...
user avatar
22 votes

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

Two different strings in hex format: ...
user avatar
  • 587
22 votes
Accepted

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

Hardened SHA-1 detects collisions built of a certain form, If someone were to find a collision using brute-force birthday attack (currently not feasible) the detection would not work. The vectors are ...
user avatar
  • 10.4k
22 votes
Accepted

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

SHA-1 in itself was never safe for password hashing. The hash algorithm itself doesn't have a work factor parameter nor does it have a salt as input. These are requirements for run-of-the-mill ...
user avatar
  • 84.5k

Only top scored, non community-wiki answers of a minimum length are eligible