# Questions tagged [collision-resistance]

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

697 questions
Filter by
Sorted by
Tagged with
1 vote
168 views

### Is the collision chance 2^(n/2) of an n-bit tag τ unchanged if reduced to (n/2)-bits using a reduction of τ to some 2^(n/2) order group element?

If $H(k, Μ) = τ$, in the context where $τ$ is an $n$-bit tag produced as a mac on a key, $k$, and a message, $M$, through a keyed-hash function, $H$, is there a function $F(τ) = T$ that transforms $τ$ ...
• 53
144 views

### Homomorphic hash from prime order group $G$ to $Z_p$

Let $G$ be a cyclic group with the generator $g$ and of prime order $p$ such that the discrete-logarithm problem is hard in $G$. A hash function is homomorphic if $H(a\ast b)=H(a)\cdot H(b)$ (where ...
• 335
1k views

### Using bcrypt to always produce the same hash like SHA, MD

I want to take advantage of the slow property of bcrypt to hash an input but also want to get the same hash value for the same input every time just like SHA, MD, etc. So in order to do that, instead ...
• 143
53 views

### Is it possible to have collision resistance but not pre-image and 2nd pre-image resistance?

I have studied cryptographic hash functions quite a lot, but have not completely understood whether it is possible to have collision resistance but not pre-image and 2nd pre-image resistance at the ...
951 views

### Many near collisions but no full collision

I read this question: Cracking $f(x) = Cx \oplus Dx$ Asking about finding collisions in a simple 64 bit hash, and I thought I will give it a go myself just for fun. I quickly wrote code to find ...
• 11.5k
69 views

### Using hash of data as proof of integrity and preventing collision

Rather than storing user data when interacting with an app, I am storing the SHA3-256 of the data. This is because data storage in this particular environment is very limited. The data can be several ...
• 103
143 views

### Cracking $f(x) = Cx \oplus Dx$

A program I reverse engineered is using $f(x) = Cx \oplus Dx$ where C = 0x20ef138e415 and D = 0xd3eafc3af14600 as a hash ...
1 vote
83 views

• 413
291 views

### Hash Function that is Collision Resistant but not Puzzle Friendly

Is there any example of a Hash function that is collision-resistant but may not be puzzle-friendly, similarly example of a hash function that is puzzle-friendly but not collision-resistant? Puzzle ...
1 vote
59 views

### Are the hash functions collosion resistant or not? [closed]

If H is collision resistant then the following are collision resistant or not? H'(x) = H(x) || H(x) H'(x) = 1 || H(x) My thoughts: I am confused in question 1. In case of different hash function(H'(...
311 views

### How many different keys can be derived with HKDF before two outputs are identical?

How many different keys can be derived with HKDF before two outputs are identical? This question is about collision resistance, not about generating different keys with different parameters (eg. ...
• 31
1 vote
90 views

### Authentication tag length and post-quantum security

The recommended hash length for post-quantum security seems to be either 384-bits or 512-bits. 512-bits gives 256-bit collision resistance, and 256-bit security is obviously ideal for post-quantum ...
• 11
1 vote
256 views

### HKDF Bit Security

I've always understood the bit security of hash functions to be related to their output size (eg. collision resistance). However, I recently came across a table from a Wickr blog post that lists HKDF-...
• 11
541 views

### What are the differences between a UHF (as used in cryptography) and a cryptographic hash function?

After reading about UHFs from different sources (From Algorithm books to Crypto books), I am still thoroughly confused about them. How is a UHF different from other cryptographically secure hashing ...
• 2,249
331 views

### Is the HMAC of a broken hash such as MD2, MD5, SHA1 etc, also broken?

As we know, MD5 and SHA1 (to some extent) are broken, and older algorithms like SHA0 or MD4 and MD2 are very broken. Does this also imply that the corresponding HMACs are also broken? Obviously nobody ...
• 1,387
1 vote
359 views

### Why this function isn't preimage resistant?

Prove that the function $$G(z) = \mathcal{H}(z) \, || \, \text{LSB}(z)$$ (where $\mathcal{H}$ is a collision resistant hash function, $||$ is concatenation and $\text{LBS}$ is the least significant ...
• 79
241 views

### is there any hash collision attack that is not defeated by adding a salt first?

In the references I've read, all the uses of "collision attacks", whether classical collision attack or chosen-prefix collision attack, goes like this: "Alice creates a 'good' document ...
• 145
930 views

### Extending the size of input for SHA-2 function

In the question Does a hash function necessarily need to allow arbitrary length input? many answers talk about the theoretical limit of the SHA-2 functions being $2^{64} - 1$ bit due to padding. I was ...
98 views

### Will repeatedly applying a hash function to the prior result visit all possible hashes? [duplicate]

If one were to take a message, say "Hello world!", and compute the MD5 hash: 86fb269d190d2c85f6e0468ceca42a20 Then, taking the MD5 hash of this, and repeating that procedure: ...
• 103
133 views

### Challenging $O(2^{n/2})$ for hash collisions using quantum computers

In "Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound" the authors Akinori Hosoyamada and Yu Sasaki state that it may ...
• 89.1k
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
494 views

### Bits of security vs collision resistance?

I have been doing some research on security, and I am confused on the bits of security vs collision resistance, and I was wondering if someone could clarify my understanding. For instance, if you have ...
• 3
261 views

### Application of cryptographic hash functions which do not require collision resistance property

I can not understand why collision resistance of a cryptographic hash function is not required for some applications. for example, if we store the trusted hash of a file or program, and later when we ...
• 43
298 views

### What are the “costs” to find a pre-image, weak collision, or strong collision?

For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?
• 23
363 views

### Is this modification in Merkle-Damgård collision-resistant?

We modify Merkle-Damgård construction by setting $z_0:=L$ (the length of the message), computing $z_i:=h(z_{i-1}||x_i)$ for $i=1,...,B$ and defining $H(x):=z_B.$ Is this construction collision-...
68 views

### Time and Space complexity of MiniAES

I am currently doing my masters research on security of wireless sensor networks, the topic is "ENHANCING THE SECURITY OF WIRLESS SENSOR NETWORKS BY COMBINING GEOENCRYPTION AND LIGHT WEIGHT ...
154 views

### How much brute forcing efforts needed to find 2 or more inputs that generating same SHA256 outputs

Say I have SHA256 hash result that produced from 2000 bits inputs. For example, 0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef (64 bit hex representation) is the SHA256 output. ...
• 61
618 views

### Examine whether a hash function is collision-resistant

Assume a collision-resistant hash function $h$ which compresses sequences of length $2n$ to length $n$. It must be examined whether the hash function which compresses seqs. length $4n$ to $n$:  h_1(...
• 79
We have two bit strings $x\in\{0,1\}^q$ , $y\in\{0,1\}^w$ of length $q$ bits, and $w$ bits. The notation $x\mathbin\|y$ means $(q+w)$ bits long concatenation, And the functions: \$H∶\ \{0,1\}^* \to \{...