Questions tagged [collision-resistance]

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

63 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13 votes
0 answers
212 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 ...
user avatar
7 votes
0 answers
279 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 ...
  • 71
5 votes
0 answers
127 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 ...
  • 87.1k
3 votes
0 answers
139 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 ...
3 votes
0 answers
110 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 ...
  • 1,294
3 votes
1 answer
242 views

Collision finding method

The "birthday paradox" places an upper bound on collision resistance: if a hash function produces $N$ bits of output, an attacker who computes only $2^{N/2}$ (...) hash operations on random ...
2 votes
0 answers
42 views

Is WPA2 collision-proof?

I was experimenting with hashcat and aircrack to test WiFi security. The WiFi AP is a WPA2 encrypted network. The tool I used to ...
  • 21
2 votes
0 answers
118 views

Why this function isn't second preimage resistant?

Why is $h(k,m)$ not second-preimage resistant? Let $E_k$ be a block cipher where the message space is the same as the key space. $$h(k,m)=E_k(m\oplus k)\oplus k$$ I've been reading about second ...
  • 21
2 votes
0 answers
85 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
0 answers
188 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
0 answers
316 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,734
2 votes
0 answers
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
0 answers
67 views

Hash function collision resistance

I have a course work for university, and am not sure on my answer so if anyone could please take the time out to read the question and my answer to let me know if I'm going in the right direction that ...
  • 43
1 vote
0 answers
26 views

Does a salt by a trusted party remove the need for collision resistance for a binding commitment?

Say a Human is operating their trusted computer, Alice, and Human wants to hand copy a collision resistant commitment, with a security factor of 128 from Bob on to paper. Naturally we want the ...
  • 488
1 vote
0 answers
51 views

Compute a hash function given commitment to some secret element

Given a secret key x and a commitment to it comm(x) where comm(x) is both binding and hiding (it can be for example $g^x$ or some homomorphic encryption). Given public parameters $P_1,...,P_k$, comm(x)...
  • 59
1 vote
0 answers
33 views

What is an advantage of the Charles--Lauter--Goren hash function?

What is an advantage of the Charles--Lauter--Goren hash function (based on isogenies of elliptic curves) among other provably secure collision-resistance hash functions ? I heard that it is slower.
1 vote
0 answers
67 views

Cryptographic hash function to map interval onto itself

Is there any existing approach to construct perfect hash function that map [0, M) to [0, M)? It should be one to one mapping and ...
1 vote
0 answers
73 views

Collision-resistant single-pass EdDSA?

Is there any reason why collision resistant variants of ed25519 that use a single-pass aren't used instead? For example: $n = h(noncekey \| m)$ $h(R \| pub \| n)$ instead of $h(R \| pub \| m)$ or ...
1 vote
0 answers
566 views

How to find the 6 main properties of cryptographic hash functions when implementing a hash function?

According to this there are at least 6 "properties" all cryptographically secure hash functions strive to attain: Deterministic: the same message always results in the same hash; Quick: it ...
  • 171
1 vote
0 answers
52 views

One way function with fixed point

As part of an exercise in a cryptography course, I want to come up with a one way function for which it is "easy" to find a collision from a given OWF. To achieve this, I tried the following:...
  • 21
1 vote
0 answers
46 views

Hash function producing cycles with expected max length

Is there a known hash function $H_k: X\to X$ such that: $\forall{x\in{X}},\exists{n\in{\mathbb{N}}}, n<k \land H^n(x)=x$ === EDIT === By hash function I mean ...
1 vote
0 answers
268 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
0 answers
80 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 ...
  • 113
1 vote
0 answers
73 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
0 answers
49 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,104
1 vote
0 answers
516 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
0 answers
86 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 ...
  • 111
1 vote
0 answers
179 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
0 answers
233 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. ...
  • 2,601
1 vote
0 answers
47 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^...
  • 2,601
0 votes
1 answer
19 views

How to understand the argument “if the adversary outputs x then it queries (a, x) to oracle”?

