Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

Is it possible for a given plaintext and ciphertext to have two different keys? [duplicate]

This has probably been asked before but for a given ciphertext and plaintext pair, is it possible to have two different keys producing said pair? Or there are no collisions in AES, unlike hashing ...
3 votes
2 answers
226 views

Can a collision resistant hash return zero?

Recently, I have been reading the original proof of GCM. It mentioned the properties of "almost universal" and "return zero" for hash function. I wonder if there is a connection ...
0 votes
0 answers
76 views

What is the fastest 128-bit non-cryptographic hash function?

I need a 128-bit hash function which is extremely fast since it will be used for generating unique IDs for billions of objects. It doesn't need to be a cryptographic hash function nor does it have to ...
11 votes
1 answer
1k views

Collision resistance of hash function built on modular exponentiation

Consider the following hash function family for hashing integers: $Gen(1^k)$: generate 2 $k$-bit primes p,q. Let $n = pq$. Choose random $y \rightarrow QR_n$ and output $n,y$. $H_{(n,y)}(x) = y^x \...
1 vote
3 answers
116 views

Is the composition of a hash function with a block cipher collision resistant?

Assume $H$ is a collision resistant and preimage resistant (unkeyed) hash function and $E(k,y)$ is a block cipher where $k$ is the key. I am interested into the collision resistance of the composed ...
0 votes
0 answers
28 views

Calculating maximum plaintexts without birthday collisions given a probability, when the encryption scheme has multiple parts?

I'm sorry if the answer to this is actually simpler than it seems to me. I'm running AES-GCM to encrypt some data keys, but I don't actually know how to go about calculating the probability of ...
2 votes
1 answer
92 views

Difficulty of finding a claw for AES-CMAC

Consider the problem of finding two keys K1 and K2, such that for two distinct plaintexts P1 and P2, AES-CMAC(K1, P1) = AES-CMAC(K2, P2). Is this problem any easier than brute-forcing? If so, how much ...
1 vote
0 answers
30 views

Grow-only set homomorphic hash function from semigroup?

I have been exploring Bellare and Micciancio's "randomize-then-combine" paradigm for deriving set homomorphic hashing functions. I am particularly interested in grow-only sets, such that ...
1 vote
1 answer
78 views

Security of this MAC scheme

I'm studying for a cryptography exam, I have this question from a past exam: Consider the MAC with key $k$, based on a block cipher $E_{(k)}$ with block size $n$, and a collision-resistant hash ...
1 vote
1 answer
1k views

What does the 256 in SHA3-256 and SHAKE256 refer to?

I am simply wondering what the bit-length in the algorithm variant in the table below refers to? For the hash functions I assume that this refers to the ouput length in bits. For instance for SHA3-256 ...
2 votes
1 answer
778 views

What is the advantage of using hash function families instead of a single hash function?

My guess would be that families are more secure. In which way though? I have seen claims that hash function families can be collision resistant while single hash functions can not be. Is this true? ...
4 votes
0 answers
141 views

Is the XOR-combiner of independent keyed hash-functions collision resistant?

Assume there are two keyed hash-functions $H_1(k_1, m)$ and $H_2(k_2, m)$, with $k_1$ and $k_2$ being independently randomly sampled public keys. The XOR-combiner is defined as $C_\oplus^{H_1, H_2}:=...
2 votes
1 answer
96 views

Merkle tree alternating hash and polynomial

