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
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 ...
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 ...
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. ...
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?
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 ...
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 ...
8
votes
1answer
1k 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: ...
-1
votes
2answers
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 ...
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?
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")?
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 ...
5
votes
1answer
961 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 ...
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 ...
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-...
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-...
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 ...
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 ...
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? ...
4
votes
1answer
3k 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 ...
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: ...
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 ...
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 ...
11
votes
1answer
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 ...
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 ...
10
votes
2answers
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 ...
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 '...
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 ...
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 ...
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. ...
7
votes
2answers
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 ...
1
vote
2answers
1k 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\...
10
votes
2answers
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 ...
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), ...
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-...
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 ...
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, ...
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 ...
11
votes
1answer
956 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 \...
9
votes
3answers
2k 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 ...
9
votes
4answers
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. ...
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 ...
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 ...
9
votes
3answers
892 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 ...
6
votes
2answers
387 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?
8
votes
3answers
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 ...
5
votes
1answer
4k 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 ...
4
votes
1answer
642 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 ...
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}...
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$?
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^{...