We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
34 views

Merkle–Damgård transformation example

I m looking at this Example of Merkle–Damgård I have a similar question about this topic. I have hash function maps 256b blocks into 128b blocks, how many rounds are required for hashing a 140KB ...
0
votes
0answers
38 views

Probability of collision of two HMACs with two random keys

Assume $k_1$ and $k_2$ are two $\lambda$ bit random number ($|k_1|=|k_2|=\lambda$), and HMAC generates $f(\lambda)$ bit tag. How much is the probability of their collision for an input message $m$? $...
7
votes
1answer
460 views

Security levels in NIST Post-quantum project: e.g. AES-128 vs SHA-256

In an article about NIST Post-quantum Standardization project I read about the security criteria of the proposed schemes and there was this table (Level I lowest security, level V highest): Level I: ...
0
votes
1answer
65 views

If multiple hashing algorithms are chained together, is the compound hash function more collision resistant? [duplicate]

The DASH cryptocurrency uses X11, which is a Proof of Work hashing algorithm composed of 11 separate hash functions which are run as a sequence. Example: $Digest = H_{11}...(H_3(H_2(H_1(Input))))$ ...
1
vote
1answer
58 views

Swapping a single bit inside a 40 bytes inputs fed to keccak256. Is it safe to assume no change in the first 20 bytes can result in the same hash?

I have the following data (represented as hex from binary below) where the lower bytes is controlled by attacker in the second case : ...
1
vote
2answers
69 views

For data shorter than 32 bytes, is it sure that no collision exists?

I’m not talking about if a collision can be found but even simply exists. The point is since it’s shorter than the length of the hash (since I’m talking about keccak256), normally there’s a hash ...
2
votes
2answers
66 views

Collision resistant functions - definition

Let $f$ be a collision resistant function i.e. it is computationally impossible to find $x_0, x_1$ such that $f(x_0) = f(x_1)$. If a computationally bounded adversary demonstrates that he knows some $...
12
votes
3answers
2k views

SHA3-255, one bit less

I need a SHA3-255 or 511. What if I simply truncate a standard SHA3-256 or 512? Apart from the doubled probability of hash collision, are there any other things I should be aware of? I could also ...
4
votes
0answers
76 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$. ...
6
votes
0answers
98 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 ...
0
votes
0answers
31 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 ...
4
votes
2answers
1k views

Why this brute force attack doesn't reduce all cryptographic hash functions' security bits against collision attacks to N/3?

The traditional brute force collision attack is generate $2^{N/2}$ (unique) random strings, hash them and this results in ~50% chance for collision. The attack talked in the question's title is ...
1
vote
2answers
120 views

How to prove if a Hash Function is collision resistant

Say we have the following Hash Function, H(x) = 4x mod N where N is a number generated by multiplying two prime numbers and x={0,1,2,3,...,N-1}. So lets assume that ...
1
vote
1answer
67 views

What is the possibility of collision of trailing 160 bits of Keccak_256, for any two differing public-keys as pre-images?

Earlier today I was answering a question on the ethereum SE site that analyzed the potential for more than one private key on curve secp256k1 (which maps to a distinct public key) to control the same ...
4
votes
1answer
130 views

Hash multiset to point on elliptic curve where $A = 0$

I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that ...
3
votes
1answer
92 views

Is it feasible to find n hashes that sum up to a given hash?