When I read the work of Dodis et al. ref1, it looks as if I have encountered a simple logical bug. (I'm not concerned with the details of secure proof techniques, but with the logic of reasoning.) In ...
  • 1
0 votes
0 answers
61 views

Probability of getting a collision using chosen plaintext attacks

For university I am doing a piece of coursework right now. This question is focusing on CPA and collisions using CPA. Question: I have attempted to answer part 3, but am not very confident in the ...
  • 43
0 votes
0 answers
63 views

What hashing algorithm is fast and good enough for checking if source data is changed?

Not sure if this falls into crypto from contextual point of view but it is about hashing algorithms. I have two directories -- assets/ and cache/. Anytime there is a file added, deleted, or changed in ...
  • 113
0 votes
0 answers
71 views

Is there a special limit in the range of the hash function?

Is there a special limit in the range of the hash function? More specifically, is it possible that there is a cryptographic hash function that outputs c-membered subsets of the n-membered set? In ...
0 votes
0 answers
37 views

Assumptions used for Designing Homomorphic CRHF

What are the possible assumptions that have been used or can be used for designing the homomorphic Collision Resistant Hash function (CRHF)? I know Short Integer Solution (SIS) is one of the ...
0 votes
0 answers
88 views

Determine if a Hash function is pre-image resistant and collision free

I'm so confused by this kind of exercise. We have that $n = p * q$, where $p$ and $q$ are prime numbers. Let's examine this hash function: $h(x) = x^2 \mod n$. Determine if the hash function is pre-...
0 votes
0 answers
52 views

Can we combine two AES (with block size 128) to to a block cipher with a block size 192 which is collision-resistant?

Encrypting values with AES we only need about $2^{64}$ trials until we finding an already used value (some collision). This can be done these days with easy. To make this harder can we combine two AES ...
  • 475
0 votes
0 answers
20 views

Do L-trees remove the need of collision resistance hashes in XMSS MT?

I read that the bitmasks in XMSS-MT lower the security requirements from a collision resistant undetectable hash to a 2nd preimage resistant undetectable hash (see LMS vs XMSS: Comparion of two Hash-...
0 votes
1 answer
62 views

Randomness and authentication on short value outputs (48 bits)

I want to implement a client that generates random 48-bit values and send them as broadcast messages. We assume also there is a legitimate receiver getting those values (so, there is some sort of pre-...
  • 635
0 votes
0 answers
23 views

Why we need DSPR or Eq. 14 for the proof of SPHNICS+?

The paper says that We show that preimage resistance (PRE) follows tightly from the conjunction of second-preimage resistance (SPR) and decisional second-preimage resistance (DSPR). As I understand ...
  • 73
0 votes
0 answers
37 views

Collision and pre-image resistances of a hash function based on SPRP

Assume we have a secure block cipher $E$ (strong pseudorandom permutation) and a fixed key $k$ which are publicly known. We construct our hash function $H(m)$ as $$ H(m) = E_k(m_1) \oplus \dots \oplus ...
0 votes
0 answers
75 views

1st Preimage, 2nd Preimage, Collision resistance of powers of 2 mod n

Let $n$ be a product of two odd, distinct large primes $p$ and $q$. Define the hash function as $$ H_{F}(x)=2^{x} \bmod n $$ Is this hash function resistant to 1st/2nd preimage and collision attacks? ...
0 votes
0 answers
49 views

Checking if a function is collision-resistant

Consider a prime order cyclic group $\Bbb G$ of order $q$ with generator $g$. Then consider the function$$f:\Bbb Z^n_q\to\Bbb G\\(\alpha_1,\alpha_2,...,\alpha_n)\mapsto g^{\alpha_1\cdot\alpha_2...\...
0 votes
0 answers
51 views

Collision resistance analysis

I am learning about collision resistance security notion of hash functions. However, I got confused when collision resistance experiment started using "keyed" hash functions in the ...
0 votes
0 answers
56 views

What happens when we hash already hashed values, concatenated together?

I read on the page 16 of On the Security of Hash Function Combiners that the classical combiner for collision-resistance simply concatenates the outputs of both hash functions $Comb_{\mathbin\|}(M) = ...
0 votes
0 answers
139 views

Merkle-Damgård construction

Let $H^f$ be a hash function designed using Merkle-Damgård construction on $f:\{0,1\}^{2n}\to\{0,1\}^n$. Write an algorithm that makes approximately $2.2^{n/2}$ many queries to $f$ and find four ...
0 votes
0 answers
152 views

Why do the first two digits of the hash table not collide within CRC32?

In this Python CRC32 table look-up method, the polynomial is 0x104c11db7. I can understand that the generated table does not collide. After all, as long as the ...
0 votes
0 answers
233 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
0 answers
93 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 \{...
  • 117
0 votes
0 answers
149 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&...