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

learn more… | top users | synonyms (1)

0
votes
1answer
64 views

Reducing size of hash function

If I have some data I hash with SHA256 as hash=SHA256(data) and then copy only the first 8 bytes of the hash instead of the whole 32 bytes. How easy is it to find a ...
2
votes
1answer
77 views

Hash “Preimage by product” resistance

Let H() be a hash function that achieves collision resistance as well as first and second preimage resistance. Let's equip the output set of H of a multiplicative group structure, more precisely a ...
0
votes
1answer
48 views

Hashing - Digital Signing and Trivial Stretching

Two very basic questions: 1. Digital Signing Why is it not possible to just simply replace the hash value from the request? Examples: ...
4
votes
1answer
221 views

How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?

Given a cryptographic hash function $h$, for example SHA256, how hard is it to find plaintexts $a,b,c$ such that $$h(a)\oplus h(b)=h(c) \text?$$
22
votes
6answers
15k 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")?
0
votes
1answer
71 views

How much work is required to detect multiple collisions for a hash function?

Assume an ideal hash function of output size n bits, detecting one collision requires approximately 2^(n/2) evaluations of the ...
4
votes
0answers
221 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 ...
3
votes
2answers
239 views

Is double hashing collision resistant?

Double hashing can surely provide more security than only one layer of hashing but does that necessarily mean it is more collision resistant? This question in a more mathematical form: If $H$ is a ...
1
vote
2answers
159 views

Are there cryptographic hash functions which do not have any collisions?

I've been studying digital signatures and hash functions recently, and I was wondering: Do hash functions exist which will never produce collisions?
6
votes
2answers
1k 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 ...
2
votes
2answers
72 views

Security concern about reducing hash value using modulo operation

As stated in the title, what I am looking for is information about a "technique" that I would like to use in some of my algorithms. Sometimes I need to map a hash function's result into a range of ...
3
votes
1answer
134 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) = ...
2
votes
1answer
274 views

Finding a collision for a hash function

I'm trying to find a collision for the following (modified) Merkle–Damgård hash function. Suppose we already have a hash function $h : \mathbb{Z}_2^{2·n} \to \mathbb{Z}_2^n$ for fixed length bit ...
2
votes
1answer
161 views

SHA-1 collision resistance

I'm researching on the SHA-1 algorithm and looking for reasons why it has fallen prey to differential cryptanalysis. I have read the research papers by Merc Stevens and Wang both of which describe how ...
1
vote
1answer
104 views

N way collision of hashes