Consider two sets $A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}$; We can calculate the hash sum of those sets: $$HASHSUM(𝐴)=(ℎ𝑎𝑠ℎ(a_1)+ ℎ𝑎𝑠ℎ(𝑎_2)+\cdots +ℎ𝑎𝑠ℎ(𝑎_𝑛))$$ and $$HASHSUM(𝐵...
1
vote
2answers
58 views

How many hash collision will exist where the digest is a pre-image?

This question follows on from the question Circular hash collision where digest is pre-image: Could hash(a) = b, hash(b)=c, then hash(c)=a? The question was answered but the issue of the number of ...
0
votes
1answer
46 views

How does concatenating diverse hash functions affect collision resistance?

Let's suppose I take 3 different types of hash functions and concatenate them for future safety so that: digest = Hash3( Hash2( Hash1( text ))) Does the birthday attack mean in this case that I must ...
0
votes
1answer
180 views

Strongest collision resistance test?

An administrator is testing the collision resistance of different hashing algorithms. Which of the following is the strongest collision resistance test? A. Find two identical messages with different ...
2
votes
1answer
80 views

Simple commitment scheme using secure hash function

Can I create a simple commitment scheme using a secure hash function? If so, is concatenation with a random secret enough to preserve hiding? (i.e. $C = H( random\_string || message)$) Thank you
1
vote
1answer
103 views

Is it possible to truncate AES output and keep uniqueness (no decryption needed)? [duplicate]

I would like to hash numbers less than 1000000000, so generally they could be stored on 30 bits. The aim is to obtain numbers that are not reversible, so my initial plan was to use SHA256 (with some ...
3
votes
1answer
113 views

Please explain me why we require $2^m$ & $2^{\frac{m}{2}}$ random messages

Assume that a one-way Hash function is secure and the best way to attack it is by using the brute force attack. It produces an $m$-bit output. Finding a message that hashes to a given hash value would ...
1
vote
1answer
83 views

collision resistance of a composed hash function

Given a collision-resistant hash function $H(x)$, say SHA256, and I devise another hash function by $H'(x)=\sum^{m}_{1}H(x||i) \mod p$. The summation is defined on finite field of prime order $p$. ...
3
votes
1answer
49 views

Security issues with computing parallel hashes?

One issue with most hash algorithms like SHA-256 is that it is inherently serial. You can't effectively use SIMD to parallelize a single SHA-256 calculation. However, you can calculate multiple SHA-...
2
votes
1answer
95 views

Collision resistant hash function implies one-way function

I'm struggling to give a formal proof that $CRH \implies OWF$ using the definition below. Intuitively, I see why a $CRH$ would be "hard to predict" and might be used as a $PRF$, but I'm unable to ...
2
votes
1answer
85 views

How secure is a hash based signature scheme after signing assuming quantum computers?

Consider a hash based signature scheme that requires taking the $k$-bit hash of an arbitrary length message to be signed (e.g. Lamport one-time signature scheme). My understanding is, assuming that ...
5
votes
2answers
188 views

Collision resistance of partial SHA-256 hashes XOR'ed

My hashing algorithm computes the SHA-256 for each of 12 input strings and XORs them to get the final hash. Is there a risk of an attacker being able to forge 2 sets of inputs that yield the same ...
2
votes
0answers
50 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$ ...
1
vote
1answer
82 views

Are Merkle Dags really Dags in most cases?

Let $H$ a cryptographic hash function of image length $n+1$ and $s_0$, $s_1$, ... , $s_k$ a finite sequence of bitstrings (length $>n+1$), such that $s_j$ contains a hash of $s_{j-1}$ for all $1\...
1
vote
1answer
110 views

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

$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,...
16
votes
3answers
3k views

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

I want to use a hash function to generate a random sequence from number 0-n. And so I would like to find a good function that results in values that are seemingly random (does not need to be secure), ...
2
votes
1answer
45 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
57 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
73 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
83 views

Cryptographic hash function based on logistic map?

Is there any secure cryptographic hash function based on the logistic map?
7
votes
1answer
294 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 ...
2
votes
2answers
196 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 ...
0
votes
0answers
51 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
28 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 ...
1
vote
1answer
86 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
27 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
32 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 ...
1
vote
2answers
173 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 ...
2
votes
0answers
59 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,...
3
votes
0answers
67 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
442 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
807 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?
0
votes
1answer
64 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$$
2
votes
1answer
160 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 ...
2
votes
2answers
345 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 ...