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

0
votes
0answers
16 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,...
2
votes
1answer
38 views

Can we assume that a hash function with high collision resistance also means highly uniform distribution?

I want to use a hash function to generate random sequence from number 0-n. And so I would like to find a good function that seemingly random (don't need to be secure) but give a sequence that uniform ...
2
votes
1answer
36 views

1 round Feistel with birthday attack

This is a reprise of an earlier question of mine, and I'm sorry if it's repetitious; I'm going at it with a different strategy. In an exercise I was given a 1-round Feistel network which uses $H(k \...
0
votes
0answers
52 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
1answer
58 views

Hashing functions - How to define them?

Let $\mathcal{G}$ be a cyclic additive group for an elliptic curve $E\, / \ \,\mathbb{F}_p$, and let $p, n$ be two large prime numbers (e.g., we can consider $\texttt{secp160r1}$ with $p = 160$ bit ...
2
votes
1answer
64 views
8
votes
1answer
249 views

Which TLS features are vulnerable to chosen-prefixes collision on SHA-1?

Gaëtan Leurent and Thomas Peyrin's preprint From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1 (in volume 1 of proceedings of the forthcoming Eurocrypt 2019) shows a feasible ...
3
votes
2answers
283 views

How can a hash function that implements random oracle model have collision resistance?

ROM is considered to be collision resistant. Does ROM assume there is an infinite set of outputs, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM ...
2
votes
2answers
318 views

How to prove that finding a cycle in a cryptographic hash function is hard?

I want to show that finding cycles in a cryptographic hash function is hard. My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial ...
17
votes
4answers
1k views

Cycles in SHA256

Let's say I start with a particular 256 bit value. Call this $v$. I then hash that value, and get another 256 bit value. Call this $\text{SHA256}(v)$. I take this value and get another 256 bit value. ...
31
votes
3answers
4k views

Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?

Note: I am not advocating anyone continues using SHA1-signed certificates: they are dead as far as security is concerned and should no longer be used. I'm just trying to clarify my understanding of ...
2
votes
2answers
136 views

Why do the non-leaf Nodes of Merkle tree need to be hashed?

Given the standard Merkle Tree as shown Wikipedia. I am having a hard time understanding why Hash(Hash(Leaf A)|| Hash(Leaf B)) at the parent of A and B is ...
5
votes
1answer
570 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 ...
0
votes
0answers
48 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} $$ $$ ... $$ $...
3
votes
2answers
5k views

Computational requirements for breaking SHA-256?

Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function): preimage attacks to get $m$ knowing $H(m)$ second-preimage ...
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
1answer
141 views

What is a fast good-uniformity hash function that if it's seed and it's hash values are unknown, can be strong as cryptographic hash functions?

The hash function is for an application that the input to the hash function is from a user's, hence the user can control the collisions, but the question is that if the collisions, the hash function's ...
-1
votes
0answers
43 views

Is there a collision free Hash Function for dynamic data that preserves already created hashes? [migrated]

I am familiar with the concept of hash functions and fingerprints but I am new to the implementation of functions and the specific characteristics of all those hash functions out there. What I need ...
125
votes
7answers
49k views

Why can't we reverse hashes?

First off, I know hashes are 1 way. There are an infinite number of inputs that can result in the same hash output. Why can't we take a hash and convert it to an equivalent string that can be hashed ...
1
vote
1answer
40 views

deterministic uuidv4 -> uuidv4

I need to copy a graph of elements with uuidv4s each, and separately stored relations containing element uuidv4s. On copy, I ...
1
vote
0answers
21 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....
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 ...
0
votes
2answers
90 views

Hash functions with variable and fixed length inputs

I was told that a hash function (mostly looking at the SHA-* family) should have input strings of variant length provided first, and those of fixed length after (ie salt), in order to avoid some kind ...
0
votes
1answer
99 views

How can I verifiably announce a choice without revealing its content?

Here is the simplified problem: Alice chooses from a small set of possible values. Bob guesses which value Alice picked. Alice reveals what value she picked. Alice's choice must stay secret ...
1
vote
1answer
182 views

hash collision chance using a 5 chars hash made of a-z A-Z and 0-9 (62 chars total)

