Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
36 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
86 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
48 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
28 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
70 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
65 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
95 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
102 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 ...
0
votes
0answers
63 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
43 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
75 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
50 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
158 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
48 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
78 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
88 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,...
15
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
43 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
56 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
68 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
277 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
155 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
22 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
65 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
26 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
30 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
130 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
58 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
60 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
302 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
739 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
57 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
91 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
328 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 ...
1
vote
0answers
106 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
1answer
107 views

Is a hashing algorithm considered broken if a collision happens under $2^{n/2}$?

If for example we would find a hash collision for SHA256 with $h(x) = h(x')$ for $x \ne x'$ and $x, \space x' < 128$ bit (meaning both $x$ and $x'$ are smaller than 128 bit), would SHA256 be ...
1
vote
2answers
92 views

Integrity check of a binary firmware file with hash function

I need to provide a mechanism that it is possible to verify the integrity of a firmware image flashed on an embedded system. The procedure should be, that if someone has doubt on the firmware’s ...
5
votes
1answer
498 views

Is there a feasible preimage attack for any hash function (no matter how deprecated) today?

Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack? All hashes that are nowadays considered 'broken' (...
-1
votes
1answer
52 views

Add string to create specific MD5?

I have a file that include a long string , I can calc the md5 of this file . Is there any way to know which string I need to add for this file so the md5 of this file will be specific md5 that I want?...
2
votes
1answer
97 views

What is the minimum message length to obtain the full potential of a hash?

Suppose I want to commit to a uniformly picked nonce of fixed length $n$ bits without revealing the nonce, so I use a secure hash function $H$ mapping messages to digests of length $d$ bits. Suppose $...
18
votes
2answers
4k views

What makes SHA256 secure?

For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem. What makes SHA256 and similar hash functions, of the same family, ...
1
vote
1answer
30 views

Number of preimages of hash function from bounded domain

Suppose we have an "ideal" cryptographic hash function $H: \{0,1\}^{n+k}\to \{0,1\}^{n}$ and a given bitstring $b\in \{0,1\}^{n}$, Can we estimate how many preimages $H^{-1}(b)$ there are? With ...
7
votes
1answer
182 views

SNARK-friendly one-way compression functions

I'm looking for a one-way compression function that is secure and efficient within a zk-SNARK circuit. The motivation behind this comes from these considerations: SHA256-compression is highly ...
6
votes
1answer
171 views

Partial collisions of hashes, why is this important?

There's a lot of work finding "partial collisions" in hashes, and "Parallel Collision Search with Cryptanalytic Applications" seems to be the go-to paper for this work. I'm trying to understand why ...
3
votes
1answer
152 views

Does Composition of compressing Collision Resistant Hash Functions $H^{*}=H_2(H_1(x))$ is Collision Resistant?

I'm trying to solve the following problem: Given two CRHF $H_1:2^{4n}\to2^{2n}$, $H_2:2^{2n}\to 2^n$, construct the following hash function $H^{*}=H_2(H_1(x))$ compressing from $2^{4n}\to 2^n$. We ...
-4
votes
2answers
294 views

AES_256_ENCRYPT_CTR(key, sha-1(plainText)+plainText) VS AES-GCM, which is more secure? [duplicate]

What if we encrypt sha-1 hash of the plain text, along with the plain text using AES-256 in CTR mode? How much future proof the above method would be in comparison to AES-GCM or any other method ...
0
votes
1answer
1k views

Hash Collision Probabilities

Please give help! how can I calculate the probability of collision? I need a mathematical equation for my studying. Assume, I am using SHA256 to hash 100-bits. Thus: SHA256 {100} = 256-bits (hash ...
1
vote
2answers
128 views

On a lower bound for the birthday problem

I'm now familiar with a lower bound for the birthday problem as exposed in the theorem A.16 of Katz and Lindell book (alternatively see this webpage). If one denotes by $C(q,N)$ the probability of ...