Questions tagged [collision-resistance]
Difficulty of finding two different inputs that hash to the same value
697
questions
1
vote
1
answer
45
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 ...
- 113
0
votes
1
answer
69
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 ...
- 111
1
vote
1
answer
129
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 ...
- 115
1
vote
0
answers
38
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 ...
- 115
2
votes
1
answer
89
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 ...
- 143
1
vote
1
answer
33
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
62
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 \...
- 11
2
votes
2
answers
1k
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 ...
- 963
2
votes
1
answer
82
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 ...
- 95
3
votes
1
answer
59
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 ...
- 93
1
vote
0
answers
27
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 ...
- 47
2
votes
0
answers
43
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 ...
- 131
1
vote
1
answer
71
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 ...
- 425
1
vote
1
answer
121
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 ...
- 175
5
votes
2
answers
478
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 ...
- 51
2
votes
1
answer
56
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.
...
- 183
1
vote
1
answer
200
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 ...
- 47
0
votes
1
answer
142
views
Is it possible that two different messages have same hash code? [duplicate]
As I know a very common hash code has 256 bits.
From a message, it outputs a hash code that's 256 bits. That hash code should be unique to that message. That message can be something like email.
But a ...
2
votes
1
answer
107
views
Can I use last N blocks of AES-CBC +IV as hash?
Suppose I want to take advantage of hardware accelerated symmetric encryption like AES and use it to compute a “hash”. How collision resistant would it be if I’d take the IV + last N blocks of an AES ...
- 165
3
votes
1
answer
162
views
Will XORing two bad hashes lead to a collision resistant hash?
I'm reading the fourth edition of "Cryptography: Theory and Practice" by D.R. Stinson and M.B. Paterson.
In the book, they have mentioned the concept of "collision-resistant hash" ...
- 31
0
votes
1
answer
35
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 ...
- 1
4
votes
3
answers
214
views
Is the sum of hashes a suitable hash for sets?
Let $H: X \rightarrow \{0, 1\}^b$ denote a cryptographically secure, $b$-bits hash function on a set $X$. Let $H^*: \mathbb{P}(X) \rightarrow \{0, 1\}^b$ be a function on the power set of $X$ defined ...
- 1,365
1
vote
1
answer
99
views
Can I use a cryptographic hash function such as sha256 for Randomness Extraction [duplicate]
I want to transform a semi random input to a shorter, uniformly random bit string. Assuming there is enough entropy in the semi random input, can I use a collision resistant hash function to extract ...
1
vote
0
answers
78
views
Hash function collision resistance
I have a course work for university, and am not sure on my answer so if anyone could please take the time out to read the question and my answer to let me know if I'm going in the right direction that ...
- 77
1
vote
0
answers
81
views
Probability of getting a collision using chosen plaintext attacks
For university I am doing a piece of coursework right now. This question is focusing on CPA and collisions using CPA.
Question:
I have attempted to answer part 3, but am not very confident in the ...
- 77
1
vote
0
answers
108
views
AES-CBC collision resistance of hash function [closed]
I'm very new to cryptography and am having some issues with the following question
...
- 11
3
votes
0
answers
104
views
Is WPA2 collision-proof?
I was experimenting with hashcat and aircrack to test WiFi security.
The WiFi AP is a WPA2 encrypted network. The tool I used to ...
- 31
1
vote
0
answers
70
views
How many hashes to recover a salted password? [closed]
If a password p is selected from a space of 2^64 passwords, and the server stores this as a hash, h = SHA-256(p||s) where s is a random 128-bit salt. How many maximum hashes would an attacker need to ...
- 151
0
votes
0
answers
32
views
How to factor $n = p.q$, where $p,q$ are primes, knowing a multiple of $\mathrm{lcm}(p-1, q-1)$? [duplicate]
I was reading this post https://senderek.com/SDLH/ about Shamir's hash function, which is defined as follows:
Let $p,q$ be positive prime integers and let $n=p\times q$. Let $\ell = \mathrm{lcm}(p-1, ...
- 413
2
votes
1
answer
171
views
How do Pre-image, Second pre-image and collision resistance actually work? How does this affect data integrity?
I'm working on this past exam paper and found this question about pre-image resistance and its relation to data integrity:
Displaying the hash of a file on a website in order to provide data integrity ...
- 183
2
votes
1
answer
69
views
How does the SWIFFT algorithm relate finding hash collisions to a lattice problem?
I've been messing around with lattice based cryptography and came across the SWIFFT algorithm, a provably secure cryptographic hash function which has a security proof stating that finding collisions ...
- 25
0
votes
0
answers
132
views
What hashing algorithm is fast and good enough for checking if source data is changed?
Not sure if this falls into crypto from contextual point of view but it is about hashing algorithms. I have two directories -- assets/ and cache/. Anytime there is a file added, deleted, or changed in ...
- 113
1
vote
1
answer
139
views
Why is $\operatorname{Hash}(x \oplus y)$ not a secure proof-of-work algorithm?
$x$ is challenging string, $y$ is proof string. $\operatorname{H}$ is the proof-of-work (pow) function, to find a $y$ such that $H(x,y)<2^{256}/D$
$x ,y = \{ 0, 1 \}^{512}$
$\operatorname{H}(x,y) =...
- 13
1
vote
1
answer
250
views
Which hash functions provide 128 bit resistance?
I was wondering out of the functions (MD5, SHA-1, SHA-256, and SHA-512), do all provide 128-bit pre-image resistance and 128-bit second-image resistance?
Also, out of these hash functions, do only SHA-...
- 151
0
votes
1
answer
141
views
How to prove that a hash function is collision resistant if it's equal to that of a collision resistant hash function? [closed]
Given that H is a collision-resistant hash function from 2n-bit strings to n-bit strings.
How do I prove that Hash is collision-resistant if:
$$\text{Hash}(X_1∥X_2∥X_3) := \text{H}(X_1∥H(X_2∥X_3))$$
user104469
0
votes
1
answer
148
views
Is sha-256 better then sha-1 in aspects othen then the hash size?
Assume I create a hash using SHA-256 and then take only the first 160 bits of the hash, as the result. is the result more cryptographically secured than SHA-1? Or are the two algorithms equally secure ...
- 103
0
votes
1
answer
100
views
Security of 128-bit hash function with salt
Modern hash function have to be at least 256-bit, due to birthday attack. But let's consider 128-bit hash function which takes as an input:
plaintext $\oplus$ salt
Salt may be know to attacker. Do ...
- 1,171
0
votes
0
answers
89
views
Is there a special limit in the range of the hash function?
Is there a special limit in the range of the hash function?
More specifically, is it possible that there is a cryptographic hash function that outputs c-membered subsets of the n-membered set?
In ...
- 21
1
vote
1
answer
64
views
Can a cryptographic hash function that outputs a c-membered subset of the n-membered set?
Is it possible that there is a cryptographic hash function that outputs a c-membered subset of the n-membered set?
In other words, can the set of the binary representation of c-membered subsets of the ...
- 21
3
votes
1
answer
80
views
Avoid hash flooding without a secret key?
I'm currently building an implementation of the dynamo paper, yottastore. Imagine it as a huge, distributed, hash map.
To find the node holding a key, I use rendezvous hashing (an improvement over ...
- 133
1
vote
1
answer
65
views
How to complete this proof of statistically indistinguishable distributions?
Given that:
$$ SD\bigg( (r, \langle r, s \rangle),(r, b) \bigg) < \mathrm{negl}(n)$$
where $SD$ stands for statistical distance, $r$ is random uniform in $\{0,1\}^n$, $s$ is random uniform in $S \...
- 321
0
votes
0
answers
38
views
Assumptions used for Designing Homomorphic CRHF
What are the possible assumptions that have been used or can be used for designing the homomorphic Collision Resistant Hash function (CRHF)? I know Short Integer Solution (SIS) is one of the ...
0
votes
1
answer
67
views
Double hashing scheme on not collision resistant hash
Given an hash H that is not collision resistant, for example 80-bit digest, if we use the following double hashing scheme: H(SHA2-256(x)).
Does this scheme increase the collision resistance?
- 1
1
vote
0
answers
28
views
Does a salt by a trusted party remove the need for collision resistance for a binding commitment?
Say a Human is operating their trusted computer, Alice, and Human wants to hand copy a collision resistant commitment, with a security factor of 128 from Bob on to paper. Naturally we want the ...
- 488
1
vote
1
answer
143
views
Does RIPEMD-320 provides the same level of security as RIPEMD-160?
This article from Wikipedia claims that "256- and 320-bit versions of RIPEMD provide the same level of security as RIPEMD-128 and RIPEMD-160, respectively".
Is that true or false ? And why ?
- 57
0
votes
4
answers
612
views
Is 32 bytes enough for a hash and would anything else be 'overengineering'?
For data integrity, specifically for small blocks of data, rather than using a SHA-256 hash, or simply truncating a SHA-512 hash, I am playing with the following idea:
...
- 293
1
vote
0
answers
56
views
Compute a hash function given commitment to some secret element
Given a secret key x and a commitment to it comm(x) where comm(x) is both binding and hiding (it can be for example $g^x$ or some homomorphic encryption). Given public parameters $P_1,...,P_k$, comm(x)...
- 79
0
votes
0
answers
106
views
Determine if a Hash function is pre-image resistant and collision free
I'm so confused by this kind of exercise.
We have that $n = p * q$, where $p$ and $q$ are prime numbers. Let's examine this hash function:
$h(x) = x^2 \mod n$.
Determine if the hash function is pre-...
0
votes
0
answers
69
views
Can we combine two AES (with block size 128) to to a block cipher with a block size 192 which is collision-resistant?
Encrypting values with AES we only need about $2^{64}$ trials until we finding an already used value (some collision). This can be done these days with easy.
To make this harder can we combine two AES ...
- 505
0
votes
1
answer
67
views
Proof of computationally binding correct?
I have defined the following commitment scheme and would like to prove that it is statistically hiding and computationally binding, but I'm not sure if my proof is accurate:
For $h$, a collision ...
- 321