Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [collision-resistance]

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

5
votes
1answer
571 views

Are there MD5 collisions for inputs of different length?

There are many examples of MD5 collisions (some of them can be found here Are there two known strings which have the same MD5 hash value?). But as far as I know two inputs should have the same length ...
10
votes
0answers
127 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 ...
3
votes
0answers
58 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
111 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
148 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
957 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
0answers
48 views

Birthday attack on hash functions derived from a collision-resistant hash function

$H_1$ is a collision-resistant hash function with an $L$-bit output. 2 hash functions are created based on it as follows: $$H_2((k_1,k_2);m) = (H_1(k_1;m), \space H_1(k_2;m))$$ $$H_3((k_1,k_2);(m_1,...
1
vote
0answers
22 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
103 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
63 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
137 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
55 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 ...
1
vote
0answers
149 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
55 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
50 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
21 views

Security implications of an extra inner encrypt for a single block Matyas-Meyer-Oseas hash function

Was giving some thought to simple MMO constructions for fast single block hash functions for things like PQ crypto. There's Haraka, but that's not standard and readily available while simple AES is in ...
0
votes
0answers
26 views

When looking for collisions of MD4, how does the 'Multi-step Modification' work in the paper of Wang et. al?

In part 4.2 of this paper, the writers introduced a technique called 'Multi-step Modification', here I got some questions. How does the Multi-step Modification ensure that we will not change any ...