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 ...
- 139k
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
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 ...
- 89.2k
1
vote
1
answer
127
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 ...
- 89.2k
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 ...
- 132k
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 ...
- 132k
1
vote
0
answers
60
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
1
answer
364
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-...
- 61
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 ...
- 218
2
votes
1
answer
81
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 ...
- 5,053
2
votes
1
answer
56
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 ...
- 2,523
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
2
votes
2
answers
624
views
Examine whether a hash function is collision-resistant
Assume a collision-resistant hash function $h$ which compresses sequences of length $2n$ to length $n$. It must be examined whether the hash function which compresses seqs. length $4n$ to $n$:
$$
h_1(...
- 173
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
0
votes
1
answer
74
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-...
CommunityBot
- 1
19
votes
1
answer
1k
views
Overview of relations between cryptographic primitives?
Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives?
More specifically, I am looking for something ...
- 519
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 ...
- 139k
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
42
votes
4
answers
40k
views
Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
I would like to maintain a list of unique data blocks (up to 1MiB in size), using the SHA-256 hash of the block as the key in the index. Obviously there is a chance of hash collisions, so what is the ...
- 1,031
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.
...
- 18.2k
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" ...
- 132k
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 ...
CommunityBot
- 1
1
vote
1
answer
199
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 ...
- 19.1k
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
0
votes
1
answer
141
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 ...
4
votes
2
answers
5k
views
Are SHA-256 and SHA-512 collision resistant?
Context: Designing a TinyUrl system. The user inputs a lengthy URL and the system computes the hash and encodes it binary64 and sends it back to the user.
From what I understood so far (from this ...
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 ...
36
votes
2
answers
53k
views
Why is HMAC-SHA1 still considered secure?
This Q & A https://security.stackexchange.com/questions/33123/hotp-with-as-hmac-hashing-algoritme-a-hash-from-the-sha-2-family
says that the security of HMAC-SHA1 does not depend on resistance to ...
- 132k
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 ...
- 132k
1
vote
1
answer
96
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 ...
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 ...
1
vote
1
answer
7k
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 ...
- 45.7k
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
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 ...
- 132k
2
votes
3
answers
231
views
Reversing hash function makes possibilities increase exponentially, yet there is a finite number of inputs. How?
When trying to reverse a hash function, there is loss, e.g.
a+b=c
given c=5, try to go back to a,b (previous step)
(a,b)=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)
but, ...
- 2,523
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
129
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) =...
- 89.2k
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-...
- 45.7k
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))$$
- 440
0
votes
1
answer
147
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 ...
- 132k
123
votes
7
answers
214k
views
Are there two known strings which have the same MD5 hash value?
Is there an example of two known strings which have the same MD5 hash value (representing a so-called "MD5 collision")?
- 53
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,900
1
vote
1
answer
62
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 ...
- 18.2k
0
votes
0
answers
87
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