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

learn more… | top users | synonyms (1)

41
votes
1answer
4k 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 ...
40
votes
7answers
37k 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")?
34
votes
1answer
8k views

No SHA-1 collision? Yet SHA-1 is 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 than how can SHA-1 be considered broken?
27
votes
4answers
23k 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 ...
25
votes
1answer
6k 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 '...
19
votes
2answers
11k 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$?
17
votes
7answers
4k 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, ...
17
votes
2answers
2k 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 ...
16
votes
3answers
9k 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
1answer
803 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 ...
13
votes
1answer
2k 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 ...
12
votes
1answer
835 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? ...
11
votes
2answers
4k 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? ...
10
votes
2answers
3k 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 ...
10
votes
3answers
657 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. ...
10
votes
1answer
3k 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 ...
10
votes
2answers
400 views

Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes?

I can't get an intuitive understanding of why it's $2^{(\frac{n}{2})}$ and not $2^n$, where $n$ is the number of bits of which the key consists.
10
votes
3answers
320 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-...
10
votes
1answer
8k 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^{...
9
votes
2answers
7k 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 ...
9
votes
1answer
2k 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 ...
9
votes
1answer
1k views

Change in probability of collision when removing digits from MD5 hexadecimal hash values

I am aware that MD5 has a known collision vulnerability and should not be relied upon when uniqueness is required, but in the environment I am working on I only have access to MD5 hash function. ...
9
votes
1answer
273 views

Non-iterative cryptographic hash functions

Consider the following cryptographic hash function $H$ which maps a message $m$ of variable size to $b$ bits: $$H:\{0,1\}^{*} \mapsto \{0,1\}^b$$ $$y = H(m) = SPRP(IV||m||padding)\mid_{b}$$ , where: ...
8
votes
1answer
4k 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{...
8
votes
2answers
6k 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 ...
8
votes
0answers
228 views

Are there any practical attacks that create a printable chosen prefix MD5 collision?

I would like to create two ASCII text messages with the same MD5. Is this possible? If not, is there a similar but less strict attack that could work? Or to rephrase my last question: what are the ...
7
votes
3answers
301 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 ...
7
votes
2answers
543 views

Is SHA-1 still practically secure under specific scenarios?

It is conjectured that SHA-1 has been broken from the "research" perspective but no in real world. That is that there is an algebraic attack that explores weaknesses on its algebraic construction. The ...
7
votes
2answers
681 views

Toy hash algorithm that can be broken

I'm looking for a toy hash function, where the idea is to have high school students break (i.e. find a collision) a hash function by hand, in order to teach them how one way functions and hashing ...
7
votes
1answer
1k views

Can I find two specific words with the same md5 hash?

I want to find two strings containing special words like "yes" or "no", mixed with random characters, for which the MD5 hash is equal. An example of what I'm looking for: ...
7
votes
4answers
641 views

Can there be two hash functions without common collisions?

Is there a way to prove/create (or are there known hash functions) two hash functions that never have the same collision? I mean, like provable in way that someone who took one cryptography class in ...
7
votes
3answers
540 views

How many bits of hash are realistically needed for key verification?

Say I'm connecting to a web server secured with TLS but with a self-signed certificate. Accordingly, I call the owners of the server and ask them what SHA1 fingerprint they have. They start reading ...
7
votes
3answers
4k views

The difference between being not strongly collision resistant, and not weakly collision resistant?

So I understand the two concepts: (Strong) collision resistance: it is infeasible to find a pair $x \neq x'$ such that $h(x) = h(x')$ Weak collision resistance / 2nd-preimage resistance: for all $x \...
7
votes
2answers
643 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 ...
7
votes
1answer
2k views

Using an MD5 hash as a password

Suppose Alice is using a password prompt that only accepts up to 32 characters for any particular password. Memorization of long strings of random characters is not one of Alice's strengths, so she ...
7
votes
2answers
604 views

Finding hash almost-collisions

A few months ago, XKCD posted a challenge to find a plaintext which hashed (using Skein 1024 1024) to a specified value. Inputs were scored based on the hamming distance between the hash of the ...
7
votes
1answer
1k 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 ...
7
votes
1answer
474 views

Why is EdDSA collision-resilient with SHA-512?

In the Bernstein et al. paper about EdDSA, the authors claim EdDSA is resilient against collisions (i.e. it can still be secure even if the hash function used isn't collision-resistant), drawing on a ...
7
votes
1answer
61 views

Difficulty to find any preimages $a$ and $b$ for given $V$ so that $H(a) \oplus H(b) = V$?

Suppose I have the values $a$, $b$, and $V = H(a) \oplus H(b)$ with inputs $a \neq b$ and $H$ being SHA-224. None of these values are a secret. How secure is it to assume that no other possible values ...
7
votes
1answer
821 views

Implementation of Tao Xie and Denguo Feng's MD5 attack

It is well known that MD5 is completely broken today - however, to understand the theory behind the attacks I am looking for an implementation of the collision attacks described in the 2009 paper A ...
6
votes
2answers
1k views

Can the XOR of two non-collision-resistant hashes be collision resistant?

Suppose I have two hash functions, of which neither (or only one) is collision resistant, and I want to create a new hash function by taking the bitwise exclusive or (XOR) of the results of those two ...
6
votes
2answers
3k 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-...
6
votes
2answers
806 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 ...
6
votes
1answer
262 views

Can iterated hashing be used to mitigate collision and preimage weaknesses?

How much security does double hashing add regarding collisions and preimages? Is it helpful to iterate a hash function even more times than two? For example, can MD5 be fixed (in practice) by ...
6
votes
1answer
163 views

How can one detect if a hash function doesn't have a full image?

Suppose we have a hash function $H: \{0,1\}^* \mapsto \{0,1\}^n$, that doesn't get all the $n$ length bitstrings as a value for any input, but is otherwise secure. Can that fact be detected? For ...
6
votes
4answers
888 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. ...
6
votes
2answers
3k 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 ...
5
votes
5answers
1k 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 ...
5
votes
4answers
7k views

Is it fair to assume that SHA1 collisions won't occur on a set of <100k strings

I'm building a system that has to take file paths, and generate a unique name for each one. I'm planning on using SHA1 as the hash function. My question is: do I have to deal with possible collisions ...
5
votes
2answers
296 views

Do MD5's weaknesses affect Oplop?

Oplop is an algorithm that generates account-specific passwords from a master password and user-chosen nickname (typically username@domain). From the website: Concatenate the master password with ...