Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
67
questions with no upvoted or accepted answers
14
votes
0
answers
215
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 ...
user991
7
votes
0
answers
290
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
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.2k
3
votes
0
answers
104
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 ...
- 31
3
votes
0
answers
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 ...
- 31
3
votes
0
answers
116
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,344
3
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 ...
- 203
3
votes
1
answer
268
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 ...
- 199
2
votes
0
answers
43
views
Is there any standard extension of the Merkle-Damgård transform that handles arbitrary-length inputs?
I have seen multiple sources claim that the Merkle-Damgård transform is able to build a collision-resistant Hash-function $H$ for arbitrary-length inputs from a compression function $h : \{0,1\}^n \to ...
- 131
2
votes
0
answers
121
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
1
answer
365
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-...
- 21
2
votes
0
answers
95
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
196
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 ...
- 750
2
votes
0
answers
333
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,744
1
vote
0
answers
38
views
How to estimate the collision resistance of a hash function if a secondary key is used (keyed hash function)?
According to the documentation of HighwayHash, for finding a collision are expected $m \over 2$ guesses, being $m$ the message.
By contrast, 'strong' hashes such as SipHash or HighwayHash require ...
- 115
1
vote
0
answers
62
views
What is the proof that the RSA is collision-free?
We have the RSA function:
$c = m^e (mod n)$.
I would like to know the proof that there is not an $m_1$ and an $m_2$ message that produce the same $c$.
My thoughts:
We know that $m \le n$, so $m_1 \...
- 11
1
vote
0
answers
27
views
Checksum algorithm using system of multivariate polynomials
I'm working on a protocol that uses zero-knowledge proofs. I'm looking at systems of polynomial equations as cheap solutions for checksumming data. Note, I'm not looking for trapdoor functionality ...
- 47
1
vote
0
answers
78
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 ...
- 77
1
vote
0
answers
81
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 ...
- 77
1
vote
0
answers
28
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
56
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)...
- 79
1
vote
0
answers
37
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.
- 317
1
vote
0
answers
70
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 ...
- 111
1
vote
0
answers
80
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 ...
- 77
1
vote
0
answers
735
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
55
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
47
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 ...
- 111
1
vote
0
answers
88
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 ...
- 165
1
vote
0
answers
80
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
50
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
549
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
90
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
193
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 ...
- 143
1
vote
0
answers
237
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,621
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,621
0
votes
1
answer
35
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
132
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
89
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 ...
- 21
0
votes
0
answers
38
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
106
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
69
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 ...
- 505
0
votes
0
answers
24
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-...
- 25
0
votes
1
answer
74
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-...
- 675
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 ...
- 113
0
votes
0
answers
38
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 ...
- 1
0
votes
0
answers
83
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? ...
- 1
0
votes
0
answers
58
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
54
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 ...
- 63
0
votes
0
answers
71
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
167
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 ...
