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
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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
0answers
234 views

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 ...
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 ...
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 ...
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 ...
0answers
86 views

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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
0answers
131 views

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

Suppose I have the following hash function: $\newcommand{\md}{\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 ...
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 ...
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$$
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}$$ $$...$$ \$...
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 ...