Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
725
questions
2
votes
1
answer
46
views
Is it hard to find m, R to make RG^H(m||R)=C?
Assuming the generator of one group $\mathbb G$ is $G$. Given an element $C\in \mathbb G$ and a cryptographic hash function $H(\cdot)$, is it hard for one adversary to find a pair of message $m$ and ...
0
votes
0
answers
32
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 ...
0
votes
0
answers
84
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 ...
1
vote
3
answers
118
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
94
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
31
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 ...
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
783
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? ...
0
votes
0
answers
167
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
128
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
761
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 ...
0
votes
0
answers
133
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 ...
1
vote
1
answer
112
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
69
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
100
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
175
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
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
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. ...
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
121
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 ...
1
vote
1
answer
296
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. ...
0
votes
1
answer
140
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 ...
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 ...
2
votes
1
answer
211
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 ...
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
145
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 ...
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 ...
4
votes
1
answer
249
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 ...
2
votes
1
answer
97
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{...
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
391
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
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 ...
1
vote
0
answers
69
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 ...
2
votes
1
answer
225
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
90
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
118
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
184
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
vote
0
answers
41
views
Checksum algorithm using system of multivariate polynomials
I'm working on a protocol that uses zero-knowledge proofs. I'm looking at systems of polynomial equations as cheap solutions for checksumming data. Note, I'm not looking for trapdoor functionality ...
2
votes
0
answers
69
views
Is there any standard extension of the Merkle-Damgård transform that handles arbitrary-length inputs?
I have seen multiple sources claim that the Merkle-Damgård transform is able to build a collision-resistant Hash-function $H$ for arbitrary-length inputs from a compression function $h : \{0,1\}^n \to ...
1
vote
1
answer
107
views
Does a salted password hash reveal info about the password?
Assume a password is hashed with a secure salt, e.g. hash = sha256(password+salt). If the hash and the salt are made public, an attacker can perform an attack by ...
1
vote
1
answer
178
views
Probability of a collision in the sum of hashed 64-bit values
I'm working on a problem where I need to track some state that's 64-bit integers. It turns out this state can tracked by simply accumulating a sum of differences, which in my case turns out to ...
5
votes
2
answers
645
views
Does using multiple hashes (to check if a file has been spoofed) reduce collisions?
I'm trying to create a script that will take a snapshot of the contents of a directory. For each file, all possible metadata will be recorded and written to the database. The point is that with some ...
2
votes
1
answer
124
views
Free-start collision vs Semi-free-start collision
Recently, I am very interested in the hash function attack paper, so I am reading it closely.
I found out that there are Free-start and Semi-free-start settings among the attacks on the hash function.
...
1
vote
1
answer
254
views
Data fingerprint using polynomial and Schwartz-Zippel Lemma
I'm working on a protocol and am looking for a way to fingerprint a set of elements. All elements are evenly distributed across a finite field that is integers modulus $2^{256}$.
Assume I have a set ...