For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$ where $\log_2(T)$ is length of hash output. Then, what would be the number of queries requried to find an $n$-collision ($H(A_1) = ...
3
votes
3answers
281 views

SHA1 Collisions - what about practical attacks?

I understand the theorical problem with hash collision but when it comes to practice, I get very confused. Suppose a attacker would like to forge a certificate (or any kind of strucutred piece of ...
3
votes
2answers
132 views

Collision in Merkle–Damgård without a collision in compression function

Is it possible to find a collision in Merkle–Damgård just by omitting the extra one bit that is appended to each input without having a collision in compression function?
1
vote
1answer
132 views

Hash collision using the leading 40-bits of SHA-1

I am trying to implement Floyd's cycle finding algorithm for finding a leading 40-bit hash collision in the SHA-1 algorithm. However, my code will not find a repetition even with 800,000,000 hashes. ...
2
votes
3answers
195 views

Does this guarantee a unique 32 bit Hash?

I came across some source code that loosely does the below in order to achieve a 32 bit hash. The input string is passed through MD5 to get 16 bytes Hash (as usual). Then the 16 bytes are split into ...
-3
votes
2answers
968 views

finding collision for truncated SHA1 hash output

Suppose we truncate only 40 bits of sha1 hash output.hence it is insecure.how can we find two message as input which gives first 40 bits of hash as same value i.e we have to find collision for first ...
4
votes
3answers
559 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 ...
0
votes
1answer
65 views
25
votes
1answer
6k 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?
6
votes
3answers
402 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 ...
2
votes
1answer
334 views

Hash collision resistance requirements for Lamport signatures

According to the original paper, Lamport one-time signature scheme uses two one-way functions: $F$ and $G$. The former one, $F$, is used to create a public key by hashing elements of the private key ...
2
votes
1answer
54 views

How can finding a collision help an attacker with tampering messages with HMAC

As stated in the HMAC RFC (RFC 2104): The strongest attack known against HMAC is based on the frequency of collisions for the hash function H. How can a collision benefit an attacker? I would ...
4
votes
2answers
110 views

Are variable-length crypto hash functions still susceptible to collisions?

I just recently learned that the SHA-3 finalist Keccak allows for variable length output. As the only answer to this question states, "[it] need to have an output length at least equal to the input ...
4
votes
1answer
152 views

Is hashing a list of hashes safe?

I have an arbitrary long list of hashes (e.g. git tree hashes), and I'm wondering by how much I am increasing the risk of hash collisions by condensing them into a single hash, like so: ...
4
votes
2answers
617 views

A patched SHA1 attempt for password verification

This is a classical scenario: For our web based authentication platform we have a username and a password field. User enters these values and presses Log In. The browser gathers the user data, ...
9
votes
1answer
2k 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 ...
2
votes
0answers
84 views

Can you help me understand this “Message Modification by Meet-in-the-Middle” related to Tiger Hash? [closed]

I found this paper that explains how to attack a reduced round tiger hash, but I'm having a hard time understanding some of the mathematical notation. Could someone explain the section "Message ...
15
votes
7answers
3k 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, ...
6
votes
1answer
631 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 ...
1
vote
1answer
150 views

SHA1 collision event probability after n iterations

There are String1 and String2 - some variables-strings. The probability of collision for different ...
2
votes
2answers
130 views

Is a collision attack possible on MD5 if message is known partially

Is it possible to find $m'$ such that $\operatorname{MD5}(m'||m_1)=\operatorname{MD5}(m_1||m_2)$ if I know $m_2$ and $\operatorname{MD5}(m_1||m_2)$? Is this a collision or a preimage attack? Also in ...
3
votes
2answers
407 views

Generate a unique 64 bit numeric database key from a string without collisions at $2^{32}$ birthday threshold?

What is the best way to generate a unique 64 bit numeric database key from a string? For example: if the string is a URL, you could generate a 64 bit key using SipHash or by truncating a SHA256 hash ...
5
votes
1answer
135 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 ...
2
votes
1answer
142 views

Probability for collisions of a one-way compression function

Given a one-way compression function $h:\{0,1\}^n \rightarrow \{0,1\}^m$ and an attacker that picks $x_1 \ldots x_t \in \{0,1\}^n$ (uniformly distributed), I have to show that the probability to find ...
2
votes
1answer
172 views

Is $H(x) = x^2 \bmod p$ pre-image resistant, second pre-image resistant and/or collision resistant

I have the function $H(x) = x^2\bmod p$ , where $p$ is a prime of length n bits and this function maps to the message $x$ to a n-bit hash value $H(x)$. I need to find out if it is pre-image ...
4
votes
1answer
119 views

Why has the sponge construction's generic collision finding attack a complexity of O(min(2^(-n/2) , 2^(-c/2)))?

I'm trying to learn about sponge function for creating hash functions and generic attacks on it. I'm looking for the collision finding attack scenario which leads to $O(\min(2^{-n/2} , 2^{-c/2}))$ ...
2
votes
0answers
45 views

space complexity of quantum collision search

Is there a known way to reduce the space complexity of quantum collision search beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below what ...
8
votes
2answers
1k 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 ...
1
vote
2answers
182 views

Current standard for hash function security parameter?

When designing a hash function, what should be the secure input and output lengths? In particular, what lengths do I need for collision resistance?
4
votes
1answer
209 views

Why are collision attacks important when talking about MAC schemes?

I'm reading Ferguson, Schneier, and Kouno's Cryptography Engineering, and it has a section on MACs. It discusses different types of MACs, but it seems to claim that to acheive 128-bit level security, ...
2
votes
2answers
364 views

Difference between collision resistance and target collision resistance

For a hash function, what's the difference between Collision Resistance and Target Collision Resistance?. I understand the definition of hash function collision resistance, but I don't know about ...
14
votes
1answer
2k 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 ...
4
votes
2answers
1k 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 ...
5
votes
1answer
287 views

I need a 64-bit cryptographic hash for 96 bits of data

I have a situation in which I need to combine a 32-bit datum, G, and a 64-bit datum, I, to produce a 64-bit datum. No two ...
1
vote
1answer
96 views

Prove that two MACs with incremendal PRF application are not secure

How do I prove the following MACs are insecure?                                                        1                                                                                   2
1
vote
1answer
197 views

Hash functions with or without secret key

The classical definition of hash functions (found in books) are OK, but when studying a little more there is a lot of notions that seem ambiguous (contradictory) to me : Sometimes we have hash ...