I want to get feedback on the security of a modified merkle tree data structure. Using the image above as a reference assume I have a random oracle function $H$. Assume $H$ outputs a value in $\mathbb{...
0 votes
0 answers
166 views

Is the following hash function construction collision resistant?

The problem Let the following function be a collision reisistant hash function $$H=\{H_s:\{0,1\}^{2n} \rightarrow \{0,1\}^{n} \}$$ Let the following function be a PRG $$G:\{0,1\}^{n+1} \rightarrow \{0,...
0 votes
1 answer
73 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 ...
0 votes
1 answer
127 views

Set with probability of SHA-3 collisions lower than for a random oracle?

Can we define one finite set of input strings for a SHA-3 hash (or SHAKE XOF) function so that the collision probability is arguably lower than for a random oracle, with a definition of the set making ...
3 votes
2 answers
759 views

How much entropy is lost due to collision?

If entropy is hashed with SHA-256 for example, and the input has exactly 256 entropy bits, how much entropy is reduced after hashing due to collision? Is there any reference that explains how to ...
25 votes
1 answer
20k views

What are the odds of collisions for a hash function with 256-bit output?

There are some related questions on the net but I did not understand their solutions. I am reading in a textbook about methods of finding a collision. It states to consider a collision for a hash ...
2 votes
1 answer
470 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-...
0 votes
0 answers
131 views

Do "superfast" keyed hash functions exist?

A common family of requirements for (cryptographic) keyed hash functions is that the function $h(k,-)$ should have good collision resistance for all keys $k$, even if the key $k$ is known to the ...
4 votes
1 answer
546 views

What are the “costs” to find a pre-image, weak collision, or strong collision?

For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?
105 votes
3 answers
123k views

Why haven't any SHA-256 collisions been found yet?

I've been thinking about this for a few days, a SHA-256 algorithm outputs 64 characters which can either be a lowercase letter or a number from 0-9. Which should mean that there are 64^36 distinct SHA-...
1 vote
1 answer
111 views

Hash-Then-Encrypt or Encrypt-Then-Hash on Keyed Hash Functions

I have seen other answers here on Stack Exchange regarding MAC-Then-Encrypt vs. Encrypt-Then-MAC (and this article regarding MAC-Then-Encrypt padding oracle attacks on SSL) as well as generic Hash-...
0 votes
0 answers
67 views

Having trouble providing a distinguisher proving this hash function is not collision-resistant

As suggested by the title, I'm working on an exercise where I'm given a hash function $H$ that takes in an input string $x$. I'm supposed to construct a distinguisher that proves $H$ isn't collision-...
1 vote
1 answer
98 views

Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

I came upon the following hash function (pseudo-code): ...
2 votes
2 answers
173 views

A question about "attacks on MAC key space"

At page 336 in "Handbook of Applied Cryptography - Menezes", I see the sentence For $n$-bit MAC with $t$-bit key space this requires $2^t$ MAC operations, after which one expects $1+2^{(t-n)...
1 vote
0 answers
68 views

Is it possible to get the negative point with −x in that version of the Pedersen hash over the BaybyJubJub curve?

The Pedersen hash is a low constraints friendly hash for Zk-Snarks. Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
1 vote
1 answer
44 views

Collision ISIS Problem

I'm trying to understand the inhomogeneous SIS problem and I'm came across to a scenario that I don't know how to evaluate. Let $A,B \in \mathbb{Z}_q^{n\times m}$ be two random matrixes and $u,v \in \...
1 vote
1 answer
292 views

Pedersen Hash : when truncating the hash to keep only the X coordinate, is it possible to compute a collision when the Babyjubjub curve is used?

The Pedersen hash is a low constraints friendly hash for Zk-Snarks. Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
2 votes
0 answers
103 views

Security of Even-Mansour based Merkle-Damgård

Assuming I have single-key Even-Mansour with single $2n$-bit permutation in wide-pipe Merkle-Damgård specifically with Matyas-Meyer-Oseas mode outputting $n$-bit hash. What security can I expect ...
2 votes
1 answer
117 views

Recommended output filter for Rumba20 [closed]

Rumba20 is a compression function that maps a 192-byte (1536-bit) string to a 64-byte (512-bit) string. It's designed to provide collision resistance by using Salsa20 (or ChaCha20) with the ...
0 votes
1 answer
137 views

If we supply a random uuid4 hashed salt to Hashid, will it be considered secure?

Ideally, Hashids -: https://pypi.org/project/hashID/ are considered insecure and it is recommended that we should not use them for any sensitive functions. Though, is a HashId considered secure if we ...
0 votes
1 answer
100 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-...
5 votes
1 answer
114 views

The rigorous proof in the commitment based on CRHF

I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous ...
3 votes
1 answer
81 views

Analyzing the security of hash approaches

Say that I have a random oracle function $H$. This function outputs a value in $\mathbb{F}_{p}$ where $p \approx 2^{256}$. $H$ can accept either one or two inputs (outputting a single value in both ...
2 votes
1 answer
206 views

Implementing a Merkle tree using a 128 bit hash function?

I need to implement a Merkle tree using a 128 bit hash function. In general, any hash function that guarantees pre-image, second pre-image and collission resistance should be fine to implement a ...
2 votes
1 answer
144 views

theoretical hash collisions vs random number collisions

I have a theoretical question about the probability of collisions of hashes versus random numbers. I'm not interested in the exact probabilities. The exact hash function is not relevant (we can assume ...
3 votes
0 answers
111 views

Are there "light" versions of cryptographic hash functions?

After tinkering with cryptographic hash functions, I started wondering if they do have counterpart functions that would imitate their cryptographic properties but with a lower level of strength in ...
4 votes
1 answer
247 views

very smooth hash (VSH) Stepwise examples

Can someone please point me to or give me stepwise example of VSH hash function. I couldn't find an example or a reference implementation. I tried to go through original publication but it seems way ...
1 vote
1 answer
85 views

Hardening a polynomial checksum scheme

I have a checksum scheme that uses a simple polynomial summation as described here. Basically I'll take a random value $R$ and a set of inputs $[v_0, v_1, v_2]$ and checksum it like $v_0*R + v_1*R^2 + ...
1 vote
1 answer
76 views

Hash Flooding a Randomized Modular Hash Table

Assume we have a hash table using the function h(x) = x mod 32. h(x) = x mod 33. Also assume it dynamically resizes by doubling the amount of buckets and rehashing. If I was able to provide inputs for ...
0 votes
1 answer
381 views

Checking encoded strings for a hash collision in Python [closed]

There is a common term used in cryptography called a hash collision. If I am reading the definition correctly on Wikipedia, this can occur if two different data values give rise to the same hash ...
1 vote
0 answers
68 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 ...
1 vote
1 answer
169 views

Does an increase of message size increase the number of guesses to find a collision?

If I hash a 256-bit message and generate an output digest of the same size with a cryptographic hash function then the number of guesses to find a collision is expected to be 2^128. Does increasing ...
2 votes
1 answer
217 views

Confusion+Diffusion comparison table? (e.g. with Avalanche Criterion / SAC)

I'm looking for a general comparison of encryption algorithms in regard to Confusion and Diffusion (as defined by Claude Shannon), and if possible, specifically for their SAC and BIC quality. For ...
1 vote
1 answer
43 views

Is a single 256 bits hash table in which the digests are from mixed cryptographic hashing algorithms still considered collision resistant?

Consider a single hash table containing digests from about 10 different 256 bits cryptographic hashing functions, like SHA256, SHA3, KECCACK256, BLAKE2, BLAKE3, etc... Is such table still considered ...
1 vote
0 answers
87 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 \...
2 votes
2 answers
2k views

Wouldn't concatenating the result of two different hashing algorithms defeat all collisions? [duplicate]

Let's say I have three messages: A B C And I run each of these through two different ...
2 votes
1 answer
117 views

Is there a CRHF based on integer factorization problem or RSA assumption

We know that in the black-box sense, we cannot use one-way functions to construct Collision Resistant Hash Functions.I feel that in my impression, I have never seen CRHF based on integer factorization ...
3 votes
1 answer
182 views

UOWHF vs CRHF / Relevance of UOWHF

What's the difference between UOWHF and CRHF and why are UOWHF useful? As far as I understand, Universal One-Way Hash Functions are an alternative to CRHF. While for CRHF it is hard, given randomly ...

1
2 3 4 5
15