What is the chance for collision or resistance of a hash made out of 5 chars randomly picked from this sets a-z A-Z and 0-9 (62 ...
2
votes
0answers
56 views

Application of High-level Mathematics to Hashing [closed]

Sorry if this post is a tad unconventional(it's also a reddit repost), but I was recently commissioned by a teacher to write a paper on the application of high-level math to a topic of our choice, and,...
1
vote
1answer
54 views

What are best known attacks for finding partial target pre-image?

Just a follow up on this question since I don't have enough point to comment: Does a partial preimage attack imply a preimage attack? Partial target preimage attack: Given $M$ and t-bit partial ...
-1
votes
1answer
93 views

Key-Bijective Secure Symmetric Encryption Methods

In AES, an N-bit message is mapped 1-to-1 message-to-output (for a fixed key). If we use a key with N bits, however, the key is not mapped 1-to-1 key-to-output (for a fixed message). So, is there any ...
-2
votes
2answers
554 views

What is the probability of any two users generating the same 128, 256, 2048 bit key?

There are some protocols that require the user to generate some random key locally (client-side) with no server authority to "approve" or "reject" their key and are based on the assumption that it's ...
1
vote
1answer
114 views

What does the〈 〉notation mean in this situation?

I was looking at solutions for a problem but I noticed it said $\langle2\rangle$ and was unsure of what that meant. From Homework 5 (PDF)
4
votes
1answer
111 views

Combining md5 collisions to create more collisions

Given X1 and X2 such that md5(X1) = md5(X2) and Y1 and Y2 such that md5(Y1) = md5(Y2), and knowing the following property of md5: if md5(a) = md5(b), md5(a|s) = md5(b|s) is there a way to find Z1, ...
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 ...
1
vote
2answers
218 views

What is a simple 8-bit cryptographic hash function that I can use in a quantum simulation of Grover's algorithm?

I'm taking a quantum computing course in which, for our final project, we must create a proof-of-concept implementation of Grover Search for finding hash collisions up to a difficulty (similar to ...
6
votes
2answers
722 views

Compression function is not collision resistant but Merkle-Damgard is collision resistant

Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?
1
vote
1answer
145 views

does SHA* collide more or less than a random function?

There were several questions here regarding how surjective SHA-1/2 is, how many values don't have a pre-image from a fixed size input. I and others answered when modelling the relevant hash function ...
2
votes
1answer
204 views

Does Keccak have an eTCR mode?

On page 7 of NIST's views on SHA-3's security requirements and Evaluation of attacks, I see that, at least at this point, NIST planned on offering SHA-3 having eTCR security (defined on page 3): ...
0
votes
1answer
54 views

What does the minimal number of round of “nr” use Keccak to avoid “collision attack”?

What does the minimal number of round of "nr" use Keccak to avoid collision attack? $$nr = 12+2L$$
4
votes
1answer
105 views

What are the implications of quantum collision search algorithms like Ambainis for collision-resistant hash functions?

I just stumbled onto a series of 2017 papers about applying the Ambainis quantum collision-finding algorithm to hash functions. (disclaimer: I haven't read all of them in full yet): Post-quantum ...
0
votes
1answer
181 views

Why is H(k || m || k) secure against birthday attack?

I don't know if my opinion is correct. I think that H(k || m || k) (I mean using Merkle and Damgard algorithm where k is a secret key shared by two parties and m is the message sent) is a good keyed ...
-1
votes
2answers
630 views

(strong) collision resistance Example

I'm studying Cryptography & Network Security. It has the following example for collision resistance: "Suppose Bob writes an IOU message, sends it to Alice, and she signs it. Bob finds two ...
4
votes
1answer
65 views

Is there an information theoretic equivalent of a trap door collision free function?

Warning: Possibly ill-posed question. I'm using the following definition from a recent paper available here. I believe their terminology is slightly different but reproduce my understanding of it ...
2
votes
1answer
81 views

Formal definition of collision resistance for hash function

In my cryptography class, the professor said that collision resistance for a fixed hash function is not a "precise" definition. The reason is since a fixed hash function is a single instance of a ...
9
votes
2answers
268 views

How should I incrementally sign a large set of documents?

Say I have a large set (i.e. unordered collection of unique elements) of documents, each of which is around 4KB in size. I'd like to sign that set with a private key so that anyone can verify the ...
6
votes
1answer
290 views

Is there a way one can combine two correlated hash outputs to maximize the collision resistance?

While practically diving into collision resistance, I am trying to first write a non-cryptographic hash (to learn from it) which is limited to arithmetic operations on 32-bit integers only. It ...
3
votes
1answer
523 views

Is there are a metric based on collisions to compare bad hash functions?

Bad hash functions are not so perfect as in the "general collision probability" hypothesis... And a general concept of "collision resistence" not need the constraint of independence between the ...
9
votes
2answers
2k views

How many trials does it take to break HMAC-MD5?

I know that you can find collision in MD5 with 2^64 trials using Birthday paradox. Now everyone is saying that HMAC-MD5 is significantly more secure. How can I ...
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 ...
4
votes
1answer
197 views

What is perfect collision-resistence in probability terms?

update: removed lots of stupidity... sorry. I didn't know I can be this stupid but I achieved it. 1. Goal Let $\mathcal{D}$ be the universal space of our plain data. Our goal is to find a function $...
3
votes
1answer
264 views

Merkle-like hash tree that mirrors existing tree structure

I'm wondering about the security of a hash-tree structure that mirrors the structure of another tree. In an ordinary Merkle tree the block hashes form the leaves of the tree, and all internal nodes ...
6
votes
2answers
946 views

Keys in HMAC and NMAC

I'm quite new to this topic and have several questions concerning HMAC and NMAC: Why does NMAC need two keys? How can it be attacked if we just used some sort of initialization vector instead of the ...