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

43 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13
votes
0answers
189 views

Space complexity of quantum collision search?

Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below ...
7
votes
0answers
193 views

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

Up to now, the pairs of strings that create an MD5 collision that have been discovered all contain non-ASCII (binary) characters. Are there two known ASCII-only strings which have the same MD5 hash ...
6
votes
0answers
118 views

Parameters for high density SIS

I am considering the SIS problem of finding $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}_q^{n\times m}$, $Ax=0$ and $\lVert x\rVert < \beta$ for some $p$-norm and bound $\beta < q$. ...
4
votes
0answers
71 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 ...
4
votes
0answers
616 views

Calculating probability of finding collisions in an invertible hash function

Assuming we have an invertible hash function H that takes inputs of size 2n and outputs hashes of size n, I use the following algorithm to find collisions: Choose a random M as input. Compute its ...
3
votes
0answers
91 views

Impossible to construct collision resistant hash function from one way function

[Simon 98] showed that it is impossible to construct collision resistant hash function from one way functions in a black-box way. I read the paper but barely understood it. Is there any source, where ...
2
votes
0answers
22 views

How to find k-way second preimages

For example: Assuming someone has found a second preimage for SHA-256. In other words, for SHA256(M1)=H, someone has found M2 which SHA256(M2)=H Now, is it possible to generate k-way second ...
2
votes
0answers
61 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
2
votes
0answers
149 views

Does there exist a highly irreversible hash function or a highly irreversible pseudo-random number generator?

In my previous question, I asked about potential symmetric cryptosystems which are designed to be computed by a reversible computer. I am now wondering if there are any cryptographic hash functions ...
2
votes
0answers
234 views

Hash function for sets with efficient membership testing

Is it possible to construct a collision-resistant function that hashes a set of values but also allows membership testing? Essentially, I'm looking for a pair of functions, $\text{H} : \{0,1\}^{**} \...
2
votes
0answers
1k views

Question about modifying the MD5 plain text to cause a collision

I was trying to understand MD5 and got stuck with this question, its from Michael sipser's book on Information security Principles and Practice, 2nd edition The MD5 collision in Problem 25 is said ...
1
vote
1answer
88 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-...
1
vote
0answers
96 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-...
1
vote
0answers
40 views

Changing a bit in IV of MD5

It is obvious that changing even one bit in data or IV (initialization vector) will change the hash value a lot. I want to know if, for example, changing a single bit within the $IV$ in MD5 can be ...
1
vote
0answers
35 views

Is there a universal construction for Davies-Meyer hash functions?

My understanding is that there exists no strong pseudorandom permutation for which the Davies-Meyer construction is known to yield a provably collision-resistant hash function. Were I mean provably ...
1
vote
0answers
37 views

Round counts and permutation usage for hashing for a Merkle tree

Are there any current recommendations for performant hashing in a Merkle tree? It appears the hash based signatures in Sphincs use Blake2 everywhere (see Table 1 on page 22 of https://sphincs.cr.yp....
1
vote
0answers
315 views

Show that the CBC-MAC construction applied to a PRP is not collision resistant

I'm trying answer the following question. Yes, it is a homework question, so I'm not asking for the answer directly but would like to get some pointers on how to solve it. So far I have spent several ...
1
vote
0answers
79 views

Extendable hash collision resistance of multiplication

I have a hash function $HashSet(A) = H(a_1) *\cdots * H(a_n)$, where $A = \{a_1,\ldots,a_n\}$ and $H$ is a hash function which generates values of $b$ bits (and $H$ has no collision attack that ...
1
vote
0answers
163 views

How many times does a hash function have to be evaluated?

I have the following homework assignment: $n$ is an even number, $1^n$ and $0^n$ are $n$-bit strings and $x$, $y$ and $z$ are arbitrary strings of length $n$. How many evaluations of hash ...
1
vote
0answers
208 views

TCR hash functions from MD5

I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical (pag. 10 and 11) and here say The most direct way to construct a TCR hash function is to key a function like MD5 or SHA-1. ...
1
vote
0answers
43 views

MD Construction Doesn't Propagate TCR

I'm reading a proof of the proposition of CollisionResistant Hashing Towards Making UOWHFs Practical Suppose there exists a compression function $F: \Sigma^k\times\Sigma^{c+m'} \rightarrow \Sigma^...
0
votes
0answers
74 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 ...
0
votes
0answers
19 views

Public Key Fingerprint: Preimage Resistance

In my system, “resources” are granted operational certificates signed by a particular CA. Each resource has a unique public/private key pair that it generates once. The operational cert granted by the ...
0
votes
0answers
36 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 ...
0
votes
0answers
232 views

Create a MD5 collision on two given files with an identical prefix

I'm stuck on an assignment of mine and maybe someone has some advice for me. I have the following task: I have to modify two files, which differ in exactly one byte, so that they have the same MD5 ...
0
votes
0answers
86 views

How a collision for a function can be for another one

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 \{...
0
votes
0answers
134 views

Does this qualify as a one-way function?

First, we observe that the expression X*Y mod P (where X and Y are secret and P is a large public prime) reveals no useful information. Next we define an extending function E(U, M) which "somehow&...
0
votes
0answers
28 views

Extractability of random oracle in simulation-based proof

I am working on the simulation-based proof, where Random Oracle (RO) is used to extract malicious parties' input. In particular, the RO considered in the proof has a small range (whose size is ...
0
votes
0answers
97 views

Is truncated hash collision resistant if original hash is collision resistant?

Let's say I have a collision resistant hash function $H: \{0,1\}^* \rightarrow \{0,1\}^n$ and I want to create another collision resistant hash function $H': \{0,1\}^* \rightarrow \{0,1\}^n$ using $H$ ...
0
votes
0answers
36 views

finding hash collisions for set of hashes

I am searching info on dependencies between different hash functions. Let's say that we have a set of x hashes H1, H2 ... Hn (using different hashing functions) of the same string S. For every hash we ...
0
votes
0answers
42 views

(key) Target Collision Resistance (kTCR)?

The enhanced Target Collision Resistance (eTCR) game implies that an adversary is allowed to choose a target message $M$. Upon choosing this target message, the attacker learns the function $\mathcal{...
0
votes
0answers
128 views

Probability of collision when we use a particular part of sha 256 hashed value

So I was supposed to use hash some co-ordinates and I was supposed to use k 3-wise independent hash functions in order for the mathematical explanations behind that algorithm to be hold. But after ...
0
votes
0answers
68 views

Is it something wrong in proof of Preservation of Collision Resistance for Merkle-Damgard?

I wonder about this proof. Can someone help me? I try to prove for Presevation of Collision Resistance for Merkle-Damgard as guide in end of this paper (Security Reductions of the Second Round SHA-3 ...
0
votes
0answers
49 views

Is Joux's multicollision attack applicable for truncated SHA256?

Joux presents an elegant way to generate k-way multi-collisions with about as much effort as generating a single collision: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf ...
0
votes
1answer
80 views

How to prove truncated MD (or chop MD) hash function is collision resistant?

We have a collision resistant hash function (based MD construction) H with 2n bits hash value size. Call chop(H) is a chopping n-bits from H's hash output. How can I prove a chop(H) is collision ...
0
votes
0answers
77 views

How to create two partly similar plaintexts with same MD5 hash value?

The problem I'd like to solve looks like this: There are two plaintexts which differ in length and letters, but contain a few common strings. The first few words and the last few words are the same, ...
0
votes
0answers
34 views

Finding a hash function that calculates average of an item in a stream of tuples

So, I have a stream of tuples coming in for example [country, state, person], where state and person are unique items. Now I have to find : 1. for each country, I have to estimate average number of ...
0
votes
0answers
50 views

Collision resistance

I have function with input 128 bit and output 64 bit that hash the header and hash the payload then concatenating them after that hash the result so my question is does this pass the collision ...
0
votes
0answers
131 views

Is md5(x) xor md4(x) collision proof?

Suppose I have the following hash function: $\newcommand{\md}[1]{\text{md#1}} \newcommand{\H}{\text{H}}$ $$\H(x, y) = \md{5}(x) \oplus \md{4}(y)$$ How can I prove it's collision proof? I tried to ...
0
votes
0answers
35 views

Help, Feedback and Solutions to a problem on a PoC CSPRNG

Background I do not recommend trying to roll your own crypto. This is just a for-fun PoC, which won't be used in any public or private scenario. I am creating a PoC nearly-true random number ...
0
votes
0answers
75 views

Function F is not resistant to collisions

If we have the following block cipher, E(k,m), why is f(x,y) not collision resistant? $$f(x,y) = E(y,x) \oplus y$$
0
votes
0answers
53 views

Collision resistance of a function which chooses the hash from a large table of hashes

Let's say you know a (possibly) large table of ids and some corresponsing hashes $h_{ID_j} = H(ID_j | secret_j)$. The resulting table looks like $$ ID_1 | h_{ID_1} $$ $$ ID_2 | h_{ID_2} $$ $$ ... $$ $...
0
votes
0answers
61 views

When we use a PRF to pad a message, do we need to worry about the PRF's output range and/or probability of collision?

My question is related to: How to contruct a pseudorandom with a specific property Collision in pseudorandom function when two different keys are used Question: When we use a pseudorandom